llvm/lib/Transforms/Utils/IntegerDivision.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-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   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 the
  69 /// remainder. Builder's insert point should be pointing where the caller wants
  70 /// code generated, e.g. at the urem instruction. This will generate a udiv in
  71 /// the process, and Builder's insert point will be pointing at the udiv (if
  72 /// present, i.e. not folded), ready to be expanded if the user wishes
  73 static Value *generateUnsignedRemainderCode(Value *Dividend, Value *Divisor,
  74                                             IRBuilder<> &Builder) {
  75   // Remainder = Dividend - Quotient*Divisor
  76
  77   // Following instructions are generated for both i32 and i64
  78
  79   // ;   %quotient  = udiv i32 %dividend, %divisor
  80   // ;   %product   = mul i32 %divisor, %quotient
  81   // ;   %remainder = sub i32 %dividend, %product
  82   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, rounded
  95 /// towards 0. Builder's insert point should be pointing where the caller wants
  96 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
  97 /// the process, and Builder's insert point will be pointing at the udiv (if
  98 /// present, i.e. not folded), ready to be expanded if the user wishes.
  99 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
 100                                          IRBuilder<> &Builder) {
 101   // Implementation taken from compiler-rt's __divsi3 and __divdi3
 102
 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) and
 107   // i64 (shift 63).
 108
 109   // ;   %tmp    = ashr i32 %dividend, 31
 110   // ;   %tmp1   = ashr i32 %divisor, 31
 111   // ;   %tmp2   = xor i32 %tmp, %dividend
 112   // ;   %u_dvnd = sub nsw i32 %tmp2, %tmp
 113   // ;   %tmp3   = xor i32 %tmp1, %divisor
 114   // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1
 115   // ;   %q_sgn  = xor i32 %tmp1, %tmp
 116   // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr
 117   // ;   %tmp4   = xor i32 %q_mag, %q_sgn
 118   // ;   %q      = sub i32 %tmp4, %q_sgn
 119   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 should
 140 /// point where the caller wants code generated, e.g. at the udiv instruction.
 141 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
 142                                            IRBuilder<> &Builder) {
 143   // The basic algorithm can be found in the compiler-rt project's
 144   // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
 145   // that's been hand-tuned to lessen the amount of control flow involved.
 146
 147   // Some helper values
 148   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 blocks
 209   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, divisor
 214   // is greater than dividend, and divisor is 1.
 215   // ; special-cases:
 216   // ;   %ret0_1      = icmp eq i32 %divisor, 0
 217   // ;   %ret0_2      = icmp eq i32 %dividend, 0
 218   // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
 219   // ;   %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, %tmp1
 222   // ;   %ret0_4      = icmp ugt i32 %sr, 31
 223   // ;   %ret0        = select i1 %ret0_3, i1 true, i1 %ret0_4
 224   // ;   %retDividend = icmp eq i32 %sr, 31
 225   // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
 226   // ;   %earlyRet    = select i1 %ret0, i1 true, %retDividend
 227   // ;   br i1 %earlyRet, label %end, label %bb1
 228   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-cases
 245   // ;   %sr_1     = add i32 %sr, 1
 246   // ;   %tmp2     = sub i32 31, %sr
 247   // ;   %q        = shl i32 %dividend, %tmp2
 248   // ;   %skipLoop = icmp eq i32 %sr_1, 0
 249   // ;   br i1 %skipLoop, label %loop-exit, label %preheader
 250   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 = %bb1
 258   // ;   %tmp3 = lshr i32 %dividend, %sr_1
 259   // ;   %tmp4 = add i32 %divisor, -1
 260   // ;   br label %do-while
 261   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, %preheader
 267   // ;   %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, 1
 272   // ;   %tmp6  = lshr i32 %q_2, 31
 273   // ;   %tmp7  = or i32 %tmp5, %tmp6
 274   // ;   %tmp8  = shl i32 %q_2, 1
 275   // ;   %q_1   = or i32 %carry_1, %tmp8
 276   // ;   %tmp9  = sub i32 %tmp4, %tmp7
 277   // ;   %tmp10 = ashr i32 %tmp9, 31
 278   // ;   %carry = and i32 %tmp10, 1
 279   // ;   %tmp11 = and i32 %tmp10, %divisor
 280   // ;   %r     = sub i32 %tmp7, %tmp11
 281   // ;   %sr_2  = add i32 %sr_3, -1
 282   // ;   %tmp12 = icmp eq i32 %sr_2, 0
 283   // ;   br i1 %tmp12, label %loop-exit, label %do-while
 284   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, %bb1
 304   // ;   %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, 1
 307   // ;   %q_4   = or i32 %carry_2, %tmp13
 308   // ;   br label %end
 309   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-cases
 317   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
 318   // ;   ret i32 %q_5
 319   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 with
 349 /// the generated code. This currently generates code using the udiv expansion,
 350 /// but future work includes generating more specialized code, e.g. when more
 351 /// information about the operands are known.
 352 ///
 353 /// Replace Rem with generated code.
 354 bool 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 remainder
 364   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 done
 375     // This happens for example if the input were constant. In this case the
 376     // Builder insertion point was unchanged
 377     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 udiv
 392   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 generated
 401 /// code. This currently generates code similarly to compiler-rt's
 402 /// implementations, but future work includes generating more specialized code
 403 /// when more information about the operands are known.
 404 ///
 405 /// Replace Div with generated code.
 406 bool 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 division
 416   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 done
 428     // This happens for example if the input were constant. In this case the
 429     // Builder insertion point was unchanged
 430     if (IsInsertPoint)
 431       return true;
 432
 433     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
 434     Div = BO;
 435   }
 436
 437   // Insert the unsigned division code
 438   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 to
 449 /// 32 bits. Uses the above routines and extends the inputs/truncates the
 450 /// outputs to operate in 32 bits; that is, these routines are good for targets
 451 /// that have no or very little suppport for smaller than 32 bit integer
 452 /// arithmetic.
 453 ///
 454 /// Replace Rem with emulation code.
 455 bool 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 proceed
 472   // 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 to
 500 /// 64 bits. Uses the above routines and extends the inputs/truncates the
 501 /// outputs to operate in 64 bits.
 502 ///
 503 /// Replace Rem with emulation code.
 504 bool 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 proceed
 518   // 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 the
 546 /// above routines and extends the inputs/truncates the outputs to operate
 547 /// in 32 bits; that is, these routines are good for targets that have no
 548 /// or very little support for smaller than 32 bit integer arithmetic.
 549 ///
 550 /// Replace Div with emulation code.
 551 bool 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 proceed
 567   // 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 the
 595 /// above routines and extends the inputs/truncates the outputs to operate
 596 /// in 64 bits.
 597 ///
 598 /// Replace Div with emulation code.
 599 bool 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 proceed
 613   // 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 }