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 20 using namespace mlir; 21 22 /// Overloaded helper to call the right function based on whether we are testing 23 /// dominance or post-dominance. 24 static bool dominatesOrPostDominates(DominanceInfo &dominanceInfo, Block *a, 25 Block *b) { 26 return dominanceInfo.dominates(a, b); 27 } 28 static bool dominatesOrPostDominates(PostDominanceInfo &dominanceInfo, Block *a, 29 Block *b) { 30 return dominanceInfo.postDominates(a, b); 31 } 32 static bool properlyDominatesOrPostDominates(DominanceInfo &dominanceInfo, 33 Block *a, Block *b) { 34 return dominanceInfo.properlyDominates(a, b); 35 } 36 static bool properlyDominatesOrPostDominates(PostDominanceInfo &dominanceInfo, 37 Block *a, Block *b) { 38 return dominanceInfo.properlyPostDominates(a, b); 39 } 40 41 namespace { 42 43 /// Helper class to print dominance information. 44 class DominanceTest { 45 public: 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(blockId); 59 op->setAttr(kBlockIdsAttrName, b.getDenseI64ArrayAttr(ids)); 60 }; 61 62 // Create unique IDs for each block. 63 operation->walk([&](Operation *nested) { 64 if (blockIds.count(nested->getBlock()) > 0) 65 return; 66 blockIds.insert({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(block).second) 79 return; 80 81 DenseSet<Block *> visited; 82 operation->walk([&](Operation *nested) { 83 Block *nestedBlock = nested->getBlock(); 84 if (!visited.insert(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 114 private: 115 Operation *operation; 116 DenseMap<Block *, size_t> blockIds; 117 }; 118 119 struct 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 154 namespace mlir { 155 namespace test { 156 void registerTestDominancePass() { PassRegistration<TestDominancePass>(); } 157 } // namespace test 158 } // namespace mlir 159