//===-- IntegerDivision.cpp - Expand integer division ---------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file contains an implementation of 32bit scalar integer division for // targets that don't have native support. It's largely derived from // compiler-rt's implementation of __udivsi3, but hand-tuned to reduce the // amount of control flow // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "integer-division" #include "llvm/Function.h" #include "llvm/Instructions.h" #include "llvm/Intrinsics.h" #include "llvm/IRBuilder.h" #include "llvm/Transforms/Utils/IntegerDivision.h" using namespace llvm; // Generate code to divide two signed integers. Returns the quotient, rounded // towards 0. Builder's insert point should be pointing at the sdiv // instruction. This will generate a udiv in the process, and Builder's insert // point will be pointing at the udiv (if present, i.e. not folded), ready to be // expanded if the user wishes. static Value* GenerateSignedDivisionCode(Value* Dividend, Value* Divisor, IRBuilder<>& Builder) { // Implementation taken from compiler-rt's __divsi3 ConstantInt* ThirtyOne = Builder.getInt32(31); // ; %tmp = ashr i32 %dividend, 31 // ; %tmp1 = ashr i32 %divisor, 31 // ; %tmp2 = xor i32 %tmp, %dividend // ; %u_dvnd = sub nsw i32 %tmp2, %tmp // ; %tmp3 = xor i32 %tmp1, %divisor // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1 // ; %q_sgn = xor i32 %tmp1, %tmp // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr // ; %tmp4 = xor i32 %q_mag, %q_sgn // ; %q = sub i32 %tmp4, %q_sgn Value* Tmp = Builder.CreateAShr(Dividend, ThirtyOne); Value* Tmp1 = Builder.CreateAShr(Divisor, ThirtyOne); Value* Tmp2 = Builder.CreateXor(Tmp, Dividend); Value* U_Dvnd = Builder.CreateSub(Tmp2, Tmp); Value* Tmp3 = Builder.CreateXor(Tmp1, Divisor); Value* U_Dvsr = Builder.CreateSub(Tmp3, Tmp1); Value* Q_Sgn = Builder.CreateXor(Tmp1, Tmp); Value* Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr); Value* Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn); Value* Q = Builder.CreateSub(Tmp4, Q_Sgn); if (Instruction* UDiv = dyn_cast(Q_Mag)) Builder.SetInsertPoint(UDiv); return Q; } // Generates code to divide two unsigned scalar 32-bit integers. Returns the // quotient, rounded towards 0. Builder's insert point should be pointing at the // udiv instruction. static Value* GenerateUnsignedDivisionCode(Value* Dividend, Value* Divisor, IRBuilder<>& Builder) { // The basic algorithm can be found in the compiler-rt project's // implementation of __udivsi3.c. Here, we do a lower-level IR based approach // that's been hand-tuned to lessen the amount of control flow involved. // Some helper values IntegerType* I32Ty = Builder.getInt32Ty(); ConstantInt* Zero = Builder.getInt32(0); ConstantInt* One = Builder.getInt32(1); ConstantInt* ThirtyOne = Builder.getInt32(31); ConstantInt* NegOne = ConstantInt::getSigned(I32Ty, -1); ConstantInt* True = Builder.getTrue(); BasicBlock* IBB = Builder.GetInsertBlock(); Function* F = IBB->getParent(); Function* CTLZi32 = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz, I32Ty); // Our CFG is going to look like: // +---------------------+ // | special-cases | // | ... | // +---------------------+ // | | // | +----------+ // | | bb1 | // | | ... | // | +----------+ // | | | // | | +------------+ // | | | preheader | // | | | ... | // | | +------------+ // | | | // | | | +---+ // | | | | | // | | +------------+ | // | | | do-while | | // | | | ... | | // | | +------------+ | // | | | | | // | +-----------+ +---+ // | | loop-exit | // | | ... | // | +-----------+ // | | // +-------+ // | ... | // | end | // +-------+ BasicBlock* SpecialCases = Builder.GetInsertBlock(); SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases")); BasicBlock* End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(), "udiv-end"); BasicBlock* LoopExit = BasicBlock::Create(Builder.getContext(), "udiv-loop-exit", F, End); BasicBlock* DoWhile = BasicBlock::Create(Builder.getContext(), "udiv-do-while", F, End); BasicBlock* Preheader = BasicBlock::Create(Builder.getContext(), "udiv-preheader", F, End); BasicBlock* BB1 = BasicBlock::Create(Builder.getContext(), "udiv-bb1", F, End); // We'll be overwriting the terminator to insert our extra blocks SpecialCases->getTerminator()->eraseFromParent(); // First off, check for special cases: dividend or divisor is zero, divisor // is greater than dividend, and divisor is 1. // ; special-cases: // ; %ret0_1 = icmp eq i32 %divisor, 0 // ; %ret0_2 = icmp eq i32 %dividend, 0 // ; %ret0_3 = or i1 %ret0_1, %ret0_2 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true) // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true) // ; %sr = sub nsw i32 %tmp0, %tmp1 // ; %ret0_4 = icmp ugt i32 %sr, 31 // ; %ret0 = or i1 %ret0_3, %ret0_4 // ; %retDividend = icmp eq i32 %sr, 31 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend // ; %earlyRet = or i1 %ret0, %retDividend // ; br i1 %earlyRet, label %end, label %bb1 Builder.SetInsertPoint(SpecialCases); Value* Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero); Value* Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero); Value* Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2); Value* Tmp0 = Builder.CreateCall2(CTLZi32, Divisor, True); Value* Tmp1 = Builder.CreateCall2(CTLZi32, Dividend, True); Value* SR = Builder.CreateSub(Tmp0, Tmp1); Value* Ret0_4 = Builder.CreateICmpUGT(SR, ThirtyOne); Value* Ret0 = Builder.CreateOr(Ret0_3, Ret0_4); Value* RetDividend = Builder.CreateICmpEQ(SR, ThirtyOne); Value* RetVal = Builder.CreateSelect(Ret0, Zero, Dividend); Value* EarlyRet = Builder.CreateOr(Ret0, RetDividend); Builder.CreateCondBr(EarlyRet, End, BB1); // ; bb1: ; preds = %special-cases // ; %sr_1 = add i32 %sr, 1 // ; %tmp2 = sub i32 31, %sr // ; %q = shl i32 %dividend, %tmp2 // ; %skipLoop = icmp eq i32 %sr_1, 0 // ; br i1 %skipLoop, label %loop-exit, label %preheader Builder.SetInsertPoint(BB1); Value* SR_1 = Builder.CreateAdd(SR, One); Value* Tmp2 = Builder.CreateSub(ThirtyOne, SR); Value* Q = Builder.CreateShl(Dividend, Tmp2); Value* SkipLoop = Builder.CreateICmpEQ(SR_1, Zero); Builder.CreateCondBr(SkipLoop, LoopExit, Preheader); // ; preheader: ; preds = %bb1 // ; %tmp3 = lshr i32 %dividend, %sr_1 // ; %tmp4 = add i32 %divisor, -1 // ; br label %do-while Builder.SetInsertPoint(Preheader); Value* Tmp3 = Builder.CreateLShr(Dividend, SR_1); Value* Tmp4 = Builder.CreateAdd(Divisor, NegOne); Builder.CreateBr(DoWhile); // ; do-while: ; preds = %do-while, %preheader // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] // ; %tmp5 = shl i32 %r_1, 1 // ; %tmp6 = lshr i32 %q_2, 31 // ; %tmp7 = or i32 %tmp5, %tmp6 // ; %tmp8 = shl i32 %q_2, 1 // ; %q_1 = or i32 %carry_1, %tmp8 // ; %tmp9 = sub i32 %tmp4, %tmp7 // ; %tmp10 = ashr i32 %tmp9, 31 // ; %carry = and i32 %tmp10, 1 // ; %tmp11 = and i32 %tmp10, %divisor // ; %r = sub i32 %tmp7, %tmp11 // ; %sr_2 = add i32 %sr_3, -1 // ; %tmp12 = icmp eq i32 %sr_2, 0 // ; br i1 %tmp12, label %loop-exit, label %do-while Builder.SetInsertPoint(DoWhile); PHINode* Carry_1 = Builder.CreatePHI(I32Ty, 2); PHINode* SR_3 = Builder.CreatePHI(I32Ty, 2); PHINode* R_1 = Builder.CreatePHI(I32Ty, 2); PHINode* Q_2 = Builder.CreatePHI(I32Ty, 2); Value* Tmp5 = Builder.CreateShl(R_1, One); Value* Tmp6 = Builder.CreateLShr(Q_2, ThirtyOne); Value* Tmp7 = Builder.CreateOr(Tmp5, Tmp6); Value* Tmp8 = Builder.CreateShl(Q_2, One); Value* Q_1 = Builder.CreateOr(Carry_1, Tmp8); Value* Tmp9 = Builder.CreateSub(Tmp4, Tmp7); Value* Tmp10 = Builder.CreateAShr(Tmp9, 31); Value* Carry = Builder.CreateAnd(Tmp10, One); Value* Tmp11 = Builder.CreateAnd(Tmp10, Divisor); Value* R = Builder.CreateSub(Tmp7, Tmp11); Value* SR_2 = Builder.CreateAdd(SR_3, NegOne); Value* Tmp12 = Builder.CreateICmpEQ(SR_2, Zero); Builder.CreateCondBr(Tmp12, LoopExit, DoWhile); // ; loop-exit: ; preds = %do-while, %bb1 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] // ; %tmp13 = shl i32 %q_3, 1 // ; %q_4 = or i32 %carry_2, %tmp13 // ; br label %end Builder.SetInsertPoint(LoopExit); PHINode* Carry_2 = Builder.CreatePHI(I32Ty, 2); PHINode* Q_3 = Builder.CreatePHI(I32Ty, 2); Value* Tmp13 = Builder.CreateShl(Q_3, One); Value* Q_4 = Builder.CreateOr(Carry_2, Tmp13); Builder.CreateBr(End); // ; end: ; preds = %loop-exit, %special-cases // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] // ; ret i32 %q_5 Builder.SetInsertPoint(End, End->begin()); PHINode* Q_5 = Builder.CreatePHI(I32Ty, 2); // Populate the Phis, since all values have now been created. Our Phis were: // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] Carry_1->addIncoming(Zero, Preheader); Carry_1->addIncoming(Carry, DoWhile); // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] SR_3->addIncoming(SR_1, Preheader); SR_3->addIncoming(SR_2, DoWhile); // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] R_1->addIncoming(Tmp3, Preheader); R_1->addIncoming(R, DoWhile); // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] Q_2->addIncoming(Q, Preheader); Q_2->addIncoming(Q_1, DoWhile); // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] Carry_2->addIncoming(Zero, BB1); Carry_2->addIncoming(Carry, DoWhile); // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] Q_3->addIncoming(Q, BB1); Q_3->addIncoming(Q_1, DoWhile); // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] Q_5->addIncoming(Q_4, LoopExit); Q_5->addIncoming(RetVal, SpecialCases); return Q_5; } bool llvm::expandDivision(BinaryOperator* Div) { assert(Div->getOpcode() == Instruction::SDiv || Div->getOpcode() == Instruction::UDiv && "Trying to expand division from a non-division function"); IRBuilder<> Builder(Div); if (Div->getType()->isVectorTy()) { assert(0 && "Div over vectors not supported"); return false; } // First prepare the sign if it's a signed division if (Div->getOpcode() == Instruction::SDiv) { // Lower the code to unsigned division, and reset Div to point to the udiv. Value* Quotient = GenerateSignedDivisionCode(Div->getOperand(0), Div->getOperand(1), Builder); Div->replaceAllUsesWith(Quotient); Div->dropAllReferences(); Div->eraseFromParent(); // If we didn't actually generate a udiv instruction, we're done BinaryOperator* BO = dyn_cast(Builder.GetInsertPoint()); if (!BO || BO->getOpcode() != Instruction::UDiv) return true; Div = BO; } // Insert the unsigned division code Value* Quotient = GenerateUnsignedDivisionCode(Div->getOperand(0), Div->getOperand(1), Builder); Div->replaceAllUsesWith(Quotient); Div->dropAllReferences(); Div->eraseFromParent(); return true; }