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