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