Debian Codegraph @

third_party/spirv-tools/source/opt/struct_cfg_analysis.h

raw
1 // Copyright (c) 2018 Google LLC.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
16 #define SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
17
18 #include <unordered_map>
19 #include <unordered_set>
20
21 #include "source/opt/function.h"
22 #include "source/util/bit_vector.h"
23
24 namespace spvtools {
25 namespace opt {
26
27 class IRContext;
28
29 // An analysis that, for each basic block, finds the constructs in which it is
30 // contained, so we can easily get headers and merge nodes.
31 class StructuredCFGAnalysis {
32 public:
33 explicit StructuredCFGAnalysis(IRContext* ctx);
34
35 // Returns the id of the header of the innermost merge construct
36 // that contains |bb_id|. Returns |0| if |bb_id| is not contained in any
37 // merge construct.
38 uint32_t ContainingConstruct(uint32_t bb_id) {
39 auto it = bb_to_construct_.find(bb_id);
40 if (it == bb_to_construct_.end()) {
41 return 0;
42 }
43 return it->second.containing_construct;
44 }
45
46 // Returns the id of the header of the innermost merge construct
47 // that contains |inst|. Returns |0| if |inst| is not contained in any
48 // merge construct.
49 uint32_t ContainingConstruct(Instruction* inst);
50
51 // Returns the id of the merge block of the innermost merge construct
52 // that contains |bb_id|. Returns |0| if |bb_id| is not contained in any
53 // merge construct.
54 uint32_t MergeBlock(uint32_t bb_id);
55
56 // Returns the nesting depth of the given block, i.e. the number of merge
57 // constructs containing it. Headers and merge blocks are not considered part
58 // of the corresponding merge constructs.
59 uint32_t NestingDepth(uint32_t block_id);
60
61 // Returns the id of the header of the innermost loop construct
62 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
63 // construct.
64 uint32_t ContainingLoop(uint32_t bb_id) {
65 auto it = bb_to_construct_.find(bb_id);
66 if (it == bb_to_construct_.end()) {
67 return 0;
68 }
69 return it->second.containing_loop;
70 }
71
72 // Returns the id of the merge block of the innermost loop construct
73 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
74 // construct.
75 uint32_t LoopMergeBlock(uint32_t bb_id);
76
77 // Returns the id of the continue block of the innermost loop construct
78 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
79 // construct.
80 uint32_t LoopContinueBlock(uint32_t bb_id);
81
82 // Returns the loop nesting depth of |bb_id| within its function, i.e. the
83 // number of loop constructs in which |bb_id| is contained. As per other
84 // functions in StructuredCFGAnalysis, a loop header is not regarded as being
85 // part of the loop that it heads, so that e.g. the nesting depth of an
86 // outer-most loop header is 0.
87 uint32_t LoopNestingDepth(uint32_t bb_id);
88
89 // Returns the id of the header of the innermost switch construct
90 // that contains |bb_id| as long as there is no intervening loop. Returns |0|
91 // if no such construct exists.
92 uint32_t ContainingSwitch(uint32_t bb_id) {
93 auto it = bb_to_construct_.find(bb_id);
94 if (it == bb_to_construct_.end()) {
95 return 0;
96 }
97 return it->second.containing_switch;
98 }
99 // Returns the id of the merge block of the innermost switch construct
100 // that contains |bb_id| as long as there is no intervening loop. Return |0|
101 // if no such block exists.
102 uint32_t SwitchMergeBlock(uint32_t bb_id);
103
104 // Returns true if |bb_id| is the continue block for a loop.
105 bool IsContinueBlock(uint32_t bb_id);
106
107 // Returns true if |bb_id| is in the continue construct for its inner most
108 // containing loop.
109 bool IsInContainingLoopsContinueConstruct(uint32_t bb_id);
110
111 // Returns true if |bb_id| is in the continue construct for any loop in its
112 // function.
113 bool IsInContinueConstruct(uint32_t bb_id);
114
115 // Return true if |bb_id| is the merge block for a construct.
116 bool IsMergeBlock(uint32_t bb_id);
117
118 // Returns the set of function ids that are called directly or indirectly from
119 // a continue construct.
120 std::unordered_set<uint32_t> FindFuncsCalledFromContinue();
121
122 private:
123 // Struct used to hold the information for a basic block.
124 // |containing_construct| is the header for the innermost containing
125 // construct, or 0 if no such construct exists. It could be a selection
126 // construct or a loop construct.
127 //
128 // |containing_loop| is the innermost containing loop construct, or 0 if the
129 // basic bloc is not in a loop. If the basic block is in a selection
130 // construct that is contained in a loop construct, then these two values will
131 // not be the same.
132 //
133 // |containing_switch| is the innermost contain selection construct with an
134 // |OpSwitch| for the branch, as long as there is not intervening loop. This
135 // is used to identify the selection construct from which it can break.
136 //
137 // |in_continue| is true of the block is in the continue construct for its
138 // innermost containing loop.
139 struct ConstructInfo {
140 uint32_t containing_construct;
141 uint32_t containing_loop;
142 uint32_t containing_switch;
143 bool in_continue;
144 };
145
146 // Populates |bb_to_construct_| with the innermost containing merge and loop
147 // constructs for each basic block in |func|.
148 void AddBlocksInFunction(Function* func);
149
150 IRContext* context_;
151
152 // A map from a basic block to the headers of its inner most containing
153 // constructs.
154 std::unordered_map<uint32_t, ConstructInfo> bb_to_construct_;
155 utils::BitVector merge_blocks_;
156 };
157
158 } // namespace opt
159 } // namespace spvtools
160 #endif // SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_