Diff
Modified: branches/dfgopt/Source/_javascript_Core/ChangeLog (117369 => 117370)
--- branches/dfgopt/Source/_javascript_Core/ChangeLog 2012-05-17 00:30:35 UTC (rev 117369)
+++ branches/dfgopt/Source/_javascript_Core/ChangeLog 2012-05-17 00:42:17 UTC (rev 117370)
@@ -1,3 +1,59 @@
+2012-05-16 Filip Pizlo <fpi...@apple.com>
+
+ DFG should have sparse conditional constant propagation
+ https://bugs.webkit.org/show_bug.cgi?id=86580
+
+ Reviewed by Oliver Hunt.
+
+ 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):
+
2012-05-14 Filip Pizlo <fpi...@apple.com>
DFG should optimize inlined uses of arguments.length and arguments[i]
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGAbstractState.cpp (117369 => 117370)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGAbstractState.cpp 2012-05-17 00:30:35 UTC (rev 117369)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGAbstractState.cpp 2012-05-17 00:42:17 UTC (rev 117370)
@@ -92,6 +92,7 @@
m_block = basicBlock;
m_isValid = true;
m_foundConstants = false;
+ m_branchDirection = InvalidBranchDirection;
}
void AbstractState::initialize(Graph& graph)
@@ -176,7 +177,7 @@
}
}
-bool AbstractState::endBasicBlock(MergeMode mergeMode)
+bool AbstractState::endBasicBlock(MergeMode mergeMode, BranchDirection* branchDirectionPtr)
{
PROFILE(FLAG_FOR_BLOCK_END);
ASSERT(m_block);
@@ -226,18 +227,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)
@@ -552,16 +562,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()))
@@ -950,9 +952,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);
@@ -964,6 +979,7 @@
forNode(node.child1()).filter(PredictInt32);
else if (child.shouldSpeculateNumber())
forNode(node.child1()).filter(PredictNumber);
+ m_branchDirection = TakeBoth;
break;
}
@@ -1499,7 +1515,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);
@@ -1509,6 +1526,7 @@
switch (terminal.op()) {
case Jump: {
+ ASSERT(branchDirection == InvalidBranchDirection);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
#endif
@@ -1516,21 +1534,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:
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGAbstractState.h (117369 => 117370)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGAbstractState.h 2012-05-17 00:30:35 UTC (rev 117369)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGAbstractState.h 2012-05-17 00:42:17 UTC (rev 117370)
@@ -92,6 +92,36 @@
MergeToSuccessors
};
+ enum BranchDirection {
+ // This is not a branch and so there is no branch direction, or
+ // the branch direction has yet to be set.
+ InvalidBranchDirection,
+
+ // The branch takes the true case.
+ TakeTrue,
+
+ // The branch takes the false case.
+ TakeFalse,
+
+ // For all we know, the branch could go either direction, so we
+ // have to assume the worst.
+ TakeBoth
+ };
+
+ static const char* branchDirectionToString(BranchDirection branchDirection)
+ {
+ switch (branchDirection) {
+ case InvalidBranchDirection:
+ return "Invalid";
+ case TakeTrue:
+ return "TakeTrue";
+ case TakeFalse:
+ return "TakeFalse";
+ case TakeBoth:
+ return "TakeBoth";
+ }
+ }
+
AbstractState(Graph&);
~AbstractState();
@@ -139,7 +169,11 @@
// A true return means that you must revisit (at least) the successor
// blocks. This also sets cfaShouldRevisit to true for basic blocks
// that must be visited next.
- bool endBasicBlock(MergeMode);
+ //
+ // If you'd like to know what direction the branch at the end of the
+ // basic block is thought to have taken, you can pass a non-0 pointer
+ // for BranchDirection.
+ bool endBasicBlock(MergeMode, BranchDirection* = 0);
// Reset the AbstractState. This throws away any results, and at this point
// you can safely call beginBasicBlock() on any basic block.
@@ -169,7 +203,7 @@
// successors. Returns true if any of the successors' states changed. Note
// that this is automatically called in endBasicBlock() if MergeMode is
// MergeToSuccessors.
- bool mergeToSuccessors(Graph&, BasicBlock*);
+ bool mergeToSuccessors(Graph&, BasicBlock*, BranchDirection);
void dump(FILE* out);
@@ -190,6 +224,8 @@
bool m_foundConstants;
bool m_isValid;
+
+ BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
};
} } // namespace JSC::DFG
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp (117369 => 117370)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2012-05-17 00:30:35 UTC (rev 117369)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2012-05-17 00:42:17 UTC (rev 117370)
@@ -46,6 +46,8 @@
bool run()
{
+ const bool extremeLogging = false;
+
bool outerChanged = false;
bool innerChanged;
@@ -67,6 +69,8 @@
dataLog("CFGSimplify: Jump merge on Block #%u to Block #%u.\n",
blockIndex, m_graph.successor(block, 0));
#endif
+ if (extremeLogging)
+ m_graph.dump();
mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock);
innerChanged = outerChanged = true;
break;
@@ -107,6 +111,8 @@
blockIndex, m_graph.successorForCondition(block, condition),
m_graph.successorForCondition(block, !condition));
#endif
+ if (extremeLogging)
+ m_graph.dump();
mergeBlocks(
blockIndex,
m_graph.successorForCondition(block, condition),
@@ -118,6 +124,8 @@
blockIndex, m_graph.successorForCondition(block, condition),
m_graph.successorForCondition(block, !condition));
#endif
+ if (extremeLogging)
+ m_graph.dump();
BlockIndex takenBlockIndex = m_graph.successorForCondition(block, condition);
BlockIndex notTakenBlockIndex = m_graph.successorForCondition(block, !condition);
@@ -385,7 +393,8 @@
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLog(" Removing reference at child %u.", edgeIndex);
#endif
- m_graph.deref(myNodeIndex);
+ if (phiNode.shouldGenerate())
+ m_graph.deref(myNodeIndex);
for (unsigned i = edgeIndex; i < AdjacencyList::Size - 1; ++i)
phiNode.children.setChild(i, phiNode.children.child(i + 1));
phiNode.children.setChild(AdjacencyList::Size - 1, Edge());
@@ -398,6 +407,12 @@
{
}
+ explicit OperandSubstitution(NodeIndex oldChild)
+ : oldChild(oldChild)
+ , newChild(oldChild)
+ {
+ }
+
OperandSubstitution(NodeIndex oldChild, NodeIndex newChild)
: oldChild(oldChild)
, newChild(newChild)
@@ -419,14 +434,25 @@
NodeIndex skipGetLocal(NodeIndex nodeIndex)
{
+ if (nodeIndex == NoNode)
+ return NoNode;
Node& node = m_graph[nodeIndex];
if (node.op() == GetLocal)
return node.child1().index();
return nodeIndex;
}
- void fixTailOperand(BasicBlock* firstBlock, BasicBlock* secondBlock, int operand, Operands<OperandSubstitution>& substitutions)
+ void recordPossibleIncomingReference(
+ BasicBlock* secondBlock, Operands<OperandSubstitution>& substitutions, int operand)
{
+ substitutions.operand(operand) = OperandSubstitution(
+ skipGetLocal(secondBlock->variablesAtTail.operand(operand)));
+ }
+
+ void fixTailOperand(
+ BasicBlock* firstBlock, BasicBlock* secondBlock, int operand,
+ Operands<OperandSubstitution>& substitutions)
+ {
NodeIndex atSecondTail = secondBlock->variablesAtTail.operand(operand);
if (atSecondTail == NoNode) {
@@ -449,9 +475,8 @@
case Phi: {
// Keep what was in the first block.
ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode);
- substitutions.operand(operand) =
- OperandSubstitution(
- atSecondTail, skipGetLocal(firstBlock->variablesAtTail.operand(operand)));
+ substitutions.operand(operand).newChild =
+ skipGetLocal(firstBlock->variablesAtTail.operand(operand));
break;
}
@@ -461,6 +486,8 @@
// block doesn't even know about this variable.
if (secondNode.variableAccessData()->isCaptured()) {
firstBlock->variablesAtTail.operand(operand) = atSecondTail;
+ substitutions.operand(operand).newChild =
+ secondNode.child1().index();
break;
}
@@ -473,16 +500,16 @@
case SetArgument:
case Phi:
firstBlock->variablesAtTail.operand(operand) = atSecondTail;
+ substitutions.operand(operand).newChild =
+ secondNode.child1().index();
break;
default:
// Keep what was in the first block, and adjust the substitution to account for
// the fact that successors will refer to the child of the GetLocal.
ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode);
- substitutions.operand(operand) =
- OperandSubstitution(
- secondNode.child1().index(),
- skipGetLocal(firstBlock->variablesAtTail.operand(operand)));
+ substitutions.operand(operand).newChild =
+ skipGetLocal(firstBlock->variablesAtTail.operand(operand));
break;
}
break;
@@ -527,7 +554,17 @@
for (size_t i = 0; i < secondBlock->phis.size(); ++i)
firstBlock->phis.append(secondBlock->phis[i]);
-
+
+ // Before we start changing the second block's graph, record what nodes would
+ // be referenced by successors of the second block.
+ Operands<OperandSubstitution> substitutions(
+ secondBlock->variablesAtTail.numberOfArguments(),
+ secondBlock->variablesAtTail.numberOfLocals());
+ for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfArguments(); ++i)
+ recordPossibleIncomingReference(secondBlock, substitutions, argumentToOperand(i));
+ for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfLocals(); ++i)
+ recordPossibleIncomingReference(secondBlock, substitutions, i);
+
for (size_t i = 0; i < secondBlock->size(); ++i) {
NodeIndex nodeIndex = secondBlock->at(i);
Node& node = m_graph[nodeIndex];
@@ -549,17 +586,21 @@
break;
}
- case Flush: {
- // The flush could use a GetLocal, SetLocal, SetArgument, or a Phi.
+ case Flush:
+ case GetLocal: {
+ // A Flush could use a GetLocal, SetLocal, SetArgument, or a Phi.
// If it uses a GetLocal, it'll be taken care of below. If it uses a
// SetLocal or SetArgument, then it must be using a node from the
// same block. But if it uses a Phi, then we should redirect it to
// use whatever the first block advertised as a tail operand.
+ // Similarly for GetLocal; it could use any of those except for
+ // GetLocal. If it uses a Phi then it should be redirected to use a
+ // Phi from the tail operand.
if (m_graph[node.child1()].op() != Phi)
break;
NodeIndex atFirstIndex = firstBlock->variablesAtTail.operand(node.local());
- m_graph.changeEdge(node.children.child1(), Edge(atFirstIndex));
+ m_graph.changeEdge(node.children.child1(), Edge(atFirstIndex), node.shouldGenerate());
break;
}
@@ -608,9 +649,6 @@
fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex);
// Fix up the variables at tail.
- Operands<OperandSubstitution> substitutions(
- secondBlock->variablesAtHead.numberOfArguments(),
- secondBlock->variablesAtHead.numberOfLocals());
for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfArguments(); ++i)
fixTailOperand(firstBlock, secondBlock, argumentToOperand(i), substitutions);
for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfLocals(); ++i)
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGDriver.cpp (117369 => 117370)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGDriver.cpp 2012-05-17 00:30:35 UTC (rev 117369)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGDriver.cpp 2012-05-17 00:42:17 UTC (rev 117370)
@@ -51,7 +51,7 @@
ASSERT(codeBlock);
ASSERT(codeBlock->alternative());
ASSERT(codeBlock->alternative()->getJITType() == JITCode::BaselineJIT);
-
+
#if DFG_ENABLE(DEBUG_VERBOSE)
dataLog("DFG compiling code block %p(%p) for executable %p, number of instructions = %u.\n", codeBlock, codeBlock->alternative(), codeBlock->ownerExecutable(), codeBlock->instructionCount());
#endif
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.h (117369 => 117370)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.h 2012-05-17 00:30:35 UTC (rev 117369)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.h 2012-05-17 00:42:17 UTC (rev 117370)
@@ -128,10 +128,12 @@
edge.setIndex(newIndex);
}
- void changeEdge(Edge& edge, Edge newEdge)
+ void changeEdge(Edge& edge, Edge newEdge, bool changeRef = true)
{
- ref(newEdge);
- deref(edge);
+ if (changeRef) {
+ ref(newEdge);
+ deref(edge);
+ }
edge = newEdge;
}
