1//===- FoldUtils.cpp ---- Fold Utilities ----------------------------------===//
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 various operation fold utilities. These utilities are
10// intended to be used by passes to unify and simply their logic.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Transforms/FoldUtils.h"
15
16#include "mlir/IR/Builders.h"
17#include "mlir/IR/Matchers.h"
18#include "mlir/IR/Operation.h"
19#include "llvm/Support/DebugLog.h"
20
21using namespace mlir;
22
23/// Given an operation, find the parent region that folded constants should be
24/// inserted into.
25static Region *
26getInsertionRegion(DialectInterfaceCollection<DialectFoldInterface> &interfaces,
27 Block *insertionBlock) {
28 while (Region *region = insertionBlock->getParent()) {
29 // Insert in this region for any of the following scenarios:
30 // * The parent is unregistered, or is known to be isolated from above.
31 // * The parent is a top-level operation.
32 auto *parentOp = region->getParentOp();
33 if (parentOp->mightHaveTrait<OpTrait::IsIsolatedFromAbove>() ||
34 !parentOp->getBlock())
35 return region;
36
37 // Otherwise, check if this region is a desired insertion region.
38 auto *interface = interfaces.getInterfaceFor(obj: parentOp);
39 if (LLVM_UNLIKELY(interface && interface->shouldMaterializeInto(region)))
40 return region;
41
42 // Traverse up the parent looking for an insertion region.
43 insertionBlock = parentOp->getBlock();
44 }
45 llvm_unreachable("expected valid insertion region");
46}
47
48/// A utility function used to materialize a constant for a given attribute and
49/// type. On success, a valid constant value is returned. Otherwise, null is
50/// returned
51static Operation *materializeConstant(Dialect *dialect, OpBuilder &builder,
52 Attribute value, Type type,
53 Location loc) {
54 auto insertPt = builder.getInsertionPoint();
55 (void)insertPt;
56
57 // Ask the dialect to materialize a constant operation for this value.
58 if (auto *constOp = dialect->materializeConstant(builder, value, type, loc)) {
59 assert(insertPt == builder.getInsertionPoint());
60 assert(matchPattern(constOp, m_Constant()));
61 return constOp;
62 }
63
64 return nullptr;
65}
66
67//===----------------------------------------------------------------------===//
68// OperationFolder
69//===----------------------------------------------------------------------===//
70
71LogicalResult OperationFolder::tryToFold(Operation *op, bool *inPlaceUpdate,
72 int maxIterations) {
73 if (inPlaceUpdate)
74 *inPlaceUpdate = false;
75
76 // If this is a unique'd constant, return failure as we know that it has
77 // already been folded.
78 if (isFolderOwnedConstant(op)) {
79 // Check to see if we should rehoist, i.e. if a non-constant operation was
80 // inserted before this one.
81 Block *opBlock = op->getBlock();
82 if (&opBlock->front() != op && !isFolderOwnedConstant(op: op->getPrevNode())) {
83 rewriter.moveOpBefore(op, existingOp: &opBlock->front());
84 op->setLoc(erasedFoldedLocation);
85 }
86 return failure();
87 }
88
89 // Try to fold the operation.
90 SmallVector<Value, 8> results;
91 if (failed(Result: tryToFold(op, results, maxIterations)))
92 return failure();
93
94 // Check to see if the operation was just updated in place.
95 if (results.empty()) {
96 if (inPlaceUpdate)
97 *inPlaceUpdate = true;
98 if (auto *rewriteListener = dyn_cast_if_present<RewriterBase::Listener>(
99 Val: rewriter.getListener())) {
100 // Folding API does not notify listeners, so we have to notify manually.
101 rewriteListener->notifyOperationModified(op);
102 }
103 return success();
104 }
105
106 // Constant folding succeeded. Replace all of the result values and erase the
107 // operation.
108 notifyRemoval(op);
109 rewriter.replaceOp(op, newValues: results);
110 return success();
111}
112
113OperationFolder::ConstantInsertionResult
114OperationFolder::insertKnownConstant(Operation *op, Attribute constValue) {
115 Block *opBlock = op->getBlock();
116
117 // If this is a constant we unique'd, we don't need to insert, but we can
118 // check to see if we should rehoist it.
119 if (isFolderOwnedConstant(op)) {
120 if (&opBlock->front() != op && !isFolderOwnedConstant(op: op->getPrevNode())) {
121 rewriter.moveOpBefore(op, existingOp: &opBlock->front());
122 op->setLoc(erasedFoldedLocation);
123 return ConstantInsertionResult::Hoisted;
124 }
125 return ConstantInsertionResult::Unchanged;
126 }
127
128 // Get the constant value of the op if necessary.
129 if (!constValue) {
130 matchPattern(op, pattern: m_Constant(bind_value: &constValue));
131 assert(constValue && "expected `op` to be a constant");
132 } else {
133 // Ensure that the provided constant was actually correct.
134#ifndef NDEBUG
135 Attribute expectedValue;
136 matchPattern(op, m_Constant(&expectedValue));
137 assert(
138 expectedValue == constValue &&
139 "provided constant value was not the expected value of the constant");
140#endif
141 }
142
143 // Check for an existing constant operation for the attribute value.
144 Region *insertRegion = getInsertionRegion(interfaces, insertionBlock: opBlock);
145 auto &uniquedConstants = foldScopes[insertRegion];
146 Operation *&folderConstOp = uniquedConstants[std::make_tuple(
147 args: op->getDialect(), args&: constValue, args: *op->result_type_begin())];
148
149 // If there is an existing constant, replace `op`.
150 if (folderConstOp) {
151 notifyRemoval(op);
152 rewriter.replaceOp(op, newValues: folderConstOp->getResults());
153 folderConstOp->setLoc(erasedFoldedLocation);
154 return ConstantInsertionResult::Replaced;
155 }
156
157 // Otherwise, we insert `op`. If `op` is in the insertion block and is either
158 // already at the front of the block, or the previous operation is already a
159 // constant we unique'd (i.e. one we inserted), then we don't need to do
160 // anything. Otherwise, we move the constant to the insertion block.
161 // The location info is erased if the constant is moved to a different block.
162 ConstantInsertionResult result = ConstantInsertionResult::Unchanged;
163 Block *insertBlock = &insertRegion->front();
164 if (opBlock != insertBlock) {
165 rewriter.moveOpBefore(op, existingOp: &insertBlock->front());
166 op->setLoc(erasedFoldedLocation);
167 result = ConstantInsertionResult::Hoisted;
168 } else if (&insertBlock->front() != op &&
169 !isFolderOwnedConstant(op: op->getPrevNode())) {
170 rewriter.moveOpBefore(op, existingOp: &insertBlock->front());
171 result = ConstantInsertionResult::Hoisted;
172 }
173
174 folderConstOp = op;
175 referencedDialects[op].push_back(Elt: op->getDialect());
176 return result;
177}
178
179/// Notifies that the given constant `op` should be remove from this
180/// OperationFolder's internal bookkeeping.
181void OperationFolder::notifyRemoval(Operation *op) {
182 // Check to see if this operation is uniqued within the folder.
183 auto it = referencedDialects.find(Val: op);
184 if (it == referencedDialects.end())
185 return;
186
187 // Get the constant value for this operation, this is the value that was used
188 // to unique the operation internally.
189 Attribute constValue;
190 matchPattern(op, pattern: m_Constant(bind_value: &constValue));
191 assert(constValue);
192
193 // Get the constant map that this operation was uniqued in.
194 auto &uniquedConstants =
195 foldScopes[getInsertionRegion(interfaces, insertionBlock: op->getBlock())];
196
197 // Erase all of the references to this operation.
198 auto type = op->getResult(idx: 0).getType();
199 for (auto *dialect : it->second)
200 uniquedConstants.erase(Val: std::make_tuple(args&: dialect, args&: constValue, args&: type));
201 referencedDialects.erase(I: it);
202}
203
204/// Clear out any constants cached inside of the folder.
205void OperationFolder::clear() {
206 foldScopes.clear();
207 referencedDialects.clear();
208}
209
210/// Get or create a constant using the given builder. On success this returns
211/// the constant operation, nullptr otherwise.
212Value OperationFolder::getOrCreateConstant(Block *block, Dialect *dialect,
213 Attribute value, Type type) {
214 // Find an insertion point for the constant.
215 auto *insertRegion = getInsertionRegion(interfaces, insertionBlock: block);
216 auto &entry = insertRegion->front();
217 rewriter.setInsertionPointToStart(&entry);
218
219 // Get the constant map for the insertion region of this operation.
220 // Use erased location since the op is being built at the front of block.
221 auto &uniquedConstants = foldScopes[insertRegion];
222 Operation *constOp = tryGetOrCreateConstant(uniquedConstants, dialect, value,
223 type, loc: erasedFoldedLocation);
224 return constOp ? constOp->getResult(idx: 0) : Value();
225}
226
227bool OperationFolder::isFolderOwnedConstant(Operation *op) const {
228 return referencedDialects.count(Val: op);
229}
230
231/// Tries to perform folding on the given `op`. If successful, populates
232/// `results` with the results of the folding.
233LogicalResult OperationFolder::tryToFold(Operation *op,
234 SmallVectorImpl<Value> &results,
235 int maxIterations) {
236 SmallVector<OpFoldResult, 8> foldResults;
237 if (failed(Result: op->fold(results&: foldResults)))
238 return failure();
239 int count = 1;
240 do {
241 LDBG() << "Folded in place #" << count
242 << " times: " << OpWithFlags(op, OpPrintingFlags().skipRegions());
243 } while (count++ < maxIterations && foldResults.empty() &&
244 succeeded(Result: op->fold(results&: foldResults)));
245
246 if (failed(Result: processFoldResults(op, results, foldResults)))
247 return failure();
248 return success();
249}
250
251LogicalResult
252OperationFolder::processFoldResults(Operation *op,
253 SmallVectorImpl<Value> &results,
254 ArrayRef<OpFoldResult> foldResults) {
255 // Check to see if the operation was just updated in place.
256 if (foldResults.empty())
257 return success();
258 assert(foldResults.size() == op->getNumResults());
259
260 // Create a builder to insert new operations into the entry block of the
261 // insertion region.
262 auto *insertRegion = getInsertionRegion(interfaces, insertionBlock: op->getBlock());
263 auto &entry = insertRegion->front();
264 rewriter.setInsertionPointToStart(&entry);
265
266 // Get the constant map for the insertion region of this operation.
267 auto &uniquedConstants = foldScopes[insertRegion];
268
269 // Create the result constants and replace the results.
270 auto *dialect = op->getDialect();
271 for (unsigned i = 0, e = op->getNumResults(); i != e; ++i) {
272 assert(!foldResults[i].isNull() && "expected valid OpFoldResult");
273
274 // Check if the result was an SSA value.
275 if (auto repl = llvm::dyn_cast_if_present<Value>(Val: foldResults[i])) {
276 results.emplace_back(Args&: repl);
277 continue;
278 }
279
280 // Check to see if there is a canonicalized version of this constant.
281 auto res = op->getResult(idx: i);
282 Attribute attrRepl = cast<Attribute>(Val: foldResults[i]);
283 if (auto *constOp =
284 tryGetOrCreateConstant(uniquedConstants, dialect, value: attrRepl,
285 type: res.getType(), loc: erasedFoldedLocation)) {
286 // Ensure that this constant dominates the operation we are replacing it
287 // with. This may not automatically happen if the operation being folded
288 // was inserted before the constant within the insertion block.
289 Block *opBlock = op->getBlock();
290 if (opBlock == constOp->getBlock() && &opBlock->front() != constOp)
291 rewriter.moveOpBefore(op: constOp, existingOp: &opBlock->front());
292
293 results.push_back(Elt: constOp->getResult(idx: 0));
294 continue;
295 }
296 // If materialization fails, cleanup any operations generated for the
297 // previous results and return failure.
298 for (Operation &op : llvm::make_early_inc_range(
299 Range: llvm::make_range(x: entry.begin(), y: rewriter.getInsertionPoint()))) {
300 notifyRemoval(op: &op);
301 rewriter.eraseOp(op: &op);
302 }
303
304 results.clear();
305 return failure();
306 }
307
308 return success();
309}
310
311/// Try to get or create a new constant entry. On success this returns the
312/// constant operation value, nullptr otherwise.
313Operation *
314OperationFolder::tryGetOrCreateConstant(ConstantMap &uniquedConstants,
315 Dialect *dialect, Attribute value,
316 Type type, Location loc) {
317 // Check if an existing mapping already exists.
318 auto constKey = std::make_tuple(args&: dialect, args&: value, args&: type);
319 Operation *&constOp = uniquedConstants[constKey];
320 if (constOp) {
321 if (loc != constOp->getLoc())
322 constOp->setLoc(erasedFoldedLocation);
323 return constOp;
324 }
325
326 // If one doesn't exist, try to materialize one.
327 if (!(constOp = materializeConstant(dialect, builder&: rewriter, value, type, loc)))
328 return nullptr;
329
330 // Check to see if the generated constant is in the expected dialect.
331 auto *newDialect = constOp->getDialect();
332 if (newDialect == dialect) {
333 referencedDialects[constOp].push_back(Elt: dialect);
334 return constOp;
335 }
336
337 // If it isn't, then we also need to make sure that the mapping for the new
338 // dialect is valid.
339 auto newKey = std::make_tuple(args&: newDialect, args&: value, args&: type);
340
341 // If an existing operation in the new dialect already exists, delete the
342 // materialized operation in favor of the existing one.
343 if (auto *existingOp = uniquedConstants.lookup(Val: newKey)) {
344 notifyRemoval(op: constOp);
345 rewriter.eraseOp(op: constOp);
346 referencedDialects[existingOp].push_back(Elt: dialect);
347 if (loc != existingOp->getLoc())
348 existingOp->setLoc(erasedFoldedLocation);
349 return constOp = existingOp;
350 }
351
352 // Otherwise, update the new dialect to the materialized operation.
353 referencedDialects[constOp].assign(IL: {dialect, newDialect});
354 auto newIt = uniquedConstants.insert(KV: {newKey, constOp});
355 return newIt.first->second;
356}
357