BypassSlowDivision.cpp revision be11991208f175892666887bc59fd9d32ee3e6a4
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 182e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd#define DEBUG_TYPE "bypass-slow-division" 192e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd#include "llvm/Instructions.h" 202e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd#include "llvm/Function.h" 212e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd#include "llvm/IRBuilder.h" 222e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd#include "llvm/ADT/DenseMap.h" 232e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd#include "llvm/Transforms/Utils/BypassSlowDivision.h" 242e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 252e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurdusing namespace llvm; 262e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 272e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurdnamespace llvm { 282e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd struct DivOpInfo { 292e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool SignedOp; 302e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Dividend; 312e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Divisor; 322e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 332e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor) 342e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {} 352e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd }; 362e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 372e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd struct DivPhiNodes { 382e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *Quotient; 392e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *Remainder; 402e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 412e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder) 422e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd : Quotient(InQuotient), Remainder(InRemainder) {} 432e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd }; 442e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 452e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd template<> 462e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd struct DenseMapInfo<DivOpInfo> { 472e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) { 482e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return Val1.SignedOp == Val2.SignedOp && 492e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Val1.Dividend == Val2.Dividend && 502e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Val1.Divisor == Val2.Divisor; 512e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 522e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 532e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static DivOpInfo getEmptyKey() { 542e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return DivOpInfo(false, 0, 0); 552e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 562e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 572e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static DivOpInfo getTombstoneKey() { 582e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return DivOpInfo(true, 0, 0); 592e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 602e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 612e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd static unsigned getHashValue(const DivOpInfo &Val) { 622e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^ 632e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd reinterpret_cast<uintptr_t>(Val.Divisor)) ^ 647b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak (unsigned)Val.SignedOp; 652e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 662e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd }; 672e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 682e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy; 692e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 702e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 712e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// insertFastDiv - Substitutes the div/rem instruction with code that checks the 722e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// value of the operands and uses a shorter-faster div/rem instruction when 732e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// possible and the longer-slower div/rem instruction otherwise. 747b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszakstatic bool insertFastDiv(Function &F, 752e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Function::iterator &I, 762e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock::iterator &J, 772e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IntegerType *BypassType, 782e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseDivOp, 792e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseSignedOp, 807b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak DivCacheTy &PerBBDivCache) { 812e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Get instruction operands 822e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instruction *Instr = J; 832e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Dividend = Instr->getOperand(0); 842e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *Divisor = Instr->getOperand(1); 852e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 867b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (isa<ConstantInt>(Divisor) || 877b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak (isa<ConstantInt>(Dividend) && isa<ConstantInt>(Divisor))) { 882e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Operations with immediate values should have 892e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // been solved and replaced during compile time. 907b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return false; 912e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 922e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 932e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Basic Block is split before divide 942e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *MainBB = I; 952e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *SuccessorBB = I->splitBasicBlock(J); 967b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ++I; //advance iterator I to successorBB 972e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 982e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Add new basic block for slow divide operation 992e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *SlowBB = BasicBlock::Create(F.getContext(), "", 1002e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBB->getParent(), SuccessorBB); 1012e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowBB->moveBefore(SuccessorBB); 1022e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin()); 1032e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *SlowQuotientV; 1042e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *SlowRemainderV; 1052e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd if (UseSignedOp) { 1062e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor); 1072e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor); 1082e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } else { 1092e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor); 1102e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor); 1112e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 1122e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd SlowBuilder.CreateBr(SuccessorBB); 1132e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1142e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Add new basic block for fast divide operation 1152e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock *FastBB = BasicBlock::Create(F.getContext(), "", 1162e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBB->getParent(), SuccessorBB); 1172e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd FastBB->moveBefore(SlowBB); 1182e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> FastBuilder(FastBB, FastBB->begin()); 1197b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor, 1207b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak BypassType); 1217b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend, 1227b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak BypassType); 1232e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1242e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // udiv/urem because optimization only handles positive numbers 1252e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV, 1267b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ShortDivisorV); 1272e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV, 1282e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd ShortDivisorV); 1292e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt, 1307b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ShortQuotientV, 1317b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Dividend->getType()); 1322e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt, 1332e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd ShortRemainderV, 1342e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Dividend->getType()); 1352e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd FastBuilder.CreateBr(SuccessorBB); 1362e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1372e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Phi nodes for result of div and rem 1382e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin()); 1392e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *QuoPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2); 1402e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd QuoPhi->addIncoming(SlowQuotientV, SlowBB); 1412e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd QuoPhi->addIncoming(FastQuotientV, FastBB); 1422e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PHINode *RemPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2); 1432e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd RemPhi->addIncoming(SlowRemainderV, SlowBB); 1442e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd RemPhi->addIncoming(FastRemainderV, FastBB); 1452e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1462e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace Instr with appropriate phi node 1477b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (UseDivOp) 1482e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->replaceAllUsesWith(QuoPhi); 1497b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak else 1502e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->replaceAllUsesWith(RemPhi); 1512e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->eraseFromParent(); 1522e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1532e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Combine operands into a single value with OR for value testing below 1542e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBB->getInstList().back().eraseFromParent(); 1552e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IRBuilder<> MainBuilder(MainBB, MainBB->end()); 1562e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *OrV = MainBuilder.CreateOr(Dividend, Divisor); 1572e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1582e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // BitMask is inverted to check if the operands are 1592e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // larger than the bypass type 1602e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd uint64_t BitMask = ~BypassType->getBitMask(); 1612e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *AndV = MainBuilder.CreateAnd(OrV, BitMask); 1622e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1632e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Compare operand values and branch 1642e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *ZeroV = MainBuilder.getInt32(0); 1652e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV); 1662e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB); 1672e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1682e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // point iterator J at first instruction of successorBB 1692e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd J = I->begin(); 1702e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1712e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Cache phi nodes to be used later in place of other instances 1722e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // of div or rem with the same sign, dividend, and divisor 1732e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivOpInfo Key(UseSignedOp, Dividend, Divisor); 1742e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivPhiNodes Value(QuoPhi, RemPhi); 1752e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value)); 1767b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return true; 1772e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 1782e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1792e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// reuseOrInsertFastDiv - Reuses previously computed dividend or remainder if 1802e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// operands and operation are identical. Otherwise call insertFastDiv to perform 1812e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// the optimization and cache the resulting dividend and remainder. 1827b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszakstatic bool reuseOrInsertFastDiv(Function &F, 1832e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Function::iterator &I, 1842e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd BasicBlock::iterator &J, 1852e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd IntegerType *BypassType, 1862e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseDivOp, 1872e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseSignedOp, 1887b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak DivCacheTy &PerBBDivCache) { 1892e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Get instruction operands 1902e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instruction *Instr = J; 1912e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1)); 192be11991208f175892666887bc59fd9d32ee3e6a4Jakub Staszak DivCacheTy::iterator CacheI = PerBBDivCache.find(Key); 1932e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 1942e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd if (CacheI == PerBBDivCache.end()) { 1952e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // If previous instance does not exist, insert fast div 1967b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp, 1977b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak PerBBDivCache); 1982e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 1992e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2002e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace operation value with previously generated phi node 201be11991208f175892666887bc59fd9d32ee3e6a4Jakub Staszak DivPhiNodes &Value = CacheI->second; 2022e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd if (UseDivOp) { 2032e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace all uses of div instruction with quotient phi node 2042e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd J->replaceAllUsesWith(Value.Quotient); 2052e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } else { 2062e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Replace all uses of rem instruction with remainder phi node 2072e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd J->replaceAllUsesWith(Value.Remainder); 2082e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 2092e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2102e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Advance to next operation 2117b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak ++J; 2122e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2132e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Remove redundant operation 2142e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Instr->eraseFromParent(); 2157b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak return true; 2162e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 2172e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2182e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// bypassSlowDivision - This optimization identifies DIV instructions that can 2192e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd// be profitably bypassed and carried out with a shorter, faster divide. 2202e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurdbool bypassSlowDivision(Function &F, 2212e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd Function::iterator &I, 2227b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak const llvm::DenseMap<Type *, Type *> &BypassTypeMap) { 2232e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd DivCacheTy DivCache; 2242e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2252e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool MadeChange = false; 2262e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd for (BasicBlock::iterator J = I->begin(); J != I->end(); J++) { 2272e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2282e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Get instruction details 2292e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd unsigned Opcode = J->getOpcode(); 2302e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseDivOp = Opcode == Instruction::SDiv || Opcode == Instruction::UDiv; 2312e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd bool UseRemOp = Opcode == Instruction::SRem || Opcode == Instruction::URem; 2327b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak bool UseSignedOp = Opcode == Instruction::SDiv || 2337b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak Opcode == Instruction::SRem; 2342e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2352e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Only optimize div or rem ops 2367b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (!UseDivOp && !UseRemOp) 2372e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd continue; 2387b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak 2392e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd // Continue if div/rem type is not bypassed 2407b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak DenseMap<Type *, Type *>::const_iterator BT = 2417b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak BypassTypeMap.find(J->getType()); 2427b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak if (BT == BypassTypeMap.end()) 2432e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd continue; 2442e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2457b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak IntegerType *BypassType = cast<IntegerType>(BT->second); 2467b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak MadeChange |= reuseOrInsertFastDiv(F, I, J, BypassType, UseDivOp, 2477b2d20d0600ffbc9ae6df67a18b6f6485ebceb54Jakub Staszak UseSignedOp, DivCache); 2482e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd } 2492e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd 2502e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd return MadeChange; 2512e2efd960056bbb7e4bbd843c8de55116d52aa7dPreston Gurd} 252