1 //===-- BypassSlowDivision.cpp - Bypass slow division ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains an optimization for div and rem on architectures that
11 // execute short instructions significantly faster than longer instructions.
12 // For example, on Intel Atom 32-bit divides are slow enough that during
13 // runtime it is profitable to check the value of the operands, and if they are
14 // positive and less than 256 use an unsigned 8-bit divide.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "bypass-slow-division"
19 #include "llvm/Instructions.h"
20 #include "llvm/Function.h"
21 #include "llvm/IRBuilder.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
33 DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor)
34 : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
41 DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder)
42 : Quotient(InQuotient), Remainder(InRemainder) {}
46 struct DenseMapInfo<DivOpInfo> {
47 static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
48 return Val1.SignedOp == Val2.SignedOp &&
49 Val1.Dividend == Val2.Dividend &&
50 Val1.Divisor == Val2.Divisor;
53 static DivOpInfo getEmptyKey() {
54 return DivOpInfo(false, 0, 0);
57 static DivOpInfo getTombstoneKey() {
58 return DivOpInfo(true, 0, 0);
61 static unsigned getHashValue(const DivOpInfo &Val) {
62 return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
63 reinterpret_cast<uintptr_t>(Val.Divisor)) ^
64 (unsigned)Val.SignedOp;
68 typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy;
71 // insertFastDiv - Substitutes the div/rem instruction with code that checks the
72 // value of the operands and uses a shorter-faster div/rem instruction when
73 // possible and the longer-slower div/rem instruction otherwise.
74 static bool insertFastDiv(Function &F,
75 Function::iterator &I,
76 BasicBlock::iterator &J,
77 IntegerType *BypassType,
80 DivCacheTy &PerBBDivCache) {
81 // Get instruction operands
82 Instruction *Instr = J;
83 Value *Dividend = Instr->getOperand(0);
84 Value *Divisor = Instr->getOperand(1);
86 if (isa<ConstantInt>(Divisor) ||
87 (isa<ConstantInt>(Dividend) && isa<ConstantInt>(Divisor))) {
88 // Operations with immediate values should have
89 // been solved and replaced during compile time.
93 // Basic Block is split before divide
94 BasicBlock *MainBB = I;
95 BasicBlock *SuccessorBB = I->splitBasicBlock(J);
96 ++I; //advance iterator I to successorBB
98 // Add new basic block for slow divide operation
99 BasicBlock *SlowBB = BasicBlock::Create(F.getContext(), "",
100 MainBB->getParent(), SuccessorBB);
101 SlowBB->moveBefore(SuccessorBB);
102 IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin());
103 Value *SlowQuotientV;
104 Value *SlowRemainderV;
106 SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor);
107 SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor);
109 SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor);
110 SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor);
112 SlowBuilder.CreateBr(SuccessorBB);
114 // Add new basic block for fast divide operation
115 BasicBlock *FastBB = BasicBlock::Create(F.getContext(), "",
116 MainBB->getParent(), SuccessorBB);
117 FastBB->moveBefore(SlowBB);
118 IRBuilder<> FastBuilder(FastBB, FastBB->begin());
119 Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor,
121 Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend,
124 // udiv/urem because optimization only handles positive numbers
125 Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV,
127 Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV,
129 Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt,
131 Dividend->getType());
132 Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt,
134 Dividend->getType());
135 FastBuilder.CreateBr(SuccessorBB);
137 // Phi nodes for result of div and rem
138 IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin());
139 PHINode *QuoPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
140 QuoPhi->addIncoming(SlowQuotientV, SlowBB);
141 QuoPhi->addIncoming(FastQuotientV, FastBB);
142 PHINode *RemPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
143 RemPhi->addIncoming(SlowRemainderV, SlowBB);
144 RemPhi->addIncoming(FastRemainderV, FastBB);
146 // Replace Instr with appropriate phi node
148 Instr->replaceAllUsesWith(QuoPhi);
150 Instr->replaceAllUsesWith(RemPhi);
151 Instr->eraseFromParent();
153 // Combine operands into a single value with OR for value testing below
154 MainBB->getInstList().back().eraseFromParent();
155 IRBuilder<> MainBuilder(MainBB, MainBB->end());
156 Value *OrV = MainBuilder.CreateOr(Dividend, Divisor);
158 // BitMask is inverted to check if the operands are
159 // larger than the bypass type
160 uint64_t BitMask = ~BypassType->getBitMask();
161 Value *AndV = MainBuilder.CreateAnd(OrV, BitMask);
163 // Compare operand values and branch
164 Value *ZeroV = MainBuilder.getInt32(0);
165 Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
166 MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB);
168 // point iterator J at first instruction of successorBB
171 // Cache phi nodes to be used later in place of other instances
172 // of div or rem with the same sign, dividend, and divisor
173 DivOpInfo Key(UseSignedOp, Dividend, Divisor);
174 DivPhiNodes Value(QuoPhi, RemPhi);
175 PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value));
179 // reuseOrInsertFastDiv - Reuses previously computed dividend or remainder if
180 // operands and operation are identical. Otherwise call insertFastDiv to perform
181 // the optimization and cache the resulting dividend and remainder.
182 static bool reuseOrInsertFastDiv(Function &F,
183 Function::iterator &I,
184 BasicBlock::iterator &J,
185 IntegerType *BypassType,
188 DivCacheTy &PerBBDivCache) {
189 // Get instruction operands
190 Instruction *Instr = J;
191 DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1));
192 DivCacheTy::const_iterator CacheI = PerBBDivCache.find(Key);
194 if (CacheI == PerBBDivCache.end()) {
195 // If previous instance does not exist, insert fast div
196 return insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp,
200 // Replace operation value with previously generated phi node
201 DivPhiNodes Value = CacheI->second;
203 // Replace all uses of div instruction with quotient phi node
204 J->replaceAllUsesWith(Value.Quotient);
206 // Replace all uses of rem instruction with remainder phi node
207 J->replaceAllUsesWith(Value.Remainder);
210 // Advance to next operation
213 // Remove redundant operation
214 Instr->eraseFromParent();
218 // bypassSlowDivision - This optimization identifies DIV instructions that can
219 // be profitably bypassed and carried out with a shorter, faster divide.
220 bool bypassSlowDivision(Function &F,
221 Function::iterator &I,
222 const llvm::DenseMap<Type *, Type *> &BypassTypeMap) {
225 bool MadeChange = false;
226 for (BasicBlock::iterator J = I->begin(); J != I->end(); J++) {
228 // Get instruction details
229 unsigned Opcode = J->getOpcode();
230 bool UseDivOp = Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
231 bool UseRemOp = Opcode == Instruction::SRem || Opcode == Instruction::URem;
232 bool UseSignedOp = Opcode == Instruction::SDiv ||
233 Opcode == Instruction::SRem;
235 // Only optimize div or rem ops
236 if (!UseDivOp && !UseRemOp)
239 // Continue if div/rem type is not bypassed
240 DenseMap<Type *, Type *>::const_iterator BT =
241 BypassTypeMap.find(J->getType());
242 if (BT == BypassTypeMap.end())
245 IntegerType *BypassType = cast<IntegerType>(BT->second);
246 MadeChange |= reuseOrInsertFastDiv(F, I, J, BypassType, UseDivOp,
247 UseSignedOp, DivCache);