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