1 //===- TestDominance.cpp - Test dominance construction and information
2 //-------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains test passes for constructing and resolving dominance
11 // information.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "mlir/IR/Dominance.h"
16 #include "mlir/Pass/Pass.h"
17 
18 using namespace mlir;
19 
20 /// Overloaded helper to call the right function based on whether we are testing
21 /// dominance or post-dominance.
22 static bool dominatesOrPostDominates(DominanceInfo &dominanceInfo, Block *a,
23                                      Block *b) {
24   return dominanceInfo.dominates(a, b);
25 }
26 
27 static bool dominatesOrPostDominates(PostDominanceInfo &dominanceInfo, Block *a,
28                                      Block *b) {
29   return dominanceInfo.postDominates(a, b);
30 }
31 
32 namespace {
33 
34 /// Helper class to print dominance information.
35 class DominanceTest {
36 public:
37   /// Constructs a new test instance using the given operation.
38   DominanceTest(Operation *operation) : operation(operation) {
39     // Create unique ids for each block.
40     operation->walk([&](Operation *nested) {
41       if (blockIds.count(nested->getBlock()) > 0)
42         return;
43       blockIds.insert({nested->getBlock(), blockIds.size()});
44     });
45   }
46 
47   /// Prints dominance information of all blocks.
48   template <typename DominanceT>
49   void printDominance(DominanceT &dominanceInfo,
50                       bool printCommonDominatorInfo) {
51     DenseSet<Block *> parentVisited;
52     operation->walk([&](Operation *op) {
53       Block *block = op->getBlock();
54       if (!parentVisited.insert(block).second)
55         return;
56 
57       DenseSet<Block *> visited;
58       operation->walk([&](Operation *nested) {
59         Block *nestedBlock = nested->getBlock();
60         if (!visited.insert(nestedBlock).second)
61           return;
62         if (printCommonDominatorInfo) {
63           llvm::errs() << "Nearest(" << blockIds[block] << ", "
64                        << blockIds[nestedBlock] << ") = ";
65           Block *dom =
66               dominanceInfo.findNearestCommonDominator(block, nestedBlock);
67           if (dom)
68             llvm::errs() << blockIds[dom];
69           else
70             llvm::errs() << "<no dom>";
71           llvm::errs() << "\n";
72         } else {
73           if (std::is_same<DominanceInfo, DominanceT>::value)
74             llvm::errs() << "dominates(";
75           else
76             llvm::errs() << "postdominates(";
77           llvm::errs() << blockIds[block] << ", " << blockIds[nestedBlock]
78                        << ") = ";
79           if (dominatesOrPostDominates(dominanceInfo, block, nestedBlock))
80             llvm::errs() << "true\n";
81           else
82             llvm::errs() << "false\n";
83         }
84       });
85     });
86   }
87 
88 private:
89   Operation *operation;
90   DenseMap<Block *, size_t> blockIds;
91 };
92 
93 struct TestDominancePass : public PassWrapper<TestDominancePass, FunctionPass> {
94   StringRef getArgument() const final { return "test-print-dominance"; }
95   StringRef getDescription() const final {
96     return "Print the dominance information for multiple regions.";
97   }
98 
99   void runOnFunction() override {
100     llvm::errs() << "Testing : " << getFunction().getName() << "\n";
101     DominanceTest dominanceTest(getFunction());
102 
103     // Print dominance information.
104     llvm::errs() << "--- DominanceInfo ---\n";
105     dominanceTest.printDominance(getAnalysis<DominanceInfo>(),
106                                  /*printCommonDominatorInfo=*/true);
107 
108     llvm::errs() << "--- PostDominanceInfo ---\n";
109     dominanceTest.printDominance(getAnalysis<PostDominanceInfo>(),
110                                  /*printCommonDominatorInfo=*/true);
111 
112     // Print dominance relationship between blocks.
113     llvm::errs() << "--- Block Dominance relationship ---\n";
114     dominanceTest.printDominance(getAnalysis<DominanceInfo>(),
115                                  /*printCommonDominatorInfo=*/false);
116 
117     llvm::errs() << "--- Block PostDominance relationship ---\n";
118     dominanceTest.printDominance(getAnalysis<PostDominanceInfo>(),
119                                  /*printCommonDominatorInfo=*/false);
120   }
121 };
122 
123 } // end anonymous namespace
124 
125 namespace mlir {
126 namespace test {
127 void registerTestDominancePass() { PassRegistration<TestDominancePass>(); }
128 } // namespace test
129 } // namespace mlir
130