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