contrib/llvm/tools/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h

   1 //===- PostOrderCFGView.h - Post order view of CFG blocks -------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements post order view of the blocks in a CFG.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
  15 #define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
  16
  17 #include "clang/Analysis/AnalysisDeclContext.h"
  18 #include "clang/Analysis/CFG.h"
  19 #include "clang/Basic/LLVM.h"
  20 #include "llvm/ADT/BitVector.h"
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/None.h"
  23 #include "llvm/ADT/PostOrderIterator.h"
  24 #include <utility>
  25 #include <vector>
  26
  27 namespace clang {
  28
  29 class PostOrderCFGView : public ManagedAnalysis {
  30   virtual void anchor();
  31
  32 public:
  33   /// Implements a set of CFGBlocks using a BitVector.
  34   ///
  35   /// This class contains a minimal interface, primarily dictated by the SetType
  36   /// template parameter of the llvm::po_iterator template, as used with
  37   /// external storage. We also use this set to keep track of which CFGBlocks we
  38   /// visit during the analysis.
  39   class CFGBlockSet {
  40     llvm::BitVector VisitedBlockIDs;
  41
  42   public:
  43     // po_iterator requires this iterator, but the only interface needed is the
  44     // value_type type.
  45     struct iterator { using value_type = const CFGBlock *; };
  46
  47     CFGBlockSet() = default;
  48     CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
  49
  50     /// Set the bit associated with a particular CFGBlock.
  51     /// This is the important method for the SetType template parameter.
  52     std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) {
  53       // Note that insert() is called by po_iterator, which doesn't check to
  54       // make sure that Block is non-null.  Moreover, the CFGBlock iterator will
  55       // occasionally hand out null pointers for pruned edges, so we catch those
  56       // here.
  57       if (!Block)
  58         return std::make_pair(None, false); // if an edge is trivially false.
  59       if (VisitedBlockIDs.test(Block->getBlockID()))
  60         return std::make_pair(None, false);
  61       VisitedBlockIDs.set(Block->getBlockID());
  62       return std::make_pair(None, true);
  63     }
  64
  65     /// Check if the bit for a CFGBlock has been already set.
  66     /// This method is for tracking visited blocks in the main threadsafety
  67     /// loop. Block must not be null.
  68     bool alreadySet(const CFGBlock *Block) {
  69       return VisitedBlockIDs.test(Block->getBlockID());
  70     }
  71   };
  72
  73 private:
  74   using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>;
  75   std::vector<const CFGBlock *> Blocks;
  76
  77   using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
  78   BlockOrderTy BlockOrder;
  79
  80 public:
  81   friend struct BlockOrderCompare;
  82
  83   using iterator = std::vector<const CFGBlock *>::reverse_iterator;
  84   using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
  85
  86   PostOrderCFGView(const CFG *cfg);
  87
  88   iterator begin() { return Blocks.rbegin(); }
  89   iterator end() { return Blocks.rend(); }
  90
  91   const_iterator begin() const { return Blocks.rbegin(); }
  92   const_iterator end() const { return Blocks.rend(); }
  93
  94   bool empty() const { return begin() == end(); }
  95
  96   struct BlockOrderCompare {
  97     const PostOrderCFGView &POV;
  98
  99   public:
 100     BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
 101
 102     bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
 103   };
 104
 105   BlockOrderCompare getComparator() const {
 106     return BlockOrderCompare(*this);
 107   }
 108
 109   // Used by AnalyisContext to construct this object.
 110   static const void *getTag();
 111
 112   static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
 113 };
 114
 115 } // namespace clang
 116
 117 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H