diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h b/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -168,4 +168,4 @@ }; } // end namespace clang -#endif +#endif // LLVM_CLANG_ANALYSES_DATAFLOW_VALUES diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h b/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h @@ -0,0 +1,94 @@ +//===- 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 { +/// A worklist implementation where the enqueued blocks will be dequeued based +/// on the order defined by 'Comp'. +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); + } +}; + +/// A worklist implementation for forward dataflow analysis. The enqueued +/// blocks will be dequeued in reverse post order. The worklist cannot contain +/// the same block multiple times at once. +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); + } +}; + +/// A worklist implementation for backward dataflow analysis. The enqueued +/// block will be dequeued in post order. The worklist cannot contain the same +/// block multiple times at once. +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 diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -13,12 +13,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/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 @@ -26,51 +24,6 @@ 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: AnalysisDeclContext &analysisContext; @@ -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. diff --git a/clang/lib/Analysis/UninitializedValues.cpp b/clang/lib/Analysis/UninitializedValues.cpp --- a/clang/lib/Analysis/UninitializedValues.cpp +++ b/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" @@ -213,68 +214,6 @@ } //------------------------------------------------------------------------====// -// 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,7 @@ } // Proceed with the workist. - DataflowWorklist worklist(cfg, *ac.getAnalysis()); + ForwardDataflowWorklist worklist(cfg, ac); llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); worklist.enqueueSuccessors(&cfg.getEntry()); llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); diff --git a/clang/unittests/Analysis/CFGBuildResult.h b/clang/unittests/Analysis/CFGBuildResult.h --- a/clang/unittests/Analysis/CFGBuildResult.h +++ b/clang/unittests/Analysis/CFGBuildResult.h @@ -23,18 +23,21 @@ BuiltCFG, }; - BuildResult(Status S, std::unique_ptr Cfg = nullptr, + BuildResult(Status S, const FunctionDecl *Func = nullptr, + std::unique_ptr Cfg = nullptr, std::unique_ptr AST = nullptr) - : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)) {} + : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)), Func(Func) {} Status getStatus() const { return S; } CFG *getCFG() const { return Cfg.get(); } ASTUnit *getAST() const { return AST.get(); } + const FunctionDecl *getFunc() const { return Func; } private: Status S; std::unique_ptr Cfg; std::unique_ptr AST; + const FunctionDecl *Func; }; class CFGCallback : public ast_matchers::MatchFinder::MatchCallback { @@ -54,7 +57,8 @@ Options.AddImplicitDtors = true; if (std::unique_ptr Cfg = CFG::buildCFG(nullptr, Body, Result.Context, Options)) - TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg), std::move(AST)}; + TheBuildResult = {BuildResult::BuiltCFG, Func, std::move(Cfg), + std::move(AST)}; } }; diff --git a/clang/unittests/Analysis/CFGTest.cpp b/clang/unittests/Analysis/CFGTest.cpp --- a/clang/unittests/Analysis/CFGTest.cpp +++ b/clang/unittests/Analysis/CFGTest.cpp @@ -7,10 +7,14 @@ //===----------------------------------------------------------------------===// #include "CFGBuildResult.h" +#include "clang/AST/Decl.h" #include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowWorklist.h" #include "clang/Tooling/Tooling.h" #include "gtest/gtest.h" +#include #include #include @@ -73,14 +77,14 @@ EXPECT_EQ(IsLinear, B.getCFG()->isLinear()); }; - expectLinear(true, "void foo() {}"); - expectLinear(true, "void foo() { if (true) return; }"); - expectLinear(true, "void foo() { if constexpr (false); }"); + expectLinear(true, "void foo() {}"); + expectLinear(true, "void foo() { if (true) return; }"); + expectLinear(true, "void foo() { if constexpr (false); }"); expectLinear(false, "void foo(bool coin) { if (coin) return; }"); expectLinear(false, "void foo() { for(;;); }"); expectLinear(false, "void foo() { do {} while (true); }"); - expectLinear(true, "void foo() { do {} while (false); }"); - expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem. + expectLinear(true, "void foo() { do {} while (false); }"); + expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem. } TEST(CFG, ElementRefIterator) { @@ -216,6 +220,54 @@ EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1); } +TEST(CFG, Worklists) { + const char *Code = "int f(bool cond) {\n" + " int a = 5;\n" + " if (cond)\n" + " a += 1;\n" + " return a;\n" + "}\n"; + BuildResult B = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus()); + const FunctionDecl *Func = B.getFunc(); + AnalysisDeclContext AC(nullptr, Func); + auto *CFG = AC.getCFG(); + + std::vector ReferenceOrder; + for (const auto *B : *AC.getAnalysis()) + ReferenceOrder.push_back(B); + + { + ForwardDataflowWorklist ForwardWorklist(*CFG, AC); + for (const auto *B : *CFG) + ForwardWorklist.enqueueBlock(B); + + std::vector ForwardNodes; + while (const CFGBlock *B = ForwardWorklist.dequeue()) + ForwardNodes.push_back(B); + + EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size()); + EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(), + ForwardNodes.begin())); + } + + std::reverse(ReferenceOrder.begin(), ReferenceOrder.end()); + + { + BackwardDataflowWorklist BackwardWorklist(*CFG, AC); + for (const auto *B : *CFG) + BackwardWorklist.enqueueBlock(B); + + std::vector BackwardNodes; + while (const CFGBlock *B = BackwardWorklist.dequeue()) + BackwardNodes.push_back(B); + + EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size()); + EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(), + BackwardNodes.begin())); + } +} + } // namespace } // namespace analysis } // namespace clang