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
20namespace clang {
21/// A worklist implementation where the enqueued blocks will be dequeued based
22/// on the order defined by 'Comp'.
23template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {
24 llvm::BitVector EnqueuedBlocks;
25 llvm::PriorityQueue<const CFGBlock *,
26 SmallVector<const CFGBlock *, QueueSize>, Comp>
27 WorkList;
28
29public:
30 DataflowWorklistBase(const CFG &Cfg, Comp C)
31 : EnqueuedBlocks(Cfg.getNumBlockIDs()), WorkList(C) {}
32
33 void enqueueBlock(const CFGBlock *Block) {
34 if (Block && !EnqueuedBlocks[Block->getBlockID()]) {
35 EnqueuedBlocks[Block->getBlockID()] = true;
36 WorkList.push(Block);
37 }
38 }
39
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
50struct ReversePostOrderCompare {
51 PostOrderCFGView::BlockOrderCompare Cmp;
52 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.
60struct ForwardDataflowWorklist
61 : DataflowWorklistBase<ReversePostOrderCompare, 20> {
62 ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
63 : DataflowWorklistBase(Cfg,
64 ReversePostOrderCompare{.Cmp: POV->getComparator()}) {}
65
66 ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
67 : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
68
69 void enqueueSuccessors(const CFGBlock *Block) {
70 for (auto B : Block->succs())
71 enqueueBlock(Block: 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.
78struct WTODataflowWorklist : DataflowWorklistBase<WTOCompare, 20> {
79 WTODataflowWorklist(const CFG &Cfg, const WTOCompare &Cmp)
80 : DataflowWorklistBase(Cfg, Cmp) {}
81
82 void enqueueSuccessors(const CFGBlock *Block) {
83 for (auto B : Block->succs())
84 enqueueBlock(Block: 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.
91struct BackwardDataflowWorklist
92 : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
93 BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
94 : DataflowWorklistBase(
95 Cfg, Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
96
97 void enqueuePredecessors(const CFGBlock *Block) {
98 for (auto B : Block->preds())
99 enqueueBlock(Block: B);
100 }
101};
102
103} // namespace clang
104
105#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
106