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