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