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
29namespace spvtools {
30namespace opt {
31namespace {
32
33using ::testing::UnorderedElementsAre;
34using 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
43void 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
60void 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
79TEST_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
249TEST_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
372TEST_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
563TEST_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
698TEST_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
805TEST_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
897TEST_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