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 = op->getAttrOfType<DenseI64ArrayAttr>(kBlockIdsAttrName);
55 SmallVector<int64_t> ids;
56 if (idAttr)
57 ids = llvm::to_vector(idAttr.asArrayRef());
58 ids.push_back(Elt: blockId);
59 op->setAttr(kBlockIdsAttrName, b.getDenseI64ArrayAttr(ids));
60 };
61
62 // Create unique IDs for each block.
63 operation->walk(callback: [&](Operation *nested) {
64 if (blockIds.count(Val: nested->getBlock()) > 0)
65 return;
66 blockIds.insert(KV: {nested->getBlock(), blockIds.size()});
67 annotateBlockId(nested->getBlock()->getParentOp(), blockIds.size() - 1);
68 });
69 }
70
71 /// Prints dominance information of all blocks.
72 template <typename DominanceT>
73 void printDominance(DominanceT &dominanceInfo,
74 bool printCommonDominatorInfo) {
75 DenseSet<Block *> parentVisited;
76 operation->walk([&](Operation *op) {
77 Block *block = op->getBlock();
78 if (!parentVisited.insert(V: block).second)
79 return;
80
81 DenseSet<Block *> visited;
82 operation->walk([&](Operation *nested) {
83 Block *nestedBlock = nested->getBlock();
84 if (!visited.insert(V: nestedBlock).second)
85 return;
86 if (printCommonDominatorInfo) {
87 llvm::outs() << "Nearest(" << blockIds[block] << ", "
88 << blockIds[nestedBlock] << ") = ";
89 Block *dom =
90 dominanceInfo.findNearestCommonDominator(block, nestedBlock);
91 if (dom)
92 llvm::outs() << blockIds[dom];
93 else
94 llvm::outs() << "<no dom>";
95 llvm::outs() << "\n";
96 } else {
97 if (std::is_same<DominanceInfo, DominanceT>::value)
98 llvm::outs() << "dominates(";
99 else
100 llvm::outs() << "postdominates(";
101 llvm::outs() << blockIds[block] << ", " << blockIds[nestedBlock]
102 << ") = "
103 << std::to_string(dominatesOrPostDominates(
104 dominanceInfo, block, nestedBlock))
105 << " (properly = "
106 << std::to_string(properlyDominatesOrPostDominates(
107 dominanceInfo, block, nestedBlock))
108 << ")\n";
109 }
110 });
111 });
112 }
113
114private:
115 Operation *operation;
116 DenseMap<Block *, size_t> blockIds;
117};
118
119struct TestDominancePass
120 : public PassWrapper<TestDominancePass, InterfacePass<SymbolOpInterface>> {
121 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestDominancePass)
122
123 StringRef getArgument() const final { return "test-print-dominance"; }
124 StringRef getDescription() const final {
125 return "Print the dominance information for multiple regions.";
126 }
127
128 void runOnOperation() override {
129 llvm::outs() << "Testing : " << getOperation().getName() << "\n";
130 DominanceTest dominanceTest(getOperation());
131
132 // Print dominance information.
133 llvm::outs() << "--- DominanceInfo ---\n";
134 dominanceTest.printDominance(getAnalysis<DominanceInfo>(),
135 /*printCommonDominatorInfo=*/true);
136
137 llvm::outs() << "--- PostDominanceInfo ---\n";
138 dominanceTest.printDominance(getAnalysis<PostDominanceInfo>(),
139 /*printCommonDominatorInfo=*/true);
140
141 // Print dominance relationship between blocks.
142 llvm::outs() << "--- Block Dominance relationship ---\n";
143 dominanceTest.printDominance(getAnalysis<DominanceInfo>(),
144 /*printCommonDominatorInfo=*/false);
145
146 llvm::outs() << "--- Block PostDominance relationship ---\n";
147 dominanceTest.printDominance(getAnalysis<PostDominanceInfo>(),
148 /*printCommonDominatorInfo=*/false);
149 }
150};
151
152} // namespace
153
154namespace mlir {
155namespace test {
156void registerTestDominancePass() { PassRegistration<TestDominancePass>(); }
157} // namespace test
158} // namespace mlir
159

source code of mlir/test/lib/IR/TestDominance.cpp