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