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; |
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. |
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(x: std::nullopt, |
57 | y: false); // if an edge is trivially false. |
58 | if (VisitedBlockIDs.test(Idx: Block->getBlockID())) |
59 | return std::make_pair(x: std::nullopt, y: false); |
60 | VisitedBlockIDs.set(Block->getBlockID()); |
61 | return std::make_pair(x: std::nullopt, y: 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(Idx: Block->getBlockID()); |
69 | } |
70 | }; |
71 | |
72 | private: |
73 | // The CFG orders the blocks of loop bodies before those of loop successors |
74 | // (both numerically, and in the successor order of the loop condition |
75 | // block). So, RPO necessarily reverses that order, placing the loop successor |
76 | // *before* the loop body. For many analyses, particularly those that converge |
77 | // to a fixpoint, this results in potentially significant extra work because |
78 | // loop successors will necessarily need to be reconsidered once the algorithm |
79 | // has reached a fixpoint on the loop body. |
80 | // |
81 | // This definition of CFG graph traits reverses the order of children, so that |
82 | // loop bodies will come first in an RPO. |
83 | struct CFGLoopBodyFirstTraits { |
84 | using NodeRef = const ::clang::CFGBlock *; |
85 | using ChildIteratorType = ::clang::CFGBlock::const_succ_reverse_iterator; |
86 | |
87 | static ChildIteratorType child_begin(NodeRef N) { return N->succ_rbegin(); } |
88 | static ChildIteratorType child_end(NodeRef N) { return N->succ_rend(); } |
89 | |
90 | using nodes_iterator = ::clang::CFG::const_iterator; |
91 | |
92 | static NodeRef getEntryNode(const ::clang::CFG *F) { |
93 | return &F->getEntry(); |
94 | } |
95 | |
96 | static nodes_iterator nodes_begin(const ::clang::CFG *F) { |
97 | return F->nodes_begin(); |
98 | } |
99 | |
100 | static nodes_iterator nodes_end(const ::clang::CFG *F) { |
101 | return F->nodes_end(); |
102 | } |
103 | |
104 | static unsigned size(const ::clang::CFG *F) { return F->size(); } |
105 | }; |
106 | using po_iterator = |
107 | llvm::po_iterator<const CFG *, CFGBlockSet, true, CFGLoopBodyFirstTraits>; |
108 | std::vector<const CFGBlock *> Blocks; |
109 | |
110 | using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>; |
111 | BlockOrderTy BlockOrder; |
112 | |
113 | public: |
114 | friend struct BlockOrderCompare; |
115 | |
116 | using iterator = std::vector<const CFGBlock *>::reverse_iterator; |
117 | using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator; |
118 | |
119 | PostOrderCFGView(const CFG *cfg); |
120 | |
121 | iterator begin() { return Blocks.rbegin(); } |
122 | iterator end() { return Blocks.rend(); } |
123 | |
124 | const_iterator begin() const { return Blocks.rbegin(); } |
125 | const_iterator end() const { return Blocks.rend(); } |
126 | |
127 | bool empty() const { return begin() == end(); } |
128 | |
129 | struct BlockOrderCompare { |
130 | const PostOrderCFGView &POV; |
131 | |
132 | public: |
133 | BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {} |
134 | |
135 | bool operator()(const CFGBlock *b1, const CFGBlock *b2) const; |
136 | }; |
137 | |
138 | BlockOrderCompare getComparator() const { |
139 | return BlockOrderCompare(*this); |
140 | } |
141 | |
142 | // Used by AnalyisContext to construct this object. |
143 | static const void *getTag(); |
144 | |
145 | static std::unique_ptr<PostOrderCFGView> |
146 | create(AnalysisDeclContext &analysisContext); |
147 | }; |
148 | |
149 | } // namespace clang |
150 | |
151 | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |
152 | |