1//===- ACCAtomicPatterns.cpp - ACC atomic to LLVM patterns ------*- C++ -*-===//
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// Lowers OpenACC atomic operations (read, write, update, capture) to LLVM
10// dialect atomicrmw / cmpxchg sequences.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Conversion/OpenACCToLLVM/ACCToLLVM.h"
15
16#include "mlir/Conversion/LLVMCommon/Pattern.h"
17#include "mlir/Dialect/Arith/IR/Arith.h"
18#include "mlir/Dialect/Complex/IR/Complex.h"
19#include "mlir/Dialect/LLVMIR/LLVMAggregateOps.h"
20#include "mlir/Dialect/LLVMIR/LLVMArithOps.h"
21#include "mlir/Dialect/LLVMIR/LLVMConstantOps.h"
22#include "mlir/Dialect/LLVMIR/LLVMConversionOps.h"
23#include "mlir/Dialect/LLVMIR/LLVMMemoryOps.h"
24#include "mlir/Dialect/LLVMIR/LLVMTerminatorOps.h"
25#include "mlir/Dialect/MemRef/IR/MemRef.h"
26#include "mlir/Dialect/OpenACC/Analysis/OpenACCSupport.h"
27#include "mlir/Dialect/OpenACC/OpenACC.h"
28#include "mlir/Dialect/OpenACC/OpenACCUtilsType.h"
29#include "mlir/IR/BuiltinOps.h"
30#include "mlir/Interfaces/SideEffectInterfaces.h"
31#include "llvm/ADT/TypeSwitch.h"
32#include "llvm/Support/Debug.h"
33
34#include <cstdint>
35#include <optional>
36#include <set>
37#include <utility>
38
39#define DEBUG_TYPE "acc-atomic-patterns"
40
41using namespace mlir;
42using namespace mlir::acc;
43
44namespace {
45
46constexpr uint64_t kBitsInByte = 8;
47
48template <typename AtomicOpTy>
49class ACCAtomicOpConversion : public ConvertOpToLLVMPattern<AtomicOpTy> {
50 using typename ConvertOpToLLVMPattern<AtomicOpTy>::OpAdaptor;
51
52public:
53 ACCAtomicOpConversion(const LLVMTypeConverter &typeConverter,
54 OpenACCSupport &accSupport,
55 const ACCAtomicLoadAddressCallback &getLoadAddress)
56 : ConvertOpToLLVMPattern<AtomicOpTy>(typeConverter),
57 accSupport(accSupport), getLoadAddress(getLoadAddress) {}
58
59 LogicalResult
60 matchAndRewrite(AtomicOpTy op, OpAdaptor adaptor,
61 ConversionPatternRewriter &rewriter) const override;
62
63private:
64 OpenACCSupport &accSupport;
65 ACCAtomicLoadAddressCallback getLoadAddress;
66
67 size_t getComplexStructElementSizeInBits(Type ty) const {
68 auto structType = dyn_cast<LLVM::LLVMStructType>(Val&: ty);
69 if (!structType || structType.getBody().size() != 2 ||
70 structType.getBody()[0] != structType.getBody()[1] ||
71 !structType.getBody()[0].isIntOrFloat())
72 return 0;
73 size_t elementSizeInBits = structType.getBody()[0].getIntOrFloatBitWidth();
74 if (elementSizeInBits == 0 || elementSizeInBits > 64)
75 llvm_unreachable("unexpected complex type");
76 return elementSizeInBits;
77 }
78
79 /// Serialize a complex value into an integer.
80 Value serializeExpr(Value expr, ConversionPatternRewriter &rewriter) const {
81 size_t elementSizeInBits =
82 getComplexStructElementSizeInBits(ty: expr.getType());
83 if (!elementSizeInBits)
84 return expr;
85
86 Location loc = expr.getLoc();
87 Value firstValue = LLVM::ExtractValueOp::create(builder&: rewriter, location: loc, container: expr, position: 0);
88 Value secondValue = LLVM::ExtractValueOp::create(builder&: rewriter, location: loc, container: expr, position: 1);
89 MLIRContext *context = rewriter.getContext();
90 Type intCastTy = IntegerType::get(context, width: elementSizeInBits);
91 Type intTy = IntegerType::get(context, width: elementSizeInBits * 2);
92 firstValue = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: intCastTy, arg: firstValue);
93 secondValue =
94 LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: intCastTy, arg: secondValue);
95 firstValue = LLVM::ZExtOp::create(builder&: rewriter, location: loc, res: intTy, arg: firstValue);
96 secondValue = LLVM::ZExtOp::create(builder&: rewriter, location: loc, res: intTy, arg: secondValue);
97 Value shlVal =
98 LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: intTy, value: elementSizeInBits);
99 Value result = LLVM::ShlOp::create(builder&: rewriter, location: loc, lhs: secondValue, rhs: shlVal);
100 return LLVM::OrOp::create(builder&: rewriter, location: loc, lhs: result, rhs: firstValue);
101 }
102
103 /// Deserialize an integer into a complex value.
104 Value deserializeExpr(Value expr, Type origTy,
105 ConversionPatternRewriter &rewriter) const {
106 size_t elementSizeInBits = getComplexStructElementSizeInBits(ty: origTy);
107 if (!elementSizeInBits)
108 return expr;
109
110 auto intTy = dyn_cast<IntegerType>(Val: expr.getType());
111 if (!intTy || intTy.getWidth() != elementSizeInBits * 2)
112 return expr;
113
114 Location loc = expr.getLoc();
115 MLIRContext *context = rewriter.getContext();
116 Type elemTy = IntegerType::get(context, width: elementSizeInBits);
117 Value low = LLVM::TruncOp::create(builder&: rewriter, location: loc, res: elemTy, arg: expr);
118 Value shiftAmount =
119 LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: intTy, value: elementSizeInBits);
120 Value highFull = LLVM::LShrOp::create(builder&: rewriter, location: loc, lhs: expr, rhs: shiftAmount);
121 Value high = LLVM::TruncOp::create(builder&: rewriter, location: loc, res: elemTy, arg: highFull);
122 Type origElemTy = cast<LLVM::LLVMStructType>(Val&: origTy).getBody()[0];
123 if (origElemTy != elemTy) {
124 low = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: origElemTy, arg: low);
125 high = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: origElemTy, arg: high);
126 }
127 Value undefStruct = LLVM::UndefOp::create(builder&: rewriter, location: loc, res: origTy);
128 Value structWithLow = LLVM::InsertValueOp::create(
129 builder&: rewriter, location: loc, res: origTy, container: undefStruct, value: low, position: ArrayRef<int64_t>{0});
130 return LLVM::InsertValueOp::create(builder&: rewriter, location: loc, res: origTy, container: structWithLow,
131 value: high, position: ArrayRef<int64_t>{1});
132 }
133
134 uint64_t getAtomicSizeInBytes(Type originalTy, Type convertedTy,
135 ModuleOp module) const {
136 std::optional<TypeSizeAndAlignment> sizeAndAlignment =
137 acc::getTypeSizeAndAlignment(ty: originalTy, module, support: &accSupport);
138 if (!sizeAndAlignment)
139 sizeAndAlignment =
140 acc::getTypeSizeAndAlignment(ty: convertedTy, module, support: &accSupport);
141 assert(sizeAndAlignment && "atomic type size is not computable");
142 return sizeAndAlignment->first.getFixedValue();
143 }
144
145 Type getAtomicType(Type originalTy, Type convertedTy, ModuleOp module) const {
146 if (convertedTy.isIntOrFloat())
147 return convertedTy;
148 return IntegerType::get(
149 context: convertedTy.getContext(),
150 width: getAtomicSizeInBytes(originalTy, convertedTy, module) * kBitsInByte);
151 }
152
153 Type getReferencedElementType(Value ref, ModuleOp module = nullptr) const {
154 auto ptr = dyn_cast<PointerLikeType>(Val: ref.getType());
155 if (!ptr)
156 llvm_unreachable("unexpected type");
157 Type elementTy = ptr.getElementType();
158 Type convertedTy = this->getTypeConverter()->convertType(elementTy);
159 if (module)
160 return getAtomicType(originalTy: elementTy, convertedTy, module);
161 return convertedTy;
162 }
163
164 /// Memrefs are converted to descriptors rather than bare pointers, so the
165 /// element pointer must be recomputed from the descriptor.
166 Value getAtomicPointer(Value originalRef, Value convertedPtr, Location loc,
167 ConversionPatternRewriter &rewriter) const {
168 auto memrefTy = dyn_cast<MemRefType>(Val: originalRef.getType());
169 if (!memrefTy)
170 return convertedPtr;
171
172 // Extract aligned base pointer (index 1) and offset (index 2).
173 Value alignedPtr =
174 LLVM::ExtractValueOp::create(builder&: rewriter, location: loc, container: convertedPtr, position: 1);
175 Value offset = LLVM::ExtractValueOp::create(builder&: rewriter, location: loc, container: convertedPtr, position: 2);
176 Type elemPtrType = LLVM::LLVMPointerType::get(context: rewriter.getContext());
177 return LLVM::GEPOp::create(
178 rewriter, loc, elemPtrType,
179 this->getTypeConverter()->convertType(memrefTy.getElementType()),
180 alignedPtr, offset);
181 }
182
183 Block *constructCmpxchgLoop(Value ptr, Type type, Value expr,
184 ConversionPatternRewriter &rewriter) const;
185
186 /// Emit a single atomicrmw for a `x = x <binop> expr` capture, or fail so
187 /// the caller falls back to the cmpxchg loop.
188 LogicalResult
189 tryEmitCaptureAtomicRMW(AtomicCaptureOp capture, AtomicUpdateOp update,
190 AtomicReadOp read,
191 ConversionPatternRewriter &rewriter) const;
192
193 Value genUpdateCmpxchgLoop(AtomicUpdateOp update,
194 ConversionPatternRewriter &rewriter) const;
195};
196
197template <>
198LogicalResult ACCAtomicOpConversion<AtomicReadOp>::matchAndRewrite(
199 AtomicReadOp read, OpAdaptor adaptor,
200 ConversionPatternRewriter &rewriter) const {
201 Location loc = read.getLoc();
202 Value xRef = read.getX();
203 Value xPtr = getAtomicPointer(originalRef: xRef, convertedPtr: adaptor.getX(), loc, rewriter);
204 ModuleOp mod = read->getParentOfType<ModuleOp>();
205 Type xType = getReferencedElementType(ref: xRef, module: mod);
206
207 auto ordering = LLVM::AtomicOrdering::monotonic;
208 Value storeVal;
209 if (xType.isSignlessInteger()) {
210 Value zero = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: xType, value: 0);
211 storeVal = LLVM::AtomicRMWOp::create(builder&: rewriter, location: loc, binOp: LLVM::AtomicBinOp::_or,
212 ptr: xPtr, val: zero, ordering);
213 } else {
214 unsigned bitWidth = xType.getIntOrFloatBitWidth();
215 Type intType = IntegerType::get(context: rewriter.getContext(), width: bitWidth);
216 Value zero = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: intType, value: 0);
217 Value intVal = LLVM::AtomicRMWOp::create(
218 builder&: rewriter, location: loc, binOp: LLVM::AtomicBinOp::_or, ptr: xPtr, val: zero, ordering);
219 storeVal = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: xType, arg: intVal);
220 }
221
222 Value vRef = read.getV();
223 Value vPtr = getAtomicPointer(originalRef: vRef, convertedPtr: adaptor.getV(), loc, rewriter);
224 Type vType = getReferencedElementType(ref: vRef, module: mod);
225
226 if (xType != vType) {
227 // Convert `x` if the types do not match.
228 auto vPtrType = cast<PointerLikeType>(Val: vRef.getType());
229 storeVal = vPtrType.genCast(builder&: rewriter, loc, value: storeVal, resultType: vType);
230 if (!storeVal) {
231 return rewriter.notifyMatchFailure(
232 arg&: read, msg: "failed to convert the loaded value to the destination type");
233 }
234 }
235 auto storeOp = LLVM::StoreOp::create(builder&: rewriter, location: loc, value: storeVal, addr: vPtr);
236 rewriter.replaceOp(op: read, newOp: storeOp);
237 return success();
238}
239
240template <>
241LogicalResult ACCAtomicOpConversion<AtomicWriteOp>::matchAndRewrite(
242 AtomicWriteOp write, OpAdaptor adaptor,
243 ConversionPatternRewriter &rewriter) const {
244 Location loc = write.getLoc();
245 Value expr = serializeExpr(expr: adaptor.getExpr(), rewriter);
246 Value xRef = write.getX();
247 Value xPtr = getAtomicPointer(originalRef: xRef, convertedPtr: adaptor.getX(), loc, rewriter);
248 ModuleOp mod = write->getParentOfType<ModuleOp>();
249 Type xType = getReferencedElementType(ref: xRef, module: mod);
250
251 auto ordering = LLVM::AtomicOrdering::monotonic;
252 if (!xType.isSignlessInteger()) {
253 unsigned bitWidth = xType.getIntOrFloatBitWidth();
254 Type intType = IntegerType::get(context: rewriter.getContext(), width: bitWidth);
255 expr = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: intType, arg: expr);
256 }
257 LLVM::AtomicRMWOp::create(builder&: rewriter, location: loc, binOp: LLVM::AtomicBinOp::xchg, ptr: xPtr, val: expr,
258 ordering);
259 rewriter.eraseOp(op: write);
260 return success();
261}
262
263// Generate a cmpxchg loop based on the GenericAtomicRMWOpLowering algorithm.
264template <typename AtomicOpTy>
265Block *ACCAtomicOpConversion<AtomicOpTy>::constructCmpxchgLoop(
266 Value ptr, Type type, Value expr,
267 ConversionPatternRewriter &rewriter) const {
268 // Split the block into initial, loop, and ending parts.
269 Location loc = rewriter.getInsertionPoint()->getLoc();
270 Block *initBlock = rewriter.getInsertionBlock();
271 Block *loopBlock =
272 rewriter.splitBlock(block: initBlock, before: rewriter.getInsertionPoint());
273 loopBlock->addArgument(type, loc);
274 Block *endBlock =
275 rewriter.splitBlock(block: loopBlock, before: rewriter.getInsertionPoint());
276
277 // Compute the loaded value and branch to the loop block.
278 rewriter.setInsertionPointToEnd(initBlock);
279 Value init = LLVM::LoadOp::create(builder&: rewriter, location: loc, type, addr: ptr);
280 LLVM::BrOp::create(builder&: rewriter, location: loc, operands: init, dest: loopBlock);
281
282 // Prepare the body of the loop block.
283 rewriter.setInsertionPointToStart(loopBlock);
284
285 Value loopArgument = loopBlock->getArgument(i: 0);
286 Value result = serializeExpr(expr: rewriter.getRemappedValue(key: expr), rewriter);
287 ModuleOp mod = initBlock->getParent()->getParentOfType<ModuleOp>();
288 Type convertedExprType =
289 this->getTypeConverter()->convertType(expr.getType());
290 Type exprType = getAtomicType(originalTy: expr.getType(), convertedTy: convertedExprType, module: mod);
291
292 // Cast to an integer type.
293 if (!exprType.isSignlessInteger()) {
294 Type tmpType = IntegerType::get(
295 context: rewriter.getContext(),
296 width: getAtomicSizeInBytes(originalTy: expr.getType(), convertedTy: convertedExprType, module: mod) *
297 kBitsInByte);
298 result = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: tmpType, arg: result);
299 loopArgument =
300 LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: tmpType, arg: loopArgument);
301 }
302
303 // Prepare the epilog of the loop block.
304 // Append the cmpxchg op to the end of the loop block.
305 auto successOrdering = LLVM::AtomicOrdering::acq_rel;
306 auto failureOrdering = LLVM::AtomicOrdering::monotonic;
307 auto cmpxchg =
308 LLVM::AtomicCmpXchgOp::create(builder&: rewriter, location: loc, ptr, cmp: loopArgument, val: result,
309 successOrdering, failureOrdering);
310 // Extract the %new_loaded and %ok values from the pair.
311 Value newLoaded = LLVM::ExtractValueOp::create(builder&: rewriter, location: loc, container: cmpxchg, position: 0);
312 Value ok = LLVM::ExtractValueOp::create(builder&: rewriter, location: loc, container: cmpxchg, position: 1);
313
314 // Cast back to the original type.
315 if (!exprType.isSignlessInteger())
316 newLoaded = LLVM::BitcastOp::create(builder&: rewriter, location: loc, res: exprType, arg: newLoaded);
317
318 // Conditionally branch to the end or back to the loop depending on %ok.
319 LLVM::CondBrOp::create(builder&: rewriter, location: loc, condition: ok, trueDest: endBlock, trueOperands: ArrayRef<Value>(),
320 falseDest: loopBlock, falseOperands: newLoaded);
321
322 return loopBlock;
323}
324
325static Value skipUnrealizedConversionOp(Value v) {
326 if (auto convOp =
327 dyn_cast_or_null<UnrealizedConversionCastOp>(Val: v.getDefiningOp()))
328 return skipUnrealizedConversionOp(v: convOp.getOperand(i: 0));
329 return v;
330}
331
332/// Obtain the foremost value of addr to indicate the origin of the storage.
333static Value getBaseStorage(Value addr, ConversionPatternRewriter &rewriter) {
334 Operation *op = skipUnrealizedConversionOp(v: addr).getDefiningOp();
335 if (auto gepOp = dyn_cast_or_null<LLVM::GEPOp>(Val: op)) {
336 addr = gepOp.getBase();
337 op = addr.getDefiningOp();
338 }
339 if (auto extractOp = dyn_cast_or_null<LLVM::ExtractValueOp>(Val: op)) {
340 // addr is in a struct. Get the inserted value corresponding to the
341 // extraction.
342 ArrayRef extractingPosition = extractOp.getPosition();
343 Value container = skipUnrealizedConversionOp(v: extractOp.getContainer());
344 Value remappedContainer = rewriter.getRemappedValue(key: container);
345 op = remappedContainer ? remappedContainer.getDefiningOp() : nullptr;
346 bool inserted = false;
347 while (auto insertValueOp = dyn_cast_or_null<LLVM::InsertValueOp>(Val: op)) {
348 ArrayRef insertingPosition = insertValueOp.getPosition();
349 if (insertingPosition == extractingPosition) {
350 addr = insertValueOp.getValue();
351 inserted = true;
352 break;
353 }
354 op = insertValueOp.getContainer().getDefiningOp();
355 }
356 // The aggregate holding addr is not built by insertions, so the value it
357 // is converted from identifies the storage.
358 if (!inserted)
359 addr = container;
360 }
361 // op might be alloca already, or addr might be an argument.
362 return skipUnrealizedConversionOp(v: addr);
363}
364
365/// Include flow dependency (v -> expr) in the generated loop of
366/// `{ atomic.read, atomic.write/update }`.
367static void moveDependency(Value vRef, Value vPtr, Value expr,
368 Value loopArgument, Operation &loopHead,
369 ConversionPatternRewriter &rewriter,
370 const ACCAtomicLoadAddressCallback &getLoadAddress) {
371 Value vStorage = getBaseStorage(addr: vPtr, rewriter);
372 // A dependency may be reached before it is itself converted, in which case
373 // its address is still expressed in terms of `vRef`.
374 Value vStorageRef = skipUnrealizedConversionOp(v: vRef);
375 LLVM_DEBUG({
376 llvm::dbgs() << "[acc-atomic] moveDependency\n";
377 llvm::dbgs() << " vPtr = " << vPtr << "\n";
378 llvm::dbgs() << " vStorage = " << vStorage << "\n";
379 llvm::dbgs() << " vStorageRef = " << vStorageRef << "\n";
380 llvm::dbgs() << " expr = " << expr << "\n";
381 });
382 llvm::DenseMap<Value, Value> remappedToOriginal;
383 std::set<std::pair<Operation *, std::set<Operation *>>> worklist;
384 std::set<Operation *> included;
385 Value mappedExpr = rewriter.getRemappedValue(key: expr);
386 remappedToOriginal[mappedExpr] = expr;
387 if (Operation *exprDef = mappedExpr.getDefiningOp())
388 worklist.insert(x: std::pair{exprDef, std::set<Operation *>{}});
389
390 while (!worklist.empty()) {
391 auto [dep, post] = worklist.extract(pos: worklist.begin()).value();
392 if (!dep)
393 continue;
394 LLVM_DEBUG(llvm::dbgs() << " visit dep = " << *dep << "\n");
395 if (vPtr.getDefiningOp() &&
396 !vPtr.getDefiningOp()->getParentOp()->isAncestor(other: dep)) {
397 // Outside the parental region. No load found in this flow.
398 LLVM_DEBUG(llvm::dbgs() << " -> skipped: not in parental region\n");
399 continue;
400 }
401
402 Value addr;
403 if (auto load = dyn_cast<LLVM::LoadOp>(Val: dep)) {
404 addr = load.getAddr();
405 } else if (auto load = dyn_cast<memref::LoadOp>(Val: dep)) {
406 addr = load.getMemref();
407 } else if (getLoadAddress) {
408 addr = getLoadAddress(dep);
409 }
410 if (addr) {
411 Value baseStorage = getBaseStorage(addr, rewriter);
412 LLVM_DEBUG({
413 llvm::dbgs() << " addr = " << addr << "\n";
414 llvm::dbgs() << " baseStorage = " << baseStorage << "\n";
415 llvm::dbgs() << " remapped = "
416 << rewriter.getRemappedValue(baseStorage) << "\n";
417 llvm::dbgs() << " matchRef=" << (baseStorage == vStorageRef)
418 << " matchConv="
419 << (rewriter.getRemappedValue(baseStorage) == vStorage)
420 << "\n";
421 });
422 if (baseStorage == vStorageRef ||
423 rewriter.getRemappedValue(key: baseStorage) == vStorage) {
424 // Found the load of `v`. Include this flow in dependency.
425 Value load = dep->getResult(idx: 0);
426 auto replaceUses = [&](Operation *op) {
427 rewriter.modifyOpInPlace(root: op, callable: [&] {
428 op->replaceUsesOfWith(from: remappedToOriginal[load], to: loopArgument);
429 });
430 };
431 for (Operation *p : post)
432 replaceUses(p);
433 replaceUses(&loopHead);
434 included.insert(first: post.begin(), last: post.end());
435 }
436 continue;
437 }
438 post.insert(x: dep);
439 for (Value operand : dep->getOperands()) {
440 Value mappedOperand = rewriter.getRemappedValue(key: operand);
441 if (auto *d = mappedOperand.getDefiningOp()) {
442 if (dep == d) {
443 if (auto *op = operand.getDefiningOp()) {
444 remappedToOriginal[op->getResult(idx: 0)] = operand;
445 worklist.insert(x: std::pair{op, post});
446 }
447 } else {
448 remappedToOriginal[mappedOperand] = operand;
449 worklist.insert(x: std::pair{d, post});
450 }
451 }
452 }
453 }
454
455 // Include dependency.
456 SmallVector<Operation *> includedInOrder;
457 vPtr.getParentRegion()->walk(callback: [&](Operation *op) {
458 if (included.find(x: op) != included.end())
459 includedInOrder.push_back(Elt: op);
460 });
461 for (Operation *d : includedInOrder)
462 d->moveBefore(existingOp: &loopHead);
463}
464
465/// Generate a cmpxchg loop for update and return a stored value.
466template <typename AtomicOpTy>
467Value ACCAtomicOpConversion<AtomicOpTy>::genUpdateCmpxchgLoop(
468 AtomicUpdateOp update, ConversionPatternRewriter &rewriter) const {
469 Location loc = update.getLoc();
470 Value xRef = update.getX();
471 Value xPtr =
472 getAtomicPointer(originalRef: xRef, convertedPtr: rewriter.getRemappedValue(key: xRef), loc, rewriter);
473 ModuleOp mod = update->getParentOfType<ModuleOp>();
474 Type xType = getReferencedElementType(ref: xRef, module: mod);
475 Type xTypeOrig = getReferencedElementType(ref: xRef);
476
477 Block &updateBlock = update.getRegion().front();
478 Value updateArgument = updateBlock.getArgument(i: 0);
479 Operation *terminator = updateBlock.getTerminator();
480 Value expr = terminator->getOperand(idx: 0);
481
482 Block *loopBlock = constructCmpxchgLoop(ptr: xPtr, type: xType, expr, rewriter);
483 Value loopArgument = loopBlock->getArgument(i: 0);
484 Operation &loopHead = loopBlock->front();
485
486 rewriter.setInsertionPointToStart(loopBlock);
487 loopArgument = deserializeExpr(expr: loopArgument, origTy: xTypeOrig, rewriter);
488
489 // Move in and out flow dependency (x -> expr). Some computation might be
490 // outside atomic regions.
491 moveDependency(vRef: xRef, vPtr: xPtr, expr, loopArgument, loopHead, rewriter,
492 getLoadAddress);
493 // Move out the residue.
494 rewriter.replaceAllUsesWith(from: cast<BlockArgument>(Val&: updateArgument),
495 to: {loopArgument});
496
497 updateBlock.walk([&](Operation *op) {
498 if (!op->hasTrait<OpTrait::IsTerminator>())
499 rewriter.moveOpBefore(op, existingOp: &loopHead);
500 });
501
502 if (auto cmpxchg = dyn_cast<LLVM::AtomicCmpXchgOp>(Val&: loopHead))
503 return cmpxchg.getVal();
504 if (auto bitcast = dyn_cast<LLVM::BitcastOp>(Val&: loopHead))
505 // Handling a non-integer type.
506 return bitcast.getArg();
507 if (auto extract = dyn_cast<LLVM::ExtractValueOp>(Val&: loopHead))
508 // Handling a complex type.
509 return extract.getContainer();
510 llvm_unreachable("invalid cmpxchg loop");
511}
512
513static std::optional<LLVM::AtomicBinOp> getAtomicBinOp(Operation *op,
514 bool updateIsLhs) {
515 return TypeSwitch<Operation *, std::optional<LLVM::AtomicBinOp>>(op)
516 .Case<arith::AddFOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::fadd; })
517 .Case<arith::AddIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::add; })
518 .Case<arith::SubFOp>(
519 caseFn: [updateIsLhs](auto) -> std::optional<LLVM::AtomicBinOp> {
520 // atomicrmw fsub is always `*ptr = *ptr - val`.
521 if (!updateIsLhs)
522 return std::nullopt;
523 return LLVM::AtomicBinOp::fsub;
524 })
525 .Case<arith::SubIOp>(
526 caseFn: [updateIsLhs](auto) -> std::optional<LLVM::AtomicBinOp> {
527 // atomicrmw sub is always `*ptr = *ptr - val`.
528 if (!updateIsLhs)
529 return std::nullopt;
530 return LLVM::AtomicBinOp::sub;
531 })
532 .Case<arith::AndIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::_and; })
533 .Case<arith::OrIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::_or; })
534 .Case<arith::XOrIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::_xor; })
535 .Case<arith::MaxSIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::max; })
536 .Case<arith::MinSIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::min; })
537 .Case<arith::MaxUIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::umax; })
538 .Case<arith::MinUIOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::umin; })
539 .Case<arith::MaximumFOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::fmaximum; })
540 .Case<arith::MinimumFOp>(caseFn: [](auto) { return LLVM::AtomicBinOp::fminimum; })
541 .Case<arith::MaxNumFOp>(
542 caseFn: [](auto) { return LLVM::AtomicBinOp::fmaximumnum; })
543 .Case<arith::MinNumFOp>(
544 caseFn: [](auto) { return LLVM::AtomicBinOp::fminimumnum; })
545 .Default(defaultFn: [](Operation *) { return std::nullopt; });
546}
547
548/// Match an update region computing `x = x <binop> expr`, and return the
549/// atomicrmw kind with the binary operation. Shared by the update and capture
550/// conversions so the same region cannot take atomicrmw in one and the cmpxchg
551/// loop in the other.
552static std::optional<std::pair<LLVM::AtomicBinOp, Operation *>>
553matchAtomicBinOpUpdate(AtomicUpdateOp update) {
554 Block &block = update.getRegion().front();
555 Value arg = block.getArgument(i: 0);
556 Operation *yield = block.getTerminator();
557 if (!yield || yield->getNumOperands() != 1)
558 return std::nullopt;
559 Operation *binOp = yield->getOperand(idx: 0).getDefiningOp();
560 if (!binOp || binOp->getBlock() != &block || binOp->getNumOperands() != 2 ||
561 binOp->getNumResults() != 1)
562 return std::nullopt;
563 // The updated value has to feed the binop and nothing else.
564 if (!arg.hasOneUse() || arg.use_begin()->getOwner() != binOp)
565 return std::nullopt;
566 bool updateIsLhs = binOp->getOperand(idx: 0) == arg;
567 std::optional<LLVM::AtomicBinOp> kind = getAtomicBinOp(op: binOp, updateIsLhs);
568 if (!kind)
569 return std::nullopt;
570 return std::make_pair(x&: *kind, y&: binOp);
571}
572
573/// Generate llvm.atomicrmw or an llvm.cmpxchg loop.
574template <>
575LogicalResult ACCAtomicOpConversion<AtomicUpdateOp>::matchAndRewrite(
576 AtomicUpdateOp update, OpAdaptor adaptor,
577 ConversionPatternRewriter &rewriter) const {
578 Block &updateBlock = update.getRegion().front();
579 Value updateArgument = updateBlock.getArgument(i: 0);
580
581 // Collect operations that depend on the update argument.
582 std::set<Operation *> dependents;
583 SmallVector<Value> worklist;
584 worklist.push_back(Elt: updateArgument);
585 while (!worklist.empty()) {
586 Value value = worklist.back();
587 worklist.pop_back();
588 for (OpOperand &use : value.getUses()) {
589 Operation *useOp = use.getOwner();
590 dependents.insert(x: useOp);
591 if (useOp->getNumResults() == 1)
592 worklist.push_back(Elt: useOp->getResult(idx: 0));
593 }
594 }
595
596 // Move independent operations out of the update block.
597 SmallVector<Operation *> independent;
598 for (Operation &op : updateBlock.getOperations()) {
599 if (dependents.find(x: &op) == dependents.end()) {
600 if (op.hasTrait<OpTrait::IsTerminator>())
601 llvm_unreachable("invalid update operation");
602 independent.push_back(Elt: &op);
603 }
604 }
605 for (Operation *op : independent)
606 rewriter.moveOpBefore(op, existingOp: update);
607
608 // Map arith op to atomicrmw kind.
609 //
610 // In the current version of LLVM, these are the equivalences for float
611 // min/max across the different instructions intrinsics and operations -
612 // confusingly they have slightly different and not very descriptive names.
613 //
614 // | MLIR | atomicrmw inst | llvm intrinsic |
615 // |------------+----------------+-------------------|
616 // | - | fmax | llvm.maxnum.* |
617 // | MaximumFOp | fmaximum | llvm.maximum.* |
618 // | MaxNumFOp | fmaximumnum | llvm.maximumnum.* |
619 //
620 // Sources:
621 // https://llvm.org/docs/LangRef.html#id236
622 // https://llvm.org/docs/LangRef.html#floating-point-min-max-intrinsics-comparison
623 // https://mlir.llvm.org/docs/Dialects/ArithOps/#arithmaximumf-arithmaximumfop
624 // https://mlir.llvm.org/docs/Dialects/ArithOps/#arithmaxnumf-arithmaxnumfop
625
626 // Select the kind and the val of atomicrmw.
627 std::optional<Value> val = std::nullopt;
628 std::optional<LLVM::AtomicBinOp> kind = std::nullopt;
629
630 if (auto matched = matchAtomicBinOpUpdate(update)) {
631 Operation *binOp = matched->second;
632 bool updateIsLhs = binOp->getOperand(idx: 0) == updateArgument;
633 kind = matched->first;
634 val = binOp->getOperand(idx: updateIsLhs ? 1 : 0);
635 }
636
637 // Per-component atomicrmw info for complex type decomposition.
638 // Decomposed complex ops (complex.re/im + arith binop + complex.create)
639 // produce per-component binary ops that each need a separate atomicrmw.
640 struct ComponentAtomic {
641 LLVM::AtomicBinOp kind;
642 Value val;
643 int32_t fieldIdx;
644 };
645 SmallVector<ComponentAtomic, 2> componentAtomics;
646
647 if (!val || !kind) {
648 Type convertedArgTy =
649 this->getTypeConverter()->convertType(t: updateArgument.getType());
650 if (auto structTy = dyn_cast<LLVM::LLVMStructType>(Val&: convertedArgTy)) {
651 if (structTy.getBody().size() == 2 &&
652 structTy.getBody()[0] == structTy.getBody()[1] &&
653 structTy.getBody()[0].isIntOrFloat() &&
654 structTy.getBody()[0].getIntOrFloatBitWidth() > 32) {
655 for (Operation &op : updateBlock.getOperations()) {
656 if (op.hasTrait<OpTrait::IsTerminator>() || op.getNumOperands() < 2)
657 continue;
658 int32_t fieldIdx = -1;
659 Value externalVal = nullptr;
660 bool updateIsLhs = false;
661 for (unsigned i = 0; i < 2; ++i) {
662 Value operand = op.getOperand(idx: i);
663 if (auto reOp = operand.getDefiningOp<complex::ReOp>()) {
664 if (reOp.getOperand() == updateArgument) {
665 fieldIdx = 0;
666 externalVal = op.getOperand(idx: 1 - i);
667 updateIsLhs = i == 0;
668 }
669 } else if (auto imOp = operand.getDefiningOp<complex::ImOp>()) {
670 if (imOp.getOperand() == updateArgument) {
671 fieldIdx = 1;
672 externalVal = op.getOperand(idx: 1 - i);
673 updateIsLhs = i == 0;
674 }
675 }
676 }
677 if (fieldIdx < 0)
678 continue;
679 auto componentKind = getAtomicBinOp(op: &op, updateIsLhs);
680 if (!componentKind)
681 continue;
682 componentAtomics.push_back(Elt: {.kind: *componentKind, .val: externalVal, .fieldIdx: fieldIdx});
683 }
684 }
685 }
686 }
687
688 Location loc = update.getLoc();
689 Value xPtr = getAtomicPointer(originalRef: update.getX(), convertedPtr: adaptor.getX(), loc, rewriter);
690
691 // Require distinct real/imag lanes; duplicate fieldIdx values must fall back
692 // to cmpxchg rather than emitting two atomicrmw ops on the same component.
693 bool hasDistinctComplexLanes = false;
694 if (componentAtomics.size() == 2) {
695 unsigned lanes = 0;
696 for (const ComponentAtomic &ca : componentAtomics) {
697 if (ca.fieldIdx == 0 || ca.fieldIdx == 1)
698 lanes |= 1u << ca.fieldIdx;
699 }
700 hasDistinctComplexLanes = lanes == 0b11;
701 }
702
703 if (val && kind) {
704 auto ordering = LLVM::AtomicOrdering::monotonic;
705 Value operand = rewriter.getRemappedValue(key: *val);
706 // There is no atomic on i1, but it occupies a byte, and and/or/xor keep a
707 // 0/1 byte 0/1, so apply them to the byte.
708 if (operand.getType().isInteger(width: 1) &&
709 llvm::is_contained(Set: {LLVM::AtomicBinOp::_and, LLVM::AtomicBinOp::_or,
710 LLVM::AtomicBinOp::_xor},
711 Element: *kind))
712 operand =
713 LLVM::ZExtOp::create(builder&: rewriter, location: loc, res: rewriter.getI8Type(), arg: operand);
714 LLVM::AtomicRMWOp::create(builder&: rewriter, location: loc, binOp: *kind, ptr: xPtr, val: operand, ordering);
715 } else if (hasDistinctComplexLanes) {
716 auto structTy = cast<LLVM::LLVMStructType>(
717 Val: this->getTypeConverter()->convertType(t: updateArgument.getType()));
718 Type ptrType = LLVM::LLVMPointerType::get(context: rewriter.getContext());
719 auto ordering = LLVM::AtomicOrdering::monotonic;
720 for (ComponentAtomic &ca : componentAtomics) {
721 Value elemPtr =
722 LLVM::GEPOp::create(builder&: rewriter, location: loc, resultType: ptrType, elementType: structTy, basePtr: xPtr,
723 indices: ArrayRef<LLVM::GEPArg>{0, ca.fieldIdx});
724 LLVM::AtomicRMWOp::create(builder&: rewriter, location: loc, binOp: ca.kind, ptr: elemPtr,
725 val: rewriter.getRemappedValue(key: ca.val), ordering);
726 }
727 } else {
728 // Fallback to the llvm.cmpxchg loop generation.
729 genUpdateCmpxchgLoop(update, rewriter);
730 }
731 rewriter.eraseOp(op: update);
732 return success();
733}
734
735/// The cmpxchg loop re-points reads of `v`/`x` inside `expr` at the atomically
736/// loaded value (see moveDependency). An atomicrmw cannot do that, so any
737/// `expr` that loads from memory keeps the loop: the load may be the captured
738/// value itself, and the address is not reliably comparable here.
739static bool exprReadsMemory(Value expr) {
740 SmallVector<Value> worklist{expr};
741 llvm::DenseSet<Operation *> seen;
742 while (!worklist.empty()) {
743 Operation *def = worklist.pop_back_val().getDefiningOp();
744 if (!def || !seen.insert(V: def).second)
745 continue;
746 if (!isMemoryEffectFree(op: def))
747 return true;
748 worklist.append(in_start: def->getOperands().begin(), in_end: def->getOperands().end());
749 }
750 return false;
751}
752
753/// Emit a single atomicrmw for a `x = x <binop> expr` capture.
754template <typename AtomicOpTy>
755LogicalResult ACCAtomicOpConversion<AtomicOpTy>::tryEmitCaptureAtomicRMW(
756 AtomicCaptureOp capture, AtomicUpdateOp update, AtomicReadOp read,
757 ConversionPatternRewriter &rewriter) const {
758 if (read.getX() != update.getX())
759 return failure();
760 auto matched = matchAtomicBinOpUpdate(update);
761 if (!matched)
762 return failure();
763 auto [kind, binOp] = *matched;
764
765 Value arg = update.getRegion().front().getArgument(i: 0);
766 bool updateIsLhs = binOp->getOperand(idx: 0) == arg;
767 Value expr = binOp->getOperand(idx: updateIsLhs ? 1 : 0);
768
769 // Keep serialized and aggregate types on the cmpxchg path.
770 Type argTy = arg.getType();
771 if (!argTy.isIntOrFloat() ||
772 this->getTypeConverter()->convertType(argTy) != argTy)
773 return failure();
774 // The operand must already be available, and must not be the captured value.
775 Operation *exprDef = expr.getDefiningOp();
776 if (exprDef && exprDef->getBlock() == &update.getRegion().front())
777 return failure();
778 if (exprReadsMemory(expr))
779 return failure();
780
781 Location loc = capture.getLoc();
782 Value xRef = update.getX();
783 Value vRef = read.getV();
784 Value xPtr =
785 getAtomicPointer(originalRef: xRef, convertedPtr: rewriter.getRemappedValue(key: xRef), loc, rewriter);
786 Value vPtr =
787 getAtomicPointer(originalRef: vRef, convertedPtr: rewriter.getRemappedValue(key: vRef), loc, rewriter);
788
789 rewriter.setInsertionPoint(capture);
790 auto rmw = LLVM::AtomicRMWOp::create(builder&: rewriter, location: loc, binOp: kind, ptr: xPtr,
791 val: rewriter.getRemappedValue(key: expr),
792 ordering: LLVM::AtomicOrdering::monotonic);
793 // atomicrmw yields the old value; `{update, read}` captures the new one.
794 Value captured = rmw.getRes();
795 if (capture.getFirstOp() == update.getOperation()) {
796 rewriter.moveOpAfter(op: binOp, existingOp: rmw);
797 binOp->replaceUsesOfWith(from: arg, to: captured);
798 captured = binOp->getResult(idx: 0);
799 }
800 rewriter.replaceOpWithNewOp<LLVM::StoreOp>(op: capture, args&: captured, args&: vPtr);
801 return success();
802}
803
804/// Generate an llvm.cmpxchg loop.
805template <>
806LogicalResult ACCAtomicOpConversion<AtomicCaptureOp>::matchAndRewrite(
807 AtomicCaptureOp capture, OpAdaptor /*adaptor*/,
808 ConversionPatternRewriter &rewriter) const {
809 Operation *firstOp = capture.getFirstOp();
810 Operation *secondOp = capture.getSecondOp();
811 Value vPtr = nullptr;
812 Value storeVal = nullptr;
813
814 // A single `x = x <binop> expr` capture becomes one atomicrmw. The cmpxchg
815 // loop below serializes retries and collapses under contention.
816 if (AtomicUpdateOp update = capture.getAtomicUpdateOp())
817 if (AtomicReadOp read = capture.getAtomicReadOp())
818 if (succeeded(Result: tryEmitCaptureAtomicRMW(capture, update, read, rewriter)))
819 return success();
820
821 if (auto firstReadStmt = dyn_cast<AtomicReadOp>(Val: firstOp)) {
822 Location loc = capture.getLoc();
823 Value xRef = firstReadStmt.getX();
824 Value xPtr =
825 getAtomicPointer(originalRef: xRef, convertedPtr: rewriter.getRemappedValue(key: xRef), loc, rewriter);
826 ModuleOp mod = capture->getParentOfType<ModuleOp>();
827 Type xType = getReferencedElementType(ref: xRef, module: mod);
828 Type xTypeOrig = getReferencedElementType(ref: xRef);
829 Value vRef = firstReadStmt.getV();
830 vPtr =
831 getAtomicPointer(originalRef: vRef, convertedPtr: rewriter.getRemappedValue(key: vRef), loc, rewriter);
832
833 Value expr = nullptr;
834 if (auto secondWriteStmt = dyn_cast<AtomicWriteOp>(Val: secondOp)) {
835 // 1. `{ atomic.read, atomic.write }` pattern
836 expr = secondWriteStmt.getExpr();
837 } else if (auto secondUpdateStmt = dyn_cast<AtomicUpdateOp>(Val: secondOp)) {
838 // 2. `{ atomic.read, atomic.update }` pattern
839 Block &updateBlock = secondUpdateStmt.getRegion().front();
840 Operation *terminator = updateBlock.getTerminator();
841 expr = terminator->getOperand(idx: 0);
842 }
843
844 Block *loopBlock = constructCmpxchgLoop(ptr: xPtr, type: xType, expr, rewriter);
845 Value loopArgument = loopBlock->getArgument(i: 0);
846 Operation &loopHead = loopBlock->front();
847 auto condBr = cast<LLVM::CondBrOp>(Val&: loopBlock->back());
848 storeVal = condBr.getFalseDestOperands()[0];
849
850 rewriter.setInsertionPointToStart(loopBlock);
851 loopArgument = deserializeExpr(expr: loopArgument, origTy: xTypeOrig, rewriter);
852
853 // Include flow dependency (v -> expr).
854 if (auto secondUpdateStmt = dyn_cast<AtomicUpdateOp>(Val: secondOp)) {
855 Block &updateBlock = secondUpdateStmt.getRegion().front();
856 Value updateArgument = updateBlock.getArgument(i: 0);
857 updateArgument.replaceAllUsesWith(newValue: loopArgument);
858 updateBlock.walk(callback: [&](Operation *op) {
859 if (!op->hasTrait<OpTrait::IsTerminator>())
860 rewriter.moveOpBefore(op, existingOp: &loopHead);
861 });
862 }
863 moveDependency(vRef, vPtr, expr, loopArgument, loopHead, rewriter,
864 getLoadAddress);
865 } else if (auto firstUpdateStmt = dyn_cast<AtomicUpdateOp>(Val: firstOp)) {
866 if (auto secondReadStmt = dyn_cast<AtomicReadOp>(Val: secondOp)) {
867 // 3. `{ atomic.update, atomic.read }` pattern
868 storeVal = genUpdateCmpxchgLoop(update: firstUpdateStmt, rewriter);
869
870 Value vRef = secondReadStmt.getV();
871 vPtr = getAtomicPointer(originalRef: vRef, convertedPtr: rewriter.getRemappedValue(key: vRef),
872 loc: capture.getLoc(), rewriter);
873 }
874 }
875 // Generate `v = x`.
876 rewriter.setInsertionPoint(capture);
877 rewriter.replaceOpWithNewOp<LLVM::StoreOp>(op: capture, args&: storeVal, args&: vPtr);
878 return success();
879}
880
881} // namespace
882
883namespace mlir {
884
885void configureACCAtomicConversionLegality(ConversionTarget &target) {
886 target.addIllegalOp<AtomicReadOp, AtomicWriteOp, AtomicUpdateOp,
887 AtomicCaptureOp>();
888}
889
890void populateACCAtomicPatterns(const LLVMTypeConverter &converter,
891 RewritePatternSet &patterns,
892 acc::OpenACCSupport &accSupport,
893 ACCAtomicLoadAddressCallback getLoadAddress) {
894 patterns.add<ACCAtomicOpConversion<AtomicReadOp>,
895 ACCAtomicOpConversion<AtomicWriteOp>,
896 ACCAtomicOpConversion<AtomicUpdateOp>,
897 ACCAtomicOpConversion<AtomicCaptureOp>>(arg: converter, args&: accSupport,
898 args&: getLoadAddress);
899}
900
901} // namespace mlir
902