639 lines · cpp
1//===-- IntegerDivision.cpp - Expand integer division ---------------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains an implementation of 32bit and 64bit scalar integer10// division for targets that don't have native support. It's largely derived11// from compiler-rt's implementations of __udivsi3 and __udivmoddi4,12// but hand-tuned for targets that prefer less control flow.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/Transforms/Utils/IntegerDivision.h"17#include "llvm/IR/Function.h"18#include "llvm/IR/IRBuilder.h"19#include "llvm/IR/Instructions.h"20#include "llvm/IR/Intrinsics.h"21 22using namespace llvm;23 24#define DEBUG_TYPE "integer-division"25 26/// Generate code to compute the remainder of two signed integers. Returns the27/// remainder, which will have the sign of the dividend. Builder's insert point28/// should be pointing where the caller wants code generated, e.g. at the srem29/// instruction. This will generate a urem in the process, and Builder's insert30/// point will be pointing at the uren (if present, i.e. not folded), ready to31/// be expanded if the user wishes32static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,33 IRBuilder<> &Builder) {34 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();35 ConstantInt *Shift = Builder.getIntN(BitWidth, BitWidth - 1);36 37 // Following instructions are generated for both i32 (shift 31) and38 // i64 (shift 63).39 40 // ; %dividend_sgn = ashr i32 %dividend, 3141 // ; %divisor_sgn = ashr i32 %divisor, 3142 // ; %dvd_xor = xor i32 %dividend, %dividend_sgn43 // ; %dvs_xor = xor i32 %divisor, %divisor_sgn44 // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn45 // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn46 // ; %urem = urem i32 %dividend, %divisor47 // ; %xored = xor i32 %urem, %dividend_sgn48 // ; %srem = sub i32 %xored, %dividend_sgn49 Dividend = Builder.CreateFreeze(Dividend);50 Divisor = Builder.CreateFreeze(Divisor);51 Value *DividendSign = Builder.CreateAShr(Dividend, Shift);52 Value *DivisorSign = Builder.CreateAShr(Divisor, Shift);53 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign);54 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign);55 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign);56 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign);57 Value *URem = Builder.CreateURem(UDividend, UDivisor);58 Value *Xored = Builder.CreateXor(URem, DividendSign);59 Value *SRem = Builder.CreateSub(Xored, DividendSign);60 61 if (Instruction *URemInst = dyn_cast<Instruction>(URem))62 Builder.SetInsertPoint(URemInst);63 64 return SRem;65}66 67 68/// Generate code to compute the remainder of two unsigned integers. Returns the69/// remainder. Builder's insert point should be pointing where the caller wants70/// code generated, e.g. at the urem instruction. This will generate a udiv in71/// the process, and Builder's insert point will be pointing at the udiv (if72/// present, i.e. not folded), ready to be expanded if the user wishes73static Value *generateUnsignedRemainderCode(Value *Dividend, Value *Divisor,74 IRBuilder<> &Builder) {75 // Remainder = Dividend - Quotient*Divisor76 77 // Following instructions are generated for both i32 and i6478 79 // ; %quotient = udiv i32 %dividend, %divisor80 // ; %product = mul i32 %divisor, %quotient81 // ; %remainder = sub i32 %dividend, %product82 Dividend = Builder.CreateFreeze(Dividend);83 Divisor = Builder.CreateFreeze(Divisor);84 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor);85 Value *Product = Builder.CreateMul(Divisor, Quotient);86 Value *Remainder = Builder.CreateSub(Dividend, Product);87 88 if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))89 Builder.SetInsertPoint(UDiv);90 91 return Remainder;92}93 94/// Generate code to divide two signed integers. Returns the quotient, rounded95/// towards 0. Builder's insert point should be pointing where the caller wants96/// code generated, e.g. at the sdiv instruction. This will generate a udiv in97/// the process, and Builder's insert point will be pointing at the udiv (if98/// present, i.e. not folded), ready to be expanded if the user wishes.99static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,100 IRBuilder<> &Builder) {101 // Implementation taken from compiler-rt's __divsi3 and __divdi3102 103 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();104 ConstantInt *Shift = Builder.getIntN(BitWidth, BitWidth - 1);105 106 // Following instructions are generated for both i32 (shift 31) and107 // i64 (shift 63).108 109 // ; %tmp = ashr i32 %dividend, 31110 // ; %tmp1 = ashr i32 %divisor, 31111 // ; %tmp2 = xor i32 %tmp, %dividend112 // ; %u_dvnd = sub nsw i32 %tmp2, %tmp113 // ; %tmp3 = xor i32 %tmp1, %divisor114 // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1115 // ; %q_sgn = xor i32 %tmp1, %tmp116 // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr117 // ; %tmp4 = xor i32 %q_mag, %q_sgn118 // ; %q = sub i32 %tmp4, %q_sgn119 Dividend = Builder.CreateFreeze(Dividend);120 Divisor = Builder.CreateFreeze(Divisor);121 Value *Tmp = Builder.CreateAShr(Dividend, Shift);122 Value *Tmp1 = Builder.CreateAShr(Divisor, Shift);123 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend);124 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);125 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor);126 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);127 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp);128 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr);129 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn);130 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn);131 132 if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))133 Builder.SetInsertPoint(UDiv);134 135 return Q;136}137 138/// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.139/// Returns the quotient, rounded towards 0. Builder's insert point should140/// point where the caller wants code generated, e.g. at the udiv instruction.141static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,142 IRBuilder<> &Builder) {143 // The basic algorithm can be found in the compiler-rt project's144 // implementation of __udivsi3.c. Here, we do a lower-level IR based approach145 // that's been hand-tuned to lessen the amount of control flow involved.146 147 // Some helper values148 IntegerType *DivTy = cast<IntegerType>(Dividend->getType());149 unsigned BitWidth = DivTy->getBitWidth();150 151 ConstantInt *Zero = ConstantInt::get(DivTy, 0);152 ConstantInt *One = ConstantInt::get(DivTy, 1);153 ConstantInt *NegOne = ConstantInt::getSigned(DivTy, -1);154 ConstantInt *MSB = ConstantInt::get(DivTy, BitWidth - 1);155 156 ConstantInt *True = Builder.getTrue();157 158 BasicBlock *IBB = Builder.GetInsertBlock();159 Function *F = IBB->getParent();160 Function *CTLZ =161 Intrinsic::getOrInsertDeclaration(F->getParent(), Intrinsic::ctlz, DivTy);162 163 // Our CFG is going to look like:164 // +---------------------+165 // | special-cases |166 // | ... |167 // +---------------------+168 // | |169 // | +----------+170 // | | bb1 |171 // | | ... |172 // | +----------+173 // | | |174 // | | +------------+175 // | | | preheader |176 // | | | ... |177 // | | +------------+178 // | | |179 // | | | +---+180 // | | | | |181 // | | +------------+ |182 // | | | do-while | |183 // | | | ... | |184 // | | +------------+ |185 // | | | | |186 // | +-----------+ +---+187 // | | loop-exit |188 // | | ... |189 // | +-----------+190 // | |191 // +-------+192 // | ... |193 // | end |194 // +-------+195 BasicBlock *SpecialCases = Builder.GetInsertBlock();196 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));197 BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),198 "udiv-end");199 BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(),200 "udiv-loop-exit", F, End);201 BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(),202 "udiv-do-while", F, End);203 BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),204 "udiv-preheader", F, End);205 BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(),206 "udiv-bb1", F, End);207 208 // We'll be overwriting the terminator to insert our extra blocks209 SpecialCases->getTerminator()->eraseFromParent();210 211 // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).212 213 // First off, check for special cases: dividend or divisor is zero, divisor214 // is greater than dividend, and divisor is 1.215 // ; special-cases:216 // ; %ret0_1 = icmp eq i32 %divisor, 0217 // ; %ret0_2 = icmp eq i32 %dividend, 0218 // ; %ret0_3 = or i1 %ret0_1, %ret0_2219 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)220 // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)221 // ; %sr = sub nsw i32 %tmp0, %tmp1222 // ; %ret0_4 = icmp ugt i32 %sr, 31223 // ; %ret0 = select i1 %ret0_3, i1 true, i1 %ret0_4224 // ; %retDividend = icmp eq i32 %sr, 31225 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend226 // ; %earlyRet = select i1 %ret0, i1 true, %retDividend227 // ; br i1 %earlyRet, label %end, label %bb1228 Builder.SetInsertPoint(SpecialCases);229 Divisor = Builder.CreateFreeze(Divisor);230 Dividend = Builder.CreateFreeze(Dividend);231 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero);232 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero);233 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2);234 Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True});235 Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True});236 Value *SR = Builder.CreateSub(Tmp0, Tmp1);237 Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB);238 Value *Ret0 = Builder.CreateLogicalOr(Ret0_3, Ret0_4);239 Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);240 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend);241 Value *EarlyRet = Builder.CreateLogicalOr(Ret0, RetDividend);242 Builder.CreateCondBr(EarlyRet, End, BB1);243 244 // ; bb1: ; preds = %special-cases245 // ; %sr_1 = add i32 %sr, 1246 // ; %tmp2 = sub i32 31, %sr247 // ; %q = shl i32 %dividend, %tmp2248 // ; %skipLoop = icmp eq i32 %sr_1, 0249 // ; br i1 %skipLoop, label %loop-exit, label %preheader250 Builder.SetInsertPoint(BB1);251 Value *SR_1 = Builder.CreateAdd(SR, One);252 Value *Tmp2 = Builder.CreateSub(MSB, SR);253 Value *Q = Builder.CreateShl(Dividend, Tmp2);254 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);255 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);256 257 // ; preheader: ; preds = %bb1258 // ; %tmp3 = lshr i32 %dividend, %sr_1259 // ; %tmp4 = add i32 %divisor, -1260 // ; br label %do-while261 Builder.SetInsertPoint(Preheader);262 Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);263 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);264 Builder.CreateBr(DoWhile);265 266 // ; do-while: ; preds = %do-while, %preheader267 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]268 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]269 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]270 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]271 // ; %tmp5 = shl i32 %r_1, 1272 // ; %tmp6 = lshr i32 %q_2, 31273 // ; %tmp7 = or i32 %tmp5, %tmp6274 // ; %tmp8 = shl i32 %q_2, 1275 // ; %q_1 = or i32 %carry_1, %tmp8276 // ; %tmp9 = sub i32 %tmp4, %tmp7277 // ; %tmp10 = ashr i32 %tmp9, 31278 // ; %carry = and i32 %tmp10, 1279 // ; %tmp11 = and i32 %tmp10, %divisor280 // ; %r = sub i32 %tmp7, %tmp11281 // ; %sr_2 = add i32 %sr_3, -1282 // ; %tmp12 = icmp eq i32 %sr_2, 0283 // ; br i1 %tmp12, label %loop-exit, label %do-while284 Builder.SetInsertPoint(DoWhile);285 PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);286 PHINode *SR_3 = Builder.CreatePHI(DivTy, 2);287 PHINode *R_1 = Builder.CreatePHI(DivTy, 2);288 PHINode *Q_2 = Builder.CreatePHI(DivTy, 2);289 Value *Tmp5 = Builder.CreateShl(R_1, One);290 Value *Tmp6 = Builder.CreateLShr(Q_2, MSB);291 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6);292 Value *Tmp8 = Builder.CreateShl(Q_2, One);293 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8);294 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7);295 Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);296 Value *Carry = Builder.CreateAnd(Tmp10, One);297 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);298 Value *R = Builder.CreateSub(Tmp7, Tmp11);299 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne);300 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);301 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);302 303 // ; loop-exit: ; preds = %do-while, %bb1304 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]305 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]306 // ; %tmp13 = shl i32 %q_3, 1307 // ; %q_4 = or i32 %carry_2, %tmp13308 // ; br label %end309 Builder.SetInsertPoint(LoopExit);310 PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);311 PHINode *Q_3 = Builder.CreatePHI(DivTy, 2);312 Value *Tmp13 = Builder.CreateShl(Q_3, One);313 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13);314 Builder.CreateBr(End);315 316 // ; end: ; preds = %loop-exit, %special-cases317 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]318 // ; ret i32 %q_5319 Builder.SetInsertPoint(End, End->begin());320 PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);321 322 // Populate the Phis, since all values have now been created. Our Phis were:323 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]324 Carry_1->addIncoming(Zero, Preheader);325 Carry_1->addIncoming(Carry, DoWhile);326 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]327 SR_3->addIncoming(SR_1, Preheader);328 SR_3->addIncoming(SR_2, DoWhile);329 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]330 R_1->addIncoming(Tmp3, Preheader);331 R_1->addIncoming(R, DoWhile);332 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]333 Q_2->addIncoming(Q, Preheader);334 Q_2->addIncoming(Q_1, DoWhile);335 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]336 Carry_2->addIncoming(Zero, BB1);337 Carry_2->addIncoming(Carry, DoWhile);338 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]339 Q_3->addIncoming(Q, BB1);340 Q_3->addIncoming(Q_1, DoWhile);341 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]342 Q_5->addIncoming(Q_4, LoopExit);343 Q_5->addIncoming(RetVal, SpecialCases);344 345 return Q_5;346}347 348/// Generate code to calculate the remainder of two integers, replacing Rem with349/// the generated code. This currently generates code using the udiv expansion,350/// but future work includes generating more specialized code, e.g. when more351/// information about the operands are known.352///353/// Replace Rem with generated code.354bool llvm::expandRemainder(BinaryOperator *Rem) {355 assert((Rem->getOpcode() == Instruction::SRem ||356 Rem->getOpcode() == Instruction::URem) &&357 "Trying to expand remainder from a non-remainder function");358 359 IRBuilder<> Builder(Rem);360 361 assert(!Rem->getType()->isVectorTy() && "Div over vectors not supported");362 363 // First prepare the sign if it's a signed remainder364 if (Rem->getOpcode() == Instruction::SRem) {365 Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),366 Rem->getOperand(1), Builder);367 368 // Check whether this is the insert point while Rem is still valid.369 bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint();370 Rem->replaceAllUsesWith(Remainder);371 Rem->dropAllReferences();372 Rem->eraseFromParent();373 374 // If we didn't actually generate an urem instruction, we're done375 // This happens for example if the input were constant. In this case the376 // Builder insertion point was unchanged377 if (IsInsertPoint)378 return true;379 380 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());381 Rem = BO;382 }383 384 Value *Remainder = generateUnsignedRemainderCode(Rem->getOperand(0),385 Rem->getOperand(1), Builder);386 387 Rem->replaceAllUsesWith(Remainder);388 Rem->dropAllReferences();389 Rem->eraseFromParent();390 391 // Expand the udiv392 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {393 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");394 expandDivision(UDiv);395 }396 397 return true;398}399 400/// Generate code to divide two integers, replacing Div with the generated401/// code. This currently generates code similarly to compiler-rt's402/// implementations, but future work includes generating more specialized code403/// when more information about the operands are known.404///405/// Replace Div with generated code.406bool llvm::expandDivision(BinaryOperator *Div) {407 assert((Div->getOpcode() == Instruction::SDiv ||408 Div->getOpcode() == Instruction::UDiv) &&409 "Trying to expand division from a non-division function");410 411 IRBuilder<> Builder(Div);412 413 assert(!Div->getType()->isVectorTy() && "Div over vectors not supported");414 415 // First prepare the sign if it's a signed division416 if (Div->getOpcode() == Instruction::SDiv) {417 // Lower the code to unsigned division, and reset Div to point to the udiv.418 Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),419 Div->getOperand(1), Builder);420 421 // Check whether this is the insert point while Div is still valid.422 bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();423 Div->replaceAllUsesWith(Quotient);424 Div->dropAllReferences();425 Div->eraseFromParent();426 427 // If we didn't actually generate an udiv instruction, we're done428 // This happens for example if the input were constant. In this case the429 // Builder insertion point was unchanged430 if (IsInsertPoint)431 return true;432 433 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());434 Div = BO;435 }436 437 // Insert the unsigned division code438 Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),439 Div->getOperand(1),440 Builder);441 Div->replaceAllUsesWith(Quotient);442 Div->dropAllReferences();443 Div->eraseFromParent();444 445 return true;446}447 448/// Generate code to compute the remainder of two integers of bitwidth up to449/// 32 bits. Uses the above routines and extends the inputs/truncates the450/// outputs to operate in 32 bits; that is, these routines are good for targets451/// that have no or very little suppport for smaller than 32 bit integer452/// arithmetic.453///454/// Replace Rem with emulation code.455bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {456 assert((Rem->getOpcode() == Instruction::SRem ||457 Rem->getOpcode() == Instruction::URem) &&458 "Trying to expand remainder from a non-remainder function");459 460 Type *RemTy = Rem->getType();461 assert(!RemTy->isVectorTy() && "Div over vectors not supported");462 463 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();464 465 assert(RemTyBitWidth <= 32 &&466 "Div of bitwidth greater than 32 not supported");467 468 if (RemTyBitWidth == 32)469 return expandRemainder(Rem);470 471 // If bitwidth smaller than 32 extend inputs, extend output and proceed472 // with 32 bit division.473 IRBuilder<> Builder(Rem);474 475 Value *ExtDividend;476 Value *ExtDivisor;477 Value *ExtRem;478 Value *Trunc;479 Type *Int32Ty = Builder.getInt32Ty();480 481 if (Rem->getOpcode() == Instruction::SRem) {482 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);483 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);484 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);485 } else {486 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);487 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);488 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);489 }490 Trunc = Builder.CreateTrunc(ExtRem, RemTy);491 492 Rem->replaceAllUsesWith(Trunc);493 Rem->dropAllReferences();494 Rem->eraseFromParent();495 496 return expandRemainder(cast<BinaryOperator>(ExtRem));497}498 499/// Generate code to compute the remainder of two integers of bitwidth up to500/// 64 bits. Uses the above routines and extends the inputs/truncates the501/// outputs to operate in 64 bits.502///503/// Replace Rem with emulation code.504bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {505 assert((Rem->getOpcode() == Instruction::SRem ||506 Rem->getOpcode() == Instruction::URem) &&507 "Trying to expand remainder from a non-remainder function");508 509 Type *RemTy = Rem->getType();510 assert(!RemTy->isVectorTy() && "Div over vectors not supported");511 512 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();513 514 if (RemTyBitWidth >= 64)515 return expandRemainder(Rem);516 517 // If bitwidth smaller than 64 extend inputs, extend output and proceed518 // with 64 bit division.519 IRBuilder<> Builder(Rem);520 521 Value *ExtDividend;522 Value *ExtDivisor;523 Value *ExtRem;524 Value *Trunc;525 Type *Int64Ty = Builder.getInt64Ty();526 527 if (Rem->getOpcode() == Instruction::SRem) {528 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);529 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);530 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);531 } else {532 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);533 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);534 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);535 }536 Trunc = Builder.CreateTrunc(ExtRem, RemTy);537 538 Rem->replaceAllUsesWith(Trunc);539 Rem->dropAllReferences();540 Rem->eraseFromParent();541 542 return expandRemainder(cast<BinaryOperator>(ExtRem));543}544 545/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the546/// above routines and extends the inputs/truncates the outputs to operate547/// in 32 bits; that is, these routines are good for targets that have no548/// or very little support for smaller than 32 bit integer arithmetic.549///550/// Replace Div with emulation code.551bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {552 assert((Div->getOpcode() == Instruction::SDiv ||553 Div->getOpcode() == Instruction::UDiv) &&554 "Trying to expand division from a non-division function");555 556 Type *DivTy = Div->getType();557 assert(!DivTy->isVectorTy() && "Div over vectors not supported");558 559 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();560 561 assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported");562 563 if (DivTyBitWidth == 32)564 return expandDivision(Div);565 566 // If bitwidth smaller than 32 extend inputs, extend output and proceed567 // with 32 bit division.568 IRBuilder<> Builder(Div);569 570 Value *ExtDividend;571 Value *ExtDivisor;572 Value *ExtDiv;573 Value *Trunc;574 Type *Int32Ty = Builder.getInt32Ty();575 576 if (Div->getOpcode() == Instruction::SDiv) {577 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);578 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);579 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);580 } else {581 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);582 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);583 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);584 }585 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);586 587 Div->replaceAllUsesWith(Trunc);588 Div->dropAllReferences();589 Div->eraseFromParent();590 591 return expandDivision(cast<BinaryOperator>(ExtDiv));592}593 594/// Generate code to divide two integers of bitwidth up to 64 bits. Uses the595/// above routines and extends the inputs/truncates the outputs to operate596/// in 64 bits.597///598/// Replace Div with emulation code.599bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {600 assert((Div->getOpcode() == Instruction::SDiv ||601 Div->getOpcode() == Instruction::UDiv) &&602 "Trying to expand division from a non-division function");603 604 Type *DivTy = Div->getType();605 assert(!DivTy->isVectorTy() && "Div over vectors not supported");606 607 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();608 609 if (DivTyBitWidth >= 64)610 return expandDivision(Div);611 612 // If bitwidth smaller than 64 extend inputs, extend output and proceed613 // with 64 bit division.614 IRBuilder<> Builder(Div);615 616 Value *ExtDividend;617 Value *ExtDivisor;618 Value *ExtDiv;619 Value *Trunc;620 Type *Int64Ty = Builder.getInt64Ty();621 622 if (Div->getOpcode() == Instruction::SDiv) {623 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);624 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);625 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);626 } else {627 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);628 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);629 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);630 }631 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);632 633 Div->replaceAllUsesWith(Trunc);634 Div->dropAllReferences();635 Div->eraseFromParent();636 637 return expandDivision(cast<BinaryOperator>(ExtDiv));638}639