1 //===- PostOrderCFGView.h - Post order view of CFG blocks ---------*- C++ --*-//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements post order view of the blocks in a CFG.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_POSTORDER_CFGVIEW
15 #define LLVM_CLANG_POSTORDER_CFGVIEW
18 //#include <algorithm>
20 #include "llvm/ADT/PostOrderIterator.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/BitVector.h"
24 #include "clang/Analysis/AnalysisContext.h"
25 #include "clang/Analysis/CFG.h"
29 class PostOrderCFGView : public ManagedAnalysis {
30 virtual void anchor();
32 /// \brief Implements a set of CFGBlocks using a BitVector.
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.
39 llvm::BitVector VisitedBlockIDs;
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; };
46 CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
48 /// \brief Set the bit associated with a particular CFGBlock.
49 /// This is the important method for the SetType template parameter.
50 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
56 return false; // if an edge is trivially false.
57 if (VisitedBlockIDs.test(Block->getBlockID()))
59 VisitedBlockIDs.set(Block->getBlockID());
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());
72 typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator;
73 std::vector<const CFGBlock*> Blocks;
75 typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy;
76 BlockOrderTy BlockOrder;
79 typedef std::vector<const CFGBlock*>::reverse_iterator iterator;
81 PostOrderCFGView(const CFG *cfg);
83 iterator begin() { return Blocks.rbegin(); }
84 iterator end() { return Blocks.rend(); }
86 bool empty() { return begin() == end(); }
88 struct BlockOrderCompare;
89 friend struct BlockOrderCompare;
91 struct BlockOrderCompare {
92 const PostOrderCFGView &POV;
94 BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
95 bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
98 BlockOrderCompare getComparator() const {
99 return BlockOrderCompare(*this);
102 // Used by AnalyisContext to construct this object.
103 static const void *getTag();
105 static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
108 } // end clang namespace