PostOrderCFGView.h revision 439ed1656664b29841f70b6c0b91460534ff4d93 
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_POSTORDER_CFGVIEW
15#define LLVM_CLANG_POSTORDER_CFGVIEW
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
27namespace clang {
28
29class PostOrderCFGView : public ManagedAnalysis {
30public:
31  /// \brief Implements a set of CFGBlocks using a BitVector.
32  ///
33  /// This class contains a minimal interface, primarily dictated by the SetType
34  /// template parameter of the llvm::po_iterator template, as used with external
35  /// storage. We also use this set to keep track of which CFGBlocks we visit
36  /// during the analysis.
37  class CFGBlockSet {
38    llvm::BitVector VisitedBlockIDs;
39  public:
40    // po_iterator requires this iterator, but the only interface needed is the
41    // value_type typedef.
42    struct iterator { typedef const CFGBlock *value_type; };
43
44    CFGBlockSet() {}
45    CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
46
47    /// \brief Set the bit associated with a particular CFGBlock.
48    /// This is the important method for the SetType template parameter.
49    bool insert(const CFGBlock *Block) {
50      // Note that insert() is called by po_iterator, which doesn't check to make
51      // sure that Block is non-null.  Moreover, the CFGBlock iterator will
52      // occasionally hand out null pointers for pruned edges, so we catch those
53      // here.
54      if (Block == 0)
55        return false;  // if an edge is trivially false.
56      if (VisitedBlockIDs.test(Block->getBlockID()))
57        return false;
58      VisitedBlockIDs.set(Block->getBlockID());
59      return true;
60    }
61
62    /// \brief Check if the bit for a CFGBlock has been already set.
63    /// This method is for tracking visited blocks in the main threadsafety loop.
64    /// Block must not be null.
65    bool alreadySet(const CFGBlock *Block) {
66      return VisitedBlockIDs.test(Block->getBlockID());
67    }
68  };
69
70private:
71  typedef llvm::po_iterator<const CFG*, CFGBlockSet, true>  po_iterator;
72  std::vector<const CFGBlock*> Blocks;
73
74  typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy;
75  BlockOrderTy BlockOrder;
76
77public:
78  typedef std::vector<const CFGBlock*>::reverse_iterator iterator;
79
80  PostOrderCFGView(const CFG *cfg);
81
82  iterator begin() { return Blocks.rbegin(); }
83  iterator end()   { return Blocks.rend(); }
84
85  bool empty() { return begin() == end(); }
86
87  struct BlockOrderCompare;
88  friend struct BlockOrderCompare;
89
90  struct BlockOrderCompare {
91    const PostOrderCFGView &POV;
92  public:
93    BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
94    bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
95  };
96
97  BlockOrderCompare getComparator() const {
98    return BlockOrderCompare(*this);
99  }
100
101  // Used by AnalyisContext to construct this object.
102  static const void *getTag();
103
104  static PostOrderCFGView *create(AnalysisContext &analysisContext);
105};
106
107} // end clang namespace
108
109#endif
110
111