1//===- SCFToGPU.cpp - Convert an affine loop nest to a GPU kernel ---------===//
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 implements a straightforward conversion of an loop nest into a GPU
10// kernel. The caller is expected to guarantee that the conversion is correct
11// or to further transform the kernel to ensure correctness.
12//
13//===----------------------------------------------------------------------===//
14
15#include "mlir/Conversion/SCFToGPU/SCFToGPU.h"
16
17#include "mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h"
18#include "mlir/Conversion/AffineToStandard/AffineToStandard.h"
19#include "mlir/Dialect/Affine/IR/AffineOps.h"
20#include "mlir/Dialect/Arith/IR/Arith.h"
21#include "mlir/Dialect/GPU/IR/GPUDialect.h"
22#include "mlir/Dialect/GPU/Transforms/ParallelLoopMapper.h"
23#include "mlir/Dialect/MemRef/IR/MemRefDialect.h"
24#include "mlir/Dialect/SCF/IR/SCF.h"
25#include "mlir/IR/AffineExpr.h"
26#include "mlir/IR/Builders.h"
27#include "mlir/IR/IRMapping.h"
28#include "mlir/Interfaces/SideEffectInterfaces.h"
29#include "mlir/Transforms/DialectConversion.h"
30#include "mlir/Transforms/RegionUtils.h"
31#include "llvm/ADT/DenseSet.h"
32#include "llvm/Support/DebugLog.h"
33#include <optional>
34
35#define DEBUG_TYPE "loops-to-gpu"
36
37using namespace mlir;
38using namespace mlir::affine;
39using namespace mlir::scf;
40
41// Name of internal attribute to mark visited operations during conversion.
42//
43// NOTE: The conversion originally used the following legality criteria:
44// `!parallelOp->hasDiscardableAttr(gpu::getMappingAttrName())`
45// But the provided pattern might reject some cases based on more detailed
46// analysis of the `mapping` attribute.
47// To avoid dialect conversion failure due to non-converted illegal operation
48// we use this extra Unit attribute as a marker, that the operation was checked
49// by the pattern and is should be considered as legal in the following legality
50// checks. The `finalizeParallelLoopToGPUConversion` function performs clean up
51// of this extra attributes ans is supposed to be called after the dialect
52// conversion.
53//
54// TODO: Implement a cleaner solution, factoring out the "matching" logic
55// from the pattern and its callees into a separate function that can be called
56// from both the pattern and the op legality check.
57static constexpr StringLiteral kVisitedAttrName = "SCFToGPU_visited";
58
59// Extract an indexed value from KernelDim3.
60static Value getDim3Value(const gpu::KernelDim3 &dim3, unsigned pos) {
61 switch (pos) {
62 case 0:
63 return dim3.x;
64 case 1:
65 return dim3.y;
66 case 2:
67 return dim3.z;
68 default:
69 llvm_unreachable("dim3 position out of bounds");
70 }
71 return nullptr;
72}
73
74// Get the lower bound-related operands of a loop operation.
75static Operation::operand_range getLowerBoundOperands(AffineForOp forOp) {
76 return forOp.getLowerBoundOperands();
77}
78
79// Get the upper bound-related operands of a loop operation.
80static Operation::operand_range getUpperBoundOperands(AffineForOp forOp) {
81 return forOp.getUpperBoundOperands();
82}
83
84// Get a Value that corresponds to the loop step. If the step is an attribute,
85// materialize a corresponding constant using builder.
86static Value getOrCreateStep(AffineForOp forOp, OpBuilder &builder) {
87 return arith::ConstantIndexOp::create(builder, location: forOp.getLoc(),
88 value: forOp.getStepAsInt());
89}
90
91// Get a Value for the loop lower bound. If the value requires computation,
92// materialize the instructions using builder.
93static Value getOrEmitLowerBound(AffineForOp forOp, OpBuilder &builder) {
94 return lowerAffineLowerBound(op: forOp, builder);
95}
96
97// Get a Value for the loop upper bound. If the value requires computation,
98// materialize the instructions using builder.
99static Value getOrEmitUpperBound(AffineForOp forOp, OpBuilder &builder) {
100 return lowerAffineUpperBound(op: forOp, builder);
101}
102
103// Check the structure of the loop nest:
104// - there are enough loops to map to numDims;
105// - the loops are perfectly nested;
106// - the loop bounds can be computed above the outermost loop.
107// This roughly corresponds to the "matcher" part of the pattern-based
108// rewriting infrastructure.
109static LogicalResult checkAffineLoopNestMappableImpl(AffineForOp forOp,
110 unsigned numDims) {
111 Region &limit = forOp.getRegion();
112 for (unsigned i = 0, e = numDims; i < e; ++i) {
113 Operation *nested = &forOp.getBody()->front();
114 if (!areValuesDefinedAbove(values: getLowerBoundOperands(forOp), limit) ||
115 !areValuesDefinedAbove(values: getUpperBoundOperands(forOp), limit))
116 return forOp.emitError(
117 message: "loops with bounds depending on other mapped loops "
118 "are not supported");
119
120 // The innermost loop can have an arbitrary body, skip the perfect nesting
121 // check for it.
122 if (i == e - 1)
123 break;
124
125 auto begin = forOp.getBody()->begin(), end = forOp.getBody()->end();
126 if (forOp.getBody()->empty() || std::next(x: begin, n: 2) != end)
127 return forOp.emitError(message: "expected perfectly nested loops in the body");
128
129 if (!(forOp = dyn_cast<AffineForOp>(Val: nested)))
130 return nested->emitError(message: "expected a nested loop");
131 }
132 return success();
133}
134
135static LogicalResult checkAffineLoopNestMappable(AffineForOp forOp,
136 unsigned numBlockDims,
137 unsigned numThreadDims) {
138 if (numBlockDims < 1 || numThreadDims < 1) {
139 LDBG() << "nothing to map";
140 return success();
141 }
142
143 if (numBlockDims > 3) {
144 return forOp.emitError(message: "cannot map to more than 3 block dimensions");
145 }
146 if (numThreadDims > 3) {
147 return forOp.emitError(message: "cannot map to more than 3 thread dimensions");
148 }
149 return checkAffineLoopNestMappableImpl(forOp, numDims: numBlockDims + numThreadDims);
150}
151
152namespace {
153// Helper structure that holds common state of the loop to GPU kernel
154// conversion.
155struct AffineLoopToGpuConverter {
156 std::optional<AffineForOp> collectBounds(AffineForOp forOp,
157 unsigned numLoops);
158
159 void createLaunch(AffineForOp rootForOp, AffineForOp innermostForOp,
160 unsigned numBlockDims, unsigned numThreadDims);
161
162 // Ranges of the loops mapped to blocks or threads.
163 SmallVector<Value, 6> dims;
164 // Lower bounds of the loops mapped to blocks or threads.
165 SmallVector<Value, 6> lbs;
166 // Induction variables of the loops mapped to blocks or threads.
167 SmallVector<Value, 6> ivs;
168 // Steps of the loops mapped to blocks or threads.
169 SmallVector<Value, 6> steps;
170};
171} // namespace
172
173// Collect ranges, bounds, steps and induction variables in preparation for
174// mapping a loop nest of depth "numLoops" rooted at "forOp" to a GPU kernel.
175// This may fail if the IR for computing loop bounds cannot be constructed, for
176// example if an affine loop uses semi-affine maps. Return the last loop to be
177// mapped on success, std::nullopt on failure.
178std::optional<AffineForOp>
179AffineLoopToGpuConverter::collectBounds(AffineForOp forOp, unsigned numLoops) {
180 OpBuilder builder(forOp.getOperation());
181 dims.reserve(N: numLoops);
182 lbs.reserve(N: numLoops);
183 ivs.reserve(N: numLoops);
184 steps.reserve(N: numLoops);
185 AffineForOp currentLoop = forOp;
186 for (unsigned i = 0; i < numLoops; ++i) {
187 if (currentLoop.getNumIterOperands() > 0) {
188 currentLoop.emitError(
189 message: "affine loop with iter_args cannot be converted to GPU kernel");
190 return std::nullopt;
191 }
192
193 Value lowerBound = getOrEmitLowerBound(forOp: currentLoop, builder);
194 Value upperBound = getOrEmitUpperBound(forOp: currentLoop, builder);
195 if (!lowerBound || !upperBound) {
196 return std::nullopt;
197 }
198
199 Value range = arith::SubIOp::create(builder, location: currentLoop.getLoc(),
200 lhs: upperBound, rhs: lowerBound);
201 Value step = getOrCreateStep(forOp: currentLoop, builder);
202 if (getConstantIntValue(ofr: step) != static_cast<int64_t>(1))
203 range = arith::CeilDivSIOp::create(builder, location: currentLoop.getLoc(), lhs: range,
204 rhs: step);
205 dims.push_back(Elt: range);
206
207 lbs.push_back(Elt: lowerBound);
208 ivs.push_back(Elt: currentLoop.getInductionVar());
209 steps.push_back(Elt: step);
210
211 if (i != numLoops - 1)
212 currentLoop = cast<AffineForOp>(Val: &currentLoop.getBody()->front());
213 }
214 return currentLoop;
215}
216
217// Replace the rooted at "rootForOp" with a GPU launch operation. This expects
218// "innermostForOp" to point to the last loop to be transformed to the kernel,
219// and to have (numBlockDims + numThreadDims) perfectly nested loops between
220// "rootForOp" and "innermostForOp".
221void AffineLoopToGpuConverter::createLaunch(AffineForOp rootForOp,
222 AffineForOp innermostForOp,
223 unsigned numBlockDims,
224 unsigned numThreadDims) {
225 OpBuilder builder(rootForOp.getOperation());
226 // Prepare the grid and block sizes for the launch operation. If there is
227 // no loop mapped to a specific dimension, use constant "1" as its size.
228 Value constOne =
229 (numBlockDims < 3 || numThreadDims < 3)
230 ? arith::ConstantIndexOp::create(builder, location: rootForOp.getLoc(), value: 1)
231 : nullptr;
232 Value gridSizeX = numBlockDims > 0 ? dims[0] : constOne;
233 Value gridSizeY = numBlockDims > 1 ? dims[1] : constOne;
234 Value gridSizeZ = numBlockDims > 2 ? dims[2] : constOne;
235 Value blockSizeX = numThreadDims > 0 ? dims[numBlockDims] : constOne;
236 Value blockSizeY = numThreadDims > 1 ? dims[numBlockDims + 1] : constOne;
237 Value blockSizeZ = numThreadDims > 2 ? dims[numBlockDims + 2] : constOne;
238
239 // Create a launch op and move the body region of the innermost loop to the
240 // launch op.
241 auto launchOp =
242 gpu::LaunchOp::create(builder, location: rootForOp.getLoc(), gridSizeX, gridSizeY,
243 gridSizeZ, blockSizeX, blockSizeY, blockSizeZ);
244
245 // Replace the loop terminator (loops contain only a single block) with the
246 // gpu terminator and move the operations from the loop body block to the gpu
247 // launch body block. Do not move the entire block because of the difference
248 // in block arguments.
249 Operation &terminator = innermostForOp.getBody()->back();
250 Location terminatorLoc = terminator.getLoc();
251 terminator.erase();
252 builder.setInsertionPointToEnd(innermostForOp.getBody());
253 gpu::TerminatorOp::create(builder, location: terminatorLoc, resultTypes: TypeRange());
254 launchOp.getBody().front().getOperations().splice(
255 where: launchOp.getBody().front().begin(),
256 L2&: innermostForOp.getBody()->getOperations());
257
258 // Remap the loop iterators to use block/thread identifiers instead. Loops
259 // may iterate from LB with step S whereas GPU thread/block ids always iterate
260 // from 0 to N with step 1. Therefore, loop induction variables are replaced
261 // with (gpu-thread/block-id * S) + LB.
262 builder.setInsertionPointToStart(&launchOp.getBody().front());
263 auto *lbArgumentIt = lbs.begin();
264 auto *stepArgumentIt = steps.begin();
265 for (const auto &en : llvm::enumerate(First&: ivs)) {
266 Value id =
267 en.index() < numBlockDims
268 ? getDim3Value(dim3: launchOp.getBlockIds(), pos: en.index())
269 : getDim3Value(dim3: launchOp.getThreadIds(), pos: en.index() - numBlockDims);
270 Value step = steps[en.index()];
271 if (getConstantIntValue(ofr: step) != static_cast<int64_t>(1))
272 id = arith::MulIOp::create(builder, location: rootForOp.getLoc(), lhs: step, rhs: id);
273
274 Value ivReplacement =
275 arith::AddIOp::create(builder, location: rootForOp.getLoc(), lhs: *lbArgumentIt, rhs: id);
276 en.value().replaceAllUsesWith(newValue: ivReplacement);
277 std::advance(i&: lbArgumentIt, n: 1);
278 std::advance(i&: stepArgumentIt, n: 1);
279 }
280
281 // We are done and can erase the original outermost loop.
282 rootForOp.erase();
283}
284
285// Generic loop to GPU kernel conversion function.
286static LogicalResult convertAffineLoopNestToGPULaunch(AffineForOp forOp,
287 unsigned numBlockDims,
288 unsigned numThreadDims) {
289 if (failed(Result: checkAffineLoopNestMappable(forOp, numBlockDims, numThreadDims)))
290 return failure();
291
292 AffineLoopToGpuConverter converter;
293 auto maybeInnerLoop =
294 converter.collectBounds(forOp, numLoops: numBlockDims + numThreadDims);
295 if (!maybeInnerLoop)
296 return failure();
297 converter.createLaunch(rootForOp: forOp, innermostForOp: *maybeInnerLoop, numBlockDims, numThreadDims);
298
299 return success();
300}
301
302LogicalResult mlir::convertAffineLoopNestToGPULaunch(AffineForOp forOp,
303 unsigned numBlockDims,
304 unsigned numThreadDims) {
305 return ::convertAffineLoopNestToGPULaunch(forOp, numBlockDims, numThreadDims);
306}
307
308namespace {
309struct ParallelToGpuLaunchLowering : public OpRewritePattern<ParallelOp> {
310 using OpRewritePattern<ParallelOp>::OpRewritePattern;
311
312 LogicalResult matchAndRewrite(ParallelOp parallelOp,
313 PatternRewriter &rewriter) const override;
314};
315} // namespace
316
317/// Tries to derive a static upper bound from the defining operation of
318/// `upperBound`.
319static Value deriveStaticUpperBound(Value upperBound,
320 PatternRewriter &rewriter) {
321 if (auto op = upperBound.getDefiningOp<arith::ConstantIndexOp>()) {
322 return op;
323 }
324
325 if (auto minOp = upperBound.getDefiningOp<AffineMinOp>()) {
326 for (const AffineExpr &result : minOp.getMap().getResults()) {
327 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val: result)) {
328 return arith::ConstantIndexOp::create(builder&: rewriter, location: minOp.getLoc(),
329 value: constExpr.getValue());
330 }
331 }
332 }
333
334 if (auto minOp = upperBound.getDefiningOp<arith::MinSIOp>()) {
335 for (Value operand : {minOp.getLhs(), minOp.getRhs()}) {
336 if (auto staticBound = deriveStaticUpperBound(upperBound: operand, rewriter))
337 return staticBound;
338 }
339 }
340
341 if (auto multiplyOp = upperBound.getDefiningOp<arith::MulIOp>()) {
342 if (auto lhs = deriveStaticUpperBound(upperBound: multiplyOp.getOperand(i: 0), rewriter)
343 .getDefiningOp<arith::ConstantIndexOp>())
344 if (auto rhs = deriveStaticUpperBound(upperBound: multiplyOp.getOperand(i: 1), rewriter)
345 .getDefiningOp<arith::ConstantIndexOp>()) {
346 // Assumptions about the upper bound of minimum computations no longer
347 // work if multiplied by mixed signs, so abort in this case.
348 if ((lhs.value() < 0) != (rhs.value() < 0))
349 return {};
350
351 return arith::ConstantIndexOp::create(builder&: rewriter, location: multiplyOp.getLoc(),
352 value: lhs.value() * rhs.value());
353 }
354 }
355
356 return {};
357}
358
359static bool isMappedToProcessor(gpu::Processor processor) {
360 return processor != gpu::Processor::Sequential;
361}
362
363static unsigned getLaunchOpArgumentNum(gpu::Processor processor) {
364 switch (processor) {
365 case gpu::Processor::BlockX:
366 return 0;
367 case gpu::Processor::BlockY:
368 return 1;
369 case gpu::Processor::BlockZ:
370 return 2;
371 case gpu::Processor::ThreadX:
372 return 3;
373 case gpu::Processor::ThreadY:
374 return 4;
375 case gpu::Processor::ThreadZ:
376 return 5;
377 default:;
378 }
379 llvm_unreachable(
380 "invalid processor type while retrieving launch op argument number");
381}
382
383/// Modifies the current transformation state to capture the effect of the given
384/// `scf.parallel` operation on index substitutions and the operations to be
385/// inserted.
386/// Specifically, if a dimension of a parallel loop is mapped to a hardware id,
387/// this function will
388/// - compute the loop index based on the hardware id and affine map from the
389/// mapping and update `cloningMap` to substitute all uses.
390/// - derive a new upper bound for the hardware id and augment the provided
391/// `gpu.launch operation` accordingly.
392/// - if the upper bound is imprecise, insert a conditional in the `gpu.launch`
393/// and update the rewriter to insert into the conditional's body.
394/// If the dimension is mapped to sequential,
395/// - insert a for loop into the body and update the rewriter to insert into
396/// the for loop's body.
397/// - update the `cloningMap` to replace uses of the index with the index of
398/// the new for loop.
399/// In either case,
400/// - append the instructions from the loops body to worklist, in reverse order.
401/// To note the end of the current scope in case a loop or conditional was
402/// inserted, a sentinel (the `gpu.launch` operation) is inserted into the
403/// worklist. This signals the processor of the worklist to pop the rewriter
404/// one scope-level up.
405static LogicalResult processParallelLoop(
406 ParallelOp parallelOp, gpu::LaunchOp launchOp, IRMapping &cloningMap,
407 SmallVectorImpl<Operation *> &worklist,
408 DenseMap<gpu::Processor, Value> &bounds, PatternRewriter &rewriter) {
409 // TODO: Verify that this is a valid GPU mapping.
410 // processor ids: 0-2 block [x/y/z], 3-5 -> thread [x/y/z], 6-> sequential
411 ArrayAttr mapping = parallelOp->getDiscardableAttrOfType<ArrayAttr>(
412 name: gpu::getMappingAttrName());
413
414 // TODO: Support multiple reductions.
415 if (!mapping || parallelOp.getNumResults() > 1)
416 return failure();
417
418 Location loc = parallelOp.getLoc();
419
420 auto launchIndependent = [&launchOp](Value val) {
421 return val.getParentRegion()->isAncestor(other: launchOp->getParentRegion());
422 };
423
424 auto ensureLaunchIndependent = [&rewriter,
425 launchIndependent](Value val) -> Value {
426 if (launchIndependent(val))
427 return val;
428 if (std::optional<int64_t> constOp = getConstantIntValue(ofr: val))
429 return arith::ConstantIndexOp::create(builder&: rewriter, location: val.getLoc(),
430 value: constOp.value());
431 return {};
432 };
433
434 for (auto config : llvm::zip(
435 t&: mapping, u: parallelOp.getInductionVars(), args: parallelOp.getLowerBound(),
436 args: parallelOp.getUpperBound(), args: parallelOp.getStep())) {
437 Attribute mappingAttribute;
438 Value iv, lowerBound, upperBound, step;
439 std::tie(args&: mappingAttribute, args&: iv, args&: lowerBound, args&: upperBound, args&: step) = config;
440 auto annotation =
441 dyn_cast<gpu::ParallelLoopDimMappingAttr>(Val&: mappingAttribute);
442 if (!annotation)
443 return parallelOp.emitOpError()
444 << "expected mapping attribute for lowering to GPU";
445 Value newIndex;
446 gpu::Processor processor = annotation.getProcessor();
447
448 if (isMappedToProcessor(processor)) {
449 // Use the corresponding thread/grid index as replacement for the loop iv.
450 Value operand =
451 launchOp.getBody().getArgument(i: getLaunchOpArgumentNum(processor));
452 // Take the indexmap and add the lower bound and step computations in.
453 // This computes operand * step + lowerBound.
454 // Use an affine map here so that it composes nicely with the provided
455 // annotation.
456 AffineMap lowerAndStep = AffineMap::get(
457 dimCount: 1, symbolCount: 2,
458 result: rewriter.getAffineDimExpr(position: 0) * rewriter.getAffineSymbolExpr(position: 0) +
459 rewriter.getAffineSymbolExpr(position: 1));
460 // Map through cloningMap first so we use values valid at the launch
461 // scope, then ensure they are launch-independent (or cloned constants).
462 Value mappedStep = cloningMap.lookupOrDefault(from: step);
463 Value mappedLowerBound = cloningMap.lookupOrDefault(from: lowerBound);
464
465 mappedStep = ensureLaunchIndependent(mappedStep);
466 mappedLowerBound = ensureLaunchIndependent(mappedLowerBound);
467
468 // If either cannot be made available above the launch, fail gracefully.
469 if (!mappedStep || !mappedLowerBound) {
470 return rewriter.notifyMatchFailure(
471 arg&: parallelOp, msg: "lower bound / step must be constant or defined above "
472 "the gpu.launch");
473 }
474
475 newIndex = AffineApplyOp::create(
476 builder&: rewriter, location: loc, map: annotation.getMap().compose(map: lowerAndStep),
477 mapOperands: ValueRange{operand, mappedStep, mappedLowerBound});
478 // If there was also a bound, insert that, too.
479 // TODO: Check that we do not assign bounds twice.
480 if (annotation.getBound()) {
481 // We pass as the single operand to the bound-map the number of
482 // iterations, which is (upperBound - lowerBound) ceilDiv step. To
483 // support inner loops with dynamic upper bounds (as generated by e.g.
484 // tiling), try to derive a max for the bounds. If the used bound for
485 // the hardware id is imprecise, wrap the contained code into a
486 // conditional. If the lower-bound is constant or defined before the
487 // launch, we can use it in the launch bounds. Otherwise fail.
488 if (!launchIndependent(lowerBound) &&
489 !getConstantIntValue(ofr: lowerBound).has_value())
490 return failure();
491 // The step must also be constant or defined outside of the loop nest.
492 if (!launchIndependent(step) && !getConstantIntValue(ofr: step).has_value())
493 return failure();
494 // If the upper-bound is constant or defined before the launch, we can
495 // use it in the launch bounds directly. Otherwise try derive a bound.
496 bool boundIsPrecise = launchIndependent(upperBound) ||
497 getConstantIntValue(ofr: upperBound).has_value();
498 {
499 PatternRewriter::InsertionGuard guard(rewriter);
500 rewriter.setInsertionPoint(launchOp);
501 if (!boundIsPrecise) {
502 upperBound = deriveStaticUpperBound(upperBound, rewriter);
503 if (!upperBound) {
504 return rewriter.notifyMatchFailure(
505 arg&: parallelOp,
506 msg: "cannot derive loop-invariant upper bound for number of"
507 "iterations");
508 }
509 }
510 // Compute the number of iterations needed. We compute this as an
511 // affine expression ceilDiv (upperBound - lowerBound) step. We use
512 // affine.apply here so that it composes nicely with the provided map.
513 AffineMap stepMap = AffineMap::get(
514 dimCount: 1, symbolCount: 2,
515 result: ((rewriter.getAffineDimExpr(position: 0) - rewriter.getAffineSymbolExpr(position: 0))
516 .ceilDiv(other: rewriter.getAffineSymbolExpr(position: 1))));
517 Value launchBound = AffineApplyOp::create(
518 builder&: rewriter, location: loc, map: annotation.getBound().compose(map: stepMap),
519 mapOperands: ValueRange{
520 ensureLaunchIndependent(
521 cloningMap.lookupOrDefault(from: upperBound)),
522 ensureLaunchIndependent(
523 cloningMap.lookupOrDefault(from: lowerBound)),
524 ensureLaunchIndependent(cloningMap.lookupOrDefault(from: step))});
525 // todo(herhut,ravishankarm): Update the behavior of setMappingAttr
526 // when this condition is relaxed.
527 if (!bounds.try_emplace(Key: processor, Args&: launchBound).second) {
528 return rewriter.notifyMatchFailure(
529 arg&: parallelOp, msg: "cannot redefine the bound for processor " +
530 Twine(static_cast<int64_t>(processor)));
531 }
532 }
533 if (!boundIsPrecise) {
534 // We are using an approximation, create a surrounding conditional.
535 Value originalBound = std::get<3>(t&: config);
536 arith::CmpIOp pred = arith::CmpIOp::create(
537 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::slt, lhs: newIndex,
538 rhs: cloningMap.lookupOrDefault(from: originalBound));
539 scf::IfOp ifOp = scf::IfOp::create(builder&: rewriter, location: loc, cond: pred, withElseRegion: false);
540 rewriter.setInsertionPointToStart(&ifOp.getThenRegion().front());
541 // Put a sentinel into the worklist so we know when to pop out of the
542 // if body again. We use the launchOp here, as that cannot be part of
543 // the bodies instruction.
544 worklist.push_back(Elt: launchOp.getOperation());
545 }
546 }
547 } else {
548 // Create a sequential for loop.
549 auto loopOp = scf::ForOp::create(builder&: rewriter, location: loc,
550 lowerBound: cloningMap.lookupOrDefault(from: lowerBound),
551 upperBound: cloningMap.lookupOrDefault(from: upperBound),
552 step: cloningMap.lookupOrDefault(from: step));
553 newIndex = loopOp.getInductionVar();
554 rewriter.setInsertionPointToStart(loopOp.getBody());
555 // Put a sentinel into the worklist so we know when to pop out of the loop
556 // body again. We use the launchOp here, as that cannot be part of the
557 // bodies instruction.
558 worklist.push_back(Elt: launchOp.getOperation());
559 }
560 cloningMap.map(from: iv, to: newIndex);
561 }
562
563 // Propagate custom user defined optional attributes, that can be used at
564 // later stage, such as extension data for GPU kernel dispatch
565 for (const auto &namedAttr :
566 parallelOp->getDiscardableAttrDictionary().getValue()) {
567 if (namedAttr.getName() == gpu::getMappingAttrName())
568 continue;
569 launchOp->setDiscardableAttr(name: namedAttr.getName(), value: namedAttr.getValue());
570 }
571
572 Block *body = parallelOp.getBody();
573 worklist.reserve(N: worklist.size() + body->getOperations().size());
574 // Include scf.reduce terminator if exists and has an operand.
575 if (auto terminator = body->getTerminator();
576 isa<scf::ReduceOp>(Val: terminator) && terminator->getOperands().size() == 1) {
577 worklist.push_back(Elt: terminator);
578 }
579 for (Operation &op : llvm::reverse(C: body->without_terminator()))
580 worklist.push_back(Elt: &op);
581 return success();
582}
583
584/// Lower a `scf.parallel` operation into a corresponding `gpu.launch`
585/// operation.
586///
587/// This essentially transforms a loop nest into a corresponding SIMT function.
588/// The conversion is driven by mapping annotations on the `scf.parallel`
589/// operations. The mapping is provided via a `DictionaryAttribute` named
590/// `mapping`, which has three entries:
591/// - processor: the hardware id to map to. 0-2 are block dimensions, 3-5 are
592/// thread dimensions and 6 is sequential.
593/// - map : An affine map that is used to pre-process hardware ids before
594/// substitution.
595/// - bound : An affine map that is used to compute the bound of the hardware
596/// id based on an upper bound of the number of iterations.
597/// If the `scf.parallel` contains nested `scf.parallel` operations, those
598/// need to be annotated, as well. Structurally, the transformation works by
599/// splicing all operations from nested `scf.parallel` operations into a single
600/// sequence. Indices mapped to hardware ids are substituted with those ids,
601/// wheras sequential mappings result in a sequential for-loop. To have more
602/// flexibility when mapping code to hardware ids, the transform supports two
603/// affine maps. The first `map` is used to compute the actual index for
604/// substitution from the hardware id. The second `bound` is used to compute the
605/// launch dimension for the hardware id from the number of iterations the
606/// mapped loop is performing. Note that the number of iterations might be
607/// imprecise if the corresponding loop-bounds are loop-dependent. In such case,
608/// the hardware id might iterate over additional indices. The transformation
609/// caters for this by predicating the created sequence of instructions on
610/// the actual loop bound. This only works if an static upper bound for the
611/// dynamic loop bound can be derived, currently via analyzing `affine.min`
612/// operations.
613LogicalResult
614ParallelToGpuLaunchLowering::matchAndRewrite(ParallelOp parallelOp,
615 PatternRewriter &rewriter) const {
616 if (parallelOp.getUnsignedCmp())
617 return rewriter.notifyMatchFailure(
618 arg&: parallelOp, msg: "unsigned loop bounds are not supported");
619 // Mark the operation as visited for recursive legality check.
620 parallelOp->setDiscardableAttr(name: kVisitedAttrName, value: rewriter.getUnitAttr());
621
622 // We can only transform starting at the outer-most loop. Launches inside of
623 // parallel loops are not supported.
624 if (auto parentLoop = parallelOp->getParentOfType<ParallelOp>())
625 return failure();
626 // Create a launch operation. We start with bound one for all grid/block
627 // sizes. Those will be refined later as we discover them from mappings.
628 Location loc = parallelOp.getLoc();
629 Value constantOne = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1);
630 gpu::LaunchOp launchOp =
631 gpu::LaunchOp::create(builder&: rewriter, location: loc, gridSizeX: constantOne, gridSizeY: constantOne,
632 gridSizeZ: constantOne, blockSizeX: constantOne, blockSizeY: constantOne, blockSizeZ: constantOne);
633 rewriter.setInsertionPointToEnd(&launchOp.getBody().front());
634 gpu::TerminatorOp::create(builder&: rewriter, location: loc);
635 rewriter.setInsertionPointToStart(&launchOp.getBody().front());
636
637 IRMapping cloningMap;
638 llvm::DenseMap<gpu::Processor, Value> launchBounds;
639 SmallVector<Operation *, 16> worklist;
640 if (failed(Result: processParallelLoop(parallelOp, launchOp, cloningMap, worklist,
641 bounds&: launchBounds, rewriter)))
642 return failure();
643
644 // Whether we have seen any side-effects. Reset when leaving an inner scope.
645 bool seenSideeffects = false;
646 // Whether we have left a nesting scope (and hence are no longer innermost).
647 bool leftNestingScope = false;
648 LocalAliasAnalysis aliasAnalysis;
649 llvm::DenseSet<Value> writtenBuffer;
650 while (!worklist.empty()) {
651 Operation *op = worklist.pop_back_val();
652 // Now walk over the body and clone it.
653 // TODO: This is only correct if there either is no further scf.parallel
654 // nested or this code has side-effect but the memory buffer is not
655 // alias to inner loop access buffer. Otherwise we might need
656 // predication.
657 if (auto nestedParallel = dyn_cast<ParallelOp>(Val: op)) {
658 // Before entering a nested scope, make sure there have been no
659 // sideeffects until now or the nested operations do not access the
660 // buffer written by outer scope.
661 if (seenSideeffects) {
662 WalkResult walkRes = nestedParallel.walk(callback: [&](Operation *nestedOp) {
663 if (isMemoryEffectFree(op: nestedOp))
664 return WalkResult::advance();
665
666 auto memEffectInterface = dyn_cast<MemoryEffectOpInterface>(Val: nestedOp);
667 if (!memEffectInterface)
668 return WalkResult::advance();
669
670 SmallVector<MemoryEffects::EffectInstance> effects;
671 memEffectInterface.getEffects(effects);
672 for (const MemoryEffects::EffectInstance &effect : effects) {
673 if (isa<MemoryEffects::Read>(Val: effect.getEffect()) ||
674 isa<MemoryEffects::Write>(Val: effect.getEffect())) {
675 Value baseBuffer = effect.getValue();
676 if (!baseBuffer)
677 return WalkResult::interrupt();
678 for (Value val : writtenBuffer) {
679 if (aliasAnalysis.alias(lhs: baseBuffer, rhs: val) !=
680 AliasResult::NoAlias) {
681 return WalkResult::interrupt();
682 }
683 }
684 }
685 }
686 return WalkResult::advance();
687 });
688 if (walkRes.wasInterrupted())
689 return failure();
690 }
691 // A nested scf.parallel needs insertion of code to compute indices.
692 // Insert that now. This will also update the worklist with the loops
693 // body.
694 if (failed(Result: processParallelLoop(parallelOp: nestedParallel, launchOp, cloningMap,
695 worklist, bounds&: launchBounds, rewriter)))
696 return failure();
697 } else if (op == launchOp.getOperation()) {
698 // Found our sentinel value. We have finished the operations from one
699 // nesting level, pop one level back up.
700 auto *parent = rewriter.getInsertionPoint()->getParentOp();
701 rewriter.setInsertionPointAfter(parent);
702 leftNestingScope = true;
703 seenSideeffects = false;
704 writtenBuffer.clear();
705 } else if (auto reduceOp = dyn_cast<scf::ReduceOp>(Val: op)) {
706 // Convert scf.reduction op
707 auto parentLoop = op->getParentOfType<ParallelOp>();
708 if (!parentLoop || op->getOperands().size() != 1)
709 return failure();
710 auto operand = op->getOperands().front();
711 auto newValue = cloningMap.lookupOrNull(from: operand);
712 if (!newValue || !operand.getType().isSignlessIntOrFloat())
713 return failure();
714 // Ensure reduction region is isolated from above.
715 llvm::SetVector<Value> externalValues;
716 getUsedValuesDefinedAbove(regions: reduceOp.getRegion(i: 0), values&: externalValues);
717 if (!externalValues.empty())
718 return failure();
719 // Replace by gpu.all_reduce.
720 auto gpuRedOp = gpu::AllReduceOp::create(
721 builder&: rewriter, location: loc, value: newValue, /*op=*/nullptr, /*uniform=*/false);
722 cloningMap.map(from: parentLoop->getResult(idx: 0), to: gpuRedOp.getResult());
723 // Copy region.
724 rewriter.inlineRegionBefore(region&: reduceOp.getRegion(i: 0), parent&: gpuRedOp.getRegion(),
725 before: gpuRedOp.getRegion().begin());
726 // Replace src.reduce.return with gpu.yield.
727 auto scfReturn = gpuRedOp.getRegion().front().getTerminator();
728 auto ip = rewriter.saveInsertionPoint();
729 rewriter.setInsertionPointToEnd(&gpuRedOp.getRegion().front());
730 rewriter.replaceOpWithNewOp<gpu::YieldOp>(
731 op: scfReturn, args: scfReturn->getOperands().front());
732 rewriter.restoreInsertionPoint(ip);
733 } else {
734 // Otherwise we copy it over.
735 Operation *clone = rewriter.clone(op&: *op, mapper&: cloningMap);
736 cloningMap.map(from: op->getResults(), to: clone->getResults());
737 // Check for side effects.
738 if (!isMemoryEffectFree(op: clone)) {
739 // Record the buffer accessed by the operations with write effects.
740 if (auto memEffectInterface =
741 dyn_cast<MemoryEffectOpInterface>(Val: clone)) {
742 SmallVector<MemoryEffects::EffectInstance> effects;
743 memEffectInterface.getEffects(effects);
744 for (const MemoryEffects::EffectInstance &effect : effects) {
745 if (isa<MemoryEffects::Write>(Val: effect.getEffect())) {
746 Value writtenBase = effect.getValue();
747 // Conservatively return failure if we cannot find the written
748 // address.
749 if (!writtenBase)
750 return failure();
751 writtenBuffer.insert(V: writtenBase);
752 }
753 }
754 }
755 }
756 // TODO: Handle region side effects properly.
757 seenSideeffects |=
758 !isMemoryEffectFree(op: clone) || clone->getNumRegions() != 0;
759 // If we are no longer in the innermost scope, sideeffects are disallowed.
760 if (seenSideeffects && leftNestingScope)
761 return failure();
762 }
763 }
764
765 // Now that we succeeded creating the launch operation, also update the
766 // bounds.
767 for (const auto &[processor, bound] : launchBounds)
768 launchOp.setOperand(i: getLaunchOpArgumentNum(processor), value: bound);
769
770 rewriter.eraseOp(op: parallelOp);
771 return success();
772}
773
774void mlir::populateParallelLoopToGPUPatterns(RewritePatternSet &patterns) {
775 patterns.add<ParallelToGpuLaunchLowering>(arg: patterns.getContext());
776}
777
778void mlir::configureParallelLoopToGPULegality(ConversionTarget &target) {
779 target.addLegalDialect<memref::MemRefDialect>();
780 target.addDynamicallyLegalOp<scf::ParallelOp>(callback: [](scf::ParallelOp parallelOp) {
781 return !parallelOp->hasDiscardableAttr(name: gpu::getMappingAttrName()) ||
782 parallelOp->hasDiscardableAttr(name: kVisitedAttrName);
783 });
784}
785
786void mlir::finalizeParallelLoopToGPUConversion(Operation *op) {
787 op->walk(callback: [](scf::ParallelOp parallelOp) {
788 parallelOp->removeDiscardableAttr(name: kVisitedAttrName);
789 });
790}
791