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/PostOrderCFGView.h"
16 #include "clang/Analysis/CFG.h"
17 #include "llvm/ADT/PriorityQueue.h"
18 
19 namespace clang {
20 /// A worklist implementation where the enqueued blocks will be dequeued based
21 /// on the order defined by 'Comp'.
22 template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {
23   llvm::BitVector EnqueuedBlocks;
24   PostOrderCFGView *POV;
25   llvm::PriorityQueue<const CFGBlock *,
26                       SmallVector<const CFGBlock *, QueueSize>, Comp>
27       WorkList;
28 
29 public:
DataflowWorklistBase(const CFG & Cfg,PostOrderCFGView * POV,Comp C)30   DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
31       : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32 
getCFGView()33   const PostOrderCFGView *getCFGView() const { return POV; }
34 
enqueueBlock(const CFGBlock * Block)35   void enqueueBlock(const CFGBlock *Block) {
36     if (Block && !EnqueuedBlocks[Block->getBlockID()]) {
37       EnqueuedBlocks[Block->getBlockID()] = true;
38       WorkList.push(Block);
39     }
40   }
41 
dequeue()42   const CFGBlock *dequeue() {
43     if (WorkList.empty())
44       return nullptr;
45     const CFGBlock *B = WorkList.top();
46     WorkList.pop();
47     EnqueuedBlocks[B->getBlockID()] = false;
48     return B;
49   }
50 };
51 
52 struct ReversePostOrderCompare {
53   PostOrderCFGView::BlockOrderCompare Cmp;
operatorReversePostOrderCompare54   bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
55     return Cmp(rhs, lhs);
56   }
57 };
58 
59 /// A worklist implementation for forward dataflow analysis. The enqueued
60 /// blocks will be dequeued in reverse post order. The worklist cannot contain
61 /// the same block multiple times at once.
62 struct ForwardDataflowWorklist
63     : DataflowWorklistBase<ReversePostOrderCompare, 20> {
ForwardDataflowWorklistForwardDataflowWorklist64   ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
65       : DataflowWorklistBase(Cfg, POV,
66                              ReversePostOrderCompare{POV->getComparator()}) {}
67 
ForwardDataflowWorklistForwardDataflowWorklist68   ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
69       : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
70 
enqueueSuccessorsForwardDataflowWorklist71   void enqueueSuccessors(const CFGBlock *Block) {
72     for (auto B : Block->succs())
73       enqueueBlock(B);
74   }
75 };
76 
77 /// A worklist implementation for backward dataflow analysis. The enqueued
78 /// block will be dequeued in post order. The worklist cannot contain the same
79 /// block multiple times at once.
80 struct BackwardDataflowWorklist
81     : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
BackwardDataflowWorklistBackwardDataflowWorklist82   BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
83       : DataflowWorklistBase(
84             Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
85             Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
86 
enqueuePredecessorsBackwardDataflowWorklist87   void enqueuePredecessors(const CFGBlock *Block) {
88     for (auto B : Block->preds())
89       enqueueBlock(B);
90   }
91 };
92 
93 } // namespace clang
94 
95 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
96