1//===- AsyncParallelFor.cpp - Implementation of Async Parallel For --------===//
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 scf.parallel to scf.for + async.execute conversion pass.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Async/Passes.h"
14
15#include "PassDetail.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/Async/IR/Async.h"
18#include "mlir/Dialect/Async/Transforms.h"
19#include "mlir/Dialect/Func/IR/FuncOps.h"
20#include "mlir/Dialect/SCF/IR/SCF.h"
21#include "mlir/IR/IRMapping.h"
22#include "mlir/IR/Matchers.h"
23#include "mlir/IR/PatternMatch.h"
24#include "mlir/Support/LLVM.h"
25#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
26#include "mlir/Transforms/RegionUtils.h"
27#include "llvm/ADT/SmallVectorExtras.h"
28#include <utility>
29
30namespace mlir {
31#define GEN_PASS_DEF_ASYNCPARALLELFORPASS
32#include "mlir/Dialect/Async/Passes.h.inc"
33} // namespace mlir
34
35using namespace mlir;
36using namespace mlir::async;
37
38#define DEBUG_TYPE "async-parallel-for"
39
40namespace {
41
42// Rewrite scf.parallel operation into multiple concurrent async.execute
43// operations over non overlapping subranges of the original loop.
44//
45// Example:
46//
47// scf.parallel (%i, %j) = (%lbi, %lbj) to (%ubi, %ubj) step (%si, %sj) {
48// "do_some_compute"(%i, %j): () -> ()
49// }
50//
51// Converted to:
52//
53// // Parallel compute function that executes the parallel body region for
54// // a subset of the parallel iteration space defined by the one-dimensional
55// // compute block index.
56// func parallel_compute_function(%block_index : index, %block_size : index,
57// <parallel operation properties>, ...) {
58// // Compute multi-dimensional loop bounds for %block_index.
59// %block_lbi, %block_lbj = ...
60// %block_ubi, %block_ubj = ...
61//
62// // Clone parallel operation body into the scf.for loop nest.
63// scf.for %i = %blockLbi to %blockUbi {
64// scf.for %j = block_lbj to %block_ubj {
65// "do_some_compute"(%i, %j): () -> ()
66// }
67// }
68// }
69//
70// And a dispatch function depending on the `asyncDispatch` option.
71//
72// When async dispatch is on: (pseudocode)
73//
74// %block_size = ... compute parallel compute block size
75// %block_count = ... compute the number of compute blocks
76//
77// func @async_dispatch(%block_start : index, %block_end : index, ...) {
78// // Keep splitting block range until we reached a range of size 1.
79// while (%block_end - %block_start > 1) {
80// %mid_index = block_start + (block_end - block_start) / 2;
81// async.execute { call @async_dispatch(%mid_index, %block_end); }
82// %block_end = %mid_index
83// }
84//
85// // Call parallel compute function for a single block.
86// call @parallel_compute_fn(%block_start, %block_size, ...);
87// }
88//
89// // Launch async dispatch for [0, block_count) range.
90// call @async_dispatch(%c0, %block_count);
91//
92// When async dispatch is off:
93//
94// %block_size = ... compute parallel compute block size
95// %block_count = ... compute the number of compute blocks
96//
97// scf.for %block_index = %c0 to %block_count {
98// call @parallel_compute_fn(%block_index, %block_size, ...)
99// }
100//
101struct AsyncParallelForPass
102 : public impl::AsyncParallelForPassBase<AsyncParallelForPass> {
103 using Base::Base;
104
105 void runOnOperation() override;
106};
107
108struct AsyncParallelForRewrite : public OpRewritePattern<scf::ParallelOp> {
109public:
110 AsyncParallelForRewrite(
111 MLIRContext *ctx, bool asyncDispatch, int32_t numWorkerThreads,
112 AsyncMinTaskSizeComputationFunction computeMinTaskSize)
113 : OpRewritePattern(ctx), asyncDispatch(asyncDispatch),
114 numWorkerThreads(numWorkerThreads),
115 computeMinTaskSize(std::move(computeMinTaskSize)) {}
116
117 LogicalResult matchAndRewrite(scf::ParallelOp op,
118 PatternRewriter &rewriter) const override;
119
120private:
121 bool asyncDispatch;
122 int32_t numWorkerThreads;
123 AsyncMinTaskSizeComputationFunction computeMinTaskSize;
124};
125
126struct ParallelComputeFunctionType {
127 FunctionType type;
128 SmallVector<Value> captures;
129};
130
131// Helper struct to parse parallel compute function argument list.
132struct ParallelComputeFunctionArgs {
133 BlockArgument blockIndex();
134 BlockArgument blockSize();
135 ArrayRef<BlockArgument> tripCounts();
136 ArrayRef<BlockArgument> lowerBounds();
137 ArrayRef<BlockArgument> steps();
138 ArrayRef<BlockArgument> captures();
139
140 unsigned numLoops;
141 ArrayRef<BlockArgument> args;
142};
143
144struct ParallelComputeFunctionBounds {
145 SmallVector<IntegerAttr> tripCounts;
146 SmallVector<IntegerAttr> lowerBounds;
147 SmallVector<IntegerAttr> upperBounds;
148 SmallVector<IntegerAttr> steps;
149};
150
151struct ParallelComputeFunction {
152 unsigned numLoops;
153 func::FuncOp func;
154 llvm::SmallVector<Value> captures;
155};
156
157} // namespace
158
159BlockArgument ParallelComputeFunctionArgs::blockIndex() { return args[0]; }
160BlockArgument ParallelComputeFunctionArgs::blockSize() { return args[1]; }
161
162ArrayRef<BlockArgument> ParallelComputeFunctionArgs::tripCounts() {
163 return args.drop_front(N: 2).take_front(N: numLoops);
164}
165
166ArrayRef<BlockArgument> ParallelComputeFunctionArgs::lowerBounds() {
167 return args.drop_front(N: 2 + 1 * numLoops).take_front(N: numLoops);
168}
169
170ArrayRef<BlockArgument> ParallelComputeFunctionArgs::steps() {
171 return args.drop_front(N: 2 + 3 * numLoops).take_front(N: numLoops);
172}
173
174ArrayRef<BlockArgument> ParallelComputeFunctionArgs::captures() {
175 return args.drop_front(N: 2 + 4 * numLoops);
176}
177
178template <typename ValueRange>
179static SmallVector<IntegerAttr> integerConstants(ValueRange values) {
180 SmallVector<IntegerAttr> attrs(values.size());
181 for (unsigned i = 0; i < values.size(); ++i)
182 matchPattern(values[i], m_Constant(bind_value: &attrs[i]));
183 return attrs;
184}
185
186// Converts one-dimensional iteration index in the [0, tripCount) interval
187// into multidimensional iteration coordinate.
188static SmallVector<Value> delinearize(ImplicitLocOpBuilder &b, Value index,
189 ArrayRef<Value> tripCounts) {
190 SmallVector<Value> coords(tripCounts.size());
191 assert(!tripCounts.empty() && "tripCounts must be not empty");
192
193 for (ssize_t i = tripCounts.size() - 1; i >= 0; --i) {
194 coords[i] = arith::RemSIOp::create(builder&: b, lhs: index, rhs: tripCounts[i]);
195 index = arith::DivSIOp::create(builder&: b, lhs: index, rhs: tripCounts[i]);
196 }
197
198 return coords;
199}
200
201// Returns a function type and implicit captures for a parallel compute
202// function. We'll need a list of implicit captures to setup block and value
203// mapping when we'll clone the body of the parallel operation.
204static ParallelComputeFunctionType
205getParallelComputeFunctionType(scf::ParallelOp op, PatternRewriter &rewriter) {
206 // Values implicitly captured by the parallel operation.
207 llvm::SetVector<Value> captures;
208 getUsedValuesDefinedAbove(region&: op.getRegion(), limit&: op.getRegion(), values&: captures);
209
210 SmallVector<Type> inputs;
211 inputs.reserve(N: 2 + 4 * op.getNumLoops() + captures.size());
212
213 Type indexTy = rewriter.getIndexType();
214
215 // One-dimensional iteration space defined by the block index and size.
216 inputs.push_back(Elt: indexTy); // blockIndex
217 inputs.push_back(Elt: indexTy); // blockSize
218
219 // Multi-dimensional parallel iteration space defined by the loop trip counts.
220 for (unsigned i = 0; i < op.getNumLoops(); ++i)
221 inputs.push_back(Elt: indexTy); // loop tripCount
222
223 // Parallel operation lower bound, upper bound and step. Lower bound, upper
224 // bound and step passed as contiguous arguments:
225 // call @compute(%lb0, %lb1, ..., %ub0, %ub1, ..., %step0, %step1, ...)
226 for (unsigned i = 0; i < op.getNumLoops(); ++i) {
227 inputs.push_back(Elt: indexTy); // lower bound
228 inputs.push_back(Elt: indexTy); // upper bound
229 inputs.push_back(Elt: indexTy); // step
230 }
231
232 // Types of the implicit captures.
233 for (Value capture : captures)
234 inputs.push_back(Elt: capture.getType());
235
236 // Convert captures to vector for later convenience.
237 SmallVector<Value> capturesVector(captures.begin(), captures.end());
238 return {.type: rewriter.getFunctionType(inputs, results: TypeRange()), .captures: capturesVector};
239}
240
241// Create a parallel compute fuction from the parallel operation.
242static ParallelComputeFunction createParallelComputeFunction(
243 scf::ParallelOp op, const ParallelComputeFunctionBounds &bounds,
244 unsigned numBlockAlignedInnerLoops, PatternRewriter &rewriter) {
245 OpBuilder::InsertionGuard guard(rewriter);
246 ImplicitLocOpBuilder b(op.getLoc(), rewriter);
247
248 ModuleOp module = op->getParentOfType<ModuleOp>();
249
250 ParallelComputeFunctionType computeFuncType =
251 getParallelComputeFunctionType(op, rewriter);
252
253 FunctionType type = computeFuncType.type;
254 func::FuncOp func = func::FuncOp::create(
255 location: op.getLoc(),
256 name: numBlockAlignedInnerLoops > 0 ? "parallel_compute_fn_with_aligned_loops"
257 : "parallel_compute_fn",
258 type);
259 func.setPrivate();
260
261 // Insert function into the module symbol table and assign it unique name.
262 SymbolTable symbolTable(module);
263 symbolTable.insert(symbol: func);
264 rewriter.getListener()->notifyOperationInserted(op: func, /*previous=*/{});
265
266 // Create function entry block.
267 Block *block =
268 b.createBlock(parent: &func.getBody(), insertPt: func.begin(), argTypes: type.getInputs(),
269 locs: SmallVector<Location>(type.getNumInputs(), op.getLoc()));
270 b.setInsertionPointToEnd(block);
271
272 ParallelComputeFunctionArgs args = {.numLoops: op.getNumLoops(), .args: func.getArguments()};
273
274 // Block iteration position defined by the block index and size.
275 BlockArgument blockIndex = args.blockIndex();
276 BlockArgument blockSize = args.blockSize();
277
278 // Constants used below.
279 Value c0 = arith::ConstantIndexOp::create(builder&: b, value: 0);
280 Value c1 = arith::ConstantIndexOp::create(builder&: b, value: 1);
281
282 // Materialize known constants as constant operation in the function body.
283 auto values = [&](ArrayRef<BlockArgument> args, ArrayRef<IntegerAttr> attrs) {
284 return llvm::map_to_vector(C: llvm::zip(t&: args, u&: attrs),
285 F: [&](auto tuple) -> Value {
286 if (IntegerAttr attr = std::get<1>(tuple))
287 return arith::ConstantOp::create(builder&: b, value: attr);
288 return std::get<0>(tuple);
289 });
290 };
291
292 // Multi-dimensional parallel iteration space defined by the loop trip counts.
293 auto tripCounts = values(args.tripCounts(), bounds.tripCounts);
294
295 // Parallel operation lower bound and step.
296 auto lowerBounds = values(args.lowerBounds(), bounds.lowerBounds);
297 auto steps = values(args.steps(), bounds.steps);
298
299 // Remaining arguments are implicit captures of the parallel operation.
300 ArrayRef<BlockArgument> captures = args.captures();
301
302 // Compute a product of trip counts to get the size of the flattened
303 // one-dimensional iteration space.
304 Value tripCount = tripCounts[0];
305 for (unsigned i = 1; i < tripCounts.size(); ++i)
306 tripCount = arith::MulIOp::create(builder&: b, lhs: tripCount, rhs: tripCounts[i]);
307
308 // Find one-dimensional iteration bounds: [blockFirstIndex, blockLastIndex]:
309 // blockFirstIndex = blockIndex * blockSize
310 Value blockFirstIndex = arith::MulIOp::create(builder&: b, lhs: blockIndex, rhs: blockSize);
311
312 // The last one-dimensional index in the block defined by the `blockIndex`:
313 // blockLastIndex = min(blockFirstIndex + blockSize, tripCount) - 1
314 Value blockEnd0 = arith::AddIOp::create(builder&: b, lhs: blockFirstIndex, rhs: blockSize);
315 Value blockEnd1 = arith::MinSIOp::create(builder&: b, lhs: blockEnd0, rhs: tripCount);
316 Value blockLastIndex = arith::SubIOp::create(builder&: b, lhs: blockEnd1, rhs: c1);
317
318 // Convert one-dimensional indices to multi-dimensional coordinates.
319 auto blockFirstCoord = delinearize(b, index: blockFirstIndex, tripCounts);
320 auto blockLastCoord = delinearize(b, index: blockLastIndex, tripCounts);
321
322 // Compute loops upper bounds derived from the block last coordinates:
323 // blockEndCoord[i] = blockLastCoord[i] + 1
324 //
325 // Block first and last coordinates can be the same along the outer compute
326 // dimension when inner compute dimension contains multiple blocks.
327 SmallVector<Value> blockEndCoord(op.getNumLoops());
328 for (size_t i = 0; i < blockLastCoord.size(); ++i)
329 blockEndCoord[i] = arith::AddIOp::create(builder&: b, lhs: blockLastCoord[i], rhs: c1);
330
331 // Construct a loop nest out of scf.for operations that will iterate over
332 // all coordinates in [blockFirstCoord, blockLastCoord] range.
333 using LoopBodyBuilder =
334 std::function<void(OpBuilder &, Location, Value, ValueRange)>;
335 using LoopNestBuilder = std::function<LoopBodyBuilder(size_t loopIdx)>;
336
337 // Parallel region induction variables computed from the multi-dimensional
338 // iteration coordinate using parallel operation bounds and step:
339 //
340 // computeBlockInductionVars[loopIdx] =
341 // lowerBound[loopIdx] + blockCoord[loopIdx] * step[loopIdx]
342 SmallVector<Value> computeBlockInductionVars(op.getNumLoops());
343
344 // We need to know if we are in the first or last iteration of the
345 // multi-dimensional loop for each loop in the nest, so we can decide what
346 // loop bounds should we use for the nested loops: bounds defined by compute
347 // block interval, or bounds defined by the parallel operation.
348 //
349 // Example: 2d parallel operation
350 // i j
351 // loop sizes: [50, 50]
352 // first coord: [25, 25]
353 // last coord: [30, 30]
354 //
355 // If `i` is equal to 25 then iteration over `j` should start at 25, when `i`
356 // is between 25 and 30 it should start at 0. The upper bound for `j` should
357 // be 50, except when `i` is equal to 30, then it should also be 30.
358 //
359 // Value at ith position specifies if all loops in [0, i) range of the loop
360 // nest are in the first/last iteration.
361 SmallVector<Value> isBlockFirstCoord(op.getNumLoops());
362 SmallVector<Value> isBlockLastCoord(op.getNumLoops());
363
364 // Builds inner loop nest inside async.execute operation that does all the
365 // work concurrently.
366 LoopNestBuilder workLoopBuilder = [&](size_t loopIdx) -> LoopBodyBuilder {
367 return [&, loopIdx](OpBuilder &nestedBuilder, Location loc, Value iv,
368 ValueRange args) {
369 ImplicitLocOpBuilder b(loc, nestedBuilder);
370
371 // Compute induction variable for `loopIdx`.
372 computeBlockInductionVars[loopIdx] =
373 arith::AddIOp::create(builder&: b, lhs: lowerBounds[loopIdx],
374 rhs: arith::MulIOp::create(builder&: b, lhs: iv, rhs: steps[loopIdx]));
375
376 // Check if we are inside first or last iteration of the loop.
377 isBlockFirstCoord[loopIdx] = arith::CmpIOp::create(
378 builder&: b, predicate: arith::CmpIPredicate::eq, lhs: iv, rhs: blockFirstCoord[loopIdx]);
379 isBlockLastCoord[loopIdx] = arith::CmpIOp::create(
380 builder&: b, predicate: arith::CmpIPredicate::eq, lhs: iv, rhs: blockLastCoord[loopIdx]);
381
382 // Check if the previous loop is in its first or last iteration.
383 if (loopIdx > 0) {
384 isBlockFirstCoord[loopIdx] = arith::AndIOp::create(
385 builder&: b, lhs: isBlockFirstCoord[loopIdx], rhs: isBlockFirstCoord[loopIdx - 1]);
386 isBlockLastCoord[loopIdx] = arith::AndIOp::create(
387 builder&: b, lhs: isBlockLastCoord[loopIdx], rhs: isBlockLastCoord[loopIdx - 1]);
388 }
389
390 // Keep building loop nest.
391 if (loopIdx < op.getNumLoops() - 1) {
392 if (loopIdx + 1 >= op.getNumLoops() - numBlockAlignedInnerLoops) {
393 // For block aligned loops we always iterate starting from 0 up to
394 // the loop trip counts.
395 scf::ForOp::create(builder&: b, lowerBound: c0, upperBound: tripCounts[loopIdx + 1], step: c1, initArgs: ValueRange(),
396 odsArg4: workLoopBuilder(loopIdx + 1));
397
398 } else {
399 // Select nested loop lower/upper bounds depending on our position in
400 // the multi-dimensional iteration space.
401 auto lb = arith::SelectOp::create(builder&: b, condition: isBlockFirstCoord[loopIdx],
402 true_value: blockFirstCoord[loopIdx + 1], false_value: c0);
403
404 auto ub = arith::SelectOp::create(builder&: b, condition: isBlockLastCoord[loopIdx],
405 true_value: blockEndCoord[loopIdx + 1],
406 false_value: tripCounts[loopIdx + 1]);
407
408 scf::ForOp::create(builder&: b, lowerBound: lb, upperBound: ub, step: c1, initArgs: ValueRange(),
409 odsArg4: workLoopBuilder(loopIdx + 1));
410 }
411
412 scf::YieldOp::create(builder&: b, location: loc);
413 return;
414 }
415
416 // Copy the body of the parallel op into the inner-most loop.
417 IRMapping mapping;
418 mapping.map(from: op.getInductionVars(), to&: computeBlockInductionVars);
419 mapping.map(from&: computeFuncType.captures, to&: captures);
420
421 for (auto &bodyOp : op.getRegion().front().without_terminator())
422 b.clone(op&: bodyOp, mapper&: mapping);
423 scf::YieldOp::create(builder&: b, location: loc);
424 };
425 };
426
427 scf::ForOp::create(builder&: b, lowerBound: blockFirstCoord[0], upperBound: blockEndCoord[0], step: c1, initArgs: ValueRange(),
428 odsArg4: workLoopBuilder(0));
429 func::ReturnOp::create(builder&: b, operands: ValueRange());
430
431 return {.numLoops: op.getNumLoops(), .func: func, .captures: std::move(computeFuncType.captures)};
432}
433
434// Creates recursive async dispatch function for the given parallel compute
435// function. Dispatch function keeps splitting block range into halves until it
436// reaches a single block, and then excecutes it inline.
437//
438// Function pseudocode (mix of C++ and MLIR):
439//
440// func @async_dispatch(%block_start : index, %block_end : index, ...) {
441//
442// // Keep splitting block range until we reached a range of size 1.
443// while (%block_end - %block_start > 1) {
444// %mid_index = block_start + (block_end - block_start) / 2;
445// async.execute { call @async_dispatch(%mid_index, %block_end); }
446// %block_end = %mid_index
447// }
448//
449// // Call parallel compute function for a single block.
450// call @parallel_compute_fn(%block_start, %block_size, ...);
451// }
452//
453static func::FuncOp
454createAsyncDispatchFunction(ParallelComputeFunction &computeFunc,
455 PatternRewriter &rewriter) {
456 OpBuilder::InsertionGuard guard(rewriter);
457 Location loc = computeFunc.func.getLoc();
458 ImplicitLocOpBuilder b(loc, rewriter);
459
460 ModuleOp module = computeFunc.func->getParentOfType<ModuleOp>();
461
462 ArrayRef<Type> computeFuncInputTypes =
463 computeFunc.func.getFunctionType().getInputs();
464
465 // Compared to the parallel compute function async dispatch function takes
466 // additional !async.group argument. Also instead of a single `blockIndex` it
467 // takes `blockStart` and `blockEnd` arguments to define the range of
468 // dispatched blocks.
469 SmallVector<Type> inputTypes;
470 inputTypes.push_back(Elt: async::GroupType::get(ctx: rewriter.getContext()));
471 inputTypes.push_back(Elt: rewriter.getIndexType()); // add blockStart argument
472 inputTypes.append(in_start: computeFuncInputTypes.begin(), in_end: computeFuncInputTypes.end());
473
474 FunctionType type = rewriter.getFunctionType(inputs: inputTypes, results: TypeRange());
475 func::FuncOp func = func::FuncOp::create(location: loc, name: "async_dispatch_fn", type);
476 func.setPrivate();
477
478 // Insert function into the module symbol table and assign it unique name.
479 SymbolTable symbolTable(module);
480 symbolTable.insert(symbol: func);
481 rewriter.getListener()->notifyOperationInserted(op: func, /*previous=*/{});
482
483 // Create function entry block.
484 Block *block = b.createBlock(parent: &func.getBody(), insertPt: func.begin(), argTypes: type.getInputs(),
485 locs: SmallVector<Location>(type.getNumInputs(), loc));
486 b.setInsertionPointToEnd(block);
487
488 Type indexTy = b.getIndexType();
489 Value c1 = arith::ConstantIndexOp::create(builder&: b, value: 1);
490 Value c2 = arith::ConstantIndexOp::create(builder&: b, value: 2);
491
492 // Get the async group that will track async dispatch completion.
493 Value group = block->getArgument(i: 0);
494
495 // Get the block iteration range: [blockStart, blockEnd)
496 Value blockStart = block->getArgument(i: 1);
497 Value blockEnd = block->getArgument(i: 2);
498
499 // Create a work splitting while loop for the [blockStart, blockEnd) range.
500 SmallVector<Type> types = {indexTy, indexTy};
501 SmallVector<Value> operands = {blockStart, blockEnd};
502 SmallVector<Location> locations = {loc, loc};
503
504 // Create a recursive dispatch loop.
505 scf::WhileOp whileOp = scf::WhileOp::create(builder&: b, resultTypes: types, operands);
506 Block *before = b.createBlock(parent: &whileOp.getBefore(), insertPt: {}, argTypes: types, locs: locations);
507 Block *after = b.createBlock(parent: &whileOp.getAfter(), insertPt: {}, argTypes: types, locs: locations);
508
509 // Setup dispatch loop condition block: decide if we need to go into the
510 // `after` block and launch one more async dispatch.
511 {
512 b.setInsertionPointToEnd(before);
513 Value start = before->getArgument(i: 0);
514 Value end = before->getArgument(i: 1);
515 Value distance = arith::SubIOp::create(builder&: b, lhs: end, rhs: start);
516 Value dispatch =
517 arith::CmpIOp::create(builder&: b, predicate: arith::CmpIPredicate::sgt, lhs: distance, rhs: c1);
518 scf::ConditionOp::create(builder&: b, condition: dispatch, args: before->getArguments());
519 }
520
521 // Setup the async dispatch loop body: recursively call dispatch function
522 // for the seconds half of the original range and go to the next iteration.
523 {
524 b.setInsertionPointToEnd(after);
525 Value start = after->getArgument(i: 0);
526 Value end = after->getArgument(i: 1);
527 Value distance = arith::SubIOp::create(builder&: b, lhs: end, rhs: start);
528 Value halfDistance = arith::DivSIOp::create(builder&: b, lhs: distance, rhs: c2);
529 Value midIndex = arith::AddIOp::create(builder&: b, lhs: start, rhs: halfDistance);
530
531 // Call parallel compute function inside the async.execute region.
532 auto executeBodyBuilder = [&](OpBuilder &executeBuilder,
533 Location executeLoc, ValueRange executeArgs) {
534 // Update the original `blockStart` and `blockEnd` with new range.
535 SmallVector<Value> operands{block->getArguments().begin(),
536 block->getArguments().end()};
537 operands[1] = midIndex;
538 operands[2] = end;
539
540 func::CallOp::create(builder&: executeBuilder, location: executeLoc, callee: func.getSymName(),
541 results: func.getResultTypes(), operands);
542 async::YieldOp::create(builder&: executeBuilder, location: executeLoc, operands: ValueRange());
543 };
544
545 // Create async.execute operation to dispatch half of the block range.
546 auto execute = ExecuteOp::create(builder&: b, resultTypes: TypeRange(), dependencies: ValueRange(), operands: ValueRange(),
547 bodyBuilder: executeBodyBuilder);
548 AddToGroupOp::create(builder&: b, rank: indexTy, operand: execute.getToken(), group);
549 scf::YieldOp::create(builder&: b, results: ValueRange({start, midIndex}));
550 }
551
552 // After dispatching async operations to process the tail of the block range
553 // call the parallel compute function for the first block of the range.
554 b.setInsertionPointAfter(whileOp);
555
556 // Drop async dispatch specific arguments: async group, block start and end.
557 auto forwardedInputs = block->getArguments().drop_front(N: 3);
558 SmallVector<Value> computeFuncOperands = {blockStart};
559 computeFuncOperands.append(in_start: forwardedInputs.begin(), in_end: forwardedInputs.end());
560
561 func::CallOp::create(builder&: b, callee: computeFunc.func.getSymName(),
562 results: computeFunc.func.getResultTypes(), operands: computeFuncOperands);
563 func::ReturnOp::create(builder&: b, operands: ValueRange());
564
565 return func;
566}
567
568// Launch async dispatch of the parallel compute function.
569static void doAsyncDispatch(ImplicitLocOpBuilder &b, PatternRewriter &rewriter,
570 ParallelComputeFunction &parallelComputeFunction,
571 scf::ParallelOp op, Value blockSize,
572 Value blockCount,
573 const SmallVector<Value> &tripCounts) {
574 MLIRContext *ctx = op->getContext();
575
576 // Add one more level of indirection to dispatch parallel compute functions
577 // using async operations and recursive work splitting.
578 func::FuncOp asyncDispatchFunction =
579 createAsyncDispatchFunction(computeFunc&: parallelComputeFunction, rewriter);
580
581 Value c0 = arith::ConstantIndexOp::create(builder&: b, value: 0);
582 Value c1 = arith::ConstantIndexOp::create(builder&: b, value: 1);
583
584 // Appends operands shared by async dispatch and parallel compute functions to
585 // the given operands vector.
586 auto appendBlockComputeOperands = [&](SmallVector<Value> &operands) {
587 operands.append(RHS: tripCounts);
588 operands.append(in_start: op.getLowerBound().begin(), in_end: op.getLowerBound().end());
589 operands.append(in_start: op.getUpperBound().begin(), in_end: op.getUpperBound().end());
590 operands.append(in_start: op.getStep().begin(), in_end: op.getStep().end());
591 operands.append(RHS: parallelComputeFunction.captures);
592 };
593
594 // Check if the block size is one, in this case we can skip the async dispatch
595 // completely. If this will be known statically, then canonicalization will
596 // erase async group operations.
597 Value isSingleBlock =
598 arith::CmpIOp::create(builder&: b, predicate: arith::CmpIPredicate::eq, lhs: blockCount, rhs: c1);
599
600 auto syncDispatch = [&](OpBuilder &nestedBuilder, Location loc) {
601 ImplicitLocOpBuilder b(loc, nestedBuilder);
602
603 // Call parallel compute function for the single block.
604 SmallVector<Value> operands = {c0, blockSize};
605 appendBlockComputeOperands(operands);
606
607 func::CallOp::create(builder&: b, callee: parallelComputeFunction.func.getSymName(),
608 results: parallelComputeFunction.func.getResultTypes(),
609 operands);
610 scf::YieldOp::create(builder&: b);
611 };
612
613 auto asyncDispatch = [&](OpBuilder &nestedBuilder, Location loc) {
614 ImplicitLocOpBuilder b(loc, nestedBuilder);
615
616 // Create an async.group to wait on all async tokens from the concurrent
617 // execution of multiple parallel compute function. First block will be
618 // executed synchronously in the caller thread.
619 Value groupSize = arith::SubIOp::create(builder&: b, lhs: blockCount, rhs: c1);
620 Value group = CreateGroupOp::create(builder&: b, result: GroupType::get(ctx), size: groupSize);
621
622 // Launch async dispatch function for [0, blockCount) range.
623 SmallVector<Value> operands = {group, c0, blockCount, blockSize};
624 appendBlockComputeOperands(operands);
625
626 func::CallOp::create(builder&: b, callee: asyncDispatchFunction.getSymName(),
627 results: asyncDispatchFunction.getResultTypes(), operands);
628
629 // Wait for the completion of all parallel compute operations.
630 AwaitAllOp::create(builder&: b, operand: group);
631
632 scf::YieldOp::create(builder&: b);
633 };
634
635 // Dispatch either single block compute function, or launch async dispatch.
636 scf::IfOp::create(builder&: b, cond: isSingleBlock, thenBuilder: syncDispatch, elseBuilder: asyncDispatch);
637}
638
639// Dispatch parallel compute functions by submitting all async compute tasks
640// from a simple for loop in the caller thread.
641static void
642doSequentialDispatch(ImplicitLocOpBuilder &b, PatternRewriter &rewriter,
643 ParallelComputeFunction &parallelComputeFunction,
644 scf::ParallelOp op, Value blockSize, Value blockCount,
645 const SmallVector<Value> &tripCounts) {
646 MLIRContext *ctx = op->getContext();
647
648 func::FuncOp compute = parallelComputeFunction.func;
649
650 Value c0 = arith::ConstantIndexOp::create(builder&: b, value: 0);
651 Value c1 = arith::ConstantIndexOp::create(builder&: b, value: 1);
652
653 // Create an async.group to wait on all async tokens from the concurrent
654 // execution of multiple parallel compute function. First block will be
655 // executed synchronously in the caller thread.
656 Value groupSize = arith::SubIOp::create(builder&: b, lhs: blockCount, rhs: c1);
657 Value group = CreateGroupOp::create(builder&: b, result: GroupType::get(ctx), size: groupSize);
658
659 // Call parallel compute function for all blocks.
660 using LoopBodyBuilder =
661 std::function<void(OpBuilder &, Location, Value, ValueRange)>;
662
663 // Returns parallel compute function operands to process the given block.
664 auto computeFuncOperands = [&](Value blockIndex) -> SmallVector<Value> {
665 SmallVector<Value> computeFuncOperands = {blockIndex, blockSize};
666 computeFuncOperands.append(RHS: tripCounts);
667 computeFuncOperands.append(in_start: op.getLowerBound().begin(),
668 in_end: op.getLowerBound().end());
669 computeFuncOperands.append(in_start: op.getUpperBound().begin(),
670 in_end: op.getUpperBound().end());
671 computeFuncOperands.append(in_start: op.getStep().begin(), in_end: op.getStep().end());
672 computeFuncOperands.append(RHS: parallelComputeFunction.captures);
673 return computeFuncOperands;
674 };
675
676 // Induction variable is the index of the block: [0, blockCount).
677 LoopBodyBuilder loopBuilder = [&](OpBuilder &loopBuilder, Location loc,
678 Value iv, ValueRange args) {
679 ImplicitLocOpBuilder b(loc, loopBuilder);
680
681 // Call parallel compute function inside the async.execute region.
682 auto executeBodyBuilder = [&](OpBuilder &executeBuilder,
683 Location executeLoc, ValueRange executeArgs) {
684 func::CallOp::create(builder&: executeBuilder, location: executeLoc, callee: compute.getSymName(),
685 results: compute.getResultTypes(), operands: computeFuncOperands(iv));
686 async::YieldOp::create(builder&: executeBuilder, location: executeLoc, operands: ValueRange());
687 };
688
689 // Create async.execute operation to launch parallel computate function.
690 auto execute = ExecuteOp::create(builder&: b, resultTypes: TypeRange(), dependencies: ValueRange(), operands: ValueRange(),
691 bodyBuilder: executeBodyBuilder);
692 AddToGroupOp::create(builder&: b, rank: rewriter.getIndexType(), operand: execute.getToken(), group);
693 scf::YieldOp::create(builder&: b);
694 };
695
696 // Iterate over all compute blocks and launch parallel compute operations.
697 scf::ForOp::create(builder&: b, lowerBound: c1, upperBound: blockCount, step: c1, initArgs: ValueRange(), odsArg4: loopBuilder);
698
699 // Call parallel compute function for the first block in the caller thread.
700 func::CallOp::create(builder&: b, callee: compute.getSymName(), results: compute.getResultTypes(),
701 operands: computeFuncOperands(c0));
702
703 // Wait for the completion of all async compute operations.
704 AwaitAllOp::create(builder&: b, operand: group);
705}
706
707LogicalResult
708AsyncParallelForRewrite::matchAndRewrite(scf::ParallelOp op,
709 PatternRewriter &rewriter) const {
710 // We do not currently support rewrite for parallel op with reductions.
711 if (op.getNumReductions() != 0)
712 return failure();
713 // The trip count computation below assumes signed bounds.
714 if (op.getUnsignedCmp())
715 return rewriter.notifyMatchFailure(
716 arg&: op, msg: "unsigned loop bounds are not supported");
717
718 ImplicitLocOpBuilder b(op.getLoc(), rewriter);
719
720 // Computing minTaskSize emits IR and can be implemented as executing a cost
721 // model on the body of the scf.parallel. Thus it needs to be computed before
722 // the body of the scf.parallel has been manipulated.
723 Value minTaskSize = computeMinTaskSize(b, op);
724
725 // Make sure that all constants will be inside the parallel operation body to
726 // reduce the number of parallel compute function arguments.
727 cloneConstantsIntoTheRegion(region&: op.getRegion(), builder&: rewriter);
728
729 // Compute trip count for each loop induction variable:
730 // tripCount = ceil_div(upperBound - lowerBound, step);
731 SmallVector<Value> tripCounts(op.getNumLoops());
732 for (size_t i = 0; i < op.getNumLoops(); ++i) {
733 auto lb = op.getLowerBound()[i];
734 auto ub = op.getUpperBound()[i];
735 auto step = op.getStep()[i];
736 auto range = b.createOrFold<arith::SubIOp>(args&: ub, args&: lb);
737 tripCounts[i] = b.createOrFold<arith::CeilDivSIOp>(args&: range, args&: step);
738 }
739
740 // Compute a product of trip counts to get the 1-dimensional iteration space
741 // for the scf.parallel operation.
742 Value tripCount = tripCounts[0];
743 for (size_t i = 1; i < tripCounts.size(); ++i)
744 tripCount = arith::MulIOp::create(builder&: b, lhs: tripCount, rhs: tripCounts[i]);
745
746 // Short circuit no-op parallel loops (zero iterations) that can arise from
747 // the memrefs with dynamic dimension(s) equal to zero.
748 Value c0 = arith::ConstantIndexOp::create(builder&: b, value: 0);
749 Value isZeroIterations =
750 arith::CmpIOp::create(builder&: b, predicate: arith::CmpIPredicate::eq, lhs: tripCount, rhs: c0);
751
752 // Do absolutely nothing if the trip count is zero.
753 auto noOp = [&](OpBuilder &nestedBuilder, Location loc) {
754 scf::YieldOp::create(builder&: nestedBuilder, location: loc);
755 };
756
757 // Compute the parallel block size and dispatch concurrent tasks computing
758 // results for each block.
759 auto dispatch = [&](OpBuilder &nestedBuilder, Location loc) {
760 ImplicitLocOpBuilder b(loc, nestedBuilder);
761
762 // Collect statically known constants defining the loop nest in the parallel
763 // compute function. LLVM can't always push constants across the non-trivial
764 // async dispatch call graph, by providing these values explicitly we can
765 // choose to build more efficient loop nest, and rely on a better constant
766 // folding, loop unrolling and vectorization.
767 ParallelComputeFunctionBounds staticBounds = {
768 .tripCounts: integerConstants(values: tripCounts),
769 .lowerBounds: integerConstants(values: op.getLowerBound()),
770 .upperBounds: integerConstants(values: op.getUpperBound()),
771 .steps: integerConstants(values: op.getStep()),
772 };
773
774 // Find how many inner iteration dimensions are statically known, and their
775 // product is smaller than the `512`. We align the parallel compute block
776 // size by the product of statically known dimensions, so that we can
777 // guarantee that the inner loops executes from 0 to the loop trip counts
778 // and we can elide dynamic loop boundaries, and give LLVM an opportunity to
779 // unroll the loops. The constant `512` is arbitrary, it should depend on
780 // how many iterations LLVM will typically decide to unroll.
781 static constexpr int64_t maxUnrollableIterations = 512;
782
783 // The number of inner loops with statically known number of iterations less
784 // than the `maxUnrollableIterations` value.
785 int numUnrollableLoops = 0;
786
787 auto getInt = [](IntegerAttr attr) { return attr ? attr.getInt() : 0; };
788
789 SmallVector<int64_t> numIterations(op.getNumLoops());
790 numIterations.back() = getInt(staticBounds.tripCounts.back());
791
792 for (int i = op.getNumLoops() - 2; i >= 0; --i) {
793 int64_t tripCount = getInt(staticBounds.tripCounts[i]);
794 int64_t innerIterations = numIterations[i + 1];
795 numIterations[i] = tripCount * innerIterations;
796
797 // Update the number of inner loops that we can potentially unroll.
798 if (innerIterations > 0 && innerIterations <= maxUnrollableIterations)
799 numUnrollableLoops++;
800 }
801
802 Value numWorkerThreadsVal;
803 if (numWorkerThreads >= 0)
804 numWorkerThreadsVal = arith::ConstantIndexOp::create(builder&: b, value: numWorkerThreads);
805 else
806 numWorkerThreadsVal = async::RuntimeNumWorkerThreadsOp::create(builder&: b);
807
808 // With large number of threads the value of creating many compute blocks
809 // is reduced because the problem typically becomes memory bound. For this
810 // reason we scale the number of workers using an equivalent to the
811 // following logic:
812 // float overshardingFactor = numWorkerThreads <= 4 ? 8.0
813 // : numWorkerThreads <= 8 ? 4.0
814 // : numWorkerThreads <= 16 ? 2.0
815 // : numWorkerThreads <= 32 ? 1.0
816 // : numWorkerThreads <= 64 ? 0.8
817 // : 0.6;
818
819 // Pairs of non-inclusive lower end of the bracket and factor that the
820 // number of workers needs to be scaled with if it falls in that bucket.
821 const SmallVector<std::pair<int, float>> overshardingBrackets = {
822 {4, 4.0f}, {8, 2.0f}, {16, 1.0f}, {32, 0.8f}, {64, 0.6f}};
823 const float initialOvershardingFactor = 8.0f;
824
825 Value scalingFactor = arith::ConstantFloatOp::create(
826 builder&: b, type: b.getF32Type(), value: llvm::APFloat(initialOvershardingFactor));
827 for (const std::pair<int, float> &p : overshardingBrackets) {
828 Value bracketBegin = arith::ConstantIndexOp::create(builder&: b, value: p.first);
829 Value inBracket = arith::CmpIOp::create(
830 builder&: b, predicate: arith::CmpIPredicate::sgt, lhs: numWorkerThreadsVal, rhs: bracketBegin);
831 Value bracketScalingFactor = arith::ConstantFloatOp::create(
832 builder&: b, type: b.getF32Type(), value: llvm::APFloat(p.second));
833 scalingFactor = arith::SelectOp::create(
834 builder&: b, condition: inBracket, true_value: bracketScalingFactor, false_value: scalingFactor);
835 }
836 Value numWorkersIndex =
837 arith::IndexCastOp::create(builder&: b, out: b.getI32Type(), in: numWorkerThreadsVal);
838 Value numWorkersFloat =
839 arith::SIToFPOp::create(builder&: b, out: b.getF32Type(), in: numWorkersIndex);
840 Value scaledNumWorkers =
841 arith::MulFOp::create(builder&: b, lhs: scalingFactor, rhs: numWorkersFloat);
842 Value scaledNumInt =
843 arith::FPToSIOp::create(builder&: b, out: b.getI32Type(), in: scaledNumWorkers);
844 Value scaledWorkers =
845 arith::IndexCastOp::create(builder&: b, out: b.getIndexType(), in: scaledNumInt);
846
847 Value maxComputeBlocks = arith::MaxSIOp::create(
848 builder&: b, lhs: arith::ConstantIndexOp::create(builder&: b, value: 1), rhs: scaledWorkers);
849
850 // Compute parallel block size from the parallel problem size:
851 // blockSize = min(tripCount,
852 // max(ceil_div(tripCount, maxComputeBlocks),
853 // minTaskSize))
854 Value bs0 = arith::CeilDivSIOp::create(builder&: b, lhs: tripCount, rhs: maxComputeBlocks);
855 Value bs1 = arith::MaxSIOp::create(builder&: b, lhs: bs0, rhs: minTaskSize);
856 Value blockSize = arith::MinSIOp::create(builder&: b, lhs: tripCount, rhs: bs1);
857
858 // Dispatch parallel compute function using async recursive work splitting,
859 // or by submitting compute task sequentially from a caller thread.
860 auto doDispatch = asyncDispatch ? doAsyncDispatch : doSequentialDispatch;
861
862 // Create a parallel compute function that takes a block id and computes
863 // the parallel operation body for a subset of iteration space.
864
865 // Compute the number of parallel compute blocks.
866 Value blockCount = arith::CeilDivSIOp::create(builder&: b, lhs: tripCount, rhs: blockSize);
867
868 // Dispatch parallel compute function without hints to unroll inner loops.
869 auto dispatchDefault = [&](OpBuilder &nestedBuilder, Location loc) {
870 ParallelComputeFunction compute =
871 createParallelComputeFunction(op, bounds: staticBounds, numBlockAlignedInnerLoops: 0, rewriter);
872
873 ImplicitLocOpBuilder b(loc, nestedBuilder);
874 doDispatch(b, rewriter, compute, op, blockSize, blockCount, tripCounts);
875 scf::YieldOp::create(builder&: b);
876 };
877
878 // Dispatch parallel compute function with hints for unrolling inner loops.
879 auto dispatchBlockAligned = [&](OpBuilder &nestedBuilder, Location loc) {
880 ParallelComputeFunction compute = createParallelComputeFunction(
881 op, bounds: staticBounds, numBlockAlignedInnerLoops: numUnrollableLoops, rewriter);
882
883 ImplicitLocOpBuilder b(loc, nestedBuilder);
884 // Align the block size to be a multiple of the statically known
885 // number of iterations in the inner loops.
886 Value numIters = arith::ConstantIndexOp::create(
887 builder&: b, value: numIterations[op.getNumLoops() - numUnrollableLoops]);
888 Value alignedBlockSize = arith::MulIOp::create(
889 builder&: b, lhs: arith::CeilDivSIOp::create(builder&: b, lhs: blockSize, rhs: numIters), rhs: numIters);
890 doDispatch(b, rewriter, compute, op, alignedBlockSize, blockCount,
891 tripCounts);
892 scf::YieldOp::create(builder&: b);
893 };
894
895 // Dispatch to block aligned compute function only if the computed block
896 // size is larger than the number of iterations in the unrollable inner
897 // loops, because otherwise it can reduce the available parallelism.
898 if (numUnrollableLoops > 0) {
899 Value numIters = arith::ConstantIndexOp::create(
900 builder&: b, value: numIterations[op.getNumLoops() - numUnrollableLoops]);
901 Value useBlockAlignedComputeFn = arith::CmpIOp::create(
902 builder&: b, predicate: arith::CmpIPredicate::sge, lhs: blockSize, rhs: numIters);
903
904 scf::IfOp::create(builder&: b, cond: useBlockAlignedComputeFn, thenBuilder: dispatchBlockAligned,
905 elseBuilder: dispatchDefault);
906 scf::YieldOp::create(builder&: b);
907 } else {
908 dispatchDefault(b, loc);
909 }
910 };
911
912 // Replace the `scf.parallel` operation with the parallel compute function.
913 scf::IfOp::create(builder&: b, cond: isZeroIterations, thenBuilder: noOp, elseBuilder: dispatch);
914
915 // Parallel operation was replaced with a block iteration loop.
916 rewriter.eraseOp(op);
917
918 return success();
919}
920
921void AsyncParallelForPass::runOnOperation() {
922 MLIRContext *ctx = &getContext();
923
924 RewritePatternSet patterns(ctx);
925 populateAsyncParallelForPatterns(
926 patterns, asyncDispatch, numWorkerThreads,
927 computeMinTaskSize: [&](ImplicitLocOpBuilder builder, scf::ParallelOp op) {
928 return arith::ConstantIndexOp::create(builder, value: minTaskSize);
929 });
930 if (failed(Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns))))
931 signalPassFailure();
932}
933
934void mlir::async::populateAsyncParallelForPatterns(
935 RewritePatternSet &patterns, bool asyncDispatch, int32_t numWorkerThreads,
936 const AsyncMinTaskSizeComputationFunction &computeMinTaskSize) {
937 MLIRContext *ctx = patterns.getContext();
938 patterns.add<AsyncParallelForRewrite>(arg&: ctx, args&: asyncDispatch, args&: numWorkerThreads,
939 args: computeMinTaskSize);
940}
941