DFG should have sparse conditional constant propagation
https://bugs.webkit.org/show_bug.cgi?id=86580
Reviewed by Oliver Hunt.
Merged r117370 from dfgopt.
This enhances CFA so that if it suspects at any point during the fixpoint that a
branch will only go one way, then it only propagates in that one way.
This vastly increases the opportunities for CFG simplification. For example, it
enables us to evaporate this loop:
for (var i = 0; i < 1; ++i) doThings(i);
As a result, it uncovered loads of bugs in the CFG simplifier. In particular:
- Phi fixup was assuming that all Phis worth fixing up are shouldGenerate().
That's not true; we also fixup Phis that are dead.
- GetLocal fixup was assuming that it's only necessary to rewire links to a
GetLocal, and that the GetLocal's own links don't need to be rewired. Untrue,
because the GetLocal may not be rewirable (first block has no GetLocal for r42
but second block does have a GetLocal), in which case it will refer to a Phi
in the second block. We need it to refer to a Phi from the first block to
ensure that subsequent transformations work.
- Tail operand fixup was ignoring the fact that Phis in successors may contain
references to the children of our tail variables. Hence, successor Phi child
substitution needs to use the original second block variable table as its
prior, rather than trying to reconstruct the prior later (since by that point
the children of the second block's tail variables will have been fixed up, so
we will not know what the prior would have been).
* dfg/DFGAbstractState.cpp:
(JSC::DFG::AbstractState::beginBasicBlock):
(JSC::DFG::AbstractState::endBasicBlock):
(JSC::DFG::AbstractState::reset):
(JSC::DFG::AbstractState::execute):
(JSC::DFG::AbstractState::mergeToSuccessors):
* dfg/DFGAbstractState.h:
(JSC::DFG::AbstractState::branchDirectionToString):
(AbstractState):
* dfg/DFGCFGSimplificationPhase.cpp:
(JSC::DFG::CFGSimplificationPhase::run):
(JSC::DFG::CFGSimplificationPhase::removePotentiallyDeadPhiReference):
(JSC::DFG::CFGSimplificationPhase::OperandSubstitution::OperandSubstitution):
(OperandSubstitution):
(JSC::DFG::CFGSimplificationPhase::skipGetLocal):
(JSC::DFG::CFGSimplificationPhase::recordPossibleIncomingReference):
(CFGSimplificationPhase):
(JSC::DFG::CFGSimplificationPhase::fixTailOperand):
(JSC::DFG::CFGSimplificationPhase::mergeBlocks):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::changeEdge):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@118309 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractState.cpp b/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
index 569a3e1..5c5b7ab 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
+++ b/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
@@ -92,6 +92,7 @@
m_block = basicBlock;
m_isValid = true;
m_foundConstants = false;
+ m_branchDirection = InvalidBranchDirection;
}
void AbstractState::initialize(Graph& graph)
@@ -174,7 +175,7 @@
}
}
-bool AbstractState::endBasicBlock(MergeMode mergeMode)
+bool AbstractState::endBasicBlock(MergeMode mergeMode, BranchDirection* branchDirectionPtr)
{
PROFILE(FLAG_FOR_BLOCK_END);
ASSERT(m_block);
@@ -224,18 +225,27 @@
ASSERT(mergeMode != DontMerge || !changed);
+ BranchDirection branchDirection = m_branchDirection;
+ if (branchDirectionPtr)
+ *branchDirectionPtr = branchDirection;
+
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog(" Branch direction = %s\n", branchDirectionToString(branchDirection));
+#endif
+
reset();
if (mergeMode != MergeToSuccessors)
return changed;
- return mergeToSuccessors(m_graph, block);
+ return mergeToSuccessors(m_graph, block, branchDirection);
}
void AbstractState::reset()
{
m_block = 0;
m_isValid = false;
+ m_branchDirection = InvalidBranchDirection;
}
bool AbstractState::execute(unsigned indexInBlock)
@@ -569,16 +579,8 @@
case LogicalNot: {
JSValue childConst = forNode(node.child1()).value();
if (childConst) {
- if (childConst.isNumber()) {
- forNode(nodeIndex).set(jsBoolean(!childConst.asNumber()));
- m_foundConstants = true;
- break;
- }
- if (childConst.isBoolean()) {
- forNode(nodeIndex).set(jsBoolean(!childConst.asBoolean()));
- m_foundConstants = true;
- break;
- }
+ forNode(nodeIndex).set(jsBoolean(!childConst.toBoolean()));
+ break;
}
Node& child = m_graph[node.child1()];
if (isBooleanPrediction(child.prediction()))
@@ -952,9 +954,22 @@
break;
case Branch: {
- // There is probably profit to be found in doing sparse conditional constant
- // propagation, and to take it one step further, where a variable's value
- // is specialized on each direction of a branch. For now, we don't do this.
+ JSValue value = forNode(node.child1()).value();
+ if (value) {
+ bool booleanValue = value.toBoolean();
+ if (booleanValue)
+ m_branchDirection = TakeTrue;
+ else
+ m_branchDirection = TakeFalse;
+ break;
+ }
+ // FIXME: The above handles the trivial cases of sparse conditional
+ // constant propagation, but we can do better:
+ // 1) If the abstract value does not have a concrete value but describes
+ // something that is known to evaluate true (or false) then we ought
+ // to sparse conditional that.
+ // 2) We can specialize the source variable's value on each direction of
+ // the branch.
Node& child = m_graph[node.child1()];
if (child.shouldSpeculateBoolean())
forNode(node.child1()).filter(PredictBoolean);
@@ -966,6 +981,7 @@
forNode(node.child1()).filter(PredictInt32);
else if (child.shouldSpeculateNumber())
forNode(node.child1()).filter(PredictNumber);
+ m_branchDirection = TakeBoth;
break;
}
@@ -1489,7 +1505,8 @@
return changed;
}
-inline bool AbstractState::mergeToSuccessors(Graph& graph, BasicBlock* basicBlock)
+inline bool AbstractState::mergeToSuccessors(
+ Graph& graph, BasicBlock* basicBlock, BranchDirection branchDirection)
{
PROFILE(FLAG_FOR_MERGE_TO_SUCCESSORS);
@@ -1499,6 +1516,7 @@
switch (terminal.op()) {
case Jump: {
+ ASSERT(branchDirection == InvalidBranchDirection);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
#endif
@@ -1506,21 +1524,25 @@
}
case Branch: {
+ ASSERT(branchDirection != InvalidBranchDirection);
bool changed = false;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
#endif
- changed |= merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
+ if (branchDirection != TakeFalse)
+ changed |= merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.notTakenBlockIndex());
#endif
- changed |= merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
+ if (branchDirection != TakeTrue)
+ changed |= merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
return changed;
}
case Return:
case Throw:
case ThrowReferenceError:
+ ASSERT(branchDirection == InvalidBranchDirection);
return false;
default:
