Home | History | Annotate | Download | only in Analyses 
      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/AnalysisDeclContext.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 
    116