clang  6.0.0svn
PostOrderCFGView.h
Go to the documentation of this file.
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 
25 #include "clang/Analysis/CFG.h"
26 
27 namespace clang {
28 
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 
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 
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 
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 
93  friend struct BlockOrderCompare;
94 
97  public:
98  BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
99  bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
100  };
101 
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 
The base class of a hierarchy of objects representing analyses tied to AnalysisDeclContext.
friend struct BlockOrderCompare
unsigned getBlockID() const
Definition: CFG.h:729
AnalysisDeclContext contains the context data for the function or method under analysis.
static PostOrderCFGView * create(AnalysisDeclContext &analysisContext)
std::vector< const CFGBlock * >::const_reverse_iterator const_iterator
bool alreadySet(const CFGBlock *Block)
Check if the bit for a CFGBlock has been already set.
Implements a set of CFGBlocks using a BitVector.
const_iterator end() const
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:834
const_iterator begin() const
#define false
Definition: stdbool.h:33
std::pair< llvm::NoneType, bool > insert(const CFGBlock *Block)
Set the bit associated with a particular CFGBlock.
BlockOrderCompare getComparator() const
Dataflow Directional Tag Classes.
BlockOrderCompare(const PostOrderCFGView &pov)
std::vector< const CFGBlock * >::reverse_iterator iterator
static const void * getTag()
PostOrderCFGView(const CFG *cfg)