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/Builders.h"
16#include "mlir/IR/Dominance.h"
17#include "mlir/IR/SymbolTable.h"
18#include "mlir/Pass/Pass.h"
19
20using namespace mlir;
21
22/// Overloaded helper to call the right function based on whether we are testing
23/// dominance or post-dominance.
24static bool dominatesOrPostDominates(DominanceInfo &dominanceInfo, Block *a,
25 Block *b) {
26 return dominanceInfo.dominates(a, b);
27}
28static bool dominatesOrPostDominates(PostDominanceInfo &dominanceInfo, Block *a,
29 Block *b) {
30 return dominanceInfo.postDominates(a, b);
31}
32static bool properlyDominatesOrPostDominates(DominanceInfo &dominanceInfo,
33 Block *a, Block *b) {
34 return dominanceInfo.properlyDominates(a, b);
35}
36static bool properlyDominatesOrPostDominates(PostDominanceInfo &dominanceInfo,
37 Block *a, Block *b) {
38 return dominanceInfo.properlyPostDominates(a, b);
39}
40
41namespace {
42
43/// Helper class to print dominance information.
44class DominanceTest {
45public:
46 static constexpr StringRef kBlockIdsAttrName = "test.block_ids";
47
48 /// Constructs a new test instance using the given operation.
49 DominanceTest(Operation *operation) : operation(operation) {
50 Builder b(operation->getContext());
51
52 // Helper function that annotates the IR with block IDs.
53 auto annotateBlockId = [&](Operation *op, int64_t blockId) {
54 auto idAttr =
55 op->getDiscardableAttrOfType<DenseI64ArrayAttr>(name: kBlockIdsAttrName);
56 SmallVector<int64_t> ids;
57 if (idAttr)
58 ids = llvm::to_vector(Range: idAttr.asArrayRef());
59 ids.push_back(Elt: blockId);
60 op->setDiscardableAttr(name: kBlockIdsAttrName, value: b.getDenseI64ArrayAttr(values: ids));
61 };
62
63 // Create unique IDs for each block.
64 operation->walk(callback: [&](Operation *nested) {
65 if (blockIds.count(Val: nested->getBlock()) > 0)
66 return;
67 blockIds.insert(KV: {nested->getBlock(), blockIds.size()});
68 annotateBlockId(nested->getBlock()->getParentOp(), blockIds.size() - 1);
69 });
70 }
71
72 /// Prints dominance information of all blocks.
73 template <typename DominanceT>
74 void printDominance(DominanceT &dominanceInfo,
75 bool printCommonDominatorInfo) {
76 DenseSet<Block *> parentVisited;
77 operation->walk([&](Operation *op) {
78 Block *block = op->getBlock();
79 if (!parentVisited.insert(V: block).second)
80 return;
81
82 DenseSet<Block *> visited;
83 operation->walk([&](Operation *nested) {
84 Block *nestedBlock = nested->getBlock();
85 if (!visited.insert(V: nestedBlock).second)
86 return;
87 if (printCommonDominatorInfo) {
88 llvm::outs() << "Nearest(" << blockIds[block] << ", "
89 << blockIds[nestedBlock] << ") = ";
90 Block *dom =
91 dominanceInfo.findNearestCommonDominator(block, nestedBlock);
92 if (dom)
93 llvm::outs() << blockIds[dom];
94 else
95 llvm::outs() << "<no dom>";
96 llvm::outs() << "\n";
97 } else {
98 if (std::is_same<DominanceInfo, DominanceT>::value)
99 llvm::outs() << "dominates(";
100 else
101 llvm::outs() << "postdominates(";
102 llvm::outs() << blockIds[block] << ", " << blockIds[nestedBlock]
103 << ") = "
104 << std::to_string(dominatesOrPostDominates(
105 dominanceInfo, block, nestedBlock))
106 << " (properly = "
107 << std::to_string(properlyDominatesOrPostDominates(
108 dominanceInfo, block, nestedBlock))
109 << ")\n";
110 }
111 });
112 });
113 }
114
115private:
116 Operation *operation;
117 DenseMap<Block *, size_t> blockIds;
118};
119
120struct TestDominancePass
121 : public PassWrapper<TestDominancePass, InterfacePass<SymbolOpInterface>> {
122 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestDominancePass)
123
124 StringRef getArgument() const final { return "test-print-dominance"; }
125 StringRef getDescription() const final {
126 return "Print the dominance information for multiple regions.";
127 }
128
129 void runOnOperation() override {
130 llvm::outs() << "Testing : " << getOperation().getName() << "\n";
131 DominanceTest dominanceTest(getOperation());
132
133 // Print dominance information.
134 llvm::outs() << "--- DominanceInfo ---\n";
135 dominanceTest.printDominance(dominanceInfo&: getAnalysis<DominanceInfo>(),
136 /*printCommonDominatorInfo=*/true);
137
138 llvm::outs() << "--- PostDominanceInfo ---\n";
139 dominanceTest.printDominance(dominanceInfo&: getAnalysis<PostDominanceInfo>(),
140 /*printCommonDominatorInfo=*/true);
141
142 // Print dominance relationship between blocks.
143 llvm::outs() << "--- Block Dominance relationship ---\n";
144 dominanceTest.printDominance(dominanceInfo&: getAnalysis<DominanceInfo>(),
145 /*printCommonDominatorInfo=*/false);
146
147 llvm::outs() << "--- Block PostDominance relationship ---\n";
148 dominanceTest.printDominance(dominanceInfo&: getAnalysis<PostDominanceInfo>(),
149 /*printCommonDominatorInfo=*/false);
150 }
151};
152
153} // namespace
154
155namespace mlir {
156namespace test {
157void registerTestDominancePass() { PassRegistration<TestDominancePass>(); }
158} // namespace test
159} // namespace mlir
160