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/AnalysisDeclContext.h"
25#include "clang/Analysis/CFG.h"
26
27namespace clang {
28
29class PostOrderCFGView : public ManagedAnalysis {
30  virtual void anchor();
31public:
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
45    CFGBlockSet() {}
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.
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.
66    bool alreadySet(const CFGBlock *Block) {
67      return VisitedBlockIDs.test(Block->getBlockID());
68    }
69  };
70
71private:
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
78public:
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
84  iterator begin() { return Blocks.rbegin(); }
85  iterator end()   { return Blocks.rend(); }
86
87  const_iterator begin() const { return Blocks.rbegin(); }
88  const_iterator end() const { return Blocks.rend(); }
89
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:
98    BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
99    bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
100  };
101
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