IntegerDivision.cpp revision 1c1ab8f53d91506f0590dc1d2448ae438e00b8c6
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 24using 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 be 30// expanded if the user wishes. 31static 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 the 66// udiv instruction. 67static 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 268bool llvm::expandDivision(BinaryOperator* Div) { 269 assert((Div->getOpcode() == Instruction::SDiv || 270 Div->getOpcode() == Instruction::UDiv) && 271 "Trying to expand division from a non-division function"); 272 273 IRBuilder<> Builder(Div); 274 275 if (Div->getType()->isVectorTy()) 276 llvm_unreachable("Div over vectors not supported"); 277 278 // First prepare the sign if it's a signed division 279 if (Div->getOpcode() == Instruction::SDiv) { 280 // Lower the code to unsigned division, and reset Div to point to the udiv. 281 Value* Quotient = GenerateSignedDivisionCode(Div->getOperand(0), 282 Div->getOperand(1), Builder); 283 Div->replaceAllUsesWith(Quotient); 284 Div->dropAllReferences(); 285 Div->eraseFromParent(); 286 287 // If we didn't actually generate a udiv instruction, we're done 288 BinaryOperator* BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 289 if (!BO || BO->getOpcode() != Instruction::UDiv) 290 return true; 291 292 Div = BO; 293 } 294 295 // Insert the unsigned division code 296 Value* Quotient = GenerateUnsignedDivisionCode(Div->getOperand(0), 297 Div->getOperand(1), 298 Builder); 299 Div->replaceAllUsesWith(Quotient); 300 Div->dropAllReferences(); 301 Div->eraseFromParent(); 302 303 return true; 304} 305