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

5 files changed, 69 insertions, 39 deletions

diff --git a/clang/lib/Analysis/Consumed.cpp b/clang/lib/Analysis/Consumed.cpp
index 2b2da2c69a4..47239d098cd 100644
--- a/clang/lib/Analysis/Consumed.cpp
+++ b/clang/lib/Analysis/Consumed.cpp
@@ -1360,7 +1360,7 @@ void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
 
   determineExpectedReturnState(AC, D);
 
-  PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+  PostOrderCFGView *SortedGraph = AC.getAnalysis<ReversePostOrderCFGView>();
   // AC.getCFG()->viewCFG(LangOptions());
   
   BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
diff --git a/clang/lib/Analysis/DataflowWorklist.cpp b/clang/lib/Analysis/DataflowWorklist.cpp
index 9b4f4f7d84a..9cc2a934e63 100644
--- a/clang/lib/Analysis/DataflowWorklist.cpp
+++ b/clang/lib/Analysis/DataflowWorklist.cpp
@@ -19,7 +19,7 @@ using namespace clang;
 // but it doesn't control when the algorithm terminates.
 // Initially, enqueuedBlocks is set to true for all blocks;
 // that's not because everything is added initially to the worklist,
-// but instead, to cause the forward analysis to follow the reverse post order
+// but instead, to cause the analysis to follow the initial graph traversal
 // until we enqueue something on the worklist. 
 void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
   if (block && !enqueuedBlocks[block->getBlockID()]) {
@@ -28,10 +28,11 @@ void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
   }
 }
 
-// The forward analysis alternates between essentially two worklists.
+// The analysis alternates between essentially two worklists.
 // A prioritization worklist (SmallVector<const CFGBlock *> worklist)
-// is consulted first, and if it's empty, we consult the reverse
-// post-order traversal (PostOrderCFGView::iterator PO_I).
+// is consulted first, and if it's empty, we consult
+// PostOrderCFGView::iterator PO_I, which implements either post-order traversal
+// for backward analysis, or reverse post-order traversal for forward analysis.
 // The prioritization worklist is used to prioritize analyzing from
 // the beginning, or to prioritize updates fed by back edges.
 // Typically, what gets enqueued on the worklist are back edges, which
@@ -45,22 +46,11 @@ void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) {
   }
 }
 
-// The reverse analysis uses a simple re-sorting of the worklist to
-// reprioritize it.  It's not as efficient as the two-worklists approach,
-// but it isn't performance sensitive since it's used by the static analyzer,
-// and the static analyzer does far more work that dwarfs the work done here.
-// TODO: It would still be nice to use the same approach for both analyses.
 void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
-  const unsigned OldWorklistSize = worklist.size();
   for (CFGBlock::const_pred_iterator I = block->pred_begin(),
        E = block->pred_end(); I != E; ++I) {
     enqueueBlock(*I);
   }
-
-  if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
-    return;
-
-  sortWorklist();
 }
 
 const CFGBlock *DataflowWorklist::dequeue() {
@@ -71,8 +61,9 @@ const CFGBlock *DataflowWorklist::dequeue() {
   if (!worklist.empty())
     B = worklist.pop_back_val();
 
-  // Next dequeue from the initial reverse post order.  This is the
-  // theoretical ideal in the presence of no back edges.
+  // Next dequeue from the initial graph traversal (either post order or
+  // reverse post order).  This is the theoretical ideal in the presence
+  // of no back edges.
   else if (PO_I != PO_E) {
     B = *PO_I;
     ++PO_I;
@@ -86,7 +77,3 @@ const CFGBlock *DataflowWorklist::dequeue() {
   return B;
 }
 
-void DataflowWorklist::sortWorklist() {
-  std::sort(worklist.begin(), worklist.end(), comparator);
-}
-
diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp
index dcde5e7619f..77f7dc386e6 100644
--- a/clang/lib/Analysis/LiveVariables.cpp
+++ b/clang/lib/Analysis/LiveVariables.cpp
@@ -448,21 +448,18 @@ LiveVariables::computeLiveness(AnalysisDeclContext &AC,
 
   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 @@ LiveVariables::computeLiveness(AnalysisDeclContext &AC,
           }
         }
       }
-  }
-  
-  worklist.sortWorklist();
+      scannedForAssignments[block->getBlockID()] = true;
+    }
   
-  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];
diff --git a/clang/lib/Analysis/PostOrderCFGView.cpp b/clang/lib/Analysis/PostOrderCFGView.cpp
index 5a3c8182a14..714292b3f98 100644
--- a/clang/lib/Analysis/PostOrderCFGView.cpp
+++ b/clang/lib/Analysis/PostOrderCFGView.cpp
@@ -7,7 +7,7 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements post order view of the blocks in a CFG.
+// This file implements post order views of the blocks in a CFG.
 //
 //===----------------------------------------------------------------------===//
 
@@ -17,14 +17,16 @@ using namespace clang;
 
 void PostOrderCFGView::anchor() { }
 
-PostOrderCFGView::PostOrderCFGView(const CFG *cfg) {
+ReversePostOrderCFGView::ReversePostOrderCFGView(const CFG *cfg) {
   Blocks.reserve(cfg->getNumBlockIDs());
   CFGBlockSet BSet(cfg);
-    
+
+  typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator;
+
   for (po_iterator I = po_iterator::begin(cfg, BSet),
                    E = po_iterator::end(cfg, BSet); I != E; ++I) {
-    BlockOrder[*I] = Blocks.size() + 1;
     Blocks.push_back(*I);      
+    BlockOrder[*I] = Blocks.size();
   }
 }
 
@@ -47,3 +49,49 @@ bool PostOrderCFGView::BlockOrderCompare::operator()(const CFGBlock *b1,
   return b1V > b2V;
 }
 
+PostOrderCFGView::PostOrderCFGView(const CFG *cfg) {
+  unsigned size = cfg->getNumBlockIDs();
+  Blocks.reserve(size);
+  CFGBlockSet BSet(cfg);
+
+  typedef llvm::po_iterator<const CFG*, CFGBlockSet, true,
+                            llvm::GraphTraits<llvm::Inverse<const CFG*> >
+                           > po_iterator;
+
+  for (po_iterator I = po_iterator::begin(cfg, BSet),
+                   E = po_iterator::end(cfg, BSet); I != E; ++I) {
+    Blocks.push_back(*I);      
+    BlockOrder[*I] = Blocks.size();
+  }
+
+  // It may be that some blocks are inaccessible going from the CFG exit upwards
+  // (e.g. infinite loops); we still need to add them.
+  for (CFG::const_iterator I = cfg->begin(), E = cfg->end();
+       (Blocks.size() < size) && (I != E); ++I) {
+    const CFGBlock* block = *I;
+    // Add a chain going upwards.
+    while (!BlockOrder.count(block)) {
+      Blocks.push_back(block);
+      BlockOrder[block] = Blocks.size();
+      CFGBlock::const_pred_iterator PI = block->pred_begin(),
+                                    PE = block->pred_end();
+      for (; PI != PE; ++PI) {
+        const CFGBlock* pred = *PI;
+        if (pred && !BlockOrder.count(pred)) {
+          block = pred;
+          break;
+        }
+      }
+      // Chain ends when we couldn't find an unmapped pred.
+      if (PI == PE) break;
+    }
+  }
+}
+
+ReversePostOrderCFGView *
+ReversePostOrderCFGView::create(AnalysisDeclContext &ctx) {
+  const CFG *cfg = ctx.getCFG();
+  if (!cfg)
+    return nullptr;
+  return new ReversePostOrderCFGView(cfg);
+}
diff --git a/clang/lib/Analysis/UninitializedValues.cpp b/clang/lib/Analysis/UninitializedValues.cpp
index b6702b0609c..0f93fe8981c 100644
--- a/clang/lib/Analysis/UninitializedValues.cpp
+++ b/clang/lib/Analysis/UninitializedValues.cpp
@@ -771,7 +771,7 @@ void clang::runUninitializedVariablesAnalysis(
   }
 
   // Proceed with the workist.
-  DataflowWorklist worklist(cfg, ac);
+  ForwardDataflowWorklist worklist(cfg, ac);
   llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
   worklist.enqueueSuccessors(&cfg.getEntry());
   llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);