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 #include <string>
16
17 #include "gmock/gmock.h"
18 #include "source/opt/struct_cfg_analysis.h"
19 #include "test/opt/assembly_builder.h"
20 #include "test/opt/pass_fixture.h"
21 #include "test/opt/pass_utils.h"
22
23 namespace spvtools {
24 namespace opt {
25 namespace {
26
27 using StructCFGAnalysisTest = PassTest<::testing::Test>;
28
TEST_F(StructCFGAnalysisTest,BBInSelection)29 TEST_F(StructCFGAnalysisTest, BBInSelection) {
30 const std::string text = R"(
31 OpCapability Shader
32 OpMemoryModel Logical GLSL450
33 OpEntryPoint Fragment %main "main"
34 %void = OpTypeVoid
35 %bool = OpTypeBool
36 %bool_undef = OpUndef %bool
37 %uint = OpTypeInt 32 0
38 %uint_undef = OpUndef %uint
39 %void_func = OpTypeFunction %void
40 %main = OpFunction %void None %void_func
41 %1 = OpLabel
42 OpSelectionMerge %3 None
43 OpBranchConditional %undef_bool %2 %3
44 %2 = OpLabel
45 OpBranch %3
46 %3 = OpLabel
47 OpReturn
48 OpFunctionEnd
49 )";
50
51 std::unique_ptr<IRContext> context =
52 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
53 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
54
55 StructuredCFGAnalysis analysis(context.get());
56
57 // The header is not in the construct.
58 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
59 EXPECT_EQ(analysis.ContainingLoop(1), 0);
60 EXPECT_EQ(analysis.MergeBlock(1), 0);
61 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
62
63 // BB2 is in the construct.
64 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
65 EXPECT_EQ(analysis.ContainingLoop(2), 0);
66 EXPECT_EQ(analysis.MergeBlock(2), 3);
67 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
68
69 // The merge node is not in the construct.
70 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
71 EXPECT_EQ(analysis.ContainingLoop(3), 0);
72 EXPECT_EQ(analysis.MergeBlock(3), 0);
73 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
74 }
75
TEST_F(StructCFGAnalysisTest,BBInLoop)76 TEST_F(StructCFGAnalysisTest, BBInLoop) {
77 const std::string text = R"(
78 OpCapability Shader
79 OpMemoryModel Logical GLSL450
80 OpEntryPoint Fragment %main "main"
81 %void = OpTypeVoid
82 %bool = OpTypeBool
83 %bool_undef = OpUndef %bool
84 %uint = OpTypeInt 32 0
85 %uint_undef = OpUndef %uint
86 %void_func = OpTypeFunction %void
87 %main = OpFunction %void None %void_func
88 %entry_lab = OpLabel
89 OpBranch %1
90 %1 = OpLabel
91 OpLoopMerge %3 %4 None
92 OpBranchConditional %undef_bool %2 %3
93 %2 = OpLabel
94 OpBranch %3
95 %4 = OpLabel
96 OpBranch %1
97 %3 = OpLabel
98 OpReturn
99 OpFunctionEnd
100 )";
101
102 std::unique_ptr<IRContext> context =
103 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
104 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
105
106 StructuredCFGAnalysis analysis(context.get());
107
108 // The header is not in the construct.
109 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
110 EXPECT_EQ(analysis.ContainingLoop(1), 0);
111 EXPECT_EQ(analysis.MergeBlock(1), 0);
112 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
113
114 // BB2 is in the construct.
115 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
116 EXPECT_EQ(analysis.ContainingLoop(2), 1);
117 EXPECT_EQ(analysis.MergeBlock(2), 3);
118 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
119
120 // The merge node is not in the construct.
121 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
122 EXPECT_EQ(analysis.ContainingLoop(3), 0);
123 EXPECT_EQ(analysis.MergeBlock(3), 0);
124 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
125
126 // The continue block is in the construct.
127 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
128 EXPECT_EQ(analysis.ContainingLoop(4), 1);
129 EXPECT_EQ(analysis.MergeBlock(4), 3);
130 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
131 }
132
TEST_F(StructCFGAnalysisTest,SelectionInLoop)133 TEST_F(StructCFGAnalysisTest, SelectionInLoop) {
134 const std::string text = R"(
135 OpCapability Shader
136 OpMemoryModel Logical GLSL450
137 OpEntryPoint Fragment %main "main"
138 %void = OpTypeVoid
139 %bool = OpTypeBool
140 %bool_undef = OpUndef %bool
141 %uint = OpTypeInt 32 0
142 %uint_undef = OpUndef %uint
143 %void_func = OpTypeFunction %void
144 %main = OpFunction %void None %void_func
145 %entry_lab = OpLabel
146 OpBranch %1
147 %1 = OpLabel
148 OpLoopMerge %3 %4 None
149 OpBranchConditional %undef_bool %2 %3
150 %2 = OpLabel
151 OpSelectionMerge %6 None
152 OpBranchConditional %undef_bool %5 %6
153 %5 = OpLabel
154 OpBranch %6
155 %6 = OpLabel
156 OpBranch %3
157 %4 = OpLabel
158 OpBranch %1
159 %3 = OpLabel
160 OpReturn
161 OpFunctionEnd
162 )";
163
164 std::unique_ptr<IRContext> context =
165 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
166 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
167
168 StructuredCFGAnalysis analysis(context.get());
169
170 // The loop header is not in either construct.
171 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
172 EXPECT_EQ(analysis.ContainingLoop(1), 0);
173 EXPECT_EQ(analysis.MergeBlock(1), 0);
174 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
175
176 // Selection header is in the loop only.
177 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
178 EXPECT_EQ(analysis.ContainingLoop(2), 1);
179 EXPECT_EQ(analysis.MergeBlock(2), 3);
180 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
181
182 // The loop merge node is not in either construct.
183 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
184 EXPECT_EQ(analysis.ContainingLoop(3), 0);
185 EXPECT_EQ(analysis.MergeBlock(3), 0);
186 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
187
188 // The continue block is in the loop only.
189 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
190 EXPECT_EQ(analysis.ContainingLoop(4), 1);
191 EXPECT_EQ(analysis.MergeBlock(4), 3);
192 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
193
194 // BB5 is in the selection fist and the loop.
195 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
196 EXPECT_EQ(analysis.ContainingLoop(5), 1);
197 EXPECT_EQ(analysis.MergeBlock(5), 6);
198 EXPECT_EQ(analysis.LoopMergeBlock(5), 3);
199
200 // The selection merge is in the loop only.
201 EXPECT_EQ(analysis.ContainingConstruct(6), 1);
202 EXPECT_EQ(analysis.ContainingLoop(6), 1);
203 EXPECT_EQ(analysis.MergeBlock(6), 3);
204 EXPECT_EQ(analysis.LoopMergeBlock(6), 3);
205 }
206
TEST_F(StructCFGAnalysisTest,LoopInSelection)207 TEST_F(StructCFGAnalysisTest, LoopInSelection) {
208 const std::string text = R"(
209 OpCapability Shader
210 OpMemoryModel Logical GLSL450
211 OpEntryPoint Fragment %main "main"
212 %void = OpTypeVoid
213 %bool = OpTypeBool
214 %bool_undef = OpUndef %bool
215 %uint = OpTypeInt 32 0
216 %uint_undef = OpUndef %uint
217 %void_func = OpTypeFunction %void
218 %main = OpFunction %void None %void_func
219 %entry_lab = OpLabel
220 OpBranch %1
221 %1 = OpLabel
222 OpSelectionMerge %3 None
223 OpBranchConditional %undef_bool %2 %3
224 %2 = OpLabel
225 OpLoopMerge %4 %5 None
226 OpBranchConditional %undef_bool %4 %6
227 %5 = OpLabel
228 OpBranch %2
229 %6 = OpLabel
230 OpBranch %4
231 %4 = OpLabel
232 OpBranch %3
233 %3 = OpLabel
234 OpReturn
235 OpFunctionEnd
236 )";
237
238 std::unique_ptr<IRContext> context =
239 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
240 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
241
242 StructuredCFGAnalysis analysis(context.get());
243
244 // The selection header is not in either construct.
245 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
246 EXPECT_EQ(analysis.ContainingLoop(1), 0);
247 EXPECT_EQ(analysis.MergeBlock(1), 0);
248 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
249
250 // Loop header is in the selection only.
251 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
252 EXPECT_EQ(analysis.ContainingLoop(2), 0);
253 EXPECT_EQ(analysis.MergeBlock(2), 3);
254 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
255
256 // The selection merge node is not in either construct.
257 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
258 EXPECT_EQ(analysis.ContainingLoop(3), 0);
259 EXPECT_EQ(analysis.MergeBlock(3), 0);
260 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
261
262 // The loop merge is in the selection only.
263 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
264 EXPECT_EQ(analysis.ContainingLoop(4), 0);
265 EXPECT_EQ(analysis.MergeBlock(4), 3);
266 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
267
268 // The loop continue target is in the loop.
269 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
270 EXPECT_EQ(analysis.ContainingLoop(5), 2);
271 EXPECT_EQ(analysis.MergeBlock(5), 4);
272 EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
273
274 // BB6 is in the loop.
275 EXPECT_EQ(analysis.ContainingConstruct(6), 2);
276 EXPECT_EQ(analysis.ContainingLoop(6), 2);
277 EXPECT_EQ(analysis.MergeBlock(6), 4);
278 EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
279 }
280
TEST_F(StructCFGAnalysisTest,SelectionInSelection)281 TEST_F(StructCFGAnalysisTest, SelectionInSelection) {
282 const std::string text = R"(
283 OpCapability Shader
284 OpMemoryModel Logical GLSL450
285 OpEntryPoint Fragment %main "main"
286 %void = OpTypeVoid
287 %bool = OpTypeBool
288 %bool_undef = OpUndef %bool
289 %uint = OpTypeInt 32 0
290 %uint_undef = OpUndef %uint
291 %void_func = OpTypeFunction %void
292 %main = OpFunction %void None %void_func
293 %entry_lab = OpLabel
294 OpBranch %1
295 %1 = OpLabel
296 OpSelectionMerge %3 None
297 OpBranchConditional %undef_bool %2 %3
298 %2 = OpLabel
299 OpSelectionMerge %4 None
300 OpBranchConditional %undef_bool %4 %5
301 %5 = OpLabel
302 OpBranch %4
303 %4 = OpLabel
304 OpBranch %3
305 %3 = OpLabel
306 OpReturn
307 OpFunctionEnd
308 )";
309
310 std::unique_ptr<IRContext> context =
311 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
312 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
313
314 StructuredCFGAnalysis analysis(context.get());
315
316 // The outer selection header is not in either construct.
317 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
318 EXPECT_EQ(analysis.ContainingLoop(1), 0);
319 EXPECT_EQ(analysis.MergeBlock(1), 0);
320 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
321
322 // The inner header is in the outer selection.
323 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
324 EXPECT_EQ(analysis.ContainingLoop(2), 0);
325 EXPECT_EQ(analysis.MergeBlock(2), 3);
326 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
327
328 // The outer merge node is not in either construct.
329 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
330 EXPECT_EQ(analysis.ContainingLoop(3), 0);
331 EXPECT_EQ(analysis.MergeBlock(3), 0);
332 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
333
334 // The inner merge is in the outer selection.
335 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
336 EXPECT_EQ(analysis.ContainingLoop(4), 0);
337 EXPECT_EQ(analysis.MergeBlock(4), 3);
338 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
339
340 // BB5 is in the inner selection.
341 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
342 EXPECT_EQ(analysis.ContainingLoop(5), 0);
343 EXPECT_EQ(analysis.MergeBlock(5), 4);
344 EXPECT_EQ(analysis.LoopMergeBlock(5), 0);
345 }
346
TEST_F(StructCFGAnalysisTest,LoopInLoop)347 TEST_F(StructCFGAnalysisTest, LoopInLoop) {
348 const std::string text = R"(
349 OpCapability Shader
350 OpMemoryModel Logical GLSL450
351 OpEntryPoint Fragment %main "main"
352 %void = OpTypeVoid
353 %bool = OpTypeBool
354 %bool_undef = OpUndef %bool
355 %uint = OpTypeInt 32 0
356 %uint_undef = OpUndef %uint
357 %void_func = OpTypeFunction %void
358 %main = OpFunction %void None %void_func
359 %entry_lab = OpLabel
360 OpBranch %1
361 %1 = OpLabel
362 OpLoopMerge %3 %7 None
363 OpBranchConditional %undef_bool %2 %3
364 %2 = OpLabel
365 OpLoopMerge %4 %5 None
366 OpBranchConditional %undef_bool %4 %6
367 %5 = OpLabel
368 OpBranch %2
369 %6 = OpLabel
370 OpBranch %4
371 %4 = OpLabel
372 OpBranch %3
373 %7 = OpLabel
374 OpBranch %1
375 %3 = OpLabel
376 OpReturn
377 OpFunctionEnd
378 )";
379
380 std::unique_ptr<IRContext> context =
381 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
382 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
383
384 StructuredCFGAnalysis analysis(context.get());
385
386 // The outer loop header is not in either construct.
387 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
388 EXPECT_EQ(analysis.ContainingLoop(1), 0);
389 EXPECT_EQ(analysis.MergeBlock(1), 0);
390 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
391
392 // The inner loop header is in the outer loop.
393 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
394 EXPECT_EQ(analysis.ContainingLoop(2), 1);
395 EXPECT_EQ(analysis.MergeBlock(2), 3);
396 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
397
398 // The outer merge node is not in either construct.
399 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
400 EXPECT_EQ(analysis.ContainingLoop(3), 0);
401 EXPECT_EQ(analysis.MergeBlock(3), 0);
402 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
403
404 // The inner merge is in the outer loop.
405 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
406 EXPECT_EQ(analysis.ContainingLoop(4), 1);
407 EXPECT_EQ(analysis.MergeBlock(4), 3);
408 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
409
410 // The inner continue target is in the inner loop.
411 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
412 EXPECT_EQ(analysis.ContainingLoop(5), 2);
413 EXPECT_EQ(analysis.MergeBlock(5), 4);
414 EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
415
416 // BB6 is in the loop.
417 EXPECT_EQ(analysis.ContainingConstruct(6), 2);
418 EXPECT_EQ(analysis.ContainingLoop(6), 2);
419 EXPECT_EQ(analysis.MergeBlock(6), 4);
420 EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
421
422 // The outer continue target is in the outer loop.
423 EXPECT_EQ(analysis.ContainingConstruct(7), 1);
424 EXPECT_EQ(analysis.ContainingLoop(7), 1);
425 EXPECT_EQ(analysis.MergeBlock(7), 3);
426 EXPECT_EQ(analysis.LoopMergeBlock(7), 3);
427 }
428
TEST_F(StructCFGAnalysisTest,KernelTest)429 TEST_F(StructCFGAnalysisTest, KernelTest) {
430 const std::string text = R"(
431 OpCapability Kernel
432 OpMemoryModel Logical GLSL450
433 OpEntryPoint Fragment %main "main"
434 %void = OpTypeVoid
435 %bool = OpTypeBool
436 %bool_undef = OpUndef %bool
437 %void_func = OpTypeFunction %void
438 %main = OpFunction %void None %void_func
439 %1 = OpLabel
440 OpBranchConditional %undef_bool %2 %3
441 %2 = OpLabel
442 OpBranch %3
443 %3 = OpLabel
444 OpReturn
445 OpFunctionEnd
446 )";
447
448 std::unique_ptr<IRContext> context =
449 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
450 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
451
452 StructuredCFGAnalysis analysis(context.get());
453
454 // No structured control flow, so none of the basic block are in any
455 // construct.
456 for (uint32_t i = 1; i <= 3; i++) {
457 EXPECT_EQ(analysis.ContainingConstruct(i), 0);
458 EXPECT_EQ(analysis.ContainingLoop(i), 0);
459 EXPECT_EQ(analysis.MergeBlock(i), 0);
460 EXPECT_EQ(analysis.LoopMergeBlock(i), 0);
461 }
462 }
463
464 } // namespace
465 } // namespace opt
466 } // namespace spvtools
467