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