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 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "AMDGPU.h"
17 #include "GCNSubtarget.h"
18 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
19 #include "llvm/CodeGen/TargetPassConfig.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/InstVisitor.h"
22 #include "llvm/IR/IntrinsicsAMDGPU.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
26 
27 #define DEBUG_TYPE "amdgpu-atomic-optimizer"
28 
29 using namespace llvm;
30 using namespace llvm::AMDGPU;
31 
32 namespace {
33 
34 struct ReplacementInfo {
35   Instruction *I;
36   AtomicRMWInst::BinOp Op;
37   unsigned ValIdx;
38   bool ValDivergent;
39 };
40 
41 class AMDGPUAtomicOptimizer : public FunctionPass,
42                               public InstVisitor<AMDGPUAtomicOptimizer> {
43 private:
44   SmallVector<ReplacementInfo, 8> ToReplace;
45   const LegacyDivergenceAnalysis *DA;
46   const DataLayout *DL;
47   DominatorTree *DT;
48   const GCNSubtarget *ST;
49   bool IsPixelShader;
50 
51   Value *buildReduction(IRBuilder<> &B, AtomicRMWInst::BinOp Op, Value *V,
52                         Value *const Identity) const;
53   Value *buildScan(IRBuilder<> &B, AtomicRMWInst::BinOp Op, Value *V,
54                    Value *const Identity) const;
55   Value *buildShiftRight(IRBuilder<> &B, Value *V, Value *const Identity) const;
56   void optimizeAtomic(Instruction &I, AtomicRMWInst::BinOp Op, unsigned ValIdx,
57                       bool ValDivergent) const;
58 
59 public:
60   static char ID;
61 
AMDGPUAtomicOptimizer()62   AMDGPUAtomicOptimizer() : FunctionPass(ID) {}
63 
64   bool runOnFunction(Function &F) override;
65 
getAnalysisUsage(AnalysisUsage & AU) const66   void getAnalysisUsage(AnalysisUsage &AU) const override {
67     AU.addPreserved<DominatorTreeWrapperPass>();
68     AU.addRequired<LegacyDivergenceAnalysis>();
69     AU.addRequired<TargetPassConfig>();
70   }
71 
72   void visitAtomicRMWInst(AtomicRMWInst &I);
73   void visitIntrinsicInst(IntrinsicInst &I);
74 };
75 
76 } // namespace
77 
78 char AMDGPUAtomicOptimizer::ID = 0;
79 
80 char &llvm::AMDGPUAtomicOptimizerID = AMDGPUAtomicOptimizer::ID;
81 
runOnFunction(Function & F)82 bool AMDGPUAtomicOptimizer::runOnFunction(Function &F) {
83   if (skipFunction(F)) {
84     return false;
85   }
86 
87   DA = &getAnalysis<LegacyDivergenceAnalysis>();
88   DL = &F.getParent()->getDataLayout();
89   DominatorTreeWrapperPass *const DTW =
90       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
91   DT = DTW ? &DTW->getDomTree() : nullptr;
92   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
93   const TargetMachine &TM = TPC.getTM<TargetMachine>();
94   ST = &TM.getSubtarget<GCNSubtarget>(F);
95   IsPixelShader = F.getCallingConv() == CallingConv::AMDGPU_PS;
96 
97   visit(F);
98 
99   const bool Changed = !ToReplace.empty();
100 
101   for (ReplacementInfo &Info : ToReplace) {
102     optimizeAtomic(*Info.I, Info.Op, Info.ValIdx, Info.ValDivergent);
103   }
104 
105   ToReplace.clear();
106 
107   return Changed;
108 }
109 
visitAtomicRMWInst(AtomicRMWInst & I)110 void AMDGPUAtomicOptimizer::visitAtomicRMWInst(AtomicRMWInst &I) {
111   // Early exit for unhandled address space atomic instructions.
112   switch (I.getPointerAddressSpace()) {
113   default:
114     return;
115   case AMDGPUAS::GLOBAL_ADDRESS:
116   case AMDGPUAS::LOCAL_ADDRESS:
117     break;
118   }
119 
120   AtomicRMWInst::BinOp Op = I.getOperation();
121 
122   switch (Op) {
123   default:
124     return;
125   case AtomicRMWInst::Add:
126   case AtomicRMWInst::Sub:
127   case AtomicRMWInst::And:
128   case AtomicRMWInst::Or:
129   case AtomicRMWInst::Xor:
130   case AtomicRMWInst::Max:
131   case AtomicRMWInst::Min:
132   case AtomicRMWInst::UMax:
133   case AtomicRMWInst::UMin:
134     break;
135   }
136 
137   const unsigned PtrIdx = 0;
138   const unsigned ValIdx = 1;
139 
140   // If the pointer operand is divergent, then each lane is doing an atomic
141   // operation on a different address, and we cannot optimize that.
142   if (DA->isDivergentUse(&I.getOperandUse(PtrIdx))) {
143     return;
144   }
145 
146   const bool ValDivergent = DA->isDivergentUse(&I.getOperandUse(ValIdx));
147 
148   // If the value operand is divergent, each lane is contributing a different
149   // value to the atomic calculation. We can only optimize divergent values if
150   // we have DPP available on our subtarget, and the atomic operation is 32
151   // bits.
152   if (ValDivergent &&
153       (!ST->hasDPP() || DL->getTypeSizeInBits(I.getType()) != 32)) {
154     return;
155   }
156 
157   // If we get here, we can optimize the atomic using a single wavefront-wide
158   // atomic operation to do the calculation for the entire wavefront, so
159   // remember the instruction so we can come back to it.
160   const ReplacementInfo Info = {&I, Op, ValIdx, ValDivergent};
161 
162   ToReplace.push_back(Info);
163 }
164 
visitIntrinsicInst(IntrinsicInst & I)165 void AMDGPUAtomicOptimizer::visitIntrinsicInst(IntrinsicInst &I) {
166   AtomicRMWInst::BinOp Op;
167 
168   switch (I.getIntrinsicID()) {
169   default:
170     return;
171   case Intrinsic::amdgcn_buffer_atomic_add:
172   case Intrinsic::amdgcn_struct_buffer_atomic_add:
173   case Intrinsic::amdgcn_raw_buffer_atomic_add:
174     Op = AtomicRMWInst::Add;
175     break;
176   case Intrinsic::amdgcn_buffer_atomic_sub:
177   case Intrinsic::amdgcn_struct_buffer_atomic_sub:
178   case Intrinsic::amdgcn_raw_buffer_atomic_sub:
179     Op = AtomicRMWInst::Sub;
180     break;
181   case Intrinsic::amdgcn_buffer_atomic_and:
182   case Intrinsic::amdgcn_struct_buffer_atomic_and:
183   case Intrinsic::amdgcn_raw_buffer_atomic_and:
184     Op = AtomicRMWInst::And;
185     break;
186   case Intrinsic::amdgcn_buffer_atomic_or:
187   case Intrinsic::amdgcn_struct_buffer_atomic_or:
188   case Intrinsic::amdgcn_raw_buffer_atomic_or:
189     Op = AtomicRMWInst::Or;
190     break;
191   case Intrinsic::amdgcn_buffer_atomic_xor:
192   case Intrinsic::amdgcn_struct_buffer_atomic_xor:
193   case Intrinsic::amdgcn_raw_buffer_atomic_xor:
194     Op = AtomicRMWInst::Xor;
195     break;
196   case Intrinsic::amdgcn_buffer_atomic_smin:
197   case Intrinsic::amdgcn_struct_buffer_atomic_smin:
198   case Intrinsic::amdgcn_raw_buffer_atomic_smin:
199     Op = AtomicRMWInst::Min;
200     break;
201   case Intrinsic::amdgcn_buffer_atomic_umin:
202   case Intrinsic::amdgcn_struct_buffer_atomic_umin:
203   case Intrinsic::amdgcn_raw_buffer_atomic_umin:
204     Op = AtomicRMWInst::UMin;
205     break;
206   case Intrinsic::amdgcn_buffer_atomic_smax:
207   case Intrinsic::amdgcn_struct_buffer_atomic_smax:
208   case Intrinsic::amdgcn_raw_buffer_atomic_smax:
209     Op = AtomicRMWInst::Max;
210     break;
211   case Intrinsic::amdgcn_buffer_atomic_umax:
212   case Intrinsic::amdgcn_struct_buffer_atomic_umax:
213   case Intrinsic::amdgcn_raw_buffer_atomic_umax:
214     Op = AtomicRMWInst::UMax;
215     break;
216   }
217 
218   const unsigned ValIdx = 0;
219 
220   const bool ValDivergent = DA->isDivergentUse(&I.getOperandUse(ValIdx));
221 
222   // If the value operand is divergent, each lane is contributing a different
223   // value to the atomic calculation. We can only optimize divergent values if
224   // we have DPP available on our subtarget, and the atomic operation is 32
225   // bits.
226   if (ValDivergent &&
227       (!ST->hasDPP() || DL->getTypeSizeInBits(I.getType()) != 32)) {
228     return;
229   }
230 
231   // If any of the other arguments to the intrinsic are divergent, we can't
232   // optimize the operation.
233   for (unsigned Idx = 1; Idx < I.getNumOperands(); Idx++) {
234     if (DA->isDivergentUse(&I.getOperandUse(Idx))) {
235       return;
236     }
237   }
238 
239   // If we get here, we can optimize the atomic using a single wavefront-wide
240   // atomic operation to do the calculation for the entire wavefront, so
241   // remember the instruction so we can come back to it.
242   const ReplacementInfo Info = {&I, Op, ValIdx, ValDivergent};
243 
244   ToReplace.push_back(Info);
245 }
246 
247 // Use the builder to create the non-atomic counterpart of the specified
248 // atomicrmw binary op.
buildNonAtomicBinOp(IRBuilder<> & B,AtomicRMWInst::BinOp Op,Value * LHS,Value * RHS)249 static Value *buildNonAtomicBinOp(IRBuilder<> &B, AtomicRMWInst::BinOp Op,
250                                   Value *LHS, Value *RHS) {
251   CmpInst::Predicate Pred;
252 
253   switch (Op) {
254   default:
255     llvm_unreachable("Unhandled atomic op");
256   case AtomicRMWInst::Add:
257     return B.CreateBinOp(Instruction::Add, LHS, RHS);
258   case AtomicRMWInst::Sub:
259     return B.CreateBinOp(Instruction::Sub, LHS, RHS);
260   case AtomicRMWInst::And:
261     return B.CreateBinOp(Instruction::And, LHS, RHS);
262   case AtomicRMWInst::Or:
263     return B.CreateBinOp(Instruction::Or, LHS, RHS);
264   case AtomicRMWInst::Xor:
265     return B.CreateBinOp(Instruction::Xor, LHS, RHS);
266 
267   case AtomicRMWInst::Max:
268     Pred = CmpInst::ICMP_SGT;
269     break;
270   case AtomicRMWInst::Min:
271     Pred = CmpInst::ICMP_SLT;
272     break;
273   case AtomicRMWInst::UMax:
274     Pred = CmpInst::ICMP_UGT;
275     break;
276   case AtomicRMWInst::UMin:
277     Pred = CmpInst::ICMP_ULT;
278     break;
279   }
280   Value *Cond = B.CreateICmp(Pred, LHS, RHS);
281   return B.CreateSelect(Cond, LHS, RHS);
282 }
283 
284 // Use the builder to create a reduction of V across the wavefront, with all
285 // lanes active, returning the same result in all lanes.
buildReduction(IRBuilder<> & B,AtomicRMWInst::BinOp Op,Value * V,Value * const Identity) const286 Value *AMDGPUAtomicOptimizer::buildReduction(IRBuilder<> &B,
287                                              AtomicRMWInst::BinOp Op, Value *V,
288                                              Value *const Identity) const {
289   Type *const Ty = V->getType();
290   Module *M = B.GetInsertBlock()->getModule();
291   Function *UpdateDPP =
292       Intrinsic::getDeclaration(M, Intrinsic::amdgcn_update_dpp, Ty);
293 
294   // Reduce within each row of 16 lanes.
295   for (unsigned Idx = 0; Idx < 4; Idx++) {
296     V = buildNonAtomicBinOp(
297         B, Op, V,
298         B.CreateCall(UpdateDPP,
299                      {Identity, V, B.getInt32(DPP::ROW_XMASK0 | 1 << Idx),
300                       B.getInt32(0xf), B.getInt32(0xf), B.getFalse()}));
301   }
302 
303   // Reduce within each pair of rows (i.e. 32 lanes).
304   assert(ST->hasPermLaneX16());
305   V = buildNonAtomicBinOp(
306       B, Op, V,
307       B.CreateIntrinsic(
308           Intrinsic::amdgcn_permlanex16, {},
309           {V, V, B.getInt32(-1), B.getInt32(-1), B.getFalse(), B.getFalse()}));
310 
311   if (ST->isWave32())
312     return V;
313 
314   // Pick an arbitrary lane from 0..31 and an arbitrary lane from 32..63 and
315   // combine them with a scalar operation.
316   Function *ReadLane =
317       Intrinsic::getDeclaration(M, Intrinsic::amdgcn_readlane, {});
318   Value *const Lane0 = B.CreateCall(ReadLane, {V, B.getInt32(0)});
319   Value *const Lane32 = B.CreateCall(ReadLane, {V, B.getInt32(32)});
320   return buildNonAtomicBinOp(B, Op, Lane0, Lane32);
321 }
322 
323 // Use the builder to create an inclusive scan of V across the wavefront, with
324 // all lanes active.
buildScan(IRBuilder<> & B,AtomicRMWInst::BinOp Op,Value * V,Value * const Identity) const325 Value *AMDGPUAtomicOptimizer::buildScan(IRBuilder<> &B, AtomicRMWInst::BinOp Op,
326                                         Value *V, Value *const Identity) const {
327   Type *const Ty = V->getType();
328   Module *M = B.GetInsertBlock()->getModule();
329   Function *UpdateDPP =
330       Intrinsic::getDeclaration(M, Intrinsic::amdgcn_update_dpp, Ty);
331 
332   for (unsigned Idx = 0; Idx < 4; Idx++) {
333     V = buildNonAtomicBinOp(
334         B, Op, V,
335         B.CreateCall(UpdateDPP,
336                      {Identity, V, B.getInt32(DPP::ROW_SHR0 | 1 << Idx),
337                       B.getInt32(0xf), B.getInt32(0xf), B.getFalse()}));
338   }
339   if (ST->hasDPPBroadcasts()) {
340     // GFX9 has DPP row broadcast operations.
341     V = buildNonAtomicBinOp(
342         B, Op, V,
343         B.CreateCall(UpdateDPP,
344                      {Identity, V, B.getInt32(DPP::BCAST15), B.getInt32(0xa),
345                       B.getInt32(0xf), B.getFalse()}));
346     V = buildNonAtomicBinOp(
347         B, Op, V,
348         B.CreateCall(UpdateDPP,
349                      {Identity, V, B.getInt32(DPP::BCAST31), B.getInt32(0xc),
350                       B.getInt32(0xf), B.getFalse()}));
351   } else {
352     // On GFX10 all DPP operations are confined to a single row. To get cross-
353     // row operations we have to use permlane or readlane.
354 
355     // Combine lane 15 into lanes 16..31 (and, for wave 64, lane 47 into lanes
356     // 48..63).
357     assert(ST->hasPermLaneX16());
358     Value *const PermX = B.CreateIntrinsic(
359         Intrinsic::amdgcn_permlanex16, {},
360         {V, V, B.getInt32(-1), B.getInt32(-1), B.getFalse(), B.getFalse()});
361     V = buildNonAtomicBinOp(
362         B, Op, V,
363         B.CreateCall(UpdateDPP,
364                      {Identity, PermX, B.getInt32(DPP::QUAD_PERM_ID),
365                       B.getInt32(0xa), B.getInt32(0xf), B.getFalse()}));
366     if (!ST->isWave32()) {
367       // Combine lane 31 into lanes 32..63.
368       Value *const Lane31 = B.CreateIntrinsic(Intrinsic::amdgcn_readlane, {},
369                                               {V, B.getInt32(31)});
370       V = buildNonAtomicBinOp(
371           B, Op, V,
372           B.CreateCall(UpdateDPP,
373                        {Identity, Lane31, B.getInt32(DPP::QUAD_PERM_ID),
374                         B.getInt32(0xc), B.getInt32(0xf), B.getFalse()}));
375     }
376   }
377   return V;
378 }
379 
380 // Use the builder to create a shift right of V across the wavefront, with all
381 // lanes active, to turn an inclusive scan into an exclusive scan.
buildShiftRight(IRBuilder<> & B,Value * V,Value * const Identity) const382 Value *AMDGPUAtomicOptimizer::buildShiftRight(IRBuilder<> &B, Value *V,
383                                               Value *const Identity) const {
384   Type *const Ty = V->getType();
385   Module *M = B.GetInsertBlock()->getModule();
386   Function *UpdateDPP =
387       Intrinsic::getDeclaration(M, Intrinsic::amdgcn_update_dpp, Ty);
388 
389   if (ST->hasDPPWavefrontShifts()) {
390     // GFX9 has DPP wavefront shift operations.
391     V = B.CreateCall(UpdateDPP,
392                      {Identity, V, B.getInt32(DPP::WAVE_SHR1), B.getInt32(0xf),
393                       B.getInt32(0xf), B.getFalse()});
394   } else {
395     Function *ReadLane =
396         Intrinsic::getDeclaration(M, Intrinsic::amdgcn_readlane, {});
397     Function *WriteLane =
398         Intrinsic::getDeclaration(M, Intrinsic::amdgcn_writelane, {});
399 
400     // On GFX10 all DPP operations are confined to a single row. To get cross-
401     // row operations we have to use permlane or readlane.
402     Value *Old = V;
403     V = B.CreateCall(UpdateDPP,
404                      {Identity, V, B.getInt32(DPP::ROW_SHR0 + 1),
405                       B.getInt32(0xf), B.getInt32(0xf), B.getFalse()});
406 
407     // Copy the old lane 15 to the new lane 16.
408     V = B.CreateCall(WriteLane, {B.CreateCall(ReadLane, {Old, B.getInt32(15)}),
409                                  B.getInt32(16), V});
410 
411     if (!ST->isWave32()) {
412       // Copy the old lane 31 to the new lane 32.
413       V = B.CreateCall(
414           WriteLane,
415           {B.CreateCall(ReadLane, {Old, B.getInt32(31)}), B.getInt32(32), V});
416 
417       // Copy the old lane 47 to the new lane 48.
418       V = B.CreateCall(
419           WriteLane,
420           {B.CreateCall(ReadLane, {Old, B.getInt32(47)}), B.getInt32(48), V});
421     }
422   }
423 
424   return V;
425 }
426 
getIdentityValueForAtomicOp(AtomicRMWInst::BinOp Op,unsigned BitWidth)427 static APInt getIdentityValueForAtomicOp(AtomicRMWInst::BinOp Op,
428                                          unsigned BitWidth) {
429   switch (Op) {
430   default:
431     llvm_unreachable("Unhandled atomic op");
432   case AtomicRMWInst::Add:
433   case AtomicRMWInst::Sub:
434   case AtomicRMWInst::Or:
435   case AtomicRMWInst::Xor:
436   case AtomicRMWInst::UMax:
437     return APInt::getMinValue(BitWidth);
438   case AtomicRMWInst::And:
439   case AtomicRMWInst::UMin:
440     return APInt::getMaxValue(BitWidth);
441   case AtomicRMWInst::Max:
442     return APInt::getSignedMinValue(BitWidth);
443   case AtomicRMWInst::Min:
444     return APInt::getSignedMaxValue(BitWidth);
445   }
446 }
447 
buildMul(IRBuilder<> & B,Value * LHS,Value * RHS)448 static Value *buildMul(IRBuilder<> &B, Value *LHS, Value *RHS) {
449   const ConstantInt *CI = dyn_cast<ConstantInt>(LHS);
450   return (CI && CI->isOne()) ? RHS : B.CreateMul(LHS, RHS);
451 }
452 
optimizeAtomic(Instruction & I,AtomicRMWInst::BinOp Op,unsigned ValIdx,bool ValDivergent) const453 void AMDGPUAtomicOptimizer::optimizeAtomic(Instruction &I,
454                                            AtomicRMWInst::BinOp Op,
455                                            unsigned ValIdx,
456                                            bool ValDivergent) const {
457   // Start building just before the instruction.
458   IRBuilder<> B(&I);
459 
460   // If we are in a pixel shader, because of how we have to mask out helper
461   // lane invocations, we need to record the entry and exit BB's.
462   BasicBlock *PixelEntryBB = nullptr;
463   BasicBlock *PixelExitBB = nullptr;
464 
465   // If we're optimizing an atomic within a pixel shader, we need to wrap the
466   // entire atomic operation in a helper-lane check. We do not want any helper
467   // lanes that are around only for the purposes of derivatives to take part
468   // in any cross-lane communication, and we use a branch on whether the lane is
469   // live to do this.
470   if (IsPixelShader) {
471     // Record I's original position as the entry block.
472     PixelEntryBB = I.getParent();
473 
474     Value *const Cond = B.CreateIntrinsic(Intrinsic::amdgcn_ps_live, {}, {});
475     Instruction *const NonHelperTerminator =
476         SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, DT, nullptr);
477 
478     // Record I's new position as the exit block.
479     PixelExitBB = I.getParent();
480 
481     I.moveBefore(NonHelperTerminator);
482     B.SetInsertPoint(&I);
483   }
484 
485   Type *const Ty = I.getType();
486   const unsigned TyBitWidth = DL->getTypeSizeInBits(Ty);
487   auto *const VecTy = FixedVectorType::get(B.getInt32Ty(), 2);
488 
489   // This is the value in the atomic operation we need to combine in order to
490   // reduce the number of atomic operations.
491   Value *const V = I.getOperand(ValIdx);
492 
493   // We need to know how many lanes are active within the wavefront, and we do
494   // this by doing a ballot of active lanes.
495   Type *const WaveTy = B.getIntNTy(ST->getWavefrontSize());
496   CallInst *const Ballot =
497       B.CreateIntrinsic(Intrinsic::amdgcn_ballot, WaveTy, B.getTrue());
498 
499   // We need to know how many lanes are active within the wavefront that are
500   // below us. If we counted each lane linearly starting from 0, a lane is
501   // below us only if its associated index was less than ours. We do this by
502   // using the mbcnt intrinsic.
503   Value *Mbcnt;
504   if (ST->isWave32()) {
505     Mbcnt = B.CreateIntrinsic(Intrinsic::amdgcn_mbcnt_lo, {},
506                               {Ballot, B.getInt32(0)});
507   } else {
508     Value *const BitCast = B.CreateBitCast(Ballot, VecTy);
509     Value *const ExtractLo = B.CreateExtractElement(BitCast, B.getInt32(0));
510     Value *const ExtractHi = B.CreateExtractElement(BitCast, B.getInt32(1));
511     Mbcnt = B.CreateIntrinsic(Intrinsic::amdgcn_mbcnt_lo, {},
512                               {ExtractLo, B.getInt32(0)});
513     Mbcnt =
514         B.CreateIntrinsic(Intrinsic::amdgcn_mbcnt_hi, {}, {ExtractHi, Mbcnt});
515   }
516   Mbcnt = B.CreateIntCast(Mbcnt, Ty, false);
517 
518   Value *const Identity = B.getInt(getIdentityValueForAtomicOp(Op, TyBitWidth));
519 
520   Value *ExclScan = nullptr;
521   Value *NewV = nullptr;
522 
523   const bool NeedResult = !I.use_empty();
524 
525   // If we have a divergent value in each lane, we need to combine the value
526   // using DPP.
527   if (ValDivergent) {
528     // First we need to set all inactive invocations to the identity value, so
529     // that they can correctly contribute to the final result.
530     NewV = B.CreateIntrinsic(Intrinsic::amdgcn_set_inactive, Ty, {V, Identity});
531 
532     const AtomicRMWInst::BinOp ScanOp =
533         Op == AtomicRMWInst::Sub ? AtomicRMWInst::Add : Op;
534     if (!NeedResult && ST->hasPermLaneX16()) {
535       // On GFX10 the permlanex16 instruction helps us build a reduction without
536       // too many readlanes and writelanes, which are generally bad for
537       // performance.
538       NewV = buildReduction(B, ScanOp, NewV, Identity);
539     } else {
540       NewV = buildScan(B, ScanOp, NewV, Identity);
541       if (NeedResult)
542         ExclScan = buildShiftRight(B, NewV, Identity);
543 
544       // Read the value from the last lane, which has accumlated the values of
545       // each active lane in the wavefront. This will be our new value which we
546       // will provide to the atomic operation.
547       Value *const LastLaneIdx = B.getInt32(ST->getWavefrontSize() - 1);
548       assert(TyBitWidth == 32);
549       NewV = B.CreateIntrinsic(Intrinsic::amdgcn_readlane, {},
550                                {NewV, LastLaneIdx});
551     }
552 
553     // Finally mark the readlanes in the WWM section.
554     NewV = B.CreateIntrinsic(Intrinsic::amdgcn_strict_wwm, Ty, NewV);
555   } else {
556     switch (Op) {
557     default:
558       llvm_unreachable("Unhandled atomic op");
559 
560     case AtomicRMWInst::Add:
561     case AtomicRMWInst::Sub: {
562       // The new value we will be contributing to the atomic operation is the
563       // old value times the number of active lanes.
564       Value *const Ctpop = B.CreateIntCast(
565           B.CreateUnaryIntrinsic(Intrinsic::ctpop, Ballot), Ty, false);
566       NewV = buildMul(B, V, Ctpop);
567       break;
568     }
569 
570     case AtomicRMWInst::And:
571     case AtomicRMWInst::Or:
572     case AtomicRMWInst::Max:
573     case AtomicRMWInst::Min:
574     case AtomicRMWInst::UMax:
575     case AtomicRMWInst::UMin:
576       // These operations with a uniform value are idempotent: doing the atomic
577       // operation multiple times has the same effect as doing it once.
578       NewV = V;
579       break;
580 
581     case AtomicRMWInst::Xor:
582       // The new value we will be contributing to the atomic operation is the
583       // old value times the parity of the number of active lanes.
584       Value *const Ctpop = B.CreateIntCast(
585           B.CreateUnaryIntrinsic(Intrinsic::ctpop, Ballot), Ty, false);
586       NewV = buildMul(B, V, B.CreateAnd(Ctpop, 1));
587       break;
588     }
589   }
590 
591   // We only want a single lane to enter our new control flow, and we do this
592   // by checking if there are any active lanes below us. Only one lane will
593   // have 0 active lanes below us, so that will be the only one to progress.
594   Value *const Cond = B.CreateICmpEQ(Mbcnt, B.getIntN(TyBitWidth, 0));
595 
596   // Store I's original basic block before we split the block.
597   BasicBlock *const EntryBB = I.getParent();
598 
599   // We need to introduce some new control flow to force a single lane to be
600   // active. We do this by splitting I's basic block at I, and introducing the
601   // new block such that:
602   // entry --> single_lane -\
603   //       \------------------> exit
604   Instruction *const SingleLaneTerminator =
605       SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, DT, nullptr);
606 
607   // Move the IR builder into single_lane next.
608   B.SetInsertPoint(SingleLaneTerminator);
609 
610   // Clone the original atomic operation into single lane, replacing the
611   // original value with our newly created one.
612   Instruction *const NewI = I.clone();
613   B.Insert(NewI);
614   NewI->setOperand(ValIdx, NewV);
615 
616   // Move the IR builder into exit next, and start inserting just before the
617   // original instruction.
618   B.SetInsertPoint(&I);
619 
620   if (NeedResult) {
621     // Create a PHI node to get our new atomic result into the exit block.
622     PHINode *const PHI = B.CreatePHI(Ty, 2);
623     PHI->addIncoming(UndefValue::get(Ty), EntryBB);
624     PHI->addIncoming(NewI, SingleLaneTerminator->getParent());
625 
626     // We need to broadcast the value who was the lowest active lane (the first
627     // lane) to all other lanes in the wavefront. We use an intrinsic for this,
628     // but have to handle 64-bit broadcasts with two calls to this intrinsic.
629     Value *BroadcastI = nullptr;
630 
631     if (TyBitWidth == 64) {
632       Value *const ExtractLo = B.CreateTrunc(PHI, B.getInt32Ty());
633       Value *const ExtractHi =
634           B.CreateTrunc(B.CreateLShr(PHI, 32), B.getInt32Ty());
635       CallInst *const ReadFirstLaneLo =
636           B.CreateIntrinsic(Intrinsic::amdgcn_readfirstlane, {}, ExtractLo);
637       CallInst *const ReadFirstLaneHi =
638           B.CreateIntrinsic(Intrinsic::amdgcn_readfirstlane, {}, ExtractHi);
639       Value *const PartialInsert = B.CreateInsertElement(
640           UndefValue::get(VecTy), ReadFirstLaneLo, B.getInt32(0));
641       Value *const Insert =
642           B.CreateInsertElement(PartialInsert, ReadFirstLaneHi, B.getInt32(1));
643       BroadcastI = B.CreateBitCast(Insert, Ty);
644     } else if (TyBitWidth == 32) {
645 
646       BroadcastI = B.CreateIntrinsic(Intrinsic::amdgcn_readfirstlane, {}, PHI);
647     } else {
648       llvm_unreachable("Unhandled atomic bit width");
649     }
650 
651     // Now that we have the result of our single atomic operation, we need to
652     // get our individual lane's slice into the result. We use the lane offset
653     // we previously calculated combined with the atomic result value we got
654     // from the first lane, to get our lane's index into the atomic result.
655     Value *LaneOffset = nullptr;
656     if (ValDivergent) {
657       LaneOffset =
658           B.CreateIntrinsic(Intrinsic::amdgcn_strict_wwm, Ty, ExclScan);
659     } else {
660       switch (Op) {
661       default:
662         llvm_unreachable("Unhandled atomic op");
663       case AtomicRMWInst::Add:
664       case AtomicRMWInst::Sub:
665         LaneOffset = buildMul(B, V, Mbcnt);
666         break;
667       case AtomicRMWInst::And:
668       case AtomicRMWInst::Or:
669       case AtomicRMWInst::Max:
670       case AtomicRMWInst::Min:
671       case AtomicRMWInst::UMax:
672       case AtomicRMWInst::UMin:
673         LaneOffset = B.CreateSelect(Cond, Identity, V);
674         break;
675       case AtomicRMWInst::Xor:
676         LaneOffset = buildMul(B, V, B.CreateAnd(Mbcnt, 1));
677         break;
678       }
679     }
680     Value *const Result = buildNonAtomicBinOp(B, Op, BroadcastI, LaneOffset);
681 
682     if (IsPixelShader) {
683       // Need a final PHI to reconverge to above the helper lane branch mask.
684       B.SetInsertPoint(PixelExitBB->getFirstNonPHI());
685 
686       PHINode *const PHI = B.CreatePHI(Ty, 2);
687       PHI->addIncoming(UndefValue::get(Ty), PixelEntryBB);
688       PHI->addIncoming(Result, I.getParent());
689       I.replaceAllUsesWith(PHI);
690     } else {
691       // Replace the original atomic instruction with the new one.
692       I.replaceAllUsesWith(Result);
693     }
694   }
695 
696   // And delete the original.
697   I.eraseFromParent();
698 }
699 
700 INITIALIZE_PASS_BEGIN(AMDGPUAtomicOptimizer, DEBUG_TYPE,
701                       "AMDGPU atomic optimizations", false, false)
INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)702 INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
703 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
704 INITIALIZE_PASS_END(AMDGPUAtomicOptimizer, DEBUG_TYPE,
705                     "AMDGPU atomic optimizations", false, false)
706 
707 FunctionPass *llvm::createAMDGPUAtomicOptimizerPass() {
708   return new AMDGPUAtomicOptimizer();
709 }
710