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