Changeset 197833 in webkit for trunk/Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp

Timestamp:

Mar 8, 2016, 9:16:47 PM (9 years ago)

Author:

[email protected]

Message:

DFG should be able to constant-fold strings
​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.

File:

• trunk/Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp (modified) (9 diffs)

trunk/Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp

@@ -1 +1 @@
 /*
- * 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
@@ -29 +29 @@
 #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
 {
@@ -41 +52 @@
         return jsSingleCharacterString(&vm, u.character);
     case KnownStringImpl:
+    case NewStringImpl:
         return jsString(&vm, u.stringImpl);
     }
@@ -74 +86 @@
     
     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();
+    }
 }
 
@@ -86 +140 @@
             return equalToSingleCharacter(value()->value(), other.character());
         case KnownStringImpl:
+        case NewStringImpl:
             return equalToStringImpl(value()->value(), other.stringImpl());
         }
@@ -94 +149 @@
             return triState(character() == other.character());
         case KnownStringImpl:
+        case NewStringImpl:
             if (other.stringImpl()->length() != 1)
                 return FalseTriState;
@@ -102 +158 @@
         break;
     case KnownStringImpl:
+    case NewStringImpl:
         switch (other.m_kind) {
         case KnownStringImpl:
+        case NewStringImpl:
             return triState(WTF::equal(stringImpl(), other.stringImpl()));
         default:
@@ -144 +202 @@
 }
 
+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
 {
@@ -156 +253 @@
         return;
     case KnownStringImpl:
-        out.print("Lazy:String(", stringImpl(), ")");
+        out.print("Lazy:KnownString(", stringImpl(), ")");
+        return;
+    case NewStringImpl:
+        out.print("Lazy:NewString(", stringImpl(), ")");
         return;
     }