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 
16 #include "clang/Analysis/AnalysisDeclContext.h"
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/PostOrderIterator.h"
22 #include <utility>
23 #include <vector>
24 
25 namespace clang {
26 
27 class PostOrderCFGView : public ManagedAnalysis {
28   virtual void anchor();
29 
30 public:
31   /// Implements a set of CFGBlocks using a BitVector.
32   ///
33   /// This class contains a minimal interface, primarily dictated by the SetType
34   /// template parameter of the llvm::po_iterator template, as used with
35   /// external storage. We also use this set to keep track of which CFGBlocks we
36   /// visit during the analysis.
37   class CFGBlockSet {
38     llvm::BitVector VisitedBlockIDs;
39 
40   public:
41     // po_iterator requires this iterator, but the only interface needed is the
42     // value_type type.
43     struct iterator { using value_type = const CFGBlock *; };
44 
45     CFGBlockSet() = default;
CFGBlockSet(const CFG * G)46     CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
47 
48     /// Set the bit associated with a particular CFGBlock.
49     /// This is the important method for the SetType template parameter.
insert(const CFGBlock * Block)50     std::pair<std::nullopt_t, 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(std::nullopt,
57                               false); // if an edge is trivially false.
58       if (VisitedBlockIDs.test(Block->getBlockID()))
59         return std::make_pair(std::nullopt, false);
60       VisitedBlockIDs.set(Block->getBlockID());
61       return std::make_pair(std::nullopt, 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.
alreadySet(const CFGBlock * Block)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 
begin()87   iterator begin() { return Blocks.rbegin(); }
end()88   iterator end() { return Blocks.rend(); }
89 
begin()90   const_iterator begin() const { return Blocks.rbegin(); }
end()91   const_iterator end() const { return Blocks.rend(); }
92 
empty()93   bool empty() const { return begin() == end(); }
94 
95   struct BlockOrderCompare {
96     const PostOrderCFGView &POV;
97 
98   public:
BlockOrderCompareBlockOrderCompare99     BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
100 
101     bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
102   };
103 
getComparator()104   BlockOrderCompare getComparator() const {
105     return BlockOrderCompare(*this);
106   }
107 
108   // Used by AnalyisContext to construct this object.
109   static const void *getTag();
110 
111   static std::unique_ptr<PostOrderCFGView>
112   create(AnalysisDeclContext &analysisContext);
113 };
114 
115 } // namespace clang
116 
117 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
118