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// 10d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// This file contains an implementation of 32bit scalar integer division for 11d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// targets that don't have native support. It's largely derived from 12d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// compiler-rt's implementation of __udivsi3, but hand-tuned to reduce the 13d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// amount of control flow 14d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman// 15d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman//===----------------------------------------------------------------------===// 16d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 17d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman#define DEBUG_TYPE "integer-division" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/IntegerDivision.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 23d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 24d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilsemanusing namespace llvm; 25d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 26b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// Generate code to compute the remainder of two signed integers. Returns the 27b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// remainder, which will have the sign of the dividend. Builder's insert point 28b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// should be pointing where the caller wants code generated, e.g. at the srem 29b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// instruction. This will generate a urem in the process, and Builder's insert 30b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// point will be pointing at the uren (if present, i.e. not folded), ready to 31b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// be expanded if the user wishes 32b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilsemanstatic Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor, 33b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman IRBuilder<> &Builder) { 34b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman ConstantInt *ThirtyOne = Builder.getInt32(31); 35b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 36b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %dividend_sgn = ashr i32 %dividend, 31 37b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %divisor_sgn = ashr i32 %divisor, 31 38b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %dvd_xor = xor i32 %dividend, %dividend_sgn 39b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %dvs_xor = xor i32 %divisor, %divisor_sgn 40b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn 41b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn 42b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %urem = urem i32 %dividend, %divisor 43b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %xored = xor i32 %urem, %dividend_sgn 44b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %srem = sub i32 %xored, %dividend_sgn 45b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *DividendSign = Builder.CreateAShr(Dividend, ThirtyOne); 46b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *DivisorSign = Builder.CreateAShr(Divisor, ThirtyOne); 47b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *DvdXor = Builder.CreateXor(Dividend, DividendSign); 48b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign); 49b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *UDividend = Builder.CreateSub(DvdXor, DividendSign); 50b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign); 51b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *URem = Builder.CreateURem(UDividend, UDivisor); 52b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Xored = Builder.CreateXor(URem, DividendSign); 53b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *SRem = Builder.CreateSub(Xored, DividendSign); 54b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 55b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (Instruction *URemInst = dyn_cast<Instruction>(URem)) 56b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Builder.SetInsertPoint(URemInst); 57b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 58b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return SRem; 59b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman} 60b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 61b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 62b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// Generate code to compute the remainder of two unsigned integers. Returns the 63b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// remainder. Builder's insert point should be pointing where the caller wants 64b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// code generated, e.g. at the urem instruction. This will generate a udiv in 65b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the process, and Builder's insert point will be pointing at the udiv (if 66b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// present, i.e. not folded), ready to be expanded if the user wishes 67b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilsemanstatic Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, 68b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman IRBuilder<> &Builder) { 69b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // Remainder = Dividend - Quotient*Divisor 70b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 71b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %quotient = udiv i32 %dividend, %divisor 72b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %product = mul i32 %divisor, %quotient 73b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // ; %remainder = sub i32 %dividend, %product 74b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Quotient = Builder.CreateUDiv(Dividend, Divisor); 75b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Product = Builder.CreateMul(Divisor, Quotient); 76b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Remainder = Builder.CreateSub(Dividend, Product); 77b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 78b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (Instruction *UDiv = dyn_cast<Instruction>(Quotient)) 79b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Builder.SetInsertPoint(UDiv); 80b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 81b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return Remainder; 82b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman} 83b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 84dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// Generate code to divide two signed integers. Returns the quotient, rounded 85b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// towards 0. Builder's insert point should be pointing where the caller wants 86b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// code generated, e.g. at the sdiv instruction. This will generate a udiv in 87b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the process, and Builder's insert point will be pointing at the udiv (if 88b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// present, i.e. not folded), ready to be expanded if the user wishes. 89fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilsemanstatic Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor, 90e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman IRBuilder<> &Builder) { 91d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Implementation taken from compiler-rt's __divsi3 92d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 93e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman ConstantInt *ThirtyOne = Builder.getInt32(31); 94d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 95d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp = ashr i32 %dividend, 31 96d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp1 = ashr i32 %divisor, 31 97d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp2 = xor i32 %tmp, %dividend 98d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %u_dvnd = sub nsw i32 %tmp2, %tmp 99d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp3 = xor i32 %tmp1, %divisor 100d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1 101d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_sgn = xor i32 %tmp1, %tmp 102d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr 103d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp4 = xor i32 %q_mag, %q_sgn 104d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q = sub i32 %tmp4, %q_sgn 105e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp = Builder.CreateAShr(Dividend, ThirtyOne); 106e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp1 = Builder.CreateAShr(Divisor, ThirtyOne); 107e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp2 = Builder.CreateXor(Tmp, Dividend); 108e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp); 109e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor); 110e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1); 111e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp); 112e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr); 113e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn); 114e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q = Builder.CreateSub(Tmp4, Q_Sgn); 115d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 116e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag)) 117d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(UDiv); 118d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 119d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return Q; 120d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman} 121d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 122dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// Generates code to divide two unsigned scalar 32-bit integers. Returns the 123b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// quotient, rounded towards 0. Builder's insert point should be pointing where 124b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the caller wants code generated, e.g. at the udiv instruction. 125fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilsemanstatic Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, 126e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman IRBuilder<> &Builder) { 127d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // The basic algorithm can be found in the compiler-rt project's 128d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // implementation of __udivsi3.c. Here, we do a lower-level IR based approach 129d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // that's been hand-tuned to lessen the amount of control flow involved. 130d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 131d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Some helper values 132e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman IntegerType *I32Ty = Builder.getInt32Ty(); 133d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 134e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman ConstantInt *Zero = Builder.getInt32(0); 135e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman ConstantInt *One = Builder.getInt32(1); 136e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman ConstantInt *ThirtyOne = Builder.getInt32(31); 137e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman ConstantInt *NegOne = ConstantInt::getSigned(I32Ty, -1); 138e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman ConstantInt *True = Builder.getTrue(); 139d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 140e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *IBB = Builder.GetInsertBlock(); 141e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Function *F = IBB->getParent(); 142e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Function *CTLZi32 = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz, 143d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman I32Ty); 144d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 145d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Our CFG is going to look like: 146d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +---------------------+ 147d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | special-cases | 148d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | ... | 149d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +---------------------+ 150d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | 151d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +----------+ 152d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | bb1 | 153d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | ... | 154d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +----------+ 155d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | 156d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ 157d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | preheader | 158d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | ... | 159d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ 160d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | 161d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | +---+ 162d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | | | 163d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ | 164d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | do-while | | 165d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | ... | | 166d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | +------------+ | 167d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | | | | 168d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +-----------+ +---+ 169d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | loop-exit | 170d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | ... | 171d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | +-----------+ 172d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | | 173d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +-------+ 174d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | ... | 175d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // | end | 176d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // +-------+ 177e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *SpecialCases = Builder.GetInsertBlock(); 178d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases")); 179e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(), 180d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-end"); 181e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(), 182d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-loop-exit", F, End); 183e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(), 184d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-do-while", F, End); 185e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(), 186d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-preheader", F, End); 187e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(), 188d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman "udiv-bb1", F, End); 189d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 190d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // We'll be overwriting the terminator to insert our extra blocks 191d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SpecialCases->getTerminator()->eraseFromParent(); 192d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 193d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // First off, check for special cases: dividend or divisor is zero, divisor 194d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // is greater than dividend, and divisor is 1. 195d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; special-cases: 196d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_1 = icmp eq i32 %divisor, 0 197d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_2 = icmp eq i32 %dividend, 0 198d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_3 = or i1 %ret0_1, %ret0_2 199d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true) 200d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true) 201d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr = sub nsw i32 %tmp0, %tmp1 202d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0_4 = icmp ugt i32 %sr, 31 203d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %ret0 = or i1 %ret0_3, %ret0_4 204d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %retDividend = icmp eq i32 %sr, 31 205d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %retVal = select i1 %ret0, i32 0, i32 %dividend 206d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %earlyRet = or i1 %ret0, %retDividend 207d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br i1 %earlyRet, label %end, label %bb1 208d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(SpecialCases); 209e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero); 210e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero); 211e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2); 212e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp0 = Builder.CreateCall2(CTLZi32, Divisor, True); 213e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp1 = Builder.CreateCall2(CTLZi32, Dividend, True); 214e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SR = Builder.CreateSub(Tmp0, Tmp1); 215e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0_4 = Builder.CreateICmpUGT(SR, ThirtyOne); 216e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Ret0 = Builder.CreateOr(Ret0_3, Ret0_4); 217e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *RetDividend = Builder.CreateICmpEQ(SR, ThirtyOne); 218e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend); 219e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *EarlyRet = Builder.CreateOr(Ret0, RetDividend); 220d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateCondBr(EarlyRet, End, BB1); 221d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 222d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; bb1: ; preds = %special-cases 223d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_1 = add i32 %sr, 1 224d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp2 = sub i32 31, %sr 225d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q = shl i32 %dividend, %tmp2 226d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %skipLoop = icmp eq i32 %sr_1, 0 227d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br i1 %skipLoop, label %loop-exit, label %preheader 228d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(BB1); 229e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SR_1 = Builder.CreateAdd(SR, One); 230e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp2 = Builder.CreateSub(ThirtyOne, SR); 231e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q = Builder.CreateShl(Dividend, Tmp2); 232e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero); 233d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateCondBr(SkipLoop, LoopExit, Preheader); 234d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 235d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; preheader: ; preds = %bb1 236d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp3 = lshr i32 %dividend, %sr_1 237d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp4 = add i32 %divisor, -1 238d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br label %do-while 239d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(Preheader); 240e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1); 241e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne); 242d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateBr(DoWhile); 243d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 244d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; do-while: ; preds = %do-while, %preheader 245d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 246d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 247d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 248d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 249d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp5 = shl i32 %r_1, 1 250d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp6 = lshr i32 %q_2, 31 251d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp7 = or i32 %tmp5, %tmp6 252d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp8 = shl i32 %q_2, 1 253d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_1 = or i32 %carry_1, %tmp8 254d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp9 = sub i32 %tmp4, %tmp7 255d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp10 = ashr i32 %tmp9, 31 256d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry = and i32 %tmp10, 1 257d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp11 = and i32 %tmp10, %divisor 258d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %r = sub i32 %tmp7, %tmp11 259d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_2 = add i32 %sr_3, -1 260d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp12 = icmp eq i32 %sr_2, 0 261d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br i1 %tmp12, label %loop-exit, label %do-while 262d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(DoWhile); 263e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *Carry_1 = Builder.CreatePHI(I32Ty, 2); 264e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *SR_3 = Builder.CreatePHI(I32Ty, 2); 265e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *R_1 = Builder.CreatePHI(I32Ty, 2); 266e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *Q_2 = Builder.CreatePHI(I32Ty, 2); 267e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp5 = Builder.CreateShl(R_1, One); 268e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp6 = Builder.CreateLShr(Q_2, ThirtyOne); 269e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6); 270e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp8 = Builder.CreateShl(Q_2, One); 271e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8); 272e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7); 273e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp10 = Builder.CreateAShr(Tmp9, 31); 274e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Carry = Builder.CreateAnd(Tmp10, One); 275e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor); 276e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *R = Builder.CreateSub(Tmp7, Tmp11); 277e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *SR_2 = Builder.CreateAdd(SR_3, NegOne); 278e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero); 279d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateCondBr(Tmp12, LoopExit, DoWhile); 280d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 281d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; loop-exit: ; preds = %do-while, %bb1 282d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 283d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 284d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %tmp13 = shl i32 %q_3, 1 285d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_4 = or i32 %carry_2, %tmp13 286d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; br label %end 287d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(LoopExit); 288e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *Carry_2 = Builder.CreatePHI(I32Ty, 2); 289e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *Q_3 = Builder.CreatePHI(I32Ty, 2); 290e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Tmp13 = Builder.CreateShl(Q_3, One); 291e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13); 292d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.CreateBr(End); 293d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 294d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; end: ; preds = %loop-exit, %special-cases 295d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 296d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; ret i32 %q_5 297d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder.SetInsertPoint(End, End->begin()); 298e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman PHINode *Q_5 = Builder.CreatePHI(I32Ty, 2); 299d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 300d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Populate the Phis, since all values have now been created. Our Phis were: 301d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ] 302d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_1->addIncoming(Zero, Preheader); 303d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_1->addIncoming(Carry, DoWhile); 304d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ] 305d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SR_3->addIncoming(SR_1, Preheader); 306d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman SR_3->addIncoming(SR_2, DoWhile); 307d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ] 308d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman R_1->addIncoming(Tmp3, Preheader); 309d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman R_1->addIncoming(R, DoWhile); 310d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ] 311d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_2->addIncoming(Q, Preheader); 312d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_2->addIncoming(Q_1, DoWhile); 313d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ] 314d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_2->addIncoming(Zero, BB1); 315d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Carry_2->addIncoming(Carry, DoWhile); 316d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ] 317d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_3->addIncoming(Q, BB1); 318d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_3->addIncoming(Q_1, DoWhile); 319d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ] 320d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_5->addIncoming(Q_4, LoopExit); 321d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Q_5->addIncoming(RetVal, SpecialCases); 322d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 323d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return Q_5; 324d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman} 325d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 326b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// Generate code to calculate the remainder of two integers, replacing Rem with 327b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// the generated code. This currently generates code using the udiv expansion, 328b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// but future work includes generating more specialized code, e.g. when more 329b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// information about the operands are known. Currently only implements 32bit 330b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// scalar division (due to udiv's limitation), but future work is removing this 331b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// limitation. 332b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// 333b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman/// @brief Replace Rem with generated code. 334b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilsemanbool llvm::expandRemainder(BinaryOperator *Rem) { 335b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman assert((Rem->getOpcode() == Instruction::SRem || 336b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->getOpcode() == Instruction::URem) && 337b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman "Trying to expand remainder from a non-remainder function"); 338b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 339b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman IRBuilder<> Builder(Rem); 340b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 341b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // First prepare the sign if it's a signed remainder 342b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (Rem->getOpcode() == Instruction::SRem) { 343b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0), 344b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->getOperand(1), Builder); 345b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 346b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->replaceAllUsesWith(Remainder); 347b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->dropAllReferences(); 348b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->eraseFromParent(); 349b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 350b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // If we didn't actually generate a udiv instruction, we're done 351b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 352b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (!BO || BO->getOpcode() != Instruction::URem) 353b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return true; 354b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 355b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem = BO; 356b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman } 357b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 358b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0), 359b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->getOperand(1), 360b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Builder); 361b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 362b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->replaceAllUsesWith(Remainder); 363b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->dropAllReferences(); 364b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Rem->eraseFromParent(); 365b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 366b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman // Expand the udiv 367b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) { 368b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?"); 369b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman expandDivision(UDiv); 370b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman } 371b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 372b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman return true; 373b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman} 374b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 375b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman 376dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// Generate code to divide two integers, replacing Div with the generated 377dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// code. This currently generates code similarly to compiler-rt's 378dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// implementations, but future work includes generating more specialized code 379dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// when more information about the operands are known. Currently only 380dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// implements 32bit scalar division, but future work is removing this 381dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// limitation. 382dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// 383dcc5212aaf9809198584a93cd00e0bd75ed83108Michael Ilseman/// @brief Replace Div with generated code. 384e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilsemanbool llvm::expandDivision(BinaryOperator *Div) { 3851c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer assert((Div->getOpcode() == Instruction::SDiv || 3861c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer Div->getOpcode() == Instruction::UDiv) && 3871c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer "Trying to expand division from a non-division function"); 388d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 389d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman IRBuilder<> Builder(Div); 390d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 3911c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer if (Div->getType()->isVectorTy()) 3921c1ab8f53d91506f0590dc1d2448ae438e00b8c6Benjamin Kramer llvm_unreachable("Div over vectors not supported"); 393d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 394d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // First prepare the sign if it's a signed division 395d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman if (Div->getOpcode() == Instruction::SDiv) { 396d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Lower the code to unsigned division, and reset Div to point to the udiv. 397fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilseman Value *Quotient = generateSignedDivisionCode(Div->getOperand(0), 398b55462bcfb9acbf8654dff83159daf695dfc3ec4Michael Ilseman Div->getOperand(1), Builder); 399d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->replaceAllUsesWith(Quotient); 400d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->dropAllReferences(); 401d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->eraseFromParent(); 402d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 403d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // If we didn't actually generate a udiv instruction, we're done 404e87138dd1e4ab006a6f78e58f8e6fec95e3284f8Michael Ilseman BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint()); 405d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman if (!BO || BO->getOpcode() != Instruction::UDiv) 406d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return true; 407d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 408d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div = BO; 409d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman } 410d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 411d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman // Insert the unsigned division code 412fc879791f2c6329bb9377ebf8a03608f6590f80eMichael Ilseman Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0), 413d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->getOperand(1), 414d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Builder); 415d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->replaceAllUsesWith(Quotient); 416d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->dropAllReferences(); 417d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman Div->eraseFromParent(); 418d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman 419d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman return true; 420d2014649e0fc3c630c7530f6da060618c789d78dMichael Ilseman} 421b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 422b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// Generate code to compute the remainder of two integers of bitwidth up to 423b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// 32 bits. Uses the above routines and extends the inputs/truncates the 424b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// outputs to operate in 32 bits; that is, these routines are good for targets 425b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// that have no or very little suppport for smaller than 32 bit integer 426b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// arithmetic. 427b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// 428b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// @brief Replace Rem with emulation code. 429b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigasbool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) { 430b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas assert((Rem->getOpcode() == Instruction::SRem || 431b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->getOpcode() == Instruction::URem) && 432b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas "Trying to expand remainder from a non-remainder function"); 433b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 434b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *RemTy = Rem->getType(); 435b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (RemTy->isVectorTy()) 436b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div over vectors not supported"); 437b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 438b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas unsigned RemTyBitWidth = RemTy->getIntegerBitWidth(); 439b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 440b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (RemTyBitWidth > 32) 441b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div of bitwidth greater than 32 not supported"); 442b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 443b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (RemTyBitWidth == 32) 444b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandRemainder(Rem); 445b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 446b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas // If bitwidth smaller than 32 extend inputs, truncate output and proceed 447b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas // with 32 bit division. 448b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas IRBuilder<> Builder(Rem); 449b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 450b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDividend; 451b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDivisor; 452b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtRem; 453b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *Trunc; 454b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *Int32Ty = Builder.getInt32Ty(); 455b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 456b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (Rem->getOpcode() == Instruction::SRem) { 457b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty); 458b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty); 459b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor); 460b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } else { 461b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty); 462b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty); 463b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor); 464b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } 465b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Trunc = Builder.CreateTrunc(ExtRem, RemTy); 466b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 467b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->replaceAllUsesWith(Trunc); 468b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->dropAllReferences(); 469b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Rem->eraseFromParent(); 470b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 471b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandRemainder(cast<BinaryOperator>(ExtRem)); 472b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas} 473b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 474b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 475b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the 476b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// above routines and extends the inputs/truncates the outputs to operate 477b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// in 32 bits; that is, these routines are good for targets that have no 478b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// or very little support for smaller than 32 bit integer arithmetic. 479b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// 480b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas/// @brief Replace Div with emulation code. 481b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigasbool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) { 482b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas assert((Div->getOpcode() == Instruction::SDiv || 483b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->getOpcode() == Instruction::UDiv) && 484b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas "Trying to expand division from a non-division function"); 485b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 486b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *DivTy = Div->getType(); 487b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (DivTy->isVectorTy()) 488b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div over vectors not supported"); 489b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 490b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas unsigned DivTyBitWidth = DivTy->getIntegerBitWidth(); 491b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 492b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (DivTyBitWidth > 32) 493b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas llvm_unreachable("Div of bitwidth greater than 32 not supported"); 494b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 495b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (DivTyBitWidth == 32) 496b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandDivision(Div); 497b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 498b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas // If bitwidth smaller than 32 extend inputs, truncate output and proceed 499b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas // with 32 bit division. 500b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas IRBuilder<> Builder(Div); 501b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 502b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDividend; 503b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDivisor; 504b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *ExtDiv; 505b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Value *Trunc; 506b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Type *Int32Ty = Builder.getInt32Ty(); 507b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 508b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas if (Div->getOpcode() == Instruction::SDiv) { 509b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty); 510b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty); 511b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor); 512b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } else { 513b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty); 514b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty); 515b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor); 516b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas } 517b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Trunc = Builder.CreateTrunc(ExtDiv, DivTy); 518b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 519b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->replaceAllUsesWith(Trunc); 520b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->dropAllReferences(); 521b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas Div->eraseFromParent(); 522b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas 523b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas return expandDivision(cast<BinaryOperator>(ExtDiv)); 524b3201c5cf1e183d840f7c99ff779d57f1549d8e5Pedro Artigas} 525