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
28namespace mlir {
29#define GEN_PASS_DEF_REDUCTIONTREEPASS
30#include "mlir/Reducer/Passes.h.inc"
31} // namespace mlir
32
33using 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.
38static void applyPatterns(Region &region,
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.
81template <typename IteratorType>
82static LogicalResult findOptimal(ModuleOp module, Region &region,
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 &currentNode = *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 = &currentNode;
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.
148static LogicalResult eraseAllOpsInRegion(ModuleOp module, Region &region,
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
185template <typename IteratorType>
186static LogicalResult findOptimal(ModuleOp module, Region &region,
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
208namespace {
209
210//===----------------------------------------------------------------------===//
211// Reduction Pattern Interface Collection
212//===----------------------------------------------------------------------===//
213
214class ReductionPatternInterfaceCollection
215 : public DialectInterfaceCollection<DialectReductionPatternInterface> {
216public:
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.
236class ReductionTreePass
237 : public impl::ReductionTreePassBase<ReductionTreePass> {
238public:
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
246private:
247 LogicalResult reduceOp(ModuleOp module, Region &region);
248
249 Tester tester;
250 FrozenRewritePatternSet reducerPatterns;
251};
252
253} // namespace
254
255LogicalResult 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
268void 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 &region : op->getRegions())
286 if (!region.empty())
287 if (failed(Result: reduceOp(module, region)))
288 return signalPassFailure();
289
290 for (Region &region : 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
297LogicalResult ReductionTreePass::reduceOp(ModuleOp module, Region &region) {
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