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 "clang/Analysis/AnalysisDeclContext.h"
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 
29 class PostOrderCFGView : public ManagedAnalysis {
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;
CFGBlockSet(const CFG * G)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.
insert(const CFGBlock * Block)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.
alreadySet(const CFGBlock * Block)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 
begin()88   iterator begin() { return Blocks.rbegin(); }
end()89   iterator end() { return Blocks.rend(); }
90 
begin()91   const_iterator begin() const { return Blocks.rbegin(); }
end()92   const_iterator end() const { return Blocks.rend(); }
93 
empty()94   bool empty() const { return begin() == end(); }
95 
96   struct BlockOrderCompare {
97     const PostOrderCFGView &POV;
98 
99   public:
BlockOrderCompareBlockOrderCompare100     BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
101 
102     bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
103   };
104 
getComparator()105   BlockOrderCompare getComparator() const {
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
118