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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains an implementation of 32bit and 64bit scalar integer 10 // division for targets that don't have native support. It's largely derived 11 // 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 22 using namespace llvm; 23 24 #define DEBUG_TYPE "integer-division" 25 26 /// Generate code to compute the remainder of two signed integers. Returns the 27 /// remainder, which will have the sign of the dividend. Builder's insert point 28 /// should be pointing where the caller wants code generated, e.g. at the srem 29 /// instruction. This will generate a urem in the process, and Builder's insert 30 /// point will be pointing at the uren (if present, i.e. not folded), ready to 31 /// be expanded if the user wishes 32 static 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) and 38 // i64 (shift 63). 39 40 // ; %dividend_sgn = ashr i32 %dividend, 31 41 // ; %divisor_sgn = ashr i32 %divisor, 31 42 // ; %dvd_xor = xor i32 %dividend, %dividend_sgn 43 // ; %dvs_xor = xor i32 %divisor, %divisor_sgn 44 // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn 45 // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn 46 // ; %urem = urem i32 %dividend, %divisor 47 // ; %xored = xor i32 %urem, %dividend_sgn 48 // ; %srem = sub i32 %xored, %dividend_sgn 49 Value *DividendSign = Builder.CreateAShr(Dividend, Shift); 50 Value *DivisorSign = Builder.CreateAShr(Divisor, Shift); 51 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign); 52 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign); 53 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign); 54 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign); 55 Value *URem = Builder.CreateURem(UDividend, UDivisor); 56 Value *Xored = Builder.CreateXor(URem, DividendSign); 57 Value *SRem = Builder.CreateSub(Xored, DividendSign); 58 59 if (Instruction *URemInst = dyn_cast<Instruction>(URem)) 60 Builder.SetInsertPoint(URemInst); 61 62 return SRem; 63 } 64 65 66 /// Generate code to compute the remainder of two unsigned integers. Returns the 67 /// remainder. Builder's insert point should be pointing where the caller wants 68 /// code generated, e.g. at the urem instruction. This will generate a udiv in 69 /// the process, and Builder's insert point will be pointing at the udiv (if 70 /// present, i.e. not folded), ready to be expanded if the user wishes 71 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, 72 IRBuilder<> &Builder) { 73 // Remainder = Dividend - Quotient*Divisor 74 75 // Following instructions are generated for both i32 and i64 76 77 // ; %quotient = udiv i32 %dividend, %divisor 78 // ; %product = mul i32 %divisor, %quotient 79 // ; %remainder = sub i32 %dividend, %product 80 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor); 81 Value *Product = Builder.CreateMul(Divisor, Quotient); 82 Value *Remainder = Builder.CreateSub(Dividend, Product); 83 84 if (Instruction *UDiv = dyn_cast<Instruction>(Quotient)) 85 Builder.SetInsertPoint(UDiv); 86 87 return Remainder; 88 } 89 90 /// Generate code to divide two signed integers. Returns the quotient, rounded 91 /// towards 0. Builder's insert point should be pointing where the caller wants 92 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in 93 /// the process, and Builder's insert point will be pointing at the udiv (if 94 /// present, i.e. not folded), ready to be expanded if the user wishes. 95 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor, 96 IRBuilder<> &Builder) { 97 // Implementation taken from compiler-rt's __divsi3 and __divdi3 98 99 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth(); 100 ConstantInt *Shift = Builder.getIntN(BitWidth, BitWidth - 1); 101 102 // Following instructions are generated for both i32 (shift 31) and 103 // i64 (shift 63). 104 105 // ; %tmp = ashr i32 %dividend, 31 106 // ; %tmp1 = ashr i32 %divisor, 31 107 // ; %tmp2 = xor i32 %tmp, %dividend 108 // ; %u_dvnd = sub nsw i32 %tmp2, %tmp 109 // ; %tmp3 = xor i32 %tmp1, %divisor 110 // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1 111 // ; %q_sgn = xor i32 %tmp1, %tmp 112 // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr 113 // ; %tmp4 = xor i32 %q_mag, %q_sgn 114 // ; %q = sub i32 %tmp4, %q_sgn 115 Value *Tmp = Builder.CreateAShr(Dividend, Shift); 116 Value *Tmp1 = Builder.CreateAShr(Divisor, Shift); 117 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend); 118 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp); 119 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor); 120 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1); 121 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp); 122 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr); 123 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn); 124 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn); 125 126 if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag)) 127 Builder.SetInsertPoint(UDiv); 128 129 return Q; 130 } 131 132 /// Generates code to divide two unsigned scalar 32-bit or 64-bit integers. 133 /// Returns the quotient, rounded towards 0. Builder's insert point should 134 /// point where the caller wants code generated, e.g. at the udiv instruction. 135 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, 136 IRBuilder<> &Builder) { 137 // The basic algorithm can be found in the compiler-rt project's 138 // implementation of __udivsi3.c. Here, we do a lower-level IR based approach 139 // that's been hand-tuned to lessen the amount of control flow involved. 140 141 // Some helper values 142 IntegerType *DivTy = cast<IntegerType>(Dividend->getType()); 143 unsigned BitWidth = DivTy->getBitWidth(); 144 145 ConstantInt *Zero = ConstantInt::get(DivTy, 0); 146 ConstantInt *One = ConstantInt::get(DivTy, 1); 147 ConstantInt *NegOne = ConstantInt::getSigned(DivTy, -1); 148 ConstantInt *MSB = ConstantInt::get(DivTy, BitWidth - 1); 149 150 ConstantInt *True = Builder.getTrue(); 151 152 BasicBlock *IBB = Builder.GetInsertBlock(); 153 Function *F = IBB->getParent(); 154 Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz, 155 DivTy); 156 157 // Our CFG is going to look like: 158 // +---------------------+ 159 // | special-cases | 160 // | ... | 161 // +---------------------+ 162 // | | 163 // | +----------+ 164 // | | bb1 | 165 // | | ... | 166 // | +----------+ 167 // | | | 168 // | | +------------+ 169 // | | | preheader | 170 // | | | ... | 171 // | | +------------+ 172 // | | | 173 // | | | +---+ 174 // | | | | | 175 // | | +------------+ | 176 // | | | do-while | | 177 // | | | ... | | 178 // | | +------------+ | 179 // | | | | | 180 // | +-----------+ +---+ 181 // | | loop-exit | 182 // | | ... | 183 // | +-----------+ 184 // | | 185 // +-------+ 186 // | ... | 187 // | end | 188 // +-------+ 189 BasicBlock *SpecialCases = Builder.GetInsertBlock(); 190 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases")); 191 BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(), 192 "udiv-end"); 193 BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(), 194 "udiv-loop-exit", F, End); 195 BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(), 196 "udiv-do-while", F, End); 197 BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(), 198 "udiv-preheader", F, End); 199 BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(), 200 "udiv-bb1", F, End); 201 202 // We'll be overwriting the terminator to insert our extra blocks 203 SpecialCases->getTerminator()->eraseFromParent(); 204 205 // Same instructions are generated for both i32 (msb 31) and i64 (msb 63). 206 207 // First off, check for special cases: dividend or divisor is zero, divisor 208 // is greater than dividend, and divisor is 1. 209 // ; special-cases: 210 // ; %ret0_1 = icmp eq i32 %divisor, 0 211 // ; %ret0_2 = icmp eq i32 %dividend, 0 212 // ; %ret0_3 = or i1 %ret0_1, %ret0_2 213 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true) 214 // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true) 215 // ; %sr = sub nsw i32 %tmp0, %tmp1 216 // ; %ret0_4 = icmp ugt i32 %sr, 31 217 // ; %ret0 = or i1 %ret0_3, %ret0_4 218 // ; %retDividend = icmp eq i32 %sr, 31 219 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend 220 // ; %earlyRet = or i1 %ret0, %retDividend 221 // ; br i1 %earlyRet, label %end, label %bb1 222 Builder.SetInsertPoint(SpecialCases); 223 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero); 224 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero); 225 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2); 226 Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True}); 227 Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True}); 228 Value *SR = Builder.CreateSub(Tmp0, Tmp1); 229 Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB); 230 Value *Ret0 = Builder.CreateOr(Ret0_3, Ret0_4); 231 Value *RetDividend = Builder.CreateICmpEQ(SR, MSB); 232 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend); 233 Value *EarlyRet = Builder.CreateOr(Ret0, RetDividend); 234 Builder.CreateCondBr(EarlyRet, End, BB1); 235 236 // ; bb1: ; preds = %special-cases 237 // ; %sr_1 = add i32 %sr, 1 238 // ; %tmp2 = sub i32 31, %sr 239 // ; %q = shl i32 %dividend, %tmp2 240 // ; %skipLoop = icmp eq i32 %sr_1, 0 241 // ; br i1 %skipLoop, label %loop-exit, label %preheader 242 Builder.SetInsertPoint(BB1); 243 Value *SR_1 = Builder.CreateAdd(SR, One); 244 Value *Tmp2 = Builder.CreateSub(MSB, SR); 245 Value *Q = Builder.CreateShl(Dividend, Tmp2); 246 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero); 247 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader); 248 249 // ; preheader: ; preds = %bb1 250 // ; %tmp3 = lshr i32 %dividend, %sr_1 251 // ; %tmp4 = add i32 %divisor, -1 252 // ; br label %do-while 253 Builder.SetInsertPoint(Preheader); 254 Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1); 255 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne); 256 Builder.CreateBr(DoWhile); 257 258 // ; do-while: ; preds = %do-while, %preheader 259 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 260 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 261 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 262 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 263 // ; %tmp5 = shl i32 %r_1, 1 264 // ; %tmp6 = lshr i32 %q_2, 31 265 // ; %tmp7 = or i32 %tmp5, %tmp6 266 // ; %tmp8 = shl i32 %q_2, 1 267 // ; %q_1 = or i32 %carry_1, %tmp8 268 // ; %tmp9 = sub i32 %tmp4, %tmp7 269 // ; %tmp10 = ashr i32 %tmp9, 31 270 // ; %carry = and i32 %tmp10, 1 271 // ; %tmp11 = and i32 %tmp10, %divisor 272 // ; %r = sub i32 %tmp7, %tmp11 273 // ; %sr_2 = add i32 %sr_3, -1 274 // ; %tmp12 = icmp eq i32 %sr_2, 0 275 // ; br i1 %tmp12, label %loop-exit, label %do-while 276 Builder.SetInsertPoint(DoWhile); 277 PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2); 278 PHINode *SR_3 = Builder.CreatePHI(DivTy, 2); 279 PHINode *R_1 = Builder.CreatePHI(DivTy, 2); 280 PHINode *Q_2 = Builder.CreatePHI(DivTy, 2); 281 Value *Tmp5 = Builder.CreateShl(R_1, One); 282 Value *Tmp6 = Builder.CreateLShr(Q_2, MSB); 283 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6); 284 Value *Tmp8 = Builder.CreateShl(Q_2, One); 285 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8); 286 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7); 287 Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB); 288 Value *Carry = Builder.CreateAnd(Tmp10, One); 289 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor); 290 Value *R = Builder.CreateSub(Tmp7, Tmp11); 291 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne); 292 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero); 293 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile); 294 295 // ; loop-exit: ; preds = %do-while, %bb1 296 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 297 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 298 // ; %tmp13 = shl i32 %q_3, 1 299 // ; %q_4 = or i32 %carry_2, %tmp13 300 // ; br label %end 301 Builder.SetInsertPoint(LoopExit); 302 PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2); 303 PHINode *Q_3 = Builder.CreatePHI(DivTy, 2); 304 Value *Tmp13 = Builder.CreateShl(Q_3, One); 305 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13); 306 Builder.CreateBr(End); 307 308 // ; end: ; preds = %loop-exit, %special-cases 309 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 310 // ; ret i32 %q_5 311 Builder.SetInsertPoint(End, End->begin()); 312 PHINode *Q_5 = Builder.CreatePHI(DivTy, 2); 313 314 // Populate the Phis, since all values have now been created. Our Phis were: 315 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 316 Carry_1->addIncoming(Zero, Preheader); 317 Carry_1->addIncoming(Carry, DoWhile); 318 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 319 SR_3->addIncoming(SR_1, Preheader); 320 SR_3->addIncoming(SR_2, DoWhile); 321 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 322 R_1->addIncoming(Tmp3, Preheader); 323 R_1->addIncoming(R, DoWhile); 324 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 325 Q_2->addIncoming(Q, Preheader); 326 Q_2->addIncoming(Q_1, DoWhile); 327 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 328 Carry_2->addIncoming(Zero, BB1); 329 Carry_2->addIncoming(Carry, DoWhile); 330 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 331 Q_3->addIncoming(Q, BB1); 332 Q_3->addIncoming(Q_1, DoWhile); 333 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 334 Q_5->addIncoming(Q_4, LoopExit); 335 Q_5->addIncoming(RetVal, SpecialCases); 336 337 return Q_5; 338 } 339 340 /// Generate code to calculate the remainder of two integers, replacing Rem with 341 /// the generated code. This currently generates code using the udiv expansion, 342 /// but future work includes generating more specialized code, e.g. when more 343 /// information about the operands are known. 344 /// 345 /// Replace Rem with generated code. 346 bool llvm::expandRemainder(BinaryOperator *Rem) { 347 assert((Rem->getOpcode() == Instruction::SRem || 348 Rem->getOpcode() == Instruction::URem) && 349 "Trying to expand remainder from a non-remainder function"); 350 351 IRBuilder<> Builder(Rem); 352 353 assert(!Rem->getType()->isVectorTy() && "Div over vectors not supported"); 354 355 // First prepare the sign if it's a signed remainder 356 if (Rem->getOpcode() == Instruction::SRem) { 357 Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0), 358 Rem->getOperand(1), Builder); 359 360 // Check whether this is the insert point while Rem is still valid. 361 bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint(); 362 Rem->replaceAllUsesWith(Remainder); 363 Rem->dropAllReferences(); 364 Rem->eraseFromParent(); 365 366 // If we didn't actually generate an urem instruction, we're done 367 // This happens for example if the input were constant. In this case the 368 // Builder insertion point was unchanged 369 if (IsInsertPoint) 370 return true; 371 372 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 373 Rem = BO; 374 } 375 376 Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0), 377 Rem->getOperand(1), 378 Builder); 379 380 Rem->replaceAllUsesWith(Remainder); 381 Rem->dropAllReferences(); 382 Rem->eraseFromParent(); 383 384 // Expand the udiv 385 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) { 386 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?"); 387 expandDivision(UDiv); 388 } 389 390 return true; 391 } 392 393 /// Generate code to divide two integers, replacing Div with the generated 394 /// code. This currently generates code similarly to compiler-rt's 395 /// implementations, but future work includes generating more specialized code 396 /// when more information about the operands are known. 397 /// 398 /// Replace Div with generated code. 399 bool llvm::expandDivision(BinaryOperator *Div) { 400 assert((Div->getOpcode() == Instruction::SDiv || 401 Div->getOpcode() == Instruction::UDiv) && 402 "Trying to expand division from a non-division function"); 403 404 IRBuilder<> Builder(Div); 405 406 assert(!Div->getType()->isVectorTy() && "Div over vectors not supported"); 407 408 // First prepare the sign if it's a signed division 409 if (Div->getOpcode() == Instruction::SDiv) { 410 // Lower the code to unsigned division, and reset Div to point to the udiv. 411 Value *Quotient = generateSignedDivisionCode(Div->getOperand(0), 412 Div->getOperand(1), Builder); 413 414 // Check whether this is the insert point while Div is still valid. 415 bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint(); 416 Div->replaceAllUsesWith(Quotient); 417 Div->dropAllReferences(); 418 Div->eraseFromParent(); 419 420 // If we didn't actually generate an udiv instruction, we're done 421 // This happens for example if the input were constant. In this case the 422 // Builder insertion point was unchanged 423 if (IsInsertPoint) 424 return true; 425 426 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 427 Div = BO; 428 } 429 430 // Insert the unsigned division code 431 Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0), 432 Div->getOperand(1), 433 Builder); 434 Div->replaceAllUsesWith(Quotient); 435 Div->dropAllReferences(); 436 Div->eraseFromParent(); 437 438 return true; 439 } 440 441 /// Generate code to compute the remainder of two integers of bitwidth up to 442 /// 32 bits. Uses the above routines and extends the inputs/truncates the 443 /// outputs to operate in 32 bits; that is, these routines are good for targets 444 /// that have no or very little suppport for smaller than 32 bit integer 445 /// arithmetic. 446 /// 447 /// Replace Rem with emulation code. 448 bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) { 449 assert((Rem->getOpcode() == Instruction::SRem || 450 Rem->getOpcode() == Instruction::URem) && 451 "Trying to expand remainder from a non-remainder function"); 452 453 Type *RemTy = Rem->getType(); 454 assert(!RemTy->isVectorTy() && "Div over vectors not supported"); 455 456 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth(); 457 458 assert(RemTyBitWidth <= 32 && 459 "Div of bitwidth greater than 32 not supported"); 460 461 if (RemTyBitWidth == 32) 462 return expandRemainder(Rem); 463 464 // If bitwidth smaller than 32 extend inputs, extend output and proceed 465 // with 32 bit division. 466 IRBuilder<> Builder(Rem); 467 468 Value *ExtDividend; 469 Value *ExtDivisor; 470 Value *ExtRem; 471 Value *Trunc; 472 Type *Int32Ty = Builder.getInt32Ty(); 473 474 if (Rem->getOpcode() == Instruction::SRem) { 475 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty); 476 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty); 477 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 478 } else { 479 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty); 480 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty); 481 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 482 } 483 Trunc = Builder.CreateTrunc(ExtRem, RemTy); 484 485 Rem->replaceAllUsesWith(Trunc); 486 Rem->dropAllReferences(); 487 Rem->eraseFromParent(); 488 489 return expandRemainder(cast<BinaryOperator>(ExtRem)); 490 } 491 492 /// Generate code to compute the remainder of two integers of bitwidth up to 493 /// 64 bits. Uses the above routines and extends the inputs/truncates the 494 /// outputs to operate in 64 bits. 495 /// 496 /// Replace Rem with emulation code. 497 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) { 498 assert((Rem->getOpcode() == Instruction::SRem || 499 Rem->getOpcode() == Instruction::URem) && 500 "Trying to expand remainder from a non-remainder function"); 501 502 Type *RemTy = Rem->getType(); 503 assert(!RemTy->isVectorTy() && "Div over vectors not supported"); 504 505 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth(); 506 507 if (RemTyBitWidth >= 64) 508 return expandRemainder(Rem); 509 510 // If bitwidth smaller than 64 extend inputs, extend output and proceed 511 // with 64 bit division. 512 IRBuilder<> Builder(Rem); 513 514 Value *ExtDividend; 515 Value *ExtDivisor; 516 Value *ExtRem; 517 Value *Trunc; 518 Type *Int64Ty = Builder.getInt64Ty(); 519 520 if (Rem->getOpcode() == Instruction::SRem) { 521 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty); 522 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty); 523 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 524 } else { 525 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty); 526 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty); 527 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 528 } 529 Trunc = Builder.CreateTrunc(ExtRem, RemTy); 530 531 Rem->replaceAllUsesWith(Trunc); 532 Rem->dropAllReferences(); 533 Rem->eraseFromParent(); 534 535 return expandRemainder(cast<BinaryOperator>(ExtRem)); 536 } 537 538 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the 539 /// above routines and extends the inputs/truncates the outputs to operate 540 /// in 32 bits; that is, these routines are good for targets that have no 541 /// or very little support for smaller than 32 bit integer arithmetic. 542 /// 543 /// Replace Div with emulation code. 544 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) { 545 assert((Div->getOpcode() == Instruction::SDiv || 546 Div->getOpcode() == Instruction::UDiv) && 547 "Trying to expand division from a non-division function"); 548 549 Type *DivTy = Div->getType(); 550 assert(!DivTy->isVectorTy() && "Div over vectors not supported"); 551 552 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth(); 553 554 assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported"); 555 556 if (DivTyBitWidth == 32) 557 return expandDivision(Div); 558 559 // If bitwidth smaller than 32 extend inputs, extend output and proceed 560 // with 32 bit division. 561 IRBuilder<> Builder(Div); 562 563 Value *ExtDividend; 564 Value *ExtDivisor; 565 Value *ExtDiv; 566 Value *Trunc; 567 Type *Int32Ty = Builder.getInt32Ty(); 568 569 if (Div->getOpcode() == Instruction::SDiv) { 570 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty); 571 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty); 572 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 573 } else { 574 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty); 575 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty); 576 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 577 } 578 Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 579 580 Div->replaceAllUsesWith(Trunc); 581 Div->dropAllReferences(); 582 Div->eraseFromParent(); 583 584 return expandDivision(cast<BinaryOperator>(ExtDiv)); 585 } 586 587 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the 588 /// above routines and extends the inputs/truncates the outputs to operate 589 /// in 64 bits. 590 /// 591 /// Replace Div with emulation code. 592 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) { 593 assert((Div->getOpcode() == Instruction::SDiv || 594 Div->getOpcode() == Instruction::UDiv) && 595 "Trying to expand division from a non-division function"); 596 597 Type *DivTy = Div->getType(); 598 assert(!DivTy->isVectorTy() && "Div over vectors not supported"); 599 600 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth(); 601 602 if (DivTyBitWidth >= 64) 603 return expandDivision(Div); 604 605 // If bitwidth smaller than 64 extend inputs, extend output and proceed 606 // with 64 bit division. 607 IRBuilder<> Builder(Div); 608 609 Value *ExtDividend; 610 Value *ExtDivisor; 611 Value *ExtDiv; 612 Value *Trunc; 613 Type *Int64Ty = Builder.getInt64Ty(); 614 615 if (Div->getOpcode() == Instruction::SDiv) { 616 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty); 617 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty); 618 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 619 } else { 620 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty); 621 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty); 622 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 623 } 624 Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 625 626 Div->replaceAllUsesWith(Trunc); 627 Div->dropAllReferences(); 628 Div->eraseFromParent(); 629 630 return expandDivision(cast<BinaryOperator>(ExtDiv)); 631 } 632