• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
CFGBlockSet()45     CFGBlockSet() {}
CFGBlockSet(const CFG * G)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.
insert(const CFGBlock * Block)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.
alreadySet(const CFGBlock * Block)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 
begin()84   iterator begin() { return Blocks.rbegin(); }
end()85   iterator end()   { return Blocks.rend(); }
86 
begin()87   const_iterator begin() const { return Blocks.rbegin(); }
end()88   const_iterator end() const { return Blocks.rend(); }
89 
empty()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:
BlockOrderCompareBlockOrderCompare98     BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
99     bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
100   };
101 
getComparator()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