Index: clang/include/clang/Analysis/FlowSensitive/DataflowValues.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ clang/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -168,4 +168,4 @@ }; } // end namespace clang -#endif +#endif // LLVM_CLANG_ANALYSES_DATAFLOW_VALUES Index: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h @@ -0,0 +1,86 @@ +//===- DataflowWorklist.h ---------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// A simple and reusable worklist for flow-sensitive analyses. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H + +#include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/PriorityQueue.h" + +namespace clang { +template class DataflowWorklistBase { + llvm::BitVector EnqueuedBlocks; + PostOrderCFGView *POV; + llvm::PriorityQueue, Comp> + WorkList; + +public: + DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C) + : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {} + + const PostOrderCFGView *getCFGView() const { return POV; } + + void enqueueBlock(const CFGBlock *Block) { + if (Block && !EnqueuedBlocks[Block->getBlockID()]) { + EnqueuedBlocks[Block->getBlockID()] = true; + WorkList.push(Block); + } + } + + const CFGBlock *dequeue() { + if (WorkList.empty()) + return nullptr; + const CFGBlock *B = WorkList.top(); + WorkList.pop(); + EnqueuedBlocks[B->getBlockID()] = false; + return B; + } +}; + +struct ReversePostOrderCompare { + PostOrderCFGView::BlockOrderCompare Cmp; + bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const { + return Cmp(rhs, lhs); + } +}; + +struct ForwardDataflowWorklist + : DataflowWorklistBase { + ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx) + : DataflowWorklistBase( + Cfg, Ctx.getAnalysis(), + ReversePostOrderCompare{ + Ctx.getAnalysis()->getComparator()}) {} + + void enqueueSuccessors(const CFGBlock *Block) { + for (auto B : Block->succs()) + enqueueBlock(B); + } +}; + +struct BackwardDataflowWorklist + : DataflowWorklistBase { + BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx) + : DataflowWorklistBase( + Cfg, Ctx.getAnalysis(), + Ctx.getAnalysis()->getComparator()) {} + + void enqueuePredecessors(const CFGBlock *Block) { + for (auto B : Block->preds()) + enqueueBlock(B); + } +}; + +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H Index: clang/lib/Analysis/LiveVariables.cpp =================================================================== --- clang/lib/Analysis/LiveVariables.cpp +++ clang/lib/Analysis/LiveVariables.cpp @@ -13,63 +13,16 @@ #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/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowWorklist.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/PriorityQueue.h" #include "llvm/Support/raw_ostream.h" #include #include using namespace clang; -namespace { - -class DataflowWorklist { - llvm::BitVector enqueuedBlocks; - PostOrderCFGView *POV; - llvm::PriorityQueue, - PostOrderCFGView::BlockOrderCompare> worklist; - -public: - DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) - : enqueuedBlocks(cfg.getNumBlockIDs()), - POV(Ctx.getAnalysis()), - worklist(POV->getComparator()) {} - - void enqueueBlock(const CFGBlock *block); - void enqueuePredecessors(const CFGBlock *block); - - const CFGBlock *dequeue(); -}; - -} - -void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { - if (block && !enqueuedBlocks[block->getBlockID()]) { - enqueuedBlocks[block->getBlockID()] = true; - worklist.push(block); - } -} - -void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { - for (CFGBlock::const_pred_iterator I = block->pred_begin(), - E = block->pred_end(); I != E; ++I) { - enqueueBlock(*I); - } -} - -const CFGBlock *DataflowWorklist::dequeue() { - if (worklist.empty()) - return nullptr; - const CFGBlock *b = worklist.top(); - worklist.pop(); - enqueuedBlocks[b->getBlockID()] = false; - return b; -} - namespace { class LiveVariablesImpl { public: @@ -136,7 +89,7 @@ } return A; } -} +} // namespace void LiveVariables::Observer::anchor() { } @@ -218,7 +171,7 @@ void VisitUnaryOperator(UnaryOperator *UO); void Visit(Stmt *S); }; -} +} // namespace static const VariableArrayType *FindVA(QualType Ty) { const Type *ty = Ty.getTypePtr(); @@ -555,7 +508,7 @@ // Construct the dataflow worklist. Enqueue the exit block as the // start of the analysis. - DataflowWorklist worklist(*cfg, AC); + BackwardDataflowWorklist worklist(*cfg, AC); llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); // FIXME: we should enqueue using post order. Index: clang/lib/Analysis/UninitializedValues.cpp =================================================================== --- clang/lib/Analysis/UninitializedValues.cpp +++ clang/lib/Analysis/UninitializedValues.cpp @@ -24,6 +24,7 @@ #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" +#include "clang/Analysis/FlowSensitive/DataflowWorklist.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" @@ -212,68 +213,6 @@ return scratch[idx.getValue()]; } -//------------------------------------------------------------------------====// -// 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(); -}; - -} // namespace - -void DataflowWorklist::enqueueSuccessors(const 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. //====------------------------------------------------------------------------// @@ -924,7 +863,15 @@ } // Proceed with the workist. - DataflowWorklist worklist(cfg, *ac.getAnalysis()); + ForwardDataflowWorklist worklist(cfg, ac); + // Populate the initial queue. + { + auto it = worklist.getCFGView()->begin(); + auto end = worklist.getCFGView()->end(); + ++it; // Treat start as analyzed. + for (; it != end; ++it) + worklist.enqueueBlock(*it); + } llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); worklist.enqueueSuccessors(&cfg.getEntry()); llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);