Analysis/FlowSensitive/DataflowWorklist.h

0001 //===- DataflowWorklist.h ---------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // A simple and reusable worklist for flow-sensitive analyses.
0010 //
0011 //===----------------------------------------------------------------------===//
0012 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
0013 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
0014
0015 #include "clang/Analysis/Analyses/IntervalPartition.h"
0016 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
0017 #include "clang/Analysis/CFG.h"
0018 #include "llvm/ADT/PriorityQueue.h"
0019
0020 namespace clang {
0021 /// A worklist implementation where the enqueued blocks will be dequeued based
0022 /// on the order defined by 'Comp'.
0023 template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {
0024   llvm::BitVector EnqueuedBlocks;
0025   llvm::PriorityQueue<const CFGBlock *,
0026                       SmallVector<const CFGBlock *, QueueSize>, Comp>
0027       WorkList;
0028
0029 public:
0030   DataflowWorklistBase(const CFG &Cfg, Comp C)
0031       : EnqueuedBlocks(Cfg.getNumBlockIDs()), WorkList(C) {}
0032
0033   void enqueueBlock(const CFGBlock *Block) {
0034     if (Block && !EnqueuedBlocks[Block->getBlockID()]) {
0035       EnqueuedBlocks[Block->getBlockID()] = true;
0036       WorkList.push(Block);
0037     }
0038   }
0039
0040   const CFGBlock *dequeue() {
0041     if (WorkList.empty())
0042       return nullptr;
0043     const CFGBlock *B = WorkList.top();
0044     WorkList.pop();
0045     EnqueuedBlocks[B->getBlockID()] = false;
0046     return B;
0047   }
0048 };
0049
0050 struct ReversePostOrderCompare {
0051   PostOrderCFGView::BlockOrderCompare Cmp;
0052   bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
0053     return Cmp(rhs, lhs);
0054   }
0055 };
0056
0057 /// A worklist implementation for forward dataflow analysis. The enqueued
0058 /// blocks will be dequeued in reverse post order. The worklist cannot contain
0059 /// the same block multiple times at once.
0060 struct ForwardDataflowWorklist
0061     : DataflowWorklistBase<ReversePostOrderCompare, 20> {
0062   ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
0063       : DataflowWorklistBase(Cfg,
0064                              ReversePostOrderCompare{POV->getComparator()}) {}
0065
0066   ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
0067       : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
0068
0069   void enqueueSuccessors(const CFGBlock *Block) {
0070     for (auto B : Block->succs())
0071       enqueueBlock(B);
0072   }
0073 };
0074
0075 /// A worklist implementation for forward dataflow analysis based on a weak
0076 /// topological ordering of the nodes. The worklist cannot contain the same
0077 /// block multiple times at once.
0078 struct WTODataflowWorklist : DataflowWorklistBase<WTOCompare, 20> {
0079   WTODataflowWorklist(const CFG &Cfg, const WTOCompare &Cmp)
0080       : DataflowWorklistBase(Cfg, Cmp) {}
0081
0082   void enqueueSuccessors(const CFGBlock *Block) {
0083     for (auto B : Block->succs())
0084       enqueueBlock(B);
0085   }
0086 };
0087
0088 /// A worklist implementation for backward dataflow analysis. The enqueued
0089 /// block will be dequeued in post order. The worklist cannot contain the same
0090 /// block multiple times at once.
0091 struct BackwardDataflowWorklist
0092     : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
0093   BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
0094       : DataflowWorklistBase(
0095             Cfg, Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
0096
0097   void enqueuePredecessors(const CFGBlock *Block) {
0098     for (auto B : Block->preds())
0099       enqueueBlock(B);
0100   }
0101 };
0102
0103 } // namespace clang
0104
0105 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H