xref: /llvm-project/llvm/lib/Target/AMDGPU/AMDGPUCodeGenPrepare.cpp (revision 14359ef1b6a0610ac91df5f5a91c88a0b51c187c)
1 //===-- AMDGPUCodeGenPrepare.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 does misc. AMDGPU optimizations on IR before instruction
11 /// selection.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "AMDGPU.h"
16 #include "AMDGPUSubtarget.h"
17 #include "AMDGPUTargetMachine.h"
18 #include "llvm/ADT/StringRef.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
21 #include "llvm/Analysis/Loads.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/CodeGen/TargetPassConfig.h"
25 #include "llvm/IR/Attributes.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstVisitor.h"
32 #include "llvm/IR/InstrTypes.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Intrinsics.h"
37 #include "llvm/IR/LLVMContext.h"
38 #include "llvm/IR/Operator.h"
39 #include "llvm/IR/Type.h"
40 #include "llvm/IR/Value.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/Casting.h"
43 #include <cassert>
44 #include <iterator>
45 
46 #define DEBUG_TYPE "amdgpu-codegenprepare"
47 
48 using namespace llvm;
49 
50 namespace {
51 
52 static cl::opt<bool> WidenLoads(
53   "amdgpu-codegenprepare-widen-constant-loads",
54   cl::desc("Widen sub-dword constant address space loads in AMDGPUCodeGenPrepare"),
55   cl::ReallyHidden,
56   cl::init(true));
57 
58 class AMDGPUCodeGenPrepare : public FunctionPass,
59                              public InstVisitor<AMDGPUCodeGenPrepare, bool> {
60   const GCNSubtarget *ST = nullptr;
61   AssumptionCache *AC = nullptr;
62   LegacyDivergenceAnalysis *DA = nullptr;
63   Module *Mod = nullptr;
64   bool HasUnsafeFPMath = false;
65 
66   /// Copies exact/nsw/nuw flags (if any) from binary operation \p I to
67   /// binary operation \p V.
68   ///
69   /// \returns Binary operation \p V.
70   /// \returns \p T's base element bit width.
71   unsigned getBaseElementBitWidth(const Type *T) const;
72 
73   /// \returns Equivalent 32 bit integer type for given type \p T. For example,
74   /// if \p T is i7, then i32 is returned; if \p T is <3 x i12>, then <3 x i32>
75   /// is returned.
76   Type *getI32Ty(IRBuilder<> &B, const Type *T) const;
77 
78   /// \returns True if binary operation \p I is a signed binary operation, false
79   /// otherwise.
80   bool isSigned(const BinaryOperator &I) const;
81 
82   /// \returns True if the condition of 'select' operation \p I comes from a
83   /// signed 'icmp' operation, false otherwise.
84   bool isSigned(const SelectInst &I) const;
85 
86   /// \returns True if type \p T needs to be promoted to 32 bit integer type,
87   /// false otherwise.
88   bool needsPromotionToI32(const Type *T) const;
89 
90   /// Promotes uniform binary operation \p I to equivalent 32 bit binary
91   /// operation.
92   ///
93   /// \details \p I's base element bit width must be greater than 1 and less
94   /// than or equal 16. Promotion is done by sign or zero extending operands to
95   /// 32 bits, replacing \p I with equivalent 32 bit binary operation, and
96   /// truncating the result of 32 bit binary operation back to \p I's original
97   /// type. Division operation is not promoted.
98   ///
99   /// \returns True if \p I is promoted to equivalent 32 bit binary operation,
100   /// false otherwise.
101   bool promoteUniformOpToI32(BinaryOperator &I) const;
102 
103   /// Promotes uniform 'icmp' operation \p I to 32 bit 'icmp' operation.
104   ///
105   /// \details \p I's base element bit width must be greater than 1 and less
106   /// than or equal 16. Promotion is done by sign or zero extending operands to
107   /// 32 bits, and replacing \p I with 32 bit 'icmp' operation.
108   ///
109   /// \returns True.
110   bool promoteUniformOpToI32(ICmpInst &I) const;
111 
112   /// Promotes uniform 'select' operation \p I to 32 bit 'select'
113   /// operation.
114   ///
115   /// \details \p I's base element bit width must be greater than 1 and less
116   /// than or equal 16. Promotion is done by sign or zero extending operands to
117   /// 32 bits, replacing \p I with 32 bit 'select' operation, and truncating the
118   /// result of 32 bit 'select' operation back to \p I's original type.
119   ///
120   /// \returns True.
121   bool promoteUniformOpToI32(SelectInst &I) const;
122 
123   /// Promotes uniform 'bitreverse' intrinsic \p I to 32 bit 'bitreverse'
124   /// intrinsic.
125   ///
126   /// \details \p I's base element bit width must be greater than 1 and less
127   /// than or equal 16. Promotion is done by zero extending the operand to 32
128   /// bits, replacing \p I with 32 bit 'bitreverse' intrinsic, shifting the
129   /// result of 32 bit 'bitreverse' intrinsic to the right with zero fill (the
130   /// shift amount is 32 minus \p I's base element bit width), and truncating
131   /// the result of the shift operation back to \p I's original type.
132   ///
133   /// \returns True.
134   bool promoteUniformBitreverseToI32(IntrinsicInst &I) const;
135 
136   /// Expands 24 bit div or rem.
137   Value* expandDivRem24(IRBuilder<> &Builder, BinaryOperator &I,
138                         Value *Num, Value *Den,
139                         bool IsDiv, bool IsSigned) const;
140 
141   /// Expands 32 bit div or rem.
142   Value* expandDivRem32(IRBuilder<> &Builder, BinaryOperator &I,
143                         Value *Num, Value *Den) const;
144 
145   /// Widen a scalar load.
146   ///
147   /// \details \p Widen scalar load for uniform, small type loads from constant
148   //  memory / to a full 32-bits and then truncate the input to allow a scalar
149   //  load instead of a vector load.
150   //
151   /// \returns True.
152 
153   bool canWidenScalarExtLoad(LoadInst &I) const;
154 
155 public:
156   static char ID;
157 
158   AMDGPUCodeGenPrepare() : FunctionPass(ID) {}
159 
160   bool visitFDiv(BinaryOperator &I);
161 
162   bool visitInstruction(Instruction &I) { return false; }
163   bool visitBinaryOperator(BinaryOperator &I);
164   bool visitLoadInst(LoadInst &I);
165   bool visitICmpInst(ICmpInst &I);
166   bool visitSelectInst(SelectInst &I);
167 
168   bool visitIntrinsicInst(IntrinsicInst &I);
169   bool visitBitreverseIntrinsicInst(IntrinsicInst &I);
170 
171   bool doInitialization(Module &M) override;
172   bool runOnFunction(Function &F) override;
173 
174   StringRef getPassName() const override { return "AMDGPU IR optimizations"; }
175 
176   void getAnalysisUsage(AnalysisUsage &AU) const override {
177     AU.addRequired<AssumptionCacheTracker>();
178     AU.addRequired<LegacyDivergenceAnalysis>();
179     AU.setPreservesAll();
180  }
181 };
182 
183 } // end anonymous namespace
184 
185 unsigned AMDGPUCodeGenPrepare::getBaseElementBitWidth(const Type *T) const {
186   assert(needsPromotionToI32(T) && "T does not need promotion to i32");
187 
188   if (T->isIntegerTy())
189     return T->getIntegerBitWidth();
190   return cast<VectorType>(T)->getElementType()->getIntegerBitWidth();
191 }
192 
193 Type *AMDGPUCodeGenPrepare::getI32Ty(IRBuilder<> &B, const Type *T) const {
194   assert(needsPromotionToI32(T) && "T does not need promotion to i32");
195 
196   if (T->isIntegerTy())
197     return B.getInt32Ty();
198   return VectorType::get(B.getInt32Ty(), cast<VectorType>(T)->getNumElements());
199 }
200 
201 bool AMDGPUCodeGenPrepare::isSigned(const BinaryOperator &I) const {
202   return I.getOpcode() == Instruction::AShr ||
203       I.getOpcode() == Instruction::SDiv || I.getOpcode() == Instruction::SRem;
204 }
205 
206 bool AMDGPUCodeGenPrepare::isSigned(const SelectInst &I) const {
207   return isa<ICmpInst>(I.getOperand(0)) ?
208       cast<ICmpInst>(I.getOperand(0))->isSigned() : false;
209 }
210 
211 bool AMDGPUCodeGenPrepare::needsPromotionToI32(const Type *T) const {
212   const IntegerType *IntTy = dyn_cast<IntegerType>(T);
213   if (IntTy && IntTy->getBitWidth() > 1 && IntTy->getBitWidth() <= 16)
214     return true;
215 
216   if (const VectorType *VT = dyn_cast<VectorType>(T)) {
217     // TODO: The set of packed operations is more limited, so may want to
218     // promote some anyway.
219     if (ST->hasVOP3PInsts())
220       return false;
221 
222     return needsPromotionToI32(VT->getElementType());
223   }
224 
225   return false;
226 }
227 
228 // Return true if the op promoted to i32 should have nsw set.
229 static bool promotedOpIsNSW(const Instruction &I) {
230   switch (I.getOpcode()) {
231   case Instruction::Shl:
232   case Instruction::Add:
233   case Instruction::Sub:
234     return true;
235   case Instruction::Mul:
236     return I.hasNoUnsignedWrap();
237   default:
238     return false;
239   }
240 }
241 
242 // Return true if the op promoted to i32 should have nuw set.
243 static bool promotedOpIsNUW(const Instruction &I) {
244   switch (I.getOpcode()) {
245   case Instruction::Shl:
246   case Instruction::Add:
247   case Instruction::Mul:
248     return true;
249   case Instruction::Sub:
250     return I.hasNoUnsignedWrap();
251   default:
252     return false;
253   }
254 }
255 
256 bool AMDGPUCodeGenPrepare::canWidenScalarExtLoad(LoadInst &I) const {
257   Type *Ty = I.getType();
258   const DataLayout &DL = Mod->getDataLayout();
259   int TySize = DL.getTypeSizeInBits(Ty);
260   unsigned Align = I.getAlignment() ?
261                    I.getAlignment() : DL.getABITypeAlignment(Ty);
262 
263   return I.isSimple() && TySize < 32 && Align >= 4 && DA->isUniform(&I);
264 }
265 
266 bool AMDGPUCodeGenPrepare::promoteUniformOpToI32(BinaryOperator &I) const {
267   assert(needsPromotionToI32(I.getType()) &&
268          "I does not need promotion to i32");
269 
270   if (I.getOpcode() == Instruction::SDiv ||
271       I.getOpcode() == Instruction::UDiv ||
272       I.getOpcode() == Instruction::SRem ||
273       I.getOpcode() == Instruction::URem)
274     return false;
275 
276   IRBuilder<> Builder(&I);
277   Builder.SetCurrentDebugLocation(I.getDebugLoc());
278 
279   Type *I32Ty = getI32Ty(Builder, I.getType());
280   Value *ExtOp0 = nullptr;
281   Value *ExtOp1 = nullptr;
282   Value *ExtRes = nullptr;
283   Value *TruncRes = nullptr;
284 
285   if (isSigned(I)) {
286     ExtOp0 = Builder.CreateSExt(I.getOperand(0), I32Ty);
287     ExtOp1 = Builder.CreateSExt(I.getOperand(1), I32Ty);
288   } else {
289     ExtOp0 = Builder.CreateZExt(I.getOperand(0), I32Ty);
290     ExtOp1 = Builder.CreateZExt(I.getOperand(1), I32Ty);
291   }
292 
293   ExtRes = Builder.CreateBinOp(I.getOpcode(), ExtOp0, ExtOp1);
294   if (Instruction *Inst = dyn_cast<Instruction>(ExtRes)) {
295     if (promotedOpIsNSW(cast<Instruction>(I)))
296       Inst->setHasNoSignedWrap();
297 
298     if (promotedOpIsNUW(cast<Instruction>(I)))
299       Inst->setHasNoUnsignedWrap();
300 
301     if (const auto *ExactOp = dyn_cast<PossiblyExactOperator>(&I))
302       Inst->setIsExact(ExactOp->isExact());
303   }
304 
305   TruncRes = Builder.CreateTrunc(ExtRes, I.getType());
306 
307   I.replaceAllUsesWith(TruncRes);
308   I.eraseFromParent();
309 
310   return true;
311 }
312 
313 bool AMDGPUCodeGenPrepare::promoteUniformOpToI32(ICmpInst &I) const {
314   assert(needsPromotionToI32(I.getOperand(0)->getType()) &&
315          "I does not need promotion to i32");
316 
317   IRBuilder<> Builder(&I);
318   Builder.SetCurrentDebugLocation(I.getDebugLoc());
319 
320   Type *I32Ty = getI32Ty(Builder, I.getOperand(0)->getType());
321   Value *ExtOp0 = nullptr;
322   Value *ExtOp1 = nullptr;
323   Value *NewICmp  = nullptr;
324 
325   if (I.isSigned()) {
326     ExtOp0 = Builder.CreateSExt(I.getOperand(0), I32Ty);
327     ExtOp1 = Builder.CreateSExt(I.getOperand(1), I32Ty);
328   } else {
329     ExtOp0 = Builder.CreateZExt(I.getOperand(0), I32Ty);
330     ExtOp1 = Builder.CreateZExt(I.getOperand(1), I32Ty);
331   }
332   NewICmp = Builder.CreateICmp(I.getPredicate(), ExtOp0, ExtOp1);
333 
334   I.replaceAllUsesWith(NewICmp);
335   I.eraseFromParent();
336 
337   return true;
338 }
339 
340 bool AMDGPUCodeGenPrepare::promoteUniformOpToI32(SelectInst &I) const {
341   assert(needsPromotionToI32(I.getType()) &&
342          "I does not need promotion to i32");
343 
344   IRBuilder<> Builder(&I);
345   Builder.SetCurrentDebugLocation(I.getDebugLoc());
346 
347   Type *I32Ty = getI32Ty(Builder, I.getType());
348   Value *ExtOp1 = nullptr;
349   Value *ExtOp2 = nullptr;
350   Value *ExtRes = nullptr;
351   Value *TruncRes = nullptr;
352 
353   if (isSigned(I)) {
354     ExtOp1 = Builder.CreateSExt(I.getOperand(1), I32Ty);
355     ExtOp2 = Builder.CreateSExt(I.getOperand(2), I32Ty);
356   } else {
357     ExtOp1 = Builder.CreateZExt(I.getOperand(1), I32Ty);
358     ExtOp2 = Builder.CreateZExt(I.getOperand(2), I32Ty);
359   }
360   ExtRes = Builder.CreateSelect(I.getOperand(0), ExtOp1, ExtOp2);
361   TruncRes = Builder.CreateTrunc(ExtRes, I.getType());
362 
363   I.replaceAllUsesWith(TruncRes);
364   I.eraseFromParent();
365 
366   return true;
367 }
368 
369 bool AMDGPUCodeGenPrepare::promoteUniformBitreverseToI32(
370     IntrinsicInst &I) const {
371   assert(I.getIntrinsicID() == Intrinsic::bitreverse &&
372          "I must be bitreverse intrinsic");
373   assert(needsPromotionToI32(I.getType()) &&
374          "I does not need promotion to i32");
375 
376   IRBuilder<> Builder(&I);
377   Builder.SetCurrentDebugLocation(I.getDebugLoc());
378 
379   Type *I32Ty = getI32Ty(Builder, I.getType());
380   Function *I32 =
381       Intrinsic::getDeclaration(Mod, Intrinsic::bitreverse, { I32Ty });
382   Value *ExtOp = Builder.CreateZExt(I.getOperand(0), I32Ty);
383   Value *ExtRes = Builder.CreateCall(I32, { ExtOp });
384   Value *LShrOp =
385       Builder.CreateLShr(ExtRes, 32 - getBaseElementBitWidth(I.getType()));
386   Value *TruncRes =
387       Builder.CreateTrunc(LShrOp, I.getType());
388 
389   I.replaceAllUsesWith(TruncRes);
390   I.eraseFromParent();
391 
392   return true;
393 }
394 
395 static bool shouldKeepFDivF32(Value *Num, bool UnsafeDiv, bool HasDenormals) {
396   const ConstantFP *CNum = dyn_cast<ConstantFP>(Num);
397   if (!CNum)
398     return HasDenormals;
399 
400   if (UnsafeDiv)
401     return true;
402 
403   bool IsOne = CNum->isExactlyValue(+1.0) || CNum->isExactlyValue(-1.0);
404 
405   // Reciprocal f32 is handled separately without denormals.
406   return HasDenormals ^ IsOne;
407 }
408 
409 // Insert an intrinsic for fast fdiv for safe math situations where we can
410 // reduce precision. Leave fdiv for situations where the generic node is
411 // expected to be optimized.
412 bool AMDGPUCodeGenPrepare::visitFDiv(BinaryOperator &FDiv) {
413   Type *Ty = FDiv.getType();
414 
415   if (!Ty->getScalarType()->isFloatTy())
416     return false;
417 
418   MDNode *FPMath = FDiv.getMetadata(LLVMContext::MD_fpmath);
419   if (!FPMath)
420     return false;
421 
422   const FPMathOperator *FPOp = cast<const FPMathOperator>(&FDiv);
423   float ULP = FPOp->getFPAccuracy();
424   if (ULP < 2.5f)
425     return false;
426 
427   FastMathFlags FMF = FPOp->getFastMathFlags();
428   bool UnsafeDiv = HasUnsafeFPMath || FMF.isFast() ||
429                                       FMF.allowReciprocal();
430 
431   // With UnsafeDiv node will be optimized to just rcp and mul.
432   if (UnsafeDiv)
433     return false;
434 
435   IRBuilder<> Builder(FDiv.getParent(), std::next(FDiv.getIterator()), FPMath);
436   Builder.setFastMathFlags(FMF);
437   Builder.SetCurrentDebugLocation(FDiv.getDebugLoc());
438 
439   Function *Decl = Intrinsic::getDeclaration(Mod, Intrinsic::amdgcn_fdiv_fast);
440 
441   Value *Num = FDiv.getOperand(0);
442   Value *Den = FDiv.getOperand(1);
443 
444   Value *NewFDiv = nullptr;
445 
446   bool HasDenormals = ST->hasFP32Denormals();
447   if (VectorType *VT = dyn_cast<VectorType>(Ty)) {
448     NewFDiv = UndefValue::get(VT);
449 
450     // FIXME: Doesn't do the right thing for cases where the vector is partially
451     // constant. This works when the scalarizer pass is run first.
452     for (unsigned I = 0, E = VT->getNumElements(); I != E; ++I) {
453       Value *NumEltI = Builder.CreateExtractElement(Num, I);
454       Value *DenEltI = Builder.CreateExtractElement(Den, I);
455       Value *NewElt;
456 
457       if (shouldKeepFDivF32(NumEltI, UnsafeDiv, HasDenormals)) {
458         NewElt = Builder.CreateFDiv(NumEltI, DenEltI);
459       } else {
460         NewElt = Builder.CreateCall(Decl, { NumEltI, DenEltI });
461       }
462 
463       NewFDiv = Builder.CreateInsertElement(NewFDiv, NewElt, I);
464     }
465   } else {
466     if (!shouldKeepFDivF32(Num, UnsafeDiv, HasDenormals))
467       NewFDiv = Builder.CreateCall(Decl, { Num, Den });
468   }
469 
470   if (NewFDiv) {
471     FDiv.replaceAllUsesWith(NewFDiv);
472     NewFDiv->takeName(&FDiv);
473     FDiv.eraseFromParent();
474   }
475 
476   return !!NewFDiv;
477 }
478 
479 static bool hasUnsafeFPMath(const Function &F) {
480   Attribute Attr = F.getFnAttribute("unsafe-fp-math");
481   return Attr.getValueAsString() == "true";
482 }
483 
484 static std::pair<Value*, Value*> getMul64(IRBuilder<> &Builder,
485                                           Value *LHS, Value *RHS) {
486   Type *I32Ty = Builder.getInt32Ty();
487   Type *I64Ty = Builder.getInt64Ty();
488 
489   Value *LHS_EXT64 = Builder.CreateZExt(LHS, I64Ty);
490   Value *RHS_EXT64 = Builder.CreateZExt(RHS, I64Ty);
491   Value *MUL64 = Builder.CreateMul(LHS_EXT64, RHS_EXT64);
492   Value *Lo = Builder.CreateTrunc(MUL64, I32Ty);
493   Value *Hi = Builder.CreateLShr(MUL64, Builder.getInt64(32));
494   Hi = Builder.CreateTrunc(Hi, I32Ty);
495   return std::make_pair(Lo, Hi);
496 }
497 
498 static Value* getMulHu(IRBuilder<> &Builder, Value *LHS, Value *RHS) {
499   return getMul64(Builder, LHS, RHS).second;
500 }
501 
502 // The fractional part of a float is enough to accurately represent up to
503 // a 24-bit signed integer.
504 Value* AMDGPUCodeGenPrepare::expandDivRem24(IRBuilder<> &Builder,
505                                             BinaryOperator &I,
506                                             Value *Num, Value *Den,
507                                             bool IsDiv, bool IsSigned) const {
508   assert(Num->getType()->isIntegerTy(32));
509 
510   const DataLayout &DL = Mod->getDataLayout();
511   unsigned LHSSignBits = ComputeNumSignBits(Num, DL, 0, AC, &I);
512   if (LHSSignBits < 9)
513     return nullptr;
514 
515   unsigned RHSSignBits = ComputeNumSignBits(Den, DL, 0, AC, &I);
516   if (RHSSignBits < 9)
517     return nullptr;
518 
519 
520   unsigned SignBits = std::min(LHSSignBits, RHSSignBits);
521   unsigned DivBits = 32 - SignBits;
522   if (IsSigned)
523     ++DivBits;
524 
525   Type *Ty = Num->getType();
526   Type *I32Ty = Builder.getInt32Ty();
527   Type *F32Ty = Builder.getFloatTy();
528   ConstantInt *One = Builder.getInt32(1);
529   Value *JQ = One;
530 
531   if (IsSigned) {
532     // char|short jq = ia ^ ib;
533     JQ = Builder.CreateXor(Num, Den);
534 
535     // jq = jq >> (bitsize - 2)
536     JQ = Builder.CreateAShr(JQ, Builder.getInt32(30));
537 
538     // jq = jq | 0x1
539     JQ = Builder.CreateOr(JQ, One);
540   }
541 
542   // int ia = (int)LHS;
543   Value *IA = Num;
544 
545   // int ib, (int)RHS;
546   Value *IB = Den;
547 
548   // float fa = (float)ia;
549   Value *FA = IsSigned ? Builder.CreateSIToFP(IA, F32Ty)
550                        : Builder.CreateUIToFP(IA, F32Ty);
551 
552   // float fb = (float)ib;
553   Value *FB = IsSigned ? Builder.CreateSIToFP(IB,F32Ty)
554                        : Builder.CreateUIToFP(IB,F32Ty);
555 
556   Value *RCP = Builder.CreateFDiv(ConstantFP::get(F32Ty, 1.0), FB);
557   Value *FQM = Builder.CreateFMul(FA, RCP);
558 
559   // fq = trunc(fqm);
560   CallInst *FQ = Builder.CreateUnaryIntrinsic(Intrinsic::trunc, FQM);
561   FQ->copyFastMathFlags(Builder.getFastMathFlags());
562 
563   // float fqneg = -fq;
564   Value *FQNeg = Builder.CreateFNeg(FQ);
565 
566   // float fr = mad(fqneg, fb, fa);
567   Value *FR = Builder.CreateIntrinsic(Intrinsic::amdgcn_fmad_ftz,
568                                       {FQNeg->getType()}, {FQNeg, FB, FA}, FQ);
569 
570   // int iq = (int)fq;
571   Value *IQ = IsSigned ? Builder.CreateFPToSI(FQ, I32Ty)
572                        : Builder.CreateFPToUI(FQ, I32Ty);
573 
574   // fr = fabs(fr);
575   FR = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FR, FQ);
576 
577   // fb = fabs(fb);
578   FB = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FB, FQ);
579 
580   // int cv = fr >= fb;
581   Value *CV = Builder.CreateFCmpOGE(FR, FB);
582 
583   // jq = (cv ? jq : 0);
584   JQ = Builder.CreateSelect(CV, JQ, Builder.getInt32(0));
585 
586   // dst = iq + jq;
587   Value *Div = Builder.CreateAdd(IQ, JQ);
588 
589   Value *Res = Div;
590   if (!IsDiv) {
591     // Rem needs compensation, it's easier to recompute it
592     Value *Rem = Builder.CreateMul(Div, Den);
593     Res = Builder.CreateSub(Num, Rem);
594   }
595 
596   // Truncate to number of bits this divide really is.
597   if (IsSigned) {
598     Res = Builder.CreateTrunc(Res, Builder.getIntNTy(DivBits));
599     Res = Builder.CreateSExt(Res, Ty);
600   } else {
601     ConstantInt *TruncMask = Builder.getInt32((UINT64_C(1) << DivBits) - 1);
602     Res = Builder.CreateAnd(Res, TruncMask);
603   }
604 
605   return Res;
606 }
607 
608 Value* AMDGPUCodeGenPrepare::expandDivRem32(IRBuilder<> &Builder,
609                                             BinaryOperator &I,
610                                             Value *Num, Value *Den) const {
611   Instruction::BinaryOps Opc = I.getOpcode();
612   assert(Opc == Instruction::URem || Opc == Instruction::UDiv ||
613          Opc == Instruction::SRem || Opc == Instruction::SDiv);
614 
615   FastMathFlags FMF;
616   FMF.setFast();
617   Builder.setFastMathFlags(FMF);
618 
619   if (isa<Constant>(Den))
620     return nullptr; // Keep it for optimization
621 
622   bool IsDiv = Opc == Instruction::UDiv || Opc == Instruction::SDiv;
623   bool IsSigned = Opc == Instruction::SRem || Opc == Instruction::SDiv;
624 
625   Type *Ty = Num->getType();
626   Type *I32Ty = Builder.getInt32Ty();
627   Type *F32Ty = Builder.getFloatTy();
628 
629   if (Ty->getScalarSizeInBits() < 32) {
630     if (IsSigned) {
631       Num = Builder.CreateSExt(Num, I32Ty);
632       Den = Builder.CreateSExt(Den, I32Ty);
633     } else {
634       Num = Builder.CreateZExt(Num, I32Ty);
635       Den = Builder.CreateZExt(Den, I32Ty);
636     }
637   }
638 
639   if (Value *Res = expandDivRem24(Builder, I, Num, Den, IsDiv, IsSigned)) {
640     Res = Builder.CreateTrunc(Res, Ty);
641     return Res;
642   }
643 
644   ConstantInt *Zero = Builder.getInt32(0);
645   ConstantInt *One = Builder.getInt32(1);
646   ConstantInt *MinusOne = Builder.getInt32(~0);
647 
648   Value *Sign = nullptr;
649   if (IsSigned) {
650     ConstantInt *K31 = Builder.getInt32(31);
651     Value *LHSign = Builder.CreateAShr(Num, K31);
652     Value *RHSign = Builder.CreateAShr(Den, K31);
653     // Remainder sign is the same as LHS
654     Sign = IsDiv ? Builder.CreateXor(LHSign, RHSign) : LHSign;
655 
656     Num = Builder.CreateAdd(Num, LHSign);
657     Den = Builder.CreateAdd(Den, RHSign);
658 
659     Num = Builder.CreateXor(Num, LHSign);
660     Den = Builder.CreateXor(Den, RHSign);
661   }
662 
663   // RCP =  URECIP(Den) = 2^32 / Den + e
664   // e is rounding error.
665   Value *DEN_F32 = Builder.CreateUIToFP(Den, F32Ty);
666   Value *RCP_F32 = Builder.CreateFDiv(ConstantFP::get(F32Ty, 1.0), DEN_F32);
667   Constant *UINT_MAX_PLUS_1 = ConstantFP::get(F32Ty, BitsToFloat(0x4f800000));
668   Value *RCP_SCALE = Builder.CreateFMul(RCP_F32, UINT_MAX_PLUS_1);
669   Value *RCP = Builder.CreateFPToUI(RCP_SCALE, I32Ty);
670 
671   // RCP_LO, RCP_HI = mul(RCP, Den) */
672   Value *RCP_LO, *RCP_HI;
673   std::tie(RCP_LO, RCP_HI) = getMul64(Builder, RCP, Den);
674 
675   // NEG_RCP_LO = -RCP_LO
676   Value *NEG_RCP_LO = Builder.CreateNeg(RCP_LO);
677 
678   // ABS_RCP_LO = (RCP_HI == 0 ? NEG_RCP_LO : RCP_LO)
679   Value *RCP_HI_0_CC = Builder.CreateICmpEQ(RCP_HI, Zero);
680   Value *ABS_RCP_LO = Builder.CreateSelect(RCP_HI_0_CC, NEG_RCP_LO, RCP_LO);
681 
682   // Calculate the rounding error from the URECIP instruction
683   // E = mulhu(ABS_RCP_LO, RCP)
684   Value *E = getMulHu(Builder, ABS_RCP_LO, RCP);
685 
686   // RCP_A_E = RCP + E
687   Value *RCP_A_E = Builder.CreateAdd(RCP, E);
688 
689   // RCP_S_E = RCP - E
690   Value *RCP_S_E = Builder.CreateSub(RCP, E);
691 
692   // Tmp0 = (RCP_HI == 0 ? RCP_A_E : RCP_SUB_E)
693   Value *Tmp0 = Builder.CreateSelect(RCP_HI_0_CC, RCP_A_E, RCP_S_E);
694 
695   // Quotient = mulhu(Tmp0, Num)
696   Value *Quotient = getMulHu(Builder, Tmp0, Num);
697 
698   // Num_S_Remainder = Quotient * Den
699   Value *Num_S_Remainder = Builder.CreateMul(Quotient, Den);
700 
701   // Remainder = Num - Num_S_Remainder
702   Value *Remainder = Builder.CreateSub(Num, Num_S_Remainder);
703 
704   // Remainder_GE_Den = (Remainder >= Den ? -1 : 0)
705   Value *Rem_GE_Den_CC = Builder.CreateICmpUGE(Remainder, Den);
706   Value *Remainder_GE_Den = Builder.CreateSelect(Rem_GE_Den_CC, MinusOne, Zero);
707 
708   // Remainder_GE_Zero = (Num >= Num_S_Remainder ? -1 : 0)
709   Value *Num_GE_Num_S_Rem_CC = Builder.CreateICmpUGE(Num, Num_S_Remainder);
710   Value *Remainder_GE_Zero = Builder.CreateSelect(Num_GE_Num_S_Rem_CC,
711                                                   MinusOne, Zero);
712 
713   // Tmp1 = Remainder_GE_Den & Remainder_GE_Zero
714   Value *Tmp1 = Builder.CreateAnd(Remainder_GE_Den, Remainder_GE_Zero);
715   Value *Tmp1_0_CC = Builder.CreateICmpEQ(Tmp1, Zero);
716 
717   Value *Res;
718   if (IsDiv) {
719     // Quotient_A_One = Quotient + 1
720     Value *Quotient_A_One = Builder.CreateAdd(Quotient, One);
721 
722     // Quotient_S_One = Quotient - 1
723     Value *Quotient_S_One = Builder.CreateSub(Quotient, One);
724 
725     // Div = (Tmp1 == 0 ? Quotient : Quotient_A_One)
726     Value *Div = Builder.CreateSelect(Tmp1_0_CC, Quotient, Quotient_A_One);
727 
728     // Div = (Remainder_GE_Zero == 0 ? Quotient_S_One : Div)
729     Res = Builder.CreateSelect(Num_GE_Num_S_Rem_CC, Div, Quotient_S_One);
730   } else {
731     // Remainder_S_Den = Remainder - Den
732     Value *Remainder_S_Den = Builder.CreateSub(Remainder, Den);
733 
734     // Remainder_A_Den = Remainder + Den
735     Value *Remainder_A_Den = Builder.CreateAdd(Remainder, Den);
736 
737     // Rem = (Tmp1 == 0 ? Remainder : Remainder_S_Den)
738     Value *Rem = Builder.CreateSelect(Tmp1_0_CC, Remainder, Remainder_S_Den);
739 
740     // Rem = (Remainder_GE_Zero == 0 ? Remainder_A_Den : Rem)
741     Res = Builder.CreateSelect(Num_GE_Num_S_Rem_CC, Rem, Remainder_A_Den);
742   }
743 
744   if (IsSigned) {
745     Res = Builder.CreateXor(Res, Sign);
746     Res = Builder.CreateSub(Res, Sign);
747   }
748 
749   Res = Builder.CreateTrunc(Res, Ty);
750 
751   return Res;
752 }
753 
754 bool AMDGPUCodeGenPrepare::visitBinaryOperator(BinaryOperator &I) {
755   if (ST->has16BitInsts() && needsPromotionToI32(I.getType()) &&
756       DA->isUniform(&I) && promoteUniformOpToI32(I))
757     return true;
758 
759   bool Changed = false;
760   Instruction::BinaryOps Opc = I.getOpcode();
761   Type *Ty = I.getType();
762   Value *NewDiv = nullptr;
763   if ((Opc == Instruction::URem || Opc == Instruction::UDiv ||
764        Opc == Instruction::SRem || Opc == Instruction::SDiv) &&
765       Ty->getScalarSizeInBits() <= 32) {
766     Value *Num = I.getOperand(0);
767     Value *Den = I.getOperand(1);
768     IRBuilder<> Builder(&I);
769     Builder.SetCurrentDebugLocation(I.getDebugLoc());
770 
771     if (VectorType *VT = dyn_cast<VectorType>(Ty)) {
772       NewDiv = UndefValue::get(VT);
773 
774       for (unsigned N = 0, E = VT->getNumElements(); N != E; ++N) {
775         Value *NumEltN = Builder.CreateExtractElement(Num, N);
776         Value *DenEltN = Builder.CreateExtractElement(Den, N);
777         Value *NewElt = expandDivRem32(Builder, I, NumEltN, DenEltN);
778         if (!NewElt)
779           NewElt = Builder.CreateBinOp(Opc, NumEltN, DenEltN);
780         NewDiv = Builder.CreateInsertElement(NewDiv, NewElt, N);
781       }
782     } else {
783       NewDiv = expandDivRem32(Builder, I, Num, Den);
784     }
785 
786     if (NewDiv) {
787       I.replaceAllUsesWith(NewDiv);
788       I.eraseFromParent();
789       Changed = true;
790     }
791   }
792 
793   return Changed;
794 }
795 
796 bool AMDGPUCodeGenPrepare::visitLoadInst(LoadInst &I) {
797   if (!WidenLoads)
798     return false;
799 
800   if ((I.getPointerAddressSpace() == AMDGPUAS::CONSTANT_ADDRESS ||
801        I.getPointerAddressSpace() == AMDGPUAS::CONSTANT_ADDRESS_32BIT) &&
802       canWidenScalarExtLoad(I)) {
803     IRBuilder<> Builder(&I);
804     Builder.SetCurrentDebugLocation(I.getDebugLoc());
805 
806     Type *I32Ty = Builder.getInt32Ty();
807     Type *PT = PointerType::get(I32Ty, I.getPointerAddressSpace());
808     Value *BitCast= Builder.CreateBitCast(I.getPointerOperand(), PT);
809     LoadInst *WidenLoad = Builder.CreateLoad(I32Ty, BitCast);
810     WidenLoad->copyMetadata(I);
811 
812     // If we have range metadata, we need to convert the type, and not make
813     // assumptions about the high bits.
814     if (auto *Range = WidenLoad->getMetadata(LLVMContext::MD_range)) {
815       ConstantInt *Lower =
816         mdconst::extract<ConstantInt>(Range->getOperand(0));
817 
818       if (Lower->getValue().isNullValue()) {
819         WidenLoad->setMetadata(LLVMContext::MD_range, nullptr);
820       } else {
821         Metadata *LowAndHigh[] = {
822           ConstantAsMetadata::get(ConstantInt::get(I32Ty, Lower->getValue().zext(32))),
823           // Don't make assumptions about the high bits.
824           ConstantAsMetadata::get(ConstantInt::get(I32Ty, 0))
825         };
826 
827         WidenLoad->setMetadata(LLVMContext::MD_range,
828                                MDNode::get(Mod->getContext(), LowAndHigh));
829       }
830     }
831 
832     int TySize = Mod->getDataLayout().getTypeSizeInBits(I.getType());
833     Type *IntNTy = Builder.getIntNTy(TySize);
834     Value *ValTrunc = Builder.CreateTrunc(WidenLoad, IntNTy);
835     Value *ValOrig = Builder.CreateBitCast(ValTrunc, I.getType());
836     I.replaceAllUsesWith(ValOrig);
837     I.eraseFromParent();
838     return true;
839   }
840 
841   return false;
842 }
843 
844 bool AMDGPUCodeGenPrepare::visitICmpInst(ICmpInst &I) {
845   bool Changed = false;
846 
847   if (ST->has16BitInsts() && needsPromotionToI32(I.getOperand(0)->getType()) &&
848       DA->isUniform(&I))
849     Changed |= promoteUniformOpToI32(I);
850 
851   return Changed;
852 }
853 
854 bool AMDGPUCodeGenPrepare::visitSelectInst(SelectInst &I) {
855   bool Changed = false;
856 
857   if (ST->has16BitInsts() && needsPromotionToI32(I.getType()) &&
858       DA->isUniform(&I))
859     Changed |= promoteUniformOpToI32(I);
860 
861   return Changed;
862 }
863 
864 bool AMDGPUCodeGenPrepare::visitIntrinsicInst(IntrinsicInst &I) {
865   switch (I.getIntrinsicID()) {
866   case Intrinsic::bitreverse:
867     return visitBitreverseIntrinsicInst(I);
868   default:
869     return false;
870   }
871 }
872 
873 bool AMDGPUCodeGenPrepare::visitBitreverseIntrinsicInst(IntrinsicInst &I) {
874   bool Changed = false;
875 
876   if (ST->has16BitInsts() && needsPromotionToI32(I.getType()) &&
877       DA->isUniform(&I))
878     Changed |= promoteUniformBitreverseToI32(I);
879 
880   return Changed;
881 }
882 
883 bool AMDGPUCodeGenPrepare::doInitialization(Module &M) {
884   Mod = &M;
885   return false;
886 }
887 
888 bool AMDGPUCodeGenPrepare::runOnFunction(Function &F) {
889   if (skipFunction(F))
890     return false;
891 
892   auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
893   if (!TPC)
894     return false;
895 
896   const AMDGPUTargetMachine &TM = TPC->getTM<AMDGPUTargetMachine>();
897   ST = &TM.getSubtarget<GCNSubtarget>(F);
898   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
899   DA = &getAnalysis<LegacyDivergenceAnalysis>();
900   HasUnsafeFPMath = hasUnsafeFPMath(F);
901 
902   bool MadeChange = false;
903 
904   for (BasicBlock &BB : F) {
905     BasicBlock::iterator Next;
906     for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; I = Next) {
907       Next = std::next(I);
908       MadeChange |= visit(*I);
909     }
910   }
911 
912   return MadeChange;
913 }
914 
915 INITIALIZE_PASS_BEGIN(AMDGPUCodeGenPrepare, DEBUG_TYPE,
916                       "AMDGPU IR optimizations", false, false)
917 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
918 INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
919 INITIALIZE_PASS_END(AMDGPUCodeGenPrepare, DEBUG_TYPE, "AMDGPU IR optimizations",
920                     false, false)
921 
922 char AMDGPUCodeGenPrepare::ID = 0;
923 
924 FunctionPass *llvm::createAMDGPUCodeGenPreparePass() {
925   return new AMDGPUCodeGenPrepare();
926 }
927