1 //===- DataflowWorklist.h ---------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // A simple and reusable worklist for flow-sensitive analyses. 10 // 11 //===----------------------------------------------------------------------===// 12 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H 13 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H 14 15 #include "clang/Analysis/Analyses/IntervalPartition.h" 16 #include "clang/Analysis/Analyses/PostOrderCFGView.h" 17 #include "clang/Analysis/CFG.h" 18 #include "llvm/ADT/PriorityQueue.h" 19 20 namespace clang { 21 /// A worklist implementation where the enqueued blocks will be dequeued based 22 /// on the order defined by 'Comp'. 23 template <typename Comp, unsigned QueueSize> class DataflowWorklistBase { 24 llvm::BitVector EnqueuedBlocks; 25 llvm::PriorityQueue<const CFGBlock *, 26 SmallVector<const CFGBlock *, QueueSize>, Comp> 27 WorkList; 28 29 public: DataflowWorklistBase(const CFG & Cfg,Comp C)30 DataflowWorklistBase(const CFG &Cfg, Comp C) 31 : EnqueuedBlocks(Cfg.getNumBlockIDs()), WorkList(C) {} 32 enqueueBlock(const CFGBlock * Block)33 void enqueueBlock(const CFGBlock *Block) { 34 if (Block && !EnqueuedBlocks[Block->getBlockID()]) { 35 EnqueuedBlocks[Block->getBlockID()] = true; 36 WorkList.push(Block); 37 } 38 } 39 dequeue()40 const CFGBlock *dequeue() { 41 if (WorkList.empty()) 42 return nullptr; 43 const CFGBlock *B = WorkList.top(); 44 WorkList.pop(); 45 EnqueuedBlocks[B->getBlockID()] = false; 46 return B; 47 } 48 }; 49 50 struct ReversePostOrderCompare { 51 PostOrderCFGView::BlockOrderCompare Cmp; operatorReversePostOrderCompare52 bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const { 53 return Cmp(rhs, lhs); 54 } 55 }; 56 57 /// A worklist implementation for forward dataflow analysis. The enqueued 58 /// blocks will be dequeued in reverse post order. The worklist cannot contain 59 /// the same block multiple times at once. 60 struct ForwardDataflowWorklist 61 : DataflowWorklistBase<ReversePostOrderCompare, 20> { ForwardDataflowWorklistForwardDataflowWorklist62 ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV) 63 : DataflowWorklistBase(Cfg, 64 ReversePostOrderCompare{POV->getComparator()}) {} 65 ForwardDataflowWorklistForwardDataflowWorklist66 ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx) 67 : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {} 68 enqueueSuccessorsForwardDataflowWorklist69 void enqueueSuccessors(const CFGBlock *Block) { 70 for (auto B : Block->succs()) 71 enqueueBlock(B); 72 } 73 }; 74 75 /// A worklist implementation for forward dataflow analysis based on a weak 76 /// topological ordering of the nodes. The worklist cannot contain the same 77 /// block multiple times at once. 78 struct WTODataflowWorklist : DataflowWorklistBase<WTOCompare, 20> { WTODataflowWorklistWTODataflowWorklist79 WTODataflowWorklist(const CFG &Cfg, const WTOCompare &Cmp) 80 : DataflowWorklistBase(Cfg, Cmp) {} 81 enqueueSuccessorsWTODataflowWorklist82 void enqueueSuccessors(const CFGBlock *Block) { 83 for (auto B : Block->succs()) 84 enqueueBlock(B); 85 } 86 }; 87 88 /// A worklist implementation for backward dataflow analysis. The enqueued 89 /// block will be dequeued in post order. The worklist cannot contain the same 90 /// block multiple times at once. 91 struct BackwardDataflowWorklist 92 : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> { BackwardDataflowWorklistBackwardDataflowWorklist93 BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx) 94 : DataflowWorklistBase( 95 Cfg, Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {} 96 enqueuePredecessorsBackwardDataflowWorklist97 void enqueuePredecessors(const CFGBlock *Block) { 98 for (auto B : Block->preds()) 99 enqueueBlock(B); 100 } 101 }; 102 103 } // namespace clang 104 105 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H 106