Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.  
  19. namespace clang {
  20. /// A worklist implementation where the enqueued blocks will be dequeued based
  21. /// on the order defined by 'Comp'.
  22. template <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.  
  29. public:
  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.  
  52. struct 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.
  62. struct 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.
  80. struct 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.