LLVM 24.0.0git
AMDGPUAtomicOptimizer.cpp
Go to the documentation of this file.
1//===-- AMDGPUAtomicOptimizer.cpp -----------------------------------------===//
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/// \file
10/// This pass optimizes atomic operations by using a single lane of a wavefront
11/// to perform the atomic operation, thus reducing contention on that memory
12/// location.
13/// Atomic optimizer uses following strategies to compute scan and reduced
14/// values
15/// 1. DPP -
16/// This is the most efficient implementation for scan. DPP uses Whole Wave
17/// Mode (WWM)
18/// 2. Iterative -
19// An alternative implementation iterates over all active lanes
20/// of Wavefront using llvm.cttz and performs scan using readlane & writelane
21/// intrinsics
22//===----------------------------------------------------------------------===//
23
24#include "AMDGPU.h"
25#include "AMDGPUInstrInfo.h"
26#include "GCNSubtarget.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/InstVisitor.h"
32#include "llvm/IR/IntrinsicsAMDGPU.h"
36
37#define DEBUG_TYPE "amdgpu-atomic-optimizer"
38
39using namespace llvm;
40using namespace llvm::AMDGPU;
41
42namespace {
43
44struct ReplacementInfo {
47 unsigned ValIdx;
48 bool ValDivergent;
49 bool IsLDS;
50};
51
52class AMDGPUAtomicOptimizer : public FunctionPass {
53public:
54 static char ID;
55 ScanOptions ScanImpl;
56 AMDGPUAtomicOptimizer(ScanOptions ScanImpl)
57 : FunctionPass(ID), ScanImpl(ScanImpl) {}
58
59 bool runOnFunction(Function &F) override;
60
61 void getAnalysisUsage(AnalysisUsage &AU) const override {
65 }
66};
67
68class AMDGPUAtomicOptimizerImpl
69 : public InstVisitor<AMDGPUAtomicOptimizerImpl> {
70private:
71 Function &F;
73 const UniformityInfo &UA;
74 const DataLayout &DL;
75 DomTreeUpdater &DTU;
76 const GCNSubtarget &ST;
77 bool IsPixelShader;
78 ScanOptions ScanImpl;
79
81 Value *const Identity) const;
82 Value *buildShiftRight(IRBuilder<> &B, Value *V, Value *const Identity) const;
83
84 std::pair<Value *, Value *>
85 buildScanIteratively(IRBuilder<> &B, AtomicRMWInst::BinOp Op,
86 Value *const Identity, Value *V, Instruction &I,
87 BasicBlock *ComputeLoop, BasicBlock *ComputeEnd) const;
88
89 void optimizeAtomic(Instruction &I, AtomicRMWInst::BinOp Op, unsigned ValIdx,
90 bool ValDivergent, bool IsLDS) const;
91
92public:
93 AMDGPUAtomicOptimizerImpl() = delete;
94
95 AMDGPUAtomicOptimizerImpl(Function &F, const UniformityInfo &UA,
96 DomTreeUpdater &DTU, const GCNSubtarget &ST,
97 ScanOptions ScanImpl)
98 : F(F), UA(UA), DL(F.getDataLayout()), DTU(DTU), ST(ST),
99 IsPixelShader(F.getCallingConv() == CallingConv::AMDGPU_PS),
100 ScanImpl(ScanImpl) {}
101
102 bool run();
103
104 void visitAtomicRMWInst(AtomicRMWInst &I);
105 void visitIntrinsicInst(IntrinsicInst &I);
106};
107
108} // namespace
109
110char AMDGPUAtomicOptimizer::ID = 0;
111
112char &llvm::AMDGPUAtomicOptimizerID = AMDGPUAtomicOptimizer::ID;
113
114bool AMDGPUAtomicOptimizer::runOnFunction(Function &F) {
115 if (skipFunction(F)) {
116 return false;
117 }
118
119 const UniformityInfo &UA =
120 getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
121
123 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
124 DomTreeUpdater DTU(DTW ? &DTW->getDomTree() : nullptr,
125 DomTreeUpdater::UpdateStrategy::Lazy);
126
127 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
128 const TargetMachine &TM = TPC.getTM<TargetMachine>();
129 const GCNSubtarget &ST = TM.getSubtarget<GCNSubtarget>(F);
130
131 return AMDGPUAtomicOptimizerImpl(F, UA, DTU, ST, ScanImpl).run();
132}
133
136 const auto &UA = AM.getResult<UniformityInfoAnalysis>(F);
137
139 DomTreeUpdater::UpdateStrategy::Lazy);
140 const GCNSubtarget &ST = TM.getSubtarget<GCNSubtarget>(F);
141
142 bool IsChanged = AMDGPUAtomicOptimizerImpl(F, UA, DTU, ST, ScanImpl).run();
143
144 if (!IsChanged) {
145 return PreservedAnalyses::all();
146 }
147
150 return PA;
151}
152
153bool AMDGPUAtomicOptimizerImpl::run() {
154 // Scan option None disables the Pass
155 if (ScanImpl == ScanOptions::None)
156 return false;
157 if (ST.isSingleLaneExecution(F))
158 return false;
159
160 visit(F);
161 if (ToReplace.empty())
162 return false;
163
164 for (auto &[I, Op, ValIdx, ValDivergent, IsLDS] : ToReplace)
165 optimizeAtomic(*I, Op, ValIdx, ValDivergent, IsLDS);
166 ToReplace.clear();
167 return true;
168}
169
170static bool isLegalCrossLaneType(Type *Ty) {
171 switch (Ty->getTypeID()) {
172 case Type::FloatTyID:
173 case Type::DoubleTyID:
174 return true;
175 case Type::IntegerTyID: {
176 unsigned Size = Ty->getIntegerBitWidth();
177 return (Size == 32 || Size == 64);
178 }
179 default:
180 return false;
181 }
182}
183
184void AMDGPUAtomicOptimizerImpl::visitAtomicRMWInst(AtomicRMWInst &I) {
185 if (I.getType()->isVectorTy() || I.isVolatile())
186 return;
187
188 // Early exit for unhandled address space atomic instructions.
189 switch (I.getPointerAddressSpace()) {
190 default:
191 return;
194 break;
195 }
196
197 AtomicRMWInst::BinOp Op = I.getOperation();
198
199 switch (Op) {
200 default:
201 return;
215 break;
216 }
217
218 // Only 32 and 64 bit floating point atomic ops are supported.
220 !(I.getType()->isFloatTy() || I.getType()->isDoubleTy())) {
221 return;
222 }
223
224 const unsigned PtrIdx = 0;
225 const unsigned ValIdx = 1;
226
227 // If the pointer operand is divergent, then each lane is doing an atomic
228 // operation on a different address, and we cannot optimize that.
229 if (UA.isDivergentAtUse(I.getOperandUse(PtrIdx))) {
230 return;
231 }
232
233 bool ValDivergent = UA.isDivergentAtUse(I.getOperandUse(ValIdx));
234
235 // If the value operand is divergent, each lane is contributing a different
236 // value to the atomic calculation. We can only optimize divergent values if
237 // we have DPP available on our subtarget (for DPP strategy), and the atomic
238 // operation is 32 or 64 bits.
239 if (ValDivergent) {
240 if (ScanImpl == ScanOptions::DPP && !ST.hasDPP())
241 return;
242
243 if (!isLegalCrossLaneType(I.getType()))
244 return;
245 }
246
247 const bool IsLDS = I.getPointerAddressSpace() == AMDGPUAS::LOCAL_ADDRESS;
248
249 // The iterative scan runs once per active lane and costs more than the
250 // hardware serialization of a native LDS atomic.
251 if (IsLDS && ValDivergent && ScanImpl == ScanOptions::Iterative &&
253 TargetLowering::AtomicExpansionKind::None)
254 return;
255
256 // If we get here, we can optimize the atomic using a single wavefront-wide
257 // atomic operation to do the calculation for the entire wavefront, so
258 // remember the instruction so we can come back to it.
259 ToReplace.push_back({&I, Op, ValIdx, ValDivergent, IsLDS});
260}
261
262void AMDGPUAtomicOptimizerImpl::visitIntrinsicInst(IntrinsicInst &I) {
263 if (I.getType()->isVectorTy())
264 return;
265
267
268 switch (I.getIntrinsicID()) {
269 default:
270 return;
271 case Intrinsic::amdgcn_struct_buffer_atomic_add:
272 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_add:
273 case Intrinsic::amdgcn_raw_buffer_atomic_add:
274 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_add:
276 break;
277 case Intrinsic::amdgcn_struct_buffer_atomic_sub:
278 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_sub:
279 case Intrinsic::amdgcn_raw_buffer_atomic_sub:
280 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_sub:
282 break;
283 case Intrinsic::amdgcn_struct_buffer_atomic_and:
284 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_and:
285 case Intrinsic::amdgcn_raw_buffer_atomic_and:
286 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_and:
288 break;
289 case Intrinsic::amdgcn_struct_buffer_atomic_or:
290 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_or:
291 case Intrinsic::amdgcn_raw_buffer_atomic_or:
292 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_or:
294 break;
295 case Intrinsic::amdgcn_struct_buffer_atomic_xor:
296 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_xor:
297 case Intrinsic::amdgcn_raw_buffer_atomic_xor:
298 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_xor:
300 break;
301 case Intrinsic::amdgcn_struct_buffer_atomic_smin:
302 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_smin:
303 case Intrinsic::amdgcn_raw_buffer_atomic_smin:
304 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_smin:
306 break;
307 case Intrinsic::amdgcn_struct_buffer_atomic_umin:
308 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_umin:
309 case Intrinsic::amdgcn_raw_buffer_atomic_umin:
310 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_umin:
312 break;
313 case Intrinsic::amdgcn_struct_buffer_atomic_smax:
314 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_smax:
315 case Intrinsic::amdgcn_raw_buffer_atomic_smax:
316 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_smax:
318 break;
319 case Intrinsic::amdgcn_struct_buffer_atomic_umax:
320 case Intrinsic::amdgcn_struct_ptr_buffer_atomic_umax:
321 case Intrinsic::amdgcn_raw_buffer_atomic_umax:
322 case Intrinsic::amdgcn_raw_ptr_buffer_atomic_umax:
324 break;
325 }
326
327 const AMDGPU::BufferIntrinsicInfo &BufInfo =
328 *AMDGPU::lookupBufferIntrinsic(I.getIntrinsicID());
329 auto *Aux = cast<ConstantInt>(I.getArgOperand(*BufInfo.getAuxArg()));
330 if (Aux->getZExtValue() & AMDGPU::CPol::VOLATILE)
331 return;
332
333 const unsigned ValIdx = *BufInfo.getVDataArg();
334
335 const bool ValDivergent = UA.isDivergentAtUse(I.getOperandUse(ValIdx));
336
337 // If the value operand is divergent, each lane is contributing a different
338 // value to the atomic calculation. We can only optimize divergent values if
339 // we have DPP available on our subtarget (for DPP strategy), and the atomic
340 // operation is 32 or 64 bits.
341 if (ValDivergent) {
342 if (ScanImpl == ScanOptions::DPP && !ST.hasDPP())
343 return;
344
345 if (!isLegalCrossLaneType(I.getType()))
346 return;
347 }
348
349 // If any of the other arguments to the intrinsic are divergent, we can't
350 // optimize the operation.
351 for (unsigned Idx = 1; Idx < I.getNumOperands(); Idx++) {
352 if (UA.isDivergentAtUse(I.getOperandUse(Idx)))
353 return;
354 }
355
356 // If we get here, we can optimize the atomic using a single wavefront-wide
357 // atomic operation to do the calculation for the entire wavefront, so
358 // remember the instruction so we can come back to it.
359 // Buffer atomics are never LDS.
360 ToReplace.push_back({&I, Op, ValIdx, ValDivergent, /*IsLDS=*/false});
361}
362
363// Use the builder to create the non-atomic counterpart of the specified
364// atomicrmw binary op.
366 Value *LHS, Value *RHS) {
368
369 switch (Op) {
370 default:
371 llvm_unreachable("Unhandled atomic op");
373 return B.CreateBinOp(Instruction::Add, LHS, RHS);
375 return B.CreateFAdd(LHS, RHS);
377 return B.CreateBinOp(Instruction::Sub, LHS, RHS);
379 return B.CreateFSub(LHS, RHS);
381 return B.CreateBinOp(Instruction::And, LHS, RHS);
383 return B.CreateBinOp(Instruction::Or, LHS, RHS);
385 return B.CreateBinOp(Instruction::Xor, LHS, RHS);
386
389 break;
392 break;
395 break;
398 break;
400 return B.CreateMaxNum(LHS, RHS);
402 return B.CreateMinNum(LHS, RHS);
403 }
404 Value *Cond = B.CreateICmp(Pred, LHS, RHS);
405 return B.CreateSelect(Cond, LHS, RHS);
406}
407
408// Use the builder to create an inclusive scan of V across the wavefront, with
409// all lanes active.
410Value *AMDGPUAtomicOptimizerImpl::buildScan(IRBuilder<> &B,
412 Value *Identity) const {
413 Type *AtomicTy = V->getType();
414 Module *M = B.getModule();
416 M, Intrinsic::amdgcn_update_dpp, AtomicTy);
417
418 for (unsigned Idx = 0; Idx < 4; Idx++) {
420 B, Op, V,
421 B.CreateCall(UpdateDPP,
422 {Identity, V, B.getInt32(DPP::ROW_SHR0 | 1 << Idx),
423 B.getInt32(0xf), B.getInt32(0xf), B.getFalse()}));
424 }
425 if (ST.hasDPPBroadcasts()) {
426 // GFX9 has DPP row broadcast operations.
428 B, Op, V,
429 B.CreateCall(UpdateDPP,
430 {Identity, V, B.getInt32(DPP::BCAST15), B.getInt32(0xa),
431 B.getInt32(0xf), B.getFalse()}));
433 B, Op, V,
434 B.CreateCall(UpdateDPP,
435 {Identity, V, B.getInt32(DPP::BCAST31), B.getInt32(0xc),
436 B.getInt32(0xf), B.getFalse()}));
437 } else {
438 // On GFX10 all DPP operations are confined to a single row. To get cross-
439 // row operations we have to use permlane or readlane.
440
441 // Combine lane 15 into lanes 16..31 (and, for wave 64, lane 47 into lanes
442 // 48..63).
443 assert(ST.hasPermlane16Insts());
444 Value *PermX =
445 B.CreateIntrinsic(AtomicTy, Intrinsic::amdgcn_permlanex16,
446 {PoisonValue::get(AtomicTy), V, B.getInt32(-1),
447 B.getInt32(-1), B.getFalse(), B.getFalse()});
448
449 Value *UpdateDPPCall = B.CreateCall(
450 UpdateDPP, {Identity, PermX, B.getInt32(DPP::QUAD_PERM_ID),
451 B.getInt32(0xa), B.getInt32(0xf), B.getFalse()});
452 V = buildNonAtomicBinOp(B, Op, V, UpdateDPPCall);
453
454 if (!ST.isWave32()) {
455 // Combine lane 31 into lanes 32..63.
456 Value *const Lane31 = B.CreateIntrinsic(
457 AtomicTy, Intrinsic::amdgcn_readlane, {V, B.getInt32(31)});
458
459 Value *UpdateDPPCall = B.CreateCall(
460 UpdateDPP, {Identity, Lane31, B.getInt32(DPP::QUAD_PERM_ID),
461 B.getInt32(0xc), B.getInt32(0xf), B.getFalse()});
462
463 V = buildNonAtomicBinOp(B, Op, V, UpdateDPPCall);
464 }
465 }
466 return V;
467}
468
469// Use the builder to create a shift right of V across the wavefront, with all
470// lanes active, to turn an inclusive scan into an exclusive scan.
471Value *AMDGPUAtomicOptimizerImpl::buildShiftRight(IRBuilder<> &B, Value *V,
472 Value *Identity) const {
473 Type *AtomicTy = V->getType();
474 Module *M = B.getModule();
476 M, Intrinsic::amdgcn_update_dpp, AtomicTy);
477 if (ST.hasDPPWavefrontShifts()) {
478 // GFX9 has DPP wavefront shift operations.
479 V = B.CreateCall(UpdateDPP,
480 {Identity, V, B.getInt32(DPP::WAVE_SHR1), B.getInt32(0xf),
481 B.getInt32(0xf), B.getFalse()});
482 } else {
484 M, Intrinsic::amdgcn_readlane, AtomicTy);
486 M, Intrinsic::amdgcn_writelane, AtomicTy);
487
488 // On GFX10 all DPP operations are confined to a single row. To get cross-
489 // row operations we have to use permlane or readlane.
490 Value *Old = V;
491 V = B.CreateCall(UpdateDPP,
492 {Identity, V, B.getInt32(DPP::ROW_SHR0 + 1),
493 B.getInt32(0xf), B.getInt32(0xf), B.getFalse()});
494
495 // Copy the old lane 15 to the new lane 16.
496 V = B.CreateCall(WriteLane, {B.CreateCall(ReadLane, {Old, B.getInt32(15)}),
497 B.getInt32(16), V});
498
499 if (!ST.isWave32()) {
500 // Copy the old lane 31 to the new lane 32.
501 V = B.CreateCall(
502 WriteLane,
503 {B.CreateCall(ReadLane, {Old, B.getInt32(31)}), B.getInt32(32), V});
504
505 // Copy the old lane 47 to the new lane 48.
506 V = B.CreateCall(
507 WriteLane,
508 {B.CreateCall(ReadLane, {Old, B.getInt32(47)}), B.getInt32(48), V});
509 }
510 }
511
512 return V;
513}
514
515// Use the builder to create an exclusive scan and compute the final reduced
516// value using an iterative approach. This provides an alternative
517// implementation to DPP which uses WMM for scan computations. This API iterate
518// over active lanes to read, compute and update the value using
519// readlane and writelane intrinsics.
520std::pair<Value *, Value *> AMDGPUAtomicOptimizerImpl::buildScanIteratively(
521 IRBuilder<> &B, AtomicRMWInst::BinOp Op, Value *const Identity, Value *V,
522 Instruction &I, BasicBlock *ComputeLoop, BasicBlock *ComputeEnd) const {
523 auto *Ty = I.getType();
524 auto *WaveTy = B.getIntNTy(ST.getWavefrontSize());
525 auto *EntryBB = I.getParent();
526
527 auto *Ballot =
528 B.CreateIntrinsic(Intrinsic::amdgcn_ballot, WaveTy, B.getTrue());
529
530 // Start inserting instructions for ComputeLoop block
531 B.SetInsertPoint(ComputeLoop);
532 // Phi nodes for Accumulator, Scan results destination, and Active Lanes
533 auto *Accumulator = B.CreatePHI(Ty, 2, "Accumulator");
534 Accumulator->addIncoming(Identity, EntryBB);
535 auto *OldValuePhi = B.CreatePHI(Ty, 2, "OldValuePhi");
536 OldValuePhi->addIncoming(PoisonValue::get(Ty), EntryBB);
537 auto *ActiveBits = B.CreatePHI(WaveTy, 2, "ActiveBits");
538 ActiveBits->addIncoming(Ballot, EntryBB);
539
540 // Use llvm.cttz intrinsic to find the lowest remaining active lane.
541 auto *FF1 =
542 B.CreateIntrinsic(Intrinsic::cttz, WaveTy, {ActiveBits, B.getTrue()});
543
544 auto *LaneIdxInt = B.CreateTrunc(FF1, B.getInt32Ty());
545
546 // Get the value required for atomic operation
547 Value *LaneValue = B.CreateIntrinsic(V->getType(), Intrinsic::amdgcn_readlane,
548 {V, LaneIdxInt});
549
550 // Perform writelane because intermediate scan results are required later in
551 // the kernel computations
552 Value *OldValue = B.CreateIntrinsic(V->getType(), Intrinsic::amdgcn_writelane,
553 {Accumulator, LaneIdxInt, OldValuePhi});
554 OldValuePhi->addIncoming(OldValue, ComputeLoop);
555
556 // Accumulate the results
557 auto *NewAccumulator = buildNonAtomicBinOp(B, Op, Accumulator, LaneValue);
558 Accumulator->addIncoming(NewAccumulator, ComputeLoop);
559
560 // Set bit to zero of current active lane so that for next iteration llvm.cttz
561 // return the next active lane
562 auto *Mask = B.CreateShl(ConstantInt::get(WaveTy, 1), FF1);
563
564 auto *InverseMask = B.CreateXor(Mask, ConstantInt::getAllOnesValue(WaveTy));
565 auto *NewActiveBits = B.CreateAnd(ActiveBits, InverseMask);
566 ActiveBits->addIncoming(NewActiveBits, ComputeLoop);
567
568 // Branch out of the loop when all lanes are processed.
569 auto *IsEnd = B.CreateICmpEQ(NewActiveBits, ConstantInt::get(WaveTy, 0));
570 B.CreateCondBr(IsEnd, ComputeEnd, ComputeLoop);
571
572 B.SetInsertPoint(ComputeEnd);
573
574 return {OldValue, NewAccumulator};
575}
576
579 LLVMContext &C = Ty->getContext();
580 const unsigned BitWidth = Ty->getPrimitiveSizeInBits();
581 switch (Op) {
582 default:
583 llvm_unreachable("Unhandled atomic op");
589 return ConstantInt::get(C, APInt::getMinValue(BitWidth));
592 return ConstantInt::get(C, APInt::getMaxValue(BitWidth));
594 return ConstantInt::get(C, APInt::getSignedMinValue(BitWidth));
596 return ConstantInt::get(C, APInt::getSignedMaxValue(BitWidth));
598 return ConstantFP::get(C, APFloat::getZero(Ty->getFltSemantics(), true));
600 return ConstantFP::get(C, APFloat::getZero(Ty->getFltSemantics(), false));
603 // FIXME: atomicrmw fmax/fmin behave like llvm.maxnum/minnum so NaN is the
604 // closest thing they have to an identity, but it still does not preserve
605 // the difference between quiet and signaling NaNs or NaNs with different
606 // payloads.
607 return ConstantFP::get(C, APFloat::getNaN(Ty->getFltSemantics()));
608 }
609}
610
612 switch (Op) {
613 default:
615 "Atomic Op yet to be ported to use Wave Reduction intrinsics.");
618 return Intrinsic::amdgcn_wave_reduce_add;
621 return Intrinsic::amdgcn_wave_reduce_fadd;
623 return Intrinsic::amdgcn_wave_reduce_and;
625 return Intrinsic::amdgcn_wave_reduce_or;
627 return Intrinsic::amdgcn_wave_reduce_xor;
629 return Intrinsic::amdgcn_wave_reduce_umax;
631 return Intrinsic::amdgcn_wave_reduce_max;
633 return Intrinsic::amdgcn_wave_reduce_fmax;
635 return Intrinsic::amdgcn_wave_reduce_umin;
637 return Intrinsic::amdgcn_wave_reduce_min;
639 return Intrinsic::amdgcn_wave_reduce_fmin;
640 }
641}
642
645 return (CI && CI->isOne()) ? RHS : B.CreateMul(LHS, RHS);
646}
647
648void AMDGPUAtomicOptimizerImpl::optimizeAtomic(Instruction &I,
650 unsigned ValIdx,
651 bool ValDivergent,
652 bool IsLDS) const {
653 // Don't generate a DPP scan if !amdgpu.expected.active.lane hint indicates
654 // insufficient lanes to offset fixed overhead.
655
656 // FIXME: The threshold was tuned empirically on gfx11 and gfx12. The DPP scan
657 // overhead differs across subtargets, so the break-even point may differ too;
658 // this may need to become subtarget-dependent.
659 if (IsLDS && ValDivergent && ScanImpl == ScanOptions::DPP) {
660 if (MDNode *MD = I.getMetadata("amdgpu.expected.active.lanes")) {
661 auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
662 constexpr unsigned ActiveLanesThreshold = 5;
663 if (CI->getValue().ule(ActiveLanesThreshold))
664 return;
665 }
666 }
667
668 // Start building just before the instruction.
669 IRBuilder<> B(&I);
670
672 B.setIsFPConstrained(I.getFunction()->hasFnAttribute(Attribute::StrictFP));
673 }
674
675 // If we are in a pixel shader, because of how we have to mask out helper
676 // lane invocations, we need to record the entry and exit BB's.
677 BasicBlock *PixelEntryBB = nullptr;
678 BasicBlock *PixelExitBB = nullptr;
679
680 // If we're optimizing an atomic within a pixel shader, we need to wrap the
681 // entire atomic operation in a helper-lane check. We do not want any helper
682 // lanes that are around only for the purposes of derivatives to take part
683 // in any cross-lane communication, and we use a branch on whether the lane is
684 // live to do this.
685 if (IsPixelShader) {
686 // Record I's original position as the entry block.
687 PixelEntryBB = I.getParent();
688
689 Value *const Cond = B.CreateIntrinsic(Intrinsic::amdgcn_ps_live, {});
690 Instruction *const NonHelperTerminator =
691 SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, &DTU, nullptr);
692
693 // Record I's new position as the exit block.
694 PixelExitBB = I.getParent();
695
696 I.moveBefore(NonHelperTerminator->getIterator());
697 B.SetInsertPoint(&I);
698 }
699
700 Type *const Ty = I.getType();
701 Type *Int32Ty = B.getInt32Ty();
702 bool isAtomicFloatingPointTy = Ty->isFloatingPointTy();
703 [[maybe_unused]] const unsigned TyBitWidth = DL.getTypeSizeInBits(Ty);
704
705 // This is the value in the atomic operation we need to combine in order to
706 // reduce the number of atomic operations.
707 Value *V = I.getOperand(ValIdx);
708
709 // We need to know how many lanes are active within the wavefront, and we do
710 // this by doing a ballot of active lanes.
711 Type *const WaveTy = B.getIntNTy(ST.getWavefrontSize());
712 CallInst *const Ballot = B.CreateIntrinsicWithoutFolding(
713 Intrinsic::amdgcn_ballot, WaveTy, B.getTrue());
714
715 // We need to know how many lanes are active within the wavefront that are
716 // below us. If we counted each lane linearly starting from 0, a lane is
717 // below us only if its associated index was less than ours. We do this by
718 // using the mbcnt intrinsic.
719 Value *Mbcnt;
720 if (ST.isWave32()) {
721 Mbcnt =
722 B.CreateIntrinsic(Intrinsic::amdgcn_mbcnt_lo, {Ballot, B.getInt32(0)});
723 } else {
724 Value *const ExtractLo = B.CreateTrunc(Ballot, Int32Ty);
725 Value *const ExtractHi = B.CreateTrunc(B.CreateLShr(Ballot, 32), Int32Ty);
726 Mbcnt = B.CreateIntrinsic(Intrinsic::amdgcn_mbcnt_lo,
727 {ExtractLo, B.getInt32(0)});
728 Mbcnt = B.CreateIntrinsic(Intrinsic::amdgcn_mbcnt_hi, {ExtractHi, Mbcnt});
729 }
730
731 Function *F = I.getFunction();
732 LLVMContext &C = F->getContext();
733 const bool NeedResult = !I.use_empty();
734 const bool UseWaveReductionIntrinsic = !ValDivergent || !NeedResult;
735
736 // For atomic sub, perform scan with add operation and allow one lane to
737 // subtract the reduced value later.
738 AtomicRMWInst::BinOp ScanOp = Op;
739 if (Op == AtomicRMWInst::Sub) {
740 ScanOp = AtomicRMWInst::Add;
741 } else if (Op == AtomicRMWInst::FSub) {
742 ScanOp = AtomicRMWInst::FAdd;
743 }
744 Value *Identity = getIdentityValueForAtomicOp(Ty, ScanOp);
745
746 Value *ExclScan = nullptr;
747 Value *NewV = nullptr;
748
749 BasicBlock *ComputeLoop = nullptr;
750 BasicBlock *ComputeEnd = nullptr;
751 if (UseWaveReductionIntrinsic) {
752 // Build reductions with wave-reduce intrinsics.
753 unsigned Strategy = ScanImpl == ScanOptions::DPP ? 2 : 1;
754 Intrinsic::ID WaveRedIntrinsic = getWaveReductionIntrinsic(Op);
755 NewV = B.CreateIntrinsic(WaveRedIntrinsic, Ty, {V, B.getInt32(Strategy)});
756 } else {
757 // If we have a divergent value in each lane, we need to combine the value
758 // using DPP.
759 assert(ValDivergent && NeedResult);
760 if (ScanImpl == ScanOptions::DPP) {
761 // First we need to set all inactive invocations to the identity value,
762 // so that they can correctly contribute to the final result.
763 NewV =
764 B.CreateIntrinsic(Intrinsic::amdgcn_set_inactive, Ty, {V, Identity});
765 NewV = buildScan(B, ScanOp, NewV, Identity);
766 ExclScan = buildShiftRight(B, NewV, Identity);
767 // Read the value from the last lane, which has accumulated the values
768 // of each active lane in the wavefront. This will be our new value
769 // which we will provide to the atomic operation.
770 Value *const LastLaneIdx = B.getInt32(ST.getWavefrontSize() - 1);
771 NewV = B.CreateIntrinsic(Ty, Intrinsic::amdgcn_readlane,
772 {NewV, LastLaneIdx});
773 // Finally mark the readlanes in the WWM section.
774 NewV = B.CreateIntrinsic(Intrinsic::amdgcn_strict_wwm, Ty, NewV);
775 } else if (ScanImpl == ScanOptions::Iterative) {
776 // Alternative implementation for scan
777 ComputeLoop = BasicBlock::Create(C, "ComputeLoop", F);
778 ComputeEnd = BasicBlock::Create(C, "ComputeEnd", F);
779 std::tie(ExclScan, NewV) = buildScanIteratively(B, ScanOp, Identity, V, I,
780 ComputeLoop, ComputeEnd);
781 } else {
782 llvm_unreachable("Atomic Optimzer is disabled for None strategy");
783 }
784 }
785
786 // We only want a single lane to enter our new control flow, and we do this
787 // by checking if there are any active lanes below us. Only one lane will
788 // have 0 active lanes below us, so that will be the only one to progress.
789 Value *const Cond = B.CreateICmpEQ(Mbcnt, B.getInt32(0));
790
791 // Store I's original basic block before we split the block.
792 BasicBlock *const OriginalBB = I.getParent();
793
794 // We need to introduce some new control flow to force a single lane to be
795 // active. We do this by splitting I's basic block at I, and introducing the
796 // new block such that:
797 // entry --> single_lane -\
798 // \------------------> exit
799 Instruction *const SingleLaneTerminator =
800 SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, &DTU, nullptr);
801
802 // At this point, we have split the I's block to allow one lane in wavefront
803 // to update the precomputed reduced value. Also, completed the codegen for
804 // new control flow i.e. iterative loop which perform reduction and scan using
805 // ComputeLoop and ComputeEnd.
806 // For the new control flow, we need to move branch instruction i.e.
807 // terminator created during SplitBlockAndInsertIfThen from I's block to
808 // ComputeEnd block. We also need to set up predecessor to next block when
809 // single lane done updating the final reduced value.
810 BasicBlock *Predecessor = nullptr;
811 if (!UseWaveReductionIntrinsic && ScanImpl == ScanOptions::Iterative) {
812 // Move terminator from I's block to ComputeEnd block.
813 //
814 // OriginalBB is known to have a branch as terminator because
815 // SplitBlockAndInsertIfThen will have inserted one.
816 CondBrInst *Terminator = cast<CondBrInst>(OriginalBB->getTerminator());
817 B.SetInsertPoint(ComputeEnd);
818 Terminator->removeFromParent();
819 B.Insert(Terminator);
820
821 // Branch to ComputeLoop Block unconditionally from the I's block for
822 // iterative approach.
823 B.SetInsertPoint(OriginalBB);
824 B.CreateBr(ComputeLoop);
825
826 // Update the dominator tree for new control flow.
828 {{DominatorTree::Insert, OriginalBB, ComputeLoop},
829 {DominatorTree::Insert, ComputeLoop, ComputeEnd}});
830
831 // We're moving the terminator from EntryBB to ComputeEnd, make sure we move
832 // the DT edges as well.
833 for (auto *Succ : Terminator->successors()) {
834 DomTreeUpdates.push_back({DominatorTree::Insert, ComputeEnd, Succ});
835 DomTreeUpdates.push_back({DominatorTree::Delete, OriginalBB, Succ});
836 }
837
838 DTU.applyUpdates(DomTreeUpdates);
839
840 Predecessor = ComputeEnd;
841 } else {
842 Predecessor = OriginalBB;
843 }
844 // Move the IR builder into single_lane next.
845 B.SetInsertPoint(SingleLaneTerminator);
846
847 // Clone the original atomic operation into single lane, replacing the
848 // original value with our newly created one.
849 Instruction *const NewI = I.clone();
850 B.Insert(NewI);
851 NewI->setOperand(ValIdx, NewV);
852
853 // Move the IR builder into exit next, and start inserting just before the
854 // original instruction.
855 B.SetInsertPoint(&I);
856
857 if (NeedResult) {
858 // Create a PHI node to get our new atomic result into the exit block.
859 PHINode *const PHI = B.CreatePHI(Ty, 2);
860 PHI->addIncoming(PoisonValue::get(Ty), Predecessor);
861 PHI->addIncoming(NewI, SingleLaneTerminator->getParent());
862
863 // We need to broadcast the value who was the lowest active lane (the first
864 // lane) to all other lanes in the wavefront.
865
866 Value *ReadlaneVal = PHI;
867 if (TyBitWidth < 32)
868 ReadlaneVal = B.CreateZExt(PHI, B.getInt32Ty());
869
870 Value *BroadcastI = B.CreateIntrinsic(
871 ReadlaneVal->getType(), Intrinsic::amdgcn_readfirstlane, ReadlaneVal);
872 if (TyBitWidth < 32)
873 BroadcastI = B.CreateTrunc(BroadcastI, Ty);
874
875 // Now that we have the result of our single atomic operation, we need to
876 // get our individual lane's slice into the result. We use the lane offset
877 // we previously calculated combined with the atomic result value we got
878 // from the first lane, to get our lane's index into the atomic result.
879 Value *LaneOffset = nullptr;
880 if (ValDivergent) {
881 if (ScanImpl == ScanOptions::DPP) {
882 LaneOffset =
883 B.CreateIntrinsic(Intrinsic::amdgcn_strict_wwm, Ty, ExclScan);
884 } else if (ScanImpl == ScanOptions::Iterative) {
885 LaneOffset = ExclScan;
886 } else {
887 llvm_unreachable("Atomic Optimzer is disabled for None strategy");
888 }
889 } else {
890 Mbcnt = isAtomicFloatingPointTy ? B.CreateUIToFP(Mbcnt, Ty)
891 : B.CreateIntCast(Mbcnt, Ty, false);
892 switch (Op) {
893 default:
894 llvm_unreachable("Unhandled atomic op");
897 LaneOffset = buildMul(B, V, Mbcnt);
898 break;
907 LaneOffset = B.CreateSelect(Cond, Identity, V);
908 break;
910 LaneOffset = buildMul(B, V, B.CreateAnd(Mbcnt, 1));
911 break;
913 case AtomicRMWInst::FSub: {
914 LaneOffset = B.CreateFMul(V, Mbcnt);
915 break;
916 }
917 }
918 }
919 Value *Result = buildNonAtomicBinOp(B, Op, BroadcastI, LaneOffset);
920 if (isAtomicFloatingPointTy) {
921 // For fadd/fsub the first active lane of LaneOffset should be the
922 // identity (-0.0 for fadd or +0.0 for fsub) but the value we calculated
923 // is V * +0.0 which might have the wrong sign or might be nan (if V is
924 // inf or nan).
925 //
926 // For all floating point ops if the in-memory value was a nan then the
927 // binop we just built might have quieted it or changed its payload.
928 //
929 // Correct all these problems by using BroadcastI as the result in the
930 // first active lane.
931 Result = B.CreateSelect(Cond, BroadcastI, Result);
932 }
933
934 if (IsPixelShader) {
935 // Need a final PHI to reconverge to above the helper lane branch mask.
936 B.SetInsertPoint(PixelExitBB->getFirstNonPHIIt());
937
938 PHINode *const PHI = B.CreatePHI(Ty, 2);
939 PHI->addIncoming(PoisonValue::get(Ty), PixelEntryBB);
940 PHI->addIncoming(Result, I.getParent());
941 I.replaceAllUsesWith(PHI);
942 } else {
943 // Replace the original atomic instruction with the new one.
944 I.replaceAllUsesWith(Result);
945 }
946 }
947
948 // And delete the original.
949 I.eraseFromParent();
950}
951
952INITIALIZE_PASS_BEGIN(AMDGPUAtomicOptimizer, DEBUG_TYPE,
953 "AMDGPU atomic optimizations", false, false)
956INITIALIZE_PASS_END(AMDGPUAtomicOptimizer, DEBUG_TYPE,
957 "AMDGPU atomic optimizations", false, false)
958
960 return new AMDGPUAtomicOptimizer(ScanStrategy);
961}
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static Constant * getIdentityValueForAtomicOp(Type *const Ty, AtomicRMWInst::BinOp Op)
static bool isLegalCrossLaneType(Type *Ty)
static Value * buildMul(IRBuilder<> &B, Value *LHS, Value *RHS)
static Value * buildNonAtomicBinOp(IRBuilder<> &B, AtomicRMWInst::BinOp Op, Value *LHS, Value *RHS)
static Intrinsic::ID getWaveReductionIntrinsic(AtomicRMWInst::BinOp Op)
Contains the definition of a TargetInstrInfo class that is common to all AMD GPUs.
Rewrite undef for PHI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool runOnFunction(Function &F, bool PostInlining)
AMD GCN specific subclass of TargetSubtarget.
#define DEBUG_TYPE
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
Machine Check Debug Module
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
SmallVector< MachineOperand, 4 > Cond
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
Target-Independent Code Generator Pass Configuration Options pass.
LLVM IR instance of the generic uniformity analysis.
Value * RHS
Value * LHS
bool isSingleLaneExecution(const Function &Kernel) const
Return true if only a single workitem can be active in a wave.
unsigned getWavefrontSize() const
static APFloat getNaN(const fltSemantics &Sem, bool Negative=false, uint64_t payload=0)
Factory for NaN values.
Definition APFloat.h:1213
static APFloat getZero(const fltSemantics &Sem, bool Negative=false)
Factory for Positive and Negative Zero.
Definition APFloat.h:1183
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition APInt.h:202
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition APInt.h:205
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition APInt.h:212
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition APInt.h:215
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
an instruction that atomically reads a memory location, combines it with another value,...
static bool isFPOperation(BinOp Op)
BinOp
This enumeration lists the possible modifications atomicrmw can make.
@ Add
*p = old + v
@ FAdd
*p = old + v
@ Min
*p = old <signed v ? old : v
@ Sub
*p = old - v
@ And
*p = old & v
@ Xor
*p = old ^ v
@ FSub
*p = old - v
@ Max
*p = old >signed v ? old : v
@ UMin
*p = old <unsigned v ? old : v
@ FMin
*p = minnum(old, v) minnum matches the behavior of llvm.minnum.
@ UMax
*p = old >unsigned v ? old : v
@ FMax
*p = maxnum(old, v) maxnum matches the behavior of llvm.maxnum.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition BasicBlock.h:206
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
@ ICMP_SLT
signed less than
Definition InstrTypes.h:769
@ ICMP_UGT
unsigned greater than
Definition InstrTypes.h:763
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:767
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:765
This is the shared class of boolean and integer constants.
Definition Constants.h:87
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition Constants.h:225
This is an important base class in LLVM.
Definition Constant.h:44
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
Legacy analysis pass which computes a DominatorTree.
Definition Dominators.h:277
DominatorTree & getDomTree()
Definition Dominators.h:285
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
const SITargetLowering * getTargetLowering() const override
bool isWave32() const
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
bool isDivergentAtUse(const UseT &U) const
Whether U is divergent at its use.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
Base class for instruction visitors.
Definition InstVisitor.h:78
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:76
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:133
AtomicExpansionKind shouldExpandAtomicRMWInIR(const AtomicRMWInst *) const override
Returns how the IR-level AtomicExpand pass should expand the given AtomicRMW, if at all.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Primary interface to the complete machine description for the target machine.
const STC & getSubtarget(const Function &F) const
This method returns a pointer to the specified type of TargetSubtargetInfo.
Target-Independent Code Generator Pass Configuration Options.
TMC & getTM() const
Get the right type of TargetMachine for this target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
@ FloatTyID
32-bit floating point type
Definition Type.h:59
@ IntegerTyID
Arbitrary bit width integers.
Definition Type.h:71
@ DoubleTyID
64-bit floating point type
Definition Type.h:60
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition Type.h:186
Analysis pass which computes UniformityInfo.
Legacy analysis pass which computes a CycleInfo.
void setOperand(unsigned i, Value *Val)
Definition User.h:212
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ LOCAL_ADDRESS
Address space for local memory.
@ GLOBAL_ADDRESS
Address space for global memory (RAT0, VTX0).
const BufferIntrinsicInfo * lookupBufferIntrinsic(unsigned Intr)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ AMDGPU_PS
Used for Mesa/AMDPAL pixel shaders.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > OverloadTys={})
Look up the Function declaration of the intrinsic id in the Module M.
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)
Extract a Value from Metadata.
Definition Metadata.h:680
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
GenericUniformityInfo< SSAContext > UniformityInfo
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
DWARFExpression::Operation Op
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
char & AMDGPUAtomicOptimizerID
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
FunctionPass * createAMDGPUAtomicOptimizerPass(AMDGPU::ScanOptions ScanStrategy)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
std::optional< unsigned > getAuxArg() const
The auxiliary (cache policy) argument.
std::optional< unsigned > getVDataArg() const
The stored value for stores and atomics.