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 "source/opt/struct_cfg_analysis.h"
16
17 #include <string>
18
19 #include "gmock/gmock.h"
20 #include "test/opt/assembly_builder.h"
21 #include "test/opt/pass_fixture.h"
22 #include "test/opt/pass_utils.h"
23
24 namespace spvtools {
25 namespace opt {
26 namespace {
27
28 using StructCFGAnalysisTest = PassTest<::testing::Test>;
29 using ::testing::UnorderedElementsAre;
30
TEST_F(StructCFGAnalysisTest,BBInSelection)31 TEST_F(StructCFGAnalysisTest, BBInSelection) {
32 const std::string text = R"(
33 OpCapability Shader
34 OpMemoryModel Logical GLSL450
35 OpEntryPoint Fragment %main "main"
36 %void = OpTypeVoid
37 %bool = OpTypeBool
38 %bool_undef = OpUndef %bool
39 %uint = OpTypeInt 32 0
40 %uint_undef = OpUndef %uint
41 %void_func = OpTypeFunction %void
42 %main = OpFunction %void None %void_func
43 %1 = OpLabel
44 OpSelectionMerge %3 None
45 OpBranchConditional %undef_bool %2 %3
46 %2 = OpLabel
47 OpBranch %3
48 %3 = OpLabel
49 OpReturn
50 OpFunctionEnd
51 )";
52
53 std::unique_ptr<IRContext> context =
54 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
55 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
56
57 StructuredCFGAnalysis analysis(context.get());
58
59 // The header is not in the construct.
60 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
61 EXPECT_EQ(analysis.ContainingLoop(1), 0);
62 EXPECT_EQ(analysis.MergeBlock(1), 0);
63 EXPECT_EQ(analysis.NestingDepth(1), 0);
64 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
65 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
66 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
67 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
68 EXPECT_FALSE(analysis.IsContinueBlock(1));
69 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
70 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
71 EXPECT_FALSE(analysis.IsMergeBlock(1));
72
73 // BB2 is in the construct.
74 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
75 EXPECT_EQ(analysis.ContainingLoop(2), 0);
76 EXPECT_EQ(analysis.MergeBlock(2), 3);
77 EXPECT_EQ(analysis.NestingDepth(2), 1);
78 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
79 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
80 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
81 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
82 EXPECT_FALSE(analysis.IsContinueBlock(2));
83 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
84 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
85 EXPECT_FALSE(analysis.IsMergeBlock(2));
86
87 // The merge node is not in the construct.
88 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
89 EXPECT_EQ(analysis.ContainingLoop(3), 0);
90 EXPECT_EQ(analysis.MergeBlock(3), 0);
91 EXPECT_EQ(analysis.NestingDepth(3), 0);
92 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
93 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
94 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
95 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
96 EXPECT_FALSE(analysis.IsContinueBlock(3));
97 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
98 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
99 EXPECT_TRUE(analysis.IsMergeBlock(3));
100 }
101
TEST_F(StructCFGAnalysisTest,BBInLoop)102 TEST_F(StructCFGAnalysisTest, BBInLoop) {
103 const std::string text = R"(
104 OpCapability Shader
105 OpMemoryModel Logical GLSL450
106 OpEntryPoint Fragment %main "main"
107 %void = OpTypeVoid
108 %bool = OpTypeBool
109 %bool_undef = OpUndef %bool
110 %uint = OpTypeInt 32 0
111 %uint_undef = OpUndef %uint
112 %void_func = OpTypeFunction %void
113 %main = OpFunction %void None %void_func
114 %entry_lab = OpLabel
115 OpBranch %1
116 %1 = OpLabel
117 OpLoopMerge %3 %4 None
118 OpBranchConditional %undef_bool %2 %3
119 %2 = OpLabel
120 OpBranch %3
121 %4 = OpLabel
122 OpBranch %1
123 %3 = OpLabel
124 OpReturn
125 OpFunctionEnd
126 )";
127
128 std::unique_ptr<IRContext> context =
129 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
130 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
131
132 StructuredCFGAnalysis analysis(context.get());
133
134 // The header is not in the construct.
135 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
136 EXPECT_EQ(analysis.ContainingLoop(1), 0);
137 EXPECT_EQ(analysis.MergeBlock(1), 0);
138 EXPECT_EQ(analysis.NestingDepth(1), 0);
139 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
140 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
141 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
142 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
143 EXPECT_FALSE(analysis.IsContinueBlock(1));
144 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
145 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
146 EXPECT_FALSE(analysis.IsMergeBlock(1));
147
148 // BB2 is in the construct.
149 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
150 EXPECT_EQ(analysis.ContainingLoop(2), 1);
151 EXPECT_EQ(analysis.MergeBlock(2), 3);
152 EXPECT_EQ(analysis.NestingDepth(2), 1);
153 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
154 EXPECT_EQ(analysis.LoopNestingDepth(2), 1);
155 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
156 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
157 EXPECT_FALSE(analysis.IsContinueBlock(2));
158 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
159 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
160 EXPECT_FALSE(analysis.IsMergeBlock(2));
161
162 // The merge node is not in the construct.
163 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
164 EXPECT_EQ(analysis.ContainingLoop(3), 0);
165 EXPECT_EQ(analysis.MergeBlock(3), 0);
166 EXPECT_EQ(analysis.NestingDepth(3), 0);
167 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
168 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
169 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
170 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
171 EXPECT_FALSE(analysis.IsContinueBlock(3));
172 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
173 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
174 EXPECT_TRUE(analysis.IsMergeBlock(3));
175
176 // The continue block is in the construct.
177 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
178 EXPECT_EQ(analysis.ContainingLoop(4), 1);
179 EXPECT_EQ(analysis.MergeBlock(4), 3);
180 EXPECT_EQ(analysis.NestingDepth(4), 1);
181 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
182 EXPECT_EQ(analysis.LoopNestingDepth(4), 1);
183 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
184 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
185 EXPECT_TRUE(analysis.IsContinueBlock(4));
186 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(4));
187 EXPECT_TRUE(analysis.IsInContinueConstruct(4));
188 EXPECT_FALSE(analysis.IsMergeBlock(4));
189 }
190
TEST_F(StructCFGAnalysisTest,SelectionInLoop)191 TEST_F(StructCFGAnalysisTest, SelectionInLoop) {
192 const std::string text = R"(
193 OpCapability Shader
194 OpMemoryModel Logical GLSL450
195 OpEntryPoint Fragment %main "main"
196 %void = OpTypeVoid
197 %bool = OpTypeBool
198 %bool_undef = OpUndef %bool
199 %uint = OpTypeInt 32 0
200 %uint_undef = OpUndef %uint
201 %void_func = OpTypeFunction %void
202 %main = OpFunction %void None %void_func
203 %entry_lab = OpLabel
204 OpBranch %1
205 %1 = OpLabel
206 OpLoopMerge %3 %4 None
207 OpBranchConditional %undef_bool %2 %3
208 %2 = OpLabel
209 OpSelectionMerge %6 None
210 OpBranchConditional %undef_bool %5 %6
211 %5 = OpLabel
212 OpBranch %6
213 %6 = OpLabel
214 OpBranch %3
215 %4 = OpLabel
216 OpBranch %1
217 %3 = OpLabel
218 OpReturn
219 OpFunctionEnd
220 )";
221
222 std::unique_ptr<IRContext> context =
223 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
224 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
225
226 StructuredCFGAnalysis analysis(context.get());
227
228 // The loop header is not in either construct.
229 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
230 EXPECT_EQ(analysis.ContainingLoop(1), 0);
231 EXPECT_EQ(analysis.MergeBlock(1), 0);
232 EXPECT_EQ(analysis.NestingDepth(1), 0);
233 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
234 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
235 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
236 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
237 EXPECT_FALSE(analysis.IsContinueBlock(1));
238 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
239 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
240 EXPECT_FALSE(analysis.IsMergeBlock(1));
241
242 // Selection header is in the loop only.
243 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
244 EXPECT_EQ(analysis.ContainingLoop(2), 1);
245 EXPECT_EQ(analysis.MergeBlock(2), 3);
246 EXPECT_EQ(analysis.NestingDepth(2), 1);
247 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
248 EXPECT_EQ(analysis.LoopNestingDepth(2), 1);
249 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
250 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
251 EXPECT_FALSE(analysis.IsContinueBlock(2));
252 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
253 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
254 EXPECT_FALSE(analysis.IsMergeBlock(2));
255
256 // The loop 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.NestingDepth(3), 0);
261 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
262 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
263 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
264 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
265 EXPECT_FALSE(analysis.IsContinueBlock(3));
266 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
267 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
268 EXPECT_TRUE(analysis.IsMergeBlock(3));
269
270 // The continue block is in the loop only.
271 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
272 EXPECT_EQ(analysis.ContainingLoop(4), 1);
273 EXPECT_EQ(analysis.MergeBlock(4), 3);
274 EXPECT_EQ(analysis.NestingDepth(4), 1);
275 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
276 EXPECT_EQ(analysis.LoopNestingDepth(4), 1);
277 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
278 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
279 EXPECT_TRUE(analysis.IsContinueBlock(4));
280 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(4));
281 EXPECT_TRUE(analysis.IsInContinueConstruct(4));
282 EXPECT_FALSE(analysis.IsMergeBlock(4));
283
284 // BB5 is in the selection and the loop.
285 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
286 EXPECT_EQ(analysis.ContainingLoop(5), 1);
287 EXPECT_EQ(analysis.MergeBlock(5), 6);
288 EXPECT_EQ(analysis.NestingDepth(5), 2);
289 EXPECT_EQ(analysis.LoopMergeBlock(5), 3);
290 EXPECT_EQ(analysis.LoopNestingDepth(5), 1);
291 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
292 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
293 EXPECT_FALSE(analysis.IsContinueBlock(5));
294 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(5));
295 EXPECT_FALSE(analysis.IsInContinueConstruct(5));
296 EXPECT_FALSE(analysis.IsMergeBlock(5));
297
298 // The selection merge is in the loop only.
299 EXPECT_EQ(analysis.ContainingConstruct(6), 1);
300 EXPECT_EQ(analysis.ContainingLoop(6), 1);
301 EXPECT_EQ(analysis.MergeBlock(6), 3);
302 EXPECT_EQ(analysis.NestingDepth(6), 1);
303 EXPECT_EQ(analysis.LoopMergeBlock(6), 3);
304 EXPECT_EQ(analysis.LoopNestingDepth(6), 1);
305 EXPECT_EQ(analysis.ContainingSwitch(6), 0);
306 EXPECT_EQ(analysis.SwitchMergeBlock(6), 0);
307 EXPECT_FALSE(analysis.IsContinueBlock(6));
308 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(6));
309 EXPECT_FALSE(analysis.IsInContinueConstruct(6));
310 EXPECT_TRUE(analysis.IsMergeBlock(6));
311 }
312
TEST_F(StructCFGAnalysisTest,LoopInSelection)313 TEST_F(StructCFGAnalysisTest, LoopInSelection) {
314 const std::string text = R"(
315 OpCapability Shader
316 OpMemoryModel Logical GLSL450
317 OpEntryPoint Fragment %main "main"
318 %void = OpTypeVoid
319 %bool = OpTypeBool
320 %bool_undef = OpUndef %bool
321 %uint = OpTypeInt 32 0
322 %uint_undef = OpUndef %uint
323 %void_func = OpTypeFunction %void
324 %main = OpFunction %void None %void_func
325 %entry_lab = OpLabel
326 OpBranch %1
327 %1 = OpLabel
328 OpSelectionMerge %3 None
329 OpBranchConditional %undef_bool %2 %3
330 %2 = OpLabel
331 OpLoopMerge %4 %5 None
332 OpBranchConditional %undef_bool %4 %6
333 %5 = OpLabel
334 OpBranch %2
335 %6 = OpLabel
336 OpBranch %4
337 %4 = OpLabel
338 OpBranch %3
339 %3 = OpLabel
340 OpReturn
341 OpFunctionEnd
342 )";
343
344 std::unique_ptr<IRContext> context =
345 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
346 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
347
348 StructuredCFGAnalysis analysis(context.get());
349
350 // The selection header is not in either construct.
351 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
352 EXPECT_EQ(analysis.ContainingLoop(1), 0);
353 EXPECT_EQ(analysis.MergeBlock(1), 0);
354 EXPECT_EQ(analysis.NestingDepth(1), 0);
355 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
356 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
357 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
358 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
359 EXPECT_FALSE(analysis.IsContinueBlock(1));
360 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
361 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
362 EXPECT_FALSE(analysis.IsMergeBlock(1));
363
364 // Loop header is in the selection only.
365 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
366 EXPECT_EQ(analysis.ContainingLoop(2), 0);
367 EXPECT_EQ(analysis.MergeBlock(2), 3);
368 EXPECT_EQ(analysis.NestingDepth(2), 1);
369 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
370 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
371 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
372 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
373 EXPECT_FALSE(analysis.IsContinueBlock(2));
374 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
375 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
376 EXPECT_FALSE(analysis.IsMergeBlock(2));
377
378 // The selection merge node is not in either construct.
379 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
380 EXPECT_EQ(analysis.ContainingLoop(3), 0);
381 EXPECT_EQ(analysis.MergeBlock(3), 0);
382 EXPECT_EQ(analysis.NestingDepth(3), 0);
383 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
384 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
385 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
386 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
387 EXPECT_FALSE(analysis.IsContinueBlock(3));
388 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
389 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
390 EXPECT_TRUE(analysis.IsMergeBlock(3));
391
392 // The loop merge is in the selection only.
393 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
394 EXPECT_EQ(analysis.ContainingLoop(4), 0);
395 EXPECT_EQ(analysis.MergeBlock(4), 3);
396 EXPECT_EQ(analysis.NestingDepth(4), 1);
397 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
398 EXPECT_EQ(analysis.LoopNestingDepth(4), 0);
399 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
400 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
401 EXPECT_FALSE(analysis.IsContinueBlock(4));
402 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(4));
403 EXPECT_FALSE(analysis.IsInContinueConstruct(4));
404 EXPECT_TRUE(analysis.IsMergeBlock(4));
405
406 // The loop continue target is in the loop.
407 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
408 EXPECT_EQ(analysis.ContainingLoop(5), 2);
409 EXPECT_EQ(analysis.MergeBlock(5), 4);
410 EXPECT_EQ(analysis.NestingDepth(5), 2);
411 EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
412 EXPECT_EQ(analysis.LoopNestingDepth(5), 1);
413 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
414 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
415 EXPECT_TRUE(analysis.IsContinueBlock(5));
416 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(5));
417 EXPECT_TRUE(analysis.IsInContinueConstruct(5));
418 EXPECT_FALSE(analysis.IsMergeBlock(5));
419
420 // BB6 is in the loop.
421 EXPECT_EQ(analysis.ContainingConstruct(6), 2);
422 EXPECT_EQ(analysis.ContainingLoop(6), 2);
423 EXPECT_EQ(analysis.MergeBlock(6), 4);
424 EXPECT_EQ(analysis.NestingDepth(6), 2);
425 EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
426 EXPECT_EQ(analysis.LoopNestingDepth(6), 1);
427 EXPECT_EQ(analysis.ContainingSwitch(6), 0);
428 EXPECT_EQ(analysis.SwitchMergeBlock(6), 0);
429 EXPECT_FALSE(analysis.IsContinueBlock(6));
430 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(6));
431 EXPECT_FALSE(analysis.IsInContinueConstruct(6));
432 EXPECT_FALSE(analysis.IsMergeBlock(6));
433 }
434
TEST_F(StructCFGAnalysisTest,SelectionInSelection)435 TEST_F(StructCFGAnalysisTest, SelectionInSelection) {
436 const std::string text = R"(
437 OpCapability Shader
438 OpMemoryModel Logical GLSL450
439 OpEntryPoint Fragment %main "main"
440 %void = OpTypeVoid
441 %bool = OpTypeBool
442 %bool_undef = OpUndef %bool
443 %uint = OpTypeInt 32 0
444 %uint_undef = OpUndef %uint
445 %void_func = OpTypeFunction %void
446 %main = OpFunction %void None %void_func
447 %entry_lab = OpLabel
448 OpBranch %1
449 %1 = OpLabel
450 OpSelectionMerge %3 None
451 OpBranchConditional %undef_bool %2 %3
452 %2 = OpLabel
453 OpSelectionMerge %4 None
454 OpBranchConditional %undef_bool %4 %5
455 %5 = OpLabel
456 OpBranch %4
457 %4 = OpLabel
458 OpBranch %3
459 %3 = OpLabel
460 OpReturn
461 OpFunctionEnd
462 )";
463
464 std::unique_ptr<IRContext> context =
465 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
466 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
467
468 StructuredCFGAnalysis analysis(context.get());
469
470 // The outer selection header is not in either construct.
471 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
472 EXPECT_EQ(analysis.ContainingLoop(1), 0);
473 EXPECT_EQ(analysis.MergeBlock(1), 0);
474 EXPECT_EQ(analysis.NestingDepth(1), 0);
475 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
476 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
477 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
478 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
479 EXPECT_FALSE(analysis.IsContinueBlock(1));
480 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
481 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
482 EXPECT_FALSE(analysis.IsMergeBlock(1));
483
484 // The inner header is in the outer selection.
485 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
486 EXPECT_EQ(analysis.ContainingLoop(2), 0);
487 EXPECT_EQ(analysis.MergeBlock(2), 3);
488 EXPECT_EQ(analysis.NestingDepth(2), 1);
489 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
490 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
491 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
492 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
493 EXPECT_FALSE(analysis.IsContinueBlock(2));
494 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
495 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
496 EXPECT_FALSE(analysis.IsMergeBlock(2));
497
498 // The outer merge node is not in either construct.
499 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
500 EXPECT_EQ(analysis.ContainingLoop(3), 0);
501 EXPECT_EQ(analysis.MergeBlock(3), 0);
502 EXPECT_EQ(analysis.NestingDepth(3), 0);
503 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
504 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
505 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
506 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
507 EXPECT_FALSE(analysis.IsContinueBlock(3));
508 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
509 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
510 EXPECT_TRUE(analysis.IsMergeBlock(3));
511
512 // The inner merge is in the outer selection.
513 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
514 EXPECT_EQ(analysis.ContainingLoop(4), 0);
515 EXPECT_EQ(analysis.MergeBlock(4), 3);
516 EXPECT_EQ(analysis.NestingDepth(4), 1);
517 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
518 EXPECT_EQ(analysis.LoopNestingDepth(4), 0);
519 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
520 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
521 EXPECT_FALSE(analysis.IsContinueBlock(4));
522 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(4));
523 EXPECT_FALSE(analysis.IsInContinueConstruct(4));
524 EXPECT_TRUE(analysis.IsMergeBlock(4));
525
526 // BB5 is in the inner selection.
527 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
528 EXPECT_EQ(analysis.ContainingLoop(5), 0);
529 EXPECT_EQ(analysis.MergeBlock(5), 4);
530 EXPECT_EQ(analysis.NestingDepth(5), 2);
531 EXPECT_EQ(analysis.LoopMergeBlock(5), 0);
532 EXPECT_EQ(analysis.LoopNestingDepth(5), 0);
533 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
534 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
535 EXPECT_FALSE(analysis.IsContinueBlock(5));
536 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(5));
537 EXPECT_FALSE(analysis.IsInContinueConstruct(5));
538 EXPECT_FALSE(analysis.IsMergeBlock(5));
539 }
540
TEST_F(StructCFGAnalysisTest,LoopInLoop)541 TEST_F(StructCFGAnalysisTest, LoopInLoop) {
542 const std::string text = R"(
543 OpCapability Shader
544 OpMemoryModel Logical GLSL450
545 OpEntryPoint Fragment %main "main"
546 %void = OpTypeVoid
547 %bool = OpTypeBool
548 %bool_undef = OpUndef %bool
549 %uint = OpTypeInt 32 0
550 %uint_undef = OpUndef %uint
551 %void_func = OpTypeFunction %void
552 %main = OpFunction %void None %void_func
553 %entry_lab = OpLabel
554 OpBranch %1
555 %1 = OpLabel
556 OpLoopMerge %3 %7 None
557 OpBranchConditional %undef_bool %2 %3
558 %2 = OpLabel
559 OpLoopMerge %4 %5 None
560 OpBranchConditional %undef_bool %4 %6
561 %5 = OpLabel
562 OpBranch %2
563 %6 = OpLabel
564 OpBranch %4
565 %4 = OpLabel
566 OpBranch %3
567 %7 = OpLabel
568 OpBranch %1
569 %3 = OpLabel
570 OpReturn
571 OpFunctionEnd
572 )";
573
574 std::unique_ptr<IRContext> context =
575 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
576 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
577
578 StructuredCFGAnalysis analysis(context.get());
579
580 // The outer loop header is not in either construct.
581 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
582 EXPECT_EQ(analysis.ContainingLoop(1), 0);
583 EXPECT_EQ(analysis.MergeBlock(1), 0);
584 EXPECT_EQ(analysis.NestingDepth(1), 0);
585 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
586 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
587 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
588 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
589 EXPECT_FALSE(analysis.IsContinueBlock(1));
590 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
591 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
592 EXPECT_FALSE(analysis.IsMergeBlock(1));
593
594 // The inner loop header is in the outer loop.
595 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
596 EXPECT_EQ(analysis.ContainingLoop(2), 1);
597 EXPECT_EQ(analysis.MergeBlock(2), 3);
598 EXPECT_EQ(analysis.NestingDepth(2), 1);
599 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
600 EXPECT_EQ(analysis.LoopNestingDepth(2), 1);
601 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
602 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
603 EXPECT_FALSE(analysis.IsContinueBlock(2));
604 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
605 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
606 EXPECT_FALSE(analysis.IsMergeBlock(2));
607
608 // The outer merge node is not in either construct.
609 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
610 EXPECT_EQ(analysis.ContainingLoop(3), 0);
611 EXPECT_EQ(analysis.MergeBlock(3), 0);
612 EXPECT_EQ(analysis.NestingDepth(3), 0);
613 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
614 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
615 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
616 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
617 EXPECT_FALSE(analysis.IsContinueBlock(3));
618 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
619 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
620 EXPECT_TRUE(analysis.IsMergeBlock(3));
621
622 // The inner merge is in the outer loop.
623 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
624 EXPECT_EQ(analysis.ContainingLoop(4), 1);
625 EXPECT_EQ(analysis.MergeBlock(4), 3);
626 EXPECT_EQ(analysis.NestingDepth(4), 1);
627 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
628 EXPECT_EQ(analysis.LoopNestingDepth(4), 1);
629 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
630 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
631 EXPECT_FALSE(analysis.IsContinueBlock(4));
632 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(4));
633 EXPECT_FALSE(analysis.IsInContinueConstruct(4));
634 EXPECT_TRUE(analysis.IsMergeBlock(4));
635
636 // The inner continue target is in the inner loop.
637 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
638 EXPECT_EQ(analysis.ContainingLoop(5), 2);
639 EXPECT_EQ(analysis.MergeBlock(5), 4);
640 EXPECT_EQ(analysis.NestingDepth(5), 2);
641 EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
642 EXPECT_EQ(analysis.LoopNestingDepth(5), 2);
643 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
644 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
645 EXPECT_TRUE(analysis.IsContinueBlock(5));
646 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(5));
647 EXPECT_TRUE(analysis.IsInContinueConstruct(5));
648 EXPECT_FALSE(analysis.IsMergeBlock(5));
649
650 // BB6 is in the loop.
651 EXPECT_EQ(analysis.ContainingConstruct(6), 2);
652 EXPECT_EQ(analysis.ContainingLoop(6), 2);
653 EXPECT_EQ(analysis.MergeBlock(6), 4);
654 EXPECT_EQ(analysis.NestingDepth(6), 2);
655 EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
656 EXPECT_EQ(analysis.LoopNestingDepth(6), 2);
657 EXPECT_EQ(analysis.ContainingSwitch(6), 0);
658 EXPECT_EQ(analysis.SwitchMergeBlock(6), 0);
659 EXPECT_FALSE(analysis.IsContinueBlock(6));
660 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(6));
661 EXPECT_FALSE(analysis.IsInContinueConstruct(6));
662 EXPECT_FALSE(analysis.IsMergeBlock(6));
663
664 // The outer continue target is in the outer loop.
665 EXPECT_EQ(analysis.ContainingConstruct(7), 1);
666 EXPECT_EQ(analysis.ContainingLoop(7), 1);
667 EXPECT_EQ(analysis.MergeBlock(7), 3);
668 EXPECT_EQ(analysis.NestingDepth(7), 1);
669 EXPECT_EQ(analysis.LoopMergeBlock(7), 3);
670 EXPECT_EQ(analysis.LoopNestingDepth(7), 1);
671 EXPECT_EQ(analysis.ContainingSwitch(7), 0);
672 EXPECT_EQ(analysis.SwitchMergeBlock(7), 0);
673 EXPECT_TRUE(analysis.IsContinueBlock(7));
674 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(7));
675 EXPECT_TRUE(analysis.IsInContinueConstruct(7));
676 EXPECT_FALSE(analysis.IsMergeBlock(7));
677 }
678
TEST_F(StructCFGAnalysisTest,KernelTest)679 TEST_F(StructCFGAnalysisTest, KernelTest) {
680 const std::string text = R"(
681 OpCapability Kernel
682 OpMemoryModel Logical GLSL450
683 OpEntryPoint Fragment %main "main"
684 %void = OpTypeVoid
685 %bool = OpTypeBool
686 %bool_undef = OpUndef %bool
687 %void_func = OpTypeFunction %void
688 %main = OpFunction %void None %void_func
689 %1 = OpLabel
690 OpBranchConditional %undef_bool %2 %3
691 %2 = OpLabel
692 OpBranch %3
693 %3 = OpLabel
694 OpReturn
695 OpFunctionEnd
696 )";
697
698 std::unique_ptr<IRContext> context =
699 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
700 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
701
702 StructuredCFGAnalysis analysis(context.get());
703
704 // No structured control flow, so none of the basic block are in any
705 // construct.
706 for (uint32_t i = 1; i <= 3; i++) {
707 EXPECT_EQ(analysis.ContainingConstruct(i), 0);
708 EXPECT_EQ(analysis.ContainingLoop(i), 0);
709 EXPECT_EQ(analysis.MergeBlock(i), 0);
710 EXPECT_EQ(analysis.NestingDepth(i), 0);
711 EXPECT_EQ(analysis.LoopMergeBlock(i), 0);
712 EXPECT_EQ(analysis.LoopNestingDepth(i), 0);
713 EXPECT_EQ(analysis.ContainingSwitch(i), 0);
714 EXPECT_EQ(analysis.SwitchMergeBlock(i), 0);
715 EXPECT_FALSE(analysis.IsContinueBlock(i));
716 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(i));
717 EXPECT_FALSE(analysis.IsInContinueConstruct(i));
718 EXPECT_FALSE(analysis.IsMergeBlock(i));
719 }
720 }
721
TEST_F(StructCFGAnalysisTest,EmptyFunctionTest)722 TEST_F(StructCFGAnalysisTest, EmptyFunctionTest) {
723 const std::string text = R"(
724 OpCapability Shader
725 OpCapability Linkage
726 OpMemoryModel Logical GLSL450
727 OpDecorate %func LinkageAttributes "x" Import
728 %void = OpTypeVoid
729 %void_fn = OpTypeFunction %void
730 %func = OpFunction %void None %void_fn
731 OpFunctionEnd
732 )";
733
734 std::unique_ptr<IRContext> context =
735 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
736 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
737
738 // #2451: This segfaulted on empty functions.
739 StructuredCFGAnalysis analysis(context.get());
740 }
741
TEST_F(StructCFGAnalysisTest,BBInSwitch)742 TEST_F(StructCFGAnalysisTest, BBInSwitch) {
743 const std::string text = R"(
744 OpCapability Shader
745 OpMemoryModel Logical GLSL450
746 OpEntryPoint Fragment %main "main"
747 %void = OpTypeVoid
748 %bool = OpTypeBool
749 %bool_undef = OpUndef %bool
750 %uint = OpTypeInt 32 0
751 %uint_undef = OpUndef %uint
752 %void_func = OpTypeFunction %void
753 %main = OpFunction %void None %void_func
754 %1 = OpLabel
755 OpSelectionMerge %3 None
756 OpSwitch %uint_undef %2 0 %3
757 %2 = OpLabel
758 OpBranch %3
759 %3 = OpLabel
760 OpReturn
761 OpFunctionEnd
762 )";
763
764 std::unique_ptr<IRContext> context =
765 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
766 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
767
768 StructuredCFGAnalysis analysis(context.get());
769
770 // The header is not in the construct.
771 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
772 EXPECT_EQ(analysis.ContainingLoop(1), 0);
773 EXPECT_EQ(analysis.MergeBlock(1), 0);
774 EXPECT_EQ(analysis.NestingDepth(1), 0);
775 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
776 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
777 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
778 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
779 EXPECT_FALSE(analysis.IsContinueBlock(1));
780 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
781 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
782 EXPECT_FALSE(analysis.IsMergeBlock(1));
783
784 // BB2 is in the construct.
785 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
786 EXPECT_EQ(analysis.ContainingLoop(2), 0);
787 EXPECT_EQ(analysis.MergeBlock(2), 3);
788 EXPECT_EQ(analysis.NestingDepth(2), 1);
789 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
790 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
791 EXPECT_EQ(analysis.ContainingSwitch(2), 1);
792 EXPECT_EQ(analysis.SwitchMergeBlock(2), 3);
793 EXPECT_FALSE(analysis.IsContinueBlock(2));
794 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
795 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
796 EXPECT_FALSE(analysis.IsMergeBlock(2));
797
798 // The merge node is not in the construct.
799 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
800 EXPECT_EQ(analysis.ContainingLoop(3), 0);
801 EXPECT_EQ(analysis.MergeBlock(3), 0);
802 EXPECT_EQ(analysis.NestingDepth(3), 0);
803 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
804 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
805 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
806 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
807 EXPECT_FALSE(analysis.IsContinueBlock(3));
808 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
809 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
810 EXPECT_TRUE(analysis.IsMergeBlock(3));
811 }
812
TEST_F(StructCFGAnalysisTest,LoopInSwitch)813 TEST_F(StructCFGAnalysisTest, LoopInSwitch) {
814 const std::string text = R"(
815 OpCapability Shader
816 OpMemoryModel Logical GLSL450
817 OpEntryPoint Fragment %main "main"
818 %void = OpTypeVoid
819 %bool = OpTypeBool
820 %bool_undef = OpUndef %bool
821 %uint = OpTypeInt 32 0
822 %uint_undef = OpUndef %uint
823 %void_func = OpTypeFunction %void
824 %main = OpFunction %void None %void_func
825 %entry_lab = OpLabel
826 OpBranch %1
827 %1 = OpLabel
828 OpSelectionMerge %3 None
829 OpSwitch %uint_undef %2 1 %3
830 %2 = OpLabel
831 OpLoopMerge %4 %5 None
832 OpBranchConditional %undef_bool %4 %6
833 %5 = OpLabel
834 OpBranch %2
835 %6 = OpLabel
836 OpBranch %4
837 %4 = OpLabel
838 OpBranch %3
839 %3 = OpLabel
840 OpReturn
841 OpFunctionEnd
842 )";
843
844 std::unique_ptr<IRContext> context =
845 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
846 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
847
848 StructuredCFGAnalysis analysis(context.get());
849
850 // The selection header is not in either construct.
851 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
852 EXPECT_EQ(analysis.ContainingLoop(1), 0);
853 EXPECT_EQ(analysis.MergeBlock(1), 0);
854 EXPECT_EQ(analysis.NestingDepth(1), 0);
855 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
856 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
857 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
858 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
859 EXPECT_FALSE(analysis.IsContinueBlock(1));
860 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
861 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
862 EXPECT_FALSE(analysis.IsMergeBlock(1));
863
864 // Loop header is in the selection only.
865 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
866 EXPECT_EQ(analysis.ContainingLoop(2), 0);
867 EXPECT_EQ(analysis.MergeBlock(2), 3);
868 EXPECT_EQ(analysis.NestingDepth(2), 1);
869 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
870 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
871 EXPECT_EQ(analysis.ContainingSwitch(2), 1);
872 EXPECT_EQ(analysis.SwitchMergeBlock(2), 3);
873 EXPECT_FALSE(analysis.IsContinueBlock(2));
874 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
875 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
876 EXPECT_FALSE(analysis.IsMergeBlock(2));
877
878 // The selection merge node is not in either construct.
879 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
880 EXPECT_EQ(analysis.ContainingLoop(3), 0);
881 EXPECT_EQ(analysis.MergeBlock(3), 0);
882 EXPECT_EQ(analysis.NestingDepth(3), 0);
883 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
884 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
885 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
886 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
887 EXPECT_FALSE(analysis.IsContinueBlock(3));
888 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
889 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
890 EXPECT_TRUE(analysis.IsMergeBlock(3));
891
892 // The loop merge is in the selection only.
893 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
894 EXPECT_EQ(analysis.ContainingLoop(4), 0);
895 EXPECT_EQ(analysis.MergeBlock(4), 3);
896 EXPECT_EQ(analysis.NestingDepth(4), 1);
897 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
898 EXPECT_EQ(analysis.LoopNestingDepth(4), 0);
899 EXPECT_EQ(analysis.ContainingSwitch(4), 1);
900 EXPECT_EQ(analysis.SwitchMergeBlock(4), 3);
901 EXPECT_FALSE(analysis.IsContinueBlock(4));
902 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(4));
903 EXPECT_FALSE(analysis.IsInContinueConstruct(4));
904 EXPECT_TRUE(analysis.IsMergeBlock(4));
905
906 // The loop continue target is in the loop.
907 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
908 EXPECT_EQ(analysis.ContainingLoop(5), 2);
909 EXPECT_EQ(analysis.MergeBlock(5), 4);
910 EXPECT_EQ(analysis.NestingDepth(5), 2);
911 EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
912 EXPECT_EQ(analysis.LoopNestingDepth(5), 1);
913 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
914 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
915 EXPECT_TRUE(analysis.IsContinueBlock(5));
916 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(5));
917 EXPECT_TRUE(analysis.IsInContinueConstruct(5));
918 EXPECT_FALSE(analysis.IsMergeBlock(5));
919
920 // BB6 is in the loop.
921 EXPECT_EQ(analysis.ContainingConstruct(6), 2);
922 EXPECT_EQ(analysis.ContainingLoop(6), 2);
923 EXPECT_EQ(analysis.MergeBlock(6), 4);
924 EXPECT_EQ(analysis.NestingDepth(6), 2);
925 EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
926 EXPECT_EQ(analysis.LoopNestingDepth(6), 1);
927 EXPECT_EQ(analysis.ContainingSwitch(6), 0);
928 EXPECT_EQ(analysis.SwitchMergeBlock(6), 0);
929 EXPECT_FALSE(analysis.IsContinueBlock(6));
930 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(6));
931 EXPECT_FALSE(analysis.IsInContinueConstruct(6));
932 EXPECT_FALSE(analysis.IsMergeBlock(6));
933 }
934
TEST_F(StructCFGAnalysisTest,SelectionInSwitch)935 TEST_F(StructCFGAnalysisTest, SelectionInSwitch) {
936 const std::string text = R"(
937 OpCapability Shader
938 OpMemoryModel Logical GLSL450
939 OpEntryPoint Fragment %main "main"
940 %void = OpTypeVoid
941 %bool = OpTypeBool
942 %bool_undef = OpUndef %bool
943 %uint = OpTypeInt 32 0
944 %uint_undef = OpUndef %uint
945 %void_func = OpTypeFunction %void
946 %main = OpFunction %void None %void_func
947 %entry_lab = OpLabel
948 OpBranch %1
949 %1 = OpLabel
950 OpSelectionMerge %3 None
951 OpSwitch %uint_undef %2 10 %3
952 %2 = OpLabel
953 OpSelectionMerge %4 None
954 OpBranchConditional %undef_bool %4 %5
955 %5 = OpLabel
956 OpBranch %4
957 %4 = OpLabel
958 OpBranch %3
959 %3 = OpLabel
960 OpReturn
961 OpFunctionEnd
962 )";
963
964 std::unique_ptr<IRContext> context =
965 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
966 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
967
968 StructuredCFGAnalysis analysis(context.get());
969
970 // The outer selection header is not in either construct.
971 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
972 EXPECT_EQ(analysis.ContainingLoop(1), 0);
973 EXPECT_EQ(analysis.MergeBlock(1), 0);
974 EXPECT_EQ(analysis.NestingDepth(1), 0);
975 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
976 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
977 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
978 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
979 EXPECT_FALSE(analysis.IsContinueBlock(1));
980 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
981 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
982 EXPECT_FALSE(analysis.IsMergeBlock(1));
983
984 // The inner header is in the outer selection.
985 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
986 EXPECT_EQ(analysis.ContainingLoop(2), 0);
987 EXPECT_EQ(analysis.MergeBlock(2), 3);
988 EXPECT_EQ(analysis.NestingDepth(2), 1);
989 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
990 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
991 EXPECT_EQ(analysis.ContainingSwitch(2), 1);
992 EXPECT_EQ(analysis.SwitchMergeBlock(2), 3);
993 EXPECT_FALSE(analysis.IsContinueBlock(2));
994 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
995 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
996 EXPECT_FALSE(analysis.IsMergeBlock(2));
997
998 // The outer merge node is not in either construct.
999 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
1000 EXPECT_EQ(analysis.ContainingLoop(3), 0);
1001 EXPECT_EQ(analysis.MergeBlock(3), 0);
1002 EXPECT_EQ(analysis.NestingDepth(3), 0);
1003 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
1004 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
1005 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
1006 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
1007 EXPECT_FALSE(analysis.IsContinueBlock(3));
1008 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
1009 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
1010 EXPECT_TRUE(analysis.IsMergeBlock(3));
1011
1012 // The inner merge is in the outer selection.
1013 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
1014 EXPECT_EQ(analysis.ContainingLoop(4), 0);
1015 EXPECT_EQ(analysis.MergeBlock(4), 3);
1016 EXPECT_EQ(analysis.NestingDepth(4), 1);
1017 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
1018 EXPECT_EQ(analysis.LoopNestingDepth(4), 0);
1019 EXPECT_EQ(analysis.ContainingSwitch(4), 1);
1020 EXPECT_EQ(analysis.SwitchMergeBlock(4), 3);
1021 EXPECT_FALSE(analysis.IsContinueBlock(4));
1022 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(4));
1023 EXPECT_FALSE(analysis.IsInContinueConstruct(4));
1024 EXPECT_TRUE(analysis.IsMergeBlock(4));
1025
1026 // BB5 is in the inner selection.
1027 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
1028 EXPECT_EQ(analysis.ContainingLoop(5), 0);
1029 EXPECT_EQ(analysis.MergeBlock(5), 4);
1030 EXPECT_EQ(analysis.NestingDepth(5), 2);
1031 EXPECT_EQ(analysis.LoopMergeBlock(5), 0);
1032 EXPECT_EQ(analysis.LoopNestingDepth(5), 0);
1033 EXPECT_EQ(analysis.ContainingSwitch(5), 1);
1034 EXPECT_EQ(analysis.SwitchMergeBlock(5), 3);
1035 EXPECT_FALSE(analysis.IsContinueBlock(5));
1036 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(5));
1037 EXPECT_FALSE(analysis.IsInContinueConstruct(5));
1038 EXPECT_FALSE(analysis.IsMergeBlock(5));
1039 }
1040
TEST_F(StructCFGAnalysisTest,SwitchInSelection)1041 TEST_F(StructCFGAnalysisTest, SwitchInSelection) {
1042 const std::string text = R"(
1043 OpCapability Shader
1044 OpMemoryModel Logical GLSL450
1045 OpEntryPoint Fragment %main "main"
1046 %void = OpTypeVoid
1047 %bool = OpTypeBool
1048 %bool_undef = OpUndef %bool
1049 %uint = OpTypeInt 32 0
1050 %uint_undef = OpUndef %uint
1051 %void_func = OpTypeFunction %void
1052 %main = OpFunction %void None %void_func
1053 %entry_lab = OpLabel
1054 OpBranch %1
1055 %1 = OpLabel
1056 OpSelectionMerge %3 None
1057 OpBranchConditional %undef_bool %2 %3
1058 %2 = OpLabel
1059 OpSelectionMerge %4 None
1060 OpSwitch %uint_undef %4 7 %5
1061 %5 = OpLabel
1062 OpBranch %4
1063 %4 = OpLabel
1064 OpBranch %3
1065 %3 = OpLabel
1066 OpReturn
1067 OpFunctionEnd
1068 )";
1069
1070 std::unique_ptr<IRContext> context =
1071 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1072 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1073
1074 StructuredCFGAnalysis analysis(context.get());
1075
1076 // The outer selection header is not in either construct.
1077 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
1078 EXPECT_EQ(analysis.ContainingLoop(1), 0);
1079 EXPECT_EQ(analysis.MergeBlock(1), 0);
1080 EXPECT_EQ(analysis.NestingDepth(1), 0);
1081 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
1082 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
1083 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
1084 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
1085 EXPECT_FALSE(analysis.IsContinueBlock(1));
1086 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
1087 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
1088 EXPECT_FALSE(analysis.IsMergeBlock(1));
1089
1090 // The inner header is in the outer selection.
1091 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
1092 EXPECT_EQ(analysis.ContainingLoop(2), 0);
1093 EXPECT_EQ(analysis.MergeBlock(2), 3);
1094 EXPECT_EQ(analysis.NestingDepth(2), 1);
1095 EXPECT_EQ(analysis.LoopMergeBlock(2), 0);
1096 EXPECT_EQ(analysis.LoopNestingDepth(2), 0);
1097 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
1098 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
1099 EXPECT_FALSE(analysis.IsContinueBlock(2));
1100 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
1101 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
1102 EXPECT_FALSE(analysis.IsMergeBlock(2));
1103
1104 // The outer merge node is not in either construct.
1105 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
1106 EXPECT_EQ(analysis.ContainingLoop(3), 0);
1107 EXPECT_EQ(analysis.MergeBlock(3), 0);
1108 EXPECT_EQ(analysis.NestingDepth(3), 0);
1109 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
1110 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
1111 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
1112 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
1113 EXPECT_FALSE(analysis.IsContinueBlock(3));
1114 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
1115 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
1116 EXPECT_TRUE(analysis.IsMergeBlock(3));
1117
1118 // The inner merge is in the outer selection.
1119 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
1120 EXPECT_EQ(analysis.ContainingLoop(4), 0);
1121 EXPECT_EQ(analysis.MergeBlock(4), 3);
1122 EXPECT_EQ(analysis.NestingDepth(4), 1);
1123 EXPECT_EQ(analysis.LoopMergeBlock(4), 0);
1124 EXPECT_EQ(analysis.LoopNestingDepth(4), 0);
1125 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
1126 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
1127 EXPECT_FALSE(analysis.IsContinueBlock(4));
1128 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(4));
1129 EXPECT_FALSE(analysis.IsInContinueConstruct(4));
1130 EXPECT_TRUE(analysis.IsMergeBlock(4));
1131
1132 // BB5 is in the inner selection.
1133 EXPECT_EQ(analysis.ContainingConstruct(5), 2);
1134 EXPECT_EQ(analysis.ContainingLoop(5), 0);
1135 EXPECT_EQ(analysis.MergeBlock(5), 4);
1136 EXPECT_EQ(analysis.NestingDepth(5), 2);
1137 EXPECT_EQ(analysis.LoopMergeBlock(5), 0);
1138 EXPECT_EQ(analysis.LoopNestingDepth(5), 0);
1139 EXPECT_EQ(analysis.ContainingSwitch(5), 2);
1140 EXPECT_EQ(analysis.SwitchMergeBlock(5), 4);
1141 EXPECT_FALSE(analysis.IsContinueBlock(5));
1142 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(5));
1143 EXPECT_FALSE(analysis.IsInContinueConstruct(5));
1144 EXPECT_FALSE(analysis.IsMergeBlock(5));
1145 }
1146
TEST_F(StructCFGAnalysisTest,SelectionInContinue)1147 TEST_F(StructCFGAnalysisTest, SelectionInContinue) {
1148 const std::string text = R"(
1149 OpCapability Shader
1150 OpMemoryModel Logical GLSL450
1151 OpEntryPoint Fragment %main "main"
1152 %void = OpTypeVoid
1153 %bool = OpTypeBool
1154 %bool_undef = OpUndef %bool
1155 %uint = OpTypeInt 32 0
1156 %uint_undef = OpUndef %uint
1157 %void_func = OpTypeFunction %void
1158 %main = OpFunction %void None %void_func
1159 %entry_lab = OpLabel
1160 OpBranch %1
1161 %1 = OpLabel
1162 OpLoopMerge %3 %4 None
1163 OpBranchConditional %undef_bool %2 %3
1164 %2 = OpLabel
1165 OpBranch %3
1166 %4 = OpLabel
1167 OpSelectionMerge %6 None
1168 OpBranchConditional %undef_bool %5 %6
1169 %5 = OpLabel
1170 OpBranch %6
1171 %6 = OpLabel
1172 OpBranch %1
1173 %3 = OpLabel
1174 OpReturn
1175 OpFunctionEnd
1176 )";
1177
1178 std::unique_ptr<IRContext> context =
1179 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1180 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1181
1182 StructuredCFGAnalysis analysis(context.get());
1183
1184 // The loop header is not in either construct.
1185 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
1186 EXPECT_EQ(analysis.ContainingLoop(1), 0);
1187 EXPECT_EQ(analysis.MergeBlock(1), 0);
1188 EXPECT_EQ(analysis.NestingDepth(1), 0);
1189 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
1190 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
1191 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
1192 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
1193 EXPECT_FALSE(analysis.IsContinueBlock(1));
1194 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
1195 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
1196 EXPECT_FALSE(analysis.IsMergeBlock(1));
1197
1198 // Selection header is in the loop only.
1199 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
1200 EXPECT_EQ(analysis.ContainingLoop(2), 1);
1201 EXPECT_EQ(analysis.MergeBlock(2), 3);
1202 EXPECT_EQ(analysis.NestingDepth(2), 1);
1203 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
1204 EXPECT_EQ(analysis.LoopNestingDepth(2), 1);
1205 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
1206 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
1207 EXPECT_FALSE(analysis.IsContinueBlock(2));
1208 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
1209 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
1210 EXPECT_FALSE(analysis.IsMergeBlock(2));
1211
1212 // The loop merge node is not in either construct.
1213 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
1214 EXPECT_EQ(analysis.ContainingLoop(3), 0);
1215 EXPECT_EQ(analysis.MergeBlock(3), 0);
1216 EXPECT_EQ(analysis.NestingDepth(3), 0);
1217 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
1218 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
1219 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
1220 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
1221 EXPECT_FALSE(analysis.IsContinueBlock(3));
1222 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
1223 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
1224 EXPECT_TRUE(analysis.IsMergeBlock(3));
1225
1226 // The continue block is in the loop only.
1227 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
1228 EXPECT_EQ(analysis.ContainingLoop(4), 1);
1229 EXPECT_EQ(analysis.MergeBlock(4), 3);
1230 EXPECT_EQ(analysis.NestingDepth(4), 1);
1231 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
1232 EXPECT_EQ(analysis.LoopNestingDepth(4), 1);
1233 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
1234 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
1235 EXPECT_TRUE(analysis.IsContinueBlock(4));
1236 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(4));
1237 EXPECT_TRUE(analysis.IsInContinueConstruct(4));
1238 EXPECT_FALSE(analysis.IsMergeBlock(4));
1239
1240 // BB5 is in the selection and the continue for the loop.
1241 EXPECT_EQ(analysis.ContainingConstruct(5), 4);
1242 EXPECT_EQ(analysis.ContainingLoop(5), 1);
1243 EXPECT_EQ(analysis.MergeBlock(5), 6);
1244 EXPECT_EQ(analysis.NestingDepth(5), 2);
1245 EXPECT_EQ(analysis.LoopMergeBlock(5), 3);
1246 EXPECT_EQ(analysis.LoopNestingDepth(5), 1);
1247 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
1248 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
1249 EXPECT_FALSE(analysis.IsContinueBlock(5));
1250 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(5));
1251 EXPECT_TRUE(analysis.IsInContinueConstruct(5));
1252 EXPECT_FALSE(analysis.IsMergeBlock(5));
1253
1254 // BB5 is in the continue for the loop.
1255 EXPECT_EQ(analysis.ContainingConstruct(6), 1);
1256 EXPECT_EQ(analysis.ContainingLoop(6), 1);
1257 EXPECT_EQ(analysis.MergeBlock(6), 3);
1258 EXPECT_EQ(analysis.NestingDepth(6), 1);
1259 EXPECT_EQ(analysis.LoopMergeBlock(6), 3);
1260 EXPECT_EQ(analysis.LoopNestingDepth(6), 1);
1261 EXPECT_EQ(analysis.ContainingSwitch(6), 0);
1262 EXPECT_EQ(analysis.SwitchMergeBlock(6), 0);
1263 EXPECT_FALSE(analysis.IsContinueBlock(6));
1264 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(6));
1265 EXPECT_TRUE(analysis.IsInContinueConstruct(6));
1266 EXPECT_TRUE(analysis.IsMergeBlock(6));
1267 }
1268
TEST_F(StructCFGAnalysisTest,LoopInContinue)1269 TEST_F(StructCFGAnalysisTest, LoopInContinue) {
1270 const std::string text = R"(
1271 OpCapability Shader
1272 OpMemoryModel Logical GLSL450
1273 OpEntryPoint Fragment %main "main"
1274 %void = OpTypeVoid
1275 %bool = OpTypeBool
1276 %bool_undef = OpUndef %bool
1277 %uint = OpTypeInt 32 0
1278 %uint_undef = OpUndef %uint
1279 %void_func = OpTypeFunction %void
1280 %main = OpFunction %void None %void_func
1281 %entry_lab = OpLabel
1282 OpBranch %1
1283 %1 = OpLabel
1284 OpLoopMerge %3 %7 None
1285 OpBranchConditional %undef_bool %2 %3
1286 %2 = OpLabel
1287 OpBranchConditional %undef_bool %3 %7
1288 %7 = OpLabel
1289 OpLoopMerge %4 %5 None
1290 OpBranchConditional %undef_bool %4 %6
1291 %5 = OpLabel
1292 OpBranch %7
1293 %6 = OpLabel
1294 OpBranch %4
1295 %4 = OpLabel
1296 OpBranch %1
1297 %3 = OpLabel
1298 OpReturn
1299 OpFunctionEnd
1300 )";
1301
1302 std::unique_ptr<IRContext> context =
1303 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1304 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1305
1306 StructuredCFGAnalysis analysis(context.get());
1307
1308 // The outer loop header is not in either construct.
1309 EXPECT_EQ(analysis.ContainingConstruct(1), 0);
1310 EXPECT_EQ(analysis.ContainingLoop(1), 0);
1311 EXPECT_EQ(analysis.MergeBlock(1), 0);
1312 EXPECT_EQ(analysis.NestingDepth(1), 0);
1313 EXPECT_EQ(analysis.LoopMergeBlock(1), 0);
1314 EXPECT_EQ(analysis.LoopNestingDepth(1), 0);
1315 EXPECT_EQ(analysis.ContainingSwitch(1), 0);
1316 EXPECT_EQ(analysis.SwitchMergeBlock(1), 0);
1317 EXPECT_FALSE(analysis.IsContinueBlock(1));
1318 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(1));
1319 EXPECT_FALSE(analysis.IsInContinueConstruct(1));
1320 EXPECT_FALSE(analysis.IsMergeBlock(1));
1321
1322 // BB2 is a regular block in the inner loop.
1323 EXPECT_EQ(analysis.ContainingConstruct(2), 1);
1324 EXPECT_EQ(analysis.ContainingLoop(2), 1);
1325 EXPECT_EQ(analysis.MergeBlock(2), 3);
1326 EXPECT_EQ(analysis.NestingDepth(2), 1);
1327 EXPECT_EQ(analysis.LoopMergeBlock(2), 3);
1328 EXPECT_EQ(analysis.LoopNestingDepth(2), 1);
1329 EXPECT_EQ(analysis.ContainingSwitch(2), 0);
1330 EXPECT_EQ(analysis.SwitchMergeBlock(2), 0);
1331 EXPECT_FALSE(analysis.IsContinueBlock(2));
1332 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(2));
1333 EXPECT_FALSE(analysis.IsInContinueConstruct(2));
1334 EXPECT_FALSE(analysis.IsMergeBlock(2));
1335
1336 // The outer merge node is not in either construct.
1337 EXPECT_EQ(analysis.ContainingConstruct(3), 0);
1338 EXPECT_EQ(analysis.ContainingLoop(3), 0);
1339 EXPECT_EQ(analysis.MergeBlock(3), 0);
1340 EXPECT_EQ(analysis.NestingDepth(3), 0);
1341 EXPECT_EQ(analysis.LoopMergeBlock(3), 0);
1342 EXPECT_EQ(analysis.LoopNestingDepth(3), 0);
1343 EXPECT_EQ(analysis.ContainingSwitch(3), 0);
1344 EXPECT_EQ(analysis.SwitchMergeBlock(3), 0);
1345 EXPECT_FALSE(analysis.IsContinueBlock(3));
1346 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(3));
1347 EXPECT_FALSE(analysis.IsInContinueConstruct(3));
1348 EXPECT_TRUE(analysis.IsMergeBlock(3));
1349
1350 // The inner merge is in the continue of the outer loop.
1351 EXPECT_EQ(analysis.ContainingConstruct(4), 1);
1352 EXPECT_EQ(analysis.ContainingLoop(4), 1);
1353 EXPECT_EQ(analysis.MergeBlock(4), 3);
1354 EXPECT_EQ(analysis.NestingDepth(4), 1);
1355 EXPECT_EQ(analysis.LoopMergeBlock(4), 3);
1356 EXPECT_EQ(analysis.LoopNestingDepth(4), 1);
1357 EXPECT_EQ(analysis.ContainingSwitch(4), 0);
1358 EXPECT_EQ(analysis.SwitchMergeBlock(4), 0);
1359 EXPECT_FALSE(analysis.IsContinueBlock(4));
1360 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(4));
1361 EXPECT_TRUE(analysis.IsInContinueConstruct(4));
1362 EXPECT_TRUE(analysis.IsMergeBlock(4));
1363
1364 // The inner continue target is in the inner loop.
1365 EXPECT_EQ(analysis.ContainingConstruct(5), 7);
1366 EXPECT_EQ(analysis.ContainingLoop(5), 7);
1367 EXPECT_EQ(analysis.MergeBlock(5), 4);
1368 EXPECT_EQ(analysis.NestingDepth(5), 2);
1369 EXPECT_EQ(analysis.LoopMergeBlock(5), 4);
1370 EXPECT_EQ(analysis.LoopNestingDepth(5), 2);
1371 EXPECT_EQ(analysis.ContainingSwitch(5), 0);
1372 EXPECT_EQ(analysis.SwitchMergeBlock(5), 0);
1373 EXPECT_TRUE(analysis.IsContinueBlock(5));
1374 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(5));
1375 EXPECT_TRUE(analysis.IsInContinueConstruct(5));
1376 EXPECT_FALSE(analysis.IsMergeBlock(5));
1377
1378 // BB6 is a regular block in the inner loop.
1379 EXPECT_EQ(analysis.ContainingConstruct(6), 7);
1380 EXPECT_EQ(analysis.ContainingLoop(6), 7);
1381 EXPECT_EQ(analysis.MergeBlock(6), 4);
1382 EXPECT_EQ(analysis.NestingDepth(6), 2);
1383 EXPECT_EQ(analysis.LoopMergeBlock(6), 4);
1384 EXPECT_EQ(analysis.LoopNestingDepth(6), 2);
1385 EXPECT_EQ(analysis.ContainingSwitch(6), 0);
1386 EXPECT_EQ(analysis.SwitchMergeBlock(6), 0);
1387 EXPECT_FALSE(analysis.IsContinueBlock(6));
1388 EXPECT_FALSE(analysis.IsInContainingLoopsContinueConstruct(6));
1389 EXPECT_TRUE(analysis.IsInContinueConstruct(6));
1390 EXPECT_FALSE(analysis.IsMergeBlock(6));
1391
1392 // The outer continue target is in the outer loop.
1393 EXPECT_EQ(analysis.ContainingConstruct(7), 1);
1394 EXPECT_EQ(analysis.ContainingLoop(7), 1);
1395 EXPECT_EQ(analysis.MergeBlock(7), 3);
1396 EXPECT_EQ(analysis.NestingDepth(7), 1);
1397 EXPECT_EQ(analysis.LoopMergeBlock(7), 3);
1398 EXPECT_EQ(analysis.LoopNestingDepth(7), 1);
1399 EXPECT_EQ(analysis.ContainingSwitch(7), 0);
1400 EXPECT_EQ(analysis.SwitchMergeBlock(7), 0);
1401 EXPECT_TRUE(analysis.IsContinueBlock(7));
1402 EXPECT_TRUE(analysis.IsInContainingLoopsContinueConstruct(7));
1403 EXPECT_TRUE(analysis.IsInContinueConstruct(7));
1404 EXPECT_FALSE(analysis.IsMergeBlock(7));
1405 }
1406
TEST_F(StructCFGAnalysisTest,FuncCallInContinueDirect)1407 TEST_F(StructCFGAnalysisTest, FuncCallInContinueDirect) {
1408 const std::string text = R"(
1409 OpCapability Shader
1410 OpMemoryModel Logical GLSL450
1411 OpEntryPoint Fragment %1 "main"
1412 %void = OpTypeVoid
1413 %bool = OpTypeBool
1414 %4 = OpUndef %bool
1415 %uint = OpTypeInt 32 0
1416 %6 = OpUndef %uint
1417 %7 = OpTypeFunction %void
1418 %1 = OpFunction %void None %7
1419 %8 = OpLabel
1420 OpBranch %9
1421 %9 = OpLabel
1422 OpLoopMerge %10 %11 None
1423 OpBranchConditional %12 %10 %11
1424 %11 = OpLabel
1425 %13 = OpFunctionCall %void %14
1426 OpBranch %9
1427 %10 = OpLabel
1428 %15 = OpFunctionCall %void %16
1429 OpReturn
1430 OpFunctionEnd
1431 %14 = OpFunction %void None %7
1432 %17 = OpLabel
1433 OpReturn
1434 OpFunctionEnd
1435 %16 = OpFunction %void None %7
1436 %18 = OpLabel
1437 OpReturn
1438 OpFunctionEnd
1439 )";
1440
1441 std::unique_ptr<IRContext> context =
1442 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1443 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1444
1445 StructuredCFGAnalysis analysis(context.get());
1446
1447 auto c = analysis.FindFuncsCalledFromContinue();
1448 EXPECT_THAT(c, UnorderedElementsAre(14u));
1449 }
1450
TEST_F(StructCFGAnalysisTest,FuncCallInContinueIndirect)1451 TEST_F(StructCFGAnalysisTest, FuncCallInContinueIndirect) {
1452 const std::string text = R"(
1453 OpCapability Shader
1454 OpMemoryModel Logical GLSL450
1455 OpEntryPoint Fragment %1 "main"
1456 %void = OpTypeVoid
1457 %bool = OpTypeBool
1458 %4 = OpUndef %bool
1459 %uint = OpTypeInt 32 0
1460 %6 = OpUndef %uint
1461 %7 = OpTypeFunction %void
1462 %1 = OpFunction %void None %7
1463 %8 = OpLabel
1464 OpBranch %9
1465 %9 = OpLabel
1466 OpLoopMerge %10 %11 None
1467 OpBranchConditional %12 %10 %11
1468 %11 = OpLabel
1469 %13 = OpFunctionCall %void %14
1470 OpBranch %9
1471 %10 = OpLabel
1472 %15 = OpFunctionCall %void %16
1473 OpReturn
1474 OpFunctionEnd
1475 %14 = OpFunction %void None %7
1476 %17 = OpLabel
1477 %19 = OpFunctionCall %void %16
1478 OpReturn
1479 OpFunctionEnd
1480 %16 = OpFunction %void None %7
1481 %18 = OpLabel
1482 %20 = OpFunctionCall %void %21
1483 OpReturn
1484 OpFunctionEnd
1485 %21 = OpFunction %void None %7
1486 %22 = OpLabel
1487 OpReturn
1488 OpFunctionEnd
1489 )";
1490
1491 std::unique_ptr<IRContext> context =
1492 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1493 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1494
1495 StructuredCFGAnalysis analysis(context.get());
1496
1497 auto c = analysis.FindFuncsCalledFromContinue();
1498 EXPECT_THAT(c, UnorderedElementsAre(14u, 16u, 21u));
1499 }
1500
TEST_F(StructCFGAnalysisTest,SingleBlockLoop)1501 TEST_F(StructCFGAnalysisTest, SingleBlockLoop) {
1502 const std::string text = R"(
1503 OpCapability Shader
1504 OpCapability Linkage
1505 OpMemoryModel Logical GLSL450
1506 %void = OpTypeVoid
1507 %bool = OpTypeBool
1508 %undef = OpUndef %bool
1509 %void_fn = OpTypeFunction %void
1510 %main = OpFunction %void None %void_fn
1511 %2 = OpLabel
1512 OpBranch %3
1513 %3 = OpLabel
1514 OpLoopMerge %4 %3 None
1515 OpBranchConditional %undef %3 %4
1516 %4 = OpLabel
1517 OpReturn
1518 OpFunctionEnd
1519 )";
1520
1521 std::unique_ptr<IRContext> context =
1522 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1523 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1524
1525 StructuredCFGAnalysis analysis(context.get());
1526
1527 EXPECT_TRUE(analysis.IsInContinueConstruct(3));
1528 }
1529 } // namespace
1530 } // namespace opt
1531 } // namespace spvtools
1532