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