lib/Transforms/Utils/IntegerDivision.cpp

   1 //===-- IntegerDivision.cpp - Expand integer division ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains an implementation of 32bit scalar integer division for
  11 // targets that don't have native support. It's largely derived from
  12 // compiler-rt's implementation of __udivsi3, but hand-tuned to reduce the
  13 // amount of control flow
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "integer-division"
  18 #include "llvm/Function.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Intrinsics.h"
  21 #include "llvm/IRBuilder.h"
  22 #include "llvm/Transforms/Utils/IntegerDivision.h"
  23
  24 using namespace llvm;
  25
  26 /// Generate code to divide two signed integers. Returns the quotient, rounded
  27 /// towards 0. Builder's insert point should be pointing at the sdiv
  28 /// instruction. This will generate a udiv in the process, and Builder's insert
  29 /// point will be pointing at the udiv (if present, i.e. not folded), ready to
  30 /// be expanded if the user wishes.
  31 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
  32                                          IRBuilder<> &Builder) {
  33   // Implementation taken from compiler-rt's __divsi3
  34
  35   ConstantInt *ThirtyOne = Builder.getInt32(31);
  36
  37   // ;   %tmp    = ashr i32 %dividend, 31
  38   // ;   %tmp1   = ashr i32 %divisor, 31
  39   // ;   %tmp2   = xor i32 %tmp, %dividend
  40   // ;   %u_dvnd = sub nsw i32 %tmp2, %tmp
  41   // ;   %tmp3   = xor i32 %tmp1, %divisor
  42   // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1
  43   // ;   %q_sgn  = xor i32 %tmp1, %tmp
  44   // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr
  45   // ;   %tmp4   = xor i32 %q_mag, %q_sgn
  46   // ;   %q      = sub i32 %tmp4, %q_sgn
  47   Value *Tmp    = Builder.CreateAShr(Dividend, ThirtyOne);
  48   Value *Tmp1   = Builder.CreateAShr(Divisor, ThirtyOne);
  49   Value *Tmp2   = Builder.CreateXor(Tmp, Dividend);
  50   Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
  51   Value *Tmp3   = Builder.CreateXor(Tmp1, Divisor);
  52   Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
  53   Value *Q_Sgn  = Builder.CreateXor(Tmp1, Tmp);
  54   Value *Q_Mag  = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
  55   Value *Tmp4   = Builder.CreateXor(Q_Mag, Q_Sgn);
  56   Value *Q      = Builder.CreateSub(Tmp4, Q_Sgn);
  57
  58   if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
  59     Builder.SetInsertPoint(UDiv);
  60
  61   return Q;
  62 }
  63
  64 /// Generates code to divide two unsigned scalar 32-bit integers. Returns the
  65 /// quotient, rounded towards 0. Builder's insert point should be pointing at
  66 /// the udiv instruction.
  67 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
  68                                            IRBuilder<> &Builder) {
  69   // The basic algorithm can be found in the compiler-rt project's
  70   // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
  71   // that's been hand-tuned to lessen the amount of control flow involved.
  72
  73   // Some helper values
  74   IntegerType *I32Ty = Builder.getInt32Ty();
  75
  76   ConstantInt *Zero      = Builder.getInt32(0);
  77   ConstantInt *One       = Builder.getInt32(1);
  78   ConstantInt *ThirtyOne = Builder.getInt32(31);
  79   ConstantInt *NegOne    = ConstantInt::getSigned(I32Ty, -1);
  80   ConstantInt *True      = Builder.getTrue();
  81
  82   BasicBlock *IBB = Builder.GetInsertBlock();
  83   Function *F = IBB->getParent();
  84   Function *CTLZi32 = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
  85                                                 I32Ty);
  86
  87   // Our CFG is going to look like:
  88   // +---------------------+
  89   // | special-cases       |
  90   // |   ...               |
  91   // +---------------------+
  92   //  |       |
  93   //  |   +----------+
  94   //  |   |  bb1     |
  95   //  |   |  ...     |
  96   //  |   +----------+
  97   //  |    |      |
  98   //  |    |  +------------+
  99   //  |    |  |  preheader |
 100   //  |    |  |  ...       |
 101   //  |    |  +------------+
 102   //  |    |      |
 103   //  |    |      |      +---+
 104   //  |    |      |      |   |
 105   //  |    |  +------------+ |
 106   //  |    |  |  do-while  | |
 107   //  |    |  |  ...       | |
 108   //  |    |  +------------+ |
 109   //  |    |      |      |   |
 110   //  |   +-----------+  +---+
 111   //  |   | loop-exit |
 112   //  |   |  ...      |
 113   //  |   +-----------+
 114   //  |     |
 115   // +-------+
 116   // | ...   |
 117   // | end   |
 118   // +-------+
 119   BasicBlock *SpecialCases = Builder.GetInsertBlock();
 120   SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
 121   BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
 122                                                   "udiv-end");
 123   BasicBlock *LoopExit  = BasicBlock::Create(Builder.getContext(),
 124                                              "udiv-loop-exit", F, End);
 125   BasicBlock *DoWhile   = BasicBlock::Create(Builder.getContext(),
 126                                              "udiv-do-while", F, End);
 127   BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
 128                                              "udiv-preheader", F, End);
 129   BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(),
 130                                              "udiv-bb1", F, End);
 131
 132   // We'll be overwriting the terminator to insert our extra blocks
 133   SpecialCases->getTerminator()->eraseFromParent();
 134
 135   // First off, check for special cases: dividend or divisor is zero, divisor
 136   // is greater than dividend, and divisor is 1.
 137   // ; special-cases:
 138   // ;   %ret0_1      = icmp eq i32 %divisor, 0
 139   // ;   %ret0_2      = icmp eq i32 %dividend, 0
 140   // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
 141   // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
 142   // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
 143   // ;   %sr          = sub nsw i32 %tmp0, %tmp1
 144   // ;   %ret0_4      = icmp ugt i32 %sr, 31
 145   // ;   %ret0        = or i1 %ret0_3, %ret0_4
 146   // ;   %retDividend = icmp eq i32 %sr, 31
 147   // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
 148   // ;   %earlyRet    = or i1 %ret0, %retDividend
 149   // ;   br i1 %earlyRet, label %end, label %bb1
 150   Builder.SetInsertPoint(SpecialCases);
 151   Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero);
 152   Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero);
 153   Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2);
 154   Value *Tmp0        = Builder.CreateCall2(CTLZi32, Divisor, True);
 155   Value *Tmp1        = Builder.CreateCall2(CTLZi32, Dividend, True);
 156   Value *SR          = Builder.CreateSub(Tmp0, Tmp1);
 157   Value *Ret0_4      = Builder.CreateICmpUGT(SR, ThirtyOne);
 158   Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4);
 159   Value *RetDividend = Builder.CreateICmpEQ(SR, ThirtyOne);
 160   Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
 161   Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
 162   Builder.CreateCondBr(EarlyRet, End, BB1);
 163
 164   // ; bb1:                                             ; preds = %special-cases
 165   // ;   %sr_1     = add i32 %sr, 1
 166   // ;   %tmp2     = sub i32 31, %sr
 167   // ;   %q        = shl i32 %dividend, %tmp2
 168   // ;   %skipLoop = icmp eq i32 %sr_1, 0
 169   // ;   br i1 %skipLoop, label %loop-exit, label %preheader
 170   Builder.SetInsertPoint(BB1);
 171   Value *SR_1     = Builder.CreateAdd(SR, One);
 172   Value *Tmp2     = Builder.CreateSub(ThirtyOne, SR);
 173   Value *Q        = Builder.CreateShl(Dividend, Tmp2);
 174   Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
 175   Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
 176
 177   // ; preheader:                                           ; preds = %bb1
 178   // ;   %tmp3 = lshr i32 %dividend, %sr_1
 179   // ;   %tmp4 = add i32 %divisor, -1
 180   // ;   br label %do-while
 181   Builder.SetInsertPoint(Preheader);
 182   Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
 183   Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
 184   Builder.CreateBr(DoWhile);
 185
 186   // ; do-while:                                 ; preds = %do-while, %preheader
 187   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
 188   // ;   %sr_3    = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
 189   // ;   %r_1     = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
 190   // ;   %q_2     = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
 191   // ;   %tmp5  = shl i32 %r_1, 1
 192   // ;   %tmp6  = lshr i32 %q_2, 31
 193   // ;   %tmp7  = or i32 %tmp5, %tmp6
 194   // ;   %tmp8  = shl i32 %q_2, 1
 195   // ;   %q_1   = or i32 %carry_1, %tmp8
 196   // ;   %tmp9  = sub i32 %tmp4, %tmp7
 197   // ;   %tmp10 = ashr i32 %tmp9, 31
 198   // ;   %carry = and i32 %tmp10, 1
 199   // ;   %tmp11 = and i32 %tmp10, %divisor
 200   // ;   %r     = sub i32 %tmp7, %tmp11
 201   // ;   %sr_2  = add i32 %sr_3, -1
 202   // ;   %tmp12 = icmp eq i32 %sr_2, 0
 203   // ;   br i1 %tmp12, label %loop-exit, label %do-while
 204   Builder.SetInsertPoint(DoWhile);
 205   PHINode *Carry_1 = Builder.CreatePHI(I32Ty, 2);
 206   PHINode *SR_3    = Builder.CreatePHI(I32Ty, 2);
 207   PHINode *R_1     = Builder.CreatePHI(I32Ty, 2);
 208   PHINode *Q_2     = Builder.CreatePHI(I32Ty, 2);
 209   Value *Tmp5  = Builder.CreateShl(R_1, One);
 210   Value *Tmp6  = Builder.CreateLShr(Q_2, ThirtyOne);
 211   Value *Tmp7  = Builder.CreateOr(Tmp5, Tmp6);
 212   Value *Tmp8  = Builder.CreateShl(Q_2, One);
 213   Value *Q_1   = Builder.CreateOr(Carry_1, Tmp8);
 214   Value *Tmp9  = Builder.CreateSub(Tmp4, Tmp7);
 215   Value *Tmp10 = Builder.CreateAShr(Tmp9, 31);
 216   Value *Carry = Builder.CreateAnd(Tmp10, One);
 217   Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
 218   Value *R     = Builder.CreateSub(Tmp7, Tmp11);
 219   Value *SR_2  = Builder.CreateAdd(SR_3, NegOne);
 220   Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
 221   Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
 222
 223   // ; loop-exit:                                      ; preds = %do-while, %bb1
 224   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
 225   // ;   %q_3     = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
 226   // ;   %tmp13 = shl i32 %q_3, 1
 227   // ;   %q_4   = or i32 %carry_2, %tmp13
 228   // ;   br label %end
 229   Builder.SetInsertPoint(LoopExit);
 230   PHINode *Carry_2 = Builder.CreatePHI(I32Ty, 2);
 231   PHINode *Q_3     = Builder.CreatePHI(I32Ty, 2);
 232   Value *Tmp13 = Builder.CreateShl(Q_3, One);
 233   Value *Q_4   = Builder.CreateOr(Carry_2, Tmp13);
 234   Builder.CreateBr(End);
 235
 236   // ; end:                                 ; preds = %loop-exit, %special-cases
 237   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
 238   // ;   ret i32 %q_5
 239   Builder.SetInsertPoint(End, End->begin());
 240   PHINode *Q_5 = Builder.CreatePHI(I32Ty, 2);
 241
 242   // Populate the Phis, since all values have now been created. Our Phis were:
 243   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
 244   Carry_1->addIncoming(Zero, Preheader);
 245   Carry_1->addIncoming(Carry, DoWhile);
 246   // ;   %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
 247   SR_3->addIncoming(SR_1, Preheader);
 248   SR_3->addIncoming(SR_2, DoWhile);
 249   // ;   %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
 250   R_1->addIncoming(Tmp3, Preheader);
 251   R_1->addIncoming(R, DoWhile);
 252   // ;   %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
 253   Q_2->addIncoming(Q, Preheader);
 254   Q_2->addIncoming(Q_1, DoWhile);
 255   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
 256   Carry_2->addIncoming(Zero, BB1);
 257   Carry_2->addIncoming(Carry, DoWhile);
 258   // ;   %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
 259   Q_3->addIncoming(Q, BB1);
 260   Q_3->addIncoming(Q_1, DoWhile);
 261   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
 262   Q_5->addIncoming(Q_4, LoopExit);
 263   Q_5->addIncoming(RetVal, SpecialCases);
 264
 265   return Q_5;
 266 }
 267
 268 /// Generate code to divide two integers, replacing Div with the generated
 269 /// code. This currently generates code similarly to compiler-rt's
 270 /// implementations, but future work includes generating more specialized code
 271 /// when more information about the operands are known. Currently only
 272 /// implements 32bit scalar division, but future work is removing this
 273 /// limitation.
 274 ///
 275 /// @brief Replace Div with generated code.
 276 bool llvm::expandDivision(BinaryOperator *Div) {
 277   assert((Div->getOpcode() == Instruction::SDiv ||
 278           Div->getOpcode() == Instruction::UDiv) &&
 279          "Trying to expand division from a non-division function");
 280
 281   IRBuilder<> Builder(Div);
 282
 283   if (Div->getType()->isVectorTy())
 284     llvm_unreachable("Div over vectors not supported");
 285
 286   // First prepare the sign if it's a signed division
 287   if (Div->getOpcode() == Instruction::SDiv) {
 288     // Lower the code to unsigned division, and reset Div to point to the udiv.
 289     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
 290                                                 Div->getOperand(1), Builder);
 291     Div->replaceAllUsesWith(Quotient);
 292     Div->dropAllReferences();
 293     Div->eraseFromParent();
 294
 295     // If we didn't actually generate a udiv instruction, we're done
 296     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
 297     if (!BO || BO->getOpcode() != Instruction::UDiv)
 298       return true;
 299
 300     Div = BO;
 301   }
 302
 303   // Insert the unsigned division code
 304   Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
 305                                                  Div->getOperand(1),
 306                                                  Builder);
 307   Div->replaceAllUsesWith(Quotient);
 308   Div->dropAllReferences();
 309   Div->eraseFromParent();
 310
 311   return true;
 312 }