1//===- BypassSlowDivision.cpp - Bypass slow division ----------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains an optimization for div and rem on architectures that
10// execute short instructions significantly faster than longer instructions.
11// For example, on Intel Atom 32-bit divides are slow enough that during
12// runtime it is profitable to check the value of the operands, and if they are
13// positive and less than 256 use an unsigned 8-bit divide.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/Utils/BypassSlowDivision.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/Analysis/BranchProbabilityInfo.h"
22#include "llvm/Analysis/DomTreeUpdater.h"
23#include "llvm/Analysis/LoopInfo.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/ProfDataUtils.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/BasicBlockUtils.h"
38#include "llvm/Transforms/Utils/Local.h"
39#include <cassert>
40
41using namespace llvm;
42
43#define DEBUG_TYPE "bypass-slow-division"
44
45namespace {
46
47struct QuotRemPair {
48 Value *Quotient;
49 Value *Remainder;
50
51 QuotRemPair(Value *InQuotient, Value *InRemainder)
52 : Quotient(InQuotient), Remainder(InRemainder) {}
53};
54
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.
58struct QuotRemWithBB {
59 BasicBlock *BB = nullptr;
60 Value *Quotient = nullptr;
61 Value *Remainder = nullptr;
62};
63
64using DivCacheTy = DenseMap<DivRemMapKey, QuotRemPair>;
65using BypassWidthsTy = DenseMap<unsigned, unsigned>;
66using VisitedSetTy = SmallPtrSet<Instruction *, 4>;
67
68enum ValueRange {
69 /// Operand definitely fits into BypassType. No runtime checks are needed.
70 VALRNG_KNOWN_SHORT,
71 /// A runtime check is required, as value range is unknown.
72 VALRNG_UNKNOWN,
73 /// Operand is unlikely to fit into BypassType. The bypassing should be
74 /// disabled.
75 VALRNG_LIKELY_LONG
76};
77
78class FastDivInsertionTask {
79 bool IsValidTask = false;
80 Instruction *SlowDivOrRem = nullptr;
81 IntegerType *BypassType = nullptr;
82 BasicBlock *MainBB = nullptr;
83 DomTreeUpdater *DTU = nullptr;
84 LoopInfo *LI = nullptr;
85 BranchProbabilityInfo *BPI = nullptr;
86
87 BasicBlock *splitMainBB();
88 bool isHashLikeValue(Value *V, VisitedSetTy &Visited);
89 ValueRange getValueRange(Value *Op, VisitedSetTy &Visited);
90 QuotRemWithBB createSlowBB(BasicBlock *Successor);
91 QuotRemWithBB createFastBB(BasicBlock *Successor);
92 QuotRemPair createDivRemPhiNodes(QuotRemWithBB &LHS, QuotRemWithBB &RHS,
93 BasicBlock *PhiBB);
94 Value *insertOperandRuntimeCheck(Value *Op1, Value *Op2);
95 std::optional<QuotRemPair> insertFastDivAndRem();
96
97 bool isSignedOp() {
98 return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
99 SlowDivOrRem->getOpcode() == Instruction::SRem;
100 }
101
102 bool isDivisionOp() {
103 return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
104 SlowDivOrRem->getOpcode() == Instruction::UDiv;
105 }
106
107 Type *getSlowType() { return SlowDivOrRem->getType(); }
108
109public:
110 FastDivInsertionTask(Instruction *I, const BypassWidthsTy &BypassWidths,
111 DomTreeUpdater *DTU, LoopInfo *LI,
112 BranchProbabilityInfo *BPI);
113
114 Value *getReplacement(DivCacheTy &Cache);
115};
116
117} // end anonymous namespace
118
119FastDivInsertionTask::FastDivInsertionTask(Instruction *I,
120 const BypassWidthsTy &BypassWidths,
121 DomTreeUpdater *DTU, LoopInfo *LI,
122 BranchProbabilityInfo *BPI)
123 : DTU(DTU), LI(LI), BPI(BPI) {
124 switch (I->getOpcode()) {
125 case Instruction::UDiv:
126 case Instruction::SDiv:
127 case Instruction::URem:
128 case Instruction::SRem:
129 SlowDivOrRem = I;
130 break;
131 default:
132 // I is not a div/rem operation.
133 return;
134 }
135
136 // Skip division on vector types. Only optimize integer instructions.
137 IntegerType *SlowType = dyn_cast<IntegerType>(Val: SlowDivOrRem->getType());
138 if (!SlowType)
139 return;
140
141 // Skip if this bitwidth is not bypassed.
142 auto BI = BypassWidths.find(Val: SlowType->getBitWidth());
143 if (BI == BypassWidths.end())
144 return;
145
146 // Get type for div/rem instruction with bypass bitwidth.
147 IntegerType *BT = IntegerType::get(C&: I->getContext(), NumBits: BI->second);
148 BypassType = BT;
149
150 // The original basic block.
151 MainBB = I->getParent();
152
153 // The instruction is indeed a slow div or rem operation.
154 IsValidTask = true;
155}
156
157/// Reuses previously-computed dividend or remainder from the current BB if
158/// operands and operation are identical. Otherwise calls insertFastDivAndRem to
159/// perform the optimization and caches the resulting dividend and remainder.
160/// If no replacement can be generated, nullptr is returned.
161Value *FastDivInsertionTask::getReplacement(DivCacheTy &Cache) {
162 // First, make sure that the task is valid.
163 if (!IsValidTask)
164 return nullptr;
165
166 // Then, look for a value in Cache.
167 Value *Dividend = SlowDivOrRem->getOperand(i: 0);
168 Value *Divisor = SlowDivOrRem->getOperand(i: 1);
169 DivRemMapKey Key(isSignedOp(), Dividend, Divisor);
170 auto CacheI = Cache.find(Val: Key);
171
172 if (CacheI == Cache.end()) {
173 // If previous instance does not exist, try to insert fast div.
174 std::optional<QuotRemPair> OptResult = insertFastDivAndRem();
175 // Bail out if insertFastDivAndRem has failed.
176 if (!OptResult)
177 return nullptr;
178 CacheI = Cache.insert(KV: {Key, *OptResult}).first;
179 }
180
181 QuotRemPair &Value = CacheI->second;
182 return isDivisionOp() ? Value.Quotient : Value.Remainder;
183}
184
185/// Check if a value looks like a hash.
186///
187/// The routine is expected to detect values computed using the most common hash
188/// algorithms. Typically, hash computations end with one of the following
189/// instructions:
190///
191/// 1) MUL with a constant wider than BypassType
192/// 2) XOR instruction
193///
194/// And even if we are wrong and the value is not a hash, it is still quite
195/// unlikely that such values will fit into BypassType.
196///
197/// To detect string hash algorithms like FNV we have to look through PHI-nodes.
198/// It is implemented as a depth-first search for values that look neither long
199/// nor hash-like.
200bool FastDivInsertionTask::isHashLikeValue(Value *V, VisitedSetTy &Visited) {
201 Instruction *I = dyn_cast<Instruction>(Val: V);
202 if (!I)
203 return false;
204
205 switch (I->getOpcode()) {
206 case Instruction::Xor:
207 return true;
208 case Instruction::Mul: {
209 // After Constant Hoisting pass, long constants may be represented as
210 // bitcast instructions. As a result, some constants may look like an
211 // instruction at first, and an additional check is necessary to find out if
212 // an operand is actually a constant.
213 Value *Op1 = I->getOperand(i: 1);
214 ConstantInt *C = dyn_cast<ConstantInt>(Val: Op1);
215 if (!C && isa<BitCastInst>(Val: Op1))
216 C = dyn_cast<ConstantInt>(Val: cast<BitCastInst>(Val: Op1)->getOperand(i_nocapture: 0));
217 return C && C->getValue().getSignificantBits() > BypassType->getBitWidth();
218 }
219 case Instruction::PHI:
220 // Stop IR traversal in case of a crazy input code. This limits recursion
221 // depth.
222 if (Visited.size() >= 16)
223 return false;
224 // Do not visit nodes that have been visited already. We return true because
225 // it means that we couldn't find any value that doesn't look hash-like.
226 if (!Visited.insert(Ptr: I).second)
227 return true;
228 return llvm::all_of(Range: cast<PHINode>(Val: I)->incoming_values(), P: [&](Value *V) {
229 // Ignore undef values as they probably don't affect the division
230 // operands.
231 return getValueRange(Op: V, Visited) == VALRNG_LIKELY_LONG ||
232 isa<UndefValue>(Val: V);
233 });
234 default:
235 return false;
236 }
237}
238
239/// Check if an integer value fits into our bypass type.
240ValueRange FastDivInsertionTask::getValueRange(Value *V,
241 VisitedSetTy &Visited) {
242 unsigned ShortLen = BypassType->getBitWidth();
243 unsigned LongLen = V->getType()->getIntegerBitWidth();
244
245 assert(LongLen > ShortLen && "Value type must be wider than BypassType");
246 unsigned HiBits = LongLen - ShortLen;
247
248 const DataLayout &DL = SlowDivOrRem->getDataLayout();
249 KnownBits Known(LongLen);
250
251 computeKnownBits(V, Known, DL);
252
253 if (Known.countMinLeadingZeros() >= HiBits)
254 return VALRNG_KNOWN_SHORT;
255
256 if (Known.countMaxLeadingZeros() < HiBits)
257 return VALRNG_LIKELY_LONG;
258
259 // Long integer divisions are often used in hashtable implementations. It's
260 // not worth bypassing such divisions because hash values are extremely
261 // unlikely to have enough leading zeros. The call below tries to detect
262 // values that are unlikely to fit BypassType (including hashes).
263 if (isHashLikeValue(V, Visited))
264 return VALRNG_LIKELY_LONG;
265
266 return VALRNG_UNKNOWN;
267}
268
269// Split MainBB and keep BPI up-to-date if its present.
270BasicBlock *FastDivInsertionTask::splitMainBB() {
271 SmallVector<BranchProbability, 4> ExitProbs;
272 if (BPI)
273 for (unsigned I = 0, E = MainBB->getTerminator()->getNumSuccessors();
274 I != E; ++I)
275 ExitProbs.push_back(Elt: BPI->getEdgeProbability(Src: MainBB, IndexInSuccessors: I));
276
277 BasicBlock *SuccessorBB = SplitBlock(Old: MainBB, SplitPt: SlowDivOrRem, DTU, LI);
278 MainBB->back().eraseFromParent();
279
280 if (BPI) {
281 BPI->setEdgeProbability(Src: SuccessorBB, Probs: ExitProbs);
282 BPI->eraseBlock(BB: MainBB);
283 }
284 return SuccessorBB;
285}
286
287/// Add new basic block for slow div and rem operations and put it before
288/// SuccessorBB.
289QuotRemWithBB FastDivInsertionTask::createSlowBB(BasicBlock *SuccessorBB) {
290 QuotRemWithBB DivRemPair;
291 DivRemPair.BB = BasicBlock::Create(Context&: MainBB->getParent()->getContext(), Name: "",
292 Parent: MainBB->getParent(), InsertBefore: SuccessorBB);
293 IRBuilder<> Builder(DivRemPair.BB->begin());
294 Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
295
296 Value *Dividend = SlowDivOrRem->getOperand(i: 0);
297 Value *Divisor = SlowDivOrRem->getOperand(i: 1);
298
299 if (isSignedOp()) {
300 DivRemPair.Quotient = Builder.CreateSDiv(LHS: Dividend, RHS: Divisor);
301 DivRemPair.Remainder = Builder.CreateSRem(LHS: Dividend, RHS: Divisor);
302 } else {
303 DivRemPair.Quotient = Builder.CreateUDiv(LHS: Dividend, RHS: Divisor);
304 DivRemPair.Remainder = Builder.CreateURem(LHS: Dividend, RHS: Divisor);
305 }
306
307 Builder.CreateBr(Dest: SuccessorBB);
308 return DivRemPair;
309}
310
311/// Add new basic block for fast div and rem operations and put it before
312/// SuccessorBB.
313QuotRemWithBB FastDivInsertionTask::createFastBB(BasicBlock *SuccessorBB) {
314 QuotRemWithBB DivRemPair;
315 DivRemPair.BB = BasicBlock::Create(Context&: MainBB->getParent()->getContext(), Name: "",
316 Parent: MainBB->getParent(), InsertBefore: SuccessorBB);
317 IRBuilder<> Builder(DivRemPair.BB->begin());
318 Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
319
320 Value *Dividend = SlowDivOrRem->getOperand(i: 0);
321 Value *Divisor = SlowDivOrRem->getOperand(i: 1);
322 Value *ShortDivisorV =
323 Builder.CreateCast(Op: Instruction::Trunc, V: Divisor, DestTy: BypassType);
324 Value *ShortDividendV =
325 Builder.CreateCast(Op: Instruction::Trunc, V: Dividend, DestTy: BypassType);
326
327 // udiv/urem because this optimization only handles positive numbers.
328 Value *ShortQV = Builder.CreateUDiv(LHS: ShortDividendV, RHS: ShortDivisorV);
329 Value *ShortRV = Builder.CreateURem(LHS: ShortDividendV, RHS: ShortDivisorV);
330 DivRemPair.Quotient =
331 Builder.CreateCast(Op: Instruction::ZExt, V: ShortQV, DestTy: getSlowType());
332 DivRemPair.Remainder =
333 Builder.CreateCast(Op: Instruction::ZExt, V: ShortRV, DestTy: getSlowType());
334 Builder.CreateBr(Dest: SuccessorBB);
335
336 return DivRemPair;
337}
338
339/// Creates Phi nodes for result of Div and Rem.
340QuotRemPair FastDivInsertionTask::createDivRemPhiNodes(QuotRemWithBB &LHS,
341 QuotRemWithBB &RHS,
342 BasicBlock *PhiBB) {
343 IRBuilder<> Builder(PhiBB->begin());
344 Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
345 PHINode *QuoPhi = Builder.CreatePHI(Ty: getSlowType(), NumReservedValues: 2);
346 QuoPhi->addIncoming(V: LHS.Quotient, BB: LHS.BB);
347 QuoPhi->addIncoming(V: RHS.Quotient, BB: RHS.BB);
348 PHINode *RemPhi = Builder.CreatePHI(Ty: getSlowType(), NumReservedValues: 2);
349 RemPhi->addIncoming(V: LHS.Remainder, BB: LHS.BB);
350 RemPhi->addIncoming(V: RHS.Remainder, BB: RHS.BB);
351 return QuotRemPair(QuoPhi, RemPhi);
352}
353
354/// Creates a runtime check to test whether both the divisor and dividend fit
355/// into BypassType. The check is inserted at the end of MainBB. True return
356/// value means that the operands fit. Either of the operands may be NULL if it
357/// doesn't need a runtime check.
358Value *FastDivInsertionTask::insertOperandRuntimeCheck(Value *Op1, Value *Op2) {
359 assert((Op1 || Op2) && "Nothing to check");
360 IRBuilder<> Builder(MainBB->end());
361 Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
362
363 Value *OrV;
364 if (Op1 && Op2)
365 OrV = Builder.CreateOr(LHS: Op1, RHS: Op2);
366 else
367 OrV = Op1 ? Op1 : Op2;
368
369 // Check whether the operands are larger than the bypass type.
370 Value *AndV = Builder.CreateAnd(
371 LHS: OrV, RHS: APInt::getBitsSetFrom(numBits: OrV->getType()->getIntegerBitWidth(),
372 loBit: BypassType->getBitWidth()));
373
374 // Compare operand values
375 Value *ZeroV = ConstantInt::getSigned(Ty: getSlowType(), V: 0);
376 return Builder.CreateICmpEQ(LHS: AndV, RHS: ZeroV);
377}
378
379/// Substitutes the div/rem instruction with code that checks the value of the
380/// operands and uses a shorter-faster div/rem instruction when possible.
381std::optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
382 Value *Dividend = SlowDivOrRem->getOperand(i: 0);
383 Value *Divisor = SlowDivOrRem->getOperand(i: 1);
384
385 VisitedSetTy SetL;
386 ValueRange DividendRange = getValueRange(V: Dividend, Visited&: SetL);
387 if (DividendRange == VALRNG_LIKELY_LONG)
388 return std::nullopt;
389
390 VisitedSetTy SetR;
391 ValueRange DivisorRange = getValueRange(V: Divisor, Visited&: SetR);
392 if (DivisorRange == VALRNG_LIKELY_LONG)
393 return std::nullopt;
394
395 bool DividendShort = (DividendRange == VALRNG_KNOWN_SHORT);
396 bool DivisorShort = (DivisorRange == VALRNG_KNOWN_SHORT);
397
398 if (DividendShort && DivisorShort) {
399 // If both operands are known to be short then just replace the long
400 // division with a short one in-place. Since we're not introducing control
401 // flow in this case, narrowing the division is always a win, even if the
402 // divisor is a constant (and will later get replaced by a multiplication).
403
404 IRBuilder<> Builder(SlowDivOrRem);
405 Value *TruncDividend = Builder.CreateTrunc(V: Dividend, DestTy: BypassType);
406 Value *TruncDivisor = Builder.CreateTrunc(V: Divisor, DestTy: BypassType);
407 Value *TruncDiv = Builder.CreateUDiv(LHS: TruncDividend, RHS: TruncDivisor);
408 Value *TruncRem = Builder.CreateURem(LHS: TruncDividend, RHS: TruncDivisor);
409 Value *ExtDiv = Builder.CreateZExt(V: TruncDiv, DestTy: getSlowType());
410 Value *ExtRem = Builder.CreateZExt(V: TruncRem, DestTy: getSlowType());
411 return QuotRemPair(ExtDiv, ExtRem);
412 }
413
414 if (isa<ConstantInt>(Val: Divisor)) {
415 // If the divisor is a constant, DAGCombiner will convert it to a
416 // multiplication by a magic constant. It isn't clear if it is worth
417 // introducing control flow to get a narrower multiply.
418 return std::nullopt;
419 }
420
421 // After Constant Hoisting pass, long constants may be represented as
422 // bitcast instructions. As a result, some constants may look like an
423 // instruction at first, and an additional check is necessary to find out if
424 // an operand is actually a constant.
425 if (auto *BCI = dyn_cast<BitCastInst>(Val: Divisor))
426 if (BCI->getParent() == SlowDivOrRem->getParent() &&
427 isa<ConstantInt>(Val: BCI->getOperand(i_nocapture: 0)))
428 return std::nullopt;
429
430 IRBuilder<> Builder(MainBB->end());
431 Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
432
433 if (DividendShort && !isSignedOp()) {
434 // If the division is unsigned and Dividend is known to be short, then
435 // either
436 // 1) Divisor is less or equal to Dividend, and the result can be computed
437 // with a short division.
438 // 2) Divisor is greater than Dividend. In this case, no division is needed
439 // at all: The quotient is 0 and the remainder is equal to Dividend.
440 //
441 // So instead of checking at runtime whether Divisor fits into BypassType,
442 // we emit a runtime check to differentiate between these two cases. This
443 // lets us entirely avoid a long div.
444
445 // Split the basic block before the div/rem.
446 BasicBlock *SuccessorBB = splitMainBB();
447 QuotRemWithBB Long;
448 Long.BB = MainBB;
449 Long.Quotient = ConstantInt::get(Ty: getSlowType(), V: 0);
450 Long.Remainder = Dividend;
451 QuotRemWithBB Fast = createFastBB(SuccessorBB);
452 QuotRemPair Result = createDivRemPhiNodes(LHS&: Fast, RHS&: Long, PhiBB: SuccessorBB);
453 Value *CmpV = Builder.CreateICmpUGE(LHS: Dividend, RHS: Divisor);
454 CondBrInst *CB = Builder.CreateCondBr(Cond: CmpV, True: Fast.BB, False: SuccessorBB);
455 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *CB, DEBUG_TYPE);
456
457 if (DTU)
458 DTU->applyUpdates(Updates: {{DominatorTree::Insert, MainBB, Fast.BB},
459 {DominatorTree::Insert, Fast.BB, SuccessorBB}});
460 if (LI) {
461 if (Loop *L = LI->getLoopFor(BB: MainBB))
462 L->addBasicBlockToLoop(NewBB: Fast.BB, LI&: *LI);
463 }
464
465 return Result;
466 }
467
468 // General case. Create both slow and fast div/rem pairs and choose one of
469 // them at runtime.
470
471 // Split the basic block before the div/rem.
472 BasicBlock *SuccessorBB = splitMainBB();
473 QuotRemWithBB Fast = createFastBB(SuccessorBB);
474 QuotRemWithBB Slow = createSlowBB(SuccessorBB);
475 QuotRemPair Result = createDivRemPhiNodes(LHS&: Fast, RHS&: Slow, PhiBB: SuccessorBB);
476 Value *CmpV = insertOperandRuntimeCheck(Op1: DividendShort ? nullptr : Dividend,
477 Op2: DivisorShort ? nullptr : Divisor);
478 CondBrInst *CB = Builder.CreateCondBr(Cond: CmpV, True: Fast.BB, False: Slow.BB);
479 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *CB, DEBUG_TYPE);
480 if (DTU)
481 DTU->applyUpdates(Updates: {{DominatorTree::Insert, MainBB, Fast.BB},
482 {DominatorTree::Insert, MainBB, Slow.BB},
483 {DominatorTree::Insert, Fast.BB, SuccessorBB},
484 {DominatorTree::Insert, Slow.BB, SuccessorBB},
485 {DominatorTree::Delete, MainBB, SuccessorBB}});
486 if (LI) {
487 if (Loop *L = LI->getLoopFor(BB: MainBB)) {
488 L->addBasicBlockToLoop(NewBB: Fast.BB, LI&: *LI);
489 L->addBasicBlockToLoop(NewBB: Slow.BB, LI&: *LI);
490 }
491 }
492 return Result;
493}
494
495/// This optimization identifies DIV/REM instructions in a BB that can be
496/// profitably bypassed and carried out with a shorter, faster divide.
497bool llvm::bypassSlowDivision(BasicBlock *BB,
498 const BypassWidthsTy &BypassWidths,
499 DomTreeUpdater *DTU, LoopInfo *LI,
500 BranchProbabilityInfo *BPI) {
501 DivCacheTy PerBBDivCache;
502
503 bool MadeChange = false;
504 Instruction *Next = &*BB->begin();
505 while (Next != nullptr) {
506 // We may add instructions immediately after I, but we want to skip over
507 // them.
508 Instruction *I = Next;
509 Next = Next->getNextNode();
510
511 // Ignore dead code to save time and avoid bugs.
512 if (I->use_empty())
513 continue;
514
515 FastDivInsertionTask Task(I, BypassWidths, DTU, LI, BPI);
516 if (Value *Replacement = Task.getReplacement(Cache&: PerBBDivCache)) {
517 I->replaceAllUsesWith(V: Replacement);
518 I->eraseFromParent();
519 MadeChange = true;
520 }
521 }
522
523 // Above we eagerly create divs and rems, as pairs, so that we can efficiently
524 // create divrem machine instructions. Now erase any unused divs / rems so we
525 // don't leave extra instructions sitting around.
526 for (auto &KV : PerBBDivCache)
527 for (Value *V : {KV.second.Quotient, KV.second.Remainder})
528 RecursivelyDeleteTriviallyDeadInstructions(V);
529
530 return MadeChange;
531}
532