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/PostOrderCFGView.h"
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;
24  PostOrderCFGView *POV;
25  llvm::PriorityQueue<const CFGBlock *,
26                      SmallVector<const CFGBlock *, QueueSize>, Comp>
27      WorkList;
28
29public:
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
52struct ReversePostOrderCompare {
53  PostOrderCFGView::BlockOrderCompare Cmp;
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.
62struct ForwardDataflowWorklist
63    : DataflowWorklistBase<ReversePostOrderCompare, 20> {
64  ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
65      : DataflowWorklistBase(Cfg, POV,
66                             ReversePostOrderCompare{POV->getComparator()}) {}
67
68  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
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.
80struct BackwardDataflowWorklist
81    : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
82  BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
83      : DataflowWorklistBase(
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
96