DFG should be able to constant-fold strings
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 9 Mar 2016 05:16:47 +0000 (05:16 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 9 Mar 2016 05:16:47 +0000 (05:16 +0000)
https://bugs.webkit.org/show_bug.cgi?id=155200

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

This adds constant-folding of string1 + string2 and string.length. The actual folding
rule is easy, but there are some gotchas.

The problem is that the DFG cannot allocate new JSString objects until we are on the
main thread. So, DFG IR must have a node for a JSValue string constant that hasn't been
created yet - i.e. it doesn't have any concrete JSValue bits yet.

We have the ability to speak of such things, using LazyJSValue. But that's a class, not
a node type. This patch now adds a node type, LazyJSConstant, which is a Node that holds
a LazyJSValue.

This puts us in a weird situation: AI uses JSValue to represent constants. It would take
a lot of work to change it to use LazyJSValue. So, this implements the constant folding
in StrengthReductionPhase. I created a bug and put a FIXME about moving these rules into
AI.

OTOH, our experience in B3 shows that constant folding in strength reduction is quite
nice. It would totally make sense to have strength reduction have constant folding rules
that mirror the rules in AI, or to factor out the AI constant folding rules, the same
way that B3 factors out those rules into Value methods.

Another issue is how to represent the cumulative result of possibly many foldings. I
initially considered adding LazyJSValue kinds that represented concatenation. Folding
the concatenation to a constant meand that this constant was actually a LazyJSValue that
represented the concatenation of two other things. But this would get super messy if we
wanted to fold an operation that uses the results of another folded operation.

So, the JIT thread folds string operations by creating a WTF::String that contains the
result. The DFG::Graph holds a +1 on the underlying StringImpl, so we can pass the
StringImpl* around without reference counting. The LazyJSValue now has a special kind
that means: we created this StringImpl* on the JIT thread, and once the JIT is done, we
will relinquish ownership of it. LazyJSValue has some magic to emit code for these
to-be-created-JSStrings while also transferring ownership of the StringImpl from the JIT
thread to the main thread and registering the JSString with the GC.

This just implements folding for concatenation and GetArrayLength. It's just a proof of
concept for evil things I want to do later.

This change is a 2.5x speed-up on the string concatenation microbenchmarks I added in
this patch.

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGFrozenValue.cpp:
(JSC::DFG::FrozenValue::emptySingleton):
(JSC::DFG::FrozenValue::tryGetString):
(JSC::DFG::FrozenValue::dumpInContext):
* dfg/DFGFrozenValue.h:
(JSC::DFG::FrozenValue::strength):
* dfg/DFGGraph.h:
* dfg/DFGLazyJSValue.cpp:
(JSC::DFG::LazyJSValue::newString):
(JSC::DFG::LazyJSValue::getValue):
(JSC::DFG::equalToStringImpl):
(JSC::DFG::LazyJSValue::tryGetStringImpl):
(JSC::DFG::LazyJSValue::tryGetString):
(JSC::DFG::LazyJSValue::strictEqual):
(JSC::DFG::LazyJSValue::switchLookupValue):
(JSC::DFG::LazyJSValue::emit):
(JSC::DFG::LazyJSValue::dumpInContext):
* dfg/DFGLazyJSValue.h:
(JSC::DFG::LazyJSValue::LazyJSValue):
(JSC::DFG::LazyJSValue::knownStringImpl):
(JSC::DFG::LazyJSValue::kind):
(JSC::DFG::LazyJSValue::tryGetValue):
(JSC::DFG::LazyJSValue::character):
(JSC::DFG::LazyJSValue::stringImpl):
* dfg/DFGMayExit.cpp:
(JSC::DFG::mayExit):
* dfg/DFGNode.cpp:
(JSC::DFG::Node::convertToIdentityOn):
(JSC::DFG::Node::convertToLazyJSConstant):
(JSC::DFG::Node::convertToPutHint):
(JSC::DFG::Node::convertToPutClosureVarHint):
(JSC::DFG::Node::tryGetString):
(JSC::DFG::Node::promotedLocationDescriptor):
* dfg/DFGNode.h:
(JSC::DFG::Node::convertToConstant):
(JSC::DFG::Node::convertToConstantStoragePointer):
(JSC::DFG::Node::castConstant):
(JSC::DFG::Node::hasLazyJSValue):
(JSC::DFG::Node::lazyJSValue):
(JSC::DFG::Node::initializationValueForActivation):
* dfg/DFGNodeType.h:
* dfg/DFGPredictionPropagationPhase.cpp:
(JSC::DFG::PredictionPropagationPhase::propagate):
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileSetRegExpObjectLastIndex):
(JSC::DFG::SpeculativeJIT::compileLazyJSConstant):
* dfg/DFGSpeculativeJIT.h:
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGStrengthReductionPhase.cpp:
(JSC::DFG::StrengthReductionPhase::handleNode):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileInt52Constant):
(JSC::FTL::DFG::LowerDFGToB3::compileLazyJSConstant):
(JSC::FTL::DFG::LowerDFGToB3::compileDoubleRep):

Source/WTF:

Also disable assertions about reference counting strings on the JIT thread. We will do
that now and it's OK.

* wtf/text/StringImpl.h:
(WTF::StringImpl::ref):
(WTF::StringImpl::deref):

LayoutTests:

* js/regress/script-tests/strcat-const.js: Added.
(foo):
(bar):
* js/regress/script-tests/strcat-length-const.js: Added.
(foo):
(bar):
* js/regress/strcat-const-expected.txt: Added.
* js/regress/strcat-const.html: Added.
* js/regress/strcat-length-const-expected.txt: Added.
* js/regress/strcat-length-const.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@197833 268f45cc-cd09-0410-ab3c-d52691b4dbfc

33 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/script-tests/strcat-const.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/strcat-length-const.js [new file with mode: 0644]
LayoutTests/js/regress/strcat-const-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/strcat-const.html [new file with mode: 0644]
LayoutTests/js/regress/strcat-length-const-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/strcat-length-const.html [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGFrozenValue.cpp
Source/JavaScriptCore/dfg/DFGFrozenValue.h
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGJITFinalizer.cpp
Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp
Source/JavaScriptCore/dfg/DFGLazyJSValue.h
Source/JavaScriptCore/dfg/DFGMayExit.cpp
Source/JavaScriptCore/dfg/DFGNode.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/text/StringImpl.h

index f97c98a..3ca641d 100644 (file)
@@ -1,3 +1,21 @@
+2016-03-08  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to constant-fold strings
+        https://bugs.webkit.org/show_bug.cgi?id=155200
+
+        Reviewed by Geoffrey Garen.
+
+        * js/regress/script-tests/strcat-const.js: Added.
+        (foo):
+        (bar):
+        * js/regress/script-tests/strcat-length-const.js: Added.
+        (foo):
+        (bar):
+        * js/regress/strcat-const-expected.txt: Added.
+        * js/regress/strcat-const.html: Added.
+        * js/regress/strcat-length-const-expected.txt: Added.
+        * js/regress/strcat-length-const.html: Added.
+
 2016-03-08  Joseph Pecoraro  <pecoraro@apple.com>
 
         Web Inspector: Add Heap domain start/stop tracking commands
diff --git a/LayoutTests/js/regress/script-tests/strcat-const.js b/LayoutTests/js/regress/script-tests/strcat-const.js
new file mode 100644 (file)
index 0000000..d20c0b9
--- /dev/null
@@ -0,0 +1,16 @@
+function foo(a, b) {
+    return a + b;
+}
+
+function bar() {
+    return foo("hello ", "world!");
+}
+
+noInline(bar);
+
+var result;
+for (var i = 0; i < 1000000; ++i)
+    result = bar();
+
+if (result != "hello world!")
+    throw "Error: bad result: " + result;
diff --git a/LayoutTests/js/regress/script-tests/strcat-length-const.js b/LayoutTests/js/regress/script-tests/strcat-length-const.js
new file mode 100644 (file)
index 0000000..87e2f7b
--- /dev/null
@@ -0,0 +1,16 @@
+function foo(a, b) {
+    return (a + b).length;
+}
+
+function bar() {
+    return foo("hello ", "world!");
+}
+
+noInline(bar);
+
+var result;
+for (var i = 0; i < 1000000; ++i)
+    result = bar();
+
+if (result != "hello world!".length)
+    throw "Error: bad result: " + result;
diff --git a/LayoutTests/js/regress/strcat-const-expected.txt b/LayoutTests/js/regress/strcat-const-expected.txt
new file mode 100644 (file)
index 0000000..cb2d30e
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/strcat-const
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/js/regress/strcat-const.html b/LayoutTests/js/regress/strcat-const.html
new file mode 100644 (file)
index 0000000..4d3ed63
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/strcat-const.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/js/regress/strcat-length-const-expected.txt b/LayoutTests/js/regress/strcat-length-const-expected.txt
new file mode 100644 (file)
index 0000000..d91448d
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/strcat-length-const
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/js/regress/strcat-length-const.html b/LayoutTests/js/regress/strcat-length-const.html
new file mode 100644 (file)
index 0000000..a09bdae
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/strcat-length-const.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
index a32bacc..92a611b 100644 (file)
@@ -1,3 +1,122 @@
+2016-03-08  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to constant-fold strings
+        https://bugs.webkit.org/show_bug.cgi?id=155200
+
+        Reviewed by Geoffrey Garen.
+
+        This adds constant-folding of string1 + string2 and string.length. The actual folding
+        rule is easy, but there are some gotchas.
+
+        The problem is that the DFG cannot allocate new JSString objects until we are on the
+        main thread. So, DFG IR must have a node for a JSValue string constant that hasn't been
+        created yet - i.e. it doesn't have any concrete JSValue bits yet.
+
+        We have the ability to speak of such things, using LazyJSValue. But that's a class, not
+        a node type. This patch now adds a node type, LazyJSConstant, which is a Node that holds
+        a LazyJSValue.
+
+        This puts us in a weird situation: AI uses JSValue to represent constants. It would take
+        a lot of work to change it to use LazyJSValue. So, this implements the constant folding
+        in StrengthReductionPhase. I created a bug and put a FIXME about moving these rules into
+        AI.
+
+        OTOH, our experience in B3 shows that constant folding in strength reduction is quite
+        nice. It would totally make sense to have strength reduction have constant folding rules
+        that mirror the rules in AI, or to factor out the AI constant folding rules, the same
+        way that B3 factors out those rules into Value methods.
+
+        Another issue is how to represent the cumulative result of possibly many foldings. I
+        initially considered adding LazyJSValue kinds that represented concatenation. Folding
+        the concatenation to a constant meand that this constant was actually a LazyJSValue that
+        represented the concatenation of two other things. But this would get super messy if we
+        wanted to fold an operation that uses the results of another folded operation.
+
+        So, the JIT thread folds string operations by creating a WTF::String that contains the
+        result. The DFG::Graph holds a +1 on the underlying StringImpl, so we can pass the
+        StringImpl* around without reference counting. The LazyJSValue now has a special kind
+        that means: we created this StringImpl* on the JIT thread, and once the JIT is done, we
+        will relinquish ownership of it. LazyJSValue has some magic to emit code for these
+        to-be-created-JSStrings while also transferring ownership of the StringImpl from the JIT
+        thread to the main thread and registering the JSString with the GC.
+
+        This just implements folding for concatenation and GetArrayLength. It's just a proof of
+        concept for evil things I want to do later.
+
+        This change is a 2.5x speed-up on the string concatenation microbenchmarks I added in
+        this patch.
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGDoesGC.cpp:
+        (JSC::DFG::doesGC):
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        * dfg/DFGFrozenValue.cpp:
+        (JSC::DFG::FrozenValue::emptySingleton):
+        (JSC::DFG::FrozenValue::tryGetString):
+        (JSC::DFG::FrozenValue::dumpInContext):
+        * dfg/DFGFrozenValue.h:
+        (JSC::DFG::FrozenValue::strength):
+        * dfg/DFGGraph.h:
+        * dfg/DFGLazyJSValue.cpp:
+        (JSC::DFG::LazyJSValue::newString):
+        (JSC::DFG::LazyJSValue::getValue):
+        (JSC::DFG::equalToStringImpl):
+        (JSC::DFG::LazyJSValue::tryGetStringImpl):
+        (JSC::DFG::LazyJSValue::tryGetString):
+        (JSC::DFG::LazyJSValue::strictEqual):
+        (JSC::DFG::LazyJSValue::switchLookupValue):
+        (JSC::DFG::LazyJSValue::emit):
+        (JSC::DFG::LazyJSValue::dumpInContext):
+        * dfg/DFGLazyJSValue.h:
+        (JSC::DFG::LazyJSValue::LazyJSValue):
+        (JSC::DFG::LazyJSValue::knownStringImpl):
+        (JSC::DFG::LazyJSValue::kind):
+        (JSC::DFG::LazyJSValue::tryGetValue):
+        (JSC::DFG::LazyJSValue::character):
+        (JSC::DFG::LazyJSValue::stringImpl):
+        * dfg/DFGMayExit.cpp:
+        (JSC::DFG::mayExit):
+        * dfg/DFGNode.cpp:
+        (JSC::DFG::Node::convertToIdentityOn):
+        (JSC::DFG::Node::convertToLazyJSConstant):
+        (JSC::DFG::Node::convertToPutHint):
+        (JSC::DFG::Node::convertToPutClosureVarHint):
+        (JSC::DFG::Node::tryGetString):
+        (JSC::DFG::Node::promotedLocationDescriptor):
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::convertToConstant):
+        (JSC::DFG::Node::convertToConstantStoragePointer):
+        (JSC::DFG::Node::castConstant):
+        (JSC::DFG::Node::hasLazyJSValue):
+        (JSC::DFG::Node::lazyJSValue):
+        (JSC::DFG::Node::initializationValueForActivation):
+        * dfg/DFGNodeType.h:
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        (JSC::DFG::PredictionPropagationPhase::propagate):
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileSetRegExpObjectLastIndex):
+        (JSC::DFG::SpeculativeJIT::compileLazyJSConstant):
+        * dfg/DFGSpeculativeJIT.h:
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGStrengthReductionPhase.cpp:
+        (JSC::DFG::StrengthReductionPhase::handleNode):
+        * ftl/FTLCapabilities.cpp:
+        (JSC::FTL::canCompile):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNode):
+        (JSC::FTL::DFG::LowerDFGToB3::compileInt52Constant):
+        (JSC::FTL::DFG::LowerDFGToB3::compileLazyJSConstant):
+        (JSC::FTL::DFG::LowerDFGToB3::compileDoubleRep):
+
 2016-03-08  Joseph Pecoraro  <pecoraro@apple.com>
 
         Web Inspector: Memory Timeline should show MemoryPressure events
index 9cfb03f..977245a 100644 (file)
@@ -141,6 +141,21 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         setBuiltInConstant(node, *node->constant());
         break;
     }
+
+    case LazyJSConstant: {
+        LazyJSValue value = node->lazyJSValue();
+        switch (value.kind()) {
+        case LazyJSValue::KnownValue:
+            setConstant(node, value.value()->value());
+            break;
+        case LazyJSValue::SingleCharacterString:
+        case LazyJSValue::KnownStringImpl:
+        case LazyJSValue::NewStringImpl:
+            forNode(node).setType(m_graph, SpecString);
+            break;
+        }
+        break;
+    }
         
     case Identity: {
         forNode(node) = forNode(node->child1());
index d0f07d9..e0d67f0 100644 (file)
@@ -113,7 +113,7 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
     case Int52Constant:
         def(PureValue(node, node->constant()));
         return;
-        
+
     case Identity:
     case Phantom:
     case Check:
@@ -121,6 +121,11 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
     case CheckStructureImmediate:
         return;
         
+    case LazyJSConstant:
+        // We should enable CSE of LazyJSConstant. It's a little annoying since LazyJSValue has
+        // more bits than we currently have in PureValue.
+        return;
+        
     case ArithIMul:
     case ArithAbs:
     case ArithClz32:
index 49e8e9f..3846692 100644 (file)
@@ -47,6 +47,7 @@ bool doesGC(Graph& graph, Node* node)
     case JSConstant:
     case DoubleConstant:
     case Int52Constant:
+    case LazyJSConstant:
     case Identity:
     case GetCallee:
     case GetArgumentCount:
index cdd3e64..f33f877 100644 (file)
@@ -1451,6 +1451,7 @@ private:
         // Have these no-op cases here to ensure that nobody forgets to add handlers for new opcodes.
         case SetArgument:
         case JSConstant:
+        case LazyJSConstant:
         case DoubleConstant:
         case GetLocal:
         case GetCallee:
index a62c38d..39c09ad 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -28,6 +28,7 @@
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGLazyJSValue.h"
 #include "JSCInlines.h"
 
 namespace JSC { namespace DFG {
@@ -38,6 +39,11 @@ FrozenValue* FrozenValue::emptySingleton()
     return &empty;
 }
 
+String FrozenValue::tryGetString(Graph& graph)
+{
+    return LazyJSValue(this).tryGetString(graph);
+}
+
 void FrozenValue::dumpInContext(PrintStream& out, DumpContext* context) const
 {
     if (!!m_value && m_value.isCell())
index 094356f..c59abeb 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -93,6 +93,8 @@ public:
     
     // The strength of the value itself. The structure is almost always weak.
     ValueStrength strength() const { return m_strength; }
+
+    String tryGetString(Graph&);
     
     void dumpInContext(PrintStream& out, DumpContext* context) const;
     void dump(PrintStream& out) const;
index 5ec65b9..bbd46ea 100644 (file)
@@ -868,6 +868,7 @@ public:
     Bag<CallVarargsData> m_callVarargsData;
     Bag<LoadVarargsData> m_loadVarargsData;
     Bag<StackAccessData> m_stackAccessData;
+    Bag<LazyJSValue> m_lazyJSValues;
     Vector<InlineVariableData, 4> m_inlineVariableData;
     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
     HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
@@ -880,6 +881,9 @@ public:
     unsigned m_localVars;
     unsigned m_nextMachineLocal;
     unsigned m_parameterSlots;
+    
+    HashSet<String> m_localStrings;
+    HashMap<const StringImpl*, String> m_copiedStrings;
 
 #if USE(JSVALUE32_64)
     std::unordered_map<int64_t, double*> m_doubleConstantsMap;
index 1132fc9..57a5a1c 100644 (file)
@@ -82,6 +82,10 @@ bool JITFinalizer::finalizeFunction()
 
 void JITFinalizer::finalizeCommon()
 {
+    // Some JIT finalizers may have added more constants. Shrink-to-fit those things now.
+    m_plan.codeBlock->constants().shrinkToFit();
+    m_plan.codeBlock->constantsSourceCodeRepresentation().shrinkToFit();
+    
 #if ENABLE(FTL_JIT)
     m_jitCode->optimizeAfterWarmUp(m_plan.codeBlock);
 #endif // ENABLE(FTL_JIT)
index 6011490..0c2ed19 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2014, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #if ENABLE(DFG_JIT)
 
+#include "CCallHelpers.h"
+#include "DFGGraph.h"
 #include "JSCInlines.h"
+#include "LinkBuffer.h"
 
 namespace JSC { namespace DFG {
 
+LazyJSValue LazyJSValue::newString(Graph& graph, const String& string)
+{
+    LazyJSValue result;
+    result.m_kind = NewStringImpl;
+    result.u.stringImpl = graph.m_localStrings.add(string).iterator->impl();
+    return result;
+}
+
 JSValue LazyJSValue::getValue(VM& vm) const
 {
     switch (m_kind) {
@@ -40,6 +51,7 @@ JSValue LazyJSValue::getValue(VM& vm) const
     case SingleCharacterString:
         return jsSingleCharacterString(&vm, u.character);
     case KnownStringImpl:
+    case NewStringImpl:
         return jsString(&vm, u.stringImpl);
     }
     RELEASE_ASSERT_NOT_REACHED();
@@ -75,6 +87,48 @@ static TriState equalToStringImpl(JSValue value, StringImpl* stringImpl)
     return triState(WTF::equal(stringImpl, string));
 }
 
+const StringImpl* LazyJSValue::tryGetStringImpl() const
+{
+    switch (m_kind) {
+    case KnownStringImpl:
+    case NewStringImpl:
+        return u.stringImpl;
+
+    case KnownValue:
+        if (JSString* string = jsDynamicCast<JSString*>(value()->value()))
+            return string->tryGetValueImpl();
+        return nullptr;
+
+    default:
+        return nullptr;
+    }
+}
+
+String LazyJSValue::tryGetString(Graph& graph) const
+{
+    switch (m_kind) {
+    case NewStringImpl:
+        return u.stringImpl;
+
+    case SingleCharacterString:
+        return String(&u.character, 1);
+
+    default:
+        if (const StringImpl* string = tryGetStringImpl()) {
+            unsigned ginormousStringLength = 10000;
+            if (string->length() > ginormousStringLength)
+                return String();
+            
+            auto result = graph.m_copiedStrings.add(string, String());
+            if (result.isNewEntry)
+                result.iterator->value = string->isolatedCopy();
+            return result.iterator->value;
+        }
+        
+        return String();
+    }
+}
+
 TriState LazyJSValue::strictEqual(const LazyJSValue& other) const
 {
     switch (m_kind) {
@@ -85,6 +139,7 @@ TriState LazyJSValue::strictEqual(const LazyJSValue& other) const
         case SingleCharacterString:
             return equalToSingleCharacter(value()->value(), other.character());
         case KnownStringImpl:
+        case NewStringImpl:
             return equalToStringImpl(value()->value(), other.stringImpl());
         }
         break;
@@ -93,6 +148,7 @@ TriState LazyJSValue::strictEqual(const LazyJSValue& other) const
         case SingleCharacterString:
             return triState(character() == other.character());
         case KnownStringImpl:
+        case NewStringImpl:
             if (other.stringImpl()->length() != 1)
                 return FalseTriState;
             return triState(other.stringImpl()->at(0) == character());
@@ -101,8 +157,10 @@ TriState LazyJSValue::strictEqual(const LazyJSValue& other) const
         }
         break;
     case KnownStringImpl:
+    case NewStringImpl:
         switch (other.m_kind) {
         case KnownStringImpl:
+        case NewStringImpl:
             return triState(WTF::equal(stringImpl(), other.stringImpl()));
         default:
             return other.strictEqual(*this);
@@ -143,6 +201,45 @@ uintptr_t LazyJSValue::switchLookupValue(SwitchKind kind) const
     }
 }
 
+void LazyJSValue::emit(CCallHelpers& jit, JSValueRegs result) const
+{
+    if (m_kind == KnownValue) {
+        jit.moveValue(value()->value(), result);
+        return;
+    }
+
+    // It must be some kind of cell.
+#if USE(JSVALUE32_64)
+    jit.move(CCallHelpers::TrustedImm32(JSValue::CellTag), result.tagGPR());
+#endif
+    CCallHelpers::DataLabelPtr label = jit.moveWithPatch(
+        CCallHelpers::TrustedImmPtr(static_cast<size_t>(0xd1e7beeflu)),
+        result.payloadGPR());
+
+    LazyJSValue thisValue = *this;
+
+    // Once we do this, we're committed. Otherwise we leak memory. Note that we call ref/deref
+    // manually to ensure that there is no concurrency shadiness. We are doing something here
+    // that might be rather brutal: transfering ownership of this string.
+    if (m_kind == NewStringImpl)
+        thisValue.u.stringImpl->ref();
+
+    CodeBlock* codeBlock = jit.codeBlock();
+    
+    jit.addLinkTask(
+        [codeBlock, label, thisValue] (LinkBuffer& linkBuffer) {
+            JSValue realValue = thisValue.getValue(linkBuffer.vm());
+            RELEASE_ASSERT(realValue.isCell());
+
+            codeBlock->addConstant(realValue);
+            
+            if (thisValue.m_kind == NewStringImpl)
+                thisValue.u.stringImpl->deref();
+
+            linkBuffer.patch(label, realValue.asCell());
+        });
+}
+
 void LazyJSValue::dumpInContext(PrintStream& out, DumpContext* context) const
 {
     switch (m_kind) {
@@ -155,7 +252,10 @@ void LazyJSValue::dumpInContext(PrintStream& out, DumpContext* context) const
         out.print(" / ", StringImpl::utf8ForCharacters(&u.character, 1), ")");
         return;
     case KnownStringImpl:
-        out.print("Lazy:String(", stringImpl(), ")");
+        out.print("Lazy:KnownString(", stringImpl(), ")");
+        return;
+    case NewStringImpl:
+        out.print("Lazy:NewString(", stringImpl(), ")");
         return;
     }
     RELEASE_ASSERT_NOT_REACHED();
index a1231db..b5a4b82 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2014, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 #include "DFGFrozenValue.h"
 #include <wtf/text/StringImpl.h>
 
-namespace JSC { namespace DFG {
+namespace JSC {
+
+class CCallHelpers;
+
+namespace DFG {
+
+class Graph;
 
 // Represents either a JSValue, or for JSValues that require allocation in the heap,
 // it tells you everything you'd need to know in order to allocate it.
 
-enum LazinessKind {
-    KnownValue,
-    SingleCharacterString,
-    KnownStringImpl
-};
-
 class LazyJSValue {
 public:
+    enum LazinessKind {
+        KnownValue,
+        SingleCharacterString,
+        KnownStringImpl,
+        NewStringImpl
+    };
+
     LazyJSValue(FrozenValue* value = FrozenValue::emptySingleton())
         : m_kind(KnownValue)
     {
@@ -66,6 +73,10 @@ public:
         result.u.stringImpl = string;
         return result;
     }
+
+    static LazyJSValue newString(Graph&, const String&);
+
+    LazinessKind kind() const { return m_kind; }
     
     FrozenValue* tryGetValue(Graph&) const
     {
@@ -87,16 +98,22 @@ public:
         ASSERT(m_kind == SingleCharacterString);
         return u.character;
     }
+
+    const StringImpl* tryGetStringImpl() const;
+    
+    String tryGetString(Graph&) const;
     
     StringImpl* stringImpl() const
     {
-        ASSERT(m_kind == KnownStringImpl);
+        ASSERT(m_kind == KnownStringImpl || m_kind == NewStringImpl);
         return u.stringImpl;
     }
-    
+
     TriState strictEqual(const LazyJSValue& other) const;
     
     uintptr_t switchLookupValue(SwitchKind) const;
+
+    void emit(CCallHelpers&, JSValueRegs) const;
     
     void dump(PrintStream&) const;
     void dumpInContext(PrintStream&, DumpContext*) const;
index daa2933..4433b44 100644 (file)
@@ -92,6 +92,7 @@ ExitMode mayExit(Graph& graph, Node* node)
     case SetArgument:
     case JSConstant:
     case DoubleConstant:
+    case LazyJSConstant:
     case Int52Constant:
     case MovHint:
     case SetLocal:
index 6a98534..381cbe0 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2014, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -160,6 +160,14 @@ void Node::convertToIdentityOn(Node* child)
     }
 }
 
+void Node::convertToLazyJSConstant(Graph& graph, LazyJSValue value)
+{
+    m_op = LazyJSConstant;
+    m_flags &= ~NodeMustGenerate;
+    m_opInfo = bitwise_cast<uintptr_t>(graph.m_lazyJSValues.add(value));
+    children.reset();
+}
+
 void Node::convertToPutHint(const PromotedLocationDescriptor& descriptor, Node* base, Node* value)
 {
     m_op = PutHint;
@@ -193,6 +201,15 @@ void Node::convertToPutClosureVarHint()
         child1().node(), child2().node());
 }
 
+String Node::tryGetString(Graph& graph)
+{
+    if (hasConstant())
+        return constant()->tryGetString(graph);
+    if (hasLazyJSValue())
+        return lazyJSValue().tryGetString(graph);
+    return String();
+}
+
 PromotedLocationDescriptor Node::promotedLocationDescriptor()
 {
     return PromotedLocationDescriptor(static_cast<PromotedLocationKind>(m_opInfo), m_opInfo2);
index e29374f..9e87973 100644 (file)
@@ -494,6 +494,8 @@ struct Node {
         m_opInfo = bitwise_cast<uintptr_t>(value);
         children.reset();
     }
+
+    void convertToLazyJSConstant(Graph&, LazyJSValue);
     
     void convertToConstantStoragePointer(void* pointer)
     {
@@ -743,6 +745,19 @@ struct Node {
         return result;
     }
 
+    bool hasLazyJSValue()
+    {
+        return op() == LazyJSConstant;
+    }
+
+    LazyJSValue lazyJSValue()
+    {
+        ASSERT(hasLazyJSValue());
+        return *bitwise_cast<LazyJSValue*>(m_opInfo);
+    }
+
+    String tryGetString(Graph&);
+
     JSValue initializationValueForActivation() const
     {
         ASSERT(op() == CreateActivation);
index 0131538..6a50dbd 100644 (file)
@@ -41,6 +41,9 @@ namespace JSC { namespace DFG {
     macro(DoubleConstant, NodeResultDouble) \
     macro(Int52Constant, NodeResultInt52) \
     \
+    /* Lazy JSValue constant. We don't know the JSValue bits of it yet. */\
+    macro(LazyJSConstant, NodeResultJS) \
+    \
     /* Marker to indicate that an operation was optimized entirely and all that is left */\
     /* is to make one node alias another. CSE will later usually eliminate this node, */\
     /* though it may choose not to if it would corrupt predictions (very rare). */\
index e492610..6b0c723 100644 (file)
@@ -668,7 +668,8 @@ private:
         case StoreBarrier:
         case GetStack:
         case GetRegExpObjectLastIndex:
-        case SetRegExpObjectLastIndex: {
+        case SetRegExpObjectLastIndex:
+        case LazyJSConstant: {
             // This node should never be visible at this stage of compilation. It is
             // inserted by fixup(), which follows this phase.
             DFG_CRASH(m_graph, node, "Unexpected node during prediction propagation");
index 0f0e633..3031c9f 100644 (file)
@@ -137,6 +137,7 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case JSConstant:
     case DoubleConstant:
     case Int52Constant:
+    case LazyJSConstant:
     case Identity:
     case ToThis:
     case CreateThis:
index 2f23d09..369ca89 100644 (file)
@@ -7647,6 +7647,14 @@ void SpeculativeJIT::compileSetRegExpObjectLastIndex(Node* node)
     noResult(node);
 }
 
+void SpeculativeJIT::compileLazyJSConstant(Node* node)
+{
+    JSValueRegsTemporary result(this);
+    JSValueRegs resultRegs = result.regs();
+    node->lazyJSValue().emit(m_jit, resultRegs);
+    jsValueResult(resultRegs, node);
+}
+
 } } // namespace JSC::DFG
 
 #endif
index 5ea8e9c..2ea8874 100644 (file)
@@ -2400,6 +2400,7 @@ public:
     void compilePutAccessorByVal(Node*);
     void compileGetRegExpObjectLastIndex(Node*);
     void compileSetRegExpObjectLastIndex(Node*);
+    void compileLazyJSConstant(Node*);
     
     void moveTrueTo(GPRReg);
     void moveFalseTo(GPRReg);
index ee2fc4c..cafbec9 100644 (file)
@@ -1874,6 +1874,10 @@ void SpeculativeJIT::compile(Node* node)
         initConstantInfo(node);
         break;
 
+    case LazyJSConstant:
+        compileLazyJSConstant(node);
+        break;
+
     case Identity: {
         speculate(node, node->child1());
         switch (node->child1().useKind()) {
index c198927..c3efacd 100644 (file)
@@ -1982,6 +1982,10 @@ void SpeculativeJIT::compile(Node* node)
         initConstantInfo(node);
         break;
 
+    case LazyJSConstant:
+        compileLazyJSConstant(node);
+        break;
+
     case Identity: {
         speculate(node, node->child1());
         switch (node->child1().useKind()) {
index acfad65..7e81df3 100644 (file)
@@ -291,7 +291,51 @@ private:
 
             break;
         }
-            
+
+        // FIXME: We have a lot of string constant-folding rules here. It would be great to
+        // move these to the abstract interpreter once AbstractValue can support LazyJSValue.
+        // https://bugs.webkit.org/show_bug.cgi?id=155204
+
+        case MakeRope:
+        case ValueAdd:
+        case StrCat: {
+            String leftString = m_node->child1()->tryGetString(m_graph);
+            if (!leftString)
+                break;
+            String rightString = m_node->child2()->tryGetString(m_graph);
+            if (!rightString)
+                break;
+            String extraString;
+            if (m_node->child3()) {
+                extraString = m_node->child3()->tryGetString(m_graph);
+                if (!extraString)
+                    break;
+            }
+
+            StringBuilder builder;
+            builder.append(leftString);
+            builder.append(rightString);
+            if (!!extraString)
+                builder.append(extraString);
+
+            m_node->convertToLazyJSConstant(
+                m_graph, LazyJSValue::newString(m_graph, builder.toString()));
+            m_changed = true;
+            break;
+        }
+
+        case GetArrayLength: {
+            if (m_node->arrayMode().type() == Array::Generic
+                || m_node->arrayMode().type() == Array::String) {
+                String string = m_node->child1()->tryGetString(m_graph);
+                if (!!string) {
+                    m_graph.convertToConstant(m_node, jsNumber(string.length()));
+                    m_changed = true;
+                }
+            }
+            break;
+        }
+
         default:
             break;
         }
index 7d44cfd..76fb1c4 100644 (file)
@@ -44,6 +44,7 @@ inline CapabilityLevel canCompile(Node* node)
     
     switch (node->op()) {
     case JSConstant:
+    case LazyJSConstant:
     case GetLocal:
     case SetLocal:
     case PutStack:
index 1ef210f..1826b02 100644 (file)
@@ -446,6 +446,9 @@ private:
         case Int52Constant:
             compileInt52Constant();
             break;
+        case LazyJSConstant:
+            compileLazyJSConstant();
+            break;
         case DoubleRep:
             compileDoubleRep();
             break;
@@ -1044,6 +1047,18 @@ private:
         setStrictInt52(m_out.constInt64(value));
     }
 
+    void compileLazyJSConstant()
+    {
+        PatchpointValue* patchpoint = m_out.patchpoint(Int64);
+        LazyJSValue value = m_node->lazyJSValue();
+        patchpoint->setGenerator(
+            [=] (CCallHelpers& jit, const StackmapGenerationParams& params) {
+                value.emit(jit, JSValueRegs(params[0].gpr()));
+            });
+        patchpoint->effects = Effects::none();
+        setJSValue(patchpoint);
+    }
+
     void compileDoubleRep()
     {
         switch (m_node->child1().useKind()) {
index 9e94595..5d3795d 100644 (file)
@@ -1,3 +1,17 @@
+2016-03-08  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to constant-fold strings
+        https://bugs.webkit.org/show_bug.cgi?id=155200
+
+        Reviewed by Geoffrey Garen.
+
+        Also disable assertions about reference counting strings on the JIT thread. We will do
+        that now and it's OK.
+
+        * wtf/text/StringImpl.h:
+        (WTF::StringImpl::ref):
+        (WTF::StringImpl::deref):
+
 2016-03-08  Anders Carlsson  <andersca@apple.com>
 
         Fix AppKitCompatibilityDeclarations build.
index 063ce63..192db73 100644 (file)
@@ -585,7 +585,7 @@ public:
 
     inline void ref()
     {
-        ASSERT(!isCompilationThread());
+        ASSERT(!isCompilationThread() || !isAtomic());
 
         STRING_STATS_REF_STRING(*this);
 
@@ -594,7 +594,7 @@ public:
 
     inline void deref()
     {
-        ASSERT(!isCompilationThread());
+        ASSERT(!isCompilationThread() || !isAtomic());
 
         STRING_STATS_DEREF_STRING(*this);