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/FloatingPointMode.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Analysis/AssumptionCache.h"
21 #include "llvm/Analysis/ConstantFolding.h"
22 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
23 #include "llvm/Analysis/Loads.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/CodeGen/Passes.h"
26 #include "llvm/CodeGen/TargetPassConfig.h"
27 #include "llvm/IR/Attributes.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/InstVisitor.h"
35 #include "llvm/IR/InstrTypes.h"
36 #include "llvm/IR/Instruction.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/IntrinsicInst.h"
39 #include "llvm/IR/Intrinsics.h"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/IR/Operator.h"
42 #include "llvm/IR/Type.h"
43 #include "llvm/IR/Value.h"
44 #include "llvm/InitializePasses.h"
45 #include "llvm/Pass.h"
46 #include "llvm/Support/Casting.h"
47 #include "llvm/Support/KnownBits.h"
48 #include "llvm/Transforms/Utils/IntegerDivision.h"
49 #include <cassert>
50 #include <iterator>
51
52 #define DEBUG_TYPE "amdgpu-codegenprepare"
53
54 using namespace llvm;
55
56 namespace {
57
58 static cl::opt<bool> WidenLoads(
59 "amdgpu-codegenprepare-widen-constant-loads",
60 cl::desc("Widen sub-dword constant address space loads in AMDGPUCodeGenPrepare"),
61 cl::ReallyHidden,
62 cl::init(false));
63
64 static cl::opt<bool> Widen16BitOps(
65 "amdgpu-codegenprepare-widen-16-bit-ops",
66 cl::desc("Widen uniform 16-bit instructions to 32-bit in AMDGPUCodeGenPrepare"),
67 cl::ReallyHidden,
68 cl::init(true));
69
70 static cl::opt<bool> UseMul24Intrin(
71 "amdgpu-codegenprepare-mul24",
72 cl::desc("Introduce mul24 intrinsics in AMDGPUCodeGenPrepare"),
73 cl::ReallyHidden,
74 cl::init(true));
75
76 // Legalize 64-bit division by using the generic IR expansion.
77 static cl::opt<bool> ExpandDiv64InIR(
78 "amdgpu-codegenprepare-expand-div64",
79 cl::desc("Expand 64-bit division in AMDGPUCodeGenPrepare"),
80 cl::ReallyHidden,
81 cl::init(false));
82
83 // Leave all division operations as they are. This supersedes ExpandDiv64InIR
84 // and is used for testing the legalizer.
85 static cl::opt<bool> DisableIDivExpand(
86 "amdgpu-codegenprepare-disable-idiv-expansion",
87 cl::desc("Prevent expanding integer division in AMDGPUCodeGenPrepare"),
88 cl::ReallyHidden,
89 cl::init(false));
90
91 class AMDGPUCodeGenPrepare : public FunctionPass,
92 public InstVisitor<AMDGPUCodeGenPrepare, bool> {
93 const GCNSubtarget *ST = nullptr;
94 AssumptionCache *AC = nullptr;
95 DominatorTree *DT = nullptr;
96 LegacyDivergenceAnalysis *DA = nullptr;
97 Module *Mod = nullptr;
98 const DataLayout *DL = nullptr;
99 bool HasUnsafeFPMath = false;
100 bool HasFP32Denormals = false;
101
102 /// Copies exact/nsw/nuw flags (if any) from binary operation \p I to
103 /// binary operation \p V.
104 ///
105 /// \returns Binary operation \p V.
106 /// \returns \p T's base element bit width.
107 unsigned getBaseElementBitWidth(const Type *T) const;
108
109 /// \returns Equivalent 32 bit integer type for given type \p T. For example,
110 /// if \p T is i7, then i32 is returned; if \p T is <3 x i12>, then <3 x i32>
111 /// is returned.
112 Type *getI32Ty(IRBuilder<> &B, const Type *T) const;
113
114 /// \returns True if binary operation \p I is a signed binary operation, false
115 /// otherwise.
116 bool isSigned(const BinaryOperator &I) const;
117
118 /// \returns True if the condition of 'select' operation \p I comes from a
119 /// signed 'icmp' operation, false otherwise.
120 bool isSigned(const SelectInst &I) const;
121
122 /// \returns True if type \p T needs to be promoted to 32 bit integer type,
123 /// false otherwise.
124 bool needsPromotionToI32(const Type *T) const;
125
126 /// Promotes uniform binary operation \p I to equivalent 32 bit binary
127 /// operation.
128 ///
129 /// \details \p I's base element bit width must be greater than 1 and less
130 /// than or equal 16. Promotion is done by sign or zero extending operands to
131 /// 32 bits, replacing \p I with equivalent 32 bit binary operation, and
132 /// truncating the result of 32 bit binary operation back to \p I's original
133 /// type. Division operation is not promoted.
134 ///
135 /// \returns True if \p I is promoted to equivalent 32 bit binary operation,
136 /// false otherwise.
137 bool promoteUniformOpToI32(BinaryOperator &I) const;
138
139 /// Promotes uniform 'icmp' operation \p I to 32 bit 'icmp' operation.
140 ///
141 /// \details \p I's base element bit width must be greater than 1 and less
142 /// than or equal 16. Promotion is done by sign or zero extending operands to
143 /// 32 bits, and replacing \p I with 32 bit 'icmp' operation.
144 ///
145 /// \returns True.
146 bool promoteUniformOpToI32(ICmpInst &I) const;
147
148 /// Promotes uniform 'select' operation \p I to 32 bit 'select'
149 /// operation.
150 ///
151 /// \details \p I's base element bit width must be greater than 1 and less
152 /// than or equal 16. Promotion is done by sign or zero extending operands to
153 /// 32 bits, replacing \p I with 32 bit 'select' operation, and truncating the
154 /// result of 32 bit 'select' operation back to \p I's original type.
155 ///
156 /// \returns True.
157 bool promoteUniformOpToI32(SelectInst &I) const;
158
159 /// Promotes uniform 'bitreverse' intrinsic \p I to 32 bit 'bitreverse'
160 /// intrinsic.
161 ///
162 /// \details \p I's base element bit width must be greater than 1 and less
163 /// than or equal 16. Promotion is done by zero extending the operand to 32
164 /// bits, replacing \p I with 32 bit 'bitreverse' intrinsic, shifting the
165 /// result of 32 bit 'bitreverse' intrinsic to the right with zero fill (the
166 /// shift amount is 32 minus \p I's base element bit width), and truncating
167 /// the result of the shift operation back to \p I's original type.
168 ///
169 /// \returns True.
170 bool promoteUniformBitreverseToI32(IntrinsicInst &I) const;
171
172
173 unsigned numBitsUnsigned(Value *Op, unsigned ScalarSize) const;
174 unsigned numBitsSigned(Value *Op, unsigned ScalarSize) const;
175 bool isI24(Value *V, unsigned ScalarSize) const;
176 bool isU24(Value *V, unsigned ScalarSize) const;
177
178 /// Replace mul instructions with llvm.amdgcn.mul.u24 or llvm.amdgcn.mul.s24.
179 /// SelectionDAG has an issue where an and asserting the bits are known
180 bool replaceMulWithMul24(BinaryOperator &I) const;
181
182 /// Perform same function as equivalently named function in DAGCombiner. Since
183 /// we expand some divisions here, we need to perform this before obscuring.
184 bool foldBinOpIntoSelect(BinaryOperator &I) const;
185
186 bool divHasSpecialOptimization(BinaryOperator &I,
187 Value *Num, Value *Den) const;
188 int getDivNumBits(BinaryOperator &I,
189 Value *Num, Value *Den,
190 unsigned AtLeast, bool Signed) const;
191
192 /// Expands 24 bit div or rem.
193 Value* expandDivRem24(IRBuilder<> &Builder, BinaryOperator &I,
194 Value *Num, Value *Den,
195 bool IsDiv, bool IsSigned) const;
196
197 Value *expandDivRem24Impl(IRBuilder<> &Builder, BinaryOperator &I,
198 Value *Num, Value *Den, unsigned NumBits,
199 bool IsDiv, bool IsSigned) const;
200
201 /// Expands 32 bit div or rem.
202 Value* expandDivRem32(IRBuilder<> &Builder, BinaryOperator &I,
203 Value *Num, Value *Den) const;
204
205 Value *shrinkDivRem64(IRBuilder<> &Builder, BinaryOperator &I,
206 Value *Num, Value *Den) const;
207 void expandDivRem64(BinaryOperator &I) const;
208
209 /// Widen a scalar load.
210 ///
211 /// \details \p Widen scalar load for uniform, small type loads from constant
212 // memory / to a full 32-bits and then truncate the input to allow a scalar
213 // load instead of a vector load.
214 //
215 /// \returns True.
216
217 bool canWidenScalarExtLoad(LoadInst &I) const;
218
219 public:
220 static char ID;
221
AMDGPUCodeGenPrepare()222 AMDGPUCodeGenPrepare() : FunctionPass(ID) {}
223
224 bool visitFDiv(BinaryOperator &I);
225
visitInstruction(Instruction & I)226 bool visitInstruction(Instruction &I) { return false; }
227 bool visitBinaryOperator(BinaryOperator &I);
228 bool visitLoadInst(LoadInst &I);
229 bool visitICmpInst(ICmpInst &I);
230 bool visitSelectInst(SelectInst &I);
231
232 bool visitIntrinsicInst(IntrinsicInst &I);
233 bool visitBitreverseIntrinsicInst(IntrinsicInst &I);
234
235 bool doInitialization(Module &M) override;
236 bool runOnFunction(Function &F) override;
237
getPassName() const238 StringRef getPassName() const override { return "AMDGPU IR optimizations"; }
239
getAnalysisUsage(AnalysisUsage & AU) const240 void getAnalysisUsage(AnalysisUsage &AU) const override {
241 AU.addRequired<AssumptionCacheTracker>();
242 AU.addRequired<LegacyDivergenceAnalysis>();
243
244 // FIXME: Division expansion needs to preserve the dominator tree.
245 if (!ExpandDiv64InIR)
246 AU.setPreservesAll();
247 }
248 };
249
250 } // end anonymous namespace
251
getBaseElementBitWidth(const Type * T) const252 unsigned AMDGPUCodeGenPrepare::getBaseElementBitWidth(const Type *T) const {
253 assert(needsPromotionToI32(T) && "T does not need promotion to i32");
254
255 if (T->isIntegerTy())
256 return T->getIntegerBitWidth();
257 return cast<VectorType>(T)->getElementType()->getIntegerBitWidth();
258 }
259
getI32Ty(IRBuilder<> & B,const Type * T) const260 Type *AMDGPUCodeGenPrepare::getI32Ty(IRBuilder<> &B, const Type *T) const {
261 assert(needsPromotionToI32(T) && "T does not need promotion to i32");
262
263 if (T->isIntegerTy())
264 return B.getInt32Ty();
265 return FixedVectorType::get(B.getInt32Ty(), cast<FixedVectorType>(T));
266 }
267
isSigned(const BinaryOperator & I) const268 bool AMDGPUCodeGenPrepare::isSigned(const BinaryOperator &I) const {
269 return I.getOpcode() == Instruction::AShr ||
270 I.getOpcode() == Instruction::SDiv || I.getOpcode() == Instruction::SRem;
271 }
272
isSigned(const SelectInst & I) const273 bool AMDGPUCodeGenPrepare::isSigned(const SelectInst &I) const {
274 return isa<ICmpInst>(I.getOperand(0)) ?
275 cast<ICmpInst>(I.getOperand(0))->isSigned() : false;
276 }
277
needsPromotionToI32(const Type * T) const278 bool AMDGPUCodeGenPrepare::needsPromotionToI32(const Type *T) const {
279 if (!Widen16BitOps)
280 return false;
281
282 const IntegerType *IntTy = dyn_cast<IntegerType>(T);
283 if (IntTy && IntTy->getBitWidth() > 1 && IntTy->getBitWidth() <= 16)
284 return true;
285
286 if (const VectorType *VT = dyn_cast<VectorType>(T)) {
287 // TODO: The set of packed operations is more limited, so may want to
288 // promote some anyway.
289 if (ST->hasVOP3PInsts())
290 return false;
291
292 return needsPromotionToI32(VT->getElementType());
293 }
294
295 return false;
296 }
297
298 // Return true if the op promoted to i32 should have nsw set.
promotedOpIsNSW(const Instruction & I)299 static bool promotedOpIsNSW(const Instruction &I) {
300 switch (I.getOpcode()) {
301 case Instruction::Shl:
302 case Instruction::Add:
303 case Instruction::Sub:
304 return true;
305 case Instruction::Mul:
306 return I.hasNoUnsignedWrap();
307 default:
308 return false;
309 }
310 }
311
312 // Return true if the op promoted to i32 should have nuw set.
promotedOpIsNUW(const Instruction & I)313 static bool promotedOpIsNUW(const Instruction &I) {
314 switch (I.getOpcode()) {
315 case Instruction::Shl:
316 case Instruction::Add:
317 case Instruction::Mul:
318 return true;
319 case Instruction::Sub:
320 return I.hasNoUnsignedWrap();
321 default:
322 return false;
323 }
324 }
325
canWidenScalarExtLoad(LoadInst & I) const326 bool AMDGPUCodeGenPrepare::canWidenScalarExtLoad(LoadInst &I) const {
327 Type *Ty = I.getType();
328 const DataLayout &DL = Mod->getDataLayout();
329 int TySize = DL.getTypeSizeInBits(Ty);
330 Align Alignment = DL.getValueOrABITypeAlignment(I.getAlign(), Ty);
331
332 return I.isSimple() && TySize < 32 && Alignment >= 4 && DA->isUniform(&I);
333 }
334
promoteUniformOpToI32(BinaryOperator & I) const335 bool AMDGPUCodeGenPrepare::promoteUniformOpToI32(BinaryOperator &I) const {
336 assert(needsPromotionToI32(I.getType()) &&
337 "I does not need promotion to i32");
338
339 if (I.getOpcode() == Instruction::SDiv ||
340 I.getOpcode() == Instruction::UDiv ||
341 I.getOpcode() == Instruction::SRem ||
342 I.getOpcode() == Instruction::URem)
343 return false;
344
345 IRBuilder<> Builder(&I);
346 Builder.SetCurrentDebugLocation(I.getDebugLoc());
347
348 Type *I32Ty = getI32Ty(Builder, I.getType());
349 Value *ExtOp0 = nullptr;
350 Value *ExtOp1 = nullptr;
351 Value *ExtRes = nullptr;
352 Value *TruncRes = nullptr;
353
354 if (isSigned(I)) {
355 ExtOp0 = Builder.CreateSExt(I.getOperand(0), I32Ty);
356 ExtOp1 = Builder.CreateSExt(I.getOperand(1), I32Ty);
357 } else {
358 ExtOp0 = Builder.CreateZExt(I.getOperand(0), I32Ty);
359 ExtOp1 = Builder.CreateZExt(I.getOperand(1), I32Ty);
360 }
361
362 ExtRes = Builder.CreateBinOp(I.getOpcode(), ExtOp0, ExtOp1);
363 if (Instruction *Inst = dyn_cast<Instruction>(ExtRes)) {
364 if (promotedOpIsNSW(cast<Instruction>(I)))
365 Inst->setHasNoSignedWrap();
366
367 if (promotedOpIsNUW(cast<Instruction>(I)))
368 Inst->setHasNoUnsignedWrap();
369
370 if (const auto *ExactOp = dyn_cast<PossiblyExactOperator>(&I))
371 Inst->setIsExact(ExactOp->isExact());
372 }
373
374 TruncRes = Builder.CreateTrunc(ExtRes, I.getType());
375
376 I.replaceAllUsesWith(TruncRes);
377 I.eraseFromParent();
378
379 return true;
380 }
381
promoteUniformOpToI32(ICmpInst & I) const382 bool AMDGPUCodeGenPrepare::promoteUniformOpToI32(ICmpInst &I) const {
383 assert(needsPromotionToI32(I.getOperand(0)->getType()) &&
384 "I does not need promotion to i32");
385
386 IRBuilder<> Builder(&I);
387 Builder.SetCurrentDebugLocation(I.getDebugLoc());
388
389 Type *I32Ty = getI32Ty(Builder, I.getOperand(0)->getType());
390 Value *ExtOp0 = nullptr;
391 Value *ExtOp1 = nullptr;
392 Value *NewICmp = nullptr;
393
394 if (I.isSigned()) {
395 ExtOp0 = Builder.CreateSExt(I.getOperand(0), I32Ty);
396 ExtOp1 = Builder.CreateSExt(I.getOperand(1), I32Ty);
397 } else {
398 ExtOp0 = Builder.CreateZExt(I.getOperand(0), I32Ty);
399 ExtOp1 = Builder.CreateZExt(I.getOperand(1), I32Ty);
400 }
401 NewICmp = Builder.CreateICmp(I.getPredicate(), ExtOp0, ExtOp1);
402
403 I.replaceAllUsesWith(NewICmp);
404 I.eraseFromParent();
405
406 return true;
407 }
408
promoteUniformOpToI32(SelectInst & I) const409 bool AMDGPUCodeGenPrepare::promoteUniformOpToI32(SelectInst &I) const {
410 assert(needsPromotionToI32(I.getType()) &&
411 "I does not need promotion to i32");
412
413 IRBuilder<> Builder(&I);
414 Builder.SetCurrentDebugLocation(I.getDebugLoc());
415
416 Type *I32Ty = getI32Ty(Builder, I.getType());
417 Value *ExtOp1 = nullptr;
418 Value *ExtOp2 = nullptr;
419 Value *ExtRes = nullptr;
420 Value *TruncRes = nullptr;
421
422 if (isSigned(I)) {
423 ExtOp1 = Builder.CreateSExt(I.getOperand(1), I32Ty);
424 ExtOp2 = Builder.CreateSExt(I.getOperand(2), I32Ty);
425 } else {
426 ExtOp1 = Builder.CreateZExt(I.getOperand(1), I32Ty);
427 ExtOp2 = Builder.CreateZExt(I.getOperand(2), I32Ty);
428 }
429 ExtRes = Builder.CreateSelect(I.getOperand(0), ExtOp1, ExtOp2);
430 TruncRes = Builder.CreateTrunc(ExtRes, I.getType());
431
432 I.replaceAllUsesWith(TruncRes);
433 I.eraseFromParent();
434
435 return true;
436 }
437
promoteUniformBitreverseToI32(IntrinsicInst & I) const438 bool AMDGPUCodeGenPrepare::promoteUniformBitreverseToI32(
439 IntrinsicInst &I) const {
440 assert(I.getIntrinsicID() == Intrinsic::bitreverse &&
441 "I must be bitreverse intrinsic");
442 assert(needsPromotionToI32(I.getType()) &&
443 "I does not need promotion to i32");
444
445 IRBuilder<> Builder(&I);
446 Builder.SetCurrentDebugLocation(I.getDebugLoc());
447
448 Type *I32Ty = getI32Ty(Builder, I.getType());
449 Function *I32 =
450 Intrinsic::getDeclaration(Mod, Intrinsic::bitreverse, { I32Ty });
451 Value *ExtOp = Builder.CreateZExt(I.getOperand(0), I32Ty);
452 Value *ExtRes = Builder.CreateCall(I32, { ExtOp });
453 Value *LShrOp =
454 Builder.CreateLShr(ExtRes, 32 - getBaseElementBitWidth(I.getType()));
455 Value *TruncRes =
456 Builder.CreateTrunc(LShrOp, I.getType());
457
458 I.replaceAllUsesWith(TruncRes);
459 I.eraseFromParent();
460
461 return true;
462 }
463
numBitsUnsigned(Value * Op,unsigned ScalarSize) const464 unsigned AMDGPUCodeGenPrepare::numBitsUnsigned(Value *Op,
465 unsigned ScalarSize) const {
466 KnownBits Known = computeKnownBits(Op, *DL, 0, AC);
467 return ScalarSize - Known.countMinLeadingZeros();
468 }
469
numBitsSigned(Value * Op,unsigned ScalarSize) const470 unsigned AMDGPUCodeGenPrepare::numBitsSigned(Value *Op,
471 unsigned ScalarSize) const {
472 // In order for this to be a signed 24-bit value, bit 23, must
473 // be a sign bit.
474 return ScalarSize - ComputeNumSignBits(Op, *DL, 0, AC);
475 }
476
isI24(Value * V,unsigned ScalarSize) const477 bool AMDGPUCodeGenPrepare::isI24(Value *V, unsigned ScalarSize) const {
478 return ScalarSize >= 24 && // Types less than 24-bit should be treated
479 // as unsigned 24-bit values.
480 numBitsSigned(V, ScalarSize) < 24;
481 }
482
isU24(Value * V,unsigned ScalarSize) const483 bool AMDGPUCodeGenPrepare::isU24(Value *V, unsigned ScalarSize) const {
484 return numBitsUnsigned(V, ScalarSize) <= 24;
485 }
486
extractValues(IRBuilder<> & Builder,SmallVectorImpl<Value * > & Values,Value * V)487 static void extractValues(IRBuilder<> &Builder,
488 SmallVectorImpl<Value *> &Values, Value *V) {
489 auto *VT = dyn_cast<FixedVectorType>(V->getType());
490 if (!VT) {
491 Values.push_back(V);
492 return;
493 }
494
495 for (int I = 0, E = VT->getNumElements(); I != E; ++I)
496 Values.push_back(Builder.CreateExtractElement(V, I));
497 }
498
insertValues(IRBuilder<> & Builder,Type * Ty,SmallVectorImpl<Value * > & Values)499 static Value *insertValues(IRBuilder<> &Builder,
500 Type *Ty,
501 SmallVectorImpl<Value *> &Values) {
502 if (Values.size() == 1)
503 return Values[0];
504
505 Value *NewVal = UndefValue::get(Ty);
506 for (int I = 0, E = Values.size(); I != E; ++I)
507 NewVal = Builder.CreateInsertElement(NewVal, Values[I], I);
508
509 return NewVal;
510 }
511
replaceMulWithMul24(BinaryOperator & I) const512 bool AMDGPUCodeGenPrepare::replaceMulWithMul24(BinaryOperator &I) const {
513 if (I.getOpcode() != Instruction::Mul)
514 return false;
515
516 Type *Ty = I.getType();
517 unsigned Size = Ty->getScalarSizeInBits();
518 if (Size <= 16 && ST->has16BitInsts())
519 return false;
520
521 // Prefer scalar if this could be s_mul_i32
522 if (DA->isUniform(&I))
523 return false;
524
525 Value *LHS = I.getOperand(0);
526 Value *RHS = I.getOperand(1);
527 IRBuilder<> Builder(&I);
528 Builder.SetCurrentDebugLocation(I.getDebugLoc());
529
530 Intrinsic::ID IntrID = Intrinsic::not_intrinsic;
531
532 // TODO: Should this try to match mulhi24?
533 if (ST->hasMulU24() && isU24(LHS, Size) && isU24(RHS, Size)) {
534 IntrID = Intrinsic::amdgcn_mul_u24;
535 } else if (ST->hasMulI24() && isI24(LHS, Size) && isI24(RHS, Size)) {
536 IntrID = Intrinsic::amdgcn_mul_i24;
537 } else
538 return false;
539
540 SmallVector<Value *, 4> LHSVals;
541 SmallVector<Value *, 4> RHSVals;
542 SmallVector<Value *, 4> ResultVals;
543 extractValues(Builder, LHSVals, LHS);
544 extractValues(Builder, RHSVals, RHS);
545
546
547 IntegerType *I32Ty = Builder.getInt32Ty();
548 FunctionCallee Intrin = Intrinsic::getDeclaration(Mod, IntrID);
549 for (int I = 0, E = LHSVals.size(); I != E; ++I) {
550 Value *LHS, *RHS;
551 if (IntrID == Intrinsic::amdgcn_mul_u24) {
552 LHS = Builder.CreateZExtOrTrunc(LHSVals[I], I32Ty);
553 RHS = Builder.CreateZExtOrTrunc(RHSVals[I], I32Ty);
554 } else {
555 LHS = Builder.CreateSExtOrTrunc(LHSVals[I], I32Ty);
556 RHS = Builder.CreateSExtOrTrunc(RHSVals[I], I32Ty);
557 }
558
559 Value *Result = Builder.CreateCall(Intrin, {LHS, RHS});
560
561 if (IntrID == Intrinsic::amdgcn_mul_u24) {
562 ResultVals.push_back(Builder.CreateZExtOrTrunc(Result,
563 LHSVals[I]->getType()));
564 } else {
565 ResultVals.push_back(Builder.CreateSExtOrTrunc(Result,
566 LHSVals[I]->getType()));
567 }
568 }
569
570 Value *NewVal = insertValues(Builder, Ty, ResultVals);
571 NewVal->takeName(&I);
572 I.replaceAllUsesWith(NewVal);
573 I.eraseFromParent();
574
575 return true;
576 }
577
578 // Find a select instruction, which may have been casted. This is mostly to deal
579 // with cases where i16 selects were promoted here to i32.
findSelectThroughCast(Value * V,CastInst * & Cast)580 static SelectInst *findSelectThroughCast(Value *V, CastInst *&Cast) {
581 Cast = nullptr;
582 if (SelectInst *Sel = dyn_cast<SelectInst>(V))
583 return Sel;
584
585 if ((Cast = dyn_cast<CastInst>(V))) {
586 if (SelectInst *Sel = dyn_cast<SelectInst>(Cast->getOperand(0)))
587 return Sel;
588 }
589
590 return nullptr;
591 }
592
foldBinOpIntoSelect(BinaryOperator & BO) const593 bool AMDGPUCodeGenPrepare::foldBinOpIntoSelect(BinaryOperator &BO) const {
594 // Don't do this unless the old select is going away. We want to eliminate the
595 // binary operator, not replace a binop with a select.
596 int SelOpNo = 0;
597
598 CastInst *CastOp;
599
600 // TODO: Should probably try to handle some cases with multiple
601 // users. Duplicating the select may be profitable for division.
602 SelectInst *Sel = findSelectThroughCast(BO.getOperand(0), CastOp);
603 if (!Sel || !Sel->hasOneUse()) {
604 SelOpNo = 1;
605 Sel = findSelectThroughCast(BO.getOperand(1), CastOp);
606 }
607
608 if (!Sel || !Sel->hasOneUse())
609 return false;
610
611 Constant *CT = dyn_cast<Constant>(Sel->getTrueValue());
612 Constant *CF = dyn_cast<Constant>(Sel->getFalseValue());
613 Constant *CBO = dyn_cast<Constant>(BO.getOperand(SelOpNo ^ 1));
614 if (!CBO || !CT || !CF)
615 return false;
616
617 if (CastOp) {
618 if (!CastOp->hasOneUse())
619 return false;
620 CT = ConstantFoldCastOperand(CastOp->getOpcode(), CT, BO.getType(), *DL);
621 CF = ConstantFoldCastOperand(CastOp->getOpcode(), CF, BO.getType(), *DL);
622 }
623
624 // TODO: Handle special 0/-1 cases DAG combine does, although we only really
625 // need to handle divisions here.
626 Constant *FoldedT = SelOpNo ?
627 ConstantFoldBinaryOpOperands(BO.getOpcode(), CBO, CT, *DL) :
628 ConstantFoldBinaryOpOperands(BO.getOpcode(), CT, CBO, *DL);
629 if (isa<ConstantExpr>(FoldedT))
630 return false;
631
632 Constant *FoldedF = SelOpNo ?
633 ConstantFoldBinaryOpOperands(BO.getOpcode(), CBO, CF, *DL) :
634 ConstantFoldBinaryOpOperands(BO.getOpcode(), CF, CBO, *DL);
635 if (isa<ConstantExpr>(FoldedF))
636 return false;
637
638 IRBuilder<> Builder(&BO);
639 Builder.SetCurrentDebugLocation(BO.getDebugLoc());
640 if (const FPMathOperator *FPOp = dyn_cast<const FPMathOperator>(&BO))
641 Builder.setFastMathFlags(FPOp->getFastMathFlags());
642
643 Value *NewSelect = Builder.CreateSelect(Sel->getCondition(),
644 FoldedT, FoldedF);
645 NewSelect->takeName(&BO);
646 BO.replaceAllUsesWith(NewSelect);
647 BO.eraseFromParent();
648 if (CastOp)
649 CastOp->eraseFromParent();
650 Sel->eraseFromParent();
651 return true;
652 }
653
654 // Optimize fdiv with rcp:
655 //
656 // 1/x -> rcp(x) when rcp is sufficiently accurate or inaccurate rcp is
657 // allowed with unsafe-fp-math or afn.
658 //
659 // a/b -> a*rcp(b) when inaccurate rcp is allowed with unsafe-fp-math or afn.
optimizeWithRcp(Value * Num,Value * Den,bool AllowInaccurateRcp,bool RcpIsAccurate,IRBuilder<> & Builder,Module * Mod)660 static Value *optimizeWithRcp(Value *Num, Value *Den, bool AllowInaccurateRcp,
661 bool RcpIsAccurate, IRBuilder<> &Builder,
662 Module *Mod) {
663
664 if (!AllowInaccurateRcp && !RcpIsAccurate)
665 return nullptr;
666
667 Type *Ty = Den->getType();
668 if (const ConstantFP *CLHS = dyn_cast<ConstantFP>(Num)) {
669 if (AllowInaccurateRcp || RcpIsAccurate) {
670 if (CLHS->isExactlyValue(1.0)) {
671 Function *Decl = Intrinsic::getDeclaration(
672 Mod, Intrinsic::amdgcn_rcp, Ty);
673
674 // v_rcp_f32 and v_rsq_f32 do not support denormals, and according to
675 // the CI documentation has a worst case error of 1 ulp.
676 // OpenCL requires <= 2.5 ulp for 1.0 / x, so it should always be OK to
677 // use it as long as we aren't trying to use denormals.
678 //
679 // v_rcp_f16 and v_rsq_f16 DO support denormals.
680
681 // NOTE: v_sqrt and v_rcp will be combined to v_rsq later. So we don't
682 // insert rsq intrinsic here.
683
684 // 1.0 / x -> rcp(x)
685 return Builder.CreateCall(Decl, { Den });
686 }
687
688 // Same as for 1.0, but expand the sign out of the constant.
689 if (CLHS->isExactlyValue(-1.0)) {
690 Function *Decl = Intrinsic::getDeclaration(
691 Mod, Intrinsic::amdgcn_rcp, Ty);
692
693 // -1.0 / x -> rcp (fneg x)
694 Value *FNeg = Builder.CreateFNeg(Den);
695 return Builder.CreateCall(Decl, { FNeg });
696 }
697 }
698 }
699
700 if (AllowInaccurateRcp) {
701 Function *Decl = Intrinsic::getDeclaration(
702 Mod, Intrinsic::amdgcn_rcp, Ty);
703
704 // Turn into multiply by the reciprocal.
705 // x / y -> x * (1.0 / y)
706 Value *Recip = Builder.CreateCall(Decl, { Den });
707 return Builder.CreateFMul(Num, Recip);
708 }
709 return nullptr;
710 }
711
712 // optimize with fdiv.fast:
713 //
714 // a/b -> fdiv.fast(a, b) when !fpmath >= 2.5ulp with denormals flushed.
715 //
716 // 1/x -> fdiv.fast(1,x) when !fpmath >= 2.5ulp.
717 //
718 // NOTE: optimizeWithRcp should be tried first because rcp is the preference.
optimizeWithFDivFast(Value * Num,Value * Den,float ReqdAccuracy,bool HasDenormals,IRBuilder<> & Builder,Module * Mod)719 static Value *optimizeWithFDivFast(Value *Num, Value *Den, float ReqdAccuracy,
720 bool HasDenormals, IRBuilder<> &Builder,
721 Module *Mod) {
722 // fdiv.fast can achieve 2.5 ULP accuracy.
723 if (ReqdAccuracy < 2.5f)
724 return nullptr;
725
726 // Only have fdiv.fast for f32.
727 Type *Ty = Den->getType();
728 if (!Ty->isFloatTy())
729 return nullptr;
730
731 bool NumIsOne = false;
732 if (const ConstantFP *CNum = dyn_cast<ConstantFP>(Num)) {
733 if (CNum->isExactlyValue(+1.0) || CNum->isExactlyValue(-1.0))
734 NumIsOne = true;
735 }
736
737 // fdiv does not support denormals. But 1.0/x is always fine to use it.
738 if (HasDenormals && !NumIsOne)
739 return nullptr;
740
741 Function *Decl = Intrinsic::getDeclaration(Mod, Intrinsic::amdgcn_fdiv_fast);
742 return Builder.CreateCall(Decl, { Num, Den });
743 }
744
745 // Optimizations is performed based on fpmath, fast math flags as well as
746 // denormals to optimize fdiv with either rcp or fdiv.fast.
747 //
748 // With rcp:
749 // 1/x -> rcp(x) when rcp is sufficiently accurate or inaccurate rcp is
750 // allowed with unsafe-fp-math or afn.
751 //
752 // a/b -> a*rcp(b) when inaccurate rcp is allowed with unsafe-fp-math or afn.
753 //
754 // With fdiv.fast:
755 // a/b -> fdiv.fast(a, b) when !fpmath >= 2.5ulp with denormals flushed.
756 //
757 // 1/x -> fdiv.fast(1,x) when !fpmath >= 2.5ulp.
758 //
759 // NOTE: rcp is the preference in cases that both are legal.
visitFDiv(BinaryOperator & FDiv)760 bool AMDGPUCodeGenPrepare::visitFDiv(BinaryOperator &FDiv) {
761
762 Type *Ty = FDiv.getType()->getScalarType();
763
764 // No intrinsic for fdiv16 if target does not support f16.
765 if (Ty->isHalfTy() && !ST->has16BitInsts())
766 return false;
767
768 const FPMathOperator *FPOp = cast<const FPMathOperator>(&FDiv);
769 const float ReqdAccuracy = FPOp->getFPAccuracy();
770
771 // Inaccurate rcp is allowed with unsafe-fp-math or afn.
772 FastMathFlags FMF = FPOp->getFastMathFlags();
773 const bool AllowInaccurateRcp = HasUnsafeFPMath || FMF.approxFunc();
774
775 // rcp_f16 is accurate for !fpmath >= 1.0ulp.
776 // rcp_f32 is accurate for !fpmath >= 1.0ulp and denormals are flushed.
777 // rcp_f64 is never accurate.
778 const bool RcpIsAccurate = (Ty->isHalfTy() && ReqdAccuracy >= 1.0f) ||
779 (Ty->isFloatTy() && !HasFP32Denormals && ReqdAccuracy >= 1.0f);
780
781 IRBuilder<> Builder(FDiv.getParent(), std::next(FDiv.getIterator()));
782 Builder.setFastMathFlags(FMF);
783 Builder.SetCurrentDebugLocation(FDiv.getDebugLoc());
784
785 Value *Num = FDiv.getOperand(0);
786 Value *Den = FDiv.getOperand(1);
787
788 Value *NewFDiv = nullptr;
789 if (auto *VT = dyn_cast<FixedVectorType>(FDiv.getType())) {
790 NewFDiv = UndefValue::get(VT);
791
792 // FIXME: Doesn't do the right thing for cases where the vector is partially
793 // constant. This works when the scalarizer pass is run first.
794 for (unsigned I = 0, E = VT->getNumElements(); I != E; ++I) {
795 Value *NumEltI = Builder.CreateExtractElement(Num, I);
796 Value *DenEltI = Builder.CreateExtractElement(Den, I);
797 // Try rcp first.
798 Value *NewElt = optimizeWithRcp(NumEltI, DenEltI, AllowInaccurateRcp,
799 RcpIsAccurate, Builder, Mod);
800 if (!NewElt) // Try fdiv.fast.
801 NewElt = optimizeWithFDivFast(NumEltI, DenEltI, ReqdAccuracy,
802 HasFP32Denormals, Builder, Mod);
803 if (!NewElt) // Keep the original.
804 NewElt = Builder.CreateFDiv(NumEltI, DenEltI);
805
806 NewFDiv = Builder.CreateInsertElement(NewFDiv, NewElt, I);
807 }
808 } else { // Scalar FDiv.
809 // Try rcp first.
810 NewFDiv = optimizeWithRcp(Num, Den, AllowInaccurateRcp, RcpIsAccurate,
811 Builder, Mod);
812 if (!NewFDiv) { // Try fdiv.fast.
813 NewFDiv = optimizeWithFDivFast(Num, Den, ReqdAccuracy, HasFP32Denormals,
814 Builder, Mod);
815 }
816 }
817
818 if (NewFDiv) {
819 FDiv.replaceAllUsesWith(NewFDiv);
820 NewFDiv->takeName(&FDiv);
821 FDiv.eraseFromParent();
822 }
823
824 return !!NewFDiv;
825 }
826
hasUnsafeFPMath(const Function & F)827 static bool hasUnsafeFPMath(const Function &F) {
828 Attribute Attr = F.getFnAttribute("unsafe-fp-math");
829 return Attr.getValueAsString() == "true";
830 }
831
getMul64(IRBuilder<> & Builder,Value * LHS,Value * RHS)832 static std::pair<Value*, Value*> getMul64(IRBuilder<> &Builder,
833 Value *LHS, Value *RHS) {
834 Type *I32Ty = Builder.getInt32Ty();
835 Type *I64Ty = Builder.getInt64Ty();
836
837 Value *LHS_EXT64 = Builder.CreateZExt(LHS, I64Ty);
838 Value *RHS_EXT64 = Builder.CreateZExt(RHS, I64Ty);
839 Value *MUL64 = Builder.CreateMul(LHS_EXT64, RHS_EXT64);
840 Value *Lo = Builder.CreateTrunc(MUL64, I32Ty);
841 Value *Hi = Builder.CreateLShr(MUL64, Builder.getInt64(32));
842 Hi = Builder.CreateTrunc(Hi, I32Ty);
843 return std::make_pair(Lo, Hi);
844 }
845
getMulHu(IRBuilder<> & Builder,Value * LHS,Value * RHS)846 static Value* getMulHu(IRBuilder<> &Builder, Value *LHS, Value *RHS) {
847 return getMul64(Builder, LHS, RHS).second;
848 }
849
850 /// Figure out how many bits are really needed for this ddivision. \p AtLeast is
851 /// an optimization hint to bypass the second ComputeNumSignBits call if we the
852 /// first one is insufficient. Returns -1 on failure.
getDivNumBits(BinaryOperator & I,Value * Num,Value * Den,unsigned AtLeast,bool IsSigned) const853 int AMDGPUCodeGenPrepare::getDivNumBits(BinaryOperator &I,
854 Value *Num, Value *Den,
855 unsigned AtLeast, bool IsSigned) const {
856 const DataLayout &DL = Mod->getDataLayout();
857 unsigned LHSSignBits = ComputeNumSignBits(Num, DL, 0, AC, &I);
858 if (LHSSignBits < AtLeast)
859 return -1;
860
861 unsigned RHSSignBits = ComputeNumSignBits(Den, DL, 0, AC, &I);
862 if (RHSSignBits < AtLeast)
863 return -1;
864
865 unsigned SignBits = std::min(LHSSignBits, RHSSignBits);
866 unsigned DivBits = Num->getType()->getScalarSizeInBits() - SignBits;
867 if (IsSigned)
868 ++DivBits;
869 return DivBits;
870 }
871
872 // The fractional part of a float is enough to accurately represent up to
873 // a 24-bit signed integer.
expandDivRem24(IRBuilder<> & Builder,BinaryOperator & I,Value * Num,Value * Den,bool IsDiv,bool IsSigned) const874 Value *AMDGPUCodeGenPrepare::expandDivRem24(IRBuilder<> &Builder,
875 BinaryOperator &I,
876 Value *Num, Value *Den,
877 bool IsDiv, bool IsSigned) const {
878 int DivBits = getDivNumBits(I, Num, Den, 9, IsSigned);
879 if (DivBits == -1)
880 return nullptr;
881 return expandDivRem24Impl(Builder, I, Num, Den, DivBits, IsDiv, IsSigned);
882 }
883
expandDivRem24Impl(IRBuilder<> & Builder,BinaryOperator & I,Value * Num,Value * Den,unsigned DivBits,bool IsDiv,bool IsSigned) const884 Value *AMDGPUCodeGenPrepare::expandDivRem24Impl(IRBuilder<> &Builder,
885 BinaryOperator &I,
886 Value *Num, Value *Den,
887 unsigned DivBits,
888 bool IsDiv, bool IsSigned) const {
889 Type *I32Ty = Builder.getInt32Ty();
890 Num = Builder.CreateTrunc(Num, I32Ty);
891 Den = Builder.CreateTrunc(Den, I32Ty);
892
893 Type *F32Ty = Builder.getFloatTy();
894 ConstantInt *One = Builder.getInt32(1);
895 Value *JQ = One;
896
897 if (IsSigned) {
898 // char|short jq = ia ^ ib;
899 JQ = Builder.CreateXor(Num, Den);
900
901 // jq = jq >> (bitsize - 2)
902 JQ = Builder.CreateAShr(JQ, Builder.getInt32(30));
903
904 // jq = jq | 0x1
905 JQ = Builder.CreateOr(JQ, One);
906 }
907
908 // int ia = (int)LHS;
909 Value *IA = Num;
910
911 // int ib, (int)RHS;
912 Value *IB = Den;
913
914 // float fa = (float)ia;
915 Value *FA = IsSigned ? Builder.CreateSIToFP(IA, F32Ty)
916 : Builder.CreateUIToFP(IA, F32Ty);
917
918 // float fb = (float)ib;
919 Value *FB = IsSigned ? Builder.CreateSIToFP(IB,F32Ty)
920 : Builder.CreateUIToFP(IB,F32Ty);
921
922 Function *RcpDecl = Intrinsic::getDeclaration(Mod, Intrinsic::amdgcn_rcp,
923 Builder.getFloatTy());
924 Value *RCP = Builder.CreateCall(RcpDecl, { FB });
925 Value *FQM = Builder.CreateFMul(FA, RCP);
926
927 // fq = trunc(fqm);
928 CallInst *FQ = Builder.CreateUnaryIntrinsic(Intrinsic::trunc, FQM);
929 FQ->copyFastMathFlags(Builder.getFastMathFlags());
930
931 // float fqneg = -fq;
932 Value *FQNeg = Builder.CreateFNeg(FQ);
933
934 // float fr = mad(fqneg, fb, fa);
935 auto FMAD = !ST->hasMadMacF32Insts()
936 ? Intrinsic::fma
937 : (Intrinsic::ID)Intrinsic::amdgcn_fmad_ftz;
938 Value *FR = Builder.CreateIntrinsic(FMAD,
939 {FQNeg->getType()}, {FQNeg, FB, FA}, FQ);
940
941 // int iq = (int)fq;
942 Value *IQ = IsSigned ? Builder.CreateFPToSI(FQ, I32Ty)
943 : Builder.CreateFPToUI(FQ, I32Ty);
944
945 // fr = fabs(fr);
946 FR = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FR, FQ);
947
948 // fb = fabs(fb);
949 FB = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FB, FQ);
950
951 // int cv = fr >= fb;
952 Value *CV = Builder.CreateFCmpOGE(FR, FB);
953
954 // jq = (cv ? jq : 0);
955 JQ = Builder.CreateSelect(CV, JQ, Builder.getInt32(0));
956
957 // dst = iq + jq;
958 Value *Div = Builder.CreateAdd(IQ, JQ);
959
960 Value *Res = Div;
961 if (!IsDiv) {
962 // Rem needs compensation, it's easier to recompute it
963 Value *Rem = Builder.CreateMul(Div, Den);
964 Res = Builder.CreateSub(Num, Rem);
965 }
966
967 if (DivBits != 0 && DivBits < 32) {
968 // Extend in register from the number of bits this divide really is.
969 if (IsSigned) {
970 int InRegBits = 32 - DivBits;
971
972 Res = Builder.CreateShl(Res, InRegBits);
973 Res = Builder.CreateAShr(Res, InRegBits);
974 } else {
975 ConstantInt *TruncMask
976 = Builder.getInt32((UINT64_C(1) << DivBits) - 1);
977 Res = Builder.CreateAnd(Res, TruncMask);
978 }
979 }
980
981 return Res;
982 }
983
984 // Try to recognize special cases the DAG will emit special, better expansions
985 // than the general expansion we do here.
986
987 // TODO: It would be better to just directly handle those optimizations here.
divHasSpecialOptimization(BinaryOperator & I,Value * Num,Value * Den) const988 bool AMDGPUCodeGenPrepare::divHasSpecialOptimization(
989 BinaryOperator &I, Value *Num, Value *Den) const {
990 if (Constant *C = dyn_cast<Constant>(Den)) {
991 // Arbitrary constants get a better expansion as long as a wider mulhi is
992 // legal.
993 if (C->getType()->getScalarSizeInBits() <= 32)
994 return true;
995
996 // TODO: Sdiv check for not exact for some reason.
997
998 // If there's no wider mulhi, there's only a better expansion for powers of
999 // two.
1000 // TODO: Should really know for each vector element.
1001 if (isKnownToBeAPowerOfTwo(C, *DL, true, 0, AC, &I, DT))
1002 return true;
1003
1004 return false;
1005 }
1006
1007 if (BinaryOperator *BinOpDen = dyn_cast<BinaryOperator>(Den)) {
1008 // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
1009 if (BinOpDen->getOpcode() == Instruction::Shl &&
1010 isa<Constant>(BinOpDen->getOperand(0)) &&
1011 isKnownToBeAPowerOfTwo(BinOpDen->getOperand(0), *DL, true,
1012 0, AC, &I, DT)) {
1013 return true;
1014 }
1015 }
1016
1017 return false;
1018 }
1019
getSign32(Value * V,IRBuilder<> & Builder,const DataLayout * DL)1020 static Value *getSign32(Value *V, IRBuilder<> &Builder, const DataLayout *DL) {
1021 // Check whether the sign can be determined statically.
1022 KnownBits Known = computeKnownBits(V, *DL);
1023 if (Known.isNegative())
1024 return Constant::getAllOnesValue(V->getType());
1025 if (Known.isNonNegative())
1026 return Constant::getNullValue(V->getType());
1027 return Builder.CreateAShr(V, Builder.getInt32(31));
1028 }
1029
expandDivRem32(IRBuilder<> & Builder,BinaryOperator & I,Value * X,Value * Y) const1030 Value *AMDGPUCodeGenPrepare::expandDivRem32(IRBuilder<> &Builder,
1031 BinaryOperator &I, Value *X,
1032 Value *Y) const {
1033 Instruction::BinaryOps Opc = I.getOpcode();
1034 assert(Opc == Instruction::URem || Opc == Instruction::UDiv ||
1035 Opc == Instruction::SRem || Opc == Instruction::SDiv);
1036
1037 FastMathFlags FMF;
1038 FMF.setFast();
1039 Builder.setFastMathFlags(FMF);
1040
1041 if (divHasSpecialOptimization(I, X, Y))
1042 return nullptr; // Keep it for later optimization.
1043
1044 bool IsDiv = Opc == Instruction::UDiv || Opc == Instruction::SDiv;
1045 bool IsSigned = Opc == Instruction::SRem || Opc == Instruction::SDiv;
1046
1047 Type *Ty = X->getType();
1048 Type *I32Ty = Builder.getInt32Ty();
1049 Type *F32Ty = Builder.getFloatTy();
1050
1051 if (Ty->getScalarSizeInBits() < 32) {
1052 if (IsSigned) {
1053 X = Builder.CreateSExt(X, I32Ty);
1054 Y = Builder.CreateSExt(Y, I32Ty);
1055 } else {
1056 X = Builder.CreateZExt(X, I32Ty);
1057 Y = Builder.CreateZExt(Y, I32Ty);
1058 }
1059 }
1060
1061 if (Value *Res = expandDivRem24(Builder, I, X, Y, IsDiv, IsSigned)) {
1062 return IsSigned ? Builder.CreateSExtOrTrunc(Res, Ty) :
1063 Builder.CreateZExtOrTrunc(Res, Ty);
1064 }
1065
1066 ConstantInt *Zero = Builder.getInt32(0);
1067 ConstantInt *One = Builder.getInt32(1);
1068
1069 Value *Sign = nullptr;
1070 if (IsSigned) {
1071 Value *SignX = getSign32(X, Builder, DL);
1072 Value *SignY = getSign32(Y, Builder, DL);
1073 // Remainder sign is the same as LHS
1074 Sign = IsDiv ? Builder.CreateXor(SignX, SignY) : SignX;
1075
1076 X = Builder.CreateAdd(X, SignX);
1077 Y = Builder.CreateAdd(Y, SignY);
1078
1079 X = Builder.CreateXor(X, SignX);
1080 Y = Builder.CreateXor(Y, SignY);
1081 }
1082
1083 // The algorithm here is based on ideas from "Software Integer Division", Tom
1084 // Rodeheffer, August 2008.
1085 //
1086 // unsigned udiv(unsigned x, unsigned y) {
1087 // // Initial estimate of inv(y). The constant is less than 2^32 to ensure
1088 // // that this is a lower bound on inv(y), even if some of the calculations
1089 // // round up.
1090 // unsigned z = (unsigned)((4294967296.0 - 512.0) * v_rcp_f32((float)y));
1091 //
1092 // // One round of UNR (Unsigned integer Newton-Raphson) to improve z.
1093 // // Empirically this is guaranteed to give a "two-y" lower bound on
1094 // // inv(y).
1095 // z += umulh(z, -y * z);
1096 //
1097 // // Quotient/remainder estimate.
1098 // unsigned q = umulh(x, z);
1099 // unsigned r = x - q * y;
1100 //
1101 // // Two rounds of quotient/remainder refinement.
1102 // if (r >= y) {
1103 // ++q;
1104 // r -= y;
1105 // }
1106 // if (r >= y) {
1107 // ++q;
1108 // r -= y;
1109 // }
1110 //
1111 // return q;
1112 // }
1113
1114 // Initial estimate of inv(y).
1115 Value *FloatY = Builder.CreateUIToFP(Y, F32Ty);
1116 Function *Rcp = Intrinsic::getDeclaration(Mod, Intrinsic::amdgcn_rcp, F32Ty);
1117 Value *RcpY = Builder.CreateCall(Rcp, {FloatY});
1118 Constant *Scale = ConstantFP::get(F32Ty, BitsToFloat(0x4F7FFFFE));
1119 Value *ScaledY = Builder.CreateFMul(RcpY, Scale);
1120 Value *Z = Builder.CreateFPToUI(ScaledY, I32Ty);
1121
1122 // One round of UNR.
1123 Value *NegY = Builder.CreateSub(Zero, Y);
1124 Value *NegYZ = Builder.CreateMul(NegY, Z);
1125 Z = Builder.CreateAdd(Z, getMulHu(Builder, Z, NegYZ));
1126
1127 // Quotient/remainder estimate.
1128 Value *Q = getMulHu(Builder, X, Z);
1129 Value *R = Builder.CreateSub(X, Builder.CreateMul(Q, Y));
1130
1131 // First quotient/remainder refinement.
1132 Value *Cond = Builder.CreateICmpUGE(R, Y);
1133 if (IsDiv)
1134 Q = Builder.CreateSelect(Cond, Builder.CreateAdd(Q, One), Q);
1135 R = Builder.CreateSelect(Cond, Builder.CreateSub(R, Y), R);
1136
1137 // Second quotient/remainder refinement.
1138 Cond = Builder.CreateICmpUGE(R, Y);
1139 Value *Res;
1140 if (IsDiv)
1141 Res = Builder.CreateSelect(Cond, Builder.CreateAdd(Q, One), Q);
1142 else
1143 Res = Builder.CreateSelect(Cond, Builder.CreateSub(R, Y), R);
1144
1145 if (IsSigned) {
1146 Res = Builder.CreateXor(Res, Sign);
1147 Res = Builder.CreateSub(Res, Sign);
1148 }
1149
1150 Res = Builder.CreateTrunc(Res, Ty);
1151
1152 return Res;
1153 }
1154
shrinkDivRem64(IRBuilder<> & Builder,BinaryOperator & I,Value * Num,Value * Den) const1155 Value *AMDGPUCodeGenPrepare::shrinkDivRem64(IRBuilder<> &Builder,
1156 BinaryOperator &I,
1157 Value *Num, Value *Den) const {
1158 if (!ExpandDiv64InIR && divHasSpecialOptimization(I, Num, Den))
1159 return nullptr; // Keep it for later optimization.
1160
1161 Instruction::BinaryOps Opc = I.getOpcode();
1162
1163 bool IsDiv = Opc == Instruction::SDiv || Opc == Instruction::UDiv;
1164 bool IsSigned = Opc == Instruction::SDiv || Opc == Instruction::SRem;
1165
1166 int NumDivBits = getDivNumBits(I, Num, Den, 32, IsSigned);
1167 if (NumDivBits == -1)
1168 return nullptr;
1169
1170 Value *Narrowed = nullptr;
1171 if (NumDivBits <= 24) {
1172 Narrowed = expandDivRem24Impl(Builder, I, Num, Den, NumDivBits,
1173 IsDiv, IsSigned);
1174 } else if (NumDivBits <= 32) {
1175 Narrowed = expandDivRem32(Builder, I, Num, Den);
1176 }
1177
1178 if (Narrowed) {
1179 return IsSigned ? Builder.CreateSExt(Narrowed, Num->getType()) :
1180 Builder.CreateZExt(Narrowed, Num->getType());
1181 }
1182
1183 return nullptr;
1184 }
1185
expandDivRem64(BinaryOperator & I) const1186 void AMDGPUCodeGenPrepare::expandDivRem64(BinaryOperator &I) const {
1187 Instruction::BinaryOps Opc = I.getOpcode();
1188 // Do the general expansion.
1189 if (Opc == Instruction::UDiv || Opc == Instruction::SDiv) {
1190 expandDivisionUpTo64Bits(&I);
1191 return;
1192 }
1193
1194 if (Opc == Instruction::URem || Opc == Instruction::SRem) {
1195 expandRemainderUpTo64Bits(&I);
1196 return;
1197 }
1198
1199 llvm_unreachable("not a division");
1200 }
1201
visitBinaryOperator(BinaryOperator & I)1202 bool AMDGPUCodeGenPrepare::visitBinaryOperator(BinaryOperator &I) {
1203 if (foldBinOpIntoSelect(I))
1204 return true;
1205
1206 if (ST->has16BitInsts() && needsPromotionToI32(I.getType()) &&
1207 DA->isUniform(&I) && promoteUniformOpToI32(I))
1208 return true;
1209
1210 if (UseMul24Intrin && replaceMulWithMul24(I))
1211 return true;
1212
1213 bool Changed = false;
1214 Instruction::BinaryOps Opc = I.getOpcode();
1215 Type *Ty = I.getType();
1216 Value *NewDiv = nullptr;
1217 unsigned ScalarSize = Ty->getScalarSizeInBits();
1218
1219 SmallVector<BinaryOperator *, 8> Div64ToExpand;
1220
1221 if ((Opc == Instruction::URem || Opc == Instruction::UDiv ||
1222 Opc == Instruction::SRem || Opc == Instruction::SDiv) &&
1223 ScalarSize <= 64 &&
1224 !DisableIDivExpand) {
1225 Value *Num = I.getOperand(0);
1226 Value *Den = I.getOperand(1);
1227 IRBuilder<> Builder(&I);
1228 Builder.SetCurrentDebugLocation(I.getDebugLoc());
1229
1230 if (auto *VT = dyn_cast<FixedVectorType>(Ty)) {
1231 NewDiv = UndefValue::get(VT);
1232
1233 for (unsigned N = 0, E = VT->getNumElements(); N != E; ++N) {
1234 Value *NumEltN = Builder.CreateExtractElement(Num, N);
1235 Value *DenEltN = Builder.CreateExtractElement(Den, N);
1236
1237 Value *NewElt;
1238 if (ScalarSize <= 32) {
1239 NewElt = expandDivRem32(Builder, I, NumEltN, DenEltN);
1240 if (!NewElt)
1241 NewElt = Builder.CreateBinOp(Opc, NumEltN, DenEltN);
1242 } else {
1243 // See if this 64-bit division can be shrunk to 32/24-bits before
1244 // producing the general expansion.
1245 NewElt = shrinkDivRem64(Builder, I, NumEltN, DenEltN);
1246 if (!NewElt) {
1247 // The general 64-bit expansion introduces control flow and doesn't
1248 // return the new value. Just insert a scalar copy and defer
1249 // expanding it.
1250 NewElt = Builder.CreateBinOp(Opc, NumEltN, DenEltN);
1251 Div64ToExpand.push_back(cast<BinaryOperator>(NewElt));
1252 }
1253 }
1254
1255 NewDiv = Builder.CreateInsertElement(NewDiv, NewElt, N);
1256 }
1257 } else {
1258 if (ScalarSize <= 32)
1259 NewDiv = expandDivRem32(Builder, I, Num, Den);
1260 else {
1261 NewDiv = shrinkDivRem64(Builder, I, Num, Den);
1262 if (!NewDiv)
1263 Div64ToExpand.push_back(&I);
1264 }
1265 }
1266
1267 if (NewDiv) {
1268 I.replaceAllUsesWith(NewDiv);
1269 I.eraseFromParent();
1270 Changed = true;
1271 }
1272 }
1273
1274 if (ExpandDiv64InIR) {
1275 // TODO: We get much worse code in specially handled constant cases.
1276 for (BinaryOperator *Div : Div64ToExpand) {
1277 expandDivRem64(*Div);
1278 Changed = true;
1279 }
1280 }
1281
1282 return Changed;
1283 }
1284
visitLoadInst(LoadInst & I)1285 bool AMDGPUCodeGenPrepare::visitLoadInst(LoadInst &I) {
1286 if (!WidenLoads)
1287 return false;
1288
1289 if ((I.getPointerAddressSpace() == AMDGPUAS::CONSTANT_ADDRESS ||
1290 I.getPointerAddressSpace() == AMDGPUAS::CONSTANT_ADDRESS_32BIT) &&
1291 canWidenScalarExtLoad(I)) {
1292 IRBuilder<> Builder(&I);
1293 Builder.SetCurrentDebugLocation(I.getDebugLoc());
1294
1295 Type *I32Ty = Builder.getInt32Ty();
1296 Type *PT = PointerType::get(I32Ty, I.getPointerAddressSpace());
1297 Value *BitCast= Builder.CreateBitCast(I.getPointerOperand(), PT);
1298 LoadInst *WidenLoad = Builder.CreateLoad(I32Ty, BitCast);
1299 WidenLoad->copyMetadata(I);
1300
1301 // If we have range metadata, we need to convert the type, and not make
1302 // assumptions about the high bits.
1303 if (auto *Range = WidenLoad->getMetadata(LLVMContext::MD_range)) {
1304 ConstantInt *Lower =
1305 mdconst::extract<ConstantInt>(Range->getOperand(0));
1306
1307 if (Lower->getValue().isNullValue()) {
1308 WidenLoad->setMetadata(LLVMContext::MD_range, nullptr);
1309 } else {
1310 Metadata *LowAndHigh[] = {
1311 ConstantAsMetadata::get(ConstantInt::get(I32Ty, Lower->getValue().zext(32))),
1312 // Don't make assumptions about the high bits.
1313 ConstantAsMetadata::get(ConstantInt::get(I32Ty, 0))
1314 };
1315
1316 WidenLoad->setMetadata(LLVMContext::MD_range,
1317 MDNode::get(Mod->getContext(), LowAndHigh));
1318 }
1319 }
1320
1321 int TySize = Mod->getDataLayout().getTypeSizeInBits(I.getType());
1322 Type *IntNTy = Builder.getIntNTy(TySize);
1323 Value *ValTrunc = Builder.CreateTrunc(WidenLoad, IntNTy);
1324 Value *ValOrig = Builder.CreateBitCast(ValTrunc, I.getType());
1325 I.replaceAllUsesWith(ValOrig);
1326 I.eraseFromParent();
1327 return true;
1328 }
1329
1330 return false;
1331 }
1332
visitICmpInst(ICmpInst & I)1333 bool AMDGPUCodeGenPrepare::visitICmpInst(ICmpInst &I) {
1334 bool Changed = false;
1335
1336 if (ST->has16BitInsts() && needsPromotionToI32(I.getOperand(0)->getType()) &&
1337 DA->isUniform(&I))
1338 Changed |= promoteUniformOpToI32(I);
1339
1340 return Changed;
1341 }
1342
visitSelectInst(SelectInst & I)1343 bool AMDGPUCodeGenPrepare::visitSelectInst(SelectInst &I) {
1344 bool Changed = false;
1345
1346 if (ST->has16BitInsts() && needsPromotionToI32(I.getType()) &&
1347 DA->isUniform(&I))
1348 Changed |= promoteUniformOpToI32(I);
1349
1350 return Changed;
1351 }
1352
visitIntrinsicInst(IntrinsicInst & I)1353 bool AMDGPUCodeGenPrepare::visitIntrinsicInst(IntrinsicInst &I) {
1354 switch (I.getIntrinsicID()) {
1355 case Intrinsic::bitreverse:
1356 return visitBitreverseIntrinsicInst(I);
1357 default:
1358 return false;
1359 }
1360 }
1361
visitBitreverseIntrinsicInst(IntrinsicInst & I)1362 bool AMDGPUCodeGenPrepare::visitBitreverseIntrinsicInst(IntrinsicInst &I) {
1363 bool Changed = false;
1364
1365 if (ST->has16BitInsts() && needsPromotionToI32(I.getType()) &&
1366 DA->isUniform(&I))
1367 Changed |= promoteUniformBitreverseToI32(I);
1368
1369 return Changed;
1370 }
1371
doInitialization(Module & M)1372 bool AMDGPUCodeGenPrepare::doInitialization(Module &M) {
1373 Mod = &M;
1374 DL = &Mod->getDataLayout();
1375 return false;
1376 }
1377
runOnFunction(Function & F)1378 bool AMDGPUCodeGenPrepare::runOnFunction(Function &F) {
1379 if (skipFunction(F))
1380 return false;
1381
1382 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
1383 if (!TPC)
1384 return false;
1385
1386 const AMDGPUTargetMachine &TM = TPC->getTM<AMDGPUTargetMachine>();
1387 ST = &TM.getSubtarget<GCNSubtarget>(F);
1388 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1389 DA = &getAnalysis<LegacyDivergenceAnalysis>();
1390
1391 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1392 DT = DTWP ? &DTWP->getDomTree() : nullptr;
1393
1394 HasUnsafeFPMath = hasUnsafeFPMath(F);
1395
1396 AMDGPU::SIModeRegisterDefaults Mode(F);
1397 HasFP32Denormals = Mode.allFP32Denormals();
1398
1399 bool MadeChange = false;
1400
1401 Function::iterator NextBB;
1402 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; FI = NextBB) {
1403 BasicBlock *BB = &*FI;
1404 NextBB = std::next(FI);
1405
1406 BasicBlock::iterator Next;
1407 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; I = Next) {
1408 Next = std::next(I);
1409
1410 MadeChange |= visit(*I);
1411
1412 if (Next != E) { // Control flow changed
1413 BasicBlock *NextInstBB = Next->getParent();
1414 if (NextInstBB != BB) {
1415 BB = NextInstBB;
1416 E = BB->end();
1417 FE = F.end();
1418 }
1419 }
1420 }
1421 }
1422
1423 return MadeChange;
1424 }
1425
1426 INITIALIZE_PASS_BEGIN(AMDGPUCodeGenPrepare, DEBUG_TYPE,
1427 "AMDGPU IR optimizations", false, false)
1428 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1429 INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
1430 INITIALIZE_PASS_END(AMDGPUCodeGenPrepare, DEBUG_TYPE, "AMDGPU IR optimizations",
1431 false, false)
1432
1433 char AMDGPUCodeGenPrepare::ID = 0;
1434
createAMDGPUCodeGenPreparePass()1435 FunctionPass *llvm::createAMDGPUCodeGenPreparePass() {
1436 return new AMDGPUCodeGenPrepare();
1437 }
1438