| 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 | |
| 21 | using namespace mlir; |
| 22 | |
| 23 | /// Given an operation, find the parent region that folded constants should be |
| 24 | /// inserted into. |
| 25 | static Region * |
| 26 | getInsertionRegion(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 |
| 51 | static 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 | |
| 71 | LogicalResult 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 | |
| 113 | OperationFolder::ConstantInsertionResult |
| 114 | OperationFolder::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. |
| 181 | void 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. |
| 205 | void 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. |
| 212 | Value 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 | |
| 227 | bool 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. |
| 233 | LogicalResult 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 | |
| 251 | LogicalResult |
| 252 | OperationFolder::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. |
| 313 | Operation * |
| 314 | OperationFolder::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 | |