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 <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     std::pair<llvm::NoneType, 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)
  56         return std::make_pair(None, false); // if an edge is trivially false.
  57       if (VisitedBlockIDs.test(Block->getBlockID()))
  58         return std::make_pair(None, false);
  59       VisitedBlockIDs.set(Block->getBlockID());
  60       return std::make_pair(None, 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   typedef std::vector<const CFGBlock *>::const_reverse_iterator const_iterator;
  81
  82   PostOrderCFGView(const CFG *cfg);
  83
  84   iterator begin() { return Blocks.rbegin(); }
  85   iterator end()   { return Blocks.rend(); }
  86
  87   const_iterator begin() const { return Blocks.rbegin(); }
  88   const_iterator end() const { return Blocks.rend(); }
  89
  90   bool empty() const { return begin() == end(); }
  91
  92   struct BlockOrderCompare;
  93   friend struct BlockOrderCompare;
  94
  95   struct BlockOrderCompare {
  96     const PostOrderCFGView &POV;
  97   public:
  98     BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
  99     bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
 100   };
 101
 102   BlockOrderCompare getComparator() const {
 103     return BlockOrderCompare(*this);
 104   }
 105
 106   // Used by AnalyisContext to construct this object.
 107   static const void *getTag();
 108
 109   static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
 110 };
 111
 112 } // end clang namespace
 113
 114 #endif
 115