/src/spirv-tools/source/val/construct.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2015-2016 The Khronos Group Inc. |
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 | | #include "source/val/construct.h" |
16 | | |
17 | | #include <cassert> |
18 | | #include <cstddef> |
19 | | |
20 | | #include "source/val/function.h" |
21 | | #include "source/val/validation_state.h" |
22 | | |
23 | | namespace spvtools { |
24 | | namespace val { |
25 | | |
26 | | Construct::Construct(ConstructType construct_type, BasicBlock* entry, |
27 | | BasicBlock* exit, std::vector<Construct*> constructs) |
28 | 68.7k | : type_(construct_type), |
29 | 68.7k | corresponding_constructs_(constructs), |
30 | 68.7k | entry_block_(entry), |
31 | 68.7k | exit_block_(exit) {} |
32 | | |
33 | 483k | ConstructType Construct::type() const { return type_; } |
34 | | |
35 | 3.82k | const std::vector<Construct*>& Construct::corresponding_constructs() const { |
36 | 3.82k | return corresponding_constructs_; |
37 | 3.82k | } |
38 | 17.3k | std::vector<Construct*>& Construct::corresponding_constructs() { |
39 | 17.3k | return corresponding_constructs_; |
40 | 17.3k | } |
41 | | |
42 | 52.0k | bool ValidateConstructSize(ConstructType type, size_t size) { |
43 | 52.0k | switch (type) { |
44 | 0 | case ConstructType::kSelection: |
45 | 0 | return size == 0; |
46 | 26.0k | case ConstructType::kContinue: |
47 | 26.0k | return size == 1; |
48 | 26.0k | case ConstructType::kLoop: |
49 | 26.0k | return size == 1; |
50 | 0 | case ConstructType::kCase: |
51 | 0 | return size >= 1; |
52 | 0 | default: |
53 | 0 | assert(1 == 0 && "Type not defined"); |
54 | 52.0k | } |
55 | 0 | return false; |
56 | 52.0k | } |
57 | | |
58 | | void Construct::set_corresponding_constructs( |
59 | 52.0k | std::vector<Construct*> constructs) { |
60 | 52.0k | assert(ValidateConstructSize(type_, constructs.size())); |
61 | 52.0k | corresponding_constructs_ = constructs; |
62 | 52.0k | } |
63 | | |
64 | 97.5k | const BasicBlock* Construct::entry_block() const { return entry_block_; } |
65 | 87.6k | BasicBlock* Construct::entry_block() { return entry_block_; } |
66 | | |
67 | 29.9k | const BasicBlock* Construct::exit_block() const { return exit_block_; } |
68 | 0 | BasicBlock* Construct::exit_block() { return exit_block_; } |
69 | | |
70 | 5.98k | void Construct::set_exit(BasicBlock* block) { exit_block_ = block; } |
71 | | |
72 | 8.18k | Construct::ConstructBlockSet Construct::blocks(Function* /*function*/) const { |
73 | 8.18k | const auto header = entry_block(); |
74 | 8.18k | const auto exit = exit_block(); |
75 | 8.18k | const bool is_continue = type() == ConstructType::kContinue; |
76 | 8.18k | const bool is_loop = type() == ConstructType::kLoop; |
77 | 8.18k | const BasicBlock* continue_header = nullptr; |
78 | 8.18k | if (is_loop) { |
79 | | // The only corresponding construct for a loop is the continue. |
80 | 1.98k | continue_header = (*corresponding_constructs().begin())->entry_block(); |
81 | 1.98k | } |
82 | 8.18k | std::vector<BasicBlock*> stack; |
83 | 8.18k | stack.push_back(const_cast<BasicBlock*>(header)); |
84 | 8.18k | ConstructBlockSet construct_blocks; |
85 | 107k | while (!stack.empty()) { |
86 | 99.7k | auto* block = stack.back(); |
87 | 99.7k | stack.pop_back(); |
88 | | |
89 | 99.7k | if (header->structurally_dominates(*block)) { |
90 | 92.9k | bool include = false; |
91 | 92.9k | if (is_continue && exit->structurally_postdominates(*block)) { |
92 | | // Continue construct include blocks dominated by the continue target |
93 | | // and post-dominated by the back-edge block. |
94 | 3.48k | include = true; |
95 | 89.4k | } else if (!exit->structurally_dominates(*block)) { |
96 | | // Selection and loop constructs include blocks dominated by the header |
97 | | // and not dominated by the merge. |
98 | 74.8k | include = true; |
99 | 74.8k | if (is_loop && continue_header->structurally_dominates(*block)) { |
100 | | // Loop constructs have an additional constraint that they do not |
101 | | // include blocks dominated by the continue construct. Since all |
102 | | // blocks in the continue construct are dominated by the continue |
103 | | // target, we just test for dominance by continue target. |
104 | 4.57k | include = false; |
105 | 4.57k | } |
106 | 74.8k | } |
107 | 92.9k | if (include) { |
108 | 73.7k | if (!construct_blocks.insert(block).second) continue; |
109 | | |
110 | 91.5k | for (auto succ : *block->structural_successors()) { |
111 | 91.5k | stack.push_back(succ); |
112 | 91.5k | } |
113 | 48.1k | } |
114 | 92.9k | } |
115 | 99.7k | } |
116 | | |
117 | 8.18k | return construct_blocks; |
118 | 8.18k | } |
119 | | |
120 | 17.5k | bool Construct::IsStructuredExit(ValidationState_t& _, BasicBlock* dest) const { |
121 | | // Structured Exits: |
122 | | // - Selection: |
123 | | // - branch to its merge |
124 | | // - branch to nearest enclosing loop merge or continue |
125 | | // - branch to nearest enclosing switch selection merge |
126 | | // - Loop: |
127 | | // - branch to its merge |
128 | | // - branch to its continue |
129 | | // - Continue: |
130 | | // - branch to loop header |
131 | | // - branch to loop merge |
132 | | // |
133 | | // Note: we will never see a case construct here. |
134 | 17.5k | assert(type() != ConstructType::kCase); |
135 | 17.5k | if (type() == ConstructType::kLoop) { |
136 | 5.42k | auto header = entry_block(); |
137 | 5.42k | auto terminator = header->terminator(); |
138 | 5.42k | auto index = terminator - &_.ordered_instructions()[0]; |
139 | 5.42k | auto merge_inst = &_.ordered_instructions()[index - 1]; |
140 | 5.42k | auto merge_block_id = merge_inst->GetOperandAs<uint32_t>(0u); |
141 | 5.42k | auto continue_block_id = merge_inst->GetOperandAs<uint32_t>(1u); |
142 | 5.42k | if (dest->id() == merge_block_id || dest->id() == continue_block_id) { |
143 | 5.41k | return true; |
144 | 5.41k | } |
145 | 12.1k | } else if (type() == ConstructType::kContinue) { |
146 | 1.84k | auto loop_construct = corresponding_constructs()[0]; |
147 | 1.84k | auto header = loop_construct->entry_block(); |
148 | 1.84k | auto terminator = header->terminator(); |
149 | 1.84k | auto index = terminator - &_.ordered_instructions()[0]; |
150 | 1.84k | auto merge_inst = &_.ordered_instructions()[index - 1]; |
151 | 1.84k | auto merge_block_id = merge_inst->GetOperandAs<uint32_t>(0u); |
152 | 1.84k | if (dest == header || dest->id() == merge_block_id) { |
153 | 1.83k | return true; |
154 | 1.83k | } |
155 | 10.2k | } else { |
156 | 10.2k | assert(type() == ConstructType::kSelection); |
157 | 10.2k | if (dest == exit_block()) { |
158 | 5.45k | return true; |
159 | 5.45k | } |
160 | | |
161 | | // The next block in the traversal is either: |
162 | | // i. The header block that declares |block| as its merge block. |
163 | | // ii. The immediate dominator of |block|. |
164 | 9.52k | auto NextBlock = [](const BasicBlock* block) -> const BasicBlock* { |
165 | 12.9k | for (auto& use : block->label()->uses()) { |
166 | 12.9k | if ((use.first->opcode() == spv::Op::OpLoopMerge || |
167 | 12.9k | use.first->opcode() == spv::Op::OpSelectionMerge) && |
168 | 12.9k | use.second == 1 && |
169 | 12.9k | use.first->block()->structurally_dominates(*block) && |
170 | | // A header likely declared itself as its merge. |
171 | 12.9k | use.first->block() != block) { |
172 | 1.62k | return use.first->block(); |
173 | 1.62k | } |
174 | 12.9k | } |
175 | 7.89k | return block->immediate_structural_dominator(); |
176 | 9.52k | }; |
177 | | |
178 | 4.82k | bool seen_switch = false; |
179 | 4.82k | auto header = entry_block(); |
180 | 4.82k | auto block = NextBlock(header); |
181 | 9.52k | while (block) { |
182 | 9.48k | auto terminator = block->terminator(); |
183 | 9.48k | auto index = terminator - &_.ordered_instructions()[0]; |
184 | 9.48k | auto merge_inst = &_.ordered_instructions()[index - 1]; |
185 | 9.48k | if (merge_inst->opcode() == spv::Op::OpLoopMerge || |
186 | 9.48k | (header->terminator()->opcode() != spv::Op::OpSwitch && |
187 | 4.90k | merge_inst->opcode() == spv::Op::OpSelectionMerge && |
188 | 5.84k | terminator->opcode() == spv::Op::OpSwitch)) { |
189 | 5.84k | auto merge_target = merge_inst->GetOperandAs<uint32_t>(0u); |
190 | 5.84k | auto merge_block = merge_inst->function()->GetBlock(merge_target).first; |
191 | 5.84k | if (merge_block->structurally_dominates(*header)) { |
192 | 1.04k | block = NextBlock(block); |
193 | 1.04k | continue; |
194 | 1.04k | } |
195 | | |
196 | 4.80k | if ((!seen_switch || merge_inst->opcode() == spv::Op::OpLoopMerge) && |
197 | 4.80k | dest->id() == merge_target) { |
198 | 2.96k | return true; |
199 | 2.96k | } else if (merge_inst->opcode() == spv::Op::OpLoopMerge) { |
200 | 1.82k | auto continue_target = merge_inst->GetOperandAs<uint32_t>(1u); |
201 | 1.82k | if (dest->id() == continue_target) { |
202 | 1.80k | return true; |
203 | 1.80k | } |
204 | 1.82k | } |
205 | | |
206 | 42 | if (terminator->opcode() == spv::Op::OpSwitch) { |
207 | 19 | seen_switch = true; |
208 | 19 | } |
209 | | |
210 | | // Hit an enclosing loop and didn't break or continue. |
211 | 42 | if (merge_inst->opcode() == spv::Op::OpLoopMerge) return false; |
212 | 42 | } |
213 | | |
214 | 3.65k | block = NextBlock(block); |
215 | 3.65k | } |
216 | 4.82k | } |
217 | | |
218 | 53 | return false; |
219 | 17.5k | } |
220 | | |
221 | | } // namespace val |
222 | | } // namespace spvtools |