1//===- AsyncRegionRewriter.cpp - Implementation of GPU async rewriters ----===//
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 pattern rewriters that make GPU op
10// within a region execute asynchronously.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/GPU/Transforms/Passes.h"
15
16#include "mlir/Dialect/Async/IR/Async.h"
17#include "mlir/Dialect/Func/IR/FuncOps.h"
18#include "mlir/Dialect/GPU/IR/GPUDialect.h"
19#include "mlir/Dialect/GPU/Utils/GPUUtils.h"
20#include "mlir/IR/Builders.h"
21#include "mlir/IR/IRMapping.h"
22#include "mlir/Interfaces/SideEffectInterfaces.h"
23#include "mlir/Support/LLVM.h"
24#include "llvm/ADT/TypeSwitch.h"
25
26namespace mlir {
27#define GEN_PASS_DEF_GPUASYNCREGIONPASS
28#include "mlir/Dialect/GPU/Transforms/Passes.h.inc"
29} // namespace mlir
30
31using namespace mlir;
32
33namespace {
34class GpuAsyncRegionPass
35 : public impl::GpuAsyncRegionPassBase<GpuAsyncRegionPass> {
36 struct ThreadTokenCallback;
37 struct DeferWaitCallback;
38 struct SingleTokenUseCallback;
39 void runOnOperation() override;
40};
41} // namespace
42
43static bool isTerminator(Operation *op) {
44 return op->mightHaveTrait<OpTrait::IsTerminator>();
45}
46static bool hasSideEffects(Operation *op) { return !isMemoryEffectFree(op); }
47
48// Region walk callback which makes GPU ops implementing the AsyncOpInterface
49// execute asynchronously.
50struct GpuAsyncRegionPass::ThreadTokenCallback {
51 ThreadTokenCallback(MLIRContext &context) : builder(&context) {}
52
53 WalkResult operator()(Block *block) {
54 for (Operation &op : make_early_inc_range(Range&: *block)) {
55 if (failed(Result: visit(op: &op)))
56 return WalkResult::interrupt();
57 }
58 return WalkResult::advance();
59 }
60
61private:
62 // If `op` implements the AsyncOpInterface, insert a `gpu.wait async` to
63 // create a current token (unless it already exists), and 'thread' that token
64 // through the `op` so that it executes asynchronously.
65 //
66 // If `op` is a terminator or an op with side-effects, insert a `gpu.wait` to
67 // host-synchronize execution. A `!gpu.async.token` will therefore only be
68 // used inside of its block and GPU execution will always synchronize with
69 // the host at block boundaries.
70 LogicalResult visit(Operation *op) {
71 if (isa<gpu::LaunchOp>(Val: op))
72 return op->emitOpError(message: "replace with gpu.launch_func first");
73 if (auto waitOp = llvm::dyn_cast<gpu::WaitOp>(Val: op)) {
74 if (currentToken)
75 waitOp.addAsyncDependency(token: currentToken);
76 currentToken = waitOp.getAsyncToken();
77 return success();
78 }
79 builder.setInsertionPoint(op);
80 if (auto asyncOp = dyn_cast<gpu::AsyncOpInterface>(Val: op))
81 return rewriteAsyncOp(asyncOp); // Replace GPU op with async version.
82 if (!currentToken)
83 return success();
84 // Insert host synchronization before terminator or op with side effects.
85 if (isTerminator(op) || hasSideEffects(op))
86 currentToken = createWaitOp(loc: op->getLoc(), resultType: Type(), operands: {currentToken});
87 return success();
88 }
89
90 // Replaces asyncOp with a clone that returns a token.
91 LogicalResult rewriteAsyncOp(gpu::AsyncOpInterface asyncOp) {
92 auto *op = asyncOp.getOperation();
93 auto tokenType = builder.getType<gpu::AsyncTokenType>();
94
95 // If there is no current token, insert a `gpu.wait async` without
96 // dependencies to create one.
97 if (!currentToken)
98 currentToken = createWaitOp(loc: op->getLoc(), resultType: tokenType, operands: {});
99 asyncOp.addAsyncDependency(token: currentToken);
100
101 // Return early if op returns a token already.
102 currentToken = asyncOp.getAsyncToken();
103 if (currentToken)
104 return success();
105
106 // Clone the op to return a token in addition to the other results.
107 SmallVector<Type, 1> resultTypes;
108 resultTypes.reserve(N: 1 + op->getNumResults());
109 copy(Range: op->getResultTypes(), Out: std::back_inserter(x&: resultTypes));
110 resultTypes.push_back(Elt: tokenType);
111 auto *newOp = Operation::create(
112 location: op->getLoc(), name: op->getName(), resultTypes, operands: op->getOperands(),
113 attributes: op->getDiscardableAttrDictionary(), properties: op->getPropertiesStorage(),
114 successors: op->getSuccessors(), numRegions: op->getNumRegions());
115
116 // Clone regions into new op.
117 IRMapping mapping;
118 for (auto pair : llvm::zip_first(t: op->getRegions(), u: newOp->getRegions()))
119 std::get<0>(t&: pair).cloneInto(dest: &std::get<1>(t&: pair), mapper&: mapping);
120
121 // Replace the op with the async clone.
122 auto results = newOp->getResults();
123 currentToken = results.back();
124 builder.insert(op: newOp);
125 op->replaceAllUsesWith(values: results.drop_back());
126 op->erase();
127
128 return success();
129 }
130
131 Value createWaitOp(Location loc, Type resultType, ValueRange operands) {
132 return gpu::WaitOp::create(builder, location: loc, asyncToken: resultType, asyncDependencies: operands)
133 .getAsyncToken();
134 }
135
136 OpBuilder builder;
137
138 // The token that represents the current asynchronous dependency. It's valid
139 // range starts with a `gpu.wait async` op, and ends with a `gpu.wait` op.
140 // In between, each gpu::AsyncOpInterface depends on the current token and
141 // produces the new one.
142 Value currentToken = {};
143};
144
145/// Erases `executeOp` and returns a clone with additional `results`.
146static async::ExecuteOp addExecuteResults(async::ExecuteOp executeOp,
147 ValueRange results) {
148 // Add values to async.yield op.
149 Operation *yieldOp = executeOp.getBody()->getTerminator();
150 yieldOp->insertOperands(index: yieldOp->getNumOperands(), operands: results);
151
152 // Construct new result type list with additional types.
153 SmallVector<Type, 2> resultTypes;
154 resultTypes.reserve(N: executeOp.getNumResults() + results.size());
155 transform(Range: executeOp.getResultTypes(), d_first: std::back_inserter(x&: resultTypes),
156 F: [](Type type) {
157 // Extract value type from !async.value.
158 if (auto valueType = dyn_cast<async::ValueType>(Val&: type))
159 return valueType.getValueType();
160 assert(isa<async::TokenType>(type) && "expected token type");
161 return type;
162 });
163 transform(Range&: results, d_first: std::back_inserter(x&: resultTypes),
164 F: [](Value value) { return value.getType(); });
165
166 // Clone executeOp with the extra results.
167 OpBuilder builder(executeOp);
168 auto newOp = async::ExecuteOp::create(
169 builder, location: executeOp.getLoc(),
170 resultTypes: TypeRange{resultTypes}.drop_front() /*drop token*/,
171 dependencies: executeOp.getDependencies(), operands: executeOp.getBodyOperands());
172 IRMapping mapper;
173 newOp.getRegion().getBlocks().clear();
174 executeOp.getRegion().cloneInto(dest: &newOp.getRegion(), mapper);
175
176 // Replace executeOp with cloned one.
177 executeOp.getOperation()->replaceAllUsesWith(
178 values: newOp.getResults().drop_back(n: results.size()));
179 executeOp.erase();
180
181 return newOp;
182}
183
184// Callback for `async.execute` ops which tries to push the contained
185// synchronous `gpu.wait` op to the dependencies of the `async.execute`.
186struct GpuAsyncRegionPass::DeferWaitCallback {
187 // If the `executeOp`s token is used only in `async.execute` or `async.await`
188 // ops, add the region's last `gpu.wait` op to the worklist if it is
189 // synchronous and is the last op with side effects.
190 void operator()(async::ExecuteOp executeOp) {
191 if (!areAllUsersExecuteOrAwait(token: executeOp.getToken()))
192 return;
193 // async.execute's region is currently restricted to one block.
194 for (auto &op : llvm::reverse(C: executeOp.getBody()->without_terminator())) {
195 if (auto waitOp = dyn_cast<gpu::WaitOp>(Val&: op)) {
196 if (!waitOp.getAsyncToken())
197 worklist.push_back(Elt: waitOp);
198 return;
199 }
200 if (hasSideEffects(op: &op))
201 return;
202 }
203 }
204
205 // The destructor performs the actual rewrite work.
206 ~DeferWaitCallback() {
207 for (size_t i = 0; i < worklist.size(); ++i) {
208 auto waitOp = worklist[i];
209 auto executeOp = waitOp->getParentOfType<async::ExecuteOp>();
210
211 // Erase `gpu.wait` and return async dependencies from execute op instead.
212 SmallVector<Value, 4> dependencies = waitOp.getAsyncDependencies();
213 waitOp.erase();
214 executeOp = addExecuteResults(executeOp, results: dependencies);
215
216 // Add the async dependency to each user of the `async.execute` token.
217 auto asyncTokens = executeOp.getResults().take_back(n: dependencies.size());
218 SmallVector<Operation *, 4> users(executeOp.getToken().user_begin(),
219 executeOp.getToken().user_end());
220 for (Operation *user : users)
221 addAsyncDependencyAfter(asyncTokens, op: user);
222 }
223 }
224
225private:
226 // Returns whether all token users are either 'async.execute' or 'async.await'
227 // ops. This is used as a requirement for pushing 'gpu.wait' ops from a
228 // 'async.execute' body to it's users. Specifically, we do not allow
229 // terminator users, because it could mean that the `async.execute` is inside
230 // control flow code.
231 static bool areAllUsersExecuteOrAwait(Value token) {
232 return !token.use_empty() &&
233 llvm::all_of(Range: token.getUsers(),
234 P: llvm::IsaPred<async::ExecuteOp, async::AwaitOp>);
235 }
236
237 // Add the `asyncToken` as dependency as needed after `op`.
238 void addAsyncDependencyAfter(ValueRange asyncTokens, Operation *op) {
239 OpBuilder builder(op->getContext());
240 auto loc = op->getLoc();
241
242 Block::iterator it;
243 SmallVector<Value, 1> tokens;
244 tokens.reserve(N: asyncTokens.size());
245 TypeSwitch<Operation *>(op)
246 .Case(caseFn: [&](async::AwaitOp awaitOp) {
247 // Add async.await ops to wait for the !gpu.async.tokens.
248 builder.setInsertionPointAfter(op);
249 for (auto asyncToken : asyncTokens)
250 tokens.push_back(
251 Elt: async::AwaitOp::create(builder, location: loc, operand: asyncToken).getResult());
252 // Set `it` after the inserted async.await ops.
253 it = builder.getInsertionPoint();
254 })
255 .Case(caseFn: [&](async::ExecuteOp executeOp) {
256 // Set `it` to the beginning of the region and add asyncTokens to the
257 // async.execute operands.
258 it = executeOp.getBody()->begin();
259 executeOp.getBodyOperandsMutable().append(values: asyncTokens);
260 SmallVector<Type, 1> tokenTypes(
261 asyncTokens.size(), builder.getType<gpu::AsyncTokenType>());
262 SmallVector<Location, 1> tokenLocs(asyncTokens.size(),
263 executeOp.getLoc());
264 copy(Range: executeOp.getBody()->addArguments(types: tokenTypes, locs: tokenLocs),
265 Out: std::back_inserter(x&: tokens));
266 });
267
268 // Advance `it` to terminator or op with side-effects.
269 it = std::find_if(first: it, last: Block::iterator(), pred: [](Operation &op) {
270 return isTerminator(op: &op) || hasSideEffects(op: &op);
271 });
272
273 // If `op` implements the AsyncOpInterface, add `token` to the list of async
274 // dependencies.
275 if (auto asyncOp = dyn_cast<gpu::AsyncOpInterface>(Val&: *it)) {
276 for (auto token : tokens)
277 asyncOp.addAsyncDependency(token);
278 return;
279 }
280
281 // Otherwise, insert a gpu.wait before 'it'.
282 builder.setInsertionPoint(block: it->getBlock(), insertPoint: it);
283 auto waitOp = gpu::WaitOp::create(builder, location: loc, asyncToken: Type{}, asyncDependencies: tokens);
284
285 // If the new waitOp is at the end of an async.execute region, add it to the
286 // worklist. 'operator()(executeOp)' would do the same, but this is faster.
287 auto executeOp = dyn_cast<async::ExecuteOp>(Val: it->getParentOp());
288 if (executeOp && areAllUsersExecuteOrAwait(token: executeOp.getToken()) &&
289 !it->getNextNode())
290 worklist.push_back(Elt: waitOp);
291 }
292
293 SmallVector<gpu::WaitOp, 8> worklist;
294};
295
296// Callback for `async.execute` ops which repeats !gpu.async.token results
297// so that each of them is only used once.
298struct GpuAsyncRegionPass::SingleTokenUseCallback {
299 void operator()(async::ExecuteOp executeOp) {
300 // Extract !gpu.async.token results which have multiple uses.
301 auto multiUseResults = llvm::make_filter_range(
302 Range: executeOp.getBodyResults(), Pred: [](OpResult result) {
303 if (result.use_empty() || result.hasOneUse())
304 return false;
305 auto valueType = dyn_cast<async::ValueType>(Val: result.getType());
306 return valueType &&
307 isa<gpu::AsyncTokenType>(Val: valueType.getValueType());
308 });
309 if (multiUseResults.empty())
310 return;
311
312 // Indices within !async.execute results (i.e. without the async.token).
313 SmallVector<int, 4> indices;
314 transform(Range&: multiUseResults, d_first: std::back_inserter(x&: indices),
315 F: [](OpResult result) {
316 return result.getResultNumber() - 1; // Index without token.
317 });
318
319 for (auto index : indices) {
320 assert(!executeOp.getBodyResults()[index].getUses().empty());
321 // Repeat async.yield token result, one for each use after the first one.
322 auto uses = llvm::drop_begin(RangeOrContainer: executeOp.getBodyResults()[index].getUses());
323 auto count = std::distance(first: uses.begin(), last: uses.end());
324 auto yieldOp = cast<async::YieldOp>(Val: executeOp.getBody()->getTerminator());
325 SmallVector<Value, 4> operands(count, yieldOp.getOperand(i: index));
326 executeOp = addExecuteResults(executeOp, results: operands);
327 // Update 'uses' to refer to the new executeOp.
328 uses = llvm::drop_begin(RangeOrContainer: executeOp.getBodyResults()[index].getUses());
329 auto results = executeOp.getBodyResults().take_back(n: count);
330 for (auto pair : llvm::zip(t&: uses, u&: results))
331 std::get<0>(t&: pair).set(std::get<1>(t&: pair));
332 }
333 }
334};
335
336// Replaces synchronous GPU ops in the op's region with asynchronous ones and
337// inserts the necessary synchronization (as gpu.wait ops). Assumes sequential
338// execution semantics and that no GPU ops are asynchronous yet.
339void GpuAsyncRegionPass::runOnOperation() {
340 if (getOperation()->walk(callback: ThreadTokenCallback(getContext())).wasInterrupted())
341 return signalPassFailure();
342
343 // Collect gpu.wait ops that we can move out of async.execute regions.
344 getOperation().getRegion().walk(callback: DeferWaitCallback());
345 // Makes each !gpu.async.token returned from async.execute op have single use.
346 getOperation().getRegion().walk(callback: SingleTokenUseCallback());
347}
348