1//===- KernelOutlining.cpp - Implementation of GPU kernel outlining -------===//
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 implements the GPU dialect kernel outlining pass.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/GPU/Transforms/Passes.h"
14
15#include "mlir/AsmParser/AsmParser.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
18#include "mlir/Dialect/DLTI/DLTI.h"
19#include "mlir/Dialect/GPU/IR/GPUDialect.h"
20#include "mlir/Dialect/GPU/Utils/GPUUtils.h"
21#include "mlir/Dialect/MemRef/IR/MemRef.h"
22#include "mlir/IR/Builders.h"
23#include "mlir/IR/BuiltinAttributes.h"
24#include "mlir/IR/IRMapping.h"
25#include "mlir/IR/Matchers.h"
26#include "mlir/IR/SymbolTable.h"
27#include "mlir/Support/LLVM.h"
28#include "mlir/Transforms/RegionUtils.h"
29#include <limits>
30
31namespace mlir {
32#define GEN_PASS_DEF_GPULAUNCHSINKINDEXCOMPUTATIONSPASS
33#define GEN_PASS_DEF_GPUKERNELOUTLININGPASS
34#include "mlir/Dialect/GPU/Transforms/Passes.h.inc"
35} // namespace mlir
36
37using namespace mlir;
38
39template <typename OpTy>
40static void createForAllDimensions(OpBuilder &builder, Location loc,
41 SmallVectorImpl<Value> &values) {
42 for (auto dim : {gpu::Dimension::x, gpu::Dimension::y, gpu::Dimension::z})
43 values.push_back(Elt: OpTy::create(builder, loc, builder.getIndexType(), dim));
44}
45
46/// Adds operations generating block/thread ids and grid/block dimensions at the
47/// beginning of the `launchFuncOpBody` region. Add mapping from argument in
48/// entry block of `launchOpBody`, to the corresponding result value of the
49/// added operations.
50static void injectGpuIndexOperations(Location loc, Region &launchFuncOpBody,
51 Region &launchOpBody, IRMapping &map,
52 bool hasCluster = false) {
53 OpBuilder builder(loc->getContext());
54 Block &firstBlock = launchOpBody.front();
55 builder.setInsertionPointToStart(&launchFuncOpBody.front());
56 SmallVector<Value> indexOps;
57 // The order is important here, as it must match the order of the arguments
58 createForAllDimensions<gpu::BlockIdOp>(builder, loc, values&: indexOps);
59 createForAllDimensions<gpu::ThreadIdOp>(builder, loc, values&: indexOps);
60 createForAllDimensions<gpu::GridDimOp>(builder, loc, values&: indexOps);
61 createForAllDimensions<gpu::BlockDimOp>(builder, loc, values&: indexOps);
62 if (hasCluster) {
63 createForAllDimensions<gpu::ClusterIdOp>(builder, loc, values&: indexOps);
64 createForAllDimensions<gpu::ClusterDimOp>(builder, loc, values&: indexOps);
65 }
66 // Replace the leading 12 function args with the respective thread/block index
67 // operations. Iterate backwards since args are erased and indices change.
68 for (const auto &indexOp : enumerate(First&: indexOps))
69 map.map(from: firstBlock.getArgument(i: indexOp.index()), to: indexOp.value());
70}
71
72/// Identifies operations that are beneficial to sink into kernels. These
73/// operations may not have side-effects, as otherwise sinking (and hence
74/// duplicating them) is not legal.
75static bool isLikelyAnIndexComputation(Operation *op) {
76 return matchPattern(op, pattern: m_Constant()) ||
77 isa<memref::DimOp, arith::SelectOp, arith::CmpIOp>(Val: op);
78}
79
80/// For a given operation `op`, computes whether it is beneficial to sink the
81/// operation into the kernel. An operation can be sunk if doing so does not
82/// introduce new kernel arguments. Whether a value is already available in the
83/// kernel (and hence does not introduce new arguments) is checked by
84/// querying `existingDependencies` and `availableValues`.
85/// If an operand is not yet available, we recursively check whether it can be
86/// made available by siking its defining op.
87/// Operations that are indentified for sinking are added to `beneficiaryOps` in
88/// the order they should appear in the kernel. Furthermore, `availableValues`
89/// is updated with results that will be available after sinking the identified
90/// ops.
91static bool extractBeneficiaryOps(
92 Operation *op, const SetVector<Value> &existingDependencies,
93 SetVector<Operation *> &beneficiaryOps,
94 llvm::SmallPtrSetImpl<Value> &availableValues,
95 llvm::function_ref<bool(Operation *)> isSinkingBeneficiary) {
96 if (beneficiaryOps.count(key: op))
97 return true;
98
99 if (!isSinkingBeneficiary(op))
100 return false;
101
102 for (Value operand : op->getOperands()) {
103 // It is already visible in the kernel, keep going.
104 if (availableValues.count(Ptr: operand))
105 continue;
106 // Else check whether it can be made available via sinking or already is a
107 // dependency.
108 Operation *definingOp = operand.getDefiningOp();
109 if ((!definingOp || !extractBeneficiaryOps(op: definingOp, existingDependencies,
110 beneficiaryOps, availableValues,
111 isSinkingBeneficiary)) &&
112 !existingDependencies.count(key: operand))
113 return false;
114 }
115 // We will sink the operation, mark its results as now available.
116 beneficiaryOps.insert(X: op);
117 for (Value result : op->getResults())
118 availableValues.insert(Ptr: result);
119 return true;
120}
121
122LogicalResult mlir::sinkOperationsIntoLaunchOp(
123 gpu::LaunchOp launchOp,
124 llvm::function_ref<bool(Operation *)> isSinkingBeneficiary) {
125 assert(isSinkingBeneficiary);
126 Region &launchOpBody = launchOp.getBody();
127
128 // Identify uses from values defined outside of the scope of the launch
129 // operation.
130 SetVector<Value> sinkCandidates;
131 getUsedValuesDefinedAbove(regions: launchOpBody, values&: sinkCandidates);
132
133 SetVector<Operation *> toBeSunk;
134 llvm::SmallPtrSet<Value, 4> availableValues;
135 for (Value operand : sinkCandidates) {
136 Operation *operandOp = operand.getDefiningOp();
137 if (!operandOp)
138 continue;
139 extractBeneficiaryOps(op: operandOp, existingDependencies: sinkCandidates, beneficiaryOps&: toBeSunk, availableValues,
140 isSinkingBeneficiary);
141 }
142
143 // Insert operations so that the defs get cloned before uses.
144 IRMapping map;
145 OpBuilder builder(launchOpBody);
146 for (Operation *op : toBeSunk) {
147 Operation *clonedOp = builder.clone(op&: *op, mapper&: map);
148 // Only replace uses within the launch op.
149 for (auto pair : llvm::zip(t: op->getResults(), u: clonedOp->getResults()))
150 replaceAllUsesInRegionWith(orig: std::get<0>(t&: pair), replacement: std::get<1>(t&: pair),
151 region&: launchOp.getBody());
152 }
153 return success();
154}
155
156/// Return the provided KernelDim3 as an array of i32 constants if possible.
157static DenseI32ArrayAttr maybeConstantDimsAttr(gpu::KernelDim3 dims) {
158 SmallVector<int32_t, 3> constants;
159 MLIRContext *ctx = dims.x.getContext();
160 for (Value v : {dims.x, dims.y, dims.z}) {
161 APInt constValue;
162 if (!matchPattern(value: v, pattern: m_ConstantInt(bind_value: &constValue)))
163 return nullptr;
164 // In the event someone called for a too-large block or grid dimension,
165 // don't set bounds as it is likely to cause more confusing behavior.
166 if (constValue.ugt(RHS: std::numeric_limits<uint32_t>::max()))
167 return nullptr;
168 constants.push_back(
169 Elt: constValue.getLimitedValue(Limit: std::numeric_limits<uint32_t>::max()));
170 }
171 return DenseI32ArrayAttr::get(context: ctx, content: constants);
172}
173
174/// Outline the `gpu.launch` operation body into a kernel function. Replace
175/// `gpu.terminator` operations by `gpu.return` in the generated function.
176/// Set block and grid size bounds if known.
177static gpu::GPUFuncOp outlineKernelFuncImpl(gpu::LaunchOp launchOp,
178 StringRef kernelFnName,
179 SetVector<Value> &operands) {
180 Location loc = launchOp.getLoc();
181 // Create a builder with no insertion point, insertion will happen separately
182 // due to symbol table manipulation.
183 OpBuilder builder(launchOp.getContext());
184 Region &launchOpBody = launchOp.getBody();
185
186 // Identify uses from values defined outside of the scope of the launch
187 // operation.
188 getUsedValuesDefinedAbove(regions: launchOpBody, values&: operands);
189
190 // Create the gpu.func operation.
191 SmallVector<Type, 4> kernelOperandTypes;
192 kernelOperandTypes.reserve(N: operands.size());
193 for (Value operand : operands) {
194 kernelOperandTypes.push_back(Elt: operand.getType());
195 }
196 FunctionType type =
197 FunctionType::get(context: launchOp.getContext(), inputs: kernelOperandTypes, results: {});
198 auto outlinedFunc = gpu::GPUFuncOp::create(
199 builder, location: loc, name: kernelFnName, type,
200 workgroupAttributions: TypeRange(ValueRange(launchOp.getWorkgroupAttributionBBArgs())),
201 privateAttributions: TypeRange(ValueRange(launchOp.getPrivateAttributions())));
202 outlinedFunc.setKernel(true);
203
204 // If we can infer bounds on the grid and/or block sizes from the arguments
205 // to the launch op, propagate them to the generated kernel. This is safe
206 // because multiple launches with the same body are not deduplicated.
207 if (auto blockBounds =
208 maybeConstantDimsAttr(dims: launchOp.getBlockSizeOperandValues()))
209 outlinedFunc.setKnownBlockSizeAttr(blockBounds);
210 if (auto gridBounds =
211 maybeConstantDimsAttr(dims: launchOp.getGridSizeOperandValues()))
212 outlinedFunc.setKnownGridSizeAttr(gridBounds);
213 if (auto clusterSize = launchOp.getClusterSizeOperandValues()) {
214 if (auto clusterBounds = maybeConstantDimsAttr(dims: *clusterSize))
215 outlinedFunc.setKnownClusterSizeAttr(clusterBounds);
216 }
217
218 IRMapping map;
219
220 // Map the arguments corresponding to the launch parameters like blockIdx,
221 // threadIdx, etc. If cluster is present, then we also generate clusterIdx and
222 // clusterDim.
223 Region &outlinedFuncBody = outlinedFunc.getBody();
224 injectGpuIndexOperations(loc, launchFuncOpBody&: outlinedFuncBody, launchOpBody, map,
225 hasCluster: launchOp.hasClusterSize());
226
227 // Map memory attributions from the LaunOp op to the GPUFuncOp attributions.
228 for (const auto &[launchArg, funcArg] :
229 llvm::zip(t: launchOp.getWorkgroupAttributionBBArgs(),
230 u: outlinedFunc.getWorkgroupAttributionBBArgs()))
231 map.map(from: launchArg, to: funcArg);
232 for (const auto &[launchArg, funcArg] :
233 llvm::zip(t: launchOp.getPrivateAttributions(),
234 u: outlinedFunc.getPrivateAttributions()))
235 map.map(from: launchArg, to: funcArg);
236
237 // Map arguments from gpu.launch region to the arguments of the gpu.func
238 // operation.
239 Block &entryBlock = outlinedFuncBody.front();
240 for (const auto &operand : enumerate(First&: operands))
241 map.map(from: operand.value(), to: entryBlock.getArgument(i: operand.index()));
242
243 // Clone the region of the gpu.launch operation into the gpu.func operation.
244 launchOpBody.cloneInto(dest: &outlinedFuncBody, mapper&: map);
245
246 // Replace the terminator op with returns.
247 for (Block &block : launchOpBody) {
248 Block *clonedBlock = map.lookup(from: &block);
249 auto terminator = dyn_cast<gpu::TerminatorOp>(Val: clonedBlock->getTerminator());
250 if (!terminator)
251 continue;
252 OpBuilder replacer(terminator);
253 gpu::ReturnOp::create(builder&: replacer, location: terminator->getLoc());
254 terminator->erase();
255 }
256
257 // Splice now the entry block of the gpu.launch operation at the end of the
258 // gpu.func entry block and erase the redundant block.
259 Block *clonedLaunchOpEntry = map.lookup(from: &launchOpBody.front());
260 entryBlock.getOperations().splice(where: entryBlock.getOperations().end(),
261 L2&: clonedLaunchOpEntry->getOperations());
262 clonedLaunchOpEntry->erase();
263
264 return outlinedFunc;
265}
266
267gpu::GPUFuncOp mlir::outlineKernelFunc(gpu::LaunchOp launchOp,
268 StringRef kernelFnName,
269 llvm::SmallVectorImpl<Value> &operands) {
270 DenseSet<Value> inputOperandSet;
271 inputOperandSet.insert_range(R&: operands);
272 SetVector<Value> operandSet(llvm::from_range, operands);
273 auto funcOp = outlineKernelFuncImpl(launchOp, kernelFnName, operands&: operandSet);
274 for (auto operand : operandSet) {
275 if (!inputOperandSet.count(V: operand))
276 operands.push_back(Elt: operand);
277 }
278 return funcOp;
279}
280
281/// Replace `gpu.launch` operations with an `gpu.launch_func` operation
282/// launching `kernelFunc`. The kernel func contains the body of the
283/// `gpu.launch` with constant region arguments inlined.
284static void convertToLaunchFuncOp(gpu::LaunchOp launchOp,
285 gpu::GPUFuncOp kernelFunc,
286 ValueRange operands) {
287 OpBuilder builder(launchOp);
288 // The launch op has an optional dynamic shared memory size. If it doesn't
289 // exist, we use zero.
290 Value asyncToken = launchOp.getAsyncToken();
291 std::optional<gpu::KernelDim3> clusterSize =
292 launchOp.getClusterSizeOperandValues();
293 auto launchFunc = gpu::LaunchFuncOp::create(
294 builder, location: launchOp.getLoc(), kernelFunc,
295 gridSize: launchOp.getGridSizeOperandValues(), blockSize: launchOp.getBlockSizeOperandValues(),
296 dynamicSharedMemorySize: launchOp.getDynamicSharedMemorySize(), kernelOperands: operands,
297 asyncTokenType: asyncToken ? asyncToken.getType() : nullptr,
298 asyncDependencies: launchOp.getAsyncDependencies(), asyncObject: launchOp.getAsyncObject(), clusterSize);
299 if (launchOp.getCooperative())
300 launchFunc.setCooperative(true);
301 launchOp.replaceAllUsesWith(values&: launchFunc);
302 launchOp.erase();
303}
304
305namespace {
306/// Pass that moves ops which are likely an index computation into gpu.launch
307/// body.
308class GpuLaunchSinkIndexComputationsPass
309 : public impl::GpuLaunchSinkIndexComputationsPassBase<
310 GpuLaunchSinkIndexComputationsPass> {
311public:
312 void runOnOperation() override {
313 Operation *op = getOperation();
314 if (op->walk(callback: [](gpu::LaunchOp launch) {
315 // Pull in instructions that can be sunk
316 if (failed(Result: sinkOperationsIntoLaunchOp(launchOp: launch,
317 isSinkingBeneficiary: isLikelyAnIndexComputation)))
318 return WalkResult::interrupt();
319
320 return WalkResult::advance();
321 }).wasInterrupted())
322 signalPassFailure();
323 }
324};
325
326/// Pass that moves the kernel of each LaunchOp into its separate nested module.
327///
328/// This pass moves the kernel code of each LaunchOp into a function created
329/// inside a nested module. It also creates an external function of the same
330/// name in the parent module.
331///
332/// The gpu.modules are intended to be compiled to a cubin blob independently in
333/// a separate pass. The external functions can then be annotated with the
334/// symbol of the cubin accessor function.
335class GpuKernelOutliningPass
336 : public impl::GpuKernelOutliningPassBase<GpuKernelOutliningPass> {
337public:
338 using Base::Base;
339
340 LogicalResult initialize(MLIRContext *context) override {
341 // Initialize the data layout specification from the data layout string.
342 if (!dataLayoutStr.empty()) {
343 Attribute resultAttr = mlir::parseAttribute(attrStr: dataLayoutStr, context);
344 if (!resultAttr)
345 return failure();
346
347 dataLayoutSpec = dyn_cast<DataLayoutSpecInterface>(Val&: resultAttr);
348 if (!dataLayoutSpec)
349 return failure();
350 }
351
352 return success();
353 }
354
355 void runOnOperation() override {
356 SymbolTable symbolTable(getOperation());
357 bool modified = false;
358 for (auto func : getOperation().getOps<SymbolOpInterface>()) {
359 // Insert just after the function.
360 Block::iterator insertPt(func->getNextNode());
361 auto funcWalkResult = func.walk(callback: [&](gpu::LaunchOp op) {
362 SetVector<Value> operands;
363 std::string kernelFnName;
364 if (op.getFunction()) {
365 kernelFnName = op.getFunction()->str();
366 } else {
367 kernelFnName =
368 Twine(op->getParentOfType<SymbolOpInterface>().getName(),
369 "_kernel")
370 .str();
371 }
372
373 gpu::GPUFuncOp outlinedFunc =
374 outlineKernelFuncImpl(launchOp: op, kernelFnName, operands);
375
376 // Create nested module and insert outlinedFunc. The module will
377 // originally get the same name as the function, but may be renamed on
378 // insertion into the parent module.
379 FailureOr<gpu::GPUModuleOp> kernelModule =
380 createKernelModule(gpuLaunchOp: op, kernelFunc: outlinedFunc, parentSymbolTable: symbolTable);
381 if (failed(Result: kernelModule))
382 return WalkResult::interrupt();
383 symbolTable.insert(symbol: *kernelModule, insertPt);
384
385 // Potentially changes signature, pulling in constants.
386 convertToLaunchFuncOp(launchOp: op, kernelFunc: outlinedFunc, operands: operands.getArrayRef());
387 modified = true;
388 return WalkResult::advance();
389 });
390 if (funcWalkResult.wasInterrupted())
391 return signalPassFailure();
392 }
393
394 // If any new module was inserted in this module, annotate this module as
395 // a container module.
396 if (modified)
397 getOperation()->setDiscardableAttr(
398 name: gpu::GPUDialect::getContainerModuleAttrName(),
399 value: UnitAttr::get(context: &getContext()));
400 }
401
402private:
403 /// Returns a gpu.module containing kernelFunc and all callees (recursive).
404 FailureOr<gpu::GPUModuleOp>
405 createKernelModule(gpu::LaunchOp gpuLaunchOp, gpu::GPUFuncOp kernelFunc,
406 const SymbolTable &parentSymbolTable) {
407 // TODO: This code cannot use an OpBuilder because it must be inserted into
408 // a SymbolTable by the caller. SymbolTable needs to be refactored to
409 // prevent manual building of Ops with symbols in code using SymbolTables
410 // and then this needs to use the OpBuilder.
411 auto *context = getOperation().getContext();
412 OpBuilder builder(context);
413 std::string kernelModuleName;
414 gpu::GPUModuleOp kernelModule;
415 if (gpuLaunchOp.getModule()) {
416 kernelModuleName = gpuLaunchOp.getModule()->str();
417 kernelModule =
418 parentSymbolTable.lookup<gpu::GPUModuleOp>(name: kernelModuleName);
419 } else {
420 kernelModuleName = kernelFunc.getName();
421 }
422
423 // Check if the module already exists in the symbol table
424 if (!kernelModule) {
425 // If not found, create a new GPU module
426 kernelModule = gpu::GPUModuleOp::create(builder, location: kernelFunc.getLoc(),
427 name: kernelModuleName);
428 }
429
430 // If a valid data layout spec was provided, attach it to the kernel module.
431 // Otherwise, the default data layout will be used.
432 if (dataLayoutSpec)
433 kernelModule->setDiscardableAttr(name: DLTIDialect::kDataLayoutAttrName,
434 value: dataLayoutSpec);
435
436 SymbolTable symbolTable(kernelModule);
437 symbolTable.insert(symbol: kernelFunc);
438
439 SmallVector<Operation *, 8> symbolDefWorklist = {kernelFunc};
440 while (!symbolDefWorklist.empty()) {
441 if (std::optional<SymbolTable::UseRange> symbolUses =
442 SymbolTable::getSymbolUses(from: symbolDefWorklist.pop_back_val())) {
443 for (SymbolTable::SymbolUse symbolUse : *symbolUses) {
444 // Nested symbol references (e.g. @M::@F) cannot be resolved inside
445 // the kernel module when @M exists in the parent: @M will not be
446 // available inside the outlined module after the transformation.
447 // Ignore references whose root does not exist in the parent, as those
448 // are phantom references (e.g. in unregistered-op attributes) that
449 // were already unresolvable and are simply copied as-is.
450 if (!symbolUse.getSymbolRef().getNestedReferences().empty() &&
451 parentSymbolTable.lookup(
452 name: symbolUse.getSymbolRef().getRootReference())) {
453 symbolUse.getUser()->emitError(message: "nested symbol reference '")
454 << symbolUse.getSymbolRef()
455 << "' cannot be resolved inside the outlined kernel module; "
456 "gpu-kernel-outlining does not support cross-module symbol "
457 "references inside gpu.launch bodies";
458 kernelModule->erase();
459 return failure();
460 }
461 StringAttr symbolName = symbolUse.getSymbolRef().getLeafReference();
462 if (symbolTable.lookup(name: symbolName))
463 continue;
464
465 Operation *symbolDef = parentSymbolTable.lookup(name: symbolName);
466 if (!symbolDef)
467 continue;
468 Operation *symbolDefClone = symbolDef->clone();
469 symbolDefWorklist.push_back(Elt: symbolDefClone);
470 symbolTable.insert(symbol: symbolDefClone);
471 }
472 }
473 }
474
475 return kernelModule;
476 }
477
478 DataLayoutSpecInterface dataLayoutSpec;
479};
480
481} // namespace
482