LLVM API Documentation

IntegerDivision.cpp
Go to the documentation of this file.
00001 //===-- IntegerDivision.cpp - Expand integer division ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains an implementation of 32bit and 64bit scalar integer
00011 // division for targets that don't have native support. It's largely derived
00012 // from compiler-rt's implementations of __udivsi3 and __udivmoddi4,
00013 // but hand-tuned for targets that prefer less control flow.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "llvm/Transforms/Utils/IntegerDivision.h"
00018 #include "llvm/IR/Function.h"
00019 #include "llvm/IR/IRBuilder.h"
00020 #include "llvm/IR/Instructions.h"
00021 #include "llvm/IR/Intrinsics.h"
00022 #include <utility>
00023 
00024 using namespace llvm;
00025 
00026 #define DEBUG_TYPE "integer-division"
00027 
00028 /// Generate code to compute the remainder of two signed integers. Returns the
00029 /// remainder, which will have the sign of the dividend. Builder's insert point
00030 /// should be pointing where the caller wants code generated, e.g. at the srem
00031 /// instruction. This will generate a urem in the process, and Builder's insert
00032 /// point will be pointing at the uren (if present, i.e. not folded), ready to
00033 /// be expanded if the user wishes
00034 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
00035                                           IRBuilder<> &Builder) {
00036   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
00037   ConstantInt *Shift;
00038 
00039   if (BitWidth == 64) {
00040     Shift = Builder.getInt64(63);
00041   } else {
00042     assert(BitWidth == 32 && "Unexpected bit width");
00043     Shift = Builder.getInt32(31);
00044   }
00045 
00046   // Following instructions are generated for both i32 (shift 31) and
00047   // i64 (shift 63).
00048 
00049   // ;   %dividend_sgn = ashr i32 %dividend, 31
00050   // ;   %divisor_sgn  = ashr i32 %divisor, 31
00051   // ;   %dvd_xor      = xor i32 %dividend, %dividend_sgn
00052   // ;   %dvs_xor      = xor i32 %divisor, %divisor_sgn
00053   // ;   %u_dividend   = sub i32 %dvd_xor, %dividend_sgn
00054   // ;   %u_divisor    = sub i32 %dvs_xor, %divisor_sgn
00055   // ;   %urem         = urem i32 %dividend, %divisor
00056   // ;   %xored        = xor i32 %urem, %dividend_sgn
00057   // ;   %srem         = sub i32 %xored, %dividend_sgn
00058   Value *DividendSign = Builder.CreateAShr(Dividend, Shift);
00059   Value *DivisorSign  = Builder.CreateAShr(Divisor, Shift);
00060   Value *DvdXor       = Builder.CreateXor(Dividend, DividendSign);
00061   Value *DvsXor       = Builder.CreateXor(Divisor, DivisorSign);
00062   Value *UDividend    = Builder.CreateSub(DvdXor, DividendSign);
00063   Value *UDivisor     = Builder.CreateSub(DvsXor, DivisorSign);
00064   Value *URem         = Builder.CreateURem(UDividend, UDivisor);
00065   Value *Xored        = Builder.CreateXor(URem, DividendSign);
00066   Value *SRem         = Builder.CreateSub(Xored, DividendSign);
00067 
00068   if (Instruction *URemInst = dyn_cast<Instruction>(URem))
00069     Builder.SetInsertPoint(URemInst);
00070 
00071   return SRem;
00072 }
00073 
00074 
00075 /// Generate code to compute the remainder of two unsigned integers. Returns the
00076 /// remainder. Builder's insert point should be pointing where the caller wants
00077 /// code generated, e.g. at the urem instruction. This will generate a udiv in
00078 /// the process, and Builder's insert point will be pointing at the udiv (if
00079 /// present, i.e. not folded), ready to be expanded if the user wishes
00080 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
00081                                              IRBuilder<> &Builder) {
00082   // Remainder = Dividend - Quotient*Divisor
00083 
00084   // Following instructions are generated for both i32 and i64
00085 
00086   // ;   %quotient  = udiv i32 %dividend, %divisor
00087   // ;   %product   = mul i32 %divisor, %quotient
00088   // ;   %remainder = sub i32 %dividend, %product
00089   Value *Quotient  = Builder.CreateUDiv(Dividend, Divisor);
00090   Value *Product   = Builder.CreateMul(Divisor, Quotient);
00091   Value *Remainder = Builder.CreateSub(Dividend, Product);
00092 
00093   if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
00094     Builder.SetInsertPoint(UDiv);
00095 
00096   return Remainder;
00097 }
00098 
00099 /// Generate code to divide two signed integers. Returns the quotient, rounded
00100 /// towards 0. Builder's insert point should be pointing where the caller wants
00101 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
00102 /// the process, and Builder's insert point will be pointing at the udiv (if
00103 /// present, i.e. not folded), ready to be expanded if the user wishes.
00104 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
00105                                          IRBuilder<> &Builder) {
00106   // Implementation taken from compiler-rt's __divsi3 and __divdi3
00107 
00108   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
00109   ConstantInt *Shift;
00110 
00111   if (BitWidth == 64) {
00112     Shift = Builder.getInt64(63);
00113   } else {
00114     assert(BitWidth == 32 && "Unexpected bit width");
00115     Shift = Builder.getInt32(31);
00116   }
00117 
00118   // Following instructions are generated for both i32 (shift 31) and
00119   // i64 (shift 63).
00120 
00121   // ;   %tmp    = ashr i32 %dividend, 31
00122   // ;   %tmp1   = ashr i32 %divisor, 31
00123   // ;   %tmp2   = xor i32 %tmp, %dividend
00124   // ;   %u_dvnd = sub nsw i32 %tmp2, %tmp
00125   // ;   %tmp3   = xor i32 %tmp1, %divisor
00126   // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1
00127   // ;   %q_sgn  = xor i32 %tmp1, %tmp
00128   // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr
00129   // ;   %tmp4   = xor i32 %q_mag, %q_sgn
00130   // ;   %q      = sub i32 %tmp4, %q_sgn
00131   Value *Tmp    = Builder.CreateAShr(Dividend, Shift);
00132   Value *Tmp1   = Builder.CreateAShr(Divisor, Shift);
00133   Value *Tmp2   = Builder.CreateXor(Tmp, Dividend);
00134   Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
00135   Value *Tmp3   = Builder.CreateXor(Tmp1, Divisor);
00136   Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
00137   Value *Q_Sgn  = Builder.CreateXor(Tmp1, Tmp);
00138   Value *Q_Mag  = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
00139   Value *Tmp4   = Builder.CreateXor(Q_Mag, Q_Sgn);
00140   Value *Q      = Builder.CreateSub(Tmp4, Q_Sgn);
00141 
00142   if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
00143     Builder.SetInsertPoint(UDiv);
00144 
00145   return Q;
00146 }
00147 
00148 /// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
00149 /// Returns the quotient, rounded towards 0. Builder's insert point should
00150 /// point where the caller wants code generated, e.g. at the udiv instruction.
00151 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
00152                                            IRBuilder<> &Builder) {
00153   // The basic algorithm can be found in the compiler-rt project's
00154   // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
00155   // that's been hand-tuned to lessen the amount of control flow involved.
00156 
00157   // Some helper values
00158   IntegerType *DivTy = cast<IntegerType>(Dividend->getType());
00159   unsigned BitWidth = DivTy->getBitWidth();
00160 
00161   ConstantInt *Zero;
00162   ConstantInt *One;
00163   ConstantInt *NegOne;
00164   ConstantInt *MSB;
00165 
00166   if (BitWidth == 64) {
00167     Zero      = Builder.getInt64(0);
00168     One       = Builder.getInt64(1);
00169     NegOne    = ConstantInt::getSigned(DivTy, -1);
00170     MSB       = Builder.getInt64(63);
00171   } else {
00172     assert(BitWidth == 32 && "Unexpected bit width");
00173     Zero      = Builder.getInt32(0);
00174     One       = Builder.getInt32(1);
00175     NegOne    = ConstantInt::getSigned(DivTy, -1);
00176     MSB       = Builder.getInt32(31);
00177   }
00178 
00179   ConstantInt *True = Builder.getTrue();
00180 
00181   BasicBlock *IBB = Builder.GetInsertBlock();
00182   Function *F = IBB->getParent();
00183   Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
00184                                              DivTy);
00185 
00186   // Our CFG is going to look like:
00187   // +---------------------+
00188   // | special-cases       |
00189   // |   ...               |
00190   // +---------------------+
00191   //  |       |
00192   //  |   +----------+
00193   //  |   |  bb1     |
00194   //  |   |  ...     |
00195   //  |   +----------+
00196   //  |    |      |
00197   //  |    |  +------------+
00198   //  |    |  |  preheader |
00199   //  |    |  |  ...       |
00200   //  |    |  +------------+
00201   //  |    |      |
00202   //  |    |      |      +---+
00203   //  |    |      |      |   |
00204   //  |    |  +------------+ |
00205   //  |    |  |  do-while  | |
00206   //  |    |  |  ...       | |
00207   //  |    |  +------------+ |
00208   //  |    |      |      |   |
00209   //  |   +-----------+  +---+
00210   //  |   | loop-exit |
00211   //  |   |  ...      |
00212   //  |   +-----------+
00213   //  |     |
00214   // +-------+
00215   // | ...   |
00216   // | end   |
00217   // +-------+
00218   BasicBlock *SpecialCases = Builder.GetInsertBlock();
00219   SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
00220   BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
00221                                                   "udiv-end");
00222   BasicBlock *LoopExit  = BasicBlock::Create(Builder.getContext(),
00223                                              "udiv-loop-exit", F, End);
00224   BasicBlock *DoWhile   = BasicBlock::Create(Builder.getContext(),
00225                                              "udiv-do-while", F, End);
00226   BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
00227                                              "udiv-preheader", F, End);
00228   BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(),
00229                                              "udiv-bb1", F, End);
00230 
00231   // We'll be overwriting the terminator to insert our extra blocks
00232   SpecialCases->getTerminator()->eraseFromParent();
00233 
00234   // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
00235 
00236   // First off, check for special cases: dividend or divisor is zero, divisor
00237   // is greater than dividend, and divisor is 1.
00238   // ; special-cases:
00239   // ;   %ret0_1      = icmp eq i32 %divisor, 0
00240   // ;   %ret0_2      = icmp eq i32 %dividend, 0
00241   // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
00242   // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
00243   // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
00244   // ;   %sr          = sub nsw i32 %tmp0, %tmp1
00245   // ;   %ret0_4      = icmp ugt i32 %sr, 31
00246   // ;   %ret0        = or i1 %ret0_3, %ret0_4
00247   // ;   %retDividend = icmp eq i32 %sr, 31
00248   // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
00249   // ;   %earlyRet    = or i1 %ret0, %retDividend
00250   // ;   br i1 %earlyRet, label %end, label %bb1
00251   Builder.SetInsertPoint(SpecialCases);
00252   Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero);
00253   Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero);
00254   Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2);
00255   Value *Tmp0        = Builder.CreateCall2(CTLZ, Divisor, True);
00256   Value *Tmp1        = Builder.CreateCall2(CTLZ, Dividend, True);
00257   Value *SR          = Builder.CreateSub(Tmp0, Tmp1);
00258   Value *Ret0_4      = Builder.CreateICmpUGT(SR, MSB);
00259   Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4);
00260   Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
00261   Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
00262   Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
00263   Builder.CreateCondBr(EarlyRet, End, BB1);
00264 
00265   // ; bb1:                                             ; preds = %special-cases
00266   // ;   %sr_1     = add i32 %sr, 1
00267   // ;   %tmp2     = sub i32 31, %sr
00268   // ;   %q        = shl i32 %dividend, %tmp2
00269   // ;   %skipLoop = icmp eq i32 %sr_1, 0
00270   // ;   br i1 %skipLoop, label %loop-exit, label %preheader
00271   Builder.SetInsertPoint(BB1);
00272   Value *SR_1     = Builder.CreateAdd(SR, One);
00273   Value *Tmp2     = Builder.CreateSub(MSB, SR);
00274   Value *Q        = Builder.CreateShl(Dividend, Tmp2);
00275   Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
00276   Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
00277 
00278   // ; preheader:                                           ; preds = %bb1
00279   // ;   %tmp3 = lshr i32 %dividend, %sr_1
00280   // ;   %tmp4 = add i32 %divisor, -1
00281   // ;   br label %do-while
00282   Builder.SetInsertPoint(Preheader);
00283   Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
00284   Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
00285   Builder.CreateBr(DoWhile);
00286 
00287   // ; do-while:                                 ; preds = %do-while, %preheader
00288   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
00289   // ;   %sr_3    = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
00290   // ;   %r_1     = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
00291   // ;   %q_2     = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
00292   // ;   %tmp5  = shl i32 %r_1, 1
00293   // ;   %tmp6  = lshr i32 %q_2, 31
00294   // ;   %tmp7  = or i32 %tmp5, %tmp6
00295   // ;   %tmp8  = shl i32 %q_2, 1
00296   // ;   %q_1   = or i32 %carry_1, %tmp8
00297   // ;   %tmp9  = sub i32 %tmp4, %tmp7
00298   // ;   %tmp10 = ashr i32 %tmp9, 31
00299   // ;   %carry = and i32 %tmp10, 1
00300   // ;   %tmp11 = and i32 %tmp10, %divisor
00301   // ;   %r     = sub i32 %tmp7, %tmp11
00302   // ;   %sr_2  = add i32 %sr_3, -1
00303   // ;   %tmp12 = icmp eq i32 %sr_2, 0
00304   // ;   br i1 %tmp12, label %loop-exit, label %do-while
00305   Builder.SetInsertPoint(DoWhile);
00306   PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);
00307   PHINode *SR_3    = Builder.CreatePHI(DivTy, 2);
00308   PHINode *R_1     = Builder.CreatePHI(DivTy, 2);
00309   PHINode *Q_2     = Builder.CreatePHI(DivTy, 2);
00310   Value *Tmp5  = Builder.CreateShl(R_1, One);
00311   Value *Tmp6  = Builder.CreateLShr(Q_2, MSB);
00312   Value *Tmp7  = Builder.CreateOr(Tmp5, Tmp6);
00313   Value *Tmp8  = Builder.CreateShl(Q_2, One);
00314   Value *Q_1   = Builder.CreateOr(Carry_1, Tmp8);
00315   Value *Tmp9  = Builder.CreateSub(Tmp4, Tmp7);
00316   Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);
00317   Value *Carry = Builder.CreateAnd(Tmp10, One);
00318   Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
00319   Value *R     = Builder.CreateSub(Tmp7, Tmp11);
00320   Value *SR_2  = Builder.CreateAdd(SR_3, NegOne);
00321   Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
00322   Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
00323 
00324   // ; loop-exit:                                      ; preds = %do-while, %bb1
00325   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
00326   // ;   %q_3     = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
00327   // ;   %tmp13 = shl i32 %q_3, 1
00328   // ;   %q_4   = or i32 %carry_2, %tmp13
00329   // ;   br label %end
00330   Builder.SetInsertPoint(LoopExit);
00331   PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);
00332   PHINode *Q_3     = Builder.CreatePHI(DivTy, 2);
00333   Value *Tmp13 = Builder.CreateShl(Q_3, One);
00334   Value *Q_4   = Builder.CreateOr(Carry_2, Tmp13);
00335   Builder.CreateBr(End);
00336 
00337   // ; end:                                 ; preds = %loop-exit, %special-cases
00338   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
00339   // ;   ret i32 %q_5
00340   Builder.SetInsertPoint(End, End->begin());
00341   PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);
00342 
00343   // Populate the Phis, since all values have now been created. Our Phis were:
00344   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
00345   Carry_1->addIncoming(Zero, Preheader);
00346   Carry_1->addIncoming(Carry, DoWhile);
00347   // ;   %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
00348   SR_3->addIncoming(SR_1, Preheader);
00349   SR_3->addIncoming(SR_2, DoWhile);
00350   // ;   %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
00351   R_1->addIncoming(Tmp3, Preheader);
00352   R_1->addIncoming(R, DoWhile);
00353   // ;   %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
00354   Q_2->addIncoming(Q, Preheader);
00355   Q_2->addIncoming(Q_1, DoWhile);
00356   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
00357   Carry_2->addIncoming(Zero, BB1);
00358   Carry_2->addIncoming(Carry, DoWhile);
00359   // ;   %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
00360   Q_3->addIncoming(Q, BB1);
00361   Q_3->addIncoming(Q_1, DoWhile);
00362   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
00363   Q_5->addIncoming(Q_4, LoopExit);
00364   Q_5->addIncoming(RetVal, SpecialCases);
00365 
00366   return Q_5;
00367 }
00368 
00369 /// Generate code to calculate the remainder of two integers, replacing Rem with
00370 /// the generated code. This currently generates code using the udiv expansion,
00371 /// but future work includes generating more specialized code, e.g. when more
00372 /// information about the operands are known. Implements both 32bit and 64bit
00373 /// scalar division.
00374 ///
00375 /// @brief Replace Rem with generated code.
00376 bool llvm::expandRemainder(BinaryOperator *Rem) {
00377   assert((Rem->getOpcode() == Instruction::SRem ||
00378           Rem->getOpcode() == Instruction::URem) &&
00379          "Trying to expand remainder from a non-remainder function");
00380 
00381   IRBuilder<> Builder(Rem);
00382 
00383   Type *RemTy = Rem->getType();
00384   if (RemTy->isVectorTy())
00385     llvm_unreachable("Div over vectors not supported");
00386 
00387   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
00388 
00389   if (RemTyBitWidth != 32 && RemTyBitWidth != 64)
00390     llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
00391 
00392   // First prepare the sign if it's a signed remainder
00393   if (Rem->getOpcode() == Instruction::SRem) {
00394     Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
00395                                                    Rem->getOperand(1), Builder);
00396 
00397     Rem->replaceAllUsesWith(Remainder);
00398     Rem->dropAllReferences();
00399     Rem->eraseFromParent();
00400 
00401     // If we didn't actually generate an urem instruction, we're done
00402     // This happens for example if the input were constant. In this case the
00403     // Builder insertion point was unchanged
00404     if (Rem == Builder.GetInsertPoint())
00405       return true;
00406 
00407     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
00408     Rem = BO;
00409   }
00410 
00411   Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
00412                                                     Rem->getOperand(1),
00413                                                     Builder);
00414 
00415   Rem->replaceAllUsesWith(Remainder);
00416   Rem->dropAllReferences();
00417   Rem->eraseFromParent();
00418 
00419   // Expand the udiv
00420   if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
00421     assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
00422     expandDivision(UDiv);
00423   }
00424 
00425   return true;
00426 }
00427 
00428 
00429 /// Generate code to divide two integers, replacing Div with the generated
00430 /// code. This currently generates code similarly to compiler-rt's
00431 /// implementations, but future work includes generating more specialized code
00432 /// when more information about the operands are known. Implements both
00433 /// 32bit and 64bit scalar division.
00434 ///
00435 /// @brief Replace Div with generated code.
00436 bool llvm::expandDivision(BinaryOperator *Div) {
00437   assert((Div->getOpcode() == Instruction::SDiv ||
00438           Div->getOpcode() == Instruction::UDiv) &&
00439          "Trying to expand division from a non-division function");
00440 
00441   IRBuilder<> Builder(Div);
00442 
00443   Type *DivTy = Div->getType();
00444   if (DivTy->isVectorTy())
00445     llvm_unreachable("Div over vectors not supported");
00446 
00447   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
00448 
00449   if (DivTyBitWidth != 32 && DivTyBitWidth != 64)
00450     llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
00451 
00452   // First prepare the sign if it's a signed division
00453   if (Div->getOpcode() == Instruction::SDiv) {
00454     // Lower the code to unsigned division, and reset Div to point to the udiv.
00455     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
00456                                                  Div->getOperand(1), Builder);
00457     Div->replaceAllUsesWith(Quotient);
00458     Div->dropAllReferences();
00459     Div->eraseFromParent();
00460 
00461     // If we didn't actually generate an udiv instruction, we're done
00462     // This happens for example if the input were constant. In this case the
00463     // Builder insertion point was unchanged
00464     if (Div == Builder.GetInsertPoint())
00465       return true;
00466 
00467     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
00468     Div = BO;
00469   }
00470 
00471   // Insert the unsigned division code
00472   Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
00473                                                  Div->getOperand(1),
00474                                                  Builder);
00475   Div->replaceAllUsesWith(Quotient);
00476   Div->dropAllReferences();
00477   Div->eraseFromParent();
00478 
00479   return true;
00480 }
00481 
00482 /// Generate code to compute the remainder of two integers of bitwidth up to 
00483 /// 32 bits. Uses the above routines and extends the inputs/truncates the
00484 /// outputs to operate in 32 bits; that is, these routines are good for targets
00485 /// that have no or very little suppport for smaller than 32 bit integer 
00486 /// arithmetic.
00487 ///
00488 /// @brief Replace Rem with emulation code.
00489 bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
00490   assert((Rem->getOpcode() == Instruction::SRem ||
00491           Rem->getOpcode() == Instruction::URem) &&
00492           "Trying to expand remainder from a non-remainder function");
00493 
00494   Type *RemTy = Rem->getType();
00495   if (RemTy->isVectorTy())
00496     llvm_unreachable("Div over vectors not supported");
00497 
00498   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
00499 
00500   if (RemTyBitWidth > 32) 
00501     llvm_unreachable("Div of bitwidth greater than 32 not supported");
00502 
00503   if (RemTyBitWidth == 32) 
00504     return expandRemainder(Rem);
00505 
00506   // If bitwidth smaller than 32 extend inputs, extend output and proceed
00507   // with 32 bit division.
00508   IRBuilder<> Builder(Rem);
00509 
00510   Value *ExtDividend;
00511   Value *ExtDivisor;
00512   Value *ExtRem;
00513   Value *Trunc;
00514   Type *Int32Ty = Builder.getInt32Ty();
00515 
00516   if (Rem->getOpcode() == Instruction::SRem) {
00517     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
00518     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
00519     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
00520   } else {
00521     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
00522     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
00523     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
00524   }
00525   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
00526 
00527   Rem->replaceAllUsesWith(Trunc);
00528   Rem->dropAllReferences();
00529   Rem->eraseFromParent();
00530 
00531   return expandRemainder(cast<BinaryOperator>(ExtRem));
00532 }
00533 
00534 /// Generate code to compute the remainder of two integers of bitwidth up to 
00535 /// 64 bits. Uses the above routines and extends the inputs/truncates the
00536 /// outputs to operate in 64 bits.
00537 ///
00538 /// @brief Replace Rem with emulation code.
00539 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
00540   assert((Rem->getOpcode() == Instruction::SRem ||
00541           Rem->getOpcode() == Instruction::URem) &&
00542           "Trying to expand remainder from a non-remainder function");
00543 
00544   Type *RemTy = Rem->getType();
00545   if (RemTy->isVectorTy())
00546     llvm_unreachable("Div over vectors not supported");
00547 
00548   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
00549 
00550   if (RemTyBitWidth > 64) 
00551     llvm_unreachable("Div of bitwidth greater than 64 not supported");
00552 
00553   if (RemTyBitWidth == 64) 
00554     return expandRemainder(Rem);
00555 
00556   // If bitwidth smaller than 64 extend inputs, extend output and proceed
00557   // with 64 bit division.
00558   IRBuilder<> Builder(Rem);
00559 
00560   Value *ExtDividend;
00561   Value *ExtDivisor;
00562   Value *ExtRem;
00563   Value *Trunc;
00564   Type *Int64Ty = Builder.getInt64Ty();
00565 
00566   if (Rem->getOpcode() == Instruction::SRem) {
00567     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
00568     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
00569     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
00570   } else {
00571     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
00572     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
00573     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
00574   }
00575   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
00576 
00577   Rem->replaceAllUsesWith(Trunc);
00578   Rem->dropAllReferences();
00579   Rem->eraseFromParent();
00580 
00581   return expandRemainder(cast<BinaryOperator>(ExtRem));
00582 }
00583 
00584 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
00585 /// above routines and extends the inputs/truncates the outputs to operate
00586 /// in 32 bits; that is, these routines are good for targets that have no
00587 /// or very little support for smaller than 32 bit integer arithmetic.
00588 ///
00589 /// @brief Replace Div with emulation code.
00590 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
00591   assert((Div->getOpcode() == Instruction::SDiv ||
00592           Div->getOpcode() == Instruction::UDiv) &&
00593           "Trying to expand division from a non-division function");
00594 
00595   Type *DivTy = Div->getType();
00596   if (DivTy->isVectorTy())
00597     llvm_unreachable("Div over vectors not supported");
00598 
00599   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
00600 
00601   if (DivTyBitWidth > 32)
00602     llvm_unreachable("Div of bitwidth greater than 32 not supported");
00603 
00604   if (DivTyBitWidth == 32)
00605     return expandDivision(Div);
00606 
00607   // If bitwidth smaller than 32 extend inputs, extend output and proceed
00608   // with 32 bit division.
00609   IRBuilder<> Builder(Div);
00610 
00611   Value *ExtDividend;
00612   Value *ExtDivisor;
00613   Value *ExtDiv;
00614   Value *Trunc;
00615   Type *Int32Ty = Builder.getInt32Ty();
00616 
00617   if (Div->getOpcode() == Instruction::SDiv) {
00618     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
00619     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
00620     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
00621   } else {
00622     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
00623     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
00624     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);  
00625   }
00626   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
00627 
00628   Div->replaceAllUsesWith(Trunc);
00629   Div->dropAllReferences();
00630   Div->eraseFromParent();
00631 
00632   return expandDivision(cast<BinaryOperator>(ExtDiv));
00633 }
00634 
00635 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
00636 /// above routines and extends the inputs/truncates the outputs to operate
00637 /// in 64 bits.
00638 ///
00639 /// @brief Replace Div with emulation code.
00640 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
00641   assert((Div->getOpcode() == Instruction::SDiv ||
00642           Div->getOpcode() == Instruction::UDiv) &&
00643           "Trying to expand division from a non-division function");
00644 
00645   Type *DivTy = Div->getType();
00646   if (DivTy->isVectorTy())
00647     llvm_unreachable("Div over vectors not supported");
00648 
00649   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
00650 
00651   if (DivTyBitWidth > 64)
00652     llvm_unreachable("Div of bitwidth greater than 64 not supported");
00653 
00654   if (DivTyBitWidth == 64)
00655     return expandDivision(Div);
00656 
00657   // If bitwidth smaller than 64 extend inputs, extend output and proceed
00658   // with 64 bit division.
00659   IRBuilder<> Builder(Div);
00660 
00661   Value *ExtDividend;
00662   Value *ExtDivisor;
00663   Value *ExtDiv;
00664   Value *Trunc;
00665   Type *Int64Ty = Builder.getInt64Ty();
00666 
00667   if (Div->getOpcode() == Instruction::SDiv) {
00668     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
00669     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
00670     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
00671   } else {
00672     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
00673     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
00674     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);  
00675   }
00676   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
00677 
00678   Div->replaceAllUsesWith(Trunc);
00679   Div->dropAllReferences();
00680   Div->eraseFromParent();
00681 
00682   return expandDivision(cast<BinaryOperator>(ExtDiv));
00683 }