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)
commit0e3a9911185cc3c7547fae25a1d6134805f95934
tree3dcc860d89c2858c135494c3db02e46f9d08ed3e
parent2f755ce3d6c6d1a274a0b02af193e3d8748ec767
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.

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