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 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/None.h"
21 #include "llvm/ADT/Optional.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/KnownBits.h"
37 #include "llvm/Transforms/Utils/Local.h"
43 #define DEBUG_TYPE "bypass-slow-division"
51 QuotRemPair(Value *InQuotient, Value *InRemainder)
52 : Quotient(InQuotient), Remainder(InRemainder) {}
55 /// A quotient and remainder, plus a BB from which they logically "originate".
56 /// If you use Quotient or Remainder in a Phi node, you should use BB as its
57 /// corresponding predecessor.
58 struct QuotRemWithBB {
59 BasicBlock *BB = nullptr;
60 Value *Quotient = nullptr;
61 Value *Remainder = nullptr;
64 using DivCacheTy = DenseMap<DivRemMapKey, QuotRemPair>;
65 using BypassWidthsTy = DenseMap<unsigned, unsigned>;
66 using VisitedSetTy = SmallPtrSet<Instruction *, 4>;
69 /// Operand definitely fits into BypassType. No runtime checks are needed.
71 /// A runtime check is required, as value range is unknown.
73 /// Operand is unlikely to fit into BypassType. The bypassing should be
78 class FastDivInsertionTask {
79 bool IsValidTask = false;
80 Instruction *SlowDivOrRem = nullptr;
81 IntegerType *BypassType = nullptr;
82 BasicBlock *MainBB = nullptr;
84 bool isHashLikeValue(Value *V, VisitedSetTy &Visited);
85 ValueRange getValueRange(Value *Op, VisitedSetTy &Visited);
86 QuotRemWithBB createSlowBB(BasicBlock *Successor);
87 QuotRemWithBB createFastBB(BasicBlock *Successor);
88 QuotRemPair createDivRemPhiNodes(QuotRemWithBB &LHS, QuotRemWithBB &RHS,
90 Value *insertOperandRuntimeCheck(Value *Op1, Value *Op2);
91 Optional<QuotRemPair> insertFastDivAndRem();
94 return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
95 SlowDivOrRem->getOpcode() == Instruction::SRem;
99 return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
100 SlowDivOrRem->getOpcode() == Instruction::UDiv;
103 Type *getSlowType() { return SlowDivOrRem->getType(); }
106 FastDivInsertionTask(Instruction *I, const BypassWidthsTy &BypassWidths);
108 Value *getReplacement(DivCacheTy &Cache);
111 } // end anonymous namespace
113 FastDivInsertionTask::FastDivInsertionTask(Instruction *I,
114 const BypassWidthsTy &BypassWidths) {
115 switch (I->getOpcode()) {
116 case Instruction::UDiv:
117 case Instruction::SDiv:
118 case Instruction::URem:
119 case Instruction::SRem:
123 // I is not a div/rem operation.
127 // Skip division on vector types. Only optimize integer instructions.
128 IntegerType *SlowType = dyn_cast<IntegerType>(SlowDivOrRem->getType());
132 // Skip if this bitwidth is not bypassed.
133 auto BI = BypassWidths.find(SlowType->getBitWidth());
134 if (BI == BypassWidths.end())
137 // Get type for div/rem instruction with bypass bitwidth.
138 IntegerType *BT = IntegerType::get(I->getContext(), BI->second);
141 // The original basic block.
142 MainBB = I->getParent();
144 // The instruction is indeed a slow div or rem operation.
148 /// Reuses previously-computed dividend or remainder from the current BB if
149 /// operands and operation are identical. Otherwise calls insertFastDivAndRem to
150 /// perform the optimization and caches the resulting dividend and remainder.
151 /// If no replacement can be generated, nullptr is returned.
152 Value *FastDivInsertionTask::getReplacement(DivCacheTy &Cache) {
153 // First, make sure that the task is valid.
157 // Then, look for a value in Cache.
158 Value *Dividend = SlowDivOrRem->getOperand(0);
159 Value *Divisor = SlowDivOrRem->getOperand(1);
160 DivRemMapKey Key(isSignedOp(), Dividend, Divisor);
161 auto CacheI = Cache.find(Key);
163 if (CacheI == Cache.end()) {
164 // If previous instance does not exist, try to insert fast div.
165 Optional<QuotRemPair> OptResult = insertFastDivAndRem();
166 // Bail out if insertFastDivAndRem has failed.
169 CacheI = Cache.insert({Key, *OptResult}).first;
172 QuotRemPair &Value = CacheI->second;
173 return isDivisionOp() ? Value.Quotient : Value.Remainder;
176 /// \brief Check if a value looks like a hash.
178 /// The routine is expected to detect values computed using the most common hash
179 /// algorithms. Typically, hash computations end with one of the following
182 /// 1) MUL with a constant wider than BypassType
183 /// 2) XOR instruction
185 /// And even if we are wrong and the value is not a hash, it is still quite
186 /// unlikely that such values will fit into BypassType.
188 /// To detect string hash algorithms like FNV we have to look through PHI-nodes.
189 /// It is implemented as a depth-first search for values that look neither long
191 bool FastDivInsertionTask::isHashLikeValue(Value *V, VisitedSetTy &Visited) {
192 Instruction *I = dyn_cast<Instruction>(V);
196 switch (I->getOpcode()) {
197 case Instruction::Xor:
199 case Instruction::Mul: {
200 // After Constant Hoisting pass, long constants may be represented as
201 // bitcast instructions. As a result, some constants may look like an
202 // instruction at first, and an additional check is necessary to find out if
203 // an operand is actually a constant.
204 Value *Op1 = I->getOperand(1);
205 ConstantInt *C = dyn_cast<ConstantInt>(Op1);
206 if (!C && isa<BitCastInst>(Op1))
207 C = dyn_cast<ConstantInt>(cast<BitCastInst>(Op1)->getOperand(0));
208 return C && C->getValue().getMinSignedBits() > BypassType->getBitWidth();
210 case Instruction::PHI:
211 // Stop IR traversal in case of a crazy input code. This limits recursion
213 if (Visited.size() >= 16)
215 // Do not visit nodes that have been visited already. We return true because
216 // it means that we couldn't find any value that doesn't look hash-like.
217 if (Visited.find(I) != Visited.end())
220 return llvm::all_of(cast<PHINode>(I)->incoming_values(), [&](Value *V) {
221 // Ignore undef values as they probably don't affect the division
223 return getValueRange(V, Visited) == VALRNG_LIKELY_LONG ||
231 /// Check if an integer value fits into our bypass type.
232 ValueRange FastDivInsertionTask::getValueRange(Value *V,
233 VisitedSetTy &Visited) {
234 unsigned ShortLen = BypassType->getBitWidth();
235 unsigned LongLen = V->getType()->getIntegerBitWidth();
237 assert(LongLen > ShortLen && "Value type must be wider than BypassType");
238 unsigned HiBits = LongLen - ShortLen;
240 const DataLayout &DL = SlowDivOrRem->getModule()->getDataLayout();
241 KnownBits Known(LongLen);
243 computeKnownBits(V, Known, DL);
245 if (Known.countMinLeadingZeros() >= HiBits)
246 return VALRNG_KNOWN_SHORT;
248 if (Known.countMaxLeadingZeros() < HiBits)
249 return VALRNG_LIKELY_LONG;
251 // Long integer divisions are often used in hashtable implementations. It's
252 // not worth bypassing such divisions because hash values are extremely
253 // unlikely to have enough leading zeros. The call below tries to detect
254 // values that are unlikely to fit BypassType (including hashes).
255 if (isHashLikeValue(V, Visited))
256 return VALRNG_LIKELY_LONG;
258 return VALRNG_UNKNOWN;
261 /// Add new basic block for slow div and rem operations and put it before
263 QuotRemWithBB FastDivInsertionTask::createSlowBB(BasicBlock *SuccessorBB) {
264 QuotRemWithBB DivRemPair;
265 DivRemPair.BB = BasicBlock::Create(MainBB->getParent()->getContext(), "",
266 MainBB->getParent(), SuccessorBB);
267 IRBuilder<> Builder(DivRemPair.BB, DivRemPair.BB->begin());
269 Value *Dividend = SlowDivOrRem->getOperand(0);
270 Value *Divisor = SlowDivOrRem->getOperand(1);
273 DivRemPair.Quotient = Builder.CreateSDiv(Dividend, Divisor);
274 DivRemPair.Remainder = Builder.CreateSRem(Dividend, Divisor);
276 DivRemPair.Quotient = Builder.CreateUDiv(Dividend, Divisor);
277 DivRemPair.Remainder = Builder.CreateURem(Dividend, Divisor);
280 Builder.CreateBr(SuccessorBB);
284 /// Add new basic block for fast div and rem operations and put it before
286 QuotRemWithBB FastDivInsertionTask::createFastBB(BasicBlock *SuccessorBB) {
287 QuotRemWithBB DivRemPair;
288 DivRemPair.BB = BasicBlock::Create(MainBB->getParent()->getContext(), "",
289 MainBB->getParent(), SuccessorBB);
290 IRBuilder<> Builder(DivRemPair.BB, DivRemPair.BB->begin());
292 Value *Dividend = SlowDivOrRem->getOperand(0);
293 Value *Divisor = SlowDivOrRem->getOperand(1);
294 Value *ShortDivisorV =
295 Builder.CreateCast(Instruction::Trunc, Divisor, BypassType);
296 Value *ShortDividendV =
297 Builder.CreateCast(Instruction::Trunc, Dividend, BypassType);
299 // udiv/urem because this optimization only handles positive numbers.
300 Value *ShortQV = Builder.CreateUDiv(ShortDividendV, ShortDivisorV);
301 Value *ShortRV = Builder.CreateURem(ShortDividendV, ShortDivisorV);
302 DivRemPair.Quotient =
303 Builder.CreateCast(Instruction::ZExt, ShortQV, getSlowType());
304 DivRemPair.Remainder =
305 Builder.CreateCast(Instruction::ZExt, ShortRV, getSlowType());
306 Builder.CreateBr(SuccessorBB);
311 /// Creates Phi nodes for result of Div and Rem.
312 QuotRemPair FastDivInsertionTask::createDivRemPhiNodes(QuotRemWithBB &LHS,
315 IRBuilder<> Builder(PhiBB, PhiBB->begin());
316 PHINode *QuoPhi = Builder.CreatePHI(getSlowType(), 2);
317 QuoPhi->addIncoming(LHS.Quotient, LHS.BB);
318 QuoPhi->addIncoming(RHS.Quotient, RHS.BB);
319 PHINode *RemPhi = Builder.CreatePHI(getSlowType(), 2);
320 RemPhi->addIncoming(LHS.Remainder, LHS.BB);
321 RemPhi->addIncoming(RHS.Remainder, RHS.BB);
322 return QuotRemPair(QuoPhi, RemPhi);
325 /// Creates a runtime check to test whether both the divisor and dividend fit
326 /// into BypassType. The check is inserted at the end of MainBB. True return
327 /// value means that the operands fit. Either of the operands may be NULL if it
328 /// doesn't need a runtime check.
329 Value *FastDivInsertionTask::insertOperandRuntimeCheck(Value *Op1, Value *Op2) {
330 assert((Op1 || Op2) && "Nothing to check");
331 IRBuilder<> Builder(MainBB, MainBB->end());
335 OrV = Builder.CreateOr(Op1, Op2);
337 OrV = Op1 ? Op1 : Op2;
339 // BitMask is inverted to check if the operands are
340 // larger than the bypass type
341 uint64_t BitMask = ~BypassType->getBitMask();
342 Value *AndV = Builder.CreateAnd(OrV, BitMask);
344 // Compare operand values
345 Value *ZeroV = ConstantInt::getSigned(getSlowType(), 0);
346 return Builder.CreateICmpEQ(AndV, ZeroV);
349 /// Substitutes the div/rem instruction with code that checks the value of the
350 /// operands and uses a shorter-faster div/rem instruction when possible.
351 Optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
352 Value *Dividend = SlowDivOrRem->getOperand(0);
353 Value *Divisor = SlowDivOrRem->getOperand(1);
356 ValueRange DividendRange = getValueRange(Dividend, SetL);
357 if (DividendRange == VALRNG_LIKELY_LONG)
361 ValueRange DivisorRange = getValueRange(Divisor, SetR);
362 if (DivisorRange == VALRNG_LIKELY_LONG)
365 bool DividendShort = (DividendRange == VALRNG_KNOWN_SHORT);
366 bool DivisorShort = (DivisorRange == VALRNG_KNOWN_SHORT);
368 if (DividendShort && DivisorShort) {
369 // If both operands are known to be short then just replace the long
370 // division with a short one in-place. Since we're not introducing control
371 // flow in this case, narrowing the division is always a win, even if the
372 // divisor is a constant (and will later get replaced by a multiplication).
374 IRBuilder<> Builder(SlowDivOrRem);
375 Value *TruncDividend = Builder.CreateTrunc(Dividend, BypassType);
376 Value *TruncDivisor = Builder.CreateTrunc(Divisor, BypassType);
377 Value *TruncDiv = Builder.CreateUDiv(TruncDividend, TruncDivisor);
378 Value *TruncRem = Builder.CreateURem(TruncDividend, TruncDivisor);
379 Value *ExtDiv = Builder.CreateZExt(TruncDiv, getSlowType());
380 Value *ExtRem = Builder.CreateZExt(TruncRem, getSlowType());
381 return QuotRemPair(ExtDiv, ExtRem);
384 if (isa<ConstantInt>(Divisor)) {
385 // If the divisor is not a constant, DAGCombiner will convert it to a
386 // multiplication by a magic constant. It isn't clear if it is worth
387 // introducing control flow to get a narrower multiply.
391 if (DividendShort && !isSignedOp()) {
392 // If the division is unsigned and Dividend is known to be short, then
394 // 1) Divisor is less or equal to Dividend, and the result can be computed
395 // with a short division.
396 // 2) Divisor is greater than Dividend. In this case, no division is needed
397 // at all: The quotient is 0 and the remainder is equal to Dividend.
399 // So instead of checking at runtime whether Divisor fits into BypassType,
400 // we emit a runtime check to differentiate between these two cases. This
401 // lets us entirely avoid a long div.
403 // Split the basic block before the div/rem.
404 BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDivOrRem);
405 // Remove the unconditional branch from MainBB to SuccessorBB.
406 MainBB->getInstList().back().eraseFromParent();
409 Long.Quotient = ConstantInt::get(getSlowType(), 0);
410 Long.Remainder = Dividend;
411 QuotRemWithBB Fast = createFastBB(SuccessorBB);
412 QuotRemPair Result = createDivRemPhiNodes(Fast, Long, SuccessorBB);
413 IRBuilder<> Builder(MainBB, MainBB->end());
414 Value *CmpV = Builder.CreateICmpUGE(Dividend, Divisor);
415 Builder.CreateCondBr(CmpV, Fast.BB, SuccessorBB);
418 // General case. Create both slow and fast div/rem pairs and choose one of
421 // Split the basic block before the div/rem.
422 BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDivOrRem);
423 // Remove the unconditional branch from MainBB to SuccessorBB.
424 MainBB->getInstList().back().eraseFromParent();
425 QuotRemWithBB Fast = createFastBB(SuccessorBB);
426 QuotRemWithBB Slow = createSlowBB(SuccessorBB);
427 QuotRemPair Result = createDivRemPhiNodes(Fast, Slow, SuccessorBB);
428 Value *CmpV = insertOperandRuntimeCheck(DividendShort ? nullptr : Dividend,
429 DivisorShort ? nullptr : Divisor);
430 IRBuilder<> Builder(MainBB, MainBB->end());
431 Builder.CreateCondBr(CmpV, Fast.BB, Slow.BB);
436 /// This optimization identifies DIV/REM instructions in a BB that can be
437 /// profitably bypassed and carried out with a shorter, faster divide.
438 bool llvm::bypassSlowDivision(BasicBlock *BB,
439 const BypassWidthsTy &BypassWidths) {
440 DivCacheTy PerBBDivCache;
442 bool MadeChange = false;
443 Instruction* Next = &*BB->begin();
444 while (Next != nullptr) {
445 // We may add instructions immediately after I, but we want to skip over
447 Instruction* I = Next;
448 Next = Next->getNextNode();
450 FastDivInsertionTask Task(I, BypassWidths);
451 if (Value *Replacement = Task.getReplacement(PerBBDivCache)) {
452 I->replaceAllUsesWith(Replacement);
453 I->eraseFromParent();
458 // Above we eagerly create divs and rems, as pairs, so that we can efficiently
459 // create divrem machine instructions. Now erase any unused divs / rems so we
460 // don't leave extra instructions sitting around.
461 for (auto &KV : PerBBDivCache)
462 for (Value *V : {KV.second.Quotient, KV.second.Remainder})
463 RecursivelyDeleteTriviallyDeadInstructions(V);