From b55462bcfb9acbf8654dff83159daf695dfc3ec4 Mon Sep 17 00:00:00 2001 From: Michael Ilseman Date: Wed, 26 Sep 2012 01:55:01 +0000 Subject: Expansions for u/srem, using the udiv expansion. More unit tests for udiv and u/srem. Fixed issue with Release build. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164654 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/IntegerDivision.h | 10 ++ lib/Transforms/Utils/IntegerDivision.cpp | 122 ++++++++++++++++++++++-- unittests/Transforms/Utils/IntegerDivision.cpp | 96 +++++++++++++++++++ 3 files changed, 221 insertions(+), 7 deletions(-) diff --git a/include/llvm/Transforms/Utils/IntegerDivision.h b/include/llvm/Transforms/Utils/IntegerDivision.h index 8d3f53e6f9..cecc8075de 100644 --- a/include/llvm/Transforms/Utils/IntegerDivision.h +++ b/include/llvm/Transforms/Utils/IntegerDivision.h @@ -23,6 +23,16 @@ namespace llvm { namespace llvm { + /// Generate code to calculate the remainder of two integers, replacing Rem + /// with the generated code. This currently generates code using the udiv + /// expansion, but future work includes generating more specialized code, + /// e.g. when more information about the operands are known. Currently only + /// implements 32bit scalar division (due to udiv's limitation), but future + /// work is removing this limitation. + /// + /// @brief Replace Rem with generated code. + bool expandRemainder(BinaryOperator *Rem); + /// Generate code to divide two integers, replacing Div with the generated /// code. This currently generates code similarly to compiler-rt's /// implementations, but future work includes generating more specialized code diff --git a/lib/Transforms/Utils/IntegerDivision.cpp b/lib/Transforms/Utils/IntegerDivision.cpp index 9d630349ab..55227e2714 100644 --- a/lib/Transforms/Utils/IntegerDivision.cpp +++ b/lib/Transforms/Utils/IntegerDivision.cpp @@ -23,11 +23,69 @@ using namespace llvm; +/// Generate code to compute the remainder of two signed integers. Returns the +/// remainder, which will have the sign of the dividend. Builder's insert point +/// should be pointing where the caller wants code generated, e.g. at the srem +/// instruction. This will generate a urem in the process, and Builder's insert +/// point will be pointing at the uren (if present, i.e. not folded), ready to +/// be expanded if the user wishes +static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor, + IRBuilder<> &Builder) { + ConstantInt *ThirtyOne = Builder.getInt32(31); + + // ; %dividend_sgn = ashr i32 %dividend, 31 + // ; %divisor_sgn = ashr i32 %divisor, 31 + // ; %dvd_xor = xor i32 %dividend, %dividend_sgn + // ; %dvs_xor = xor i32 %divisor, %divisor_sgn + // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn + // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn + // ; %urem = urem i32 %dividend, %divisor + // ; %xored = xor i32 %urem, %dividend_sgn + // ; %srem = sub i32 %xored, %dividend_sgn + Value *DividendSign = Builder.CreateAShr(Dividend, ThirtyOne); + Value *DivisorSign = Builder.CreateAShr(Divisor, ThirtyOne); + Value *DvdXor = Builder.CreateXor(Dividend, DividendSign); + Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign); + Value *UDividend = Builder.CreateSub(DvdXor, DividendSign); + Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign); + Value *URem = Builder.CreateURem(UDividend, UDivisor); + Value *Xored = Builder.CreateXor(URem, DividendSign); + Value *SRem = Builder.CreateSub(Xored, DividendSign); + + if (Instruction *URemInst = dyn_cast(URem)) + Builder.SetInsertPoint(URemInst); + + return SRem; +} + + +/// Generate code to compute the remainder of two unsigned integers. Returns the +/// remainder. Builder's insert point should be pointing where the caller wants +/// code generated, e.g. at the urem 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 *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, + IRBuilder<> &Builder) { + // Remainder = Dividend - Quotient*Divisor + + // ; %quotient = udiv i32 %dividend, %divisor + // ; %product = mul i32 %divisor, %quotient + // ; %remainder = sub i32 %dividend, %product + Value *Quotient = Builder.CreateUDiv(Dividend, Divisor); + Value *Product = Builder.CreateMul(Divisor, Quotient); + Value *Remainder = Builder.CreateSub(Dividend, Product); + + if (Instruction *UDiv = dyn_cast(Quotient)) + Builder.SetInsertPoint(UDiv); + + return Remainder; +} + /// 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. +/// towards 0. Builder's insert point should be pointing where the caller wants +/// code generated, e.g. 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 @@ -62,8 +120,8 @@ static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor, } /// 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. +/// quotient, rounded towards 0. Builder's insert point should be pointing where +/// the caller wants code generated, e.g. 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 @@ -265,6 +323,56 @@ static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, return Q_5; } +/// Generate code to calculate the remainder of two integers, replacing Rem with +/// the generated code. This currently generates code using the udiv expansion, +/// but future work includes generating more specialized code, e.g. when more +/// information about the operands are known. Currently only implements 32bit +/// scalar division (due to udiv's limitation), but future work is removing this +/// limitation. +/// +/// @brief Replace Rem with generated code. +bool llvm::expandRemainder(BinaryOperator *Rem) { + assert((Rem->getOpcode() == Instruction::SRem || + Rem->getOpcode() == Instruction::URem) && + "Trying to expand remainder from a non-remainder function"); + + IRBuilder<> Builder(Rem); + + // First prepare the sign if it's a signed remainder + if (Rem->getOpcode() == Instruction::SRem) { + Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0), + Rem->getOperand(1), Builder); + + Rem->replaceAllUsesWith(Remainder); + Rem->dropAllReferences(); + Rem->eraseFromParent(); + + // If we didn't actually generate a udiv instruction, we're done + BinaryOperator *BO = dyn_cast(Builder.GetInsertPoint()); + if (!BO || BO->getOpcode() != Instruction::URem) + return true; + + Rem = BO; + } + + Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0), + Rem->getOperand(1), + Builder); + + Rem->replaceAllUsesWith(Remainder); + Rem->dropAllReferences(); + Rem->eraseFromParent(); + + // Expand the udiv + if (BinaryOperator *UDiv = dyn_cast(Builder.GetInsertPoint())) { + assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?"); + expandDivision(UDiv); + } + + return true; +} + + /// Generate code to divide two integers, replacing Div with the generated /// code. This currently generates code similarly to compiler-rt's /// implementations, but future work includes generating more specialized code @@ -287,7 +395,7 @@ bool llvm::expandDivision(BinaryOperator *Div) { 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->getOperand(1), Builder); Div->replaceAllUsesWith(Quotient); Div->dropAllReferences(); Div->eraseFromParent(); diff --git a/unittests/Transforms/Utils/IntegerDivision.cpp b/unittests/Transforms/Utils/IntegerDivision.cpp index a026b343d2..e5b84b893d 100644 --- a/unittests/Transforms/Utils/IntegerDivision.cpp +++ b/unittests/Transforms/Utils/IntegerDivision.cpp @@ -51,4 +51,100 @@ TEST(IntegerDivision, SDiv) { Builder.SetInsertPoint(BB->end()); } +TEST(IntegerDivision, UDiv) { + LLVMContext &C(getGlobalContext()); + Module M("test division", C); + IRBuilder<> Builder(C); + + SmallVector ArgTys(2, Builder.getInt32Ty()); + Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), + ArgTys, false), + GlobalValue::ExternalLinkage, "F", &M); + assert(F->getArgumentList().size() == 2); + + BasicBlock *BB = BasicBlock::Create(C, "", F); + Builder.SetInsertPoint(BB); + + Function::arg_iterator AI = F->arg_begin(); + Value *A = AI++; + Value *B = AI++; + + Value *Div = Builder.CreateUDiv(A, B); + EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv); + + Value *Ret = Builder.CreateRet(Div); + + expandDivision(cast(Div)); + EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp); + + Instruction* Quotient = dyn_cast(cast(Ret)->getOperand(0)); + EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI); + + Builder.SetInsertPoint(BB->end()); +} + +TEST(IntegerDivision, SRem) { + LLVMContext &C(getGlobalContext()); + Module M("test remainder", C); + IRBuilder<> Builder(C); + + SmallVector ArgTys(2, Builder.getInt32Ty()); + Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), + ArgTys, false), + GlobalValue::ExternalLinkage, "F", &M); + assert(F->getArgumentList().size() == 2); + + BasicBlock *BB = BasicBlock::Create(C, "", F); + Builder.SetInsertPoint(BB); + + Function::arg_iterator AI = F->arg_begin(); + Value *A = AI++; + Value *B = AI++; + + Value *Rem = Builder.CreateSRem(A, B); + EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem); + + Value *Ret = Builder.CreateRet(Rem); + + expandRemainder(cast(Rem)); + EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr); + + Instruction* Remainder = dyn_cast(cast(Ret)->getOperand(0)); + EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub); + + Builder.SetInsertPoint(BB->end()); +} + +TEST(IntegerDivision, URem) { + LLVMContext &C(getGlobalContext()); + Module M("test remainder", C); + IRBuilder<> Builder(C); + + SmallVector ArgTys(2, Builder.getInt32Ty()); + Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), + ArgTys, false), + GlobalValue::ExternalLinkage, "F", &M); + assert(F->getArgumentList().size() == 2); + + BasicBlock *BB = BasicBlock::Create(C, "", F); + Builder.SetInsertPoint(BB); + + Function::arg_iterator AI = F->arg_begin(); + Value *A = AI++; + Value *B = AI++; + + Value *Rem = Builder.CreateURem(A, B); + EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem); + + Value *Ret = Builder.CreateRet(Rem); + + expandRemainder(cast(Rem)); + EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp); + + Instruction* Remainder = dyn_cast(cast(Ret)->getOperand(0)); + EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub); + + Builder.SetInsertPoint(BB->end()); +} + } -- cgit v1.2.3