clang 17.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
19namespace clang {
20/// A worklist implementation where the enqueued blocks will be dequeued based
21/// on the order defined by 'Comp'.
22template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {
23 llvm::BitVector EnqueuedBlocks;
25 llvm::PriorityQueue<const CFGBlock *,
27 WorkList;
28
29public:
31 : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32
33 const PostOrderCFGView *getCFGView() const { return POV; }
34
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,
66 ReversePostOrderCompare{POV->getComparator()}) {}
67
69 : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
70
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
88 for (auto B : Block->preds())
89 enqueueBlock(B);
90 }
91};
92
93} // namespace clang
94
95#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
AnalysisDeclContext contains the context data for the function, method or block under analysis.
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
unsigned getBlockID() const
Definition: CFG.h:1074
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1225
A worklist implementation where the enqueued blocks will be dequeued based on the order defined by 'C...
void enqueueBlock(const CFGBlock *Block)
DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
const PostOrderCFGView * getCFGView() const
const CFGBlock * dequeue()
@ C
Languages that the frontend can parse and compile.
A worklist implementation for backward dataflow analysis.
BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
void enqueuePredecessors(const CFGBlock *Block)
A worklist implementation for forward dataflow analysis.
void enqueueSuccessors(const CFGBlock *Block)
ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
PostOrderCFGView::BlockOrderCompare Cmp
bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const