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