clang  8.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 
18 #include "clang/Analysis/CFG.h"
19 #include "clang/Basic/LLVM.h"
20 #include "llvm/ADT/BitVector.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/PostOrderIterator.h"
24 #include <utility>
25 #include <vector>
26 
27 namespace clang {
28 
30  virtual void anchor();
31 
32 public:
33  /// Implements a set of CFGBlocks using a BitVector.
34  ///
35  /// This class contains a minimal interface, primarily dictated by the SetType
36  /// template parameter of the llvm::po_iterator template, as used with
37  /// external storage. We also use this set to keep track of which CFGBlocks we
38  /// visit during the analysis.
39  class CFGBlockSet {
40  llvm::BitVector VisitedBlockIDs;
41 
42  public:
43  // po_iterator requires this iterator, but the only interface needed is the
44  // value_type type.
45  struct iterator { using value_type = const CFGBlock *; };
46 
47  CFGBlockSet() = default;
48  CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
49 
50  /// Set the bit associated with a particular CFGBlock.
51  /// This is the important method for the SetType template parameter.
52  std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) {
53  // Note that insert() is called by po_iterator, which doesn't check to
54  // make sure that Block is non-null. Moreover, the CFGBlock iterator will
55  // occasionally hand out null pointers for pruned edges, so we catch those
56  // here.
57  if (!Block)
58  return std::make_pair(None, false); // if an edge is trivially false.
59  if (VisitedBlockIDs.test(Block->getBlockID()))
60  return std::make_pair(None, false);
61  VisitedBlockIDs.set(Block->getBlockID());
62  return std::make_pair(None, true);
63  }
64 
65  /// Check if the bit for a CFGBlock has been already set.
66  /// This method is for tracking visited blocks in the main threadsafety
67  /// loop. Block must not be null.
68  bool alreadySet(const CFGBlock *Block) {
69  return VisitedBlockIDs.test(Block->getBlockID());
70  }
71  };
72 
73 private:
74  using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>;
75  std::vector<const CFGBlock *> Blocks;
76 
77  using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
78  BlockOrderTy BlockOrder;
79 
80 public:
81  friend struct BlockOrderCompare;
82 
83  using iterator = std::vector<const CFGBlock *>::reverse_iterator;
84  using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
85 
86  PostOrderCFGView(const CFG *cfg);
87 
88  iterator begin() { return Blocks.rbegin(); }
89  iterator end() { return Blocks.rend(); }
90 
91  const_iterator begin() const { return Blocks.rbegin(); }
92  const_iterator end() const { return Blocks.rend(); }
93 
94  bool empty() const { return begin() == end(); }
95 
98 
99  public:
100  BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
101 
102  bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
103  };
104 
106  return BlockOrderCompare(*this);
107  }
108 
109  // Used by AnalyisContext to construct this object.
110  static const void *getTag();
111 
112  static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
113 };
114 
115 } // namespace clang
116 
117 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
The base class of a hierarchy of objects representing analyses tied to AnalysisDeclContext.
friend struct BlockOrderCompare
unsigned getBlockID() const
Definition: CFG.h:856
std::vector< const CFGBlock * >::const_reverse_iterator const_iterator
AnalysisDeclContext contains the context data for the function or method under analysis.
static PostOrderCFGView * create(AnalysisDeclContext &analysisContext)
bool alreadySet(const CFGBlock *Block)
Check if the bit for a CFGBlock has been already set.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
Implements a set of CFGBlocks using a BitVector.
const_iterator end() const
Represents a single basic block in a source-level CFG.
Definition: CFG.h:552
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1003
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
std::vector< const CFGBlock * >::reverse_iterator iterator
Dataflow Directional Tag Classes.
BlockOrderCompare(const PostOrderCFGView &pov)
static const void * getTag()
PostOrderCFGView(const CFG *cfg)