1d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman//===-- IntegerDivision.cpp - Expand integer division ---------------------===// 2d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// 3d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// The LLVM Compiler Infrastructure 4d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// 5d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// This file is distributed under the University of Illinois Open Source 6d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// License. See LICENSE.TXT for details. 7d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// 8d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman//===----------------------------------------------------------------------===// 9d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file contains an implementation of 32bit and 64bit scalar integer 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// division for targets that don't have native support. It's largely derived 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// from compiler-rt's implementations of __udivsi3 and __udivmoddi4, 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// but hand-tuned for targets that prefer less control flow. 14d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// 15d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman//===----------------------------------------------------------------------===// 16d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/IntegerDivision.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <utility> 23d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 24d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilsemanusing namespace llvm; 25d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "integer-division" 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 28b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// Generate code to compute the remainder of two signed integers. Returns the 29b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// remainder, which will have the sign of the dividend. Builder's insert point 30b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// should be pointing where the caller wants code generated, e.g. at the srem 31b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// instruction. This will generate a urem in the process, and Builder's insert 32b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// point will be pointing at the uren (if present, i.e. not folded), ready to 33b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// be expanded if the user wishes 34b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilsemanstatic Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor, 35b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman IRBuilder<> &Builder) { 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned BitWidth = Dividend->getType()->getIntegerBitWidth(); 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *Shift; 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BitWidth == 64) { 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Shift = Builder.getInt64(63); 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(BitWidth == 32 && "Unexpected bit width"); 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Shift = Builder.getInt32(31); 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Following instructions are generated for both i32 (shift 31) and 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // i64 (shift 63). 48b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 49b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %dividend_sgn = ashr i32 %dividend, 31 50b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %divisor_sgn = ashr i32 %divisor, 31 51b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %dvd_xor = xor i32 %dividend, %dividend_sgn 52b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %dvs_xor = xor i32 %divisor, %divisor_sgn 53b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn 54b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn 55b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %urem = urem i32 %dividend, %divisor 56b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %xored = xor i32 %urem, %dividend_sgn 57b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %srem = sub i32 %xored, %dividend_sgn 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *DividendSign = Builder.CreateAShr(Dividend, Shift); 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *DivisorSign = Builder.CreateAShr(Divisor, Shift); 60b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *DvdXor = Builder.CreateXor(Dividend, DividendSign); 61b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign); 62b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *UDividend = Builder.CreateSub(DvdXor, DividendSign); 63b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign); 64b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *URem = Builder.CreateURem(UDividend, UDivisor); 65b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Xored = Builder.CreateXor(URem, DividendSign); 66b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *SRem = Builder.CreateSub(Xored, DividendSign); 67b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 68b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (Instruction *URemInst = dyn_cast<Instruction>(URem)) 69b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Builder.SetInsertPoint(URemInst); 70b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 71b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return SRem; 72b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman} 73b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 74b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 75b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// Generate code to compute the remainder of two unsigned integers. Returns the 76b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// remainder. Builder's insert point should be pointing where the caller wants 77b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// code generated, e.g. at the urem instruction. This will generate a udiv in 78b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the process, and Builder's insert point will be pointing at the udiv (if 79b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// present, i.e. not folded), ready to be expanded if the user wishes 80b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilsemanstatic Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, 81b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman IRBuilder<> &Builder) { 82b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // Remainder = Dividend - Quotient*Divisor 83b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Following instructions are generated for both i32 and i64 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 86b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %quotient = udiv i32 %dividend, %divisor 87b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %product = mul i32 %divisor, %quotient 88b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %remainder = sub i32 %dividend, %product 89b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Quotient = Builder.CreateUDiv(Dividend, Divisor); 90b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Product = Builder.CreateMul(Divisor, Quotient); 91b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Remainder = Builder.CreateSub(Dividend, Product); 92b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 93b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (Instruction *UDiv = dyn_cast<Instruction>(Quotient)) 94b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Builder.SetInsertPoint(UDiv); 95b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 96b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return Remainder; 97b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman} 98b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 99dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// Generate code to divide two signed integers. Returns the quotient, rounded 100b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// towards 0. Builder's insert point should be pointing where the caller wants 101b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// code generated, e.g. at the sdiv instruction. This will generate a udiv in 102b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the process, and Builder's insert point will be pointing at the udiv (if 103b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// present, i.e. not folded), ready to be expanded if the user wishes. 104fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilsemanstatic Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor, 105e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman IRBuilder<> &Builder) { 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Implementation taken from compiler-rt's __divsi3 and __divdi3 107d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned BitWidth = Dividend->getType()->getIntegerBitWidth(); 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *Shift; 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BitWidth == 64) { 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Shift = Builder.getInt64(63); 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(BitWidth == 32 && "Unexpected bit width"); 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Shift = Builder.getInt32(31); 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Following instructions are generated for both i32 (shift 31) and 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // i64 (shift 63). 120d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 121d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp = ashr i32 %dividend, 31 122d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp1 = ashr i32 %divisor, 31 123d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp2 = xor i32 %tmp, %dividend 124d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %u_dvnd = sub nsw i32 %tmp2, %tmp 125d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp3 = xor i32 %tmp1, %divisor 126d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1 127d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_sgn = xor i32 %tmp1, %tmp 128d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr 129d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp4 = xor i32 %q_mag, %q_sgn 130d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q = sub i32 %tmp4, %q_sgn 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp = Builder.CreateAShr(Dividend, Shift); 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp1 = Builder.CreateAShr(Divisor, Shift); 133e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp2 = Builder.CreateXor(Tmp, Dividend); 134e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp); 135e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor); 136e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1); 137e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp); 138e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr); 139e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn); 140e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q = Builder.CreateSub(Tmp4, Q_Sgn); 141d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 142e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag)) 143d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(UDiv); 144d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 145d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return Q; 146d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman} 147d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Generates code to divide two unsigned scalar 32-bit or 64-bit integers. 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Returns the quotient, rounded towards 0. Builder's insert point should 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// point where the caller wants code generated, e.g. at the udiv instruction. 151fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilsemanstatic Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, 152e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman IRBuilder<> &Builder) { 153d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // The basic algorithm can be found in the compiler-rt project's 154d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // implementation of __udivsi3.c. Here, we do a lower-level IR based approach 155d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // that's been hand-tuned to lessen the amount of control flow involved. 156d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 157d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Some helper values 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IntegerType *DivTy = cast<IntegerType>(Dividend->getType()); 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned BitWidth = DivTy->getBitWidth(); 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *Zero; 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *One; 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *NegOne; 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *MSB; 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BitWidth == 64) { 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Zero = Builder.getInt64(0); 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines One = Builder.getInt64(1); 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NegOne = ConstantInt::getSigned(DivTy, -1); 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MSB = Builder.getInt64(63); 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(BitWidth == 32 && "Unexpected bit width"); 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Zero = Builder.getInt32(0); 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines One = Builder.getInt32(1); 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NegOne = ConstantInt::getSigned(DivTy, -1); 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MSB = Builder.getInt32(31); 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 178d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *True = Builder.getTrue(); 180d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 181e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *IBB = Builder.GetInsertBlock(); 182e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Function *F = IBB->getParent(); 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz, 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DivTy); 185d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 186d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Our CFG is going to look like: 187d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +---------------------+ 188d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | special-cases | 189d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | ... | 190d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +---------------------+ 191d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | 192d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +----------+ 193d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | bb1 | 194d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | ... | 195d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +----------+ 196d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | 197d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ 198d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | preheader | 199d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | ... | 200d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ 201d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | 202d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | +---+ 203d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | | | 204d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ | 205d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | do-while | | 206d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | ... | | 207d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ | 208d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | | | 209d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +-----------+ +---+ 210d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | loop-exit | 211d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | ... | 212d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +-----------+ 213d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | 214d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +-------+ 215d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | ... | 216d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | end | 217d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +-------+ 218e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *SpecialCases = Builder.GetInsertBlock(); 219d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases")); 220e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(), 221d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-end"); 222e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(), 223d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-loop-exit", F, End); 224e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(), 225d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-do-while", F, End); 226e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(), 227d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-preheader", F, End); 228e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(), 229d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-bb1", F, End); 230d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 231d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // We'll be overwriting the terminator to insert our extra blocks 232d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SpecialCases->getTerminator()->eraseFromParent(); 233d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Same instructions are generated for both i32 (msb 31) and i64 (msb 63). 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 236d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // First off, check for special cases: dividend or divisor is zero, divisor 237d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // is greater than dividend, and divisor is 1. 238d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; special-cases: 239d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_1 = icmp eq i32 %divisor, 0 240d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_2 = icmp eq i32 %dividend, 0 241d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_3 = or i1 %ret0_1, %ret0_2 242d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true) 243d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true) 244d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr = sub nsw i32 %tmp0, %tmp1 245d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_4 = icmp ugt i32 %sr, 31 246d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0 = or i1 %ret0_3, %ret0_4 247d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %retDividend = icmp eq i32 %sr, 31 248d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %retVal = select i1 %ret0, i32 0, i32 %dividend 249d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %earlyRet = or i1 %ret0, %retDividend 250d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br i1 %earlyRet, label %end, label %bb1 251d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(SpecialCases); 252e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero); 253e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero); 254e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2); 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp0 = Builder.CreateCall2(CTLZ, Divisor, True); 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp1 = Builder.CreateCall2(CTLZ, Dividend, True); 257e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SR = Builder.CreateSub(Tmp0, Tmp1); 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB); 259e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0 = Builder.CreateOr(Ret0_3, Ret0_4); 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *RetDividend = Builder.CreateICmpEQ(SR, MSB); 261e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend); 262e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *EarlyRet = Builder.CreateOr(Ret0, RetDividend); 263d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateCondBr(EarlyRet, End, BB1); 264d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 265d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; bb1: ; preds = %special-cases 266d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_1 = add i32 %sr, 1 267d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp2 = sub i32 31, %sr 268d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q = shl i32 %dividend, %tmp2 269d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %skipLoop = icmp eq i32 %sr_1, 0 270d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br i1 %skipLoop, label %loop-exit, label %preheader 271d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(BB1); 272e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SR_1 = Builder.CreateAdd(SR, One); 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp2 = Builder.CreateSub(MSB, SR); 274e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q = Builder.CreateShl(Dividend, Tmp2); 275e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero); 276d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateCondBr(SkipLoop, LoopExit, Preheader); 277d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 278d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; preheader: ; preds = %bb1 279d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp3 = lshr i32 %dividend, %sr_1 280d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp4 = add i32 %divisor, -1 281d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br label %do-while 282d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(Preheader); 283e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1); 284e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne); 285d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateBr(DoWhile); 286d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 287d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; do-while: ; preds = %do-while, %preheader 288d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 289d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 290d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 291d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 292d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp5 = shl i32 %r_1, 1 293d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp6 = lshr i32 %q_2, 31 294d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp7 = or i32 %tmp5, %tmp6 295d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp8 = shl i32 %q_2, 1 296d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_1 = or i32 %carry_1, %tmp8 297d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp9 = sub i32 %tmp4, %tmp7 298d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp10 = ashr i32 %tmp9, 31 299d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry = and i32 %tmp10, 1 300d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp11 = and i32 %tmp10, %divisor 301d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %r = sub i32 %tmp7, %tmp11 302d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_2 = add i32 %sr_3, -1 303d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp12 = icmp eq i32 %sr_2, 0 304d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br i1 %tmp12, label %loop-exit, label %do-while 305d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(DoWhile); 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2); 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *SR_3 = Builder.CreatePHI(DivTy, 2); 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *R_1 = Builder.CreatePHI(DivTy, 2); 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *Q_2 = Builder.CreatePHI(DivTy, 2); 310e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp5 = Builder.CreateShl(R_1, One); 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp6 = Builder.CreateLShr(Q_2, MSB); 312e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6); 313e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp8 = Builder.CreateShl(Q_2, One); 314e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8); 315e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7); 31636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB); 317e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Carry = Builder.CreateAnd(Tmp10, One); 318e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor); 319e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *R = Builder.CreateSub(Tmp7, Tmp11); 320e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SR_2 = Builder.CreateAdd(SR_3, NegOne); 321e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero); 322d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateCondBr(Tmp12, LoopExit, DoWhile); 323d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 324d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; loop-exit: ; preds = %do-while, %bb1 325d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 326d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 327d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp13 = shl i32 %q_3, 1 328d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_4 = or i32 %carry_2, %tmp13 329d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br label %end 330d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(LoopExit); 33136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2); 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *Q_3 = Builder.CreatePHI(DivTy, 2); 333e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp13 = Builder.CreateShl(Q_3, One); 334e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13); 335d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateBr(End); 336d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 337d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; end: ; preds = %loop-exit, %special-cases 338d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 339d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; ret i32 %q_5 340d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(End, End->begin()); 34136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *Q_5 = Builder.CreatePHI(DivTy, 2); 342d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 343d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Populate the Phis, since all values have now been created. Our Phis were: 344d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 345d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_1->addIncoming(Zero, Preheader); 346d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_1->addIncoming(Carry, DoWhile); 347d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 348d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SR_3->addIncoming(SR_1, Preheader); 349d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SR_3->addIncoming(SR_2, DoWhile); 350d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 351d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman R_1->addIncoming(Tmp3, Preheader); 352d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman R_1->addIncoming(R, DoWhile); 353d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 354d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_2->addIncoming(Q, Preheader); 355d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_2->addIncoming(Q_1, DoWhile); 356d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 357d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_2->addIncoming(Zero, BB1); 358d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_2->addIncoming(Carry, DoWhile); 359d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 360d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_3->addIncoming(Q, BB1); 361d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_3->addIncoming(Q_1, DoWhile); 362d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 363d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_5->addIncoming(Q_4, LoopExit); 364d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_5->addIncoming(RetVal, SpecialCases); 365d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 366d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return Q_5; 367d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman} 368d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 369b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// Generate code to calculate the remainder of two integers, replacing Rem with 370b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the generated code. This currently generates code using the udiv expansion, 371b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// but future work includes generating more specialized code, e.g. when more 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// information about the operands are known. Implements both 32bit and 64bit 37336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// scalar division. 374b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// 375b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// @brief Replace Rem with generated code. 376b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilsemanbool llvm::expandRemainder(BinaryOperator *Rem) { 377b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman assert((Rem->getOpcode() == Instruction::SRem || 378b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->getOpcode() == Instruction::URem) && 379b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman "Trying to expand remainder from a non-remainder function"); 380b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 381b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman IRBuilder<> Builder(Rem); 382b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 38336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *RemTy = Rem->getType(); 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RemTy->isVectorTy()) 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div over vectors not supported"); 38636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 38736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned RemTyBitWidth = RemTy->getIntegerBitWidth(); 38836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RemTyBitWidth != 32 && RemTyBitWidth != 64) 39036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div of bitwidth other than 32 or 64 not supported"); 39136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 392b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // First prepare the sign if it's a signed remainder 393b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (Rem->getOpcode() == Instruction::SRem) { 394b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0), 395b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->getOperand(1), Builder); 396b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 397b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->replaceAllUsesWith(Remainder); 398b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->dropAllReferences(); 399b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->eraseFromParent(); 400b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 401b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // If we didn't actually generate a udiv instruction, we're done 402b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 403b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (!BO || BO->getOpcode() != Instruction::URem) 404b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return true; 405b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 406b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem = BO; 407b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman } 408b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 409b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0), 410b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->getOperand(1), 411b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Builder); 412b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 413b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->replaceAllUsesWith(Remainder); 414b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->dropAllReferences(); 415b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->eraseFromParent(); 416b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 417b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // Expand the udiv 418b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) { 419b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?"); 420b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman expandDivision(UDiv); 421b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman } 422b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 423b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return true; 424b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman} 425b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 426b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 427dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// Generate code to divide two integers, replacing Div with the generated 428dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// code. This currently generates code similarly to compiler-rt's 429dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// implementations, but future work includes generating more specialized code 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// when more information about the operands are known. Implements both 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 32bit and 64bit scalar division. 432dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// 433dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// @brief Replace Div with generated code. 434e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilsemanbool llvm::expandDivision(BinaryOperator *Div) { 4351c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer assert((Div->getOpcode() == Instruction::SDiv || 4361c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer Div->getOpcode() == Instruction::UDiv) && 4371c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer "Trying to expand division from a non-division function"); 438d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 439d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman IRBuilder<> Builder(Div); 440d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 44136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *DivTy = Div->getType(); 44236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DivTy->isVectorTy()) 4431c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer llvm_unreachable("Div over vectors not supported"); 444d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 44536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned DivTyBitWidth = DivTy->getIntegerBitWidth(); 44636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 44736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DivTyBitWidth != 32 && DivTyBitWidth != 64) 44836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div of bitwidth other than 32 or 64 not supported"); 44936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 450d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // First prepare the sign if it's a signed division 451d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman if (Div->getOpcode() == Instruction::SDiv) { 452d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Lower the code to unsigned division, and reset Div to point to the udiv. 453fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilseman Value *Quotient = generateSignedDivisionCode(Div->getOperand(0), 454b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Div->getOperand(1), Builder); 455d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->replaceAllUsesWith(Quotient); 456d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->dropAllReferences(); 457d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->eraseFromParent(); 458d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 459d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // If we didn't actually generate a udiv instruction, we're done 460e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 461d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman if (!BO || BO->getOpcode() != Instruction::UDiv) 462d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return true; 463d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 464d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div = BO; 465d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman } 466d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 467d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Insert the unsigned division code 468fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilseman Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0), 469d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->getOperand(1), 470d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder); 471d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->replaceAllUsesWith(Quotient); 472d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->dropAllReferences(); 473d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->eraseFromParent(); 474d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 475d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return true; 476d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman} 477b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 478b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// Generate code to compute the remainder of two integers of bitwidth up to 479b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// 32 bits. Uses the above routines and extends the inputs/truncates the 480b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// outputs to operate in 32 bits; that is, these routines are good for targets 481b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// that have no or very little suppport for smaller than 32 bit integer 482b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// arithmetic. 483b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// 484b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// @brief Replace Rem with emulation code. 485b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigasbool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) { 486b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas assert((Rem->getOpcode() == Instruction::SRem || 487b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->getOpcode() == Instruction::URem) && 488b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas "Trying to expand remainder from a non-remainder function"); 489b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 490b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *RemTy = Rem->getType(); 491b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (RemTy->isVectorTy()) 492b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div over vectors not supported"); 493b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 494b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas unsigned RemTyBitWidth = RemTy->getIntegerBitWidth(); 495b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 496b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (RemTyBitWidth > 32) 497b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div of bitwidth greater than 32 not supported"); 498b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 499b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (RemTyBitWidth == 32) 500b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandRemainder(Rem); 501b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 50236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If bitwidth smaller than 32 extend inputs, extend output and proceed 503b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas // with 32 bit division. 504b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas IRBuilder<> Builder(Rem); 505b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 506b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDividend; 507b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDivisor; 508b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtRem; 509b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *Trunc; 510b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *Int32Ty = Builder.getInt32Ty(); 511b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 512b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (Rem->getOpcode() == Instruction::SRem) { 513b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty); 514b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty); 515b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 516b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } else { 517b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty); 518b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty); 519b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 520b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } 521b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Trunc = Builder.CreateTrunc(ExtRem, RemTy); 522b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 523b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->replaceAllUsesWith(Trunc); 524b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->dropAllReferences(); 525b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->eraseFromParent(); 526b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 527b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandRemainder(cast<BinaryOperator>(ExtRem)); 528b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas} 529b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 53036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Generate code to compute the remainder of two integers of bitwidth up to 53136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 64 bits. Uses the above routines and extends the inputs/truncates the 53236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// outputs to operate in 64 bits. 53336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 53436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// @brief Replace Rem with emulation code. 53536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) { 53636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((Rem->getOpcode() == Instruction::SRem || 53736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Rem->getOpcode() == Instruction::URem) && 53836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Trying to expand remainder from a non-remainder function"); 53936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *RemTy = Rem->getType(); 54136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RemTy->isVectorTy()) 54236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div over vectors not supported"); 54336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned RemTyBitWidth = RemTy->getIntegerBitWidth(); 54536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RemTyBitWidth > 64) 54736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div of bitwidth greater than 64 not supported"); 54836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RemTyBitWidth == 64) 55036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return expandRemainder(Rem); 55136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 55236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If bitwidth smaller than 64 extend inputs, extend output and proceed 55336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // with 64 bit division. 55436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IRBuilder<> Builder(Rem); 55536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 55636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ExtDividend; 55736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ExtDivisor; 55836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ExtRem; 55936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Trunc; 56036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *Int64Ty = Builder.getInt64Ty(); 56136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 56236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Rem->getOpcode() == Instruction::SRem) { 56336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty); 56436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty); 56536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 56636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 56736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty); 56836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty); 56936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 57036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 57136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Trunc = Builder.CreateTrunc(ExtRem, RemTy); 57236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 57336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Rem->replaceAllUsesWith(Trunc); 57436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Rem->dropAllReferences(); 57536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Rem->eraseFromParent(); 57636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 57736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return expandRemainder(cast<BinaryOperator>(ExtRem)); 57836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 579b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 580b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the 581b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// above routines and extends the inputs/truncates the outputs to operate 582b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// in 32 bits; that is, these routines are good for targets that have no 583b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// or very little support for smaller than 32 bit integer arithmetic. 584b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// 585b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// @brief Replace Div with emulation code. 586b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigasbool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) { 587b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas assert((Div->getOpcode() == Instruction::SDiv || 588b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->getOpcode() == Instruction::UDiv) && 589b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas "Trying to expand division from a non-division function"); 590b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 591b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *DivTy = Div->getType(); 592b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (DivTy->isVectorTy()) 593b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div over vectors not supported"); 594b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 595b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas unsigned DivTyBitWidth = DivTy->getIntegerBitWidth(); 596b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 597b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (DivTyBitWidth > 32) 598b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div of bitwidth greater than 32 not supported"); 599b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 600b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (DivTyBitWidth == 32) 601b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandDivision(Div); 602b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 60336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If bitwidth smaller than 32 extend inputs, extend output and proceed 604b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas // with 32 bit division. 605b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas IRBuilder<> Builder(Div); 606b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 607b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDividend; 608b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDivisor; 609b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDiv; 610b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *Trunc; 611b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *Int32Ty = Builder.getInt32Ty(); 612b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 613b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (Div->getOpcode() == Instruction::SDiv) { 614b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty); 615b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty); 616b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 617b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } else { 618b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty); 619b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty); 620b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 621b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } 622b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 623b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 624b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->replaceAllUsesWith(Trunc); 625b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->dropAllReferences(); 626b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->eraseFromParent(); 627b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 628b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandDivision(cast<BinaryOperator>(ExtDiv)); 629b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas} 63036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 63136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Generate code to divide two integers of bitwidth up to 64 bits. Uses the 63236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// above routines and extends the inputs/truncates the outputs to operate 63336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// in 64 bits. 63436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 63536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// @brief Replace Div with emulation code. 63636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) { 63736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((Div->getOpcode() == Instruction::SDiv || 63836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Div->getOpcode() == Instruction::UDiv) && 63936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Trying to expand division from a non-division function"); 64036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *DivTy = Div->getType(); 64236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DivTy->isVectorTy()) 64336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div over vectors not supported"); 64436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned DivTyBitWidth = DivTy->getIntegerBitWidth(); 64636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DivTyBitWidth > 64) 64836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Div of bitwidth greater than 64 not supported"); 64936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DivTyBitWidth == 64) 65136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return expandDivision(Div); 65236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If bitwidth smaller than 64 extend inputs, extend output and proceed 65436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // with 64 bit division. 65536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IRBuilder<> Builder(Div); 65636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ExtDividend; 65836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ExtDivisor; 65936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ExtDiv; 66036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Trunc; 66136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *Int64Ty = Builder.getInt64Ty(); 66236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 66336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Div->getOpcode() == Instruction::SDiv) { 66436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty); 66536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty); 66636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 66736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 66836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty); 66936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty); 67036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 67136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 67236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 67336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Div->replaceAllUsesWith(Trunc); 67536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Div->dropAllReferences(); 67636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Div->eraseFromParent(); 67736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return expandDivision(cast<BinaryOperator>(ExtDiv)); 67936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 680