[JSC] Add support for GetByVal on arrays of Undecided shape
https://bugs.webkit.org/show_bug.cgi?id=147814
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-08-13
Reviewed by Filip Pizlo.
Previously, GetByVal on Array::Undecided would just take
the generic path. The problem is the generic path is so
slow that it could take a significant amount of time
even for unfrequent accesses.
With this patch, if the following conditions are met,
the GetByVal just returns a "undefined" constant:
-The object is an OriginalArray.
-The prototype chain is sane.
-The index is an integer.
-The integer is positive (runtime check).
Ideally, the 4th conditions should be removed
deducing a compile-time constant gives us so much better
opportunities at getting rid of this code.
There are two cases where this patch removes the runtime
check:
-If the index is constant (uncommon but easy)
-If the index is within a range known to be positive.
(common case and made possible with DFGIntegerRangeOptimizationPhase).
When we get into those cases, DFG just nukes everything
and all we have left is a structure check :)
This patch is a 14% improvement on audio-beat-detection,
a few percent faster here and there and no regression.
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
If the index is a positive constant, we can get rid of the GetByVal
entirely. :)
* dfg/DFGArrayMode.cpp:
(JSC::DFG::ArrayMode::fromObserved):
The returned type is now Array::Undecided + profiling information.
The useful type is set in ArrayMode::refine().
(JSC::DFG::ArrayMode::refine):
If we meet the particular set conditions, we speculate an Undecided
array type with sane chain. Anything else comes back to Generic.
(JSC::DFG::ArrayMode::originalArrayStructure):
To enable the structure check for Undecided array.
(JSC::DFG::ArrayMode::alreadyChecked):
* dfg/DFGArrayMode.h:
(JSC::DFG::ArrayMode::withProfile):
(JSC::DFG::ArrayMode::canCSEStorage):
(JSC::DFG::ArrayMode::benefitsFromOriginalArray):
(JSC::DFG::ArrayMode::lengthNeedsStorage): Deleted.
(JSC::DFG::ArrayMode::isSpecific): Deleted.A
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsic): Deleted.
This is somewhat unrelated.
Having Array::Undecided on ArrayPush was impossible before
since ArrayMode::fromObserved() used to return Array::Generic.
Now that Array::Undecided is possible, we must make sure not
to provide it to ArrayPush since there is no code to handle it
properly.
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
The operation only depends on the index, it is pure.
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode): Deleted.
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::jumpSlowForUnwantedArrayMode):
(JSC::DFG::SpeculativeJIT::checkArray):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::compileGetByVal):
* tests/stress/get-by-val-on-undecided-array-type.js: Added.
* tests/stress/get-by-val-on-undecided-sane-chain-1.js: Added.
* tests/stress/get-by-val-on-undecided-sane-chain-2.js: Added.
* tests/stress/get-by-val-on-undecided-sane-chain-3.js: Added.
* tests/stress/get-by-val-on-undecided-sane-chain-4.js: Added.
* tests/stress/get-by-val-on-undecided-sane-chain-5.js: Added.
* tests/stress/get-by-val-on-undecided-sane-chain-6.js: Added.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@188432 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
index 229087d..9325348 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
@@ -1287,12 +1287,21 @@
switch (node->arrayMode().type()) {
case Array::SelectUsingPredictions:
case Array::Unprofiled:
- case Array::Undecided:
+ case Array::SelectUsingArguments:
RELEASE_ASSERT_NOT_REACHED();
break;
case Array::ForceExit:
m_state.setIsValid(false);
break;
+ case Array::Undecided: {
+ JSValue index = forNode(node->child2()).value();
+ if (index && index.isInt32() && index.asInt32() >= 0) {
+ setConstant(node, jsUndefined());
+ break;
+ }
+ forNode(node).setType(SpecOther);
+ break;
+ }
case Array::Generic:
clobberWorld(node->origin.semantic, clobberLimit);
forNode(node).makeHeapTop();
@@ -1910,6 +1919,7 @@
case Array::Int32:
case Array::Double:
case Array::Contiguous:
+ case Array::Undecided:
case Array::ArrayStorage:
case Array::SlowPutArrayStorage:
break;
diff --git a/Source/JavaScriptCore/dfg/DFGArrayMode.cpp b/Source/JavaScriptCore/dfg/DFGArrayMode.cpp
index b0a4b04..75fd6d1 100644
--- a/Source/JavaScriptCore/dfg/DFGArrayMode.cpp
+++ b/Source/JavaScriptCore/dfg/DFGArrayMode.cpp
@@ -28,6 +28,7 @@
#if ENABLE(DFG_JIT)
+#include "ArrayPrototype.h"
#include "DFGAbstractValue.h"
#include "DFGGraph.h"
#include "JSCInlines.h"
@@ -48,17 +49,17 @@
return ArrayMode(Array::Unprofiled);
case asArrayModes(NonArray):
if (action == Array::Write && !profile->mayInterceptIndexedAccesses(locker))
- return ArrayMode(Array::Undecided, nonArray, Array::OutOfBounds, Array::Convert);
+ return ArrayMode(Array::SelectUsingArguments, nonArray, Array::OutOfBounds, Array::Convert);
return ArrayMode(Array::SelectUsingPredictions, nonArray).withSpeculationFromProfile(locker, profile, makeSafe);
case asArrayModes(ArrayWithUndecided):
if (action == Array::Write)
- return ArrayMode(Array::Undecided, Array::Array, Array::OutOfBounds, Array::Convert);
- return ArrayMode(Array::Generic);
+ return ArrayMode(Array::SelectUsingArguments, Array::Array, Array::OutOfBounds, Array::Convert);
+ return ArrayMode(Array::Undecided, Array::Array, Array::OutOfBounds, Array::AsIs).withProfile(locker, profile, makeSafe);
case asArrayModes(NonArray) | asArrayModes(ArrayWithUndecided):
if (action == Array::Write && !profile->mayInterceptIndexedAccesses(locker))
- return ArrayMode(Array::Undecided, Array::PossiblyArray, Array::OutOfBounds, Array::Convert);
+ return ArrayMode(Array::SelectUsingArguments, Array::PossiblyArray, Array::OutOfBounds, Array::Convert);
return ArrayMode(Array::SelectUsingPredictions).withSpeculationFromProfile(locker, profile, makeSafe);
case asArrayModes(NonArrayWithInt32):
@@ -134,7 +135,7 @@
else if (shouldUseInt32(observed))
type = Array::Int32;
else
- type = Array::Undecided;
+ type = Array::SelectUsingArguments;
if (hasSeenArray(observed) && hasSeenNonArray(observed))
arrayClass = Array::PossiblyArray;
@@ -179,7 +180,7 @@
// should just trust the array profile.
switch (type()) {
- case Array::Undecided:
+ case Array::SelectUsingArguments:
if (!value)
return withType(Array::ForceExit);
if (isInt32Speculation(value))
@@ -187,7 +188,20 @@
if (isFullNumberSpeculation(value))
return withTypeAndConversion(Array::Double, Array::Convert);
return withTypeAndConversion(Array::Contiguous, Array::Convert);
-
+ case Array::Undecided: {
+ // If we have an OriginalArray and the JSArray prototype chain is sane,
+ // any indexed access always return undefined. We have a fast path for that.
+ JSGlobalObject* globalObject = graph.globalObjectFor(node->origin.semantic);
+ if (node->op() == GetByVal
+ && arrayClass() == Array::OriginalArray
+ && globalObject->arrayPrototypeChainIsSane()
+ && !graph.hasExitSite(node->origin.semantic, OutOfBounds)) {
+ graph.watchpoints().addLazily(globalObject->arrayPrototype()->structure()->transitionWatchpointSet());
+ graph.watchpoints().addLazily(globalObject->objectPrototype()->structure()->transitionWatchpointSet());
+ return withSpeculation(Array::SaneChain);
+ }
+ return ArrayMode(Array::Generic);
+ }
case Array::Int32:
if (!value || isInt32Speculation(value))
return *this;
@@ -302,6 +316,8 @@
return globalObject->originalArrayStructureForIndexingType(ArrayWithDouble);
case Array::Contiguous:
return globalObject->originalArrayStructureForIndexingType(ArrayWithContiguous);
+ case Array::Undecided:
+ return globalObject->originalArrayStructureForIndexingType(ArrayWithUndecided);
case Array::ArrayStorage:
return globalObject->originalArrayStructureForIndexingType(ArrayWithArrayStorage);
default:
@@ -398,6 +414,9 @@
case Array::ArrayStorage:
return alreadyChecked(graph, node, value, ArrayStorageShape);
+
+ case Array::Undecided:
+ return alreadyChecked(graph, node, value, UndecidedShape);
case Array::SlowPutArrayStorage:
switch (arrayClass()) {
@@ -469,7 +488,7 @@
case Array::SelectUsingPredictions:
case Array::Unprofiled:
- case Array::Undecided:
+ case Array::SelectUsingArguments:
break;
}
@@ -482,6 +501,8 @@
switch (type) {
case Array::SelectUsingPredictions:
return "SelectUsingPredictions";
+ case Array::SelectUsingArguments:
+ return "SelectUsingArguments";
case Array::Unprofiled:
return "Unprofiled";
case Array::Generic:
diff --git a/Source/JavaScriptCore/dfg/DFGArrayMode.h b/Source/JavaScriptCore/dfg/DFGArrayMode.h
index a77c888d..9c988c0 100644
--- a/Source/JavaScriptCore/dfg/DFGArrayMode.h
+++ b/Source/JavaScriptCore/dfg/DFGArrayMode.h
@@ -53,6 +53,7 @@
enum Type {
SelectUsingPredictions, // Implies that we need predictions to decide. We will never get to the backend in this mode.
+ SelectUsingArguments, // Implies that we use the Node's arguments to decide. We will never get to the backend in this mode.
Unprofiled, // Implies that array profiling didn't see anything. But that could be because the operands didn't comply with basic type assumptions (base is cell, property is int). This either becomes Generic or ForceExit depending on value profiling.
ForceExit, // Implies that we have no idea how to execute this operation, so we should just give up.
Generic,
@@ -195,7 +196,7 @@
ArrayMode withProfile(const ConcurrentJITLocker& locker, ArrayProfile* profile, bool makeSafe) const
{
Array::Class myArrayClass;
-
+
if (isJSArray()) {
if (profile->usesOriginalArrayStructures(locker) && benefitsFromOriginalArray())
myArrayClass = Array::OriginalArray;
@@ -293,7 +294,9 @@
{
switch (type()) {
case Array::SelectUsingPredictions:
+ case Array::SelectUsingArguments:
case Array::Unprofiled:
+ case Array::Undecided:
case Array::ForceExit:
case Array::Generic:
case Array::DirectArguments:
@@ -307,7 +310,6 @@
bool lengthNeedsStorage() const
{
switch (type()) {
- case Array::Undecided:
case Array::Int32:
case Array::Double:
case Array::Contiguous:
@@ -335,10 +337,10 @@
{
switch (type()) {
case Array::SelectUsingPredictions:
+ case Array::SelectUsingArguments:
case Array::Unprofiled:
case Array::ForceExit:
case Array::Generic:
- case Array::Undecided:
return false;
default:
return true;
@@ -372,6 +374,7 @@
case Array::Int32:
case Array::Double:
case Array::Contiguous:
+ case Array::Undecided:
case Array::ArrayStorage:
return true;
default:
diff --git a/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp b/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
index e272343..a56337c 100644
--- a/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
+++ b/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
@@ -1951,7 +1951,6 @@
if (!arrayMode.isJSArray())
return false;
switch (arrayMode.type()) {
- case Array::Undecided:
case Array::Int32:
case Array::Double:
case Array::Contiguous:
diff --git a/Source/JavaScriptCore/dfg/DFGClobberize.h b/Source/JavaScriptCore/dfg/DFGClobberize.h
index 46f5fe4..85c57e5 100644
--- a/Source/JavaScriptCore/dfg/DFGClobberize.h
+++ b/Source/JavaScriptCore/dfg/DFGClobberize.h
@@ -467,7 +467,7 @@
switch (mode.type()) {
case Array::SelectUsingPredictions:
case Array::Unprofiled:
- case Array::Undecided:
+ case Array::SelectUsingArguments:
// Assume the worst since we don't have profiling yet.
read(World);
write(Heap);
@@ -534,6 +534,10 @@
read(World);
write(Heap);
return;
+
+ case Array::Undecided:
+ def(PureValue(node));
+ return;
case Array::ArrayStorage:
case Array::SlowPutArrayStorage:
@@ -580,6 +584,7 @@
Node* value = graph.varArgChild(node, 2).node();
switch (mode.modeForPut().type()) {
case Array::SelectUsingPredictions:
+ case Array::SelectUsingArguments:
case Array::Unprofiled:
case Array::Undecided:
// Assume the worst since we don't have profiling yet.
diff --git a/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp b/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
index d6a9790..da76e7a 100644
--- a/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
@@ -625,7 +625,6 @@
switch (arrayMode.type()) {
case Array::SelectUsingPredictions:
case Array::Unprofiled:
- case Array::Undecided:
RELEASE_ASSERT_NOT_REACHED();
break;
case Array::Generic:
@@ -686,6 +685,7 @@
switch (node->arrayMode().modeForPut().type()) {
case Array::SelectUsingPredictions:
+ case Array::SelectUsingArguments:
case Array::Unprofiled:
case Array::Undecided:
RELEASE_ASSERT_NOT_REACHED();
diff --git a/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp b/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
index 6ab8af8..d67e3f1 100644
--- a/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
@@ -958,7 +958,28 @@
}
break;
}
-
+
+ case GetByVal: {
+ if (node->arrayMode().type() != Array::Undecided)
+ break;
+
+ auto iter = m_relationships.find(node->child2().node());
+ if (iter == m_relationships.end())
+ break;
+
+ int minValue = std::numeric_limits<int>::min();
+ for (Relationship relationship : iter->value)
+ minValue = std::max(minValue, relationship.minValueOfLeft());
+
+ if (minValue < 0)
+ break;
+
+ executeNode(block->at(nodeIndex));
+ m_graph.convertToConstant(node, jsUndefined());
+ changed = true;
+ break;
+ }
+
default:
break;
}
diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
index 0537363..484bf8d 100644
--- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
@@ -716,6 +716,9 @@
case Array::Contiguous:
return jumpSlowForUnwantedArrayMode(tempGPR, arrayMode, ContiguousShape);
+ case Array::Undecided:
+ return jumpSlowForUnwantedArrayMode(tempGPR, arrayMode, UndecidedShape);
+
case Array::ArrayStorage:
case Array::SlowPutArrayStorage: {
ASSERT(!arrayMode.isJSArrayWithOriginalStructure());
@@ -781,6 +784,7 @@
case Array::Int32:
case Array::Double:
case Array::Contiguous:
+ case Array::Undecided:
case Array::ArrayStorage:
case Array::SlowPutArrayStorage: {
GPRTemporary temp(this);
diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
index 6249902..800b872 100644
--- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
@@ -2331,6 +2331,26 @@
terminateSpeculativeExecution(InadequateCoverage, JSValueRegs(), 0);
#endif
break;
+ case Array::Undecided: {
+ SpeculateStrictInt32Operand index(this, node->child2());
+ GPRTemporary resultTag(this, Reuse, index);
+ GPRTemporary resultPayload(this);
+
+ GPRReg indexGPR = index.gpr();
+ GPRReg resultTagGPR = resultTag.gpr();
+ GPRReg resultPayloadGPR = resultPayload.gpr();
+
+ use(node->child1());
+ index.use();
+
+ speculationCheck(OutOfBounds, JSValueRegs(), node,
+ m_jit.branch32(MacroAssembler::LessThan, indexGPR, MacroAssembler::TrustedImm32(0)));
+
+ m_jit.move(MacroAssembler::TrustedImm32(JSValue::UndefinedTag), resultTagGPR);
+ m_jit.move(MacroAssembler::TrustedImm32(0), resultPayloadGPR);
+ jsValueResult(resultTagGPR, resultPayloadGPR, node, UseChildrenCalledExplicitly);
+ break;
+ }
case Array::Generic: {
SpeculateCellOperand base(this, node->child1()); // Save a register, speculate cell. We'll probably be right.
JSValueOperand property(this, node->child2());
diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
index 13e628f..53daf34 100644
--- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
@@ -2461,6 +2461,22 @@
case Array::ForceExit:
DFG_CRASH(m_jit.graph(), node, "Bad array mode type");
break;
+ case Array::Undecided: {
+ SpeculateStrictInt32Operand index(this, node->child2());
+ GPRTemporary result(this, Reuse, index);
+ GPRReg indexGPR = index.gpr();
+ GPRReg resultGPR = result.gpr();
+
+ use(node->child1());
+ index.use();
+
+ speculationCheck(OutOfBounds, JSValueRegs(), node,
+ m_jit.branch32(MacroAssembler::LessThan, indexGPR, MacroAssembler::TrustedImm32(0)));
+
+ m_jit.move(MacroAssembler::TrustedImm64(ValueUndefined), resultGPR);
+ jsValueResult(resultGPR, node, UseChildrenCalledExplicitly);
+ break;
+ }
case Array::Generic: {
JSValueOperand base(this, node->child1());
JSValueOperand property(this, node->child2());
