Home | History | Annotate | Download | only in Utils
      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   assert(!Rem->getType()->isVectorTy() && "Div over vectors not supported");
    384   assert((Rem->getType()->getIntegerBitWidth() == 32 ||
    385           Rem->getType()->getIntegerBitWidth() == 64) &&
    386          "Div of bitwidth other than 32 or 64 not supported");
    387 
    388   // First prepare the sign if it's a signed remainder
    389   if (Rem->getOpcode() == Instruction::SRem) {
    390     Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
    391                                                    Rem->getOperand(1), Builder);
    392 
    393     // Check whether this is the insert point while Rem is still valid.
    394     bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint();
    395     Rem->replaceAllUsesWith(Remainder);
    396     Rem->dropAllReferences();
    397     Rem->eraseFromParent();
    398 
    399     // If we didn't actually generate an urem instruction, we're done
    400     // This happens for example if the input were constant. In this case the
    401     // Builder insertion point was unchanged
    402     if (IsInsertPoint)
    403       return true;
    404 
    405     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
    406     Rem = BO;
    407   }
    408 
    409   Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
    410                                                     Rem->getOperand(1),
    411                                                     Builder);
    412 
    413   Rem->replaceAllUsesWith(Remainder);
    414   Rem->dropAllReferences();
    415   Rem->eraseFromParent();
    416 
    417   // Expand the udiv
    418   if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
    419     assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
    420     expandDivision(UDiv);
    421   }
    422 
    423   return true;
    424 }
    425 
    426 
    427 /// Generate code to divide two integers, replacing Div with the generated
    428 /// code. This currently generates code similarly to compiler-rt's
    429 /// implementations, but future work includes generating more specialized code
    430 /// when more information about the operands are known. Implements both
    431 /// 32bit and 64bit scalar division.
    432 ///
    433 /// @brief Replace Div with generated code.
    434 bool llvm::expandDivision(BinaryOperator *Div) {
    435   assert((Div->getOpcode() == Instruction::SDiv ||
    436           Div->getOpcode() == Instruction::UDiv) &&
    437          "Trying to expand division from a non-division function");
    438 
    439   IRBuilder<> Builder(Div);
    440 
    441   assert(!Div->getType()->isVectorTy() && "Div over vectors not supported");
    442   assert((Div->getType()->getIntegerBitWidth() == 32 ||
    443           Div->getType()->getIntegerBitWidth() == 64) &&
    444          "Div of bitwidth other than 32 or 64 not supported");
    445 
    446   // First prepare the sign if it's a signed division
    447   if (Div->getOpcode() == Instruction::SDiv) {
    448     // Lower the code to unsigned division, and reset Div to point to the udiv.
    449     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
    450                                                  Div->getOperand(1), Builder);
    451 
    452     // Check whether this is the insert point while Div is still valid.
    453     bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();
    454     Div->replaceAllUsesWith(Quotient);
    455     Div->dropAllReferences();
    456     Div->eraseFromParent();
    457 
    458     // If we didn't actually generate an udiv instruction, we're done
    459     // This happens for example if the input were constant. In this case the
    460     // Builder insertion point was unchanged
    461     if (IsInsertPoint)
    462       return true;
    463 
    464     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
    465     Div = BO;
    466   }
    467 
    468   // Insert the unsigned division code
    469   Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
    470                                                  Div->getOperand(1),
    471                                                  Builder);
    472   Div->replaceAllUsesWith(Quotient);
    473   Div->dropAllReferences();
    474   Div->eraseFromParent();
    475 
    476   return true;
    477 }
    478 
    479 /// Generate code to compute the remainder of two integers of bitwidth up to
    480 /// 32 bits. Uses the above routines and extends the inputs/truncates the
    481 /// outputs to operate in 32 bits; that is, these routines are good for targets
    482 /// that have no or very little suppport for smaller than 32 bit integer
    483 /// arithmetic.
    484 ///
    485 /// @brief Replace Rem with emulation code.
    486 bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
    487   assert((Rem->getOpcode() == Instruction::SRem ||
    488           Rem->getOpcode() == Instruction::URem) &&
    489           "Trying to expand remainder from a non-remainder function");
    490 
    491   Type *RemTy = Rem->getType();
    492   assert(!RemTy->isVectorTy() && "Div over vectors not supported");
    493 
    494   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
    495 
    496   assert(RemTyBitWidth <= 32 &&
    497          "Div of bitwidth greater than 32 not supported");
    498 
    499   if (RemTyBitWidth == 32)
    500     return expandRemainder(Rem);
    501 
    502   // If bitwidth smaller than 32 extend inputs, extend output and proceed
    503   // with 32 bit division.
    504   IRBuilder<> Builder(Rem);
    505 
    506   Value *ExtDividend;
    507   Value *ExtDivisor;
    508   Value *ExtRem;
    509   Value *Trunc;
    510   Type *Int32Ty = Builder.getInt32Ty();
    511 
    512   if (Rem->getOpcode() == Instruction::SRem) {
    513     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
    514     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
    515     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
    516   } else {
    517     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
    518     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
    519     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
    520   }
    521   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
    522 
    523   Rem->replaceAllUsesWith(Trunc);
    524   Rem->dropAllReferences();
    525   Rem->eraseFromParent();
    526 
    527   return expandRemainder(cast<BinaryOperator>(ExtRem));
    528 }
    529 
    530 /// Generate code to compute the remainder of two integers of bitwidth up to
    531 /// 64 bits. Uses the above routines and extends the inputs/truncates the
    532 /// outputs to operate in 64 bits.
    533 ///
    534 /// @brief Replace Rem with emulation code.
    535 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
    536   assert((Rem->getOpcode() == Instruction::SRem ||
    537           Rem->getOpcode() == Instruction::URem) &&
    538           "Trying to expand remainder from a non-remainder function");
    539 
    540   Type *RemTy = Rem->getType();
    541   assert(!RemTy->isVectorTy() && "Div over vectors not supported");
    542 
    543   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
    544 
    545   assert(RemTyBitWidth <= 64 && "Div of bitwidth greater than 64 not supported");
    546 
    547   if (RemTyBitWidth == 64)
    548     return expandRemainder(Rem);
    549 
    550   // If bitwidth smaller than 64 extend inputs, extend output and proceed
    551   // with 64 bit division.
    552   IRBuilder<> Builder(Rem);
    553 
    554   Value *ExtDividend;
    555   Value *ExtDivisor;
    556   Value *ExtRem;
    557   Value *Trunc;
    558   Type *Int64Ty = Builder.getInt64Ty();
    559 
    560   if (Rem->getOpcode() == Instruction::SRem) {
    561     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
    562     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
    563     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
    564   } else {
    565     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
    566     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
    567     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
    568   }
    569   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
    570 
    571   Rem->replaceAllUsesWith(Trunc);
    572   Rem->dropAllReferences();
    573   Rem->eraseFromParent();
    574 
    575   return expandRemainder(cast<BinaryOperator>(ExtRem));
    576 }
    577 
    578 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
    579 /// above routines and extends the inputs/truncates the outputs to operate
    580 /// in 32 bits; that is, these routines are good for targets that have no
    581 /// or very little support for smaller than 32 bit integer arithmetic.
    582 ///
    583 /// @brief Replace Div with emulation code.
    584 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
    585   assert((Div->getOpcode() == Instruction::SDiv ||
    586           Div->getOpcode() == Instruction::UDiv) &&
    587           "Trying to expand division from a non-division function");
    588 
    589   Type *DivTy = Div->getType();
    590   assert(!DivTy->isVectorTy() && "Div over vectors not supported");
    591 
    592   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
    593 
    594   assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported");
    595 
    596   if (DivTyBitWidth == 32)
    597     return expandDivision(Div);
    598 
    599   // If bitwidth smaller than 32 extend inputs, extend output and proceed
    600   // with 32 bit division.
    601   IRBuilder<> Builder(Div);
    602 
    603   Value *ExtDividend;
    604   Value *ExtDivisor;
    605   Value *ExtDiv;
    606   Value *Trunc;
    607   Type *Int32Ty = Builder.getInt32Ty();
    608 
    609   if (Div->getOpcode() == Instruction::SDiv) {
    610     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
    611     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
    612     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
    613   } else {
    614     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
    615     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
    616     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
    617   }
    618   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
    619 
    620   Div->replaceAllUsesWith(Trunc);
    621   Div->dropAllReferences();
    622   Div->eraseFromParent();
    623 
    624   return expandDivision(cast<BinaryOperator>(ExtDiv));
    625 }
    626 
    627 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
    628 /// above routines and extends the inputs/truncates the outputs to operate
    629 /// in 64 bits.
    630 ///
    631 /// @brief Replace Div with emulation code.
    632 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
    633   assert((Div->getOpcode() == Instruction::SDiv ||
    634           Div->getOpcode() == Instruction::UDiv) &&
    635           "Trying to expand division from a non-division function");
    636 
    637   Type *DivTy = Div->getType();
    638   assert(!DivTy->isVectorTy() && "Div over vectors not supported");
    639 
    640   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
    641 
    642   assert(DivTyBitWidth <= 64 &&
    643          "Div of bitwidth greater than 64 not supported");
    644 
    645   if (DivTyBitWidth == 64)
    646     return expandDivision(Div);
    647 
    648   // If bitwidth smaller than 64 extend inputs, extend output and proceed
    649   // with 64 bit division.
    650   IRBuilder<> Builder(Div);
    651 
    652   Value *ExtDividend;
    653   Value *ExtDivisor;
    654   Value *ExtDiv;
    655   Value *Trunc;
    656   Type *Int64Ty = Builder.getInt64Ty();
    657 
    658   if (Div->getOpcode() == Instruction::SDiv) {
    659     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
    660     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
    661     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
    662   } else {
    663     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
    664     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
    665     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
    666   }
    667   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
    668 
    669   Div->replaceAllUsesWith(Trunc);
    670   Div->dropAllReferences();
    671   Div->eraseFromParent();
    672 
    673   return expandDivision(cast<BinaryOperator>(ExtDiv));
    674 }
    675