12e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd//===-- BypassSlowDivision.cpp - Bypass slow division ---------------------===// 22e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// 32e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// The LLVM Compiler Infrastructure 42e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// 52e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// This file is distributed under the University of Illinois Open Source 62e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// License. See LICENSE.TXT for details. 72e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// 82e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd//===----------------------------------------------------------------------===// 92e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// 102e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// This file contains an optimization for div and rem on architectures that 112e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// execute short instructions significantly faster than longer instructions. 122e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// For example, on Intel Atom 32-bit divides are slow enough that during 132e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// runtime it is profitable to check the value of the operands, and if they are 142e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// positive and less than 256 use an unsigned 8-bit divide. 152e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// 162e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd//===----------------------------------------------------------------------===// 172e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/BypassSlowDivision.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 232e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 242e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurdusing namespace llvm; 252e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "bypass-slow-division" 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 2804142bc845c513141046e852db86670505459416Benjamin Kramernamespace { 292e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd struct DivOpInfo { 302e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool SignedOp; 312e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Dividend; 322e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Divisor; 332e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 342e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor) 352e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {} 362e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd }; 372e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 382e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd struct DivPhiNodes { 392e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *Quotient; 402e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *Remainder; 412e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 422e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder) 432e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd : Quotient(InQuotient), Remainder(InRemainder) {} 442e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd }; 4504142bc845c513141046e852db86670505459416Benjamin Kramer} 462e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 4704142bc845c513141046e852db86670505459416Benjamin Kramernamespace llvm { 482e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd template<> 492e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd struct DenseMapInfo<DivOpInfo> { 502e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) { 512e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return Val1.SignedOp == Val2.SignedOp && 522e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Val1.Dividend == Val2.Dividend && 532e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Val1.Divisor == Val2.Divisor; 542e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 552e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 562e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static DivOpInfo getEmptyKey() { 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return DivOpInfo(false, nullptr, nullptr); 582e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 592e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 602e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static DivOpInfo getTombstoneKey() { 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return DivOpInfo(true, nullptr, nullptr); 622e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 632e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 642e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static unsigned getHashValue(const DivOpInfo &Val) { 652e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^ 662e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd reinterpret_cast<uintptr_t>(Val.Divisor)) ^ 677b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak (unsigned)Val.SignedOp; 682e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 692e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd }; 702e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 712e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy; 722e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 732e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 742e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// insertFastDiv - Substitutes the div/rem instruction with code that checks the 752e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// value of the operands and uses a shorter-faster div/rem instruction when 762e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// possible and the longer-slower div/rem instruction otherwise. 777b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszakstatic bool insertFastDiv(Function &F, 782e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Function::iterator &I, 792e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock::iterator &J, 802e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IntegerType *BypassType, 812e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseDivOp, 822e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseSignedOp, 837b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak DivCacheTy &PerBBDivCache) { 842e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Get instruction operands 852e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instruction *Instr = J; 862e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Dividend = Instr->getOperand(0); 872e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Divisor = Instr->getOperand(1); 882e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 897b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (isa<ConstantInt>(Divisor) || 907b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak (isa<ConstantInt>(Dividend) && isa<ConstantInt>(Divisor))) { 912e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Operations with immediate values should have 922e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // been solved and replaced during compile time. 937b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return false; 942e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 952e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 962e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Basic Block is split before divide 972e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *MainBB = I; 982e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *SuccessorBB = I->splitBasicBlock(J); 997b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ++I; //advance iterator I to successorBB 1002e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1012e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Add new basic block for slow divide operation 1022e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *SlowBB = BasicBlock::Create(F.getContext(), "", 1032e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBB->getParent(), SuccessorBB); 1042e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowBB->moveBefore(SuccessorBB); 1052e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin()); 1062e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *SlowQuotientV; 1072e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *SlowRemainderV; 1082e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd if (UseSignedOp) { 1092e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor); 1102e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor); 1112e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } else { 1122e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor); 1132e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor); 1142e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 1152e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowBuilder.CreateBr(SuccessorBB); 1162e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1172e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Add new basic block for fast divide operation 1182e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *FastBB = BasicBlock::Create(F.getContext(), "", 1192e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBB->getParent(), SuccessorBB); 1202e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd FastBB->moveBefore(SlowBB); 1212e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> FastBuilder(FastBB, FastBB->begin()); 1227b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor, 1237b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak BypassType); 1247b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend, 1257b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak BypassType); 1262e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1272e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // udiv/urem because optimization only handles positive numbers 1282e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV, 1297b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ShortDivisorV); 1302e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV, 1312e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd ShortDivisorV); 1322e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt, 1337b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ShortQuotientV, 1347b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Dividend->getType()); 1352e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt, 1362e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd ShortRemainderV, 1372e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Dividend->getType()); 1382e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd FastBuilder.CreateBr(SuccessorBB); 1392e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1402e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Phi nodes for result of div and rem 1412e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin()); 1422e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *QuoPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2); 1432e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd QuoPhi->addIncoming(SlowQuotientV, SlowBB); 1442e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd QuoPhi->addIncoming(FastQuotientV, FastBB); 1452e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *RemPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2); 1462e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd RemPhi->addIncoming(SlowRemainderV, SlowBB); 1472e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd RemPhi->addIncoming(FastRemainderV, FastBB); 1482e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1492e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace Instr with appropriate phi node 1507b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (UseDivOp) 1512e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->replaceAllUsesWith(QuoPhi); 1527b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak else 1532e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->replaceAllUsesWith(RemPhi); 1542e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->eraseFromParent(); 1552e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1562e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Combine operands into a single value with OR for value testing below 1572e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBB->getInstList().back().eraseFromParent(); 1582e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> MainBuilder(MainBB, MainBB->end()); 1592e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *OrV = MainBuilder.CreateOr(Dividend, Divisor); 1602e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1612e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // BitMask is inverted to check if the operands are 1622e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // larger than the bypass type 1632e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd uint64_t BitMask = ~BypassType->getBitMask(); 1642e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *AndV = MainBuilder.CreateAnd(OrV, BitMask); 1652e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1662e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Compare operand values and branch 1679a2cfffdb6340c54ff553c1b81364d0f17fa8f45Preston Gurd Value *ZeroV = ConstantInt::getSigned(Dividend->getType(), 0); 1682e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV); 1692e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB); 1702e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1712e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // point iterator J at first instruction of successorBB 1722e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd J = I->begin(); 1732e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1742e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Cache phi nodes to be used later in place of other instances 1752e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // of div or rem with the same sign, dividend, and divisor 1762e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivOpInfo Key(UseSignedOp, Dividend, Divisor); 1772e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivPhiNodes Value(QuoPhi, RemPhi); 1782e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value)); 1797b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return true; 1802e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 1812e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1822e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// reuseOrInsertFastDiv - Reuses previously computed dividend or remainder if 1832e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// operands and operation are identical. Otherwise call insertFastDiv to perform 1842e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// the optimization and cache the resulting dividend and remainder. 1857b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszakstatic bool reuseOrInsertFastDiv(Function &F, 1862e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Function::iterator &I, 1872e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock::iterator &J, 1882e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IntegerType *BypassType, 1892e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseDivOp, 1902e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseSignedOp, 1917b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak DivCacheTy &PerBBDivCache) { 1922e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Get instruction operands 1932e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instruction *Instr = J; 1942e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1)); 195be11991208f175892666887bc59fd9d32ee3e6a4Jakub Staszak DivCacheTy::iterator CacheI = PerBBDivCache.find(Key); 1962e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1972e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd if (CacheI == PerBBDivCache.end()) { 1982e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // If previous instance does not exist, insert fast div 1997b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp, 2007b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak PerBBDivCache); 2012e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 2022e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2032e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace operation value with previously generated phi node 204be11991208f175892666887bc59fd9d32ee3e6a4Jakub Staszak DivPhiNodes &Value = CacheI->second; 2052e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd if (UseDivOp) { 2062e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace all uses of div instruction with quotient phi node 2072e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd J->replaceAllUsesWith(Value.Quotient); 2082e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } else { 2092e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace all uses of rem instruction with remainder phi node 2102e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd J->replaceAllUsesWith(Value.Remainder); 2112e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 2122e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2132e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Advance to next operation 2147b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ++J; 2152e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2162e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Remove redundant operation 2172e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->eraseFromParent(); 2187b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return true; 2192e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 2202e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2212e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// bypassSlowDivision - This optimization identifies DIV instructions that can 2222e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// be profitably bypassed and carried out with a shorter, faster divide. 22304142bc845c513141046e852db86670505459416Benjamin Kramerbool llvm::bypassSlowDivision(Function &F, 22404142bc845c513141046e852db86670505459416Benjamin Kramer Function::iterator &I, 2258d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd const DenseMap<unsigned int, unsigned int> &BypassWidths) { 2262e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivCacheTy DivCache; 2272e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2282e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool MadeChange = false; 2292e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd for (BasicBlock::iterator J = I->begin(); J != I->end(); J++) { 2302e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2312e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Get instruction details 2322e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd unsigned Opcode = J->getOpcode(); 2332e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseDivOp = Opcode == Instruction::SDiv || Opcode == Instruction::UDiv; 2342e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseRemOp = Opcode == Instruction::SRem || Opcode == Instruction::URem; 2357b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak bool UseSignedOp = Opcode == Instruction::SDiv || 2367b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Opcode == Instruction::SRem; 2372e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2382e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Only optimize div or rem ops 2397b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (!UseDivOp && !UseRemOp) 2402e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd continue; 2417b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak 242fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd // Skip division on vector types, only optimize integer instructions 243fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd if (!J->getType()->isIntegerTy()) 244fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd continue; 245fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd 2468d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd // Get bitwidth of div/rem instruction 247fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd IntegerType *T = cast<IntegerType>(J->getType()); 2489a2cfffdb6340c54ff553c1b81364d0f17fa8f45Preston Gurd unsigned int bitwidth = T->getBitWidth(); 249fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd 2508d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd // Continue if bitwidth is not bypassed 2518d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd DenseMap<unsigned int, unsigned int>::const_iterator BI = BypassWidths.find(bitwidth); 2528d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd if (BI == BypassWidths.end()) 2532e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd continue; 2542e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2558d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd // Get type for div/rem instruction with bypass bitwidth 2568d662b59f075da67e663ed142ecdd58e381eee98Preston Gurd IntegerType *BT = IntegerType::get(J->getContext(), BI->second); 257fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd 258fcf0628d93d759ae36106f7a738f66cb77badc79Preston Gurd MadeChange |= reuseOrInsertFastDiv(F, I, J, BT, UseDivOp, 2597b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak UseSignedOp, DivCache); 2602e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 2612e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2622e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return MadeChange; 2632e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 264