From 12ce6d91a1b1acde9762c82e206343c1fef1d4a5 Mon Sep 17 00:00:00 2001 From: Artyom Skrobov Date: Mon, 28 Jul 2014 08:47:38 +0000 Subject: [PATCH] Factoring DataflowWorklist out of LiveVariables and UninitializedValues analyses llvm-svn: 214064 --- .../clang/Analysis/Analyses/DataflowWorklist.h | 53 +++++++++++++ clang/lib/Analysis/CMakeLists.txt | 1 + clang/lib/Analysis/DataflowWorklist.cpp | 92 ++++++++++++++++++++++ clang/lib/Analysis/LiveVariables.cpp | 56 +------------ clang/lib/Analysis/UninitializedValues.cpp | 64 +-------------- 5 files changed, 149 insertions(+), 117 deletions(-) create mode 100644 clang/include/clang/Analysis/Analyses/DataflowWorklist.h create mode 100644 clang/lib/Analysis/DataflowWorklist.cpp diff --git a/clang/include/clang/Analysis/Analyses/DataflowWorklist.h b/clang/include/clang/Analysis/Analyses/DataflowWorklist.h new file mode 100644 index 0000000..9afaae9 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/DataflowWorklist.h @@ -0,0 +1,53 @@ +//===- DataflowWorklist.h - worklist for dataflow analysis --------*- C++ --*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// DataflowWorklist is used in LiveVariables and UninitializedValues analyses +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_DATAFLOW_WORKLIST +#define LLVM_CLANG_DATAFLOW_WORKLIST + +#include "clang/Analysis/Analyses/PostOrderCFGView.h" + +namespace clang { + +class DataflowWorklist { + PostOrderCFGView::iterator PO_I, PO_E; + PostOrderCFGView::BlockOrderCompare comparator; + SmallVector worklist; + llvm::BitVector enqueuedBlocks; + + DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) + : PO_I(view.begin()), PO_E(view.end()), + comparator(view.getComparator()), + enqueuedBlocks(cfg.getNumBlockIDs(), true) { + // Treat the first block as already analyzed. + if (PO_I != PO_E) { + assert(*PO_I == &cfg.getEntry()); + enqueuedBlocks[(*PO_I)->getBlockID()] = false; + ++PO_I; + } + } + +public: + DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) + : DataflowWorklist(cfg, *Ctx.getAnalysis()) {} + + void enqueueBlock(const CFGBlock *block); + void enqueuePredecessors(const CFGBlock *block); + void enqueueSuccessors(const CFGBlock *block); + const CFGBlock *dequeue(); + + void sortWorklist(); +}; + +} // end clang namespace + +#endif diff --git a/clang/lib/Analysis/CMakeLists.txt b/clang/lib/Analysis/CMakeLists.txt index 461ffb0..0f5ec76 100644 --- a/clang/lib/Analysis/CMakeLists.txt +++ b/clang/lib/Analysis/CMakeLists.txt @@ -12,6 +12,7 @@ add_clang_library(clangAnalysis CocoaConventions.cpp Consumed.cpp Dominators.cpp + DataflowWorklist.cpp FormatString.cpp LiveVariables.cpp ObjCNoReturn.cpp diff --git a/clang/lib/Analysis/DataflowWorklist.cpp b/clang/lib/Analysis/DataflowWorklist.cpp new file mode 100644 index 0000000..9b4f4f7 --- /dev/null +++ b/clang/lib/Analysis/DataflowWorklist.cpp @@ -0,0 +1,92 @@ +//===- DataflowWorklist.cpp - worklist for dataflow analysis ------*- C++ --*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// DataflowWorklist is used in LiveVariables and UninitializedValues analyses +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/DataflowWorklist.h" + +using namespace clang; + +// Marking a block as enqueued means that it cannot be re-added to the worklist, +// 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 +// until we enqueue something on the worklist. +void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { + if (block && !enqueuedBlocks[block->getBlockID()]) { + enqueuedBlocks[block->getBlockID()] = true; + worklist.push_back(block); + } +} + +// The forward analysis alternates between essentially two worklists. +// A prioritization worklist (SmallVector worklist) +// is consulted first, and if it's empty, we consult the reverse +// post-order traversal (PostOrderCFGView::iterator PO_I). +// 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 +// we want to prioritize analyzing first, because that causes dataflow facts +// to flow up the graph, which we then want to propagate forward. +// In practice this can cause the analysis to converge much faster. +void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { + for (CFGBlock::const_succ_iterator I = block->succ_begin(), + E = block->succ_end(); I != E; ++I) { + enqueueBlock(*I); + } +} + +// 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() { + const CFGBlock *B = nullptr; + + // First dequeue from the worklist. This can represent + // updates along backedges that we want propagated as quickly as possible. + 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. + else if (PO_I != PO_E) { + B = *PO_I; + ++PO_I; + } + else { + return nullptr; + } + + assert(enqueuedBlocks[B->getBlockID()] == true); + enqueuedBlocks[B->getBlockID()] = false; + 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 3d6fc03..dcde5e7 100644 --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -14,11 +14,10 @@ #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" -#include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/Analyses/DataflowWorklist.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/PostOrderIterator.h" #include "llvm/Support/raw_ostream.h" #include #include @@ -26,59 +25,6 @@ using namespace clang; namespace { - -class DataflowWorklist { - SmallVector worklist; - llvm::BitVector enqueuedBlocks; - PostOrderCFGView *POV; -public: - DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) - : enqueuedBlocks(cfg.getNumBlockIDs()), - POV(Ctx.getAnalysis()) {} - - void enqueueBlock(const CFGBlock *block); - void enqueuePredecessors(const CFGBlock *block); - - const CFGBlock *dequeue(); - - void sortWorklist(); -}; - -} - -void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { - if (block && !enqueuedBlocks[block->getBlockID()]) { - enqueuedBlocks[block->getBlockID()] = true; - worklist.push_back(block); - } -} - -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(); -} - -void DataflowWorklist::sortWorklist() { - std::sort(worklist.begin(), worklist.end(), POV->getComparator()); -} - -const CFGBlock *DataflowWorklist::dequeue() { - if (worklist.empty()) - return nullptr; - const CFGBlock *b = worklist.pop_back_val(); - enqueuedBlocks[b->getBlockID()] = false; - return b; -} - -namespace { class LiveVariablesImpl { public: AnalysisDeclContext &analysisContext; diff --git a/clang/lib/Analysis/UninitializedValues.cpp b/clang/lib/Analysis/UninitializedValues.cpp index f5c786a..b6702b0 100644 --- a/clang/lib/Analysis/UninitializedValues.cpp +++ b/clang/lib/Analysis/UninitializedValues.cpp @@ -15,7 +15,7 @@ #include "clang/AST/Attr.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" -#include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/Analyses/DataflowWorklist.h" #include "clang/Analysis/Analyses/UninitializedValues.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" @@ -199,66 +199,6 @@ ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { } //------------------------------------------------------------------------====// -// Worklist: worklist for dataflow analysis. -//====------------------------------------------------------------------------// - -namespace { -class DataflowWorklist { - PostOrderCFGView::iterator PO_I, PO_E; - SmallVector worklist; - llvm::BitVector enqueuedBlocks; -public: - DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) - : PO_I(view.begin()), PO_E(view.end()), - enqueuedBlocks(cfg.getNumBlockIDs(), true) { - // Treat the first block as already analyzed. - if (PO_I != PO_E) { - assert(*PO_I == &cfg.getEntry()); - enqueuedBlocks[(*PO_I)->getBlockID()] = false; - ++PO_I; - } - } - - void enqueueSuccessors(const CFGBlock *block); - const CFGBlock *dequeue(); -}; -} - -void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { - for (CFGBlock::const_succ_iterator I = block->succ_begin(), - E = block->succ_end(); I != E; ++I) { - const CFGBlock *Successor = *I; - if (!Successor || enqueuedBlocks[Successor->getBlockID()]) - continue; - worklist.push_back(Successor); - enqueuedBlocks[Successor->getBlockID()] = true; - } -} - -const CFGBlock *DataflowWorklist::dequeue() { - const CFGBlock *B = nullptr; - - // First dequeue from the worklist. This can represent - // updates along backedges that we want propagated as quickly as possible. - 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. - else if (PO_I != PO_E) { - B = *PO_I; - ++PO_I; - } - else { - return nullptr; - } - - assert(enqueuedBlocks[B->getBlockID()] == true); - enqueuedBlocks[B->getBlockID()] = false; - return B; -} - -//------------------------------------------------------------------------====// // Classification of DeclRefExprs as use or initialization. //====------------------------------------------------------------------------// @@ -831,7 +771,7 @@ void clang::runUninitializedVariablesAnalysis( } // Proceed with the workist. - DataflowWorklist worklist(cfg, *ac.getAnalysis()); + DataflowWorklist worklist(cfg, ac); llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); worklist.enqueueSuccessors(&cfg.getEntry()); llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); -- 2.7.4