clang  10.0.0svn
PostOrderCFGView.h
Go to the documentation of this file.
1 //===- PostOrderCFGView.h - Post order view of CFG blocks -------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements post order view of the blocks in a CFG.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
14 #define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
15 
17 #include "clang/Analysis/CFG.h"
18 #include "clang/Basic/LLVM.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/None.h"
22 #include "llvm/ADT/PostOrderIterator.h"
23 #include <utility>
24 #include <vector>
25 
26 namespace clang {
27 
29  virtual void anchor();
30 
31 public:
32  /// 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 
41  public:
42  // po_iterator requires this iterator, but the only interface needed is the
43  // value_type type.
44  struct iterator { using value_type = const CFGBlock *; };
45 
46  CFGBlockSet() = default;
47  CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
48 
49  /// Set the bit associated with a particular CFGBlock.
50  /// This is the important method for the SetType template parameter.
51  std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) {
52  // Note that insert() is called by po_iterator, which doesn't check to
53  // make sure that Block is non-null. Moreover, the CFGBlock iterator will
54  // occasionally hand out null pointers for pruned edges, so we catch those
55  // here.
56  if (!Block)
57  return std::make_pair(None, false); // if an edge is trivially false.
58  if (VisitedBlockIDs.test(Block->getBlockID()))
59  return std::make_pair(None, false);
60  VisitedBlockIDs.set(Block->getBlockID());
61  return std::make_pair(None, true);
62  }
63 
64  /// Check if the bit for a CFGBlock has been already set.
65  /// This method is for tracking visited blocks in the main threadsafety
66  /// loop. Block must not be null.
67  bool alreadySet(const CFGBlock *Block) {
68  return VisitedBlockIDs.test(Block->getBlockID());
69  }
70  };
71 
72 private:
73  using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>;
74  std::vector<const CFGBlock *> Blocks;
75 
76  using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
77  BlockOrderTy BlockOrder;
78 
79 public:
80  friend struct BlockOrderCompare;
81 
82  using iterator = std::vector<const CFGBlock *>::reverse_iterator;
83  using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
84 
85  PostOrderCFGView(const CFG *cfg);
86 
87  iterator begin() { return Blocks.rbegin(); }
88  iterator end() { return Blocks.rend(); }
89 
90  const_iterator begin() const { return Blocks.rbegin(); }
91  const_iterator end() const { return Blocks.rend(); }
92 
93  bool empty() const { return begin() == end(); }
94 
97 
98  public:
99  BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
100 
101  bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
102  };
103 
105  return BlockOrderCompare(*this);
106  }
107 
108  // Used by AnalyisContext to construct this object.
109  static const void *getTag();
110 
111  static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
112 };
113 
114 } // namespace clang
115 
116 #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:1075
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:576
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1226
const_iterator begin() const
#define false
Definition: stdbool.h:17
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)