1//===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
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 implements induction variable simplification. It does
10// not define any actual pass or policy, but provides a single function to
11// simplify a loop's induction variables based on ScalarEvolution.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Utils/SimplifyIndVar.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/Analysis/LoopInfo.h"
19#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20#include "llvm/Analysis/ValueTracking.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/PatternMatch.h"
26#include "llvm/IR/ProfDataUtils.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/Transforms/Utils/Local.h"
30#include "llvm/Transforms/Utils/LoopUtils.h"
31#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
32
33using namespace llvm;
34using namespace llvm::PatternMatch;
35
36#define DEBUG_TYPE "indvars"
37
38STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
39STATISTIC(NumElimOperand, "Number of IV operands folded into a use");
40STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
41STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");
42STATISTIC(
43 NumSimplifiedSDiv,
44 "Number of IV signed division operations converted to unsigned division");
45STATISTIC(
46 NumSimplifiedSRem,
47 "Number of IV signed remainder operations converted to unsigned remainder");
48STATISTIC(NumElimCmp, "Number of IV comparisons eliminated");
49STATISTIC(NumInvariantCmp, "Number of IV comparisons made loop invariant");
50STATISTIC(NumSameSign, "Number of IV comparisons with new samesign flags");
51
52namespace {
53 /// This is a utility for simplifying induction variables
54 /// based on ScalarEvolution. It is the primary instrument of the
55 /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
56 /// other loop passes that preserve SCEV.
57 class SimplifyIndvar {
58 Loop *L;
59 LoopInfo *LI;
60 ScalarEvolution *SE;
61 DominatorTree *DT;
62 const TargetTransformInfo *TTI;
63 SCEVExpander &Rewriter;
64 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
65
66 bool Changed = false;
67 bool RunUnswitching = false;
68
69 public:
70 SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
71 LoopInfo *LI, const TargetTransformInfo *TTI,
72 SCEVExpander &Rewriter,
73 SmallVectorImpl<WeakTrackingVH> &Dead)
74 : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),
75 DeadInsts(Dead) {
76 assert(LI && "IV simplification requires LoopInfo");
77 }
78
79 bool hasChanged() const { return Changed; }
80 bool runUnswitching() const { return RunUnswitching; }
81
82 /// Iteratively perform simplification on a worklist of users of the
83 /// specified induction variable. This is the top-level driver that applies
84 /// all simplifications to users of an IV.
85 void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
86
87 void pushIVUsers(Instruction *Def,
88 SmallPtrSet<Instruction *, 16> &Simplified,
89 SmallVectorImpl<std::pair<Instruction *, Instruction *>>
90 &SimpleIVUsers);
91
92 Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
93
94 bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
95 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
96 bool replaceFloatIVWithIntegerIV(Instruction *UseInst);
97
98 bool eliminateOverflowIntrinsic(WithOverflowInst *WO);
99 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);
100 bool eliminateTrunc(TruncInst *TI);
101 bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
102 bool makeIVComparisonInvariant(ICmpInst *ICmp, Instruction *IVOperand);
103 void eliminateIVComparison(ICmpInst *ICmp, Instruction *IVOperand);
104 void simplifyIVRemainder(BinaryOperator *Rem, Instruction *IVOperand,
105 bool IsSigned);
106 void replaceRemWithNumerator(BinaryOperator *Rem);
107 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
108 bool replaceRemWithNumeratorOrZeroUpdateProfiles(SelectInst &SI);
109 void replaceSRemWithURem(BinaryOperator *Rem);
110 bool eliminateSDiv(BinaryOperator *SDiv);
111 bool strengthenBinaryOp(BinaryOperator *BO, Instruction *IVOperand);
112 bool strengthenOverflowingOperation(BinaryOperator *OBO,
113 Instruction *IVOperand);
114 bool strengthenRightShift(BinaryOperator *BO, Instruction *IVOperand);
115 };
116}
117
118/// Find a point in code which dominates all given instructions. We can safely
119/// assume that, whatever fact we can prove at the found point, this fact is
120/// also true for each of the given instructions.
121static Instruction *findCommonDominator(ArrayRef<Instruction *> Instructions,
122 DominatorTree &DT) {
123 Instruction *CommonDom = nullptr;
124 for (auto *Insn : Instructions)
125 CommonDom =
126 CommonDom ? DT.findNearestCommonDominator(I1: CommonDom, I2: Insn) : Insn;
127 assert(CommonDom && "Common dominator not found?");
128 return CommonDom;
129}
130
131/// Fold an IV operand into its use. This removes increments of an
132/// aligned IV when used by a instruction that ignores the low bits.
133///
134/// IVOperand is guaranteed SCEVable, but UseInst may not be.
135///
136/// Return the operand of IVOperand for this induction variable if IVOperand can
137/// be folded (in case more folding opportunities have been exposed).
138/// Otherwise return null.
139Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
140 Value *IVSrc = nullptr;
141 const unsigned OperIdx = 0;
142 const SCEV *FoldedExpr = nullptr;
143 bool MustDropExactFlag = false;
144 switch (UseInst->getOpcode()) {
145 default:
146 return nullptr;
147 case Instruction::UDiv:
148 case Instruction::LShr:
149 // We're only interested in the case where we know something about
150 // the numerator and have a constant denominator.
151 if (IVOperand != UseInst->getOperand(i: OperIdx) ||
152 !isa<ConstantInt>(Val: UseInst->getOperand(i: 1)))
153 return nullptr;
154
155 // Attempt to fold a binary operator with constant operand.
156 // e.g. ((I + 1) >> 2) => I >> 2
157 if (!isa<BinaryOperator>(Val: IVOperand)
158 || !isa<ConstantInt>(Val: IVOperand->getOperand(i: 1)))
159 return nullptr;
160
161 IVSrc = IVOperand->getOperand(i: 0);
162 // IVSrc must be the (SCEVable) IV, since the other operand is const.
163 assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
164
165 ConstantInt *D = cast<ConstantInt>(Val: UseInst->getOperand(i: 1));
166 if (UseInst->getOpcode() == Instruction::LShr) {
167 // Get a constant for the divisor. See createSCEV.
168 uint32_t BitWidth = cast<IntegerType>(Val: UseInst->getType())->getBitWidth();
169 if (D->getValue().uge(RHS: BitWidth))
170 return nullptr;
171
172 D = ConstantInt::get(Context&: UseInst->getContext(),
173 V: APInt::getOneBitSet(numBits: BitWidth, BitNo: D->getZExtValue()));
174 }
175 const SCEV *LHS = SE->getSCEV(V: IVSrc);
176 const SCEV *RHS = SE->getSCEV(V: D);
177 FoldedExpr = SE->getUDivExpr(LHS, RHS);
178 // We might have 'exact' flag set at this point which will no longer be
179 // correct after we make the replacement.
180 if (UseInst->isExact() && LHS != SE->getMulExpr(LHS: FoldedExpr, RHS))
181 MustDropExactFlag = true;
182 }
183 // We have something that might fold it's operand. Compare SCEVs.
184 if (!SE->isSCEVable(Ty: UseInst->getType()))
185 return nullptr;
186
187 // Bypass the operand if SCEV can prove it has no effect.
188 if (SE->getSCEV(V: UseInst) != FoldedExpr)
189 return nullptr;
190
191 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
192 << " -> " << *UseInst << '\n');
193
194 UseInst->setOperand(i: OperIdx, Val: IVSrc);
195 assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
196
197 if (MustDropExactFlag)
198 UseInst->dropPoisonGeneratingFlags();
199
200 ++NumElimOperand;
201 Changed = true;
202 if (IVOperand->use_empty())
203 DeadInsts.emplace_back(Args&: IVOperand);
204 return IVSrc;
205}
206
207bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
208 Instruction *IVOperand) {
209 auto *Preheader = L->getLoopPreheader();
210 if (!Preheader)
211 return false;
212 unsigned IVOperIdx = 0;
213 CmpPredicate Pred = ICmp->getCmpPredicate();
214 if (IVOperand != ICmp->getOperand(i_nocapture: 0)) {
215 // Swapped
216 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
217 IVOperIdx = 1;
218 Pred = ICmpInst::getSwappedCmpPredicate(Pred);
219 }
220
221 // Get the SCEVs for the ICmp operands (in the specific context of the
222 // current loop)
223 const Loop *ICmpLoop = LI->getLoopFor(BB: ICmp->getParent());
224 const SCEV *S = SE->getSCEVAtScope(V: ICmp->getOperand(i_nocapture: IVOperIdx), L: ICmpLoop);
225 const SCEV *X = SE->getSCEVAtScope(V: ICmp->getOperand(i_nocapture: 1 - IVOperIdx), L: ICmpLoop);
226 auto LIP = SE->getLoopInvariantPredicate(Pred, LHS: S, RHS: X, L, CtxI: ICmp);
227 if (!LIP)
228 return false;
229 ICmpInst::Predicate InvariantPredicate = LIP->Pred;
230 const SCEV *InvariantLHS = LIP->LHS;
231 const SCEV *InvariantRHS = LIP->RHS;
232
233 // Do not generate something ridiculous.
234 auto *PHTerm = Preheader->getTerminator();
235 if (Rewriter.isHighCostExpansion(Exprs: {InvariantLHS, InvariantRHS}, L,
236 Budget: 2 * SCEVCheapExpansionBudget, TTI, At: PHTerm) ||
237 !Rewriter.isSafeToExpandAt(S: InvariantLHS, InsertionPoint: PHTerm) ||
238 !Rewriter.isSafeToExpandAt(S: InvariantRHS, InsertionPoint: PHTerm))
239 return false;
240 auto *NewLHS =
241 Rewriter.expandCodeFor(SH: InvariantLHS, Ty: IVOperand->getType(), I: PHTerm);
242 auto *NewRHS =
243 Rewriter.expandCodeFor(SH: InvariantRHS, Ty: IVOperand->getType(), I: PHTerm);
244 LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
245 IRBuilder<> Builder(PHTerm);
246 Builder.SetCurrentDebugLocation(DebugLoc::getDropped());
247 Value *NewICmp = Builder.CreateICmp(P: InvariantPredicate, LHS: NewLHS, RHS: NewRHS, Name: "",
248 HasSameSign: ICmp->hasSameSign());
249 NewICmp->takeName(V: ICmp);
250 ICmp->replaceAllUsesWith(V: NewICmp);
251 DeadInsts.emplace_back(Args&: ICmp);
252 RunUnswitching = true;
253 return true;
254}
255
256/// SimplifyIVUsers helper for eliminating useless
257/// comparisons against an induction variable.
258void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp,
259 Instruction *IVOperand) {
260 unsigned IVOperIdx = 0;
261 CmpPredicate Pred = ICmp->getCmpPredicate();
262 ICmpInst::Predicate OriginalPred = Pred;
263 if (IVOperand != ICmp->getOperand(i_nocapture: 0)) {
264 // Swapped
265 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
266 IVOperIdx = 1;
267 Pred = ICmpInst::getSwappedCmpPredicate(Pred);
268 }
269
270 // Get the SCEVs for the ICmp operands (in the specific context of the
271 // current loop)
272 const Loop *ICmpLoop = LI->getLoopFor(BB: ICmp->getParent());
273 const SCEV *S = SE->getSCEVAtScope(V: ICmp->getOperand(i_nocapture: IVOperIdx), L: ICmpLoop);
274 const SCEV *X = SE->getSCEVAtScope(V: ICmp->getOperand(i_nocapture: 1 - IVOperIdx), L: ICmpLoop);
275
276 // If the condition is always true or always false in the given context,
277 // replace it with a constant value.
278 SmallVector<Instruction *, 4> Users;
279 for (auto *U : ICmp->users())
280 Users.push_back(Elt: cast<Instruction>(Val: U));
281 const Instruction *CtxI = findCommonDominator(Instructions: Users, DT&: *DT);
282 if (auto Ev = SE->evaluatePredicateAt(Pred, LHS: S, RHS: X, CtxI)) {
283 SE->forgetValue(V: ICmp);
284 ICmp->replaceAllUsesWith(V: ConstantInt::getBool(Context&: ICmp->getContext(), V: *Ev));
285 DeadInsts.emplace_back(Args&: ICmp);
286 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
287 ++NumElimCmp;
288 Changed = true;
289 return;
290 }
291
292 if (makeIVComparisonInvariant(ICmp, IVOperand)) {
293 ++NumInvariantCmp;
294 Changed = true;
295 return;
296 }
297
298 if ((ICmpInst::isSigned(Pred: OriginalPred) ||
299 (ICmpInst::isUnsigned(Pred: OriginalPred) && !ICmp->hasSameSign())) &&
300 SE->haveSameSign(S1: S, S2: X)) {
301 // Set the samesign flag on the compare if legal, and canonicalize to
302 // the unsigned variant (for signed compares) hoping that it will open
303 // the doors for other optimizations. Note that we cannot rely on Pred
304 // here unless we check if we have swapped it.
305 assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
306 LLVM_DEBUG(dbgs() << "INDVARS: Marking comparison samesign: " << *ICmp
307 << '\n');
308 ICmp->setPredicate(ICmpInst::getUnsignedPredicate(Pred: OriginalPred));
309 ICmp->setSameSign();
310 NumSameSign++;
311 Changed = true;
312 return;
313 }
314}
315
316bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
317 // Get the SCEVs for the ICmp operands.
318 const SCEV *N = SE->getSCEV(V: SDiv->getOperand(i_nocapture: 0));
319 const SCEV *D = SE->getSCEV(V: SDiv->getOperand(i_nocapture: 1));
320
321 // Simplify unnecessary loops away.
322 const Loop *L = LI->getLoopFor(BB: SDiv->getParent());
323 N = SE->getSCEVAtScope(S: N, L);
324 D = SE->getSCEVAtScope(S: D, L);
325
326 // Replace sdiv by udiv if both of the operands are non-negative
327 if (SE->isKnownNonNegative(S: N) && SE->isKnownNonNegative(S: D)) {
328 auto *UDiv = BinaryOperator::Create(
329 Op: BinaryOperator::UDiv, S1: SDiv->getOperand(i_nocapture: 0), S2: SDiv->getOperand(i_nocapture: 1),
330 Name: SDiv->getName() + ".udiv", InsertBefore: SDiv->getIterator());
331 UDiv->setIsExact(SDiv->isExact());
332 SDiv->replaceAllUsesWith(V: UDiv);
333 UDiv->setDebugLoc(SDiv->getDebugLoc());
334 LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
335 ++NumSimplifiedSDiv;
336 Changed = true;
337 DeadInsts.push_back(Elt: SDiv);
338 return true;
339 }
340
341 return false;
342}
343
344// i %s n -> i %u n if i >= 0 and n >= 0
345void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
346 auto *N = Rem->getOperand(i_nocapture: 0), *D = Rem->getOperand(i_nocapture: 1);
347 auto *URem = BinaryOperator::Create(Op: BinaryOperator::URem, S1: N, S2: D,
348 Name: Rem->getName() + ".urem", InsertBefore: Rem->getIterator());
349 Rem->replaceAllUsesWith(V: URem);
350 URem->setDebugLoc(Rem->getDebugLoc());
351 LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
352 ++NumSimplifiedSRem;
353 Changed = true;
354 DeadInsts.emplace_back(Args&: Rem);
355}
356
357// i % n --> i if i is in [0,n).
358void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
359 Rem->replaceAllUsesWith(V: Rem->getOperand(i_nocapture: 0));
360 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
361 ++NumElimRem;
362 Changed = true;
363 DeadInsts.emplace_back(Args&: Rem);
364}
365
366bool SimplifyIndvar::replaceRemWithNumeratorOrZeroUpdateProfiles(
367 SelectInst &SI) {
368 if (ProfcheckDisableMetadataFixes)
369 return false;
370 // The select instruction condition is guaranteed to evaluate to true exactly
371 // once through the duration of the loop if it is executed on every loop
372 // iteration. So we set the branch weights to be {1, LoopIterations - 1}.
373
374 // Check that the select instruction does execute every iteration.
375 BasicBlock *Latch = L->getLoopLatch();
376 if (L->getExitingBlock() != Latch || !DT->dominates(A: SI.getParent(), B: Latch))
377 return false;
378
379 // Early exits also invalidate the assumption that the select instruction is
380 // executed on every iteration, so bail here if we run into any.
381 if (L->getExitingBlock() == nullptr || L->getExitingBlock() != Latch)
382 return false;
383
384 // Construct the branch weights using the trip count.
385 unsigned TripCount = SE->getSmallConstantTripCount(L);
386 if (!TripCount)
387 TripCount = getLoopEstimatedTripCount(L).value_or(u: 0);
388 if (!TripCount)
389 return false;
390 setBranchWeights(I&: SI, Weights: {1, TripCount - 1}, /*IsExpected=*/false);
391 return true;
392}
393
394// (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
395void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
396 auto *T = Rem->getType();
397 auto *N = Rem->getOperand(i_nocapture: 0), *D = Rem->getOperand(i_nocapture: 1);
398 ICmpInst *ICmp = new ICmpInst(Rem->getIterator(), ICmpInst::ICMP_EQ, N, D);
399 ICmp->setDebugLoc(Rem->getDebugLoc());
400 SelectInst *Sel =
401 SelectInst::Create(C: ICmp, S1: ConstantInt::get(Ty: T, V: 0), S2: N, NameStr: "iv.rem", InsertBefore: Rem->getIterator());
402 Rem->replaceAllUsesWith(V: Sel);
403 Sel->setDebugLoc(Rem->getDebugLoc());
404 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
405 ++NumElimRem;
406 Changed = true;
407 DeadInsts.emplace_back(Args&: Rem);
408 if (!replaceRemWithNumeratorOrZeroUpdateProfiles(SI&: *Sel))
409 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *Sel, DEBUG_TYPE);
410}
411
412/// SimplifyIVUsers helper for eliminating useless remainder operations
413/// operating on an induction variable or replacing srem by urem.
414void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,
415 Instruction *IVOperand,
416 bool IsSigned) {
417 auto *NValue = Rem->getOperand(i_nocapture: 0);
418 auto *DValue = Rem->getOperand(i_nocapture: 1);
419 // We're only interested in the case where we know something about
420 // the numerator, unless it is a srem, because we want to replace srem by urem
421 // in general.
422 bool UsedAsNumerator = IVOperand == NValue;
423 if (!UsedAsNumerator && !IsSigned)
424 return;
425
426 const SCEV *N = SE->getSCEV(V: NValue);
427
428 // Simplify unnecessary loops away.
429 const Loop *ICmpLoop = LI->getLoopFor(BB: Rem->getParent());
430 N = SE->getSCEVAtScope(S: N, L: ICmpLoop);
431
432 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(S: N);
433
434 // Do not proceed if the Numerator may be negative
435 if (!IsNumeratorNonNegative)
436 return;
437
438 const SCEV *D = SE->getSCEV(V: DValue);
439 D = SE->getSCEVAtScope(S: D, L: ICmpLoop);
440
441 if (UsedAsNumerator) {
442 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
443 if (SE->isKnownPredicate(Pred: LT, LHS: N, RHS: D)) {
444 replaceRemWithNumerator(Rem);
445 return;
446 }
447
448 auto *T = Rem->getType();
449 const SCEV *NLessOne = SE->getMinusSCEV(LHS: N, RHS: SE->getOne(Ty: T));
450 if (SE->isKnownPredicate(Pred: LT, LHS: NLessOne, RHS: D)) {
451 replaceRemWithNumeratorOrZero(Rem);
452 return;
453 }
454 }
455
456 // Try to replace SRem with URem, if both N and D are known non-negative.
457 // Since we had already check N, we only need to check D now
458 if (!IsSigned || !SE->isKnownNonNegative(S: D))
459 return;
460
461 replaceSRemWithURem(Rem);
462}
463
464bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
465 const SCEV *LHS = SE->getSCEV(V: WO->getLHS());
466 const SCEV *RHS = SE->getSCEV(V: WO->getRHS());
467 if (!SE->willNotOverflow(BinOp: WO->getBinaryOp(), Signed: WO->isSigned(), LHS, RHS))
468 return false;
469
470 // Proved no overflow, nuke the overflow check and, if possible, the overflow
471 // intrinsic as well.
472
473 BinaryOperator *NewResult = BinaryOperator::Create(
474 Op: WO->getBinaryOp(), S1: WO->getLHS(), S2: WO->getRHS(), Name: "", InsertBefore: WO->getIterator());
475
476 if (WO->isSigned())
477 NewResult->setHasNoSignedWrap(true);
478 else
479 NewResult->setHasNoUnsignedWrap(true);
480
481 SmallVector<ExtractValueInst *, 4> ToDelete;
482
483 for (auto *U : WO->users()) {
484 if (auto *EVI = dyn_cast<ExtractValueInst>(Val: U)) {
485 if (EVI->getIndices()[0] == 1)
486 EVI->replaceAllUsesWith(V: ConstantInt::getFalse(Context&: WO->getContext()));
487 else {
488 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
489 EVI->replaceAllUsesWith(V: NewResult);
490 NewResult->setDebugLoc(EVI->getDebugLoc());
491 }
492 ToDelete.push_back(Elt: EVI);
493 }
494 }
495
496 for (auto *EVI : ToDelete)
497 EVI->eraseFromParent();
498
499 if (WO->use_empty())
500 WO->eraseFromParent();
501
502 Changed = true;
503 return true;
504}
505
506bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
507 const SCEV *LHS = SE->getSCEV(V: SI->getLHS());
508 const SCEV *RHS = SE->getSCEV(V: SI->getRHS());
509 if (!SE->willNotOverflow(BinOp: SI->getBinaryOp(), Signed: SI->isSigned(), LHS, RHS))
510 return false;
511
512 BinaryOperator *BO = BinaryOperator::Create(
513 Op: SI->getBinaryOp(), S1: SI->getLHS(), S2: SI->getRHS(), Name: SI->getName(), InsertBefore: SI->getIterator());
514 if (SI->isSigned())
515 BO->setHasNoSignedWrap();
516 else
517 BO->setHasNoUnsignedWrap();
518
519 SI->replaceAllUsesWith(V: BO);
520 BO->setDebugLoc(SI->getDebugLoc());
521 DeadInsts.emplace_back(Args&: SI);
522 Changed = true;
523 return true;
524}
525
526bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
527 // It is always legal to replace
528 // icmp <pred> i32 trunc(iv), n
529 // with
530 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
531 // Or with
532 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
533 // Or with either of these if pred is an equality predicate.
534 //
535 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
536 // every comparison which uses trunc, it means that we can replace each of
537 // them with comparison of iv against sext/zext(n). We no longer need trunc
538 // after that.
539 //
540 // TODO: Should we do this if we can widen *some* comparisons, but not all
541 // of them? Sometimes it is enough to enable other optimizations, but the
542 // trunc instruction will stay in the loop.
543 Value *IV = TI->getOperand(i_nocapture: 0);
544 Type *IVTy = IV->getType();
545 const SCEV *IVSCEV = SE->getSCEV(V: IV);
546 const SCEV *TISCEV = SE->getSCEV(V: TI);
547
548 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
549 // get rid of trunc
550 bool DoesSExtCollapse = false;
551 bool DoesZExtCollapse = false;
552 if (IVSCEV == SE->getSignExtendExpr(Op: TISCEV, Ty: IVTy))
553 DoesSExtCollapse = true;
554 if (IVSCEV == SE->getZeroExtendExpr(Op: TISCEV, Ty: IVTy))
555 DoesZExtCollapse = true;
556
557 // If neither sext nor zext does collapse, it is not profitable to do any
558 // transform. Bail.
559 if (!DoesSExtCollapse && !DoesZExtCollapse)
560 return false;
561
562 // Collect users of the trunc that look like comparisons against invariants.
563 // Bail if we find something different.
564 SmallVector<ICmpInst *, 4> ICmpUsers;
565 for (auto *U : TI->users()) {
566 // We don't care about users in unreachable blocks.
567 if (isa<Instruction>(Val: U) &&
568 !DT->isReachableFromEntry(A: cast<Instruction>(Val: U)->getParent()))
569 continue;
570 ICmpInst *ICI = dyn_cast<ICmpInst>(Val: U);
571 if (!ICI) return false;
572 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
573 if (!(ICI->getOperand(i_nocapture: 0) == TI && L->isLoopInvariant(V: ICI->getOperand(i_nocapture: 1))) &&
574 !(ICI->getOperand(i_nocapture: 1) == TI && L->isLoopInvariant(V: ICI->getOperand(i_nocapture: 0))))
575 return false;
576 // If we cannot get rid of trunc, bail.
577 if (ICI->isSigned() && !DoesSExtCollapse)
578 return false;
579 if (ICI->isUnsigned() && !DoesZExtCollapse)
580 return false;
581 // For equality, either signed or unsigned works.
582 ICmpUsers.push_back(Elt: ICI);
583 }
584
585 auto CanUseZExt = [&](ICmpInst *ICI) {
586 // Unsigned comparison can be widened as unsigned.
587 if (ICI->isUnsigned())
588 return true;
589 // Is it profitable to do zext?
590 if (!DoesZExtCollapse)
591 return false;
592 // For equality, we can safely zext both parts.
593 if (ICI->isEquality())
594 return true;
595 // Otherwise we can only use zext when comparing two non-negative or two
596 // negative values. But in practice, we will never pass DoesZExtCollapse
597 // check for a negative value, because zext(trunc(x)) is non-negative. So
598 // it only make sense to check for non-negativity here.
599 const SCEV *SCEVOP1 = SE->getSCEV(V: ICI->getOperand(i_nocapture: 0));
600 const SCEV *SCEVOP2 = SE->getSCEV(V: ICI->getOperand(i_nocapture: 1));
601 return SE->isKnownNonNegative(S: SCEVOP1) && SE->isKnownNonNegative(S: SCEVOP2);
602 };
603 // Replace all comparisons against trunc with comparisons against IV.
604 for (auto *ICI : ICmpUsers) {
605 bool IsSwapped = L->isLoopInvariant(V: ICI->getOperand(i_nocapture: 0));
606 auto *Op1 = IsSwapped ? ICI->getOperand(i_nocapture: 0) : ICI->getOperand(i_nocapture: 1);
607 IRBuilder<> Builder(ICI);
608 Value *Ext = nullptr;
609 // For signed/unsigned predicate, replace the old comparison with comparison
610 // of immediate IV against sext/zext of the invariant argument. If we can
611 // use either sext or zext (i.e. we are dealing with equality predicate),
612 // then prefer zext as a more canonical form.
613 // TODO: If we see a signed comparison which can be turned into unsigned,
614 // we can do it here for canonicalization purposes.
615 ICmpInst::Predicate Pred = ICI->getPredicate();
616 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(pred: Pred);
617 if (CanUseZExt(ICI)) {
618 assert(DoesZExtCollapse && "Unprofitable zext?");
619 Ext = Builder.CreateZExt(V: Op1, DestTy: IVTy, Name: "zext");
620 Pred = ICmpInst::getUnsignedPredicate(Pred);
621 } else {
622 assert(DoesSExtCollapse && "Unprofitable sext?");
623 Ext = Builder.CreateSExt(V: Op1, DestTy: IVTy, Name: "sext");
624 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
625 }
626 bool Changed;
627 L->makeLoopInvariant(V: Ext, Changed);
628 (void)Changed;
629 auto *NewCmp = Builder.CreateICmp(P: Pred, LHS: IV, RHS: Ext);
630 ICI->replaceAllUsesWith(V: NewCmp);
631 DeadInsts.emplace_back(Args&: ICI);
632 }
633
634 // Trunc no longer needed.
635 TI->replaceAllUsesWith(V: PoisonValue::get(T: TI->getType()));
636 DeadInsts.emplace_back(Args&: TI);
637 return true;
638}
639
640/// Eliminate an operation that consumes a simple IV and has no observable
641/// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
642/// but UseInst may not be.
643bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
644 Instruction *IVOperand) {
645 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: UseInst)) {
646 eliminateIVComparison(ICmp, IVOperand);
647 return true;
648 }
649 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(Val: UseInst)) {
650 bool IsSRem = Bin->getOpcode() == Instruction::SRem;
651 if (IsSRem || Bin->getOpcode() == Instruction::URem) {
652 simplifyIVRemainder(Rem: Bin, IVOperand, IsSigned: IsSRem);
653 return true;
654 }
655
656 if (Bin->getOpcode() == Instruction::SDiv)
657 return eliminateSDiv(SDiv: Bin);
658 }
659
660 if (auto *WO = dyn_cast<WithOverflowInst>(Val: UseInst))
661 if (eliminateOverflowIntrinsic(WO))
662 return true;
663
664 if (auto *SI = dyn_cast<SaturatingInst>(Val: UseInst))
665 if (eliminateSaturatingIntrinsic(SI))
666 return true;
667
668 if (auto *TI = dyn_cast<TruncInst>(Val: UseInst))
669 if (eliminateTrunc(TI))
670 return true;
671
672 if (eliminateIdentitySCEV(UseInst, IVOperand))
673 return true;
674
675 return false;
676}
677
678static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
679 if (auto *BB = L->getLoopPreheader())
680 return BB->getTerminator();
681
682 return Hint;
683}
684
685/// Replace the UseInst with a loop invariant expression if it is safe.
686bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
687 if (!SE->isSCEVable(Ty: I->getType()))
688 return false;
689
690 // Get the symbolic expression for this instruction.
691 const SCEV *S = SE->getSCEV(V: I);
692
693 if (!SE->isLoopInvariant(S, L))
694 return false;
695
696 // Do not generate something ridiculous even if S is loop invariant.
697 if (Rewriter.isHighCostExpansion(Exprs: S, L, Budget: SCEVCheapExpansionBudget, TTI, At: I))
698 return false;
699
700 auto *IP = GetLoopInvariantInsertPosition(L, Hint: I);
701
702 if (!Rewriter.isSafeToExpandAt(S, InsertionPoint: IP)) {
703 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
704 << " with non-speculable loop invariant: " << *S << '\n');
705 return false;
706 }
707
708 auto *Invariant = Rewriter.expandCodeFor(SH: S, Ty: I->getType(), I: IP);
709 bool NeedToEmitLCSSAPhis = false;
710 if (!LI->replacementPreservesLCSSAForm(From: I, To: Invariant))
711 NeedToEmitLCSSAPhis = true;
712
713 I->replaceAllUsesWith(V: Invariant);
714 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
715 << " with loop invariant: " << *S << '\n');
716
717 if (NeedToEmitLCSSAPhis) {
718 SmallVector<Instruction *, 1> NeedsLCSSAPhis;
719 NeedsLCSSAPhis.push_back(Elt: cast<Instruction>(Val: Invariant));
720 formLCSSAForInstructions(Worklist&: NeedsLCSSAPhis, DT: *DT, LI: *LI, SE);
721 LLVM_DEBUG(dbgs() << " INDVARS: Replacement breaks LCSSA form"
722 << " inserting LCSSA Phis" << '\n');
723 }
724 ++NumFoldedUser;
725 Changed = true;
726 DeadInsts.emplace_back(Args&: I);
727 return true;
728}
729
730/// Eliminate redundant type cast between integer and float.
731bool SimplifyIndvar::replaceFloatIVWithIntegerIV(Instruction *UseInst) {
732 if (UseInst->getOpcode() != CastInst::SIToFP &&
733 UseInst->getOpcode() != CastInst::UIToFP)
734 return false;
735
736 Instruction *IVOperand = cast<Instruction>(Val: UseInst->getOperand(i: 0));
737 // Get the symbolic expression for this instruction.
738 const SCEV *IV = SE->getSCEV(V: IVOperand);
739 int MaskBits;
740 if (UseInst->getOpcode() == CastInst::SIToFP)
741 MaskBits = (int)SE->getSignedRange(S: IV).getMinSignedBits();
742 else
743 MaskBits = (int)SE->getUnsignedRange(S: IV).getActiveBits();
744 int DestNumSigBits = UseInst->getType()->getFPMantissaWidth();
745 if (MaskBits <= DestNumSigBits) {
746 for (User *U : UseInst->users()) {
747 // Match for fptosi/fptoui of sitofp and with same type.
748 auto *CI = dyn_cast<CastInst>(Val: U);
749 if (!CI)
750 continue;
751
752 CastInst::CastOps Opcode = CI->getOpcode();
753 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
754 continue;
755
756 Value *Conv = nullptr;
757 if (IVOperand->getType() != CI->getType()) {
758 IRBuilder<> Builder(CI);
759 StringRef Name = IVOperand->getName();
760 // To match InstCombine logic, we only need sext if both fptosi and
761 // sitofp are used. If one of them is unsigned, then we can use zext.
762 if (SE->getTypeSizeInBits(Ty: IVOperand->getType()) >
763 SE->getTypeSizeInBits(Ty: CI->getType())) {
764 Conv = Builder.CreateTrunc(V: IVOperand, DestTy: CI->getType(), Name: Name + ".trunc");
765 } else if (Opcode == CastInst::FPToUI ||
766 UseInst->getOpcode() == CastInst::UIToFP) {
767 Conv = Builder.CreateZExt(V: IVOperand, DestTy: CI->getType(), Name: Name + ".zext");
768 } else {
769 Conv = Builder.CreateSExt(V: IVOperand, DestTy: CI->getType(), Name: Name + ".sext");
770 }
771 } else
772 Conv = IVOperand;
773
774 CI->replaceAllUsesWith(V: Conv);
775 DeadInsts.push_back(Elt: CI);
776 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *CI
777 << " with: " << *Conv << '\n');
778
779 ++NumFoldedUser;
780 Changed = true;
781 }
782 }
783
784 return Changed;
785}
786
787/// Eliminate any operation that SCEV can prove is an identity function.
788bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
789 Instruction *IVOperand) {
790 if (!SE->isSCEVable(Ty: UseInst->getType()) ||
791 UseInst->getType() != IVOperand->getType())
792 return false;
793
794 const SCEV *UseSCEV = SE->getSCEV(V: UseInst);
795 if (UseSCEV != SE->getSCEV(V: IVOperand))
796 return false;
797
798 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
799 // dominator tree, even if X is an operand to Y. For instance, in
800 //
801 // %iv = phi i32 {0,+,1}
802 // br %cond, label %left, label %merge
803 //
804 // left:
805 // %X = add i32 %iv, 0
806 // br label %merge
807 //
808 // merge:
809 // %M = phi (%X, %iv)
810 //
811 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
812 // %M.replaceAllUsesWith(%X) would be incorrect.
813
814 if (isa<PHINode>(Val: UseInst))
815 // If UseInst is not a PHI node then we know that IVOperand dominates
816 // UseInst directly from the legality of SSA.
817 if (!DT || !DT->dominates(Def: IVOperand, User: UseInst))
818 return false;
819
820 if (!LI->replacementPreservesLCSSAForm(From: UseInst, To: IVOperand))
821 return false;
822
823 // Make sure the operand is not more poisonous than the instruction.
824 if (!impliesPoison(ValAssumedPoison: IVOperand, V: UseInst)) {
825 SmallVector<Instruction *> DropPoisonGeneratingInsts;
826 if (!SE->canReuseInstruction(S: UseSCEV, I: IVOperand, DropPoisonGeneratingInsts))
827 return false;
828
829 for (Instruction *I : DropPoisonGeneratingInsts)
830 I->dropPoisonGeneratingAnnotations();
831 }
832
833 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
834
835 SE->forgetValue(V: UseInst);
836 UseInst->replaceAllUsesWith(V: IVOperand);
837 ++NumElimIdentity;
838 Changed = true;
839 DeadInsts.emplace_back(Args&: UseInst);
840 return true;
841}
842
843bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,
844 Instruction *IVOperand) {
845 return (isa<OverflowingBinaryOperator>(Val: BO) &&
846 strengthenOverflowingOperation(OBO: BO, IVOperand)) ||
847 (isa<ShlOperator>(Val: BO) && strengthenRightShift(BO, IVOperand));
848}
849
850/// Annotate BO with nsw / nuw if it provably does not signed-overflow /
851/// unsigned-overflow. Returns true if anything changed, false otherwise.
852bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
853 Instruction *IVOperand) {
854 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
855 OBO: cast<OverflowingBinaryOperator>(Val: BO));
856
857 if (!Flags)
858 return false;
859
860 BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(Flags: *Flags, Mask: SCEV::FlagNUW) ==
861 SCEV::FlagNUW);
862 BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(Flags: *Flags, Mask: SCEV::FlagNSW) ==
863 SCEV::FlagNSW);
864
865 // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap
866 // flags on addrecs while performing zero/sign extensions. We could call
867 // forgetValue() here to make sure those flags also propagate to any other
868 // SCEV expressions based on the addrec. However, this can have pathological
869 // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.
870 return true;
871}
872
873/// Annotate the Shr in (X << IVOperand) >> C as exact using the
874/// information from the IV's range. Returns true if anything changed, false
875/// otherwise.
876bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
877 Instruction *IVOperand) {
878 if (BO->getOpcode() == Instruction::Shl) {
879 bool Changed = false;
880 ConstantRange IVRange = SE->getUnsignedRange(S: SE->getSCEV(V: IVOperand));
881 for (auto *U : BO->users()) {
882 const APInt *C;
883 if (match(V: U,
884 P: m_AShr(L: m_Shl(L: m_Value(), R: m_Specific(V: IVOperand)), R: m_APInt(Res&: C))) ||
885 match(V: U,
886 P: m_LShr(L: m_Shl(L: m_Value(), R: m_Specific(V: IVOperand)), R: m_APInt(Res&: C)))) {
887 BinaryOperator *Shr = cast<BinaryOperator>(Val: U);
888 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(RHS: *C)) {
889 Shr->setIsExact(true);
890 Changed = true;
891 }
892 }
893 }
894 return Changed;
895 }
896
897 return false;
898}
899
900/// Add all uses of Def to the current IV's worklist.
901void SimplifyIndvar::pushIVUsers(
902 Instruction *Def, SmallPtrSet<Instruction *, 16> &Simplified,
903 SmallVectorImpl<std::pair<Instruction *, Instruction *>> &SimpleIVUsers) {
904 for (User *U : Def->users()) {
905 Instruction *UI = cast<Instruction>(Val: U);
906
907 // Avoid infinite or exponential worklist processing.
908 // Also ensure unique worklist users.
909 // If Def is a LoopPhi, it may not be in the Simplified set, so check for
910 // self edges first.
911 if (UI == Def)
912 continue;
913
914 // Only change the current Loop, do not change the other parts (e.g. other
915 // Loops).
916 if (!L->contains(Inst: UI))
917 continue;
918
919 // Do not push the same instruction more than once.
920 if (!Simplified.insert(Ptr: UI).second)
921 continue;
922
923 SimpleIVUsers.push_back(Elt: std::make_pair(x&: UI, y&: Def));
924 }
925}
926
927/// Return true if this instruction generates a simple SCEV
928/// expression in terms of that IV.
929///
930/// This is similar to IVUsers' isInteresting() but processes each instruction
931/// non-recursively when the operand is already known to be a simpleIVUser.
932///
933static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
934 if (!SE->isSCEVable(Ty: I->getType()))
935 return false;
936
937 // Get the symbolic expression for this instruction.
938 const SCEV *S = SE->getSCEV(V: I);
939
940 // Only consider affine recurrences.
941 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: S);
942 if (AR && AR->getLoop() == L)
943 return true;
944
945 return false;
946}
947
948/// Iteratively perform simplification on a worklist of users
949/// of the specified induction variable. Each successive simplification may push
950/// more users which may themselves be candidates for simplification.
951///
952/// This algorithm does not require IVUsers analysis. Instead, it simplifies
953/// instructions in-place during analysis. Rather than rewriting induction
954/// variables bottom-up from their users, it transforms a chain of IVUsers
955/// top-down, updating the IR only when it encounters a clear optimization
956/// opportunity.
957///
958/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
959///
960void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
961 if (!SE->isSCEVable(Ty: CurrIV->getType()))
962 return;
963
964 // Instructions processed by SimplifyIndvar for CurrIV.
965 SmallPtrSet<Instruction*,16> Simplified;
966
967 // Use-def pairs if IV users waiting to be processed for CurrIV.
968 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
969
970 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
971 // called multiple times for the same LoopPhi. This is the proper thing to
972 // do for loop header phis that use each other.
973 pushIVUsers(Def: CurrIV, Simplified, SimpleIVUsers);
974
975 while (!SimpleIVUsers.empty()) {
976 std::pair<Instruction*, Instruction*> UseOper =
977 SimpleIVUsers.pop_back_val();
978 Instruction *UseInst = UseOper.first;
979
980 // If a user of the IndVar is trivially dead, we prefer just to mark it dead
981 // rather than try to do some complex analysis or transformation (such as
982 // widening) basing on it.
983 // TODO: Propagate TLI and pass it here to handle more cases.
984 if (isInstructionTriviallyDead(I: UseInst, /* TLI */ nullptr)) {
985 DeadInsts.emplace_back(Args&: UseInst);
986 continue;
987 }
988
989 // Bypass back edges to avoid extra work.
990 if (UseInst == CurrIV) continue;
991
992 // Try to replace UseInst with a loop invariant before any other
993 // simplifications.
994 if (replaceIVUserWithLoopInvariant(I: UseInst))
995 continue;
996
997 // Go further for the bitcast 'prtoint ptr to i64' or if the cast is done
998 // by truncation
999 if (isa<PtrToIntInst, PtrToAddrInst, TruncInst>(Val: UseInst))
1000 for (Use &U : UseInst->uses()) {
1001 Instruction *User = cast<Instruction>(Val: U.getUser());
1002 if (replaceIVUserWithLoopInvariant(I: User))
1003 break; // done replacing
1004 }
1005
1006 Instruction *IVOperand = UseOper.second;
1007 for (unsigned N = 0; IVOperand; ++N) {
1008 assert(N <= Simplified.size() && "runaway iteration");
1009 (void) N;
1010
1011 Value *NewOper = foldIVUser(UseInst, IVOperand);
1012 if (!NewOper)
1013 break; // done folding
1014 IVOperand = dyn_cast<Instruction>(Val: NewOper);
1015 }
1016 if (!IVOperand)
1017 continue;
1018
1019 if (eliminateIVUser(UseInst, IVOperand)) {
1020 pushIVUsers(Def: IVOperand, Simplified, SimpleIVUsers);
1021 continue;
1022 }
1023
1024 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: UseInst)) {
1025 if (strengthenBinaryOp(BO, IVOperand)) {
1026 // re-queue uses of the now modified binary operator and fall
1027 // through to the checks that remain.
1028 pushIVUsers(Def: IVOperand, Simplified, SimpleIVUsers);
1029 }
1030 }
1031
1032 // Try to use integer induction for FPToSI of float induction directly.
1033 if (replaceFloatIVWithIntegerIV(UseInst)) {
1034 // Re-queue the potentially new direct uses of IVOperand.
1035 pushIVUsers(Def: IVOperand, Simplified, SimpleIVUsers);
1036 continue;
1037 }
1038
1039 CastInst *Cast = dyn_cast<CastInst>(Val: UseInst);
1040 if (V && Cast) {
1041 V->visitCast(Cast);
1042 continue;
1043 }
1044 if (isSimpleIVUser(I: UseInst, L, SE)) {
1045 pushIVUsers(Def: UseInst, Simplified, SimpleIVUsers);
1046 }
1047 }
1048}
1049
1050namespace llvm {
1051
1052void IVVisitor::anchor() { }
1053
1054/// Simplify instructions that use this induction variable
1055/// by using ScalarEvolution to analyze the IV's recurrence.
1056/// Returns a pair where the first entry indicates that the function makes
1057/// changes and the second entry indicates that it introduced new opportunities
1058/// for loop unswitching.
1059std::pair<bool, bool> simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE,
1060 DominatorTree *DT, LoopInfo *LI,
1061 const TargetTransformInfo *TTI,
1062 SmallVectorImpl<WeakTrackingVH> &Dead,
1063 SCEVExpander &Rewriter, IVVisitor *V) {
1064 SimplifyIndvar SIV(LI->getLoopFor(BB: CurrIV->getParent()), SE, DT, LI, TTI,
1065 Rewriter, Dead);
1066 SIV.simplifyUsers(CurrIV, V);
1067 return {SIV.hasChanged(), SIV.runUnswitching()};
1068}
1069
1070/// Simplify users of induction variables within this
1071/// loop. This does not actually change or add IVs.
1072bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
1073 LoopInfo *LI, const TargetTransformInfo *TTI,
1074 SmallVectorImpl<WeakTrackingVH> &Dead) {
1075 SCEVExpander Rewriter(*SE, "indvars");
1076#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1077 Rewriter.setDebugType(DEBUG_TYPE);
1078#endif
1079 bool Changed = false;
1080 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(Val: I); ++I) {
1081 const auto &[C, _] =
1082 simplifyUsersOfIV(CurrIV: cast<PHINode>(Val&: I), SE, DT, LI, TTI, Dead, Rewriter);
1083 Changed |= C;
1084 }
1085 return Changed;
1086}
1087
1088} // namespace llvm
1089
1090namespace {
1091//===----------------------------------------------------------------------===//
1092// Widen Induction Variables - Extend the width of an IV to cover its
1093// widest uses.
1094//===----------------------------------------------------------------------===//
1095
1096class WidenIV {
1097 // Parameters
1098 PHINode *OrigPhi;
1099 Type *WideType;
1100
1101 // Context
1102 LoopInfo *LI;
1103 Loop *L;
1104 ScalarEvolution *SE;
1105 DominatorTree *DT;
1106
1107 // Does the module have any calls to the llvm.experimental.guard intrinsic
1108 // at all? If not we can avoid scanning instructions looking for guards.
1109 bool HasGuards;
1110
1111 bool UsePostIncrementRanges;
1112
1113 // Statistics
1114 unsigned NumElimExt = 0;
1115 unsigned NumWidened = 0;
1116
1117 // Result
1118 PHINode *WidePhi = nullptr;
1119 Instruction *WideInc = nullptr;
1120 const SCEV *WideIncExpr = nullptr;
1121 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
1122
1123 SmallPtrSet<Instruction *,16> Widened;
1124
1125 enum class ExtendKind { Zero, Sign, Unknown };
1126
1127 // A map tracking the kind of extension used to widen each narrow IV
1128 // and narrow IV user.
1129 // Key: pointer to a narrow IV or IV user.
1130 // Value: the kind of extension used to widen this Instruction.
1131 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
1132
1133 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
1134
1135 // A map with control-dependent ranges for post increment IV uses. The key is
1136 // a pair of IV def and a use of this def denoting the context. The value is
1137 // a ConstantRange representing possible values of the def at the given
1138 // context.
1139 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
1140
1141 std::optional<ConstantRange> getPostIncRangeInfo(Value *Def,
1142 Instruction *UseI) {
1143 DefUserPair Key(Def, UseI);
1144 auto It = PostIncRangeInfos.find(Val: Key);
1145 return It == PostIncRangeInfos.end()
1146 ? std::optional<ConstantRange>(std::nullopt)
1147 : std::optional<ConstantRange>(It->second);
1148 }
1149
1150 void calculatePostIncRanges(PHINode *OrigPhi);
1151 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
1152
1153 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
1154 DefUserPair Key(Def, UseI);
1155 auto [It, Inserted] = PostIncRangeInfos.try_emplace(Key, Args&: R);
1156 if (!Inserted)
1157 It->second = R.intersectWith(CR: It->second);
1158 }
1159
1160public:
1161 /// Record a link in the Narrow IV def-use chain along with the WideIV that
1162 /// computes the same value as the Narrow IV def. This avoids caching Use*
1163 /// pointers.
1164 struct NarrowIVDefUse {
1165 Instruction *NarrowDef = nullptr;
1166 Instruction *NarrowUse = nullptr;
1167 Instruction *WideDef = nullptr;
1168
1169 // True if the narrow def is never negative. Tracking this information lets
1170 // us use a sign extension instead of a zero extension or vice versa, when
1171 // profitable and legal.
1172 bool NeverNegative = false;
1173
1174 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
1175 bool NeverNegative)
1176 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1177 NeverNegative(NeverNegative) {}
1178 };
1179
1180 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1181 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
1182 bool HasGuards, bool UsePostIncrementRanges = true);
1183
1184 PHINode *createWideIV(SCEVExpander &Rewriter);
1185
1186 unsigned getNumElimExt() { return NumElimExt; };
1187 unsigned getNumWidened() { return NumWidened; };
1188
1189protected:
1190 Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
1191 Instruction *Use);
1192
1193 Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
1194 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1195 const SCEVAddRecExpr *WideAR);
1196 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1197
1198 ExtendKind getExtendKind(Instruction *I);
1199
1200 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1201
1202 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1203
1204 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1205
1206 const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1207 unsigned OpCode) const;
1208
1209 Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter,
1210 PHINode *OrigPhi, PHINode *WidePhi);
1211 void truncateIVUse(NarrowIVDefUse DU);
1212
1213 bool widenLoopCompare(NarrowIVDefUse DU);
1214 bool widenWithVariantUse(NarrowIVDefUse DU);
1215
1216 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1217
1218private:
1219 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
1220};
1221} // namespace
1222
1223/// Determine the insertion point for this user. By default, insert immediately
1224/// before the user. SCEVExpander or LICM will hoist loop invariants out of the
1225/// loop. For PHI nodes, there may be multiple uses, so compute the nearest
1226/// common dominator for the incoming blocks. A nullptr can be returned if no
1227/// viable location is found: it may happen if User is a PHI and Def only comes
1228/// to this PHI from unreachable blocks.
1229static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
1230 DominatorTree *DT, LoopInfo *LI) {
1231 PHINode *PHI = dyn_cast<PHINode>(Val: User);
1232 if (!PHI)
1233 return User;
1234
1235 Instruction *InsertPt = nullptr;
1236 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
1237 if (PHI->getIncomingValue(i) != Def)
1238 continue;
1239
1240 BasicBlock *InsertBB = PHI->getIncomingBlock(i);
1241
1242 if (!DT->isReachableFromEntry(A: InsertBB))
1243 continue;
1244
1245 if (!InsertPt) {
1246 InsertPt = InsertBB->getTerminator();
1247 continue;
1248 }
1249 InsertBB = DT->findNearestCommonDominator(A: InsertPt->getParent(), B: InsertBB);
1250 InsertPt = InsertBB->getTerminator();
1251 }
1252
1253 // If we have skipped all inputs, it means that Def only comes to Phi from
1254 // unreachable blocks.
1255 if (!InsertPt)
1256 return nullptr;
1257
1258 auto *DefI = dyn_cast<Instruction>(Val: Def);
1259 if (!DefI)
1260 return InsertPt;
1261
1262 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
1263
1264 auto *L = LI->getLoopFor(BB: DefI->getParent());
1265 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
1266
1267 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
1268 if (LI->getLoopFor(BB: DTN->getBlock()) == L)
1269 return DTN->getBlock()->getTerminator();
1270
1271 llvm_unreachable("DefI dominates InsertPt!");
1272}
1273
1274WidenIV::WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1275 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
1276 bool HasGuards, bool UsePostIncrementRanges)
1277 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1278 L(LI->getLoopFor(BB: OrigPhi->getParent())), SE(SEv), DT(DTree),
1279 HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),
1280 DeadInsts(DI) {
1281 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
1282 ExtendKindMap[OrigPhi] = WI.IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1283}
1284
1285Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1286 bool IsSigned, Instruction *Use) {
1287 // Set the debug location and conservative insertion point.
1288 IRBuilder<> Builder(Use);
1289 // Hoist the insertion point into loop preheaders as far as possible.
1290 for (const Loop *L = LI->getLoopFor(BB: Use->getParent());
1291 L && L->getLoopPreheader() && L->isLoopInvariant(V: NarrowOper);
1292 L = L->getParentLoop())
1293 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
1294
1295 return IsSigned ? Builder.CreateSExt(V: NarrowOper, DestTy: WideType) :
1296 Builder.CreateZExt(V: NarrowOper, DestTy: WideType);
1297}
1298
1299/// Instantiate a wide operation to replace a narrow operation. This only needs
1300/// to handle operations that can evaluation to SCEVAddRec. It can safely return
1301/// 0 for any operation we decide not to clone.
1302Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1303 const SCEVAddRecExpr *WideAR) {
1304 unsigned Opcode = DU.NarrowUse->getOpcode();
1305 switch (Opcode) {
1306 default:
1307 return nullptr;
1308 case Instruction::Add:
1309 case Instruction::Mul:
1310 case Instruction::UDiv:
1311 case Instruction::Sub:
1312 return cloneArithmeticIVUser(DU, WideAR);
1313
1314 case Instruction::And:
1315 case Instruction::Or:
1316 case Instruction::Xor:
1317 case Instruction::Shl:
1318 case Instruction::LShr:
1319 case Instruction::AShr:
1320 return cloneBitwiseIVUser(DU);
1321 }
1322}
1323
1324Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1325 Instruction *NarrowUse = DU.NarrowUse;
1326 Instruction *NarrowDef = DU.NarrowDef;
1327 Instruction *WideDef = DU.WideDef;
1328
1329 LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1330
1331 // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1332 // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1333 // invariant and will be folded or hoisted. If it actually comes from a
1334 // widened IV, it should be removed during a future call to widenIVUse.
1335 bool IsSigned = getExtendKind(I: NarrowDef) == ExtendKind::Sign;
1336 Value *LHS = (NarrowUse->getOperand(i: 0) == NarrowDef)
1337 ? WideDef
1338 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 0), WideType,
1339 IsSigned, Use: NarrowUse);
1340 Value *RHS = (NarrowUse->getOperand(i: 1) == NarrowDef)
1341 ? WideDef
1342 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 1), WideType,
1343 IsSigned, Use: NarrowUse);
1344
1345 auto *NarrowBO = cast<BinaryOperator>(Val: NarrowUse);
1346 auto *WideBO = BinaryOperator::Create(Op: NarrowBO->getOpcode(), S1: LHS, S2: RHS,
1347 Name: NarrowBO->getName());
1348 IRBuilder<> Builder(NarrowUse);
1349 Builder.Insert(I: WideBO);
1350 WideBO->copyIRFlags(V: NarrowBO);
1351 return WideBO;
1352}
1353
1354Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1355 const SCEVAddRecExpr *WideAR) {
1356 Instruction *NarrowUse = DU.NarrowUse;
1357 Instruction *NarrowDef = DU.NarrowDef;
1358 Instruction *WideDef = DU.WideDef;
1359
1360 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1361
1362 unsigned IVOpIdx = (NarrowUse->getOperand(i: 0) == NarrowDef) ? 0 : 1;
1363
1364 // We're trying to find X such that
1365 //
1366 // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1367 //
1368 // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1369 // and check using SCEV if any of them are correct.
1370
1371 // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1372 // correct solution to X.
1373 auto GuessNonIVOperand = [&](bool SignExt) {
1374 const SCEV *WideLHS;
1375 const SCEV *WideRHS;
1376
1377 auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1378 if (SignExt)
1379 return SE->getSignExtendExpr(Op: S, Ty);
1380 return SE->getZeroExtendExpr(Op: S, Ty);
1381 };
1382
1383 if (IVOpIdx == 0) {
1384 WideLHS = SE->getSCEV(V: WideDef);
1385 const SCEV *NarrowRHS = SE->getSCEV(V: NarrowUse->getOperand(i: 1));
1386 WideRHS = GetExtend(NarrowRHS, WideType);
1387 } else {
1388 const SCEV *NarrowLHS = SE->getSCEV(V: NarrowUse->getOperand(i: 0));
1389 WideLHS = GetExtend(NarrowLHS, WideType);
1390 WideRHS = SE->getSCEV(V: WideDef);
1391 }
1392
1393 // WideUse is "WideDef `op.wide` X" as described in the comment.
1394 const SCEV *WideUse =
1395 getSCEVByOpCode(LHS: WideLHS, RHS: WideRHS, OpCode: NarrowUse->getOpcode());
1396
1397 return WideUse == WideAR;
1398 };
1399
1400 bool SignExtend = getExtendKind(I: NarrowDef) == ExtendKind::Sign;
1401 if (!GuessNonIVOperand(SignExtend)) {
1402 SignExtend = !SignExtend;
1403 if (!GuessNonIVOperand(SignExtend))
1404 return nullptr;
1405 }
1406
1407 Value *LHS = (NarrowUse->getOperand(i: 0) == NarrowDef)
1408 ? WideDef
1409 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 0), WideType,
1410 IsSigned: SignExtend, Use: NarrowUse);
1411 Value *RHS = (NarrowUse->getOperand(i: 1) == NarrowDef)
1412 ? WideDef
1413 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 1), WideType,
1414 IsSigned: SignExtend, Use: NarrowUse);
1415
1416 auto *NarrowBO = cast<BinaryOperator>(Val: NarrowUse);
1417 auto *WideBO = BinaryOperator::Create(Op: NarrowBO->getOpcode(), S1: LHS, S2: RHS,
1418 Name: NarrowBO->getName());
1419
1420 IRBuilder<> Builder(NarrowUse);
1421 Builder.Insert(I: WideBO);
1422 WideBO->copyIRFlags(V: NarrowBO);
1423 return WideBO;
1424}
1425
1426WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1427 auto It = ExtendKindMap.find(Val: I);
1428 assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1429 return It->second;
1430}
1431
1432const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1433 unsigned OpCode) const {
1434 switch (OpCode) {
1435 case Instruction::Add:
1436 return SE->getAddExpr(LHS, RHS);
1437 case Instruction::Sub:
1438 return SE->getMinusSCEV(LHS, RHS);
1439 case Instruction::Mul:
1440 return SE->getMulExpr(LHS, RHS);
1441 case Instruction::UDiv:
1442 return SE->getUDivExpr(LHS, RHS);
1443 default:
1444 llvm_unreachable("Unsupported opcode.");
1445 };
1446}
1447
1448namespace {
1449
1450// Represents a interesting integer binary operation for
1451// getExtendedOperandRecurrence. This may be a shl that is being treated as a
1452// multiply or a 'or disjoint' that is being treated as 'add nsw nuw'.
1453struct BinaryOp {
1454 unsigned Opcode;
1455 std::array<Value *, 2> Operands;
1456 bool IsNSW = false;
1457 bool IsNUW = false;
1458
1459 explicit BinaryOp(Instruction *Op)
1460 : Opcode(Op->getOpcode()),
1461 Operands({Op->getOperand(i: 0), Op->getOperand(i: 1)}) {
1462 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: Op)) {
1463 IsNSW = OBO->hasNoSignedWrap();
1464 IsNUW = OBO->hasNoUnsignedWrap();
1465 }
1466 }
1467
1468 explicit BinaryOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
1469 bool IsNSW = false, bool IsNUW = false)
1470 : Opcode(Opcode), Operands({LHS, RHS}), IsNSW(IsNSW), IsNUW(IsNUW) {}
1471};
1472
1473} // end anonymous namespace
1474
1475static std::optional<BinaryOp> matchBinaryOp(Instruction *Op) {
1476 switch (Op->getOpcode()) {
1477 case Instruction::Add:
1478 case Instruction::Sub:
1479 case Instruction::Mul:
1480 return BinaryOp(Op);
1481 case Instruction::Or: {
1482 // Convert or disjoint into add nuw nsw.
1483 if (cast<PossiblyDisjointInst>(Val: Op)->isDisjoint())
1484 return BinaryOp(Instruction::Add, Op->getOperand(i: 0), Op->getOperand(i: 1),
1485 /*IsNSW=*/true, /*IsNUW=*/true);
1486 break;
1487 }
1488 case Instruction::Shl: {
1489 if (ConstantInt *SA = dyn_cast<ConstantInt>(Val: Op->getOperand(i: 1))) {
1490 unsigned BitWidth = cast<IntegerType>(Val: SA->getType())->getBitWidth();
1491
1492 // If the shift count is not less than the bitwidth, the result of
1493 // the shift is undefined. Don't try to analyze it, because the
1494 // resolution chosen here may differ from the resolution chosen in
1495 // other parts of the compiler.
1496 if (SA->getValue().ult(RHS: BitWidth)) {
1497 // We can safely preserve the nuw flag in all cases. It's also safe to
1498 // turn a nuw nsw shl into a nuw nsw mul. However, nsw in isolation
1499 // requires special handling. It can be preserved as long as we're not
1500 // left shifting by bitwidth - 1.
1501 bool IsNUW = Op->hasNoUnsignedWrap();
1502 bool IsNSW = Op->hasNoSignedWrap() &&
1503 (IsNUW || SA->getValue().ult(RHS: BitWidth - 1));
1504
1505 ConstantInt *X =
1506 ConstantInt::get(Context&: Op->getContext(),
1507 V: APInt::getOneBitSet(numBits: BitWidth, BitNo: SA->getZExtValue()));
1508 return BinaryOp(Instruction::Mul, Op->getOperand(i: 0), X, IsNSW, IsNUW);
1509 }
1510 }
1511
1512 break;
1513 }
1514 }
1515
1516 return std::nullopt;
1517}
1518
1519/// No-wrap operations can transfer sign extension of their result to their
1520/// operands. Generate the SCEV value for the widened operation without
1521/// actually modifying the IR yet. If the expression after extending the
1522/// operands is an AddRec for this loop, return the AddRec and the kind of
1523/// extension used.
1524WidenIV::WidenedRecTy
1525WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1526 auto Op = matchBinaryOp(Op: DU.NarrowUse);
1527 if (!Op)
1528 return {nullptr, ExtendKind::Unknown};
1529
1530 assert((Op->Opcode == Instruction::Add || Op->Opcode == Instruction::Sub ||
1531 Op->Opcode == Instruction::Mul) &&
1532 "Unexpected opcode");
1533
1534 // One operand (NarrowDef) has already been extended to WideDef. Now determine
1535 // if extending the other will lead to a recurrence.
1536 const unsigned ExtendOperIdx = Op->Operands[0] == DU.NarrowDef ? 1 : 0;
1537 assert(Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef && "bad DU");
1538
1539 ExtendKind ExtKind = getExtendKind(I: DU.NarrowDef);
1540 if (!(ExtKind == ExtendKind::Sign && Op->IsNSW) &&
1541 !(ExtKind == ExtendKind::Zero && Op->IsNUW)) {
1542 ExtKind = ExtendKind::Unknown;
1543
1544 // For a non-negative NarrowDef, we can choose either type of
1545 // extension. We want to use the current extend kind if legal
1546 // (see above), and we only hit this code if we need to check
1547 // the opposite case.
1548 if (DU.NeverNegative) {
1549 if (Op->IsNSW) {
1550 ExtKind = ExtendKind::Sign;
1551 } else if (Op->IsNUW) {
1552 ExtKind = ExtendKind::Zero;
1553 }
1554 }
1555 }
1556
1557 const SCEV *ExtendOperExpr = SE->getSCEV(V: Op->Operands[ExtendOperIdx]);
1558 if (ExtKind == ExtendKind::Sign)
1559 ExtendOperExpr = SE->getSignExtendExpr(Op: ExtendOperExpr, Ty: WideType);
1560 else if (ExtKind == ExtendKind::Zero)
1561 ExtendOperExpr = SE->getZeroExtendExpr(Op: ExtendOperExpr, Ty: WideType);
1562 else
1563 return {nullptr, ExtendKind::Unknown};
1564
1565 // When creating this SCEV expr, don't apply the current operations NSW or NUW
1566 // flags. This instruction may be guarded by control flow that the no-wrap
1567 // behavior depends on. Non-control-equivalent instructions can be mapped to
1568 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1569 // semantics to those operations.
1570 const SCEV *lhs = SE->getSCEV(V: DU.WideDef);
1571 const SCEV *rhs = ExtendOperExpr;
1572
1573 // Let's swap operands to the initial order for the case of non-commutative
1574 // operations, like SUB. See PR21014.
1575 if (ExtendOperIdx == 0)
1576 std::swap(a&: lhs, b&: rhs);
1577 const SCEVAddRecExpr *AddRec =
1578 dyn_cast<SCEVAddRecExpr>(Val: getSCEVByOpCode(LHS: lhs, RHS: rhs, OpCode: Op->Opcode));
1579
1580 if (!AddRec || AddRec->getLoop() != L)
1581 return {nullptr, ExtendKind::Unknown};
1582
1583 return {AddRec, ExtKind};
1584}
1585
1586/// Is this instruction potentially interesting for further simplification after
1587/// widening it's type? In other words, can the extend be safely hoisted out of
1588/// the loop with SCEV reducing the value to a recurrence on the same loop. If
1589/// so, return the extended recurrence and the kind of extension used. Otherwise
1590/// return {nullptr, ExtendKind::Unknown}.
1591WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1592 if (!DU.NarrowUse->getType()->isIntegerTy())
1593 return {nullptr, ExtendKind::Unknown};
1594
1595 const SCEV *NarrowExpr = SE->getSCEV(V: DU.NarrowUse);
1596 if (SE->getTypeSizeInBits(Ty: NarrowExpr->getType()) >=
1597 SE->getTypeSizeInBits(Ty: WideType)) {
1598 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1599 // index. So don't follow this use.
1600 return {nullptr, ExtendKind::Unknown};
1601 }
1602
1603 const SCEV *WideExpr;
1604 ExtendKind ExtKind;
1605 if (DU.NeverNegative) {
1606 WideExpr = SE->getSignExtendExpr(Op: NarrowExpr, Ty: WideType);
1607 if (isa<SCEVAddRecExpr>(Val: WideExpr))
1608 ExtKind = ExtendKind::Sign;
1609 else {
1610 WideExpr = SE->getZeroExtendExpr(Op: NarrowExpr, Ty: WideType);
1611 ExtKind = ExtendKind::Zero;
1612 }
1613 } else if (getExtendKind(I: DU.NarrowDef) == ExtendKind::Sign) {
1614 WideExpr = SE->getSignExtendExpr(Op: NarrowExpr, Ty: WideType);
1615 ExtKind = ExtendKind::Sign;
1616 } else {
1617 WideExpr = SE->getZeroExtendExpr(Op: NarrowExpr, Ty: WideType);
1618 ExtKind = ExtendKind::Zero;
1619 }
1620 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Val: WideExpr);
1621 if (!AddRec || AddRec->getLoop() != L)
1622 return {nullptr, ExtendKind::Unknown};
1623 return {AddRec, ExtKind};
1624}
1625
1626/// This IV user cannot be widened. Replace this use of the original narrow IV
1627/// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1628void WidenIV::truncateIVUse(NarrowIVDefUse DU) {
1629 auto *InsertPt = getInsertPointForUses(User: DU.NarrowUse, Def: DU.NarrowDef, DT, LI);
1630 if (!InsertPt)
1631 return;
1632 LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1633 << *DU.NarrowUse << "\n");
1634 ExtendKind ExtKind = getExtendKind(I: DU.NarrowDef);
1635 IRBuilder<> Builder(InsertPt);
1636 Value *Trunc =
1637 Builder.CreateTrunc(V: DU.WideDef, DestTy: DU.NarrowDef->getType(), Name: "",
1638 IsNUW: DU.NeverNegative || ExtKind == ExtendKind::Zero,
1639 IsNSW: DU.NeverNegative || ExtKind == ExtendKind::Sign);
1640 DU.NarrowUse->replaceUsesOfWith(From: DU.NarrowDef, To: Trunc);
1641}
1642
1643/// If the narrow use is a compare instruction, then widen the compare
1644// (and possibly the other operand). The extend operation is hoisted into the
1645// loop preheader as far as possible.
1646bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1647 ICmpInst *Cmp = dyn_cast<ICmpInst>(Val: DU.NarrowUse);
1648 if (!Cmp)
1649 return false;
1650
1651 // We can legally widen the comparison in the following two cases:
1652 //
1653 // - The signedness of the IV extension and comparison match
1654 //
1655 // - The narrow IV is always non-negative (and thus its sign extension is
1656 // equal to its zero extension). For instance, let's say we're zero
1657 // extending %narrow for the following use
1658 //
1659 // icmp slt i32 %narrow, %val ... (A)
1660 //
1661 // and %narrow is always non-negative. Then
1662 //
1663 // (A) == icmp slt i32 sext(%narrow), sext(%val)
1664 // == icmp slt i32 zext(%narrow), sext(%val)
1665 bool IsSigned = getExtendKind(I: DU.NarrowDef) == ExtendKind::Sign;
1666 bool CmpPreferredSign = Cmp->hasSameSign() ? IsSigned : Cmp->isSigned();
1667 if (!DU.NeverNegative && IsSigned != CmpPreferredSign)
1668 return false;
1669
1670 Value *Op = Cmp->getOperand(i_nocapture: Cmp->getOperand(i_nocapture: 0) == DU.NarrowDef ? 1 : 0);
1671 unsigned CastWidth = SE->getTypeSizeInBits(Ty: Op->getType());
1672 unsigned IVWidth = SE->getTypeSizeInBits(Ty: WideType);
1673 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1674
1675 // Widen the compare instruction.
1676 DU.NarrowUse->replaceUsesOfWith(From: DU.NarrowDef, To: DU.WideDef);
1677
1678 // Widen the other operand of the compare, if necessary.
1679 if (CastWidth < IVWidth) {
1680 // If the narrow IV is always non-negative and the other operand is sext,
1681 // widen using sext so we can combine them. This works for all non-signed
1682 // comparison predicates.
1683 if (DU.NeverNegative && isa<SExtInst>(Val: Op) && !Cmp->isSigned())
1684 CmpPreferredSign = true;
1685
1686 Value *ExtOp = createExtendInst(NarrowOper: Op, WideType, IsSigned: CmpPreferredSign, Use: Cmp);
1687 DU.NarrowUse->replaceUsesOfWith(From: Op, To: ExtOp);
1688 }
1689 return true;
1690}
1691
1692// The widenIVUse avoids generating trunc by evaluating the use as AddRec, this
1693// will not work when:
1694// 1) SCEV traces back to an instruction inside the loop that SCEV can not
1695// expand, eg. add %indvar, (load %addr)
1696// 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant
1697// While SCEV fails to avoid trunc, we can still try to use instruction
1698// combining approach to prove trunc is not required. This can be further
1699// extended with other instruction combining checks, but for now we handle the
1700// following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")
1701//
1702// Src:
1703// %c = sub nsw %b, %indvar
1704// %d = sext %c to i64
1705// Dst:
1706// %indvar.ext1 = sext %indvar to i64
1707// %m = sext %b to i64
1708// %d = sub nsw i64 %m, %indvar.ext1
1709// Therefore, as long as the result of add/sub/mul is extended to wide type, no
1710// trunc is required regardless of how %b is generated. This pattern is common
1711// when calculating address in 64 bit architecture
1712bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1713 Instruction *NarrowUse = DU.NarrowUse;
1714 Instruction *NarrowDef = DU.NarrowDef;
1715 Instruction *WideDef = DU.WideDef;
1716
1717 // Handle the common case of add<nsw/nuw>
1718 const unsigned OpCode = NarrowUse->getOpcode();
1719 // Only Add/Sub/Mul instructions are supported.
1720 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1721 OpCode != Instruction::Mul)
1722 return false;
1723
1724 // The operand that is not defined by NarrowDef of DU. Let's call it the
1725 // other operand.
1726 assert((NarrowUse->getOperand(0) == NarrowDef ||
1727 NarrowUse->getOperand(1) == NarrowDef) &&
1728 "bad DU");
1729
1730 const OverflowingBinaryOperator *OBO =
1731 cast<OverflowingBinaryOperator>(Val: NarrowUse);
1732 ExtendKind ExtKind = getExtendKind(I: NarrowDef);
1733 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap();
1734 bool CanZeroExtend = ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap();
1735 auto AnotherOpExtKind = ExtKind;
1736
1737 // Check that all uses are either:
1738 // - narrow def (in case of we are widening the IV increment);
1739 // - single-input LCSSA Phis;
1740 // - comparison of the chosen type;
1741 // - extend of the chosen type (raison d'etre).
1742 SmallVector<Instruction *, 4> ExtUsers;
1743 SmallVector<PHINode *, 4> LCSSAPhiUsers;
1744 SmallVector<ICmpInst *, 4> ICmpUsers;
1745 for (Use &U : NarrowUse->uses()) {
1746 Instruction *User = cast<Instruction>(Val: U.getUser());
1747 if (User == NarrowDef)
1748 continue;
1749 if (!L->contains(Inst: User)) {
1750 auto *LCSSAPhi = cast<PHINode>(Val: User);
1751 // Make sure there is only 1 input, so that we don't have to split
1752 // critical edges.
1753 if (LCSSAPhi->getNumOperands() != 1)
1754 return false;
1755 LCSSAPhiUsers.push_back(Elt: LCSSAPhi);
1756 continue;
1757 }
1758 if (auto *ICmp = dyn_cast<ICmpInst>(Val: User)) {
1759 auto Pred = ICmp->getPredicate();
1760 // We have 3 types of predicates: signed, unsigned and equality
1761 // predicates. For equality, it's legal to widen icmp for either sign and
1762 // zero extend. For sign extend, we can also do so for signed predicates,
1763 // likeweise for zero extend we can widen icmp for unsigned predicates.
1764 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1765 return false;
1766 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1767 return false;
1768 ICmpUsers.push_back(Elt: ICmp);
1769 continue;
1770 }
1771 if (ExtKind == ExtendKind::Sign)
1772 User = dyn_cast<SExtInst>(Val: User);
1773 else
1774 User = dyn_cast<ZExtInst>(Val: User);
1775 if (!User || User->getType() != WideType)
1776 return false;
1777 ExtUsers.push_back(Elt: User);
1778 }
1779 if (ExtUsers.empty()) {
1780 DeadInsts.emplace_back(Args&: NarrowUse);
1781 return true;
1782 }
1783
1784 // We'll prove some facts that should be true in the context of ext users. If
1785 // there is no users, we are done now. If there are some, pick their common
1786 // dominator as context.
1787 const Instruction *CtxI = findCommonDominator(Instructions: ExtUsers, DT&: *DT);
1788
1789 if (!CanSignExtend && !CanZeroExtend) {
1790 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
1791 // will most likely not see it. Let's try to prove it.
1792 if (OpCode != Instruction::Add)
1793 return false;
1794 if (ExtKind != ExtendKind::Zero)
1795 return false;
1796 const SCEV *LHS = SE->getSCEV(V: OBO->getOperand(i_nocapture: 0));
1797 const SCEV *RHS = SE->getSCEV(V: OBO->getOperand(i_nocapture: 1));
1798 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
1799 if (NarrowUse->getOperand(i: 0) != NarrowDef)
1800 return false;
1801 // We cannot use a different extend kind for the same operand.
1802 if (NarrowUse->getOperand(i: 1) == NarrowDef)
1803 return false;
1804 if (!SE->isKnownNegative(S: RHS))
1805 return false;
1806 bool ProvedSubNUW = SE->isKnownPredicateAt(Pred: ICmpInst::ICMP_UGE, LHS,
1807 RHS: SE->getNegativeSCEV(V: RHS), CtxI);
1808 if (!ProvedSubNUW)
1809 return false;
1810 // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as
1811 // neg(zext(neg(op))), which is basically sext(op).
1812 AnotherOpExtKind = ExtendKind::Sign;
1813 }
1814
1815 // Verifying that Defining operand is an AddRec
1816 const SCEV *Op1 = SE->getSCEV(V: WideDef);
1817 const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Val: Op1);
1818 if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1819 return false;
1820
1821 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1822
1823 // Generating a widening use instruction.
1824 Value *LHS =
1825 (NarrowUse->getOperand(i: 0) == NarrowDef)
1826 ? WideDef
1827 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 0), WideType,
1828 IsSigned: AnotherOpExtKind == ExtendKind::Sign, Use: NarrowUse);
1829 Value *RHS =
1830 (NarrowUse->getOperand(i: 1) == NarrowDef)
1831 ? WideDef
1832 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 1), WideType,
1833 IsSigned: AnotherOpExtKind == ExtendKind::Sign, Use: NarrowUse);
1834
1835 auto *NarrowBO = cast<BinaryOperator>(Val: NarrowUse);
1836 auto *WideBO = BinaryOperator::Create(Op: NarrowBO->getOpcode(), S1: LHS, S2: RHS,
1837 Name: NarrowBO->getName());
1838 IRBuilder<> Builder(NarrowUse);
1839 Builder.Insert(I: WideBO);
1840 WideBO->copyIRFlags(V: NarrowBO);
1841 ExtendKindMap[NarrowUse] = ExtKind;
1842
1843 for (Instruction *User : ExtUsers) {
1844 assert(User->getType() == WideType && "Checked before!");
1845 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1846 << *WideBO << "\n");
1847 ++NumElimExt;
1848 User->replaceAllUsesWith(V: WideBO);
1849 DeadInsts.emplace_back(Args&: User);
1850 }
1851
1852 for (PHINode *User : LCSSAPhiUsers) {
1853 assert(User->getNumOperands() == 1 && "Checked before!");
1854 Builder.SetInsertPoint(User);
1855 auto *WidePN =
1856 Builder.CreatePHI(Ty: WideBO->getType(), NumReservedValues: 1, Name: User->getName() + ".wide");
1857 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
1858 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
1859 "Not a LCSSA Phi?");
1860 WidePN->addIncoming(V: WideBO, BB: LoopExitingBlock);
1861 Builder.SetInsertPoint(User->getParent()->getFirstInsertionPt());
1862 auto *TruncPN = Builder.CreateTrunc(V: WidePN, DestTy: User->getType());
1863 User->replaceAllUsesWith(V: TruncPN);
1864 DeadInsts.emplace_back(Args&: User);
1865 }
1866
1867 for (ICmpInst *User : ICmpUsers) {
1868 Builder.SetInsertPoint(User);
1869 auto ExtendedOp = [&](Value * V)->Value * {
1870 if (V == NarrowUse)
1871 return WideBO;
1872 if (ExtKind == ExtendKind::Zero)
1873 return Builder.CreateZExt(V, DestTy: WideBO->getType());
1874 else
1875 return Builder.CreateSExt(V, DestTy: WideBO->getType());
1876 };
1877 auto Pred = User->getPredicate();
1878 auto *LHS = ExtendedOp(User->getOperand(i_nocapture: 0));
1879 auto *RHS = ExtendedOp(User->getOperand(i_nocapture: 1));
1880 auto *WideCmp =
1881 Builder.CreateICmp(P: Pred, LHS, RHS, Name: User->getName() + ".wide");
1882 User->replaceAllUsesWith(V: WideCmp);
1883 DeadInsts.emplace_back(Args&: User);
1884 }
1885
1886 return true;
1887}
1888
1889/// Determine whether an individual user of the narrow IV can be widened. If so,
1890/// return the wide clone of the user.
1891Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,
1892 SCEVExpander &Rewriter, PHINode *OrigPhi,
1893 PHINode *WidePhi) {
1894 assert(ExtendKindMap.count(DU.NarrowDef) &&
1895 "Should already know the kind of extension used to widen NarrowDef");
1896
1897 // This narrow use can be widened by a sext if it's non-negative or its narrow
1898 // def was widened by a sext. Same for zext.
1899 bool CanWidenBySExt =
1900 DU.NeverNegative || getExtendKind(I: DU.NarrowDef) == ExtendKind::Sign;
1901 bool CanWidenByZExt =
1902 DU.NeverNegative || getExtendKind(I: DU.NarrowDef) == ExtendKind::Zero;
1903
1904 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1905 if (PHINode *UsePhi = dyn_cast<PHINode>(Val: DU.NarrowUse)) {
1906 if (LI->getLoopFor(BB: UsePhi->getParent()) != L) {
1907 // For LCSSA phis, sink the truncate outside the loop.
1908 // After SimplifyCFG most loop exit targets have a single predecessor.
1909 // Otherwise fall back to a truncate within the loop.
1910 if (UsePhi->getNumOperands() != 1)
1911 truncateIVUse(DU);
1912 else {
1913 // Widening the PHI requires us to insert a trunc. The logical place
1914 // for this trunc is in the same BB as the PHI. This is not possible if
1915 // the BB is terminated by a catchswitch.
1916 if (isa<CatchSwitchInst>(Val: UsePhi->getParent()->getTerminator()))
1917 return nullptr;
1918
1919 PHINode *WidePhi =
1920 PHINode::Create(Ty: DU.WideDef->getType(), NumReservedValues: 1, NameStr: UsePhi->getName() + ".wide",
1921 InsertBefore: UsePhi->getIterator());
1922 WidePhi->addIncoming(V: DU.WideDef, BB: UsePhi->getIncomingBlock(i: 0));
1923 BasicBlock *WidePhiBB = WidePhi->getParent();
1924 IRBuilder<> Builder(WidePhiBB->getFirstInsertionPt());
1925 Value *Trunc = Builder.CreateTrunc(V: WidePhi, DestTy: DU.NarrowDef->getType(), Name: "",
1926 IsNUW: CanWidenByZExt, IsNSW: CanWidenBySExt);
1927 UsePhi->replaceAllUsesWith(V: Trunc);
1928 DeadInsts.emplace_back(Args&: UsePhi);
1929 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1930 << *WidePhi << "\n");
1931 }
1932 return nullptr;
1933 }
1934 }
1935
1936 // Our raison d'etre! Eliminate sign and zero extension.
1937 if ((match(V: DU.NarrowUse, P: m_SExtLike(Op: m_Value())) && CanWidenBySExt) ||
1938 (isa<ZExtInst>(Val: DU.NarrowUse) && CanWidenByZExt)) {
1939 Value *NewDef = DU.WideDef;
1940 if (DU.NarrowUse->getType() != WideType) {
1941 unsigned CastWidth = SE->getTypeSizeInBits(Ty: DU.NarrowUse->getType());
1942 unsigned IVWidth = SE->getTypeSizeInBits(Ty: WideType);
1943 if (CastWidth < IVWidth) {
1944 // The cast isn't as wide as the IV, so insert a Trunc.
1945 IRBuilder<> Builder(DU.NarrowUse);
1946 NewDef = Builder.CreateTrunc(V: DU.WideDef, DestTy: DU.NarrowUse->getType(), Name: "",
1947 IsNUW: CanWidenByZExt, IsNSW: CanWidenBySExt);
1948 }
1949 else {
1950 // A wider extend was hidden behind a narrower one. This may induce
1951 // another round of IV widening in which the intermediate IV becomes
1952 // dead. It should be very rare.
1953 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1954 << " not wide enough to subsume " << *DU.NarrowUse
1955 << "\n");
1956 DU.NarrowUse->replaceUsesOfWith(From: DU.NarrowDef, To: DU.WideDef);
1957 NewDef = DU.NarrowUse;
1958 }
1959 }
1960 if (NewDef != DU.NarrowUse) {
1961 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1962 << " replaced by " << *DU.WideDef << "\n");
1963 ++NumElimExt;
1964 DU.NarrowUse->replaceAllUsesWith(V: NewDef);
1965 DeadInsts.emplace_back(Args&: DU.NarrowUse);
1966 }
1967 // Now that the extend is gone, we want to expose it's uses for potential
1968 // further simplification. We don't need to directly inform SimplifyIVUsers
1969 // of the new users, because their parent IV will be processed later as a
1970 // new loop phi. If we preserved IVUsers analysis, we would also want to
1971 // push the uses of WideDef here.
1972
1973 // No further widening is needed. The deceased [sz]ext had done it for us.
1974 return nullptr;
1975 }
1976
1977 auto tryAddRecExpansion = [&]() -> Instruction* {
1978 // Does this user itself evaluate to a recurrence after widening?
1979 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1980 if (!WideAddRec.first)
1981 WideAddRec = getWideRecurrence(DU);
1982 assert((WideAddRec.first == nullptr) ==
1983 (WideAddRec.second == ExtendKind::Unknown));
1984 if (!WideAddRec.first)
1985 return nullptr;
1986
1987 auto CanUseWideInc = [&]() {
1988 if (!WideInc)
1989 return false;
1990 // Reuse the IV increment that SCEVExpander created. Recompute flags,
1991 // unless the flags for both increments agree and it is safe to use the
1992 // ones from the original inc. In that case, the new use of the wide
1993 // increment won't be more poisonous.
1994 bool NeedToRecomputeFlags =
1995 !SCEVExpander::canReuseFlagsFromOriginalIVInc(
1996 OrigPhi, WidePhi, OrigInc: DU.NarrowUse, WideInc) ||
1997 DU.NarrowUse->hasNoUnsignedWrap() != WideInc->hasNoUnsignedWrap() ||
1998 DU.NarrowUse->hasNoSignedWrap() != WideInc->hasNoSignedWrap();
1999 return WideAddRec.first == WideIncExpr &&
2000 Rewriter.hoistIVInc(IncV: WideInc, InsertPos: DU.NarrowUse, RecomputePoisonFlags: NeedToRecomputeFlags);
2001 };
2002
2003 Instruction *WideUse = nullptr;
2004 if (CanUseWideInc())
2005 WideUse = WideInc;
2006 else {
2007 WideUse = cloneIVUser(DU, WideAR: WideAddRec.first);
2008 if (!WideUse)
2009 return nullptr;
2010 }
2011 // Evaluation of WideAddRec ensured that the narrow expression could be
2012 // extended outside the loop without overflow. This suggests that the wide use
2013 // evaluates to the same expression as the extended narrow use, but doesn't
2014 // absolutely guarantee it. Hence the following failsafe check. In rare cases
2015 // where it fails, we simply throw away the newly created wide use.
2016 if (WideAddRec.first != SE->getSCEV(V: WideUse)) {
2017 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
2018 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
2019 << "\n");
2020 DeadInsts.emplace_back(Args&: WideUse);
2021 return nullptr;
2022 };
2023
2024 // if we reached this point then we are going to replace
2025 // DU.NarrowUse with WideUse. Reattach DbgValue then.
2026 replaceAllDbgUsesWith(From&: *DU.NarrowUse, To&: *WideUse, DomPoint&: *WideUse, DT&: *DT);
2027
2028 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
2029 // Returning WideUse pushes it on the worklist.
2030 return WideUse;
2031 };
2032
2033 if (auto *I = tryAddRecExpansion())
2034 return I;
2035
2036 // If use is a loop condition, try to promote the condition instead of
2037 // truncating the IV first.
2038 if (widenLoopCompare(DU))
2039 return nullptr;
2040
2041 // We are here about to generate a truncate instruction that may hurt
2042 // performance because the scalar evolution expression computed earlier
2043 // in WideAddRec.first does not indicate a polynomial induction expression.
2044 // In that case, look at the operands of the use instruction to determine
2045 // if we can still widen the use instead of truncating its operand.
2046 if (widenWithVariantUse(DU))
2047 return nullptr;
2048
2049 // This user does not evaluate to a recurrence after widening, so don't
2050 // follow it. Instead insert a Trunc to kill off the original use,
2051 // eventually isolating the original narrow IV so it can be removed.
2052 truncateIVUse(DU);
2053 return nullptr;
2054}
2055
2056/// Add eligible users of NarrowDef to NarrowIVUsers.
2057void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
2058 const SCEV *NarrowSCEV = SE->getSCEV(V: NarrowDef);
2059 bool NonNegativeDef =
2060 SE->isKnownPredicateAt(Pred: ICmpInst::ICMP_SGE, LHS: NarrowSCEV,
2061 RHS: SE->getZero(Ty: NarrowSCEV->getType()), CtxI: NarrowDef);
2062 for (User *U : NarrowDef->users()) {
2063 Instruction *NarrowUser = cast<Instruction>(Val: U);
2064
2065 // Handle data flow merges and bizarre phi cycles.
2066 if (!Widened.insert(Ptr: NarrowUser).second)
2067 continue;
2068
2069 bool NonNegativeUse = false;
2070 if (!NonNegativeDef) {
2071 // We might have a control-dependent range information for this context.
2072 if (auto RangeInfo = getPostIncRangeInfo(Def: NarrowDef, UseI: NarrowUser))
2073 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
2074 }
2075
2076 NarrowIVUsers.emplace_back(Args&: NarrowDef, Args&: NarrowUser, Args&: WideDef,
2077 Args: NonNegativeDef || NonNegativeUse);
2078 }
2079}
2080
2081/// Process a single induction variable. First use the SCEVExpander to create a
2082/// wide induction variable that evaluates to the same recurrence as the
2083/// original narrow IV. Then use a worklist to forward traverse the narrow IV's
2084/// def-use chain. After widenIVUse has processed all interesting IV users, the
2085/// narrow IV will be isolated for removal by DeleteDeadPHIs.
2086///
2087/// It would be simpler to delete uses as they are processed, but we must avoid
2088/// invalidating SCEV expressions.
2089PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
2090 // Is this phi an induction variable?
2091 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: OrigPhi));
2092 if (!AddRec)
2093 return nullptr;
2094
2095 // Widen the induction variable expression.
2096 const SCEV *WideIVExpr = getExtendKind(I: OrigPhi) == ExtendKind::Sign
2097 ? SE->getSignExtendExpr(Op: AddRec, Ty: WideType)
2098 : SE->getZeroExtendExpr(Op: AddRec, Ty: WideType);
2099
2100 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
2101 "Expect the new IV expression to preserve its type");
2102
2103 // Can the IV be extended outside the loop without overflow?
2104 AddRec = dyn_cast<SCEVAddRecExpr>(Val: WideIVExpr);
2105 if (!AddRec || AddRec->getLoop() != L)
2106 return nullptr;
2107
2108 // An AddRec must have loop-invariant operands. Since this AddRec is
2109 // materialized by a loop header phi, the expression cannot have any post-loop
2110 // operands, so they must dominate the loop header.
2111 assert(
2112 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
2113 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
2114 "Loop header phi recurrence inputs do not dominate the loop");
2115
2116 // Iterate over IV uses (including transitive ones) looking for IV increments
2117 // of the form 'add nsw %iv, <const>'. For each increment and each use of
2118 // the increment calculate control-dependent range information basing on
2119 // dominating conditions inside of the loop (e.g. a range check inside of the
2120 // loop). Calculated ranges are stored in PostIncRangeInfos map.
2121 //
2122 // Control-dependent range information is later used to prove that a narrow
2123 // definition is not negative (see pushNarrowIVUsers). It's difficult to do
2124 // this on demand because when pushNarrowIVUsers needs this information some
2125 // of the dominating conditions might be already widened.
2126 if (UsePostIncrementRanges)
2127 calculatePostIncRanges(OrigPhi);
2128
2129 // The rewriter provides a value for the desired IV expression. This may
2130 // either find an existing phi or materialize a new one. Either way, we
2131 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
2132 // of the phi-SCC dominates the loop entry.
2133 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
2134 Value *ExpandInst = Rewriter.expandCodeFor(SH: AddRec, Ty: WideType, I: InsertPt);
2135 // If the wide phi is not a phi node, for example a cast node, like bitcast,
2136 // inttoptr, ptrtoint, just skip for now.
2137 if (!(WidePhi = dyn_cast<PHINode>(Val: ExpandInst))) {
2138 // if the cast node is an inserted instruction without any user, we should
2139 // remove it to make sure the pass don't touch the function as we can not
2140 // wide the phi.
2141 if (ExpandInst->use_empty() &&
2142 Rewriter.isInsertedInstruction(I: cast<Instruction>(Val: ExpandInst)))
2143 DeadInsts.emplace_back(Args&: ExpandInst);
2144 return nullptr;
2145 }
2146
2147 // Remembering the WideIV increment generated by SCEVExpander allows
2148 // widenIVUse to reuse it when widening the narrow IV's increment. We don't
2149 // employ a general reuse mechanism because the call above is the only call to
2150 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
2151 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2152 WideInc =
2153 dyn_cast<Instruction>(Val: WidePhi->getIncomingValueForBlock(BB: LatchBlock));
2154 if (WideInc) {
2155 WideIncExpr = SE->getSCEV(V: WideInc);
2156 // Propagate the debug location associated with the original loop
2157 // increment to the new (widened) increment.
2158 auto *OrigInc =
2159 cast<Instruction>(Val: OrigPhi->getIncomingValueForBlock(BB: LatchBlock));
2160
2161 WideInc->setDebugLoc(OrigInc->getDebugLoc());
2162 // We are replacing a narrow IV increment with a wider IV increment. If
2163 // the original (narrow) increment did not wrap, the wider increment one
2164 // should not wrap either. Set the flags to be the union of both wide
2165 // increment and original increment; this ensures we preserve flags SCEV
2166 // could infer for the wider increment. Limit this only to cases where
2167 // both increments directly increment the corresponding PHI nodes and have
2168 // the same opcode. It is not safe to re-use the flags from the original
2169 // increment, if it is more complex and SCEV expansion may have yielded a
2170 // more simplified wider increment.
2171 if (SCEVExpander::canReuseFlagsFromOriginalIVInc(OrigPhi, WidePhi,
2172 OrigInc, WideInc) &&
2173 isa<OverflowingBinaryOperator>(Val: OrigInc) &&
2174 isa<OverflowingBinaryOperator>(Val: WideInc)) {
2175 WideInc->setHasNoUnsignedWrap(WideInc->hasNoUnsignedWrap() ||
2176 OrigInc->hasNoUnsignedWrap());
2177 WideInc->setHasNoSignedWrap(WideInc->hasNoSignedWrap() ||
2178 OrigInc->hasNoSignedWrap());
2179 }
2180 }
2181 }
2182
2183 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
2184 ++NumWidened;
2185
2186 // Traverse the def-use chain using a worklist starting at the original IV.
2187 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
2188
2189 Widened.insert(Ptr: OrigPhi);
2190 pushNarrowIVUsers(NarrowDef: OrigPhi, WideDef: WidePhi);
2191
2192 while (!NarrowIVUsers.empty()) {
2193 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
2194
2195 // Process a def-use edge. This may replace the use, so don't hold a
2196 // use_iterator across it.
2197 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);
2198
2199 // Follow all def-use edges from the previous narrow use.
2200 if (WideUse)
2201 pushNarrowIVUsers(NarrowDef: DU.NarrowUse, WideDef: WideUse);
2202
2203 // widenIVUse may have removed the def-use edge.
2204 if (DU.NarrowDef->use_empty())
2205 DeadInsts.emplace_back(Args&: DU.NarrowDef);
2206 }
2207
2208 // Attach any debug information to the new PHI.
2209 replaceAllDbgUsesWith(From&: *OrigPhi, To&: *WidePhi, DomPoint&: *WidePhi, DT&: *DT);
2210
2211 return WidePhi;
2212}
2213
2214/// Calculates control-dependent range for the given def at the given context
2215/// by looking at dominating conditions inside of the loop
2216void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
2217 Instruction *NarrowUser) {
2218 Value *NarrowDefLHS;
2219 const APInt *NarrowDefRHS;
2220 if (!match(V: NarrowDef, P: m_NSWAdd(L: m_Value(V&: NarrowDefLHS),
2221 R: m_APInt(Res&: NarrowDefRHS))) ||
2222 !NarrowDefRHS->isNonNegative())
2223 return;
2224
2225 auto UpdateRangeFromCondition = [&](Value *Condition, bool TrueDest) {
2226 CmpPredicate Pred;
2227 Value *CmpRHS;
2228 if (!match(V: Condition, P: m_ICmp(Pred, L: m_Specific(V: NarrowDefLHS),
2229 R: m_Value(V&: CmpRHS))))
2230 return;
2231
2232 CmpPredicate P = TrueDest ? Pred : ICmpInst::getInverseCmpPredicate(Pred);
2233
2234 auto CmpRHSRange = SE->getSignedRange(S: SE->getSCEV(V: CmpRHS));
2235 auto CmpConstrainedLHSRange =
2236 ConstantRange::makeAllowedICmpRegion(Pred: P, Other: CmpRHSRange);
2237 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2238 Other: *NarrowDefRHS, NoWrapKind: OverflowingBinaryOperator::NoSignedWrap);
2239
2240 updatePostIncRangeInfo(Def: NarrowDef, UseI: NarrowUser, R: NarrowDefRange);
2241 };
2242
2243 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
2244 if (!HasGuards)
2245 return;
2246
2247 for (Instruction &I : make_range(x: Ctx->getIterator().getReverse(),
2248 y: Ctx->getParent()->rend())) {
2249 Value *C = nullptr;
2250 if (match(V: &I, P: m_Intrinsic<Intrinsic::experimental_guard>(Ops: m_Value(V&: C))))
2251 UpdateRangeFromCondition(C, /*TrueDest=*/true);
2252 }
2253 };
2254
2255 UpdateRangeFromGuards(NarrowUser);
2256
2257 BasicBlock *NarrowUserBB = NarrowUser->getParent();
2258 // If NarrowUserBB is statically unreachable asking dominator queries may
2259 // yield surprising results. (e.g. the block may not have a dom tree node)
2260 if (!DT->isReachableFromEntry(A: NarrowUserBB))
2261 return;
2262
2263 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2264 L->contains(BB: DTB->getBlock());
2265 DTB = DTB->getIDom()) {
2266 auto *BB = DTB->getBlock();
2267 auto *TI = BB->getTerminator();
2268 UpdateRangeFromGuards(TI);
2269
2270 auto *BI = dyn_cast<CondBrInst>(Val: TI);
2271 if (!BI)
2272 continue;
2273
2274 auto *TrueSuccessor = BI->getSuccessor(i: 0);
2275 auto *FalseSuccessor = BI->getSuccessor(i: 1);
2276
2277 if (DT->dominates(BBE: BasicBlockEdge(BB, TrueSuccessor), BB: NarrowUserBB))
2278 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
2279
2280 if (DT->dominates(BBE: BasicBlockEdge(BB, FalseSuccessor), BB: NarrowUserBB))
2281 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
2282 }
2283}
2284
2285/// Calculates PostIncRangeInfos map for the given IV
2286void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
2287 SmallPtrSet<Instruction *, 16> Visited;
2288 SmallVector<Instruction *, 6> Worklist;
2289 Worklist.push_back(Elt: OrigPhi);
2290 Visited.insert(Ptr: OrigPhi);
2291
2292 while (!Worklist.empty()) {
2293 Instruction *NarrowDef = Worklist.pop_back_val();
2294
2295 for (Use &U : NarrowDef->uses()) {
2296 auto *NarrowUser = cast<Instruction>(Val: U.getUser());
2297
2298 // Don't go looking outside the current loop.
2299 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
2300 if (!NarrowUserLoop || !L->contains(L: NarrowUserLoop))
2301 continue;
2302
2303 if (!Visited.insert(Ptr: NarrowUser).second)
2304 continue;
2305
2306 Worklist.push_back(Elt: NarrowUser);
2307
2308 calculatePostIncRange(NarrowDef, NarrowUser);
2309 }
2310 }
2311}
2312
2313PHINode *llvm::createWideIV(const WideIVInfo &WI,
2314 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,
2315 DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,
2316 unsigned &NumElimExt, unsigned &NumWidened,
2317 bool HasGuards, bool UsePostIncrementRanges) {
2318 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);
2319 PHINode *WidePHI = Widener.createWideIV(Rewriter);
2320 NumElimExt = Widener.getNumElimExt();
2321 NumWidened = Widener.getNumWidened();
2322 return WidePHI;
2323}
2324