1 // Copyright (c) 2017 Google Inc.
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 <array>
16 #include <memory>
17 #include <string>
18 #include <vector>
19 
20 #include "gmock/gmock.h"
21 #include "source/opt/dominator_analysis.h"
22 #include "source/opt/iterator.h"
23 #include "source/opt/pass.h"
24 #include "test/opt/assembly_builder.h"
25 #include "test/opt/function_utils.h"
26 #include "test/opt/pass_fixture.h"
27 #include "test/opt/pass_utils.h"
28 
29 namespace spvtools {
30 namespace opt {
31 namespace {
32 
33 using ::testing::UnorderedElementsAre;
34 using PassClassTest = PassTest<::testing::Test>;
35 
36 // Check that x dominates y, and
37 //   if x != y then
38 //      x strictly dominates y and
39 //      y does not dominate x and
40 //      y does not strictly dominate x
41 //   if x == x then
42 //      x does not strictly dominate itself
check_dominance(const DominatorAnalysisBase & dom_tree,const Function * fn,uint32_t x,uint32_t y)43 void check_dominance(const DominatorAnalysisBase& dom_tree, const Function* fn,
44                      uint32_t x, uint32_t y) {
45   SCOPED_TRACE("Check dominance properties for Basic Block " +
46                std::to_string(x) + " and " + std::to_string(y));
47   EXPECT_TRUE(dom_tree.Dominates(spvtest::GetBasicBlock(fn, x),
48                                  spvtest::GetBasicBlock(fn, y)));
49   EXPECT_TRUE(dom_tree.Dominates(x, y));
50   if (x == y) {
51     EXPECT_FALSE(dom_tree.StrictlyDominates(x, x));
52   } else {
53     EXPECT_TRUE(dom_tree.StrictlyDominates(x, y));
54     EXPECT_FALSE(dom_tree.Dominates(y, x));
55     EXPECT_FALSE(dom_tree.StrictlyDominates(y, x));
56   }
57 }
58 
59 // Check that x does not dominates y and vice versa
check_no_dominance(const DominatorAnalysisBase & dom_tree,const Function * fn,uint32_t x,uint32_t y)60 void check_no_dominance(const DominatorAnalysisBase& dom_tree,
61                         const Function* fn, uint32_t x, uint32_t y) {
62   SCOPED_TRACE("Check no domination for Basic Block " + std::to_string(x) +
63                " and " + std::to_string(y));
64   EXPECT_FALSE(dom_tree.Dominates(spvtest::GetBasicBlock(fn, x),
65                                   spvtest::GetBasicBlock(fn, y)));
66   EXPECT_FALSE(dom_tree.Dominates(x, y));
67   EXPECT_FALSE(dom_tree.StrictlyDominates(spvtest::GetBasicBlock(fn, x),
68                                           spvtest::GetBasicBlock(fn, y)));
69   EXPECT_FALSE(dom_tree.StrictlyDominates(x, y));
70 
71   EXPECT_FALSE(dom_tree.Dominates(spvtest::GetBasicBlock(fn, y),
72                                   spvtest::GetBasicBlock(fn, x)));
73   EXPECT_FALSE(dom_tree.Dominates(y, x));
74   EXPECT_FALSE(dom_tree.StrictlyDominates(spvtest::GetBasicBlock(fn, y),
75                                           spvtest::GetBasicBlock(fn, x)));
76   EXPECT_FALSE(dom_tree.StrictlyDominates(y, x));
77 }
78 
TEST_F(PassClassTest,DominatorSimpleCFG)79 TEST_F(PassClassTest, DominatorSimpleCFG) {
80   const std::string text = R"(
81                OpCapability Addresses
82                OpCapability Kernel
83                OpMemoryModel Physical64 OpenCL
84                OpEntryPoint Kernel %1 "main"
85           %2 = OpTypeVoid
86           %3 = OpTypeFunction %2
87           %4 = OpTypeBool
88           %5 = OpTypeInt 32 0
89           %6 = OpConstant %5 0
90           %7 = OpConstantFalse %4
91           %8 = OpConstantTrue %4
92           %9 = OpConstant %5 1
93           %1 = OpFunction %2 None %3
94          %10 = OpLabel
95                OpBranch %11
96          %11 = OpLabel
97                OpSwitch %6 %12 1 %13
98          %12 = OpLabel
99                OpBranch %14
100          %13 = OpLabel
101                OpBranch %14
102          %14 = OpLabel
103                OpBranchConditional %8 %11 %15
104          %15 = OpLabel
105                OpReturn
106                OpFunctionEnd
107 )";
108   // clang-format on
109   std::unique_ptr<IRContext> context =
110       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
111                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
112   Module* module = context->module();
113   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
114                              << text << std::endl;
115   const Function* fn = spvtest::GetFunction(module, 1);
116   const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
117   EXPECT_EQ(entry, fn->entry().get())
118       << "The entry node is not the expected one";
119 
120   // Test normal dominator tree
121   {
122     DominatorAnalysis dom_tree;
123     const CFG& cfg = *context->cfg();
124     dom_tree.InitializeTree(cfg, fn);
125 
126     // Inspect the actual tree
127     DominatorTree& tree = dom_tree.GetDomTree();
128     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
129     EXPECT_TRUE(
130         dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));
131 
132     // (strict) dominance checks
133     for (uint32_t id : {10, 11, 12, 13, 14, 15})
134       check_dominance(dom_tree, fn, id, id);
135 
136     check_dominance(dom_tree, fn, 10, 11);
137     check_dominance(dom_tree, fn, 10, 12);
138     check_dominance(dom_tree, fn, 10, 13);
139     check_dominance(dom_tree, fn, 10, 14);
140     check_dominance(dom_tree, fn, 10, 15);
141 
142     check_dominance(dom_tree, fn, 11, 12);
143     check_dominance(dom_tree, fn, 11, 13);
144     check_dominance(dom_tree, fn, 11, 14);
145     check_dominance(dom_tree, fn, 11, 15);
146 
147     check_dominance(dom_tree, fn, 14, 15);
148 
149     check_no_dominance(dom_tree, fn, 12, 13);
150     check_no_dominance(dom_tree, fn, 12, 14);
151     check_no_dominance(dom_tree, fn, 13, 14);
152 
153     // check with some invalid inputs
154     EXPECT_FALSE(dom_tree.Dominates(nullptr, entry));
155     EXPECT_FALSE(dom_tree.Dominates(entry, nullptr));
156     EXPECT_FALSE(dom_tree.Dominates(static_cast<BasicBlock*>(nullptr),
157                                     static_cast<BasicBlock*>(nullptr)));
158     EXPECT_FALSE(dom_tree.Dominates(10, 1));
159     EXPECT_FALSE(dom_tree.Dominates(1, 10));
160     EXPECT_FALSE(dom_tree.Dominates(1, 1));
161 
162     EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, entry));
163     EXPECT_FALSE(dom_tree.StrictlyDominates(entry, nullptr));
164     EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, nullptr));
165     EXPECT_FALSE(dom_tree.StrictlyDominates(10, 1));
166     EXPECT_FALSE(dom_tree.StrictlyDominates(1, 10));
167     EXPECT_FALSE(dom_tree.StrictlyDominates(1, 1));
168 
169     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
170     EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
171     EXPECT_EQ(dom_tree.ImmediateDominator(nullptr), nullptr);
172 
173     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
174               spvtest::GetBasicBlock(fn, 10));
175     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
176               spvtest::GetBasicBlock(fn, 11));
177     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
178               spvtest::GetBasicBlock(fn, 11));
179     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
180               spvtest::GetBasicBlock(fn, 11));
181     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
182               spvtest::GetBasicBlock(fn, 14));
183   }
184 
185   // Test post dominator tree
186   {
187     PostDominatorAnalysis dom_tree;
188     const CFG& cfg = *context->cfg();
189     dom_tree.InitializeTree(cfg, fn);
190 
191     // Inspect the actual tree
192     DominatorTree& tree = dom_tree.GetDomTree();
193     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
194     EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 15));
195 
196     // (strict) dominance checks
197     for (uint32_t id : {10, 11, 12, 13, 14, 15})
198       check_dominance(dom_tree, fn, id, id);
199 
200     check_dominance(dom_tree, fn, 14, 10);
201     check_dominance(dom_tree, fn, 14, 11);
202     check_dominance(dom_tree, fn, 14, 12);
203     check_dominance(dom_tree, fn, 14, 13);
204 
205     check_dominance(dom_tree, fn, 15, 10);
206     check_dominance(dom_tree, fn, 15, 11);
207     check_dominance(dom_tree, fn, 15, 12);
208     check_dominance(dom_tree, fn, 15, 13);
209     check_dominance(dom_tree, fn, 15, 14);
210 
211     check_no_dominance(dom_tree, fn, 13, 12);
212     check_no_dominance(dom_tree, fn, 12, 11);
213     check_no_dominance(dom_tree, fn, 13, 11);
214 
215     // check with some invalid inputs
216     EXPECT_FALSE(dom_tree.Dominates(nullptr, entry));
217     EXPECT_FALSE(dom_tree.Dominates(entry, nullptr));
218     EXPECT_FALSE(dom_tree.Dominates(static_cast<BasicBlock*>(nullptr),
219                                     static_cast<BasicBlock*>(nullptr)));
220     EXPECT_FALSE(dom_tree.Dominates(10, 1));
221     EXPECT_FALSE(dom_tree.Dominates(1, 10));
222     EXPECT_FALSE(dom_tree.Dominates(1, 1));
223 
224     EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, entry));
225     EXPECT_FALSE(dom_tree.StrictlyDominates(entry, nullptr));
226     EXPECT_FALSE(dom_tree.StrictlyDominates(nullptr, nullptr));
227     EXPECT_FALSE(dom_tree.StrictlyDominates(10, 1));
228     EXPECT_FALSE(dom_tree.StrictlyDominates(1, 10));
229     EXPECT_FALSE(dom_tree.StrictlyDominates(1, 1));
230 
231     EXPECT_EQ(dom_tree.ImmediateDominator(nullptr), nullptr);
232 
233     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
234               spvtest::GetBasicBlock(fn, 14));
235     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
236               spvtest::GetBasicBlock(fn, 14));
237     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
238               spvtest::GetBasicBlock(fn, 14));
239     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
240               spvtest::GetBasicBlock(fn, 15));
241 
242     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
243               cfg.pseudo_exit_block());
244 
245     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
246   }
247 }
248 
TEST_F(PassClassTest,DominatorIrreducibleCFG)249 TEST_F(PassClassTest, DominatorIrreducibleCFG) {
250   const std::string text = R"(
251                OpCapability Addresses
252                OpCapability Kernel
253                OpMemoryModel Physical64 OpenCL
254                OpEntryPoint Kernel %1 "main"
255           %2 = OpTypeVoid
256           %3 = OpTypeFunction %2
257           %4 = OpTypeBool
258           %5 = OpTypeInt 32 0
259           %6 = OpConstantFalse %4
260           %7 = OpConstantTrue %4
261           %1 = OpFunction %2 None %3
262           %8 = OpLabel
263                OpBranch %9
264           %9 = OpLabel
265                OpBranchConditional %7 %10 %11
266          %10 = OpLabel
267                OpBranch %11
268          %11 = OpLabel
269                OpBranchConditional %7 %10 %12
270          %12 = OpLabel
271                OpReturn
272                OpFunctionEnd
273 )";
274   // clang-format on
275   std::unique_ptr<IRContext> context =
276       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
277                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
278   Module* module = context->module();
279   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
280                              << text << std::endl;
281   const Function* fn = spvtest::GetFunction(module, 1);
282 
283   const BasicBlock* entry = spvtest::GetBasicBlock(fn, 8);
284   EXPECT_EQ(entry, fn->entry().get())
285       << "The entry node is not the expected one";
286 
287   // Check normal dominator tree
288   {
289     DominatorAnalysis dom_tree;
290     const CFG& cfg = *context->cfg();
291     dom_tree.InitializeTree(cfg, fn);
292 
293     // Inspect the actual tree
294     DominatorTree& tree = dom_tree.GetDomTree();
295     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
296     EXPECT_TRUE(
297         dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));
298 
299     // (strict) dominance checks
300     for (uint32_t id : {8, 9, 10, 11, 12})
301       check_dominance(dom_tree, fn, id, id);
302 
303     check_dominance(dom_tree, fn, 8, 9);
304     check_dominance(dom_tree, fn, 8, 10);
305     check_dominance(dom_tree, fn, 8, 11);
306     check_dominance(dom_tree, fn, 8, 12);
307 
308     check_dominance(dom_tree, fn, 9, 10);
309     check_dominance(dom_tree, fn, 9, 11);
310     check_dominance(dom_tree, fn, 9, 12);
311 
312     check_dominance(dom_tree, fn, 11, 12);
313 
314     check_no_dominance(dom_tree, fn, 10, 11);
315 
316     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
317     EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
318 
319     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
320               spvtest::GetBasicBlock(fn, 8));
321     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
322               spvtest::GetBasicBlock(fn, 9));
323     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
324               spvtest::GetBasicBlock(fn, 9));
325     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
326               spvtest::GetBasicBlock(fn, 11));
327   }
328 
329   // Check post dominator tree
330   {
331     PostDominatorAnalysis dom_tree;
332     const CFG& cfg = *context->cfg();
333     dom_tree.InitializeTree(cfg, fn);
334 
335     // Inspect the actual tree
336     DominatorTree& tree = dom_tree.GetDomTree();
337     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
338     EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 12));
339 
340     // (strict) dominance checks
341     for (uint32_t id : {8, 9, 10, 11, 12})
342       check_dominance(dom_tree, fn, id, id);
343 
344     check_dominance(dom_tree, fn, 12, 8);
345     check_dominance(dom_tree, fn, 12, 10);
346     check_dominance(dom_tree, fn, 12, 11);
347     check_dominance(dom_tree, fn, 12, 12);
348 
349     check_dominance(dom_tree, fn, 11, 8);
350     check_dominance(dom_tree, fn, 11, 9);
351     check_dominance(dom_tree, fn, 11, 10);
352 
353     check_dominance(dom_tree, fn, 9, 8);
354 
355     EXPECT_EQ(dom_tree.ImmediateDominator(entry),
356               spvtest::GetBasicBlock(fn, 9));
357 
358     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
359               spvtest::GetBasicBlock(fn, 11));
360     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
361               spvtest::GetBasicBlock(fn, 11));
362     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
363               spvtest::GetBasicBlock(fn, 12));
364 
365     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
366               cfg.pseudo_exit_block());
367 
368     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
369   }
370 }
371 
TEST_F(PassClassTest,DominatorLoopToSelf)372 TEST_F(PassClassTest, DominatorLoopToSelf) {
373   const std::string text = R"(
374                OpCapability Addresses
375                OpCapability Kernel
376                OpMemoryModel Physical64 OpenCL
377                OpEntryPoint Kernel %1 "main"
378           %2 = OpTypeVoid
379           %3 = OpTypeFunction %2
380           %4 = OpTypeBool
381           %5 = OpTypeInt 32 0
382           %6 = OpConstant %5 0
383           %7 = OpConstantFalse %4
384           %8 = OpConstantTrue %4
385           %9 = OpConstant %5 1
386           %1 = OpFunction %2 None %3
387          %10 = OpLabel
388                OpBranch %11
389          %11 = OpLabel
390                OpSwitch %6 %12 1 %11
391          %12 = OpLabel
392                OpReturn
393                OpFunctionEnd
394 )";
395   // clang-format on
396   std::unique_ptr<IRContext> context =
397       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
398                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
399   Module* module = context->module();
400   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
401                              << text << std::endl;
402   const Function* fn = spvtest::GetFunction(module, 1);
403 
404   const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
405   EXPECT_EQ(entry, fn->entry().get())
406       << "The entry node is not the expected one";
407 
408   // Check normal dominator tree
409   {
410     DominatorAnalysis dom_tree;
411     const CFG& cfg = *context->cfg();
412     dom_tree.InitializeTree(cfg, fn);
413 
414     // Inspect the actual tree
415     DominatorTree& tree = dom_tree.GetDomTree();
416     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
417     EXPECT_TRUE(
418         dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));
419 
420     // (strict) dominance checks
421     for (uint32_t id : {10, 11, 12}) check_dominance(dom_tree, fn, id, id);
422 
423     check_dominance(dom_tree, fn, 10, 11);
424     check_dominance(dom_tree, fn, 10, 12);
425     check_dominance(dom_tree, fn, 11, 12);
426 
427     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
428     EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
429 
430     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
431               spvtest::GetBasicBlock(fn, 10));
432     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
433               spvtest::GetBasicBlock(fn, 11));
434 
435     std::array<uint32_t, 3> node_order = {{10, 11, 12}};
436     {
437       // Test dominator tree iteration order.
438       DominatorTree::iterator node_it = dom_tree.GetDomTree().begin();
439       DominatorTree::iterator node_end = dom_tree.GetDomTree().end();
440       for (uint32_t id : node_order) {
441         EXPECT_NE(node_it, node_end);
442         EXPECT_EQ(node_it->id(), id);
443         node_it++;
444       }
445       EXPECT_EQ(node_it, node_end);
446     }
447     {
448       // Same as above, but with const iterators.
449       DominatorTree::const_iterator node_it = dom_tree.GetDomTree().cbegin();
450       DominatorTree::const_iterator node_end = dom_tree.GetDomTree().cend();
451       for (uint32_t id : node_order) {
452         EXPECT_NE(node_it, node_end);
453         EXPECT_EQ(node_it->id(), id);
454         node_it++;
455       }
456       EXPECT_EQ(node_it, node_end);
457     }
458     {
459       // Test dominator tree iteration order.
460       DominatorTree::post_iterator node_it = dom_tree.GetDomTree().post_begin();
461       DominatorTree::post_iterator node_end = dom_tree.GetDomTree().post_end();
462       for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
463         EXPECT_NE(node_it, node_end);
464         EXPECT_EQ(node_it->id(), id);
465         node_it++;
466       }
467       EXPECT_EQ(node_it, node_end);
468     }
469     {
470       // Same as above, but with const iterators.
471       DominatorTree::const_post_iterator node_it =
472           dom_tree.GetDomTree().post_cbegin();
473       DominatorTree::const_post_iterator node_end =
474           dom_tree.GetDomTree().post_cend();
475       for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
476         EXPECT_NE(node_it, node_end);
477         EXPECT_EQ(node_it->id(), id);
478         node_it++;
479       }
480       EXPECT_EQ(node_it, node_end);
481     }
482   }
483 
484   // Check post dominator tree
485   {
486     PostDominatorAnalysis dom_tree;
487     const CFG& cfg = *context->cfg();
488     dom_tree.InitializeTree(cfg, fn);
489 
490     // Inspect the actual tree
491     DominatorTree& tree = dom_tree.GetDomTree();
492     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
493     EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 12));
494 
495     // (strict) dominance checks
496     for (uint32_t id : {10, 11, 12}) check_dominance(dom_tree, fn, id, id);
497 
498     check_dominance(dom_tree, fn, 12, 10);
499     check_dominance(dom_tree, fn, 12, 11);
500     check_dominance(dom_tree, fn, 12, 12);
501 
502     EXPECT_EQ(dom_tree.ImmediateDominator(entry),
503               spvtest::GetBasicBlock(fn, 11));
504 
505     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
506               spvtest::GetBasicBlock(fn, 12));
507 
508     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
509 
510     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
511               cfg.pseudo_exit_block());
512 
513     std::array<uint32_t, 3> node_order = {{12, 11, 10}};
514     {
515       // Test dominator tree iteration order.
516       DominatorTree::iterator node_it = tree.begin();
517       DominatorTree::iterator node_end = tree.end();
518       for (uint32_t id : node_order) {
519         EXPECT_NE(node_it, node_end);
520         EXPECT_EQ(node_it->id(), id);
521         node_it++;
522       }
523       EXPECT_EQ(node_it, node_end);
524     }
525     {
526       // Same as above, but with const iterators.
527       DominatorTree::const_iterator node_it = tree.cbegin();
528       DominatorTree::const_iterator node_end = tree.cend();
529       for (uint32_t id : node_order) {
530         EXPECT_NE(node_it, node_end);
531         EXPECT_EQ(node_it->id(), id);
532         node_it++;
533       }
534       EXPECT_EQ(node_it, node_end);
535     }
536     {
537       // Test dominator tree iteration order.
538       DominatorTree::post_iterator node_it = dom_tree.GetDomTree().post_begin();
539       DominatorTree::post_iterator node_end = dom_tree.GetDomTree().post_end();
540       for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
541         EXPECT_NE(node_it, node_end);
542         EXPECT_EQ(node_it->id(), id);
543         node_it++;
544       }
545       EXPECT_EQ(node_it, node_end);
546     }
547     {
548       // Same as above, but with const iterators.
549       DominatorTree::const_post_iterator node_it =
550           dom_tree.GetDomTree().post_cbegin();
551       DominatorTree::const_post_iterator node_end =
552           dom_tree.GetDomTree().post_cend();
553       for (uint32_t id : make_range(node_order.rbegin(), node_order.rend())) {
554         EXPECT_NE(node_it, node_end);
555         EXPECT_EQ(node_it->id(), id);
556         node_it++;
557       }
558       EXPECT_EQ(node_it, node_end);
559     }
560   }
561 }
562 
TEST_F(PassClassTest,DominatorUnreachableInLoop)563 TEST_F(PassClassTest, DominatorUnreachableInLoop) {
564   const std::string text = R"(
565                OpCapability Addresses
566                OpCapability Kernel
567                OpMemoryModel Physical64 OpenCL
568                OpEntryPoint Kernel %1 "main"
569           %2 = OpTypeVoid
570           %3 = OpTypeFunction %2
571           %4 = OpTypeBool
572           %5 = OpTypeInt 32 0
573           %6 = OpConstant %5 0
574           %7 = OpConstantFalse %4
575           %8 = OpConstantTrue %4
576           %9 = OpConstant %5 1
577           %1 = OpFunction %2 None %3
578          %10 = OpLabel
579                OpBranch %11
580          %11 = OpLabel
581                OpSwitch %6 %12 1 %13
582          %12 = OpLabel
583                OpBranch %14
584          %13 = OpLabel
585                OpUnreachable
586          %14 = OpLabel
587                OpBranchConditional %8 %11 %15
588          %15 = OpLabel
589                OpReturn
590                OpFunctionEnd
591 )";
592   // clang-format on
593   std::unique_ptr<IRContext> context =
594       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
595                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
596   Module* module = context->module();
597   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
598                              << text << std::endl;
599   const Function* fn = spvtest::GetFunction(module, 1);
600 
601   const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
602   EXPECT_EQ(entry, fn->entry().get())
603       << "The entry node is not the expected one";
604 
605   // Check normal dominator tree
606   {
607     DominatorAnalysis dom_tree;
608     const CFG& cfg = *context->cfg();
609     dom_tree.InitializeTree(cfg, fn);
610 
611     // Inspect the actual tree
612     DominatorTree& tree = dom_tree.GetDomTree();
613     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
614     EXPECT_TRUE(
615         dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));
616 
617     // (strict) dominance checks
618     for (uint32_t id : {10, 11, 12, 13, 14, 15})
619       check_dominance(dom_tree, fn, id, id);
620 
621     check_dominance(dom_tree, fn, 10, 11);
622     check_dominance(dom_tree, fn, 10, 13);
623     check_dominance(dom_tree, fn, 10, 12);
624     check_dominance(dom_tree, fn, 10, 14);
625     check_dominance(dom_tree, fn, 10, 15);
626 
627     check_dominance(dom_tree, fn, 11, 12);
628     check_dominance(dom_tree, fn, 11, 13);
629     check_dominance(dom_tree, fn, 11, 14);
630     check_dominance(dom_tree, fn, 11, 15);
631 
632     check_dominance(dom_tree, fn, 12, 14);
633     check_dominance(dom_tree, fn, 12, 15);
634 
635     check_dominance(dom_tree, fn, 14, 15);
636 
637     check_no_dominance(dom_tree, fn, 13, 12);
638     check_no_dominance(dom_tree, fn, 13, 14);
639     check_no_dominance(dom_tree, fn, 13, 15);
640 
641     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
642     EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
643 
644     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
645               spvtest::GetBasicBlock(fn, 10));
646     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
647               spvtest::GetBasicBlock(fn, 11));
648     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
649               spvtest::GetBasicBlock(fn, 11));
650     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
651               spvtest::GetBasicBlock(fn, 12));
652     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
653               spvtest::GetBasicBlock(fn, 14));
654   }
655 
656   // Check post dominator tree.
657   {
658     PostDominatorAnalysis dom_tree;
659     const CFG& cfg = *context->cfg();
660     dom_tree.InitializeTree(cfg, fn);
661 
662     // (strict) dominance checks.
663     for (uint32_t id : {10, 11, 12, 13, 14, 15})
664       check_dominance(dom_tree, fn, id, id);
665 
666     check_no_dominance(dom_tree, fn, 15, 10);
667     check_no_dominance(dom_tree, fn, 15, 11);
668     check_no_dominance(dom_tree, fn, 15, 12);
669     check_no_dominance(dom_tree, fn, 15, 13);
670     check_no_dominance(dom_tree, fn, 15, 14);
671 
672     check_dominance(dom_tree, fn, 14, 12);
673 
674     check_no_dominance(dom_tree, fn, 13, 10);
675     check_no_dominance(dom_tree, fn, 13, 11);
676     check_no_dominance(dom_tree, fn, 13, 12);
677     check_no_dominance(dom_tree, fn, 13, 14);
678     check_no_dominance(dom_tree, fn, 13, 15);
679 
680     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
681               spvtest::GetBasicBlock(fn, 11));
682     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
683               spvtest::GetBasicBlock(fn, 14));
684 
685     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
686 
687     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 15)),
688               cfg.pseudo_exit_block());
689     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
690               cfg.pseudo_exit_block());
691     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 14)),
692               cfg.pseudo_exit_block());
693     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
694               cfg.pseudo_exit_block());
695   }
696 }
697 
TEST_F(PassClassTest,DominatorInfinitLoop)698 TEST_F(PassClassTest, DominatorInfinitLoop) {
699   const std::string text = R"(
700                OpCapability Addresses
701                OpCapability Kernel
702                OpMemoryModel Physical64 OpenCL
703                OpEntryPoint Kernel %1 "main"
704           %2 = OpTypeVoid
705           %3 = OpTypeFunction %2
706           %4 = OpTypeBool
707           %5 = OpTypeInt 32 0
708           %6 = OpConstant %5 0
709           %7 = OpConstantFalse %4
710           %8 = OpConstantTrue %4
711           %9 = OpConstant %5 1
712           %1 = OpFunction %2 None %3
713          %10 = OpLabel
714                OpBranch %11
715          %11 = OpLabel
716                OpSwitch %6 %12 1 %13
717          %12 = OpLabel
718                OpReturn
719          %13 = OpLabel
720                OpBranch %13
721                OpFunctionEnd
722 )";
723   // clang-format on
724   std::unique_ptr<IRContext> context =
725       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
726                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
727   Module* module = context->module();
728   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
729                              << text << std::endl;
730   const Function* fn = spvtest::GetFunction(module, 1);
731 
732   const BasicBlock* entry = spvtest::GetBasicBlock(fn, 10);
733   EXPECT_EQ(entry, fn->entry().get())
734       << "The entry node is not the expected one";
735   // Check normal dominator tree
736   {
737     DominatorAnalysis dom_tree;
738     const CFG& cfg = *context->cfg();
739     dom_tree.InitializeTree(cfg, fn);
740 
741     // Inspect the actual tree
742     DominatorTree& tree = dom_tree.GetDomTree();
743     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
744     EXPECT_TRUE(
745         dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));
746 
747     // (strict) dominance checks
748     for (uint32_t id : {10, 11, 12, 13}) check_dominance(dom_tree, fn, id, id);
749 
750     check_dominance(dom_tree, fn, 10, 11);
751     check_dominance(dom_tree, fn, 10, 12);
752     check_dominance(dom_tree, fn, 10, 13);
753 
754     check_dominance(dom_tree, fn, 11, 12);
755     check_dominance(dom_tree, fn, 11, 13);
756 
757     check_no_dominance(dom_tree, fn, 13, 12);
758 
759     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
760     EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
761 
762     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
763               spvtest::GetBasicBlock(fn, 10));
764     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
765               spvtest::GetBasicBlock(fn, 11));
766     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 13)),
767               spvtest::GetBasicBlock(fn, 11));
768   }
769 
770   // Check post dominator tree
771   {
772     PostDominatorAnalysis dom_tree;
773     const CFG& cfg = *context->cfg();
774     dom_tree.InitializeTree(cfg, fn);
775 
776     // Inspect the actual tree
777     DominatorTree& tree = dom_tree.GetDomTree();
778     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
779     EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 12));
780 
781     // (strict) dominance checks
782     for (uint32_t id : {10, 11, 12}) check_dominance(dom_tree, fn, id, id);
783 
784     check_dominance(dom_tree, fn, 12, 11);
785     check_dominance(dom_tree, fn, 12, 10);
786 
787     // 13 should be completely out of tree as it's unreachable from exit nodes
788     check_no_dominance(dom_tree, fn, 12, 13);
789     check_no_dominance(dom_tree, fn, 11, 13);
790     check_no_dominance(dom_tree, fn, 10, 13);
791 
792     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
793 
794     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 12)),
795               cfg.pseudo_exit_block());
796 
797     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
798               spvtest::GetBasicBlock(fn, 11));
799 
800     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 11)),
801               spvtest::GetBasicBlock(fn, 12));
802   }
803 }
804 
TEST_F(PassClassTest,DominatorUnreachableFromEntry)805 TEST_F(PassClassTest, DominatorUnreachableFromEntry) {
806   const std::string text = R"(
807                OpCapability Addresses
808                OpCapability Addresses
809                OpCapability Kernel
810                OpMemoryModel Physical64 OpenCL
811                OpEntryPoint Kernel %1 "main"
812           %2 = OpTypeVoid
813           %3 = OpTypeFunction %2
814           %4 = OpTypeBool
815           %5 = OpTypeInt 32 0
816           %6 = OpConstantFalse %4
817           %7 = OpConstantTrue %4
818           %1 = OpFunction %2 None %3
819           %8 = OpLabel
820                OpBranch %9
821           %9 = OpLabel
822                OpReturn
823          %10 = OpLabel
824                OpBranch %9
825                OpFunctionEnd
826 )";
827   // clang-format on
828   std::unique_ptr<IRContext> context =
829       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
830                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
831   Module* module = context->module();
832   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
833                              << text << std::endl;
834   const Function* fn = spvtest::GetFunction(module, 1);
835 
836   const BasicBlock* entry = spvtest::GetBasicBlock(fn, 8);
837   EXPECT_EQ(entry, fn->entry().get())
838       << "The entry node is not the expected one";
839 
840   // Check dominator tree
841   {
842     DominatorAnalysis dom_tree;
843     const CFG& cfg = *context->cfg();
844     dom_tree.InitializeTree(cfg, fn);
845 
846     // Inspect the actual tree
847     DominatorTree& tree = dom_tree.GetDomTree();
848     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_entry_block());
849     EXPECT_TRUE(
850         dom_tree.Dominates(cfg.pseudo_entry_block()->id(), entry->id()));
851 
852     // (strict) dominance checks
853     for (uint32_t id : {8, 9}) check_dominance(dom_tree, fn, id, id);
854 
855     check_dominance(dom_tree, fn, 8, 9);
856 
857     check_no_dominance(dom_tree, fn, 10, 8);
858     check_no_dominance(dom_tree, fn, 10, 9);
859 
860     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_entry_block()), nullptr);
861     EXPECT_EQ(dom_tree.ImmediateDominator(entry), cfg.pseudo_entry_block());
862 
863     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
864               spvtest::GetBasicBlock(fn, 8));
865     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
866               nullptr);
867   }
868 
869   // Check post dominator tree
870   {
871     PostDominatorAnalysis dom_tree;
872     const CFG& cfg = *context->cfg();
873     dom_tree.InitializeTree(cfg, fn);
874 
875     // Inspect the actual tree
876     DominatorTree& tree = dom_tree.GetDomTree();
877     EXPECT_EQ(tree.GetRoot()->bb_, cfg.pseudo_exit_block());
878     EXPECT_TRUE(dom_tree.Dominates(cfg.pseudo_exit_block()->id(), 9));
879 
880     // (strict) dominance checks
881     for (uint32_t id : {8, 9, 10}) check_dominance(dom_tree, fn, id, id);
882 
883     check_dominance(dom_tree, fn, 9, 8);
884     check_dominance(dom_tree, fn, 9, 10);
885 
886     EXPECT_EQ(dom_tree.ImmediateDominator(entry),
887               spvtest::GetBasicBlock(fn, 9));
888 
889     EXPECT_EQ(dom_tree.ImmediateDominator(cfg.pseudo_exit_block()), nullptr);
890     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 9)),
891               cfg.pseudo_exit_block());
892     EXPECT_EQ(dom_tree.ImmediateDominator(spvtest::GetBasicBlock(fn, 10)),
893               spvtest::GetBasicBlock(fn, 9));
894   }
895 }
896 
TEST_F(PassClassTest,DominationForInstructions)897 TEST_F(PassClassTest, DominationForInstructions) {
898   const std::string text = R"(
899                OpCapability Shader
900           %1 = OpExtInstImport "GLSL.std.450"
901                OpMemoryModel Logical GLSL450
902                OpEntryPoint Fragment %4 "main"
903                OpExecutionMode %4 OriginUpperLeft
904                OpSource ESSL 310
905           %2 = OpTypeVoid
906           %3 = OpTypeFunction %2
907           %6 = OpTypeInt 32 1
908           %7 = OpTypeBool
909           %8 = OpConstantTrue %7
910           %9 = OpConstant %6 37
911          %10 = OpConstant %6 3
912          %13 = OpConstant %6 5
913           %4 = OpFunction %2 None %3
914           %5 = OpLabel
915          %12 = OpIAdd %6 %9 %10
916          %15 = OpISub %6 %12 %13
917                OpSelectionMerge %18 None
918                OpBranchConditional %8 %16 %17
919          %16 = OpLabel
920          %20 = OpISub %6 %12 %13
921                OpBranch %18
922          %17 = OpLabel
923          %21 = OpISub %6 %12 %13
924                OpBranch %18
925          %18 = OpLabel
926          %22 = OpISub %6 %12 %13
927                OpReturn
928                OpFunctionEnd
929   )";
930 
931   // clang-format on
932   std::unique_ptr<IRContext> context =
933       BuildModule(SPV_ENV_UNIVERSAL_1_0, nullptr, text,
934                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
935   EXPECT_NE(nullptr, context->module()) << "Assembling failed for shader:\n"
936                                         << text << std::endl;
937 
938   {
939     const DominatorAnalysis* dominator_analysis = context->GetDominatorAnalysis(
940         spvtest::GetFunction(context->module(), 4));
941 
942     EXPECT_TRUE(
943         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(12),
944                                       context->get_def_use_mgr()->GetDef(15)));
945     EXPECT_FALSE(
946         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
947                                       context->get_def_use_mgr()->GetDef(12)));
948     EXPECT_TRUE(
949         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(5),
950                                       context->get_def_use_mgr()->GetDef(12)));
951     EXPECT_FALSE(
952         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(12),
953                                       context->get_def_use_mgr()->GetDef(5)));
954     EXPECT_TRUE(
955         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
956                                       context->get_def_use_mgr()->GetDef(16)));
957     EXPECT_TRUE(
958         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
959                                       context->get_def_use_mgr()->GetDef(21)));
960     EXPECT_TRUE(
961         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
962                                       context->get_def_use_mgr()->GetDef(18)));
963     EXPECT_TRUE(
964         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
965                                       context->get_def_use_mgr()->GetDef(22)));
966     EXPECT_FALSE(
967         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(20),
968                                       context->get_def_use_mgr()->GetDef(22)));
969     EXPECT_FALSE(
970         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(21),
971                                       context->get_def_use_mgr()->GetDef(22)));
972     EXPECT_TRUE(
973         dominator_analysis->Dominates(context->get_def_use_mgr()->GetDef(15),
974                                       context->get_def_use_mgr()->GetDef(15)));
975   }
976   {
977     const PostDominatorAnalysis* post_dominator_analysis =
978         context->GetPostDominatorAnalysis(
979             spvtest::GetFunction(context->module(), 4));
980 
981     EXPECT_TRUE(post_dominator_analysis->Dominates(
982         context->get_def_use_mgr()->GetDef(15),
983         context->get_def_use_mgr()->GetDef(12)));
984     EXPECT_FALSE(post_dominator_analysis->Dominates(
985         context->get_def_use_mgr()->GetDef(12),
986         context->get_def_use_mgr()->GetDef(15)));
987     EXPECT_TRUE(post_dominator_analysis->Dominates(
988         context->get_def_use_mgr()->GetDef(12),
989         context->get_def_use_mgr()->GetDef(5)));
990     EXPECT_FALSE(post_dominator_analysis->Dominates(
991         context->get_def_use_mgr()->GetDef(5),
992         context->get_def_use_mgr()->GetDef(12)));
993     EXPECT_FALSE(post_dominator_analysis->Dominates(
994         context->get_def_use_mgr()->GetDef(16),
995         context->get_def_use_mgr()->GetDef(15)));
996     EXPECT_FALSE(post_dominator_analysis->Dominates(
997         context->get_def_use_mgr()->GetDef(21),
998         context->get_def_use_mgr()->GetDef(15)));
999     EXPECT_TRUE(post_dominator_analysis->Dominates(
1000         context->get_def_use_mgr()->GetDef(18),
1001         context->get_def_use_mgr()->GetDef(15)));
1002     EXPECT_TRUE(post_dominator_analysis->Dominates(
1003         context->get_def_use_mgr()->GetDef(22),
1004         context->get_def_use_mgr()->GetDef(15)));
1005     EXPECT_TRUE(post_dominator_analysis->Dominates(
1006         context->get_def_use_mgr()->GetDef(22),
1007         context->get_def_use_mgr()->GetDef(20)));
1008     EXPECT_TRUE(post_dominator_analysis->Dominates(
1009         context->get_def_use_mgr()->GetDef(22),
1010         context->get_def_use_mgr()->GetDef(21)));
1011     EXPECT_TRUE(post_dominator_analysis->Dominates(
1012         context->get_def_use_mgr()->GetDef(15),
1013         context->get_def_use_mgr()->GetDef(15)));
1014   }
1015 }
1016 
1017 }  // namespace
1018 }  // namespace opt
1019 }  // namespace spvtools
1020