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