lib/Transforms/Utils/IntegerDivision.cpp

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