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 SCEV *LHS = SE->getSCEV(V: IVSrc);
171 const SCEV *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 CmpPredicate Pred = ICmp->getCmpPredicate();
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::getSwappedCmpPredicate(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 CmpPredicate Pred = ICmp->getCmpPredicate();
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::getSwappedCmpPredicate(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 ICmp->setSameSign();
292 } else
293 return;
294
295 ++NumElimCmp;
296 Changed = true;
297}
298
299bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
300 // Get the SCEVs for the ICmp operands.
301 const SCEV *N = SE->getSCEV(V: SDiv->getOperand(i_nocapture: 0));
302 const SCEV *D = SE->getSCEV(V: SDiv->getOperand(i_nocapture: 1));
303
304 // Simplify unnecessary loops away.
305 const Loop *L = LI->getLoopFor(BB: SDiv->getParent());
306 N = SE->getSCEVAtScope(S: N, L);
307 D = SE->getSCEVAtScope(S: D, L);
308
309 // Replace sdiv by udiv if both of the operands are non-negative
310 if (SE->isKnownNonNegative(S: N) && SE->isKnownNonNegative(S: D)) {
311 auto *UDiv = BinaryOperator::Create(
312 Op: BinaryOperator::UDiv, S1: SDiv->getOperand(i_nocapture: 0), S2: SDiv->getOperand(i_nocapture: 1),
313 Name: SDiv->getName() + ".udiv", InsertBefore: SDiv->getIterator());
314 UDiv->setIsExact(SDiv->isExact());
315 SDiv->replaceAllUsesWith(V: UDiv);
316 UDiv->setDebugLoc(SDiv->getDebugLoc());
317 LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
318 ++NumSimplifiedSDiv;
319 Changed = true;
320 DeadInsts.push_back(Elt: SDiv);
321 return true;
322 }
323
324 return false;
325}
326
327// i %s n -> i %u n if i >= 0 and n >= 0
328void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
329 auto *N = Rem->getOperand(i_nocapture: 0), *D = Rem->getOperand(i_nocapture: 1);
330 auto *URem = BinaryOperator::Create(Op: BinaryOperator::URem, S1: N, S2: D,
331 Name: Rem->getName() + ".urem", InsertBefore: Rem->getIterator());
332 Rem->replaceAllUsesWith(V: URem);
333 URem->setDebugLoc(Rem->getDebugLoc());
334 LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
335 ++NumSimplifiedSRem;
336 Changed = true;
337 DeadInsts.emplace_back(Args&: Rem);
338}
339
340// i % n --> i if i is in [0,n).
341void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
342 Rem->replaceAllUsesWith(V: Rem->getOperand(i_nocapture: 0));
343 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
344 ++NumElimRem;
345 Changed = true;
346 DeadInsts.emplace_back(Args&: Rem);
347}
348
349// (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
350void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
351 auto *T = Rem->getType();
352 auto *N = Rem->getOperand(i_nocapture: 0), *D = Rem->getOperand(i_nocapture: 1);
353 ICmpInst *ICmp = new ICmpInst(Rem->getIterator(), ICmpInst::ICMP_EQ, N, D);
354 ICmp->setDebugLoc(Rem->getDebugLoc());
355 SelectInst *Sel =
356 SelectInst::Create(C: ICmp, S1: ConstantInt::get(Ty: T, V: 0), S2: N, NameStr: "iv.rem", InsertBefore: Rem->getIterator());
357 Rem->replaceAllUsesWith(V: Sel);
358 Sel->setDebugLoc(Rem->getDebugLoc());
359 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
360 ++NumElimRem;
361 Changed = true;
362 DeadInsts.emplace_back(Args&: Rem);
363}
364
365/// SimplifyIVUsers helper for eliminating useless remainder operations
366/// operating on an induction variable or replacing srem by urem.
367void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,
368 Instruction *IVOperand,
369 bool IsSigned) {
370 auto *NValue = Rem->getOperand(i_nocapture: 0);
371 auto *DValue = Rem->getOperand(i_nocapture: 1);
372 // We're only interested in the case where we know something about
373 // the numerator, unless it is a srem, because we want to replace srem by urem
374 // in general.
375 bool UsedAsNumerator = IVOperand == NValue;
376 if (!UsedAsNumerator && !IsSigned)
377 return;
378
379 const SCEV *N = SE->getSCEV(V: NValue);
380
381 // Simplify unnecessary loops away.
382 const Loop *ICmpLoop = LI->getLoopFor(BB: Rem->getParent());
383 N = SE->getSCEVAtScope(S: N, L: ICmpLoop);
384
385 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(S: N);
386
387 // Do not proceed if the Numerator may be negative
388 if (!IsNumeratorNonNegative)
389 return;
390
391 const SCEV *D = SE->getSCEV(V: DValue);
392 D = SE->getSCEVAtScope(S: D, L: ICmpLoop);
393
394 if (UsedAsNumerator) {
395 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
396 if (SE->isKnownPredicate(Pred: LT, LHS: N, RHS: D)) {
397 replaceRemWithNumerator(Rem);
398 return;
399 }
400
401 auto *T = Rem->getType();
402 const SCEV *NLessOne = SE->getMinusSCEV(LHS: N, RHS: SE->getOne(Ty: T));
403 if (SE->isKnownPredicate(Pred: LT, LHS: NLessOne, RHS: D)) {
404 replaceRemWithNumeratorOrZero(Rem);
405 return;
406 }
407 }
408
409 // Try to replace SRem with URem, if both N and D are known non-negative.
410 // Since we had already check N, we only need to check D now
411 if (!IsSigned || !SE->isKnownNonNegative(S: D))
412 return;
413
414 replaceSRemWithURem(Rem);
415}
416
417bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
418 const SCEV *LHS = SE->getSCEV(V: WO->getLHS());
419 const SCEV *RHS = SE->getSCEV(V: WO->getRHS());
420 if (!SE->willNotOverflow(BinOp: WO->getBinaryOp(), Signed: WO->isSigned(), LHS, RHS))
421 return false;
422
423 // Proved no overflow, nuke the overflow check and, if possible, the overflow
424 // intrinsic as well.
425
426 BinaryOperator *NewResult = BinaryOperator::Create(
427 Op: WO->getBinaryOp(), S1: WO->getLHS(), S2: WO->getRHS(), Name: "", InsertBefore: WO->getIterator());
428
429 if (WO->isSigned())
430 NewResult->setHasNoSignedWrap(true);
431 else
432 NewResult->setHasNoUnsignedWrap(true);
433
434 SmallVector<ExtractValueInst *, 4> ToDelete;
435
436 for (auto *U : WO->users()) {
437 if (auto *EVI = dyn_cast<ExtractValueInst>(Val: U)) {
438 if (EVI->getIndices()[0] == 1)
439 EVI->replaceAllUsesWith(V: ConstantInt::getFalse(Context&: WO->getContext()));
440 else {
441 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
442 EVI->replaceAllUsesWith(V: NewResult);
443 NewResult->setDebugLoc(EVI->getDebugLoc());
444 }
445 ToDelete.push_back(Elt: EVI);
446 }
447 }
448
449 for (auto *EVI : ToDelete)
450 EVI->eraseFromParent();
451
452 if (WO->use_empty())
453 WO->eraseFromParent();
454
455 Changed = true;
456 return true;
457}
458
459bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
460 const SCEV *LHS = SE->getSCEV(V: SI->getLHS());
461 const SCEV *RHS = SE->getSCEV(V: SI->getRHS());
462 if (!SE->willNotOverflow(BinOp: SI->getBinaryOp(), Signed: SI->isSigned(), LHS, RHS))
463 return false;
464
465 BinaryOperator *BO = BinaryOperator::Create(
466 Op: SI->getBinaryOp(), S1: SI->getLHS(), S2: SI->getRHS(), Name: SI->getName(), InsertBefore: SI->getIterator());
467 if (SI->isSigned())
468 BO->setHasNoSignedWrap();
469 else
470 BO->setHasNoUnsignedWrap();
471
472 SI->replaceAllUsesWith(V: BO);
473 BO->setDebugLoc(SI->getDebugLoc());
474 DeadInsts.emplace_back(Args&: SI);
475 Changed = true;
476 return true;
477}
478
479bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
480 // It is always legal to replace
481 // icmp <pred> i32 trunc(iv), n
482 // with
483 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
484 // Or with
485 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
486 // Or with either of these if pred is an equality predicate.
487 //
488 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
489 // every comparison which uses trunc, it means that we can replace each of
490 // them with comparison of iv against sext/zext(n). We no longer need trunc
491 // after that.
492 //
493 // TODO: Should we do this if we can widen *some* comparisons, but not all
494 // of them? Sometimes it is enough to enable other optimizations, but the
495 // trunc instruction will stay in the loop.
496 Value *IV = TI->getOperand(i_nocapture: 0);
497 Type *IVTy = IV->getType();
498 const SCEV *IVSCEV = SE->getSCEV(V: IV);
499 const SCEV *TISCEV = SE->getSCEV(V: TI);
500
501 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
502 // get rid of trunc
503 bool DoesSExtCollapse = false;
504 bool DoesZExtCollapse = false;
505 if (IVSCEV == SE->getSignExtendExpr(Op: TISCEV, Ty: IVTy))
506 DoesSExtCollapse = true;
507 if (IVSCEV == SE->getZeroExtendExpr(Op: TISCEV, Ty: IVTy))
508 DoesZExtCollapse = true;
509
510 // If neither sext nor zext does collapse, it is not profitable to do any
511 // transform. Bail.
512 if (!DoesSExtCollapse && !DoesZExtCollapse)
513 return false;
514
515 // Collect users of the trunc that look like comparisons against invariants.
516 // Bail if we find something different.
517 SmallVector<ICmpInst *, 4> ICmpUsers;
518 for (auto *U : TI->users()) {
519 // We don't care about users in unreachable blocks.
520 if (isa<Instruction>(Val: U) &&
521 !DT->isReachableFromEntry(A: cast<Instruction>(Val: U)->getParent()))
522 continue;
523 ICmpInst *ICI = dyn_cast<ICmpInst>(Val: U);
524 if (!ICI) return false;
525 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
526 if (!(ICI->getOperand(i_nocapture: 0) == TI && L->isLoopInvariant(V: ICI->getOperand(i_nocapture: 1))) &&
527 !(ICI->getOperand(i_nocapture: 1) == TI && L->isLoopInvariant(V: ICI->getOperand(i_nocapture: 0))))
528 return false;
529 // If we cannot get rid of trunc, bail.
530 if (ICI->isSigned() && !DoesSExtCollapse)
531 return false;
532 if (ICI->isUnsigned() && !DoesZExtCollapse)
533 return false;
534 // For equality, either signed or unsigned works.
535 ICmpUsers.push_back(Elt: ICI);
536 }
537
538 auto CanUseZExt = [&](ICmpInst *ICI) {
539 // Unsigned comparison can be widened as unsigned.
540 if (ICI->isUnsigned())
541 return true;
542 // Is it profitable to do zext?
543 if (!DoesZExtCollapse)
544 return false;
545 // For equality, we can safely zext both parts.
546 if (ICI->isEquality())
547 return true;
548 // Otherwise we can only use zext when comparing two non-negative or two
549 // negative values. But in practice, we will never pass DoesZExtCollapse
550 // check for a negative value, because zext(trunc(x)) is non-negative. So
551 // it only make sense to check for non-negativity here.
552 const SCEV *SCEVOP1 = SE->getSCEV(V: ICI->getOperand(i_nocapture: 0));
553 const SCEV *SCEVOP2 = SE->getSCEV(V: ICI->getOperand(i_nocapture: 1));
554 return SE->isKnownNonNegative(S: SCEVOP1) && SE->isKnownNonNegative(S: SCEVOP2);
555 };
556 // Replace all comparisons against trunc with comparisons against IV.
557 for (auto *ICI : ICmpUsers) {
558 bool IsSwapped = L->isLoopInvariant(V: ICI->getOperand(i_nocapture: 0));
559 auto *Op1 = IsSwapped ? ICI->getOperand(i_nocapture: 0) : ICI->getOperand(i_nocapture: 1);
560 IRBuilder<> Builder(ICI);
561 Value *Ext = nullptr;
562 // For signed/unsigned predicate, replace the old comparison with comparison
563 // of immediate IV against sext/zext of the invariant argument. If we can
564 // use either sext or zext (i.e. we are dealing with equality predicate),
565 // then prefer zext as a more canonical form.
566 // TODO: If we see a signed comparison which can be turned into unsigned,
567 // we can do it here for canonicalization purposes.
568 ICmpInst::Predicate Pred = ICI->getPredicate();
569 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(pred: Pred);
570 if (CanUseZExt(ICI)) {
571 assert(DoesZExtCollapse && "Unprofitable zext?");
572 Ext = Builder.CreateZExt(V: Op1, DestTy: IVTy, Name: "zext");
573 Pred = ICmpInst::getUnsignedPredicate(Pred);
574 } else {
575 assert(DoesSExtCollapse && "Unprofitable sext?");
576 Ext = Builder.CreateSExt(V: Op1, DestTy: IVTy, Name: "sext");
577 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
578 }
579 bool Changed;
580 L->makeLoopInvariant(V: Ext, Changed);
581 (void)Changed;
582 auto *NewCmp = Builder.CreateICmp(P: Pred, LHS: IV, RHS: Ext);
583 ICI->replaceAllUsesWith(V: NewCmp);
584 DeadInsts.emplace_back(Args&: ICI);
585 }
586
587 // Trunc no longer needed.
588 TI->replaceAllUsesWith(V: PoisonValue::get(T: TI->getType()));
589 DeadInsts.emplace_back(Args&: TI);
590 return true;
591}
592
593/// Eliminate an operation that consumes a simple IV and has no observable
594/// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
595/// but UseInst may not be.
596bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
597 Instruction *IVOperand) {
598 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: UseInst)) {
599 eliminateIVComparison(ICmp, IVOperand);
600 return true;
601 }
602 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(Val: UseInst)) {
603 bool IsSRem = Bin->getOpcode() == Instruction::SRem;
604 if (IsSRem || Bin->getOpcode() == Instruction::URem) {
605 simplifyIVRemainder(Rem: Bin, IVOperand, IsSigned: IsSRem);
606 return true;
607 }
608
609 if (Bin->getOpcode() == Instruction::SDiv)
610 return eliminateSDiv(SDiv: Bin);
611 }
612
613 if (auto *WO = dyn_cast<WithOverflowInst>(Val: UseInst))
614 if (eliminateOverflowIntrinsic(WO))
615 return true;
616
617 if (auto *SI = dyn_cast<SaturatingInst>(Val: UseInst))
618 if (eliminateSaturatingIntrinsic(SI))
619 return true;
620
621 if (auto *TI = dyn_cast<TruncInst>(Val: UseInst))
622 if (eliminateTrunc(TI))
623 return true;
624
625 if (eliminateIdentitySCEV(UseInst, IVOperand))
626 return true;
627
628 return false;
629}
630
631static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
632 if (auto *BB = L->getLoopPreheader())
633 return BB->getTerminator();
634
635 return Hint;
636}
637
638/// Replace the UseInst with a loop invariant expression if it is safe.
639bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
640 if (!SE->isSCEVable(Ty: I->getType()))
641 return false;
642
643 // Get the symbolic expression for this instruction.
644 const SCEV *S = SE->getSCEV(V: I);
645
646 if (!SE->isLoopInvariant(S, L))
647 return false;
648
649 // Do not generate something ridiculous even if S is loop invariant.
650 if (Rewriter.isHighCostExpansion(Exprs: S, L, Budget: SCEVCheapExpansionBudget, TTI, At: I))
651 return false;
652
653 auto *IP = GetLoopInvariantInsertPosition(L, Hint: I);
654
655 if (!Rewriter.isSafeToExpandAt(S, InsertionPoint: IP)) {
656 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
657 << " with non-speculable loop invariant: " << *S << '\n');
658 return false;
659 }
660
661 auto *Invariant = Rewriter.expandCodeFor(SH: S, Ty: I->getType(), I: IP);
662 bool NeedToEmitLCSSAPhis = false;
663 if (!LI->replacementPreservesLCSSAForm(From: I, To: Invariant))
664 NeedToEmitLCSSAPhis = true;
665
666 I->replaceAllUsesWith(V: Invariant);
667 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
668 << " with loop invariant: " << *S << '\n');
669
670 if (NeedToEmitLCSSAPhis) {
671 SmallVector<Instruction *, 1> NeedsLCSSAPhis;
672 NeedsLCSSAPhis.push_back(Elt: cast<Instruction>(Val: Invariant));
673 formLCSSAForInstructions(Worklist&: NeedsLCSSAPhis, DT: *DT, LI: *LI, SE);
674 LLVM_DEBUG(dbgs() << " INDVARS: Replacement breaks LCSSA form"
675 << " inserting LCSSA Phis" << '\n');
676 }
677 ++NumFoldedUser;
678 Changed = true;
679 DeadInsts.emplace_back(Args&: I);
680 return true;
681}
682
683/// Eliminate redundant type cast between integer and float.
684bool SimplifyIndvar::replaceFloatIVWithIntegerIV(Instruction *UseInst) {
685 if (UseInst->getOpcode() != CastInst::SIToFP &&
686 UseInst->getOpcode() != CastInst::UIToFP)
687 return false;
688
689 Instruction *IVOperand = cast<Instruction>(Val: UseInst->getOperand(i: 0));
690 // Get the symbolic expression for this instruction.
691 const SCEV *IV = SE->getSCEV(V: IVOperand);
692 int MaskBits;
693 if (UseInst->getOpcode() == CastInst::SIToFP)
694 MaskBits = (int)SE->getSignedRange(S: IV).getMinSignedBits();
695 else
696 MaskBits = (int)SE->getUnsignedRange(S: IV).getActiveBits();
697 int DestNumSigBits = UseInst->getType()->getFPMantissaWidth();
698 if (MaskBits <= DestNumSigBits) {
699 for (User *U : UseInst->users()) {
700 // Match for fptosi/fptoui of sitofp and with same type.
701 auto *CI = dyn_cast<CastInst>(Val: U);
702 if (!CI)
703 continue;
704
705 CastInst::CastOps Opcode = CI->getOpcode();
706 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
707 continue;
708
709 Value *Conv = nullptr;
710 if (IVOperand->getType() != CI->getType()) {
711 IRBuilder<> Builder(CI);
712 StringRef Name = IVOperand->getName();
713 // To match InstCombine logic, we only need sext if both fptosi and
714 // sitofp are used. If one of them is unsigned, then we can use zext.
715 if (SE->getTypeSizeInBits(Ty: IVOperand->getType()) >
716 SE->getTypeSizeInBits(Ty: CI->getType())) {
717 Conv = Builder.CreateTrunc(V: IVOperand, DestTy: CI->getType(), Name: Name + ".trunc");
718 } else if (Opcode == CastInst::FPToUI ||
719 UseInst->getOpcode() == CastInst::UIToFP) {
720 Conv = Builder.CreateZExt(V: IVOperand, DestTy: CI->getType(), Name: Name + ".zext");
721 } else {
722 Conv = Builder.CreateSExt(V: IVOperand, DestTy: CI->getType(), Name: Name + ".sext");
723 }
724 } else
725 Conv = IVOperand;
726
727 CI->replaceAllUsesWith(V: Conv);
728 DeadInsts.push_back(Elt: CI);
729 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *CI
730 << " with: " << *Conv << '\n');
731
732 ++NumFoldedUser;
733 Changed = true;
734 }
735 }
736
737 return Changed;
738}
739
740/// Eliminate any operation that SCEV can prove is an identity function.
741bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
742 Instruction *IVOperand) {
743 if (!SE->isSCEVable(Ty: UseInst->getType()) ||
744 UseInst->getType() != IVOperand->getType())
745 return false;
746
747 const SCEV *UseSCEV = SE->getSCEV(V: UseInst);
748 if (UseSCEV != SE->getSCEV(V: IVOperand))
749 return false;
750
751 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
752 // dominator tree, even if X is an operand to Y. For instance, in
753 //
754 // %iv = phi i32 {0,+,1}
755 // br %cond, label %left, label %merge
756 //
757 // left:
758 // %X = add i32 %iv, 0
759 // br label %merge
760 //
761 // merge:
762 // %M = phi (%X, %iv)
763 //
764 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
765 // %M.replaceAllUsesWith(%X) would be incorrect.
766
767 if (isa<PHINode>(Val: UseInst))
768 // If UseInst is not a PHI node then we know that IVOperand dominates
769 // UseInst directly from the legality of SSA.
770 if (!DT || !DT->dominates(Def: IVOperand, User: UseInst))
771 return false;
772
773 if (!LI->replacementPreservesLCSSAForm(From: UseInst, To: IVOperand))
774 return false;
775
776 // Make sure the operand is not more poisonous than the instruction.
777 if (!impliesPoison(ValAssumedPoison: IVOperand, V: UseInst)) {
778 SmallVector<Instruction *> DropPoisonGeneratingInsts;
779 if (!SE->canReuseInstruction(S: UseSCEV, I: IVOperand, DropPoisonGeneratingInsts))
780 return false;
781
782 for (Instruction *I : DropPoisonGeneratingInsts)
783 I->dropPoisonGeneratingAnnotations();
784 }
785
786 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
787
788 SE->forgetValue(V: UseInst);
789 UseInst->replaceAllUsesWith(V: IVOperand);
790 ++NumElimIdentity;
791 Changed = true;
792 DeadInsts.emplace_back(Args&: UseInst);
793 return true;
794}
795
796bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,
797 Instruction *IVOperand) {
798 return (isa<OverflowingBinaryOperator>(Val: BO) &&
799 strengthenOverflowingOperation(OBO: BO, IVOperand)) ||
800 (isa<ShlOperator>(Val: BO) && strengthenRightShift(BO, IVOperand));
801}
802
803/// Annotate BO with nsw / nuw if it provably does not signed-overflow /
804/// unsigned-overflow. Returns true if anything changed, false otherwise.
805bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
806 Instruction *IVOperand) {
807 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
808 OBO: cast<OverflowingBinaryOperator>(Val: BO));
809
810 if (!Flags)
811 return false;
812
813 BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(Flags: *Flags, Mask: SCEV::FlagNUW) ==
814 SCEV::FlagNUW);
815 BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(Flags: *Flags, Mask: SCEV::FlagNSW) ==
816 SCEV::FlagNSW);
817
818 // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap
819 // flags on addrecs while performing zero/sign extensions. We could call
820 // forgetValue() here to make sure those flags also propagate to any other
821 // SCEV expressions based on the addrec. However, this can have pathological
822 // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.
823 return true;
824}
825
826/// Annotate the Shr in (X << IVOperand) >> C as exact using the
827/// information from the IV's range. Returns true if anything changed, false
828/// otherwise.
829bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
830 Instruction *IVOperand) {
831 if (BO->getOpcode() == Instruction::Shl) {
832 bool Changed = false;
833 ConstantRange IVRange = SE->getUnsignedRange(S: SE->getSCEV(V: IVOperand));
834 for (auto *U : BO->users()) {
835 const APInt *C;
836 if (match(V: U,
837 P: m_AShr(L: m_Shl(L: m_Value(), R: m_Specific(V: IVOperand)), R: m_APInt(Res&: C))) ||
838 match(V: U,
839 P: m_LShr(L: m_Shl(L: m_Value(), R: m_Specific(V: IVOperand)), R: m_APInt(Res&: C)))) {
840 BinaryOperator *Shr = cast<BinaryOperator>(Val: U);
841 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(RHS: *C)) {
842 Shr->setIsExact(true);
843 Changed = true;
844 }
845 }
846 }
847 return Changed;
848 }
849
850 return false;
851}
852
853/// Add all uses of Def to the current IV's worklist.
854void SimplifyIndvar::pushIVUsers(
855 Instruction *Def, SmallPtrSet<Instruction *, 16> &Simplified,
856 SmallVectorImpl<std::pair<Instruction *, Instruction *>> &SimpleIVUsers) {
857 for (User *U : Def->users()) {
858 Instruction *UI = cast<Instruction>(Val: U);
859
860 // Avoid infinite or exponential worklist processing.
861 // Also ensure unique worklist users.
862 // If Def is a LoopPhi, it may not be in the Simplified set, so check for
863 // self edges first.
864 if (UI == Def)
865 continue;
866
867 // Only change the current Loop, do not change the other parts (e.g. other
868 // Loops).
869 if (!L->contains(Inst: UI))
870 continue;
871
872 // Do not push the same instruction more than once.
873 if (!Simplified.insert(Ptr: UI).second)
874 continue;
875
876 SimpleIVUsers.push_back(Elt: std::make_pair(x&: UI, y&: Def));
877 }
878}
879
880/// Return true if this instruction generates a simple SCEV
881/// expression in terms of that IV.
882///
883/// This is similar to IVUsers' isInteresting() but processes each instruction
884/// non-recursively when the operand is already known to be a simpleIVUser.
885///
886static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
887 if (!SE->isSCEVable(Ty: I->getType()))
888 return false;
889
890 // Get the symbolic expression for this instruction.
891 const SCEV *S = SE->getSCEV(V: I);
892
893 // Only consider affine recurrences.
894 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: S);
895 if (AR && AR->getLoop() == L)
896 return true;
897
898 return false;
899}
900
901/// Iteratively perform simplification on a worklist of users
902/// of the specified induction variable. Each successive simplification may push
903/// more users which may themselves be candidates for simplification.
904///
905/// This algorithm does not require IVUsers analysis. Instead, it simplifies
906/// instructions in-place during analysis. Rather than rewriting induction
907/// variables bottom-up from their users, it transforms a chain of IVUsers
908/// top-down, updating the IR only when it encounters a clear optimization
909/// opportunity.
910///
911/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
912///
913void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
914 if (!SE->isSCEVable(Ty: CurrIV->getType()))
915 return;
916
917 // Instructions processed by SimplifyIndvar for CurrIV.
918 SmallPtrSet<Instruction*,16> Simplified;
919
920 // Use-def pairs if IV users waiting to be processed for CurrIV.
921 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
922
923 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
924 // called multiple times for the same LoopPhi. This is the proper thing to
925 // do for loop header phis that use each other.
926 pushIVUsers(Def: CurrIV, Simplified, SimpleIVUsers);
927
928 while (!SimpleIVUsers.empty()) {
929 std::pair<Instruction*, Instruction*> UseOper =
930 SimpleIVUsers.pop_back_val();
931 Instruction *UseInst = UseOper.first;
932
933 // If a user of the IndVar is trivially dead, we prefer just to mark it dead
934 // rather than try to do some complex analysis or transformation (such as
935 // widening) basing on it.
936 // TODO: Propagate TLI and pass it here to handle more cases.
937 if (isInstructionTriviallyDead(I: UseInst, /* TLI */ nullptr)) {
938 DeadInsts.emplace_back(Args&: UseInst);
939 continue;
940 }
941
942 // Bypass back edges to avoid extra work.
943 if (UseInst == CurrIV) continue;
944
945 // Try to replace UseInst with a loop invariant before any other
946 // simplifications.
947 if (replaceIVUserWithLoopInvariant(I: UseInst))
948 continue;
949
950 // Go further for the bitcast 'prtoint ptr to i64' or if the cast is done
951 // by truncation
952 if ((isa<PtrToIntInst>(Val: UseInst)) || (isa<TruncInst>(Val: UseInst)))
953 for (Use &U : UseInst->uses()) {
954 Instruction *User = cast<Instruction>(Val: U.getUser());
955 if (replaceIVUserWithLoopInvariant(I: User))
956 break; // done replacing
957 }
958
959 Instruction *IVOperand = UseOper.second;
960 for (unsigned N = 0; IVOperand; ++N) {
961 assert(N <= Simplified.size() && "runaway iteration");
962 (void) N;
963
964 Value *NewOper = foldIVUser(UseInst, IVOperand);
965 if (!NewOper)
966 break; // done folding
967 IVOperand = dyn_cast<Instruction>(Val: NewOper);
968 }
969 if (!IVOperand)
970 continue;
971
972 if (eliminateIVUser(UseInst, IVOperand)) {
973 pushIVUsers(Def: IVOperand, Simplified, SimpleIVUsers);
974 continue;
975 }
976
977 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: UseInst)) {
978 if (strengthenBinaryOp(BO, IVOperand)) {
979 // re-queue uses of the now modified binary operator and fall
980 // through to the checks that remain.
981 pushIVUsers(Def: IVOperand, Simplified, SimpleIVUsers);
982 }
983 }
984
985 // Try to use integer induction for FPToSI of float induction directly.
986 if (replaceFloatIVWithIntegerIV(UseInst)) {
987 // Re-queue the potentially new direct uses of IVOperand.
988 pushIVUsers(Def: IVOperand, Simplified, SimpleIVUsers);
989 continue;
990 }
991
992 CastInst *Cast = dyn_cast<CastInst>(Val: UseInst);
993 if (V && Cast) {
994 V->visitCast(Cast);
995 continue;
996 }
997 if (isSimpleIVUser(I: UseInst, L, SE)) {
998 pushIVUsers(Def: UseInst, Simplified, SimpleIVUsers);
999 }
1000 }
1001}
1002
1003namespace llvm {
1004
1005void IVVisitor::anchor() { }
1006
1007/// Simplify instructions that use this induction variable
1008/// by using ScalarEvolution to analyze the IV's recurrence.
1009/// Returns a pair where the first entry indicates that the function makes
1010/// changes and the second entry indicates that it introduced new opportunities
1011/// for loop unswitching.
1012std::pair<bool, bool> simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE,
1013 DominatorTree *DT, LoopInfo *LI,
1014 const TargetTransformInfo *TTI,
1015 SmallVectorImpl<WeakTrackingVH> &Dead,
1016 SCEVExpander &Rewriter, IVVisitor *V) {
1017 SimplifyIndvar SIV(LI->getLoopFor(BB: CurrIV->getParent()), SE, DT, LI, TTI,
1018 Rewriter, Dead);
1019 SIV.simplifyUsers(CurrIV, V);
1020 return {SIV.hasChanged(), SIV.runUnswitching()};
1021}
1022
1023/// Simplify users of induction variables within this
1024/// loop. This does not actually change or add IVs.
1025bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
1026 LoopInfo *LI, const TargetTransformInfo *TTI,
1027 SmallVectorImpl<WeakTrackingVH> &Dead) {
1028 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
1029#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1030 Rewriter.setDebugType(DEBUG_TYPE);
1031#endif
1032 bool Changed = false;
1033 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(Val: I); ++I) {
1034 const auto &[C, _] =
1035 simplifyUsersOfIV(CurrIV: cast<PHINode>(Val&: I), SE, DT, LI, TTI, Dead, Rewriter);
1036 Changed |= C;
1037 }
1038 return Changed;
1039}
1040
1041} // namespace llvm
1042
1043namespace {
1044//===----------------------------------------------------------------------===//
1045// Widen Induction Variables - Extend the width of an IV to cover its
1046// widest uses.
1047//===----------------------------------------------------------------------===//
1048
1049class WidenIV {
1050 // Parameters
1051 PHINode *OrigPhi;
1052 Type *WideType;
1053
1054 // Context
1055 LoopInfo *LI;
1056 Loop *L;
1057 ScalarEvolution *SE;
1058 DominatorTree *DT;
1059
1060 // Does the module have any calls to the llvm.experimental.guard intrinsic
1061 // at all? If not we can avoid scanning instructions looking for guards.
1062 bool HasGuards;
1063
1064 bool UsePostIncrementRanges;
1065
1066 // Statistics
1067 unsigned NumElimExt = 0;
1068 unsigned NumWidened = 0;
1069
1070 // Result
1071 PHINode *WidePhi = nullptr;
1072 Instruction *WideInc = nullptr;
1073 const SCEV *WideIncExpr = nullptr;
1074 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
1075
1076 SmallPtrSet<Instruction *,16> Widened;
1077
1078 enum class ExtendKind { Zero, Sign, Unknown };
1079
1080 // A map tracking the kind of extension used to widen each narrow IV
1081 // and narrow IV user.
1082 // Key: pointer to a narrow IV or IV user.
1083 // Value: the kind of extension used to widen this Instruction.
1084 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
1085
1086 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
1087
1088 // A map with control-dependent ranges for post increment IV uses. The key is
1089 // a pair of IV def and a use of this def denoting the context. The value is
1090 // a ConstantRange representing possible values of the def at the given
1091 // context.
1092 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
1093
1094 std::optional<ConstantRange> getPostIncRangeInfo(Value *Def,
1095 Instruction *UseI) {
1096 DefUserPair Key(Def, UseI);
1097 auto It = PostIncRangeInfos.find(Val: Key);
1098 return It == PostIncRangeInfos.end()
1099 ? std::optional<ConstantRange>(std::nullopt)
1100 : std::optional<ConstantRange>(It->second);
1101 }
1102
1103 void calculatePostIncRanges(PHINode *OrigPhi);
1104 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
1105
1106 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
1107 DefUserPair Key(Def, UseI);
1108 auto [It, Inserted] = PostIncRangeInfos.try_emplace(Key, Args&: R);
1109 if (!Inserted)
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 non-negative (and thus its sign extension is
1609 // equal to its zero extension). For instance, let's say we're zero
1610 // extending %narrow for the following use
1611 //
1612 // icmp slt i32 %narrow, %val ... (A)
1613 //
1614 // and %narrow is always non-negative. 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 bool CmpPreferredSign = Cmp->hasSameSign() ? IsSigned : Cmp->isSigned();
1620 if (!DU.NeverNegative && IsSigned != CmpPreferredSign)
1621 return false;
1622
1623 Value *Op = Cmp->getOperand(i_nocapture: Cmp->getOperand(i_nocapture: 0) == DU.NarrowDef ? 1 : 0);
1624 unsigned CastWidth = SE->getTypeSizeInBits(Ty: Op->getType());
1625 unsigned IVWidth = SE->getTypeSizeInBits(Ty: WideType);
1626 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1627
1628 // Widen the compare instruction.
1629 DU.NarrowUse->replaceUsesOfWith(From: DU.NarrowDef, To: DU.WideDef);
1630
1631 // Widen the other operand of the compare, if necessary.
1632 if (CastWidth < IVWidth) {
1633 // If the narrow IV is always non-negative and the other operand is sext,
1634 // widen using sext so we can combine them. This works for all non-signed
1635 // comparison predicates.
1636 if (DU.NeverNegative && isa<SExtInst>(Val: Op) && !Cmp->isSigned())
1637 CmpPreferredSign = true;
1638
1639 Value *ExtOp = createExtendInst(NarrowOper: Op, WideType, IsSigned: CmpPreferredSign, Use: Cmp);
1640 DU.NarrowUse->replaceUsesOfWith(From: Op, To: ExtOp);
1641 }
1642 return true;
1643}
1644
1645// The widenIVUse avoids generating trunc by evaluating the use as AddRec, this
1646// will not work when:
1647// 1) SCEV traces back to an instruction inside the loop that SCEV can not
1648// expand, eg. add %indvar, (load %addr)
1649// 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant
1650// While SCEV fails to avoid trunc, we can still try to use instruction
1651// combining approach to prove trunc is not required. This can be further
1652// extended with other instruction combining checks, but for now we handle the
1653// following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")
1654//
1655// Src:
1656// %c = sub nsw %b, %indvar
1657// %d = sext %c to i64
1658// Dst:
1659// %indvar.ext1 = sext %indvar to i64
1660// %m = sext %b to i64
1661// %d = sub nsw i64 %m, %indvar.ext1
1662// Therefore, as long as the result of add/sub/mul is extended to wide type, no
1663// trunc is required regardless of how %b is generated. This pattern is common
1664// when calculating address in 64 bit architecture
1665bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1666 Instruction *NarrowUse = DU.NarrowUse;
1667 Instruction *NarrowDef = DU.NarrowDef;
1668 Instruction *WideDef = DU.WideDef;
1669
1670 // Handle the common case of add<nsw/nuw>
1671 const unsigned OpCode = NarrowUse->getOpcode();
1672 // Only Add/Sub/Mul instructions are supported.
1673 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1674 OpCode != Instruction::Mul)
1675 return false;
1676
1677 // The operand that is not defined by NarrowDef of DU. Let's call it the
1678 // other operand.
1679 assert((NarrowUse->getOperand(0) == NarrowDef ||
1680 NarrowUse->getOperand(1) == NarrowDef) &&
1681 "bad DU");
1682
1683 const OverflowingBinaryOperator *OBO =
1684 cast<OverflowingBinaryOperator>(Val: NarrowUse);
1685 ExtendKind ExtKind = getExtendKind(I: NarrowDef);
1686 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap();
1687 bool CanZeroExtend = ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap();
1688 auto AnotherOpExtKind = ExtKind;
1689
1690 // Check that all uses are either:
1691 // - narrow def (in case of we are widening the IV increment);
1692 // - single-input LCSSA Phis;
1693 // - comparison of the chosen type;
1694 // - extend of the chosen type (raison d'etre).
1695 SmallVector<Instruction *, 4> ExtUsers;
1696 SmallVector<PHINode *, 4> LCSSAPhiUsers;
1697 SmallVector<ICmpInst *, 4> ICmpUsers;
1698 for (Use &U : NarrowUse->uses()) {
1699 Instruction *User = cast<Instruction>(Val: U.getUser());
1700 if (User == NarrowDef)
1701 continue;
1702 if (!L->contains(Inst: User)) {
1703 auto *LCSSAPhi = cast<PHINode>(Val: User);
1704 // Make sure there is only 1 input, so that we don't have to split
1705 // critical edges.
1706 if (LCSSAPhi->getNumOperands() != 1)
1707 return false;
1708 LCSSAPhiUsers.push_back(Elt: LCSSAPhi);
1709 continue;
1710 }
1711 if (auto *ICmp = dyn_cast<ICmpInst>(Val: User)) {
1712 auto Pred = ICmp->getPredicate();
1713 // We have 3 types of predicates: signed, unsigned and equality
1714 // predicates. For equality, it's legal to widen icmp for either sign and
1715 // zero extend. For sign extend, we can also do so for signed predicates,
1716 // likeweise for zero extend we can widen icmp for unsigned predicates.
1717 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(predicate: Pred))
1718 return false;
1719 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(predicate: Pred))
1720 return false;
1721 ICmpUsers.push_back(Elt: ICmp);
1722 continue;
1723 }
1724 if (ExtKind == ExtendKind::Sign)
1725 User = dyn_cast<SExtInst>(Val: User);
1726 else
1727 User = dyn_cast<ZExtInst>(Val: User);
1728 if (!User || User->getType() != WideType)
1729 return false;
1730 ExtUsers.push_back(Elt: User);
1731 }
1732 if (ExtUsers.empty()) {
1733 DeadInsts.emplace_back(Args&: NarrowUse);
1734 return true;
1735 }
1736
1737 // We'll prove some facts that should be true in the context of ext users. If
1738 // there is no users, we are done now. If there are some, pick their common
1739 // dominator as context.
1740 const Instruction *CtxI = findCommonDominator(Instructions: ExtUsers, DT&: *DT);
1741
1742 if (!CanSignExtend && !CanZeroExtend) {
1743 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
1744 // will most likely not see it. Let's try to prove it.
1745 if (OpCode != Instruction::Add)
1746 return false;
1747 if (ExtKind != ExtendKind::Zero)
1748 return false;
1749 const SCEV *LHS = SE->getSCEV(V: OBO->getOperand(i_nocapture: 0));
1750 const SCEV *RHS = SE->getSCEV(V: OBO->getOperand(i_nocapture: 1));
1751 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
1752 if (NarrowUse->getOperand(i: 0) != NarrowDef)
1753 return false;
1754 // We cannot use a different extend kind for the same operand.
1755 if (NarrowUse->getOperand(i: 1) == NarrowDef)
1756 return false;
1757 if (!SE->isKnownNegative(S: RHS))
1758 return false;
1759 bool ProvedSubNUW = SE->isKnownPredicateAt(Pred: ICmpInst::ICMP_UGE, LHS,
1760 RHS: SE->getNegativeSCEV(V: RHS), CtxI);
1761 if (!ProvedSubNUW)
1762 return false;
1763 // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as
1764 // neg(zext(neg(op))), which is basically sext(op).
1765 AnotherOpExtKind = ExtendKind::Sign;
1766 }
1767
1768 // Verifying that Defining operand is an AddRec
1769 const SCEV *Op1 = SE->getSCEV(V: WideDef);
1770 const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Val: Op1);
1771 if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1772 return false;
1773
1774 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1775
1776 // Generating a widening use instruction.
1777 Value *LHS =
1778 (NarrowUse->getOperand(i: 0) == NarrowDef)
1779 ? WideDef
1780 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 0), WideType,
1781 IsSigned: AnotherOpExtKind == ExtendKind::Sign, Use: NarrowUse);
1782 Value *RHS =
1783 (NarrowUse->getOperand(i: 1) == NarrowDef)
1784 ? WideDef
1785 : createExtendInst(NarrowOper: NarrowUse->getOperand(i: 1), WideType,
1786 IsSigned: AnotherOpExtKind == ExtendKind::Sign, Use: NarrowUse);
1787
1788 auto *NarrowBO = cast<BinaryOperator>(Val: NarrowUse);
1789 auto *WideBO = BinaryOperator::Create(Op: NarrowBO->getOpcode(), S1: LHS, S2: RHS,
1790 Name: NarrowBO->getName());
1791 IRBuilder<> Builder(NarrowUse);
1792 Builder.Insert(I: WideBO);
1793 WideBO->copyIRFlags(V: NarrowBO);
1794 ExtendKindMap[NarrowUse] = ExtKind;
1795
1796 for (Instruction *User : ExtUsers) {
1797 assert(User->getType() == WideType && "Checked before!");
1798 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1799 << *WideBO << "\n");
1800 ++NumElimExt;
1801 User->replaceAllUsesWith(V: WideBO);
1802 DeadInsts.emplace_back(Args&: User);
1803 }
1804
1805 for (PHINode *User : LCSSAPhiUsers) {
1806 assert(User->getNumOperands() == 1 && "Checked before!");
1807 Builder.SetInsertPoint(User);
1808 auto *WidePN =
1809 Builder.CreatePHI(Ty: WideBO->getType(), NumReservedValues: 1, Name: User->getName() + ".wide");
1810 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
1811 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
1812 "Not a LCSSA Phi?");
1813 WidePN->addIncoming(V: WideBO, BB: LoopExitingBlock);
1814 Builder.SetInsertPoint(TheBB: User->getParent(),
1815 IP: User->getParent()->getFirstInsertionPt());
1816 auto *TruncPN = Builder.CreateTrunc(V: WidePN, DestTy: User->getType());
1817 User->replaceAllUsesWith(V: TruncPN);
1818 DeadInsts.emplace_back(Args&: User);
1819 }
1820
1821 for (ICmpInst *User : ICmpUsers) {
1822 Builder.SetInsertPoint(User);
1823 auto ExtendedOp = [&](Value * V)->Value * {
1824 if (V == NarrowUse)
1825 return WideBO;
1826 if (ExtKind == ExtendKind::Zero)
1827 return Builder.CreateZExt(V, DestTy: WideBO->getType());
1828 else
1829 return Builder.CreateSExt(V, DestTy: WideBO->getType());
1830 };
1831 auto Pred = User->getPredicate();
1832 auto *LHS = ExtendedOp(User->getOperand(i_nocapture: 0));
1833 auto *RHS = ExtendedOp(User->getOperand(i_nocapture: 1));
1834 auto *WideCmp =
1835 Builder.CreateICmp(P: Pred, LHS, RHS, Name: User->getName() + ".wide");
1836 User->replaceAllUsesWith(V: WideCmp);
1837 DeadInsts.emplace_back(Args&: User);
1838 }
1839
1840 return true;
1841}
1842
1843/// Determine whether an individual user of the narrow IV can be widened. If so,
1844/// return the wide clone of the user.
1845Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,
1846 SCEVExpander &Rewriter, PHINode *OrigPhi,
1847 PHINode *WidePhi) {
1848 assert(ExtendKindMap.count(DU.NarrowDef) &&
1849 "Should already know the kind of extension used to widen NarrowDef");
1850
1851 // This narrow use can be widened by a sext if it's non-negative or its narrow
1852 // def was widened by a sext. Same for zext.
1853 bool CanWidenBySExt =
1854 DU.NeverNegative || getExtendKind(I: DU.NarrowDef) == ExtendKind::Sign;
1855 bool CanWidenByZExt =
1856 DU.NeverNegative || getExtendKind(I: DU.NarrowDef) == ExtendKind::Zero;
1857
1858 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1859 if (PHINode *UsePhi = dyn_cast<PHINode>(Val: DU.NarrowUse)) {
1860 if (LI->getLoopFor(BB: UsePhi->getParent()) != L) {
1861 // For LCSSA phis, sink the truncate outside the loop.
1862 // After SimplifyCFG most loop exit targets have a single predecessor.
1863 // Otherwise fall back to a truncate within the loop.
1864 if (UsePhi->getNumOperands() != 1)
1865 truncateIVUse(DU);
1866 else {
1867 // Widening the PHI requires us to insert a trunc. The logical place
1868 // for this trunc is in the same BB as the PHI. This is not possible if
1869 // the BB is terminated by a catchswitch.
1870 if (isa<CatchSwitchInst>(Val: UsePhi->getParent()->getTerminator()))
1871 return nullptr;
1872
1873 PHINode *WidePhi =
1874 PHINode::Create(Ty: DU.WideDef->getType(), NumReservedValues: 1, NameStr: UsePhi->getName() + ".wide",
1875 InsertBefore: UsePhi->getIterator());
1876 WidePhi->addIncoming(V: DU.WideDef, BB: UsePhi->getIncomingBlock(i: 0));
1877 BasicBlock *WidePhiBB = WidePhi->getParent();
1878 IRBuilder<> Builder(WidePhiBB, WidePhiBB->getFirstInsertionPt());
1879 Value *Trunc = Builder.CreateTrunc(V: WidePhi, DestTy: DU.NarrowDef->getType(), Name: "",
1880 IsNUW: CanWidenByZExt, IsNSW: CanWidenBySExt);
1881 UsePhi->replaceAllUsesWith(V: Trunc);
1882 DeadInsts.emplace_back(Args&: UsePhi);
1883 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1884 << *WidePhi << "\n");
1885 }
1886 return nullptr;
1887 }
1888 }
1889
1890 // Our raison d'etre! Eliminate sign and zero extension.
1891 if ((match(V: DU.NarrowUse, P: m_SExtLike(Op: m_Value())) && CanWidenBySExt) ||
1892 (isa<ZExtInst>(Val: DU.NarrowUse) && CanWidenByZExt)) {
1893 Value *NewDef = DU.WideDef;
1894 if (DU.NarrowUse->getType() != WideType) {
1895 unsigned CastWidth = SE->getTypeSizeInBits(Ty: DU.NarrowUse->getType());
1896 unsigned IVWidth = SE->getTypeSizeInBits(Ty: WideType);
1897 if (CastWidth < IVWidth) {
1898 // The cast isn't as wide as the IV, so insert a Trunc.
1899 IRBuilder<> Builder(DU.NarrowUse);
1900 NewDef = Builder.CreateTrunc(V: DU.WideDef, DestTy: DU.NarrowUse->getType(), Name: "",
1901 IsNUW: CanWidenByZExt, IsNSW: CanWidenBySExt);
1902 }
1903 else {
1904 // A wider extend was hidden behind a narrower one. This may induce
1905 // another round of IV widening in which the intermediate IV becomes
1906 // dead. It should be very rare.
1907 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1908 << " not wide enough to subsume " << *DU.NarrowUse
1909 << "\n");
1910 DU.NarrowUse->replaceUsesOfWith(From: DU.NarrowDef, To: DU.WideDef);
1911 NewDef = DU.NarrowUse;
1912 }
1913 }
1914 if (NewDef != DU.NarrowUse) {
1915 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1916 << " replaced by " << *DU.WideDef << "\n");
1917 ++NumElimExt;
1918 DU.NarrowUse->replaceAllUsesWith(V: NewDef);
1919 DeadInsts.emplace_back(Args&: DU.NarrowUse);
1920 }
1921 // Now that the extend is gone, we want to expose it's uses for potential
1922 // further simplification. We don't need to directly inform SimplifyIVUsers
1923 // of the new users, because their parent IV will be processed later as a
1924 // new loop phi. If we preserved IVUsers analysis, we would also want to
1925 // push the uses of WideDef here.
1926
1927 // No further widening is needed. The deceased [sz]ext had done it for us.
1928 return nullptr;
1929 }
1930
1931 auto tryAddRecExpansion = [&]() -> Instruction* {
1932 // Does this user itself evaluate to a recurrence after widening?
1933 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1934 if (!WideAddRec.first)
1935 WideAddRec = getWideRecurrence(DU);
1936 assert((WideAddRec.first == nullptr) ==
1937 (WideAddRec.second == ExtendKind::Unknown));
1938 if (!WideAddRec.first)
1939 return nullptr;
1940
1941 auto CanUseWideInc = [&]() {
1942 if (!WideInc)
1943 return false;
1944 // Reuse the IV increment that SCEVExpander created. Recompute flags,
1945 // unless the flags for both increments agree and it is safe to use the
1946 // ones from the original inc. In that case, the new use of the wide
1947 // increment won't be more poisonous.
1948 bool NeedToRecomputeFlags =
1949 !SCEVExpander::canReuseFlagsFromOriginalIVInc(
1950 OrigPhi, WidePhi, OrigInc: DU.NarrowUse, WideInc) ||
1951 DU.NarrowUse->hasNoUnsignedWrap() != WideInc->hasNoUnsignedWrap() ||
1952 DU.NarrowUse->hasNoSignedWrap() != WideInc->hasNoSignedWrap();
1953 return WideAddRec.first == WideIncExpr &&
1954 Rewriter.hoistIVInc(IncV: WideInc, InsertPos: DU.NarrowUse, RecomputePoisonFlags: NeedToRecomputeFlags);
1955 };
1956
1957 Instruction *WideUse = nullptr;
1958 if (CanUseWideInc())
1959 WideUse = WideInc;
1960 else {
1961 WideUse = cloneIVUser(DU, WideAR: WideAddRec.first);
1962 if (!WideUse)
1963 return nullptr;
1964 }
1965 // Evaluation of WideAddRec ensured that the narrow expression could be
1966 // extended outside the loop without overflow. This suggests that the wide use
1967 // evaluates to the same expression as the extended narrow use, but doesn't
1968 // absolutely guarantee it. Hence the following failsafe check. In rare cases
1969 // where it fails, we simply throw away the newly created wide use.
1970 if (WideAddRec.first != SE->getSCEV(V: WideUse)) {
1971 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1972 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1973 << "\n");
1974 DeadInsts.emplace_back(Args&: WideUse);
1975 return nullptr;
1976 };
1977
1978 // if we reached this point then we are going to replace
1979 // DU.NarrowUse with WideUse. Reattach DbgValue then.
1980 replaceAllDbgUsesWith(From&: *DU.NarrowUse, To&: *WideUse, DomPoint&: *WideUse, DT&: *DT);
1981
1982 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1983 // Returning WideUse pushes it on the worklist.
1984 return WideUse;
1985 };
1986
1987 if (auto *I = tryAddRecExpansion())
1988 return I;
1989
1990 // If use is a loop condition, try to promote the condition instead of
1991 // truncating the IV first.
1992 if (widenLoopCompare(DU))
1993 return nullptr;
1994
1995 // We are here about to generate a truncate instruction that may hurt
1996 // performance because the scalar evolution expression computed earlier
1997 // in WideAddRec.first does not indicate a polynomial induction expression.
1998 // In that case, look at the operands of the use instruction to determine
1999 // if we can still widen the use instead of truncating its operand.
2000 if (widenWithVariantUse(DU))
2001 return nullptr;
2002
2003 // This user does not evaluate to a recurrence after widening, so don't
2004 // follow it. Instead insert a Trunc to kill off the original use,
2005 // eventually isolating the original narrow IV so it can be removed.
2006 truncateIVUse(DU);
2007 return nullptr;
2008}
2009
2010/// Add eligible users of NarrowDef to NarrowIVUsers.
2011void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
2012 const SCEV *NarrowSCEV = SE->getSCEV(V: NarrowDef);
2013 bool NonNegativeDef =
2014 SE->isKnownPredicate(Pred: ICmpInst::ICMP_SGE, LHS: NarrowSCEV,
2015 RHS: SE->getZero(Ty: NarrowSCEV->getType()));
2016 for (User *U : NarrowDef->users()) {
2017 Instruction *NarrowUser = cast<Instruction>(Val: U);
2018
2019 // Handle data flow merges and bizarre phi cycles.
2020 if (!Widened.insert(Ptr: NarrowUser).second)
2021 continue;
2022
2023 bool NonNegativeUse = false;
2024 if (!NonNegativeDef) {
2025 // We might have a control-dependent range information for this context.
2026 if (auto RangeInfo = getPostIncRangeInfo(Def: NarrowDef, UseI: NarrowUser))
2027 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
2028 }
2029
2030 NarrowIVUsers.emplace_back(Args&: NarrowDef, Args&: NarrowUser, Args&: WideDef,
2031 Args: NonNegativeDef || NonNegativeUse);
2032 }
2033}
2034
2035/// Process a single induction variable. First use the SCEVExpander to create a
2036/// wide induction variable that evaluates to the same recurrence as the
2037/// original narrow IV. Then use a worklist to forward traverse the narrow IV's
2038/// def-use chain. After widenIVUse has processed all interesting IV users, the
2039/// narrow IV will be isolated for removal by DeleteDeadPHIs.
2040///
2041/// It would be simpler to delete uses as they are processed, but we must avoid
2042/// invalidating SCEV expressions.
2043PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
2044 // Is this phi an induction variable?
2045 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: OrigPhi));
2046 if (!AddRec)
2047 return nullptr;
2048
2049 // Widen the induction variable expression.
2050 const SCEV *WideIVExpr = getExtendKind(I: OrigPhi) == ExtendKind::Sign
2051 ? SE->getSignExtendExpr(Op: AddRec, Ty: WideType)
2052 : SE->getZeroExtendExpr(Op: AddRec, Ty: WideType);
2053
2054 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
2055 "Expect the new IV expression to preserve its type");
2056
2057 // Can the IV be extended outside the loop without overflow?
2058 AddRec = dyn_cast<SCEVAddRecExpr>(Val: WideIVExpr);
2059 if (!AddRec || AddRec->getLoop() != L)
2060 return nullptr;
2061
2062 // An AddRec must have loop-invariant operands. Since this AddRec is
2063 // materialized by a loop header phi, the expression cannot have any post-loop
2064 // operands, so they must dominate the loop header.
2065 assert(
2066 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
2067 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
2068 "Loop header phi recurrence inputs do not dominate the loop");
2069
2070 // Iterate over IV uses (including transitive ones) looking for IV increments
2071 // of the form 'add nsw %iv, <const>'. For each increment and each use of
2072 // the increment calculate control-dependent range information basing on
2073 // dominating conditions inside of the loop (e.g. a range check inside of the
2074 // loop). Calculated ranges are stored in PostIncRangeInfos map.
2075 //
2076 // Control-dependent range information is later used to prove that a narrow
2077 // definition is not negative (see pushNarrowIVUsers). It's difficult to do
2078 // this on demand because when pushNarrowIVUsers needs this information some
2079 // of the dominating conditions might be already widened.
2080 if (UsePostIncrementRanges)
2081 calculatePostIncRanges(OrigPhi);
2082
2083 // The rewriter provides a value for the desired IV expression. This may
2084 // either find an existing phi or materialize a new one. Either way, we
2085 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
2086 // of the phi-SCC dominates the loop entry.
2087 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
2088 Value *ExpandInst = Rewriter.expandCodeFor(SH: AddRec, Ty: WideType, I: InsertPt);
2089 // If the wide phi is not a phi node, for example a cast node, like bitcast,
2090 // inttoptr, ptrtoint, just skip for now.
2091 if (!(WidePhi = dyn_cast<PHINode>(Val: ExpandInst))) {
2092 // if the cast node is an inserted instruction without any user, we should
2093 // remove it to make sure the pass don't touch the function as we can not
2094 // wide the phi.
2095 if (ExpandInst->use_empty() &&
2096 Rewriter.isInsertedInstruction(I: cast<Instruction>(Val: ExpandInst)))
2097 DeadInsts.emplace_back(Args&: ExpandInst);
2098 return nullptr;
2099 }
2100
2101 // Remembering the WideIV increment generated by SCEVExpander allows
2102 // widenIVUse to reuse it when widening the narrow IV's increment. We don't
2103 // employ a general reuse mechanism because the call above is the only call to
2104 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
2105 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2106 WideInc =
2107 dyn_cast<Instruction>(Val: WidePhi->getIncomingValueForBlock(BB: LatchBlock));
2108 if (WideInc) {
2109 WideIncExpr = SE->getSCEV(V: WideInc);
2110 // Propagate the debug location associated with the original loop
2111 // increment to the new (widened) increment.
2112 auto *OrigInc =
2113 cast<Instruction>(Val: OrigPhi->getIncomingValueForBlock(BB: LatchBlock));
2114
2115 WideInc->setDebugLoc(OrigInc->getDebugLoc());
2116 // We are replacing a narrow IV increment with a wider IV increment. If
2117 // the original (narrow) increment did not wrap, the wider increment one
2118 // should not wrap either. Set the flags to be the union of both wide
2119 // increment and original increment; this ensures we preserve flags SCEV
2120 // could infer for the wider increment. Limit this only to cases where
2121 // both increments directly increment the corresponding PHI nodes and have
2122 // the same opcode. It is not safe to re-use the flags from the original
2123 // increment, if it is more complex and SCEV expansion may have yielded a
2124 // more simplified wider increment.
2125 if (SCEVExpander::canReuseFlagsFromOriginalIVInc(OrigPhi, WidePhi,
2126 OrigInc, WideInc) &&
2127 isa<OverflowingBinaryOperator>(Val: OrigInc) &&
2128 isa<OverflowingBinaryOperator>(Val: WideInc)) {
2129 WideInc->setHasNoUnsignedWrap(WideInc->hasNoUnsignedWrap() ||
2130 OrigInc->hasNoUnsignedWrap());
2131 WideInc->setHasNoSignedWrap(WideInc->hasNoSignedWrap() ||
2132 OrigInc->hasNoSignedWrap());
2133 }
2134 }
2135 }
2136
2137 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
2138 ++NumWidened;
2139
2140 // Traverse the def-use chain using a worklist starting at the original IV.
2141 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
2142
2143 Widened.insert(Ptr: OrigPhi);
2144 pushNarrowIVUsers(NarrowDef: OrigPhi, WideDef: WidePhi);
2145
2146 while (!NarrowIVUsers.empty()) {
2147 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
2148
2149 // Process a def-use edge. This may replace the use, so don't hold a
2150 // use_iterator across it.
2151 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);
2152
2153 // Follow all def-use edges from the previous narrow use.
2154 if (WideUse)
2155 pushNarrowIVUsers(NarrowDef: DU.NarrowUse, WideDef: WideUse);
2156
2157 // widenIVUse may have removed the def-use edge.
2158 if (DU.NarrowDef->use_empty())
2159 DeadInsts.emplace_back(Args&: DU.NarrowDef);
2160 }
2161
2162 // Attach any debug information to the new PHI.
2163 replaceAllDbgUsesWith(From&: *OrigPhi, To&: *WidePhi, DomPoint&: *WidePhi, DT&: *DT);
2164
2165 return WidePhi;
2166}
2167
2168/// Calculates control-dependent range for the given def at the given context
2169/// by looking at dominating conditions inside of the loop
2170void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
2171 Instruction *NarrowUser) {
2172 Value *NarrowDefLHS;
2173 const APInt *NarrowDefRHS;
2174 if (!match(V: NarrowDef, P: m_NSWAdd(L: m_Value(V&: NarrowDefLHS),
2175 R: m_APInt(Res&: NarrowDefRHS))) ||
2176 !NarrowDefRHS->isNonNegative())
2177 return;
2178
2179 auto UpdateRangeFromCondition = [&](Value *Condition, bool TrueDest) {
2180 CmpPredicate Pred;
2181 Value *CmpRHS;
2182 if (!match(V: Condition, P: m_ICmp(Pred, L: m_Specific(V: NarrowDefLHS),
2183 R: m_Value(V&: CmpRHS))))
2184 return;
2185
2186 CmpPredicate P = TrueDest ? Pred : ICmpInst::getInverseCmpPredicate(Pred);
2187
2188 auto CmpRHSRange = SE->getSignedRange(S: SE->getSCEV(V: CmpRHS));
2189 auto CmpConstrainedLHSRange =
2190 ConstantRange::makeAllowedICmpRegion(Pred: P, Other: CmpRHSRange);
2191 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2192 Other: *NarrowDefRHS, NoWrapKind: OverflowingBinaryOperator::NoSignedWrap);
2193
2194 updatePostIncRangeInfo(Def: NarrowDef, UseI: NarrowUser, R: NarrowDefRange);
2195 };
2196
2197 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
2198 if (!HasGuards)
2199 return;
2200
2201 for (Instruction &I : make_range(x: Ctx->getIterator().getReverse(),
2202 y: Ctx->getParent()->rend())) {
2203 Value *C = nullptr;
2204 if (match(V: &I, P: m_Intrinsic<Intrinsic::experimental_guard>(Op0: m_Value(V&: C))))
2205 UpdateRangeFromCondition(C, /*TrueDest=*/true);
2206 }
2207 };
2208
2209 UpdateRangeFromGuards(NarrowUser);
2210
2211 BasicBlock *NarrowUserBB = NarrowUser->getParent();
2212 // If NarrowUserBB is statically unreachable asking dominator queries may
2213 // yield surprising results. (e.g. the block may not have a dom tree node)
2214 if (!DT->isReachableFromEntry(A: NarrowUserBB))
2215 return;
2216
2217 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2218 L->contains(BB: DTB->getBlock());
2219 DTB = DTB->getIDom()) {
2220 auto *BB = DTB->getBlock();
2221 auto *TI = BB->getTerminator();
2222 UpdateRangeFromGuards(TI);
2223
2224 auto *BI = dyn_cast<BranchInst>(Val: TI);
2225 if (!BI || !BI->isConditional())
2226 continue;
2227
2228 auto *TrueSuccessor = BI->getSuccessor(i: 0);
2229 auto *FalseSuccessor = BI->getSuccessor(i: 1);
2230
2231 auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
2232 return BBE.isSingleEdge() &&
2233 DT->dominates(BBE, BB: NarrowUser->getParent());
2234 };
2235
2236 if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
2237 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
2238
2239 if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
2240 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
2241 }
2242}
2243
2244/// Calculates PostIncRangeInfos map for the given IV
2245void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
2246 SmallPtrSet<Instruction *, 16> Visited;
2247 SmallVector<Instruction *, 6> Worklist;
2248 Worklist.push_back(Elt: OrigPhi);
2249 Visited.insert(Ptr: OrigPhi);
2250
2251 while (!Worklist.empty()) {
2252 Instruction *NarrowDef = Worklist.pop_back_val();
2253
2254 for (Use &U : NarrowDef->uses()) {
2255 auto *NarrowUser = cast<Instruction>(Val: U.getUser());
2256
2257 // Don't go looking outside the current loop.
2258 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
2259 if (!NarrowUserLoop || !L->contains(L: NarrowUserLoop))
2260 continue;
2261
2262 if (!Visited.insert(Ptr: NarrowUser).second)
2263 continue;
2264
2265 Worklist.push_back(Elt: NarrowUser);
2266
2267 calculatePostIncRange(NarrowDef, NarrowUser);
2268 }
2269 }
2270}
2271
2272PHINode *llvm::createWideIV(const WideIVInfo &WI,
2273 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,
2274 DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,
2275 unsigned &NumElimExt, unsigned &NumWidened,
2276 bool HasGuards, bool UsePostIncrementRanges) {
2277 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);
2278 PHINode *WidePHI = Widener.createWideIV(Rewriter);
2279 NumElimExt = Widener.getNumElimExt();
2280 NumWidened = Widener.getNumWidened();
2281 return WidePHI;
2282}
2283