24#define DEBUG_TYPE "integer-division"
49 Dividend =
Builder.CreateFreeze(Dividend);
50 Divisor =
Builder.CreateFreeze(Divisor);
51 Value *DividendSign =
Builder.CreateAShr(Dividend, Shift);
53 Value *DvdXor =
Builder.CreateXor(Dividend, DividendSign);
55 Value *UDividend =
Builder.CreateSub(DvdXor, DividendSign);
56 Value *UDivisor =
Builder.CreateSub(DvsXor, DivisorSign);
61 if (
Instruction *URemInst = dyn_cast<Instruction>(URem))
62 Builder.SetInsertPoint(URemInst);
82 Dividend =
Builder.CreateFreeze(Dividend);
83 Divisor =
Builder.CreateFreeze(Divisor);
88 if (
Instruction *UDiv = dyn_cast<Instruction>(Quotient))
119 Dividend =
Builder.CreateFreeze(Dividend);
120 Divisor =
Builder.CreateFreeze(Divisor);
132 if (
Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
200 "udiv-loop-exit",
F,
End);
202 "udiv-do-while",
F,
End);
204 "udiv-preheader",
F,
End);
228 Builder.SetInsertPoint(SpecialCases);
229 Divisor =
Builder.CreateFreeze(Divisor);
230 Dividend =
Builder.CreateFreeze(Dividend);
234 Value *Tmp0 =
Builder.CreateCall(CTLZ, {Divisor, True});
235 Value *Tmp1 =
Builder.CreateCall(CTLZ, {Dividend, True});
240 Value *RetVal =
Builder.CreateSelect(Ret0, Zero, Dividend);
241 Value *EarlyRet =
Builder.CreateLogicalOr(Ret0, RetDividend);
255 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
261 Builder.SetInsertPoint(Preheader);
284 Builder.SetInsertPoint(DoWhile);
301 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
309 Builder.SetInsertPoint(LoopExit);
356 Rem->
getOpcode() == Instruction::URem) &&
357 "Trying to expand remainder from a non-remainder function");
364 if (Rem->
getOpcode() == Instruction::SRem) {
394 assert(UDiv->getOpcode() == Instruction::UDiv &&
"Non-udiv in expansion?");
409 Div->
getOpcode() == Instruction::UDiv) &&
410 "Trying to expand division from a non-division function");
417 if (Div->
getOpcode() == Instruction::SDiv) {
458 Rem->
getOpcode() == Instruction::URem) &&
459 "Trying to expand remainder from a non-remainder function");
466 assert(RemTyBitWidth <= 32 &&
467 "Div of bitwidth greater than 32 not supported");
469 if (RemTyBitWidth == 32)
482 if (Rem->
getOpcode() == Instruction::SRem) {
485 ExtRem =
Builder.CreateSRem(ExtDividend, ExtDivisor);
489 ExtRem =
Builder.CreateURem(ExtDividend, ExtDivisor);
491 Trunc =
Builder.CreateTrunc(ExtRem, RemTy);
507 Rem->
getOpcode() == Instruction::URem) &&
508 "Trying to expand remainder from a non-remainder function");
515 if (RemTyBitWidth >= 64)
528 if (Rem->
getOpcode() == Instruction::SRem) {
531 ExtRem =
Builder.CreateSRem(ExtDividend, ExtDivisor);
535 ExtRem =
Builder.CreateURem(ExtDividend, ExtDivisor);
537 Trunc =
Builder.CreateTrunc(ExtRem, RemTy);
554 Div->
getOpcode() == Instruction::UDiv) &&
555 "Trying to expand division from a non-division function");
562 assert(DivTyBitWidth <= 32 &&
"Div of bitwidth greater than 32 not supported");
564 if (DivTyBitWidth == 32)
577 if (Div->
getOpcode() == Instruction::SDiv) {
580 ExtDiv =
Builder.CreateSDiv(ExtDividend, ExtDivisor);
584 ExtDiv =
Builder.CreateUDiv(ExtDividend, ExtDivisor);
586 Trunc =
Builder.CreateTrunc(ExtDiv, DivTy);
602 Div->
getOpcode() == Instruction::UDiv) &&
603 "Trying to expand division from a non-division function");
610 if (DivTyBitWidth >= 64)
623 if (Div->
getOpcode() == Instruction::SDiv) {
626 ExtDiv =
Builder.CreateSDiv(ExtDividend, ExtDivisor);
630 ExtDiv =
Builder.CreateUDiv(ExtDividend, ExtDivisor);
632 Trunc =
Builder.CreateTrunc(ExtDiv, DivTy);
static Value * generateSignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to divide two signed integers.
static Value * generateSignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two signed integers.
static Value * generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
static Value * generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two unsigned integers.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BinaryOps getOpcode() const
This is the shared class of boolean and integer constants.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
void dropAllReferences()
Drop all references to operands.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
self_iterator getIterator()
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
This is an optimization pass for GlobalISel generic memory operations.
bool expandDivision(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
bool expandRemainderUpTo32Bits(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
bool expandRemainderUpTo64Bits(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
bool expandDivisionUpTo64Bits(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
bool expandDivisionUpTo32Bits(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
constexpr unsigned BitWidth
bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.