| 1 | //===- SCFTransformOps.cpp - Implementation of SCF transformation ops -----===// |
| 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 | #include "mlir/Dialect/SCF/TransformOps/SCFTransformOps.h" |
| 10 | |
| 11 | #include "mlir/Conversion/SCFToControlFlow/SCFToControlFlow.h" |
| 12 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 13 | #include "mlir/Dialect/Affine/LoopUtils.h" |
| 14 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 15 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 16 | #include "mlir/Dialect/SCF/Transforms/Patterns.h" |
| 17 | #include "mlir/Dialect/SCF/Transforms/Transforms.h" |
| 18 | #include "mlir/Dialect/SCF/Utils/Utils.h" |
| 19 | #include "mlir/Dialect/Transform/IR/TransformDialect.h" |
| 20 | #include "mlir/Dialect/Transform/Interfaces/TransformInterfaces.h" |
| 21 | #include "mlir/Dialect/Utils/StaticValueUtils.h" |
| 22 | #include "mlir/Dialect/Vector/IR/VectorOps.h" |
| 23 | #include "mlir/IR/BuiltinAttributes.h" |
| 24 | #include "mlir/IR/Dominance.h" |
| 25 | #include "mlir/IR/OpDefinition.h" |
| 26 | |
| 27 | using namespace mlir; |
| 28 | using namespace mlir::affine; |
| 29 | |
| 30 | //===----------------------------------------------------------------------===// |
| 31 | // Apply...PatternsOp |
| 32 | //===----------------------------------------------------------------------===// |
| 33 | |
| 34 | void transform::ApplyForLoopCanonicalizationPatternsOp::populatePatterns( |
| 35 | RewritePatternSet &patterns) { |
| 36 | scf::populateSCFForLoopCanonicalizationPatterns(patterns); |
| 37 | } |
| 38 | |
| 39 | void transform::ApplySCFStructuralConversionPatternsOp::populatePatterns( |
| 40 | TypeConverter &typeConverter, RewritePatternSet &patterns) { |
| 41 | scf::populateSCFStructuralTypeConversions(typeConverter, patterns); |
| 42 | } |
| 43 | |
| 44 | void transform::ApplySCFStructuralConversionPatternsOp:: |
| 45 | populateConversionTargetRules(const TypeConverter &typeConverter, |
| 46 | ConversionTarget &conversionTarget) { |
| 47 | scf::populateSCFStructuralTypeConversionTarget(typeConverter, |
| 48 | target&: conversionTarget); |
| 49 | } |
| 50 | |
| 51 | void transform::ApplySCFToControlFlowPatternsOp::populatePatterns( |
| 52 | TypeConverter &typeConverter, RewritePatternSet &patterns) { |
| 53 | populateSCFToControlFlowConversionPatterns(patterns); |
| 54 | } |
| 55 | |
| 56 | //===----------------------------------------------------------------------===// |
| 57 | // ForallToForOp |
| 58 | //===----------------------------------------------------------------------===// |
| 59 | |
| 60 | DiagnosedSilenceableFailure |
| 61 | transform::ForallToForOp::apply(transform::TransformRewriter &rewriter, |
| 62 | transform::TransformResults &results, |
| 63 | transform::TransformState &state) { |
| 64 | auto payload = state.getPayloadOps(value: getTarget()); |
| 65 | if (!llvm::hasSingleElement(C&: payload)) |
| 66 | return emitSilenceableError() << "expected a single payload op" ; |
| 67 | |
| 68 | auto target = dyn_cast<scf::ForallOp>(Val: *payload.begin()); |
| 69 | if (!target) { |
| 70 | DiagnosedSilenceableFailure diag = |
| 71 | emitSilenceableError() << "expected the payload to be scf.forall" ; |
| 72 | diag.attachNote(loc: (*payload.begin())->getLoc()) << "payload op" ; |
| 73 | return diag; |
| 74 | } |
| 75 | |
| 76 | if (!target.getOutputs().empty()) { |
| 77 | return emitSilenceableError() |
| 78 | << "unsupported shared outputs (didn't bufferize?)" ; |
| 79 | } |
| 80 | |
| 81 | SmallVector<OpFoldResult> lbs = target.getMixedLowerBound(); |
| 82 | |
| 83 | if (getNumResults() != lbs.size()) { |
| 84 | DiagnosedSilenceableFailure diag = |
| 85 | emitSilenceableError() |
| 86 | << "op expects as many results (" << getNumResults() |
| 87 | << ") as payload has induction variables (" << lbs.size() << ")" ; |
| 88 | diag.attachNote(loc: target.getLoc()) << "payload op" ; |
| 89 | return diag; |
| 90 | } |
| 91 | |
| 92 | SmallVector<Operation *> opResults; |
| 93 | if (failed(Result: scf::forallToForLoop(rewriter, forallOp: target, results: &opResults))) { |
| 94 | DiagnosedSilenceableFailure diag = emitSilenceableError() |
| 95 | << "failed to convert forall into for" ; |
| 96 | return diag; |
| 97 | } |
| 98 | |
| 99 | for (auto &&[i, res] : llvm::enumerate(First&: opResults)) { |
| 100 | results.set(value: cast<OpResult>(Val: getTransformed()[i]), ops: {res}); |
| 101 | } |
| 102 | return DiagnosedSilenceableFailure::success(); |
| 103 | } |
| 104 | |
| 105 | //===----------------------------------------------------------------------===// |
| 106 | // ForallToForOp |
| 107 | //===----------------------------------------------------------------------===// |
| 108 | |
| 109 | DiagnosedSilenceableFailure |
| 110 | transform::ForallToParallelOp::apply(transform::TransformRewriter &rewriter, |
| 111 | transform::TransformResults &results, |
| 112 | transform::TransformState &state) { |
| 113 | auto payload = state.getPayloadOps(value: getTarget()); |
| 114 | if (!llvm::hasSingleElement(C&: payload)) |
| 115 | return emitSilenceableError() << "expected a single payload op" ; |
| 116 | |
| 117 | auto target = dyn_cast<scf::ForallOp>(Val: *payload.begin()); |
| 118 | if (!target) { |
| 119 | DiagnosedSilenceableFailure diag = |
| 120 | emitSilenceableError() << "expected the payload to be scf.forall" ; |
| 121 | diag.attachNote(loc: (*payload.begin())->getLoc()) << "payload op" ; |
| 122 | return diag; |
| 123 | } |
| 124 | |
| 125 | if (!target.getOutputs().empty()) { |
| 126 | return emitSilenceableError() |
| 127 | << "unsupported shared outputs (didn't bufferize?)" ; |
| 128 | } |
| 129 | |
| 130 | if (getNumResults() != 1) { |
| 131 | DiagnosedSilenceableFailure diag = emitSilenceableError() |
| 132 | << "op expects one result, given " |
| 133 | << getNumResults(); |
| 134 | diag.attachNote(loc: target.getLoc()) << "payload op" ; |
| 135 | return diag; |
| 136 | } |
| 137 | |
| 138 | scf::ParallelOp opResult; |
| 139 | if (failed(Result: scf::forallToParallelLoop(rewriter, forallOp: target, result: &opResult))) { |
| 140 | DiagnosedSilenceableFailure diag = |
| 141 | emitSilenceableError() << "failed to convert forall into parallel" ; |
| 142 | return diag; |
| 143 | } |
| 144 | |
| 145 | results.set(value: cast<OpResult>(Val: getTransformed()[0]), ops: {opResult}); |
| 146 | return DiagnosedSilenceableFailure::success(); |
| 147 | } |
| 148 | |
| 149 | //===----------------------------------------------------------------------===// |
| 150 | // ParallelForToNestedForOps |
| 151 | //===----------------------------------------------------------------------===// |
| 152 | |
| 153 | DiagnosedSilenceableFailure transform::ParallelForToNestedForOps::apply( |
| 154 | transform::TransformRewriter &rewriter, |
| 155 | transform::TransformResults &results, transform::TransformState &state) { |
| 156 | auto payload = state.getPayloadOps(value: getTarget()); |
| 157 | if (!llvm::hasSingleElement(C&: payload)) |
| 158 | return emitSilenceableError() << "expected a single payload op" ; |
| 159 | |
| 160 | auto target = dyn_cast<scf::ParallelOp>(Val: *payload.begin()); |
| 161 | if (!target) { |
| 162 | DiagnosedSilenceableFailure diag = |
| 163 | emitSilenceableError() << "expected the payload to be scf.parallel" ; |
| 164 | diag.attachNote(loc: (*payload.begin())->getLoc()) << "payload op" ; |
| 165 | return diag; |
| 166 | } |
| 167 | |
| 168 | if (getNumResults() != 1) { |
| 169 | DiagnosedSilenceableFailure diag = emitSilenceableError() |
| 170 | << "op expects one result, given " |
| 171 | << getNumResults(); |
| 172 | diag.attachNote(loc: target.getLoc()) << "payload op" ; |
| 173 | return diag; |
| 174 | } |
| 175 | |
| 176 | FailureOr<scf::LoopNest> loopNest = |
| 177 | scf::parallelForToNestedFors(rewriter, parallelOp: target); |
| 178 | if (failed(Result: loopNest)) { |
| 179 | DiagnosedSilenceableFailure diag = |
| 180 | emitSilenceableError() << "failed to convert parallel into nested fors" ; |
| 181 | return diag; |
| 182 | } |
| 183 | |
| 184 | results.set(value: cast<OpResult>(Val: getTransformed()[0]), ops: {loopNest->loops.front()}); |
| 185 | return DiagnosedSilenceableFailure::success(); |
| 186 | } |
| 187 | |
| 188 | //===----------------------------------------------------------------------===// |
| 189 | // LoopOutlineOp |
| 190 | //===----------------------------------------------------------------------===// |
| 191 | |
| 192 | /// Wraps the given operation `op` into an `scf.execute_region` operation. Uses |
| 193 | /// the provided rewriter for all operations to remain compatible with the |
| 194 | /// rewriting infra, as opposed to just splicing the op in place. |
| 195 | static scf::ExecuteRegionOp wrapInExecuteRegion(RewriterBase &b, |
| 196 | Operation *op) { |
| 197 | if (op->getNumRegions() != 1) |
| 198 | return nullptr; |
| 199 | OpBuilder::InsertionGuard g(b); |
| 200 | b.setInsertionPoint(op); |
| 201 | scf::ExecuteRegionOp executeRegionOp = |
| 202 | scf::ExecuteRegionOp::create(builder&: b, location: op->getLoc(), resultType0: op->getResultTypes()); |
| 203 | { |
| 204 | OpBuilder::InsertionGuard g(b); |
| 205 | b.setInsertionPointToStart(&executeRegionOp.getRegion().emplaceBlock()); |
| 206 | Operation *clonedOp = b.cloneWithoutRegions(op&: *op); |
| 207 | Region &clonedRegion = clonedOp->getRegions().front(); |
| 208 | assert(clonedRegion.empty() && "expected empty region" ); |
| 209 | b.inlineRegionBefore(region&: op->getRegions().front(), parent&: clonedRegion, |
| 210 | before: clonedRegion.end()); |
| 211 | scf::YieldOp::create(builder&: b, location: op->getLoc(), results: clonedOp->getResults()); |
| 212 | } |
| 213 | b.replaceOp(op, newValues: executeRegionOp.getResults()); |
| 214 | return executeRegionOp; |
| 215 | } |
| 216 | |
| 217 | DiagnosedSilenceableFailure |
| 218 | transform::LoopOutlineOp::apply(transform::TransformRewriter &rewriter, |
| 219 | transform::TransformResults &results, |
| 220 | transform::TransformState &state) { |
| 221 | SmallVector<Operation *> functions; |
| 222 | SmallVector<Operation *> calls; |
| 223 | DenseMap<Operation *, SymbolTable> symbolTables; |
| 224 | for (Operation *target : state.getPayloadOps(value: getTarget())) { |
| 225 | Location location = target->getLoc(); |
| 226 | Operation *symbolTableOp = SymbolTable::getNearestSymbolTable(from: target); |
| 227 | scf::ExecuteRegionOp exec = wrapInExecuteRegion(b&: rewriter, op: target); |
| 228 | if (!exec) { |
| 229 | DiagnosedSilenceableFailure diag = emitSilenceableError() |
| 230 | << "failed to outline" ; |
| 231 | diag.attachNote(loc: target->getLoc()) << "target op" ; |
| 232 | return diag; |
| 233 | } |
| 234 | func::CallOp call; |
| 235 | FailureOr<func::FuncOp> outlined = outlineSingleBlockRegion( |
| 236 | rewriter, loc: location, region&: exec.getRegion(), funcName: getFuncName(), callOp: &call); |
| 237 | |
| 238 | if (failed(Result: outlined)) |
| 239 | return emitDefaultDefiniteFailure(target); |
| 240 | |
| 241 | if (symbolTableOp) { |
| 242 | SymbolTable &symbolTable = |
| 243 | symbolTables.try_emplace(Key: symbolTableOp, Args&: symbolTableOp) |
| 244 | .first->getSecond(); |
| 245 | symbolTable.insert(symbol: *outlined); |
| 246 | call.setCalleeAttr(FlatSymbolRefAttr::get(symbol: *outlined)); |
| 247 | } |
| 248 | functions.push_back(Elt: *outlined); |
| 249 | calls.push_back(Elt: call); |
| 250 | } |
| 251 | results.set(value: cast<OpResult>(Val: getFunction()), ops&: functions); |
| 252 | results.set(value: cast<OpResult>(Val: getCall()), ops&: calls); |
| 253 | return DiagnosedSilenceableFailure::success(); |
| 254 | } |
| 255 | |
| 256 | //===----------------------------------------------------------------------===// |
| 257 | // LoopPeelOp |
| 258 | //===----------------------------------------------------------------------===// |
| 259 | |
| 260 | DiagnosedSilenceableFailure |
| 261 | transform::LoopPeelOp::applyToOne(transform::TransformRewriter &rewriter, |
| 262 | scf::ForOp target, |
| 263 | transform::ApplyToEachResultList &results, |
| 264 | transform::TransformState &state) { |
| 265 | scf::ForOp result; |
| 266 | if (getPeelFront()) { |
| 267 | LogicalResult status = |
| 268 | scf::peelForLoopFirstIteration(rewriter, forOp: target, partialIteration&: result); |
| 269 | if (failed(Result: status)) { |
| 270 | DiagnosedSilenceableFailure diag = |
| 271 | emitSilenceableError() << "failed to peel the first iteration" ; |
| 272 | return diag; |
| 273 | } |
| 274 | } else { |
| 275 | LogicalResult status = |
| 276 | scf::peelForLoopAndSimplifyBounds(rewriter, forOp: target, partialIteration&: result); |
| 277 | if (failed(Result: status)) { |
| 278 | DiagnosedSilenceableFailure diag = emitSilenceableError() |
| 279 | << "failed to peel the last iteration" ; |
| 280 | return diag; |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | results.push_back(op: target); |
| 285 | if (getPartialAsIf()) |
| 286 | results.push_back(op: scf::convertPartialIterationToIf(rewriter, partialIteration: result)); |
| 287 | else |
| 288 | results.push_back(op: result); |
| 289 | |
| 290 | return DiagnosedSilenceableFailure::success(); |
| 291 | } |
| 292 | |
| 293 | //===----------------------------------------------------------------------===// |
| 294 | // LoopPipelineOp |
| 295 | //===----------------------------------------------------------------------===// |
| 296 | |
| 297 | /// Callback for PipeliningOption. Populates `schedule` with the mapping from an |
| 298 | /// operation to its logical time position given the iteration interval and the |
| 299 | /// read latency. The latter is only relevant for vector transfers. |
| 300 | static void |
| 301 | loopScheduling(scf::ForOp forOp, |
| 302 | std::vector<std::pair<Operation *, unsigned>> &schedule, |
| 303 | unsigned iterationInterval, unsigned readLatency) { |
| 304 | auto getLatency = [&](Operation *op) -> unsigned { |
| 305 | if (isa<vector::TransferReadOp>(Val: op)) |
| 306 | return readLatency; |
| 307 | return 1; |
| 308 | }; |
| 309 | |
| 310 | std::optional<int64_t> ubConstant = |
| 311 | getConstantIntValue(ofr: forOp.getUpperBound()); |
| 312 | std::optional<int64_t> lbConstant = |
| 313 | getConstantIntValue(ofr: forOp.getLowerBound()); |
| 314 | DenseMap<Operation *, unsigned> opCycles; |
| 315 | std::map<unsigned, std::vector<Operation *>> wrappedSchedule; |
| 316 | for (Operation &op : forOp.getBody()->getOperations()) { |
| 317 | if (isa<scf::YieldOp>(Val: op)) |
| 318 | continue; |
| 319 | unsigned earlyCycle = 0; |
| 320 | for (Value operand : op.getOperands()) { |
| 321 | Operation *def = operand.getDefiningOp(); |
| 322 | if (!def) |
| 323 | continue; |
| 324 | if (ubConstant && lbConstant) { |
| 325 | unsigned ubInt = ubConstant.value(); |
| 326 | unsigned lbInt = lbConstant.value(); |
| 327 | auto minLatency = std::min(a: ubInt - lbInt - 1, b: getLatency(def)); |
| 328 | earlyCycle = std::max(a: earlyCycle, b: opCycles[def] + minLatency); |
| 329 | } else { |
| 330 | earlyCycle = std::max(a: earlyCycle, b: opCycles[def] + getLatency(def)); |
| 331 | } |
| 332 | } |
| 333 | opCycles[&op] = earlyCycle; |
| 334 | wrappedSchedule[earlyCycle % iterationInterval].push_back(x: &op); |
| 335 | } |
| 336 | for (const auto &it : wrappedSchedule) { |
| 337 | for (Operation *op : it.second) { |
| 338 | unsigned cycle = opCycles[op]; |
| 339 | schedule.emplace_back(args&: op, args: cycle / iterationInterval); |
| 340 | } |
| 341 | } |
| 342 | } |
| 343 | |
| 344 | DiagnosedSilenceableFailure |
| 345 | transform::LoopPipelineOp::applyToOne(transform::TransformRewriter &rewriter, |
| 346 | scf::ForOp target, |
| 347 | transform::ApplyToEachResultList &results, |
| 348 | transform::TransformState &state) { |
| 349 | scf::PipeliningOption options; |
| 350 | options.getScheduleFn = |
| 351 | [this](scf::ForOp forOp, |
| 352 | std::vector<std::pair<Operation *, unsigned>> &schedule) mutable { |
| 353 | loopScheduling(forOp, schedule, iterationInterval: getIterationInterval(), |
| 354 | readLatency: getReadLatency()); |
| 355 | }; |
| 356 | scf::ForLoopPipeliningPattern pattern(options, target->getContext()); |
| 357 | rewriter.setInsertionPoint(target); |
| 358 | FailureOr<scf::ForOp> patternResult = |
| 359 | scf::pipelineForLoop(rewriter, forOp: target, options); |
| 360 | if (succeeded(Result: patternResult)) { |
| 361 | results.push_back(op: *patternResult); |
| 362 | return DiagnosedSilenceableFailure::success(); |
| 363 | } |
| 364 | return emitDefaultSilenceableFailure(target); |
| 365 | } |
| 366 | |
| 367 | //===----------------------------------------------------------------------===// |
| 368 | // LoopPromoteIfOneIterationOp |
| 369 | //===----------------------------------------------------------------------===// |
| 370 | |
| 371 | DiagnosedSilenceableFailure transform::LoopPromoteIfOneIterationOp::applyToOne( |
| 372 | transform::TransformRewriter &rewriter, LoopLikeOpInterface target, |
| 373 | transform::ApplyToEachResultList &results, |
| 374 | transform::TransformState &state) { |
| 375 | (void)target.promoteIfSingleIteration(rewriter); |
| 376 | return DiagnosedSilenceableFailure::success(); |
| 377 | } |
| 378 | |
| 379 | void transform::LoopPromoteIfOneIterationOp::getEffects( |
| 380 | SmallVectorImpl<MemoryEffects::EffectInstance> &effects) { |
| 381 | consumesHandle(handles: getTargetMutable(), effects); |
| 382 | modifiesPayload(effects); |
| 383 | } |
| 384 | |
| 385 | //===----------------------------------------------------------------------===// |
| 386 | // LoopUnrollOp |
| 387 | //===----------------------------------------------------------------------===// |
| 388 | |
| 389 | DiagnosedSilenceableFailure |
| 390 | transform::LoopUnrollOp::applyToOne(transform::TransformRewriter &rewriter, |
| 391 | Operation *op, |
| 392 | transform::ApplyToEachResultList &results, |
| 393 | transform::TransformState &state) { |
| 394 | LogicalResult result(failure()); |
| 395 | if (scf::ForOp scfFor = dyn_cast<scf::ForOp>(Val: op)) |
| 396 | result = loopUnrollByFactor(forOp: scfFor, unrollFactor: getFactor()); |
| 397 | else if (AffineForOp affineFor = dyn_cast<AffineForOp>(Val: op)) |
| 398 | result = loopUnrollByFactor(forOp: affineFor, unrollFactor: getFactor()); |
| 399 | else |
| 400 | return emitSilenceableError() |
| 401 | << "failed to unroll, incorrect type of payload" ; |
| 402 | |
| 403 | if (failed(Result: result)) |
| 404 | return emitSilenceableError() << "failed to unroll" ; |
| 405 | |
| 406 | return DiagnosedSilenceableFailure::success(); |
| 407 | } |
| 408 | |
| 409 | //===----------------------------------------------------------------------===// |
| 410 | // LoopUnrollFullOp |
| 411 | //===----------------------------------------------------------------------===// |
| 412 | |
| 413 | DiagnosedSilenceableFailure transform::LoopUnrollFullOp::applyToOne( |
| 414 | transform::TransformRewriter &rewriter, Operation *op, |
| 415 | transform::ApplyToEachResultList &results, |
| 416 | transform::TransformState &state) { |
| 417 | LogicalResult result(failure()); |
| 418 | if (scf::ForOp scfFor = dyn_cast<scf::ForOp>(Val: op)) |
| 419 | result = loopUnrollFull(forOp: scfFor); |
| 420 | else if (AffineForOp affineFor = dyn_cast<AffineForOp>(Val: op)) |
| 421 | result = loopUnrollFull(forOp: affineFor); |
| 422 | else |
| 423 | return emitSilenceableError() |
| 424 | << "failed to fully unroll, incorrect type of payload" ; |
| 425 | |
| 426 | if (failed(Result: result)) |
| 427 | return emitSilenceableError() << "failed to fully unroll" ; |
| 428 | |
| 429 | return DiagnosedSilenceableFailure::success(); |
| 430 | } |
| 431 | |
| 432 | //===----------------------------------------------------------------------===// |
| 433 | // LoopUnrollAndJamOp |
| 434 | //===----------------------------------------------------------------------===// |
| 435 | |
| 436 | DiagnosedSilenceableFailure transform::LoopUnrollAndJamOp::applyToOne( |
| 437 | transform::TransformRewriter &rewriter, Operation *op, |
| 438 | transform::ApplyToEachResultList &results, |
| 439 | transform::TransformState &state) { |
| 440 | LogicalResult result(failure()); |
| 441 | if (scf::ForOp scfFor = dyn_cast<scf::ForOp>(Val: op)) |
| 442 | result = loopUnrollJamByFactor(forOp: scfFor, unrollFactor: getFactor()); |
| 443 | else if (AffineForOp affineFor = dyn_cast<AffineForOp>(Val: op)) |
| 444 | result = loopUnrollJamByFactor(forOp: affineFor, unrollJamFactor: getFactor()); |
| 445 | else |
| 446 | return emitSilenceableError() |
| 447 | << "failed to unroll and jam, incorrect type of payload" ; |
| 448 | |
| 449 | if (failed(Result: result)) |
| 450 | return emitSilenceableError() << "failed to unroll and jam" ; |
| 451 | |
| 452 | return DiagnosedSilenceableFailure::success(); |
| 453 | } |
| 454 | |
| 455 | //===----------------------------------------------------------------------===// |
| 456 | // LoopCoalesceOp |
| 457 | //===----------------------------------------------------------------------===// |
| 458 | |
| 459 | DiagnosedSilenceableFailure |
| 460 | transform::LoopCoalesceOp::applyToOne(transform::TransformRewriter &rewriter, |
| 461 | Operation *op, |
| 462 | transform::ApplyToEachResultList &results, |
| 463 | transform::TransformState &state) { |
| 464 | LogicalResult result(failure()); |
| 465 | if (scf::ForOp scfForOp = dyn_cast<scf::ForOp>(Val: op)) |
| 466 | result = coalescePerfectlyNestedSCFForLoops(op: scfForOp); |
| 467 | else if (AffineForOp affineForOp = dyn_cast<AffineForOp>(Val: op)) |
| 468 | result = coalescePerfectlyNestedAffineLoops(op: affineForOp); |
| 469 | |
| 470 | results.push_back(op); |
| 471 | if (failed(Result: result)) { |
| 472 | DiagnosedSilenceableFailure diag = emitSilenceableError() |
| 473 | << "failed to coalesce" ; |
| 474 | return diag; |
| 475 | } |
| 476 | return DiagnosedSilenceableFailure::success(); |
| 477 | } |
| 478 | |
| 479 | //===----------------------------------------------------------------------===// |
| 480 | // LoopCoalesceNestedOp |
| 481 | //===----------------------------------------------------------------------===// |
| 482 | DiagnosedSilenceableFailure transform::LoopCoalesceNestedOp::applyToOne( |
| 483 | transform::TransformRewriter &rewriter, Operation *op, |
| 484 | transform::ApplyToEachResultList &results, |
| 485 | transform::TransformState &state) { |
| 486 | auto forOp = dyn_cast<scf::ForOp>(Val: op); |
| 487 | if (!forOp) { |
| 488 | return emitSilenceableError() << "expected scf.for operation" ; |
| 489 | } |
| 490 | |
| 491 | // Collect nested loops (including imperfectly nested ones) |
| 492 | SmallVector<scf::ForOp> nestedLoops; |
| 493 | scf::ForOp currentLoop = forOp; |
| 494 | |
| 495 | while (currentLoop) { |
| 496 | nestedLoops.push_back(Elt: currentLoop); |
| 497 | Block &body = currentLoop.getRegion().front(); |
| 498 | |
| 499 | // Look for the next nested loop |
| 500 | scf::ForOp nextLoop = nullptr; |
| 501 | for (Operation &bodyOp : body) { |
| 502 | if (auto innerFor = dyn_cast<scf::ForOp>(Val: &bodyOp)) { |
| 503 | nextLoop = innerFor; |
| 504 | break; |
| 505 | } |
| 506 | } |
| 507 | |
| 508 | currentLoop = nextLoop; |
| 509 | } |
| 510 | |
| 511 | // Need at least 2 loops to coalesce |
| 512 | if (nestedLoops.size() < 2) { |
| 513 | return emitSilenceableError() << "need at least 2 nested loops to coalesce" ; |
| 514 | } |
| 515 | |
| 516 | // Call coalesceLoops directly |
| 517 | if (failed(Result: coalesceLoops(rewriter, nestedLoops))) { |
| 518 | return emitSilenceableError() << "failed to coalesce nested loops" ; |
| 519 | } |
| 520 | |
| 521 | results.push_back(op: nestedLoops.front()); |
| 522 | return DiagnosedSilenceableFailure::success(); |
| 523 | } |
| 524 | |
| 525 | //===----------------------------------------------------------------------===// |
| 526 | // TakeAssumedBranchOp |
| 527 | //===----------------------------------------------------------------------===// |
| 528 | /// Replaces the given op with the contents of the given single-block region, |
| 529 | /// using the operands of the block terminator to replace operation results. |
| 530 | static void replaceOpWithRegion(RewriterBase &rewriter, Operation *op, |
| 531 | Region ®ion) { |
| 532 | assert(region.hasOneBlock() && "expected single-block region" ); |
| 533 | Block *block = ®ion.front(); |
| 534 | Operation *terminator = block->getTerminator(); |
| 535 | ValueRange results = terminator->getOperands(); |
| 536 | rewriter.inlineBlockBefore(source: block, op, /*blockArgs=*/argValues: {}); |
| 537 | rewriter.replaceOp(op, newValues: results); |
| 538 | rewriter.eraseOp(op: terminator); |
| 539 | } |
| 540 | |
| 541 | DiagnosedSilenceableFailure transform::TakeAssumedBranchOp::applyToOne( |
| 542 | transform::TransformRewriter &rewriter, scf::IfOp ifOp, |
| 543 | transform::ApplyToEachResultList &results, |
| 544 | transform::TransformState &state) { |
| 545 | rewriter.setInsertionPoint(ifOp); |
| 546 | Region ®ion = |
| 547 | getTakeElseBranch() ? ifOp.getElseRegion() : ifOp.getThenRegion(); |
| 548 | if (!region.hasOneBlock()) { |
| 549 | return emitDefiniteFailure() |
| 550 | << "requires an scf.if op with a single-block " |
| 551 | << ((getTakeElseBranch()) ? "`else`" : "`then`" ) << " region" ; |
| 552 | } |
| 553 | replaceOpWithRegion(rewriter, op: ifOp, region); |
| 554 | return DiagnosedSilenceableFailure::success(); |
| 555 | } |
| 556 | |
| 557 | void transform::TakeAssumedBranchOp::getEffects( |
| 558 | SmallVectorImpl<MemoryEffects::EffectInstance> &effects) { |
| 559 | onlyReadsHandle(handles: getTargetMutable(), effects); |
| 560 | modifiesPayload(effects); |
| 561 | } |
| 562 | |
| 563 | //===----------------------------------------------------------------------===// |
| 564 | // LoopFuseSiblingOp |
| 565 | //===----------------------------------------------------------------------===// |
| 566 | |
| 567 | /// Check if `target` and `source` are siblings, in the context that `target` |
| 568 | /// is being fused into `source`. |
| 569 | /// |
| 570 | /// This is a simple check that just checks if both operations are in the same |
| 571 | /// block and some checks to ensure that the fused IR does not violate |
| 572 | /// dominance. |
| 573 | static DiagnosedSilenceableFailure isOpSibling(Operation *target, |
| 574 | Operation *source) { |
| 575 | // Check if both operations are same. |
| 576 | if (target == source) |
| 577 | return emitSilenceableFailure(op: source) |
| 578 | << "target and source need to be different loops" ; |
| 579 | |
| 580 | // Check if both operations are in the same block. |
| 581 | if (target->getBlock() != source->getBlock()) |
| 582 | return emitSilenceableFailure(op: source) |
| 583 | << "target and source are not in the same block" ; |
| 584 | |
| 585 | // Check if fusion will violate dominance. |
| 586 | DominanceInfo domInfo(source); |
| 587 | if (target->isBeforeInBlock(other: source)) { |
| 588 | // Since `target` is before `source`, all users of results of `target` |
| 589 | // need to be dominated by `source`. |
| 590 | for (Operation *user : target->getUsers()) { |
| 591 | if (!domInfo.properlyDominates(a: source, b: user, /*enclosingOpOk=*/false)) { |
| 592 | return emitSilenceableFailure(op: target) |
| 593 | << "user of results of target should be properly dominated by " |
| 594 | "source" ; |
| 595 | } |
| 596 | } |
| 597 | } else { |
| 598 | // Since `target` is after `source`, all values used by `target` need |
| 599 | // to dominate `source`. |
| 600 | |
| 601 | // Check if operands of `target` are dominated by `source`. |
| 602 | for (Value operand : target->getOperands()) { |
| 603 | Operation *operandOp = operand.getDefiningOp(); |
| 604 | // Operands without defining operations are block arguments. When `target` |
| 605 | // and `source` occur in the same block, these operands dominate `source`. |
| 606 | if (!operandOp) |
| 607 | continue; |
| 608 | |
| 609 | // Operand's defining operation should properly dominate `source`. |
| 610 | if (!domInfo.properlyDominates(a: operandOp, b: source, |
| 611 | /*enclosingOpOk=*/false)) |
| 612 | return emitSilenceableFailure(op: target) |
| 613 | << "operands of target should be properly dominated by source" ; |
| 614 | } |
| 615 | |
| 616 | // Check if values used by `target` are dominated by `source`. |
| 617 | bool failed = false; |
| 618 | OpOperand *failedValue = nullptr; |
| 619 | visitUsedValuesDefinedAbove(regions: target->getRegions(), callback: [&](OpOperand *operand) { |
| 620 | Operation *operandOp = operand->get().getDefiningOp(); |
| 621 | if (operandOp && !domInfo.properlyDominates(a: operandOp, b: source, |
| 622 | /*enclosingOpOk=*/false)) { |
| 623 | // `operand` is not an argument of an enclosing block and the defining |
| 624 | // op of `operand` is outside `target` but does not dominate `source`. |
| 625 | failed = true; |
| 626 | failedValue = operand; |
| 627 | } |
| 628 | }); |
| 629 | |
| 630 | if (failed) |
| 631 | return emitSilenceableFailure(op: failedValue->getOwner()) |
| 632 | << "values used inside regions of target should be properly " |
| 633 | "dominated by source" ; |
| 634 | } |
| 635 | |
| 636 | return DiagnosedSilenceableFailure::success(); |
| 637 | } |
| 638 | |
| 639 | /// Check if `target` scf.forall can be fused into `source` scf.forall. |
| 640 | /// |
| 641 | /// This simply checks if both loops have the same bounds, steps and mapping. |
| 642 | /// No attempt is made at checking that the side effects of `target` and |
| 643 | /// `source` are independent of each other. |
| 644 | static bool isForallWithIdenticalConfiguration(Operation *target, |
| 645 | Operation *source) { |
| 646 | auto targetOp = dyn_cast<scf::ForallOp>(Val: target); |
| 647 | auto sourceOp = dyn_cast<scf::ForallOp>(Val: source); |
| 648 | if (!targetOp || !sourceOp) |
| 649 | return false; |
| 650 | |
| 651 | return targetOp.getMixedLowerBound() == sourceOp.getMixedLowerBound() && |
| 652 | targetOp.getMixedUpperBound() == sourceOp.getMixedUpperBound() && |
| 653 | targetOp.getMixedStep() == sourceOp.getMixedStep() && |
| 654 | targetOp.getMapping() == sourceOp.getMapping(); |
| 655 | } |
| 656 | |
| 657 | /// Check if `target` scf.for can be fused into `source` scf.for. |
| 658 | /// |
| 659 | /// This simply checks if both loops have the same bounds and steps. No attempt |
| 660 | /// is made at checking that the side effects of `target` and `source` are |
| 661 | /// independent of each other. |
| 662 | static bool isForWithIdenticalConfiguration(Operation *target, |
| 663 | Operation *source) { |
| 664 | auto targetOp = dyn_cast<scf::ForOp>(Val: target); |
| 665 | auto sourceOp = dyn_cast<scf::ForOp>(Val: source); |
| 666 | if (!targetOp || !sourceOp) |
| 667 | return false; |
| 668 | |
| 669 | return targetOp.getLowerBound() == sourceOp.getLowerBound() && |
| 670 | targetOp.getUpperBound() == sourceOp.getUpperBound() && |
| 671 | targetOp.getStep() == sourceOp.getStep(); |
| 672 | } |
| 673 | |
| 674 | DiagnosedSilenceableFailure |
| 675 | transform::LoopFuseSiblingOp::apply(transform::TransformRewriter &rewriter, |
| 676 | transform::TransformResults &results, |
| 677 | transform::TransformState &state) { |
| 678 | auto targetOps = state.getPayloadOps(value: getTarget()); |
| 679 | auto sourceOps = state.getPayloadOps(value: getSource()); |
| 680 | |
| 681 | if (!llvm::hasSingleElement(C&: targetOps) || |
| 682 | !llvm::hasSingleElement(C&: sourceOps)) { |
| 683 | return emitDefiniteFailure() |
| 684 | << "requires exactly one target handle (got " |
| 685 | << llvm::range_size(Range&: targetOps) << ") and exactly one " |
| 686 | << "source handle (got " << llvm::range_size(Range&: sourceOps) << ")" ; |
| 687 | } |
| 688 | |
| 689 | Operation *target = *targetOps.begin(); |
| 690 | Operation *source = *sourceOps.begin(); |
| 691 | |
| 692 | // Check if the target and source are siblings. |
| 693 | DiagnosedSilenceableFailure diag = isOpSibling(target, source); |
| 694 | if (!diag.succeeded()) |
| 695 | return diag; |
| 696 | |
| 697 | Operation *fusedLoop; |
| 698 | /// TODO: Support fusion for loop-like ops besides scf.for and scf.forall. |
| 699 | if (isForWithIdenticalConfiguration(target, source)) { |
| 700 | fusedLoop = fuseIndependentSiblingForLoops( |
| 701 | target: cast<scf::ForOp>(Val: target), source: cast<scf::ForOp>(Val: source), rewriter); |
| 702 | } else if (isForallWithIdenticalConfiguration(target, source)) { |
| 703 | fusedLoop = fuseIndependentSiblingForallLoops( |
| 704 | target: cast<scf::ForallOp>(Val: target), source: cast<scf::ForallOp>(Val: source), rewriter); |
| 705 | } else { |
| 706 | return emitSilenceableFailure(loc: target->getLoc()) |
| 707 | << "operations cannot be fused" ; |
| 708 | } |
| 709 | |
| 710 | assert(fusedLoop && "failed to fuse operations" ); |
| 711 | |
| 712 | results.set(value: cast<OpResult>(Val: getFusedLoop()), ops: {fusedLoop}); |
| 713 | return DiagnosedSilenceableFailure::success(); |
| 714 | } |
| 715 | |
| 716 | //===----------------------------------------------------------------------===// |
| 717 | // Transform op registration |
| 718 | //===----------------------------------------------------------------------===// |
| 719 | |
| 720 | namespace { |
| 721 | class SCFTransformDialectExtension |
| 722 | : public transform::TransformDialectExtension< |
| 723 | SCFTransformDialectExtension> { |
| 724 | public: |
| 725 | MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(SCFTransformDialectExtension) |
| 726 | |
| 727 | using Base::Base; |
| 728 | |
| 729 | void init() { |
| 730 | declareGeneratedDialect<affine::AffineDialect>(); |
| 731 | declareGeneratedDialect<func::FuncDialect>(); |
| 732 | |
| 733 | registerTransformOps< |
| 734 | #define GET_OP_LIST |
| 735 | #include "mlir/Dialect/SCF/TransformOps/SCFTransformOps.cpp.inc" |
| 736 | >(); |
| 737 | } |
| 738 | }; |
| 739 | } // namespace |
| 740 | |
| 741 | #define GET_OP_CLASSES |
| 742 | #include "mlir/Dialect/SCF/TransformOps/SCFTransformOps.cpp.inc" |
| 743 | |
| 744 | void mlir::scf::registerTransformDialectExtension(DialectRegistry ®istry) { |
| 745 | registry.addExtensions<SCFTransformDialectExtension>(); |
| 746 | } |
| 747 | |