DFG CFA may get overzealous in loops that have code that must exit
https://bugs.webkit.org/show_bug.cgi?id=91188
Source/JavaScriptCore:
Reviewed by Gavin Barraclough.
Ensure that if the CFA assumes that an operation must exit, then it will always exit
no matter what happens after. That's necessary to preserve soundness.
Remove a broken fixup done by the DFG simplifier, where it was trying to say that the
variable-at-head was the first access in the second block in the merge, if the first
block did not read the variable. That's totally wrong, if the first block was in fact
doing a phantom read. I removed that fixup and instead hardened the rest of the
compiler.
* dfg/DFGAbstractState.cpp:
(JSC::DFG::AbstractState::endBasicBlock):
* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::BasicBlock):
(BasicBlock):
* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::performBlockCFA):
* dfg/DFGCFGSimplificationPhase.cpp:
(JSC::DFG::CFGSimplificationPhase::mergeBlocks):
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::ConstantFoldingPhase):
(JSC::DFG::ConstantFoldingPhase::run):
(ConstantFoldingPhase):
(JSC::DFG::ConstantFoldingPhase::foldConstants):
(JSC::DFG::ConstantFoldingPhase::paintUnreachableCode):
* dfg/DFGVariableEventStream.cpp:
(JSC::DFG::VariableEventStream::reconstruct):
LayoutTests:
Reviewed by Gavin Baraclough.
* fast/js/dfg-force-exit-then-sparse-conditional-constant-prop-in-loop-expected.txt: Added.
* fast/js/dfg-force-exit-then-sparse-conditional-constant-prop-in-loop.html: Added.
* fast/js/script-tests/dfg-force-exit-then-sparse-conditional-constant-prop-in-loop.js: Added.
(foo):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@122541 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractState.cpp b/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
index 4cd31f2..95f44c0 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
+++ b/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
@@ -52,6 +52,10 @@
ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
+ // This is usually a no-op, but it is possible that the graph has grown since the
+ // abstract state was last used.
+ m_nodes.resize(m_graph.size());
+
for (size_t i = 0; i < basicBlock->size(); i++)
m_nodes[basicBlock->at(i)].clear();
@@ -164,6 +168,7 @@
BasicBlock* block = m_block; // Save the block for successor merging.
block->cfaFoundConstants = m_foundConstants;
+ block->cfaDidFinish = m_isValid;
if (!m_isValid) {
reset();
diff --git a/Source/JavaScriptCore/dfg/DFGBasicBlock.h b/Source/JavaScriptCore/dfg/DFGBasicBlock.h
index 9128f08..441e2e7 100644
--- a/Source/JavaScriptCore/dfg/DFGBasicBlock.h
+++ b/Source/JavaScriptCore/dfg/DFGBasicBlock.h
@@ -45,6 +45,7 @@
, cfaHasVisited(false)
, cfaShouldRevisit(false)
, cfaFoundConstants(false)
+ , cfaDidFinish(true)
#if !ASSERT_DISABLED
, isLinked(false)
#endif
@@ -103,6 +104,7 @@
bool cfaHasVisited;
bool cfaShouldRevisit;
bool cfaFoundConstants;
+ bool cfaDidFinish;
#if !ASSERT_DISABLED
bool isLinked;
#endif
diff --git a/Source/JavaScriptCore/dfg/DFGCFAPhase.cpp b/Source/JavaScriptCore/dfg/DFGCFAPhase.cpp
index c523496..24ea0b3 100644
--- a/Source/JavaScriptCore/dfg/DFGCFAPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGCFAPhase.cpp
@@ -95,8 +95,12 @@
m_state.dump(WTF::dataFile());
dataLog("\n");
#endif
- if (!m_state.execute(i))
+ if (!m_state.execute(i)) {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog(" Expect OSR exit.\n");
+#endif
break;
+ }
}
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" tail regs: ");
diff --git a/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp b/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp
index c234e6e..dc1632d 100644
--- a/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp
@@ -643,18 +643,6 @@
NodeIndex atFirstIndex = firstBlock->variablesAtTail.operand(node.local());
m_graph.changeEdge(node.children.child1(), Edge(skipGetLocal(atFirstIndex)), node.shouldGenerate());
childrenAlreadyFixed = true;
-
- if (node.op() != GetLocal)
- break;
-
- NodeIndex atFirstHeadIndex = firstBlock->variablesAtHead.operand(node.local());
- if (atFirstHeadIndex == NoNode)
- break;
-
- if (m_graph[atFirstHeadIndex].op() != Phi)
- break;
-
- firstBlock->variablesAtHead.operand(node.local()) = nodeIndex;
break;
}
diff --git a/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp b/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
index d3029b3..a8eb9ee 100644
--- a/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
@@ -40,6 +40,7 @@
public:
ConstantFoldingPhase(Graph& graph)
: Phase(graph, "constant folding")
+ , m_state(graph)
{
}
@@ -47,114 +48,192 @@
{
bool changed = false;
- AbstractState state(m_graph);
- InsertionSet<NodeIndex> insertionSet;
-
for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
BasicBlock* block = m_graph.m_blocks[blockIndex].get();
if (!block)
continue;
- if (!block->cfaFoundConstants)
- continue;
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLog("Constant folding considering Block #%u.\n", blockIndex);
-#endif
- state.beginBasicBlock(block);
- for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
- if (!state.isValid())
- break;
- NodeIndex nodeIndex = block->at(indexInBlock);
- Node& node = m_graph[nodeIndex];
-
- bool eliminated = false;
-
- switch (node.op()) {
- case CheckArgumentsNotCreated: {
- if (!isEmptySpeculation(
- state.variables().operand(
- m_graph.argumentsRegisterFor(node.codeOrigin)).m_type))
- break;
- ASSERT(node.refCount() == 1);
- node.setOpAndDefaultFlags(Phantom);
- eliminated = true;
- break;
- }
-
- // FIXME: This would be a great place to remove CheckStructure's.
-
- default:
- break;
- }
-
- if (eliminated) {
- changed = true;
- continue;
- }
-
- state.execute(indexInBlock);
- if (!node.shouldGenerate()
- || state.didClobber()
- || node.hasConstant())
- continue;
- JSValue value = state.forNode(nodeIndex).value();
- if (!value)
- continue;
-
- Node phantom(Phantom, node.codeOrigin);
-
- if (node.op() == GetLocal) {
- NodeIndex previousLocalAccess = NoNode;
- if (block->variablesAtHead.operand(node.local()) == nodeIndex
- && m_graph[node.child1()].op() == Phi) {
- // We expect this to be the common case.
- ASSERT(block->isInPhis(node.child1().index()));
- previousLocalAccess = node.child1().index();
- block->variablesAtHead.operand(node.local()) = previousLocalAccess;
- } else {
- ASSERT(indexInBlock > 0);
- // Must search for the previous access to this local.
- for (BlockIndex subIndexInBlock = indexInBlock; subIndexInBlock--;) {
- NodeIndex subNodeIndex = block->at(subIndexInBlock);
- Node& subNode = m_graph[subNodeIndex];
- if (!subNode.shouldGenerate())
- continue;
- if (!subNode.hasVariableAccessData())
- continue;
- if (subNode.local() != node.local())
- continue;
- // The two must have been unified.
- ASSERT(subNode.variableAccessData() == node.variableAccessData());
- previousLocalAccess = subNodeIndex;
- break;
- }
- ASSERT(previousLocalAccess != NoNode);
- }
-
- NodeIndex tailNodeIndex = block->variablesAtTail.operand(node.local());
- if (tailNodeIndex == nodeIndex)
- block->variablesAtTail.operand(node.local()) = previousLocalAccess;
- else {
- ASSERT(m_graph[tailNodeIndex].op() == Flush
- || m_graph[tailNodeIndex].op() == SetLocal);
- }
- }
-
- phantom.children = node.children;
- phantom.ref();
-
- m_graph.convertToConstant(nodeIndex, value);
- NodeIndex phantomNodeIndex = m_graph.size();
- m_graph.append(phantom);
- insertionSet.append(indexInBlock, phantomNodeIndex);
-
- changed = true;
- }
- insertionSet.execute(*block);
- state.reset();
+ if (!block->cfaDidFinish)
+ changed |= paintUnreachableCode(blockIndex);
+ if (block->cfaFoundConstants)
+ changed |= foldConstants(blockIndex);
}
return changed;
}
+
+private:
+ bool foldConstants(BlockIndex blockIndex)
+ {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog("Constant folding considering Block #%u.\n", blockIndex);
+#endif
+ BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+ bool changed = false;
+ m_state.beginBasicBlock(block);
+ for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
+ NodeIndex nodeIndex = block->at(indexInBlock);
+ Node& node = m_graph[nodeIndex];
+
+ if (!m_state.isValid())
+ break;
+
+ bool eliminated = false;
+
+ switch (node.op()) {
+ case CheckArgumentsNotCreated: {
+ if (!isEmptySpeculation(
+ m_state.variables().operand(
+ m_graph.argumentsRegisterFor(node.codeOrigin)).m_type))
+ break;
+ ASSERT(node.refCount() == 1);
+ node.setOpAndDefaultFlags(Phantom);
+ eliminated = true;
+ break;
+ }
+
+ // FIXME: This would be a great place to remove CheckStructure's.
+
+ default:
+ break;
+ }
+
+ if (eliminated) {
+ changed = true;
+ continue;
+ }
+
+ m_state.execute(indexInBlock);
+ if (!node.shouldGenerate()
+ || m_state.didClobber()
+ || node.hasConstant())
+ continue;
+ JSValue value = m_state.forNode(nodeIndex).value();
+ if (!value)
+ continue;
+
+ Node phantom(Phantom, node.codeOrigin);
+
+ if (node.op() == GetLocal) {
+ NodeIndex previousLocalAccess = NoNode;
+ if (block->variablesAtHead.operand(node.local()) == nodeIndex
+ && m_graph[node.child1()].op() == Phi) {
+ // We expect this to be the common case.
+ ASSERT(block->isInPhis(node.child1().index()));
+ previousLocalAccess = node.child1().index();
+ block->variablesAtHead.operand(node.local()) = previousLocalAccess;
+ } else {
+ ASSERT(indexInBlock > 0);
+ // Must search for the previous access to this local.
+ for (BlockIndex subIndexInBlock = indexInBlock; subIndexInBlock--;) {
+ NodeIndex subNodeIndex = block->at(subIndexInBlock);
+ Node& subNode = m_graph[subNodeIndex];
+ if (!subNode.shouldGenerate())
+ continue;
+ if (!subNode.hasVariableAccessData())
+ continue;
+ if (subNode.local() != node.local())
+ continue;
+ // The two must have been unified.
+ ASSERT(subNode.variableAccessData() == node.variableAccessData());
+ previousLocalAccess = subNodeIndex;
+ break;
+ }
+ if (previousLocalAccess == NoNode) {
+ // The previous access must have been a Phi.
+ for (BlockIndex phiIndexInBlock = block->phis.size(); phiIndexInBlock--;) {
+ NodeIndex phiNodeIndex = block->phis[phiIndexInBlock];
+ Node& phiNode = m_graph[phiNodeIndex];
+ if (!phiNode.shouldGenerate())
+ continue;
+ if (phiNode.local() != node.local())
+ continue;
+ // The two must have been unified.
+ ASSERT(phiNode.variableAccessData() == node.variableAccessData());
+ previousLocalAccess = phiNodeIndex;
+ break;
+ }
+ ASSERT(previousLocalAccess != NoNode);
+ }
+ }
+
+ ASSERT(previousLocalAccess != NoNode);
+
+ NodeIndex tailNodeIndex = block->variablesAtTail.operand(node.local());
+ if (tailNodeIndex == nodeIndex)
+ block->variablesAtTail.operand(node.local()) = previousLocalAccess;
+ else {
+ ASSERT(m_graph[tailNodeIndex].op() == Flush
+ || m_graph[tailNodeIndex].op() == SetLocal);
+ }
+ }
+
+ phantom.children = node.children;
+ phantom.ref();
+
+ m_graph.convertToConstant(nodeIndex, value);
+ NodeIndex phantomNodeIndex = m_graph.size();
+ m_graph.append(phantom);
+ m_insertionSet.append(indexInBlock, phantomNodeIndex);
+
+ changed = true;
+ }
+ m_state.reset();
+ m_insertionSet.execute(*block);
+
+ return changed;
+ }
+
+ // This is necessary because the CFA may reach conclusions about constants based on its
+ // assumption that certain code must exit, but then those constants may lead future
+ // reexecutions of the CFA to believe that the same code will now no longer exit. Thus
+ // to ensure soundness, we must paint unreachable code as such, by inserting an
+ // unconditional ForceOSRExit wherever we find that a node would have always exited.
+ // This will only happen in cases where we are making static speculations, or we're
+ // making totally wrong speculations due to imprecision on the prediction propagator.
+ bool paintUnreachableCode(BlockIndex blockIndex)
+ {
+ bool changed = false;
+
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog("Painting unreachable code in Block #%u.\n", blockIndex);
+#endif
+ BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+ m_state.beginBasicBlock(block);
+
+ for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
+ m_state.execute(indexInBlock);
+ if (m_state.isValid())
+ continue;
+
+ NodeIndex nodeIndex = block->at(indexInBlock);
+ Node& node = m_graph[nodeIndex];
+ switch (node.op()) {
+ case Return:
+ case Throw:
+ case ThrowReferenceError:
+ case ForceOSRExit:
+ // Do nothing. These nodes will already do the right thing.
+ break;
+
+ default:
+ Node forceOSRExit(ForceOSRExit, node.codeOrigin);
+ forceOSRExit.ref();
+ NodeIndex forceOSRExitIndex = m_graph.size();
+ m_graph.append(forceOSRExit);
+ m_insertionSet.append(indexInBlock, forceOSRExitIndex);
+ changed = true;
+ break;
+ }
+ break;
+ }
+ m_state.reset();
+ m_insertionSet.execute(*block);
+
+ return changed;
+ }
+
+ AbstractState m_state;
+ InsertionSet<NodeIndex> m_insertionSet;
};
bool performConstantFolding(Graph& graph)
diff --git a/Source/JavaScriptCore/dfg/DFGVariableEventStream.cpp b/Source/JavaScriptCore/dfg/DFGVariableEventStream.cpp
index 5d548a7..a1152bc 100644
--- a/Source/JavaScriptCore/dfg/DFGVariableEventStream.cpp
+++ b/Source/JavaScriptCore/dfg/DFGVariableEventStream.cpp
@@ -102,6 +102,10 @@
while (at(startIndex).kind() != Reset)
startIndex--;
+#if DFG_ENABLE(DEBUG_VERBOSE)
+ dataLog("Computing OSR exit recoveries starting at seq#%u.\n", startIndex);
+#endif
+
// Step 2: Create a mock-up of the DFG's state and execute the events.
Operands<ValueSource> operandSources(codeBlock->numParameters(), numVariables);
Vector<MinifiedGenerationInfo, 32> generationInfos(graph.originalGraphSize());
