Use the proper post-order traversal in LiveVariables analysis,
to recover the performance after r214064.
Also sorts out the naming for PostOrderCFGView, ReversePostOrderCFGView,
BackwardDataflowWorklist and ForwardDataflowWorklist, to match the accepted
terminology.
Also unifies BackwardDataflowWorklist and ForwardDataflowWorklist to share
the "worklist for prioritization, post-order traversal for fallback" logic,
and to avoid repetitive sorting.
Also cleans up comments in the affected area.
llvm-svn: 215650
diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp
index dcde5e7..77f7dc3 100644
--- a/clang/lib/Analysis/LiveVariables.cpp
+++ b/clang/lib/Analysis/LiveVariables.cpp
@@ -448,21 +448,18 @@
LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
- // Construct the dataflow worklist. Enqueue the exit block as the
- // start of the analysis.
- DataflowWorklist worklist(*cfg, AC);
+ // Construct the backward dataflow worklist.
+ BackwardDataflowWorklist worklist(*cfg, AC);
llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
+ llvm::BitVector scannedForAssignments(cfg->getNumBlockIDs());
- // FIXME: we should enqueue using post order.
- for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
- const CFGBlock *block = *it;
- worklist.enqueueBlock(block);
+ while (const CFGBlock *block = worklist.dequeue()) {
// FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
// We need to do this because we lack context in the reverse analysis
// to determine if a DeclRefExpr appears in such a context, and thus
// doesn't constitute a "use".
- if (killAtAssign)
+ if (killAtAssign && !scannedForAssignments[block->getBlockID()]) {
for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
bi != be; ++bi) {
if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
@@ -477,11 +474,9 @@
}
}
}
- }
+ scannedForAssignments[block->getBlockID()] = true;
+ }
- worklist.sortWorklist();
-
- while (const CFGBlock *block = worklist.dequeue()) {
// Determine if the block's end value has changed. If not, we
// have nothing left to do for this block.
LivenessValues &prevVal = LV->blocksEndToLiveness[block];