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