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/PostOrderCFGView.cpp b/clang/lib/Analysis/PostOrderCFGView.cpp
index 5a3c8182..714292b 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 @@
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 @@
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);
+}