clang  16.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:
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> {
65  : DataflowWorklistBase(Cfg, POV,
67 
69  : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
70 
71  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.
81  : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
84  Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
85  Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
86 
87  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
clang::interp::Comp
bool Comp(InterpState &S, CodePtr OpPC)
1) Pops the value from the stack.
Definition: Interp.h:401
llvm::SmallVector
Definition: LLVM.h:38
clang::DataflowWorklistBase
A worklist implementation where the enqueued blocks will be dequeued based on the order defined by 'C...
Definition: DataflowWorklist.h:22
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1076
clang::ForwardDataflowWorklist::ForwardDataflowWorklist
ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
Definition: DataflowWorklist.h:68
clang::AnalysisDeclContext
AnalysisDeclContext contains the context data for the function, method or block under analysis.
Definition: AnalysisDeclContext.h:72
clang::DataflowWorklistBase::getCFGView
const PostOrderCFGView * getCFGView() const
Definition: DataflowWorklist.h:33
PostOrderCFGView.h
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1227
clang::PostOrderCFGView::BlockOrderCompare
Definition: PostOrderCFGView.h:95
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:578
clang::DataflowWorklistBase::DataflowWorklistBase
DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
Definition: DataflowWorklist.h:30
clang::ReversePostOrderCompare
Definition: DataflowWorklist.h:52
clang::BackwardDataflowWorklist::enqueuePredecessors
void enqueuePredecessors(const CFGBlock *Block)
Definition: DataflowWorklist.h:87
clang::PostOrderCFGView::getComparator
BlockOrderCompare getComparator() const
Definition: PostOrderCFGView.h:104
clang::PostOrderCFGView
Definition: PostOrderCFGView.h:28
clang::DataflowWorklistBase::enqueueBlock
void enqueueBlock(const CFGBlock *Block)
Definition: DataflowWorklist.h:35
clang::ForwardDataflowWorklist
A worklist implementation for forward dataflow analysis.
Definition: DataflowWorklist.h:62
clang::ReversePostOrderCompare::operator()
bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const
Definition: DataflowWorklist.h:54
clang::BackwardDataflowWorklist
A worklist implementation for backward dataflow analysis.
Definition: DataflowWorklist.h:80
clang::DataflowWorklistBase::dequeue
const CFGBlock * dequeue()
Definition: DataflowWorklist.h:42
clang::ForwardDataflowWorklist::ForwardDataflowWorklist
ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
Definition: DataflowWorklist.h:64
clang::ForwardDataflowWorklist::enqueueSuccessors
void enqueueSuccessors(const CFGBlock *Block)
Definition: DataflowWorklist.h:71
clang
Definition: CalledOnceCheck.h:17
CFG.h
clang::DeclaratorContext::Block
@ Block
clang::ReversePostOrderCompare::Cmp
PostOrderCFGView::BlockOrderCompare Cmp
Definition: DataflowWorklist.h:53
clang::BackwardDataflowWorklist::BackwardDataflowWorklist
BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
Definition: DataflowWorklist.h:82