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:
30   DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
31       : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32 
33   const PostOrderCFGView *getCFGView() const { return POV; }
34 
35   void enqueueBlock(const CFGBlock *Block) {
36     if (Block && !EnqueuedBlocks[Block->getBlockID()]) {
37       EnqueuedBlocks[Block->getBlockID()] = true;
38       WorkList.push(Block);
39     }
40   }
41 
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;
54   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> {
64   ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
65       : DataflowWorklistBase(
66             Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
67             ReversePostOrderCompare{
68                 Ctx.getAnalysis<PostOrderCFGView>()->getComparator()}) {}
69 
70   void enqueueSuccessors(const CFGBlock *Block) {
71     for (auto B : Block->succs())
72       enqueueBlock(B);
73   }
74 };
75 
76 /// A worklist implementation for backward dataflow analysis. The enqueued
77 /// block will be dequeued in post order. The worklist cannot contain the same
78 /// block multiple times at once.
79 struct BackwardDataflowWorklist
80     : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
81   BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
82       : DataflowWorklistBase(
83             Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
84             Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
85 
86   void enqueuePredecessors(const CFGBlock *Block) {
87     for (auto B : Block->preds())
88       enqueueBlock(B);
89   }
90 };
91 
92 } // namespace clang
93 
94 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
95