1//===- SCFToOpenMP.cpp - Structured Control Flow to OpenMP conversion -----===//
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 a pass to convert scf.parallel operations into OpenMP
10// parallel loops.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Conversion/SCFToOpenMP/SCFToOpenMP.h"
15
16#include "mlir/Analysis/SliceAnalysis.h"
17#include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
18#include "mlir/Dialect/Arith/IR/Arith.h"
19#include "mlir/Dialect/LLVMIR/LLVMArithOps.h"
20#include "mlir/Dialect/LLVMIR/LLVMConstantOps.h"
21#include "mlir/Dialect/LLVMIR/LLVMMemoryOps.h"
22#include "mlir/Dialect/MemRef/IR/MemRef.h"
23#include "mlir/Dialect/OpenMP/OpenMPDialect.h"
24#include "mlir/Dialect/SCF/IR/SCF.h"
25#include "mlir/IR/SymbolTable.h"
26#include "mlir/IR/TypeUtilities.h"
27#include "mlir/Pass/Pass.h"
28#include "mlir/Transforms/WalkPatternRewriteDriver.h"
29
30namespace mlir {
31#define GEN_PASS_DEF_CONVERTSCFTOOPENMPPASS
32#include "mlir/Conversion/Passes.h.inc"
33} // namespace mlir
34
35using namespace mlir;
36
37/// Matches a block containing a "simple" reduction. The expected shape of the
38/// block is as follows.
39///
40/// ^bb(%arg0, %arg1):
41/// %0 = OpTy(%arg0, %arg1)
42/// scf.reduce.return %0
43template <typename... OpTy>
44static bool matchSimpleReduction(Block &block) {
45 if (block.empty() || llvm::hasSingleElement(C&: block) ||
46 std::next(x: block.begin(), n: 2) != block.end())
47 return false;
48
49 if (block.getNumArguments() != 2)
50 return false;
51
52 SmallVector<Operation *, 4> combinerOps;
53 Value reducedVal = matchReduction(iterCarriedArgs: {block.getArguments()[1]},
54 /*redPos=*/0, combinerOps);
55
56 if (!reducedVal || !isa<BlockArgument>(Val: reducedVal) || combinerOps.size() != 1)
57 return false;
58
59 return isa<OpTy...>(combinerOps[0]) &&
60 isa<scf::ReduceReturnOp>(Val: block.back()) &&
61 block.front().getOperands() == block.getArguments();
62}
63
64/// Matches a block containing a select-based min/max reduction. The types of
65/// select and compare operations are provided as template arguments. The
66/// comparison predicates suitable for min and max are provided as function
67/// arguments. If a reduction is matched, `ifMin` will be set if the reduction
68/// compute the minimum and unset if it computes the maximum, otherwise it
69/// remains unmodified. The expected shape of the block is as follows.
70///
71/// ^bb(%arg0, %arg1):
72/// %0 = CompareOpTy(<one-of-predicates>, %arg0, %arg1)
73/// %1 = SelectOpTy(%0, %arg0, %arg1) // %arg0, %arg1 may be swapped here.
74/// scf.reduce.return %1
75template <
76 typename CompareOpTy, typename SelectOpTy,
77 typename Predicate = decltype(std::declval<CompareOpTy>().getPredicate())>
78static bool
79matchSelectReduction(Block &block, ArrayRef<Predicate> lessThanPredicates,
80 ArrayRef<Predicate> greaterThanPredicates, bool &isMin) {
81 static_assert(
82 llvm::is_one_of<SelectOpTy, arith::SelectOp, LLVM::SelectOp>::value,
83 "only arithmetic and llvm select ops are supported");
84
85 // Expect exactly three operations in the block.
86 if (block.empty() || llvm::hasSingleElement(C&: block) ||
87 std::next(x: block.begin(), n: 2) == block.end() ||
88 std::next(x: block.begin(), n: 3) != block.end())
89 return false;
90
91 // Check op kinds.
92 auto compare = dyn_cast<CompareOpTy>(block.front());
93 auto select = dyn_cast<SelectOpTy>(block.front().getNextNode());
94 auto terminator = dyn_cast<scf::ReduceReturnOp>(Val&: block.back());
95 if (!compare || !select || !terminator)
96 return false;
97
98 // Block arguments must be compared.
99 if (compare->getOperands() != block.getArguments())
100 return false;
101
102 // Detect whether the comparison is less-than or greater-than, otherwise bail.
103 bool isLess;
104 if (llvm::is_contained(lessThanPredicates, compare.getPredicate())) {
105 isLess = true;
106 } else if (llvm::is_contained(greaterThanPredicates,
107 compare.getPredicate())) {
108 isLess = false;
109 } else {
110 return false;
111 }
112
113 if (select.getCondition() != compare.getResult())
114 return false;
115
116 // Detect if the operands are swapped between cmpf and select. Match the
117 // comparison type with the requested type or with the opposite of the
118 // requested type if the operands are swapped. Use generic accessors because
119 // std and LLVM versions of select have different operand names but identical
120 // positions.
121 constexpr unsigned kTrueValue = 1;
122 constexpr unsigned kFalseValue = 2;
123 bool sameOperands = select.getOperand(kTrueValue) == compare.getLhs() &&
124 select.getOperand(kFalseValue) == compare.getRhs();
125 bool swappedOperands = select.getOperand(kTrueValue) == compare.getRhs() &&
126 select.getOperand(kFalseValue) == compare.getLhs();
127 if (!sameOperands && !swappedOperands)
128 return false;
129
130 if (select.getResult() != terminator.getResult())
131 return false;
132
133 // The reduction is a min if it uses less-than predicates with same operands
134 // or greather-than predicates with swapped operands. Similarly for max.
135 isMin = (isLess && sameOperands) || (!isLess && swappedOperands);
136 return isMin || (isLess & swappedOperands) || (!isLess && sameOperands);
137}
138
139/// Returns the float semantics for the given float type.
140static const llvm::fltSemantics &fltSemanticsForType(FloatType type) {
141 if (type.isF16())
142 return llvm::APFloat::IEEEhalf();
143 if (type.isF32())
144 return llvm::APFloat::IEEEsingle();
145 if (type.isF64())
146 return llvm::APFloat::IEEEdouble();
147 if (type.isF128())
148 return llvm::APFloat::IEEEquad();
149 if (type.isBF16())
150 return llvm::APFloat::BFloat();
151 if (type.isF80())
152 return llvm::APFloat::x87DoubleExtended();
153 llvm_unreachable("unknown float type");
154}
155
156/// Helper to create a splat attribute for vector types, or return the scalar
157/// attribute for scalar types.
158static Attribute getSplatOrScalarAttr(Type type, Attribute val) {
159 if (auto vecType = dyn_cast<VectorType>(Val&: type))
160 return DenseElementsAttr::get(type: vecType, values: val);
161 return val;
162}
163
164/// Returns an attribute with the minimum (if `min` is set) or the maximum value
165/// (otherwise) for the given float type.
166static Attribute minMaxValueForFloat(Type type, bool min) {
167 Type elType = getElementTypeOrSelf(type);
168 auto fltType = cast<FloatType>(Val&: elType);
169 auto val = llvm::APFloat::getLargest(Sem: fltSemanticsForType(type: fltType), Negative: min);
170
171 return getSplatOrScalarAttr(type, val: FloatAttr::get(type: elType, value: val));
172}
173
174/// Returns an attribute with the signed integer minimum (if `min` is set) or
175/// the maximum value (otherwise) for the given integer type, regardless of its
176/// signedness semantics (only the width is considered).
177static Attribute minMaxValueForSignedInt(Type type, bool min) {
178 Type elType = getElementTypeOrSelf(type);
179 auto intType = cast<IntegerType>(Val&: elType);
180 unsigned bitwidth = intType.getWidth();
181 auto val = min ? llvm::APInt::getSignedMinValue(numBits: bitwidth)
182 : llvm::APInt::getSignedMaxValue(numBits: bitwidth);
183
184 return getSplatOrScalarAttr(type, val: IntegerAttr::get(type: elType, value: val));
185}
186
187/// Returns an attribute with the unsigned integer minimum (if `min` is set) or
188/// the maximum value (otherwise) for the given integer type, regardless of its
189/// signedness semantics (only the width is considered).
190static Attribute minMaxValueForUnsignedInt(Type type, bool min) {
191 Type elType = getElementTypeOrSelf(type);
192 auto intType = cast<IntegerType>(Val&: elType);
193 unsigned bitwidth = intType.getWidth();
194 auto val =
195 min ? llvm::APInt::getZero(numBits: bitwidth) : llvm::APInt::getAllOnes(numBits: bitwidth);
196
197 return getSplatOrScalarAttr(type, val: IntegerAttr::get(type: elType, value: val));
198}
199
200/// Creates an OpenMP reduction declaration and inserts it into the provided
201/// symbol table. The declaration has a constant initializer with the neutral
202/// value `initValue`, and the `reductionIndex`-th reduction combiner carried
203/// over from `reduce`.
204static omp::DeclareReductionOp
205createDecl(PatternRewriter &builder, SymbolTable &symbolTable,
206 scf::ReduceOp reduce, int64_t reductionIndex, Attribute initValue) {
207 OpBuilder::InsertionGuard guard(builder);
208 Type type = reduce.getOperands()[reductionIndex].getType();
209 auto decl = omp::DeclareReductionOp::create(builder, location: reduce.getLoc(),
210 sym_name: "__scf_reduction",
211 /*sym_visibility=*/nullptr, type,
212 /*byref_element_type=*/{});
213 symbolTable.insert(symbol: decl);
214
215 builder.createBlock(parent: &decl.getInitializerRegion(),
216 insertPt: decl.getInitializerRegion().end(), argTypes: {type},
217 locs: {reduce.getOperands()[reductionIndex].getLoc()});
218 builder.setInsertionPointToEnd(&decl.getInitializerRegion().back());
219 Value init =
220 LLVM::ConstantOp::create(builder, location: reduce.getLoc(), res: type, value: initValue);
221 omp::YieldOp::create(builder, location: reduce.getLoc(), results: init);
222
223 Operation *terminator =
224 &reduce.getReductions()[reductionIndex].front().back();
225 assert(isa<scf::ReduceReturnOp>(terminator) &&
226 "expected reduce op to be terminated by reduce return");
227 builder.setInsertionPoint(terminator);
228 builder.replaceOpWithNewOp<omp::YieldOp>(op: terminator,
229 args: terminator->getOperands());
230 builder.inlineRegionBefore(region&: reduce.getReductions()[reductionIndex],
231 parent&: decl.getReductionRegion(),
232 before: decl.getReductionRegion().end());
233 return decl;
234}
235
236/// Adds an atomic reduction combiner to the given OpenMP reduction declaration
237/// using llvm.atomicrmw of the given kind.
238static omp::DeclareReductionOp addAtomicRMW(OpBuilder &builder,
239 LLVM::AtomicBinOp atomicKind,
240 omp::DeclareReductionOp decl,
241 scf::ReduceOp reduce,
242 int64_t reductionIndex) {
243 OpBuilder::InsertionGuard guard(builder);
244 auto ptrType = LLVM::LLVMPointerType::get(context: builder.getContext());
245 Location reduceOperandLoc = reduce.getOperands()[reductionIndex].getLoc();
246 builder.createBlock(parent: &decl.getAtomicReductionRegion(),
247 insertPt: decl.getAtomicReductionRegion().end(), argTypes: {ptrType, ptrType},
248 locs: {reduceOperandLoc, reduceOperandLoc});
249 Block *atomicBlock = &decl.getAtomicReductionRegion().back();
250 builder.setInsertionPointToEnd(atomicBlock);
251 Value loaded = LLVM::LoadOp::create(builder, location: reduce.getLoc(), type: decl.getType(),
252 addr: atomicBlock->getArgument(i: 1));
253 LLVM::AtomicRMWOp::create(builder, location: reduce.getLoc(), binOp: atomicKind,
254 ptr: atomicBlock->getArgument(i: 0), val: loaded,
255 ordering: LLVM::AtomicOrdering::monotonic);
256 omp::YieldOp::create(builder, location: reduce.getLoc(), results: ArrayRef<Value>());
257 return decl;
258}
259
260/// Returns true if the type is supported by llvm.atomicrmw.
261/// LLVM IR currently does not support atomic operations on vector types.
262/// See LLVM Language Reference Manual on 'atomicrmw'.
263static bool supportsAtomic(Type type) { return !isa<VectorType>(Val: type); }
264
265/// Creates an OpenMP reduction declaration that corresponds to the given SCF
266/// reduction and returns it. Recognizes common reductions in order to identify
267/// the neutral value, necessary for the OpenMP declaration. If the reduction
268/// cannot be recognized, returns null.
269static omp::DeclareReductionOp declareReduction(PatternRewriter &builder,
270 scf::ReduceOp reduce,
271 int64_t reductionIndex) {
272 Operation *container = SymbolTable::getNearestSymbolTable(from: reduce);
273 SymbolTable symbolTable(container);
274
275 // Insert reduction declarations in the symbol-table ancestor before the
276 // ancestor of the current insertion point.
277 Operation *insertionPoint = reduce;
278 while (insertionPoint->getParentOp() != container)
279 insertionPoint = insertionPoint->getParentOp();
280 OpBuilder::InsertionGuard guard(builder);
281 builder.setInsertionPoint(insertionPoint);
282
283 assert(llvm::hasSingleElement(reduce.getReductions()[reductionIndex]) &&
284 "expected reduction region to have a single element");
285
286 // Match simple binary reductions that can be expressed with atomicrmw.
287 Type type = reduce.getOperands()[reductionIndex].getType();
288 Block &reduction = reduce.getReductions()[reductionIndex].front();
289
290 // Handle scalar element type extraction for vector bitwidth safety.
291 Type elType = getElementTypeOrSelf(type);
292
293 // Arithmetic Reductions
294 if (matchSimpleReduction<arith::AddFOp, LLVM::FAddOp>(block&: reduction)) {
295 omp::DeclareReductionOp decl = createDecl(
296 builder, symbolTable, reduce, reductionIndex,
297 initValue: getSplatOrScalarAttr(type, val: builder.getFloatAttr(type: elType, value: 0.0)));
298 return supportsAtomic(type) ? addAtomicRMW(builder, atomicKind: LLVM::AtomicBinOp::fadd,
299 decl, reduce, reductionIndex)
300 : decl;
301 }
302 if (matchSimpleReduction<arith::AddIOp, LLVM::AddOp>(block&: reduction)) {
303 omp::DeclareReductionOp decl = createDecl(
304 builder, symbolTable, reduce, reductionIndex,
305 initValue: getSplatOrScalarAttr(type, val: builder.getIntegerAttr(type: elType, value: 0)));
306 return supportsAtomic(type) ? addAtomicRMW(builder, atomicKind: LLVM::AtomicBinOp::add,
307 decl, reduce, reductionIndex)
308 : decl;
309 }
310 if (matchSimpleReduction<arith::OrIOp, LLVM::OrOp>(block&: reduction)) {
311 omp::DeclareReductionOp decl = createDecl(
312 builder, symbolTable, reduce, reductionIndex,
313 initValue: getSplatOrScalarAttr(type, val: builder.getIntegerAttr(type: elType, value: 0)));
314 return supportsAtomic(type) ? addAtomicRMW(builder, atomicKind: LLVM::AtomicBinOp::_or,
315 decl, reduce, reductionIndex)
316 : decl;
317 }
318 if (matchSimpleReduction<arith::XOrIOp, LLVM::XOrOp>(block&: reduction)) {
319 omp::DeclareReductionOp decl = createDecl(
320 builder, symbolTable, reduce, reductionIndex,
321 initValue: getSplatOrScalarAttr(type, val: builder.getIntegerAttr(type: elType, value: 0)));
322 return supportsAtomic(type) ? addAtomicRMW(builder, atomicKind: LLVM::AtomicBinOp::_xor,
323 decl, reduce, reductionIndex)
324 : decl;
325 }
326 if (matchSimpleReduction<arith::AndIOp, LLVM::AndOp>(block&: reduction)) {
327 APInt allOnes = llvm::APInt::getAllOnes(numBits: elType.getIntOrFloatBitWidth());
328 omp::DeclareReductionOp decl = createDecl(
329 builder, symbolTable, reduce, reductionIndex,
330 initValue: getSplatOrScalarAttr(type, val: builder.getIntegerAttr(type: elType, value: allOnes)));
331 return supportsAtomic(type) ? addAtomicRMW(builder, atomicKind: LLVM::AtomicBinOp::_and,
332 decl, reduce, reductionIndex)
333 : decl;
334 }
335
336 // Match simple binary reductions that cannot be expressed with atomicrmw.
337 // TODO: add atomic region using cmpxchg (which needs atomic load to be
338 // available as an op).
339 if (matchSimpleReduction<arith::MulFOp, LLVM::FMulOp>(block&: reduction)) {
340 return createDecl(
341 builder, symbolTable, reduce, reductionIndex,
342 initValue: getSplatOrScalarAttr(type, val: builder.getFloatAttr(type: elType, value: 1.0)));
343 }
344
345 if (matchSimpleReduction<arith::MulIOp, LLVM::MulOp>(block&: reduction)) {
346 return createDecl(
347 builder, symbolTable, reduce, reductionIndex,
348 initValue: getSplatOrScalarAttr(type, val: builder.getIntegerAttr(type: elType, value: 1)));
349 }
350
351 // Match select-based min/max reductions.
352 bool isMin;
353 // Floating Point Min/Max
354 if (matchSelectReduction<arith::CmpFOp, arith::SelectOp,
355 arith::CmpFPredicate>(
356 block&: reduction, lessThanPredicates: {arith::CmpFPredicate::OLT, arith::CmpFPredicate::OLE},
357 greaterThanPredicates: {arith::CmpFPredicate::OGT, arith::CmpFPredicate::OGE}, isMin) ||
358 matchSelectReduction<arith::CmpFOp, arith::SelectOp,
359 arith::CmpFPredicate>(
360 block&: reduction, lessThanPredicates: {arith::CmpFPredicate::OGT, arith::CmpFPredicate::OGE},
361 greaterThanPredicates: {arith::CmpFPredicate::OLT, arith::CmpFPredicate::OLE}, isMin)) {
362 return createDecl(builder, symbolTable, reduce, reductionIndex,
363 initValue: minMaxValueForFloat(type, min: !isMin));
364 }
365
366 // Integer Min/Max
367 if (matchSelectReduction<arith::CmpIOp, arith::SelectOp,
368 arith::CmpIPredicate>(
369 block&: reduction, lessThanPredicates: {arith::CmpIPredicate::slt, arith::CmpIPredicate::sle},
370 greaterThanPredicates: {arith::CmpIPredicate::sgt, arith::CmpIPredicate::sge}, isMin) ||
371 matchSelectReduction<arith::CmpIOp, arith::SelectOp,
372 arith::CmpIPredicate>(
373 block&: reduction, lessThanPredicates: {arith::CmpIPredicate::sgt, arith::CmpIPredicate::sge},
374 greaterThanPredicates: {arith::CmpIPredicate::slt, arith::CmpIPredicate::sle}, isMin)) {
375 omp::DeclareReductionOp decl =
376 createDecl(builder, symbolTable, reduce, reductionIndex,
377 initValue: minMaxValueForSignedInt(type, min: !isMin));
378 return supportsAtomic(type) ? addAtomicRMW(builder,
379 atomicKind: isMin ? LLVM::AtomicBinOp::min
380 : LLVM::AtomicBinOp::max,
381 decl, reduce, reductionIndex)
382 : decl;
383 }
384
385 // Unsigned Integer Min/Max
386 if (matchSelectReduction<arith::CmpIOp, arith::SelectOp,
387 arith::CmpIPredicate>(
388 block&: reduction, lessThanPredicates: {arith::CmpIPredicate::ult, arith::CmpIPredicate::ule},
389 greaterThanPredicates: {arith::CmpIPredicate::ugt, arith::CmpIPredicate::uge}, isMin) ||
390 matchSelectReduction<arith::CmpIOp, arith::SelectOp,
391 arith::CmpIPredicate>(
392 block&: reduction, lessThanPredicates: {arith::CmpIPredicate::ugt, arith::CmpIPredicate::uge},
393 greaterThanPredicates: {arith::CmpIPredicate::ult, arith::CmpIPredicate::ule}, isMin)) {
394 omp::DeclareReductionOp decl =
395 createDecl(builder, symbolTable, reduce, reductionIndex,
396 initValue: minMaxValueForUnsignedInt(type, min: !isMin));
397 return supportsAtomic(type) ? addAtomicRMW(builder,
398 atomicKind: isMin ? LLVM::AtomicBinOp::umin
399 : LLVM::AtomicBinOp::umax,
400 decl, reduce, reductionIndex)
401 : decl;
402 }
403
404 return nullptr;
405}
406
407namespace {
408
409struct ParallelOpLowering : public OpRewritePattern<scf::ParallelOp> {
410 static constexpr unsigned kUseOpenMPDefaultNumThreads = 0;
411 unsigned numThreads;
412
413 ParallelOpLowering(MLIRContext *context,
414 unsigned numThreads = kUseOpenMPDefaultNumThreads)
415 : OpRewritePattern<scf::ParallelOp>(context), numThreads(numThreads) {}
416
417 LogicalResult matchAndRewrite(scf::ParallelOp parallelOp,
418 PatternRewriter &rewriter) const override {
419 if (parallelOp.getUnsignedCmp())
420 return rewriter.notifyMatchFailure(
421 arg&: parallelOp, msg: "unsigned loop bounds are not supported");
422 // Bail out early if any reduction init value has a type that is not
423 // compatible with LLVM (e.g. index), since we cannot allocate a reduction
424 // variable for such types.
425 for (Value init : parallelOp.getInitVals()) {
426 if (!LLVM::isCompatibleType(type: init.getType()) &&
427 !isa<LLVM::PointerElementTypeInterface>(Val: init.getType()))
428 return rewriter.notifyMatchFailure(
429 arg&: parallelOp, msg: "reduction init type is not an LLVM-compatible type");
430 }
431
432 // Declare reductions.
433 // TODO: consider checking it here is already a compatible reduction
434 // declaration and use it instead of redeclaring.
435 SmallVector<Attribute> reductionSyms;
436 SmallVector<omp::DeclareReductionOp> ompReductionDecls;
437 auto reduce = cast<scf::ReduceOp>(Val: parallelOp.getBody()->getTerminator());
438 for (int64_t i = 0, e = parallelOp.getNumReductions(); i < e; ++i) {
439 omp::DeclareReductionOp decl = declareReduction(builder&: rewriter, reduce, reductionIndex: i);
440 ompReductionDecls.push_back(Elt: decl);
441 if (!decl)
442 return failure();
443 reductionSyms.push_back(
444 Elt: SymbolRefAttr::get(ctx: rewriter.getContext(), value: decl.getSymName()));
445 }
446
447 // Allocate reduction variables. Make sure the we don't overflow the stack
448 // with local `alloca`s by saving and restoring the stack pointer.
449 Location loc = parallelOp.getLoc();
450 Value one =
451 LLVM::ConstantOp::create(builder&: rewriter, location: loc, res: rewriter.getIntegerType(width: 64),
452 value: rewriter.getI64IntegerAttr(value: 1));
453 SmallVector<Value> reductionVariables;
454 reductionVariables.reserve(N: parallelOp.getNumReductions());
455 auto ptrType = LLVM::LLVMPointerType::get(context: parallelOp.getContext());
456 for (Value init : parallelOp.getInitVals()) {
457 Value storage = LLVM::AllocaOp::create(builder&: rewriter, location: loc, resultType: ptrType,
458 elementType: init.getType(), arraySize: one, alignment: 0);
459 LLVM::StoreOp::create(builder&: rewriter, location: loc, value: init, addr: storage);
460 reductionVariables.push_back(Elt: storage);
461 }
462
463 // Replace the reduction operations contained in this loop. Must be done
464 // here rather than in a separate pattern to have access to the list of
465 // reduction variables.
466 for (auto [x, y, rD] : llvm::zip_equal(
467 t&: reductionVariables, u: reduce.getOperands(), args&: ompReductionDecls)) {
468 OpBuilder::InsertionGuard guard(rewriter);
469 rewriter.setInsertionPoint(reduce);
470 Region &redRegion = rD.getReductionRegion();
471 // The SCF dialect by definition contains only structured operations
472 // and hence the SCF reduction region will contain a single block.
473 // The ompReductionDecls region is a copy of the SCF reduction region
474 // and hence has the same property.
475 assert(redRegion.hasOneBlock() &&
476 "expect reduction region to have one block");
477 Value pvtRedVar = parallelOp.getRegion().addArgument(type: x.getType(), loc);
478 Value pvtRedVal = LLVM::LoadOp::create(builder&: rewriter, location: reduce.getLoc(),
479 type: rD.getType(), addr: pvtRedVar);
480 // Make a copy of the reduction combiner region in the body
481 mlir::OpBuilder builder(rewriter.getContext());
482 builder.setInsertionPoint(reduce);
483 mlir::IRMapping mapper;
484 assert(redRegion.getNumArguments() == 2 &&
485 "expect reduction region to have two arguments");
486 mapper.map(from: redRegion.getArgument(i: 0), to: pvtRedVal);
487 mapper.map(from: redRegion.getArgument(i: 1), to: y);
488 for (auto &op : redRegion.getOps()) {
489 Operation *cloneOp = builder.clone(op, mapper);
490 if (auto yieldOp = dyn_cast<omp::YieldOp>(Val&: *cloneOp)) {
491 assert(yieldOp && yieldOp.getResults().size() == 1 &&
492 "expect YieldOp in reduction region to return one result");
493 Value redVal = yieldOp.getResults()[0];
494 LLVM::StoreOp::create(builder&: rewriter, location: loc, value: redVal, addr: pvtRedVar);
495 rewriter.eraseOp(op: yieldOp);
496 break;
497 }
498 }
499 }
500 rewriter.eraseOp(op: reduce);
501
502 SmallVector<Value> numThreadsVars;
503 if (numThreads > 0) {
504 Value numThreadsVar = LLVM::ConstantOp::create(
505 builder&: rewriter, location: loc, value: rewriter.getI32IntegerAttr(value: numThreads));
506 numThreadsVars.push_back(Elt: numThreadsVar);
507 }
508 // Create the parallel wrapper.
509 auto ompParallel = omp::ParallelOp::create(
510 builder&: rewriter, location: loc,
511 /* allocate_vars = */ llvm::SmallVector<Value>{},
512 /* allocator_vars = */ llvm::SmallVector<Value>{},
513 /* allocate_alignments = */ nullptr,
514 /* allocate_private_indices = */ nullptr,
515 /* if_expr = */ Value{},
516 /* num_threads_vars = */ numThreadsVars,
517 /* private_vars = */ ValueRange(),
518 /* private_syms = */ nullptr,
519 /* private_needs_barrier = */ false,
520 /* proc_bind_kind = */ omp::ClauseProcBindKindAttr{},
521 /* reduction_mods = */ nullptr,
522 /* reduction_vars = */ llvm::SmallVector<Value>{},
523 /* reduction_byref = */ DenseBoolArrayAttr{},
524 /* reduction_syms = */ ArrayAttr{});
525 {
526
527 OpBuilder::InsertionGuard guard(rewriter);
528 rewriter.createBlock(parent: &ompParallel.getRegion());
529
530 // Replace the loop.
531 {
532 OpBuilder::InsertionGuard allocaGuard(rewriter);
533 // Create worksharing loop wrapper.
534 auto wsloopOp = omp::WsloopOp::create(builder&: rewriter, location: parallelOp.getLoc());
535 if (!reductionVariables.empty()) {
536 wsloopOp.setReductionSymsAttr(
537 ArrayAttr::get(context: rewriter.getContext(), value: reductionSyms));
538 wsloopOp.getReductionVarsMutable().append(values: reductionVariables);
539 llvm::SmallVector<bool> reductionByRef;
540 // false because these reductions always reduce scalars and so do
541 // not need to pass by reference
542 reductionByRef.resize(N: reductionVariables.size(), NV: false);
543 wsloopOp.setReductionByref(
544 DenseBoolArrayAttr::get(context: rewriter.getContext(), content: reductionByRef));
545 }
546 omp::TerminatorOp::create(builder&: rewriter, location: loc); // omp.parallel terminator.
547
548 // The wrapper's entry block arguments will define the reduction
549 // variables.
550 llvm::SmallVector<mlir::Type> reductionTypes;
551 reductionTypes.reserve(N: reductionVariables.size());
552 llvm::transform(Range&: reductionVariables, d_first: std::back_inserter(x&: reductionTypes),
553 F: [](mlir::Value v) { return v.getType(); });
554 rewriter.createBlock(
555 parent: &wsloopOp.getRegion(), insertPt: {}, argTypes: reductionTypes,
556 locs: llvm::SmallVector<mlir::Location>(reductionVariables.size(),
557 parallelOp.getLoc()));
558
559 // Create loop nest and populate region with contents of scf.parallel.
560 auto loopOp = omp::LoopNestOp::create(
561 builder&: rewriter, location: parallelOp.getLoc(), collapse_num_loops: parallelOp.getLowerBound().size(),
562 loop_lower_bounds: parallelOp.getLowerBound(), loop_upper_bounds: parallelOp.getUpperBound(),
563 loop_steps: parallelOp.getStep(), /*loop_inclusive=*/false,
564 /*tile_sizes=*/nullptr);
565
566 rewriter.inlineRegionBefore(region&: parallelOp.getRegion(), parent&: loopOp.getRegion(),
567 before: loopOp.getRegion().begin());
568
569 // Remove reduction-related block arguments from omp.loop_nest and
570 // redirect uses to the corresponding omp.wsloop block argument.
571 mlir::Block &loopOpEntryBlock = loopOp.getRegion().front();
572 unsigned numLoops = parallelOp.getNumLoops();
573 rewriter.replaceAllUsesWith(
574 from: loopOpEntryBlock.getArguments().drop_front(N: numLoops),
575 to: wsloopOp.getRegion().getArguments());
576 loopOpEntryBlock.eraseArguments(
577 start: numLoops, num: loopOpEntryBlock.getNumArguments() - numLoops);
578
579 Block *ops =
580 rewriter.splitBlock(block: &loopOpEntryBlock, before: loopOpEntryBlock.begin());
581 rewriter.setInsertionPointToStart(&loopOpEntryBlock);
582
583 auto scope = memref::AllocaScopeOp::create(
584 builder&: rewriter, location: parallelOp.getLoc(), results: TypeRange());
585 omp::YieldOp::create(builder&: rewriter, location: loc, results: ValueRange());
586 Block *scopeBlock = rewriter.createBlock(parent: &scope.getBodyRegion());
587 rewriter.mergeBlocks(source: ops, dest: scopeBlock);
588 rewriter.setInsertionPointToEnd(&*scope.getBodyRegion().begin());
589 memref::AllocaScopeReturnOp::create(builder&: rewriter, location: loc, results: ValueRange());
590 }
591 }
592
593 // Load loop results.
594 SmallVector<Value> results;
595 results.reserve(N: reductionVariables.size());
596 for (auto [variable, type] :
597 llvm::zip(t&: reductionVariables, u: parallelOp.getResultTypes())) {
598 Value res = LLVM::LoadOp::create(builder&: rewriter, location: loc, type, addr: variable);
599 results.push_back(Elt: res);
600 }
601 rewriter.replaceOp(op: parallelOp, newValues: results);
602
603 return success();
604 }
605};
606
607/// Applies the conversion patterns in the given function.
608static LogicalResult applyPatterns(ModuleOp module, unsigned numThreads) {
609 RewritePatternSet patterns(module.getContext());
610 patterns.add<ParallelOpLowering>(arg: module.getContext(), args&: numThreads);
611 FrozenRewritePatternSet frozen(std::move(patterns));
612 walkAndApplyPatterns(op: module, patterns: frozen);
613 auto status = module.walk(callback: [](Operation *op) {
614 if (isa<scf::ReduceOp, scf::ReduceReturnOp, scf::ParallelOp>(Val: op)) {
615 op->emitError(message: "unconverted operation found");
616 return WalkResult::interrupt();
617 }
618 return WalkResult::advance();
619 });
620 return failure(IsFailure: status.wasInterrupted());
621}
622
623/// A pass converting SCF operations to OpenMP operations.
624struct SCFToOpenMPPass
625 : public impl::ConvertSCFToOpenMPPassBase<SCFToOpenMPPass> {
626
627 using Base::Base;
628
629 /// Pass entry point.
630 void runOnOperation() override {
631 if (failed(Result: applyPatterns(module: getOperation(), numThreads)))
632 signalPassFailure();
633 }
634};
635
636} // namespace
637