clang  12.0.0git
DataflowWorklist.h
Go to the documentation of this file.
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 
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 *,
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 
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.
63  : DataflowWorklistBase<ReversePostOrderCompare, 20> {
66  Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
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.
80  : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
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
A worklist implementation for backward dataflow analysis.
unsigned getBlockID() const
Definition: CFG.h:1074
ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
AnalysisDeclContext contains the context data for the function, method or block under analysis...
succ_range succs()
Definition: CFG.h:965
void enqueueBlock(const CFGBlock *Block)
A worklist implementation for forward dataflow analysis.
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1225
BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
A worklist implementation where the enqueued blocks will be dequeued based on the order defined by &#39;C...
const CFGBlock * dequeue()
void enqueueSuccessors(const CFGBlock *Block)
Dataflow Directional Tag Classes.
bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const
pred_range preds()
Definition: CFG.h:947
DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
void enqueuePredecessors(const CFGBlock *Block)
PostOrderCFGView::BlockOrderCompare Cmp
const PostOrderCFGView * getCFGView() const