1234287Sdim//===- PostOrderCFGView.h - Post order view of CFG blocks ---------*- C++ --*-// 2234287Sdim// 3234287Sdim// The LLVM Compiler Infrastructure 4234287Sdim// 5234287Sdim// This file is distributed under the University of Illinois Open Source 6234287Sdim// License. See LICENSE.TXT for details. 7234287Sdim// 8234287Sdim//===----------------------------------------------------------------------===// 9234287Sdim// 10234287Sdim// This file implements post order view of the blocks in a CFG. 11234287Sdim// 12234287Sdim//===----------------------------------------------------------------------===// 13234287Sdim 14234287Sdim#ifndef LLVM_CLANG_POSTORDER_CFGVIEW 15234287Sdim#define LLVM_CLANG_POSTORDER_CFGVIEW 16234287Sdim 17234287Sdim#include <vector> 18234287Sdim//#include <algorithm> 19234287Sdim 20234287Sdim#include "llvm/ADT/PostOrderIterator.h" 21234287Sdim#include "llvm/ADT/DenseMap.h" 22234287Sdim#include "llvm/ADT/BitVector.h" 23234287Sdim 24234287Sdim#include "clang/Analysis/AnalysisContext.h" 25234287Sdim#include "clang/Analysis/CFG.h" 26234287Sdim 27234287Sdimnamespace clang { 28234287Sdim 29234287Sdimclass PostOrderCFGView : public ManagedAnalysis { 30234287Sdim virtual void anchor(); 31234287Sdimpublic: 32234287Sdim /// \brief Implements a set of CFGBlocks using a BitVector. 33234287Sdim /// 34234287Sdim /// This class contains a minimal interface, primarily dictated by the SetType 35234287Sdim /// template parameter of the llvm::po_iterator template, as used with 36234287Sdim /// external storage. We also use this set to keep track of which CFGBlocks we 37234287Sdim /// visit during the analysis. 38234287Sdim class CFGBlockSet { 39234287Sdim llvm::BitVector VisitedBlockIDs; 40234287Sdim public: 41234287Sdim // po_iterator requires this iterator, but the only interface needed is the 42234287Sdim // value_type typedef. 43234287Sdim struct iterator { typedef const CFGBlock *value_type; }; 44234287Sdim 45234287Sdim CFGBlockSet() {} 46234287Sdim CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} 47234287Sdim 48234287Sdim /// \brief Set the bit associated with a particular CFGBlock. 49234287Sdim /// This is the important method for the SetType template parameter. 50234287Sdim bool insert(const CFGBlock *Block) { 51234287Sdim // Note that insert() is called by po_iterator, which doesn't check to 52234287Sdim // make sure that Block is non-null. Moreover, the CFGBlock iterator will 53234287Sdim // occasionally hand out null pointers for pruned edges, so we catch those 54234287Sdim // here. 55234287Sdim if (Block == 0) 56234287Sdim return false; // if an edge is trivially false. 57234287Sdim if (VisitedBlockIDs.test(Block->getBlockID())) 58234287Sdim return false; 59234287Sdim VisitedBlockIDs.set(Block->getBlockID()); 60234287Sdim return true; 61234287Sdim } 62234287Sdim 63234287Sdim /// \brief Check if the bit for a CFGBlock has been already set. 64234287Sdim /// This method is for tracking visited blocks in the main threadsafety 65234287Sdim /// loop. Block must not be null. 66234287Sdim bool alreadySet(const CFGBlock *Block) { 67234287Sdim return VisitedBlockIDs.test(Block->getBlockID()); 68234287Sdim } 69234287Sdim }; 70234287Sdim 71234287Sdimprivate: 72234287Sdim typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; 73234287Sdim std::vector<const CFGBlock*> Blocks; 74234287Sdim 75234287Sdim typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy; 76234287Sdim BlockOrderTy BlockOrder; 77234287Sdim 78234287Sdimpublic: 79234287Sdim typedef std::vector<const CFGBlock*>::reverse_iterator iterator; 80234287Sdim 81234287Sdim PostOrderCFGView(const CFG *cfg); 82234287Sdim 83234287Sdim iterator begin() { return Blocks.rbegin(); } 84234287Sdim iterator end() { return Blocks.rend(); } 85234287Sdim 86234287Sdim bool empty() { return begin() == end(); } 87234287Sdim 88234287Sdim struct BlockOrderCompare; 89234287Sdim friend struct BlockOrderCompare; 90234287Sdim 91234287Sdim struct BlockOrderCompare { 92234287Sdim const PostOrderCFGView &POV; 93234287Sdim public: 94234287Sdim BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {} 95234287Sdim bool operator()(const CFGBlock *b1, const CFGBlock *b2) const; 96234287Sdim }; 97234287Sdim 98234287Sdim BlockOrderCompare getComparator() const { 99234287Sdim return BlockOrderCompare(*this); 100234287Sdim } 101234287Sdim 102234287Sdim // Used by AnalyisContext to construct this object. 103234287Sdim static const void *getTag(); 104234287Sdim 105234287Sdim static PostOrderCFGView *create(AnalysisDeclContext &analysisContext); 106234287Sdim}; 107234287Sdim 108234287Sdim} // end clang namespace 109234287Sdim 110234287Sdim#endif 111234287Sdim 112