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
23namespace spvtools {
24namespace opt {
25namespace {
26
27using StructCFGAnalysisTest = PassTest<::testing::Test>;
28using ::testing::UnorderedElementsAre;
29
30TEST_F(StructCFGAnalysisTest, BBInSelection) {
31  const std::string text = R"(
32OpCapability Shader
33OpMemoryModel Logical GLSL450
34OpEntryPoint 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
43OpSelectionMerge %3 None
44OpBranchConditional %undef_bool %2 %3
45%2 = OpLabel
46OpBranch %3
47%3 = OpLabel
48OpReturn
49OpFunctionEnd
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
101TEST_F(StructCFGAnalysisTest, BBInLoop) {
102  const std::string text = R"(
103OpCapability Shader
104OpMemoryModel Logical GLSL450
105OpEntryPoint 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
114OpBranch %1
115%1 = OpLabel
116OpLoopMerge %3 %4 None
117OpBranchConditional %undef_bool %2 %3
118%2 = OpLabel
119OpBranch %3
120%4 = OpLabel
121OpBranch %1
122%3 = OpLabel
123OpReturn
124OpFunctionEnd
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
190TEST_F(StructCFGAnalysisTest, SelectionInLoop) {
191  const std::string text = R"(
192OpCapability Shader
193OpMemoryModel Logical GLSL450
194OpEntryPoint 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
203OpBranch %1
204%1 = OpLabel
205OpLoopMerge %3 %4 None
206OpBranchConditional %undef_bool %2 %3
207%2 = OpLabel
208OpSelectionMerge %6 None
209OpBranchConditional %undef_bool %5 %6
210%5 = OpLabel
211OpBranch %6
212%6 = OpLabel
213OpBranch %3
214%4 = OpLabel
215OpBranch %1
216%3 = OpLabel
217OpReturn
218OpFunctionEnd
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
312TEST_F(StructCFGAnalysisTest, LoopInSelection) {
313  const std::string text = R"(
314OpCapability Shader
315OpMemoryModel Logical GLSL450
316OpEntryPoint 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
325OpBranch %1
326%1 = OpLabel
327OpSelectionMerge %3 None
328OpBranchConditional %undef_bool %2 %3
329%2 = OpLabel
330OpLoopMerge %4 %5 None
331OpBranchConditional %undef_bool %4 %6
332%5 = OpLabel
333OpBranch %2
334%6 = OpLabel
335OpBranch %4
336%4 = OpLabel
337OpBranch %3
338%3 = OpLabel
339OpReturn
340OpFunctionEnd
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
434TEST_F(StructCFGAnalysisTest, SelectionInSelection) {
435  const std::string text = R"(
436OpCapability Shader
437OpMemoryModel Logical GLSL450
438OpEntryPoint 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
447OpBranch %1
448%1 = OpLabel
449OpSelectionMerge %3 None
450OpBranchConditional %undef_bool %2 %3
451%2 = OpLabel
452OpSelectionMerge %4 None
453OpBranchConditional %undef_bool %4 %5
454%5 = OpLabel
455OpBranch %4
456%4 = OpLabel
457OpBranch %3
458%3 = OpLabel
459OpReturn
460OpFunctionEnd
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
540TEST_F(StructCFGAnalysisTest, LoopInLoop) {
541  const std::string text = R"(
542OpCapability Shader
543OpMemoryModel Logical GLSL450
544OpEntryPoint 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
553OpBranch %1
554%1 = OpLabel
555OpLoopMerge %3 %7 None
556OpBranchConditional %undef_bool %2 %3
557%2 = OpLabel
558OpLoopMerge %4 %5 None
559OpBranchConditional %undef_bool %4 %6
560%5 = OpLabel
561OpBranch %2
562%6 = OpLabel
563OpBranch %4
564%4 = OpLabel
565OpBranch %3
566%7 = OpLabel
567OpBranch %1
568%3 = OpLabel
569OpReturn
570OpFunctionEnd
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
678TEST_F(StructCFGAnalysisTest, KernelTest) {
679  const std::string text = R"(
680OpCapability Kernel
681OpMemoryModel Logical GLSL450
682OpEntryPoint 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
689OpBranchConditional %undef_bool %2 %3
690%2 = OpLabel
691OpBranch %3
692%3 = OpLabel
693OpReturn
694OpFunctionEnd
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
721TEST_F(StructCFGAnalysisTest, EmptyFunctionTest) {
722  const std::string text = R"(
723OpCapability Shader
724OpCapability Linkage
725OpMemoryModel Logical GLSL450
726OpDecorate %func LinkageAttributes "x" Import
727%void = OpTypeVoid
728%void_fn = OpTypeFunction %void
729%func = OpFunction %void None %void_fn
730OpFunctionEnd
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
741TEST_F(StructCFGAnalysisTest, BBInSwitch) {
742  const std::string text = R"(
743OpCapability Shader
744OpMemoryModel Logical GLSL450
745OpEntryPoint 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
754OpSelectionMerge %3 None
755OpSwitch %uint_undef %2 0 %3
756%2 = OpLabel
757OpBranch %3
758%3 = OpLabel
759OpReturn
760OpFunctionEnd
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
812TEST_F(StructCFGAnalysisTest, LoopInSwitch) {
813  const std::string text = R"(
814OpCapability Shader
815OpMemoryModel Logical GLSL450
816OpEntryPoint 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
825OpBranch %1
826%1 = OpLabel
827OpSelectionMerge %3 None
828OpSwitch %uint_undef %2 1 %3
829%2 = OpLabel
830OpLoopMerge %4 %5 None
831OpBranchConditional %undef_bool %4 %6
832%5 = OpLabel
833OpBranch %2
834%6 = OpLabel
835OpBranch %4
836%4 = OpLabel
837OpBranch %3
838%3 = OpLabel
839OpReturn
840OpFunctionEnd
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
934TEST_F(StructCFGAnalysisTest, SelectionInSwitch) {
935  const std::string text = R"(
936OpCapability Shader
937OpMemoryModel Logical GLSL450
938OpEntryPoint 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
947OpBranch %1
948%1 = OpLabel
949OpSelectionMerge %3 None
950OpSwitch %uint_undef %2 10 %3
951%2 = OpLabel
952OpSelectionMerge %4 None
953OpBranchConditional %undef_bool %4 %5
954%5 = OpLabel
955OpBranch %4
956%4 = OpLabel
957OpBranch %3
958%3 = OpLabel
959OpReturn
960OpFunctionEnd
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
1040TEST_F(StructCFGAnalysisTest, SwitchInSelection) {
1041  const std::string text = R"(
1042OpCapability Shader
1043OpMemoryModel Logical GLSL450
1044OpEntryPoint 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
1053OpBranch %1
1054%1 = OpLabel
1055OpSelectionMerge %3 None
1056OpBranchConditional %undef_bool %2 %3
1057%2 = OpLabel
1058OpSelectionMerge %4 None
1059OpSwitch %uint_undef %4 7 %5
1060%5 = OpLabel
1061OpBranch %4
1062%4 = OpLabel
1063OpBranch %3
1064%3 = OpLabel
1065OpReturn
1066OpFunctionEnd
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
1146TEST_F(StructCFGAnalysisTest, SelectionInContinue) {
1147  const std::string text = R"(
1148OpCapability Shader
1149OpMemoryModel Logical GLSL450
1150OpEntryPoint 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
1159OpBranch %1
1160%1 = OpLabel
1161OpLoopMerge %3 %4 None
1162OpBranchConditional %undef_bool %2 %3
1163%2 = OpLabel
1164OpBranch %3
1165%4 = OpLabel
1166OpSelectionMerge %6 None
1167OpBranchConditional %undef_bool %5 %6
1168%5 = OpLabel
1169OpBranch %6
1170%6 = OpLabel
1171OpBranch %1
1172%3 = OpLabel
1173OpReturn
1174OpFunctionEnd
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
1268TEST_F(StructCFGAnalysisTest, LoopInContinue) {
1269  const std::string text = R"(
1270OpCapability Shader
1271OpMemoryModel Logical GLSL450
1272OpEntryPoint 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
1281OpBranch %1
1282%1 = OpLabel
1283OpLoopMerge %3 %7 None
1284OpBranchConditional %undef_bool %2 %3
1285%2 = OpLabel
1286OpBranchConditional %undef_bool %3 %7
1287%7 = OpLabel
1288OpLoopMerge %4 %5 None
1289OpBranchConditional %undef_bool %4 %6
1290%5 = OpLabel
1291OpBranch %7
1292%6 = OpLabel
1293OpBranch %4
1294%4 = OpLabel
1295OpBranch %1
1296%3 = OpLabel
1297OpReturn
1298OpFunctionEnd
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
1406TEST_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
1450TEST_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
1500TEST_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