| 1 | //===- ReductionTreePass.cpp - ReductionTreePass Implementation -----------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This file defines the Reduction Tree Pass class. It provides a framework for |
| 10 | // the implementation of different reduction passes in the MLIR Reduce tool. It |
| 11 | // allows for custom specification of the variant generation behavior. It |
| 12 | // implements methods that define the different possible traversals of the |
| 13 | // reduction tree. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
| 17 | #include "mlir/IR/DialectInterface.h" |
| 18 | #include "mlir/Reducer/Passes.h" |
| 19 | #include "mlir/Reducer/ReductionNode.h" |
| 20 | #include "mlir/Reducer/ReductionPatternInterface.h" |
| 21 | #include "mlir/Reducer/Tester.h" |
| 22 | #include "mlir/Rewrite/FrozenRewritePatternSet.h" |
| 23 | #include "mlir/Transforms/GreedyPatternRewriteDriver.h" |
| 24 | |
| 25 | #include "llvm/ADT/ArrayRef.h" |
| 26 | #include "llvm/Support/Allocator.h" |
| 27 | |
| 28 | namespace mlir { |
| 29 | #define GEN_PASS_DEF_REDUCTIONTREEPASS |
| 30 | #include "mlir/Reducer/Passes.h.inc" |
| 31 | } // namespace mlir |
| 32 | |
| 33 | using namespace mlir; |
| 34 | |
| 35 | /// We implicitly number each operation in the region and if an operation's |
| 36 | /// number falls into rangeToKeep, we need to keep it and apply the given |
| 37 | /// rewrite patterns on it. |
| 38 | static void applyPatterns(Region ®ion, |
| 39 | const FrozenRewritePatternSet &patterns, |
| 40 | ArrayRef<ReductionNode::Range> rangeToKeep, |
| 41 | bool eraseOpNotInRange) { |
| 42 | std::vector<Operation *> opsNotInRange; |
| 43 | size_t keepIndex = 0; |
| 44 | for (const auto &op : enumerate(First: region.getOps())) { |
| 45 | int index = op.index(); |
| 46 | if (keepIndex < rangeToKeep.size() && |
| 47 | index == rangeToKeep[keepIndex].second) |
| 48 | ++keepIndex; |
| 49 | if (keepIndex == rangeToKeep.size() || index < rangeToKeep[keepIndex].first) |
| 50 | opsNotInRange.push_back(x: &op.value()); |
| 51 | } |
| 52 | |
| 53 | // `applyOpPatternsGreedily` with folding may erase the ops so we can't do the |
| 54 | // pattern matching in above iteration. Besides, erase op not-in-range may end |
| 55 | // up in invalid module, so `applyOpPatternsGreedily` with folding should come |
| 56 | // before that transform. |
| 57 | if (!eraseOpNotInRange) |
| 58 | for (Operation *op : opsNotInRange) { |
| 59 | // `applyOpPatternsGreedily` with folding returns whether the op is |
| 60 | // converted. Omit it because we don't have expectation this reduction |
| 61 | // will be success or not. |
| 62 | (void)applyOpPatternsGreedily(ops: op, patterns, |
| 63 | config: GreedyRewriteConfig().setStrictness( |
| 64 | GreedyRewriteStrictness::ExistingOps)); |
| 65 | } |
| 66 | |
| 67 | if (eraseOpNotInRange) |
| 68 | for (Operation *op : opsNotInRange) { |
| 69 | op->dropAllUses(); |
| 70 | op->erase(); |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | /// We will apply the reducer patterns to the operations in the ranges specified |
| 75 | /// by ReductionNode. Note that we are not able to remove an operation without |
| 76 | /// replacing it with another valid operation. However, The validity of module |
| 77 | /// reduction is based on the Tester provided by the user and that means certain |
| 78 | /// invalid module is still interested by the use. Thus we provide an |
| 79 | /// alternative way to remove operations, which is using `eraseOpNotInRange` to |
| 80 | /// erase the operations not in the range specified by ReductionNode. |
| 81 | template <typename IteratorType> |
| 82 | static LogicalResult findOptimal(ModuleOp module, Region ®ion, |
| 83 | const FrozenRewritePatternSet &patterns, |
| 84 | const Tester &test, bool eraseOpNotInRange) { |
| 85 | std::pair<Tester::Interestingness, size_t> initStatus = |
| 86 | test.isInteresting(topOp: module); |
| 87 | // While exploring the reduction tree, we always branch from an interesting |
| 88 | // node. Thus the root node must be interesting. |
| 89 | if (initStatus.first != Tester::Interestingness::True) |
| 90 | return module.emitError() << "uninterested module will not be reduced" ; |
| 91 | |
| 92 | llvm::SpecificBumpPtrAllocator<ReductionNode> allocator; |
| 93 | |
| 94 | std::vector<ReductionNode::Range> ranges{ |
| 95 | {0, std::distance(first: region.op_begin(), last: region.op_end())}}; |
| 96 | |
| 97 | ReductionNode *root = allocator.Allocate(); |
| 98 | new (root) ReductionNode(nullptr, ranges, allocator); |
| 99 | // Duplicate the module for root node and locate the region in the copy. |
| 100 | if (failed(Result: root->initialize(parentModule: module, parentRegion&: region))) |
| 101 | llvm_unreachable("unexpected initialization failure" ); |
| 102 | root->update(result: initStatus); |
| 103 | |
| 104 | ReductionNode *smallestNode = root; |
| 105 | IteratorType iter(root); |
| 106 | |
| 107 | while (iter != IteratorType::end()) { |
| 108 | ReductionNode ¤tNode = *iter; |
| 109 | Region &curRegion = currentNode.getRegion(); |
| 110 | |
| 111 | applyPatterns(region&: curRegion, patterns, rangeToKeep: currentNode.getRanges(), |
| 112 | eraseOpNotInRange); |
| 113 | currentNode.update(result: test.isInteresting(topOp: currentNode.getModule())); |
| 114 | |
| 115 | if (currentNode.isInteresting() == Tester::Interestingness::True && |
| 116 | currentNode.getSize() < smallestNode->getSize()) |
| 117 | smallestNode = ¤tNode; |
| 118 | |
| 119 | ++iter; |
| 120 | } |
| 121 | |
| 122 | // At here, we have found an optimal path to reduce the given region. Retrieve |
| 123 | // the path and apply the reducer to it. |
| 124 | SmallVector<ReductionNode *> trace; |
| 125 | ReductionNode *curNode = smallestNode; |
| 126 | trace.push_back(Elt: curNode); |
| 127 | while (curNode != root) { |
| 128 | curNode = curNode->getParent(); |
| 129 | trace.push_back(Elt: curNode); |
| 130 | } |
| 131 | |
| 132 | // Reduce the region through the optimal path. |
| 133 | while (!trace.empty()) { |
| 134 | ReductionNode *top = trace.pop_back_val(); |
| 135 | applyPatterns(region, patterns, rangeToKeep: top->getStartRanges(), eraseOpNotInRange); |
| 136 | } |
| 137 | |
| 138 | if (test.isInteresting(topOp: module).first != Tester::Interestingness::True) |
| 139 | llvm::report_fatal_error(reason: "Reduced module is not interesting" ); |
| 140 | if (test.isInteresting(topOp: module).second != smallestNode->getSize()) |
| 141 | llvm::report_fatal_error( |
| 142 | reason: "Reduced module doesn't have consistent size with smallestNode" ); |
| 143 | return success(); |
| 144 | } |
| 145 | |
| 146 | /// This function attempts to erase all operations within the region currently |
| 147 | /// being processed. |
| 148 | static LogicalResult eraseAllOpsInRegion(ModuleOp module, Region ®ion, |
| 149 | const Tester &test) { |
| 150 | std::pair<Tester::Interestingness, size_t> initStatus = |
| 151 | test.isInteresting(topOp: module); |
| 152 | |
| 153 | // While exploring the reduction tree, we always branch from an interesting |
| 154 | // node. Thus the root node must be interesting. |
| 155 | if (initStatus.first != Tester::Interestingness::True) |
| 156 | return module.emitError() << "uninterested module will not be reduced" ; |
| 157 | llvm::SpecificBumpPtrAllocator<ReductionNode> allocator; |
| 158 | |
| 159 | // Setting the ranges to {{0, 0}} will result in the deletion of all ops |
| 160 | // within the region. |
| 161 | std::vector<ReductionNode::Range> ranges{{0, 0}}; |
| 162 | |
| 163 | // We allocate memory on the stack, and the 'allocator' is only used to |
| 164 | // construct the 'root node'. Since we won't be constructing any child nodes |
| 165 | // for emptyRegionNode, it is only used within the current scope. |
| 166 | ReductionNode emptyRegionNode(nullptr, ranges, allocator); |
| 167 | ReductionNode *root = &emptyRegionNode; |
| 168 | |
| 169 | // Create a copy of the current IR. |
| 170 | if (failed(Result: root->initialize(parentModule: module, parentRegion&: region))) |
| 171 | llvm_unreachable("unexpected initialization failure" ); |
| 172 | |
| 173 | // Erase all operations within the corresponding region of the clone. |
| 174 | applyPatterns(region&: root->getRegion(), patterns: {}, rangeToKeep: root->getRanges(), eraseOpNotInRange: true); |
| 175 | root->update(result: test.isInteresting(topOp: root->getModule())); |
| 176 | if (root->isInteresting() == Tester::Interestingness::True) { |
| 177 | // If we can successfully remove all ops in the region, we apply the same |
| 178 | // transformation to the original IR and return success. |
| 179 | applyPatterns(region, patterns: {}, rangeToKeep: root->getRanges(), eraseOpNotInRange: true); |
| 180 | return success(); |
| 181 | } |
| 182 | return failure(); |
| 183 | } |
| 184 | |
| 185 | template <typename IteratorType> |
| 186 | static LogicalResult findOptimal(ModuleOp module, Region ®ion, |
| 187 | const FrozenRewritePatternSet &patterns, |
| 188 | const Tester &test) { |
| 189 | // We separate the reduction process into 3 steps, the first one is to erase |
| 190 | // redundant operations and the second one is to apply the reducer patterns. |
| 191 | |
| 192 | // In the first phase, we attempt to erase all operations within the entire |
| 193 | // region. |
| 194 | if (succeeded(Result: eraseAllOpsInRegion(module, region, test))) |
| 195 | return success(); |
| 196 | |
| 197 | // In the second phase, we don't apply any patterns so that we only select the |
| 198 | // range of operations to keep to the module stay interesting. |
| 199 | if (failed(findOptimal<IteratorType>(module, region, /*patterns=*/{}, test, |
| 200 | /*eraseOpNotInRange=*/true))) |
| 201 | return failure(); |
| 202 | // In the third phase, we suppose that no operation is redundant, so we try |
| 203 | // to rewrite the operation into simpler form. |
| 204 | return findOptimal<IteratorType>(module, region, patterns, test, |
| 205 | /*eraseOpNotInRange=*/false); |
| 206 | } |
| 207 | |
| 208 | namespace { |
| 209 | |
| 210 | //===----------------------------------------------------------------------===// |
| 211 | // Reduction Pattern Interface Collection |
| 212 | //===----------------------------------------------------------------------===// |
| 213 | |
| 214 | class ReductionPatternInterfaceCollection |
| 215 | : public DialectInterfaceCollection<DialectReductionPatternInterface> { |
| 216 | public: |
| 217 | using Base::Base; |
| 218 | |
| 219 | // Collect the reduce patterns defined by each dialect. |
| 220 | void populateReductionPatterns(RewritePatternSet &pattern, |
| 221 | Tester &tester) const { |
| 222 | for (const DialectReductionPatternInterface &interface : *this) { |
| 223 | interface.populateReductionPatterns(patterns&: pattern); |
| 224 | interface.populateReductionPatternsWithTester(patterns&: pattern, tester); |
| 225 | } |
| 226 | } |
| 227 | }; |
| 228 | |
| 229 | //===----------------------------------------------------------------------===// |
| 230 | // ReductionTreePass |
| 231 | //===----------------------------------------------------------------------===// |
| 232 | |
| 233 | /// This class defines the Reduction Tree Pass. It provides a framework to |
| 234 | /// to implement a reduction pass using a tree structure to keep track of the |
| 235 | /// generated reduced variants. |
| 236 | class ReductionTreePass |
| 237 | : public impl::ReductionTreePassBase<ReductionTreePass> { |
| 238 | public: |
| 239 | using Base::Base; |
| 240 | |
| 241 | LogicalResult initialize(MLIRContext *context) override; |
| 242 | |
| 243 | /// Runs the pass instance in the pass pipeline. |
| 244 | void runOnOperation() override; |
| 245 | |
| 246 | private: |
| 247 | LogicalResult reduceOp(ModuleOp module, Region ®ion); |
| 248 | |
| 249 | Tester tester; |
| 250 | FrozenRewritePatternSet reducerPatterns; |
| 251 | }; |
| 252 | |
| 253 | } // namespace |
| 254 | |
| 255 | LogicalResult ReductionTreePass::initialize(MLIRContext *context) { |
| 256 | tester.setTestScript(testerName); |
| 257 | tester.setTestScriptArgs(testerArgs); |
| 258 | |
| 259 | RewritePatternSet patterns(context); |
| 260 | |
| 261 | ReductionPatternInterfaceCollection reducePatternCollection(context); |
| 262 | reducePatternCollection.populateReductionPatterns(pattern&: patterns, tester); |
| 263 | |
| 264 | reducerPatterns = std::move(patterns); |
| 265 | return success(); |
| 266 | } |
| 267 | |
| 268 | void ReductionTreePass::runOnOperation() { |
| 269 | Operation *topOperation = getOperation(); |
| 270 | while (topOperation->getParentOp() != nullptr) |
| 271 | topOperation = topOperation->getParentOp(); |
| 272 | ModuleOp module = dyn_cast<ModuleOp>(Val: topOperation); |
| 273 | if (!module) { |
| 274 | emitError(loc: getOperation()->getLoc()) |
| 275 | << "top-level op must be 'builtin.module'" ; |
| 276 | return signalPassFailure(); |
| 277 | } |
| 278 | |
| 279 | SmallVector<Operation *, 8> workList; |
| 280 | workList.push_back(Elt: getOperation()); |
| 281 | |
| 282 | do { |
| 283 | Operation *op = workList.pop_back_val(); |
| 284 | |
| 285 | for (Region ®ion : op->getRegions()) |
| 286 | if (!region.empty()) |
| 287 | if (failed(Result: reduceOp(module, region))) |
| 288 | return signalPassFailure(); |
| 289 | |
| 290 | for (Region ®ion : op->getRegions()) |
| 291 | for (Operation &op : region.getOps()) |
| 292 | if (op.getNumRegions() != 0) |
| 293 | workList.push_back(Elt: &op); |
| 294 | } while (!workList.empty()); |
| 295 | } |
| 296 | |
| 297 | LogicalResult ReductionTreePass::reduceOp(ModuleOp module, Region ®ion) { |
| 298 | switch (traversalModeId) { |
| 299 | case TraversalMode::SinglePath: |
| 300 | return findOptimal<ReductionNode::iterator<TraversalMode::SinglePath>>( |
| 301 | module, region, patterns: reducerPatterns, test: tester); |
| 302 | default: |
| 303 | return module.emitError() << "unsupported traversal mode detected" ; |
| 304 | } |
| 305 | } |
| 306 | |