1//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
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 transformation analyzes and transforms the induction variables (and
10// computations derived from them) into simpler forms suitable for subsequent
11// analysis and transformation.
12//
13// If the trip count of a loop is computable, this pass also makes the following
14// changes:
15// 1. The exit condition for the loop is canonicalized to compare the
16// induction value against the exit value. This turns loops like:
17// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
18// 2. Any use outside of the loop of an expression derived from the indvar
19// is changed to compute the derived value outside of the loop, eliminating
20// the dependence on the exit value of the induction variable. If the only
21// purpose of the loop is to compute the exit value of some derived
22// expression, this transformation will make the loop dead.
23//
24//===----------------------------------------------------------------------===//
25
26#include "llvm/Transforms/Scalar/IndVarSimplify.h"
27#include "ScalarOptions.h"
28#include "llvm/ADT/APFloat.h"
29#include "llvm/ADT/ArrayRef.h"
30#include "llvm/ADT/STLExtras.h"
31#include "llvm/ADT/SmallPtrSet.h"
32#include "llvm/ADT/SmallVector.h"
33#include "llvm/ADT/Statistic.h"
34#include "llvm/ADT/iterator_range.h"
35#include "llvm/Analysis/LoopInfo.h"
36#include "llvm/Analysis/LoopPass.h"
37#include "llvm/Analysis/MemorySSA.h"
38#include "llvm/Analysis/MemorySSAUpdater.h"
39#include "llvm/Analysis/ScalarEvolution.h"
40#include "llvm/Analysis/ScalarEvolutionExpressions.h"
41#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
42#include "llvm/Analysis/TargetLibraryInfo.h"
43#include "llvm/Analysis/TargetTransformInfo.h"
44#include "llvm/Analysis/ValueTracking.h"
45#include "llvm/IR/BasicBlock.h"
46#include "llvm/IR/Constant.h"
47#include "llvm/IR/ConstantRange.h"
48#include "llvm/IR/Constants.h"
49#include "llvm/IR/DataLayout.h"
50#include "llvm/IR/DerivedTypes.h"
51#include "llvm/IR/Dominators.h"
52#include "llvm/IR/Function.h"
53#include "llvm/IR/IRBuilder.h"
54#include "llvm/IR/InstrTypes.h"
55#include "llvm/IR/Instruction.h"
56#include "llvm/IR/Instructions.h"
57#include "llvm/IR/Intrinsics.h"
58#include "llvm/IR/PassManager.h"
59#include "llvm/IR/PatternMatch.h"
60#include "llvm/IR/Type.h"
61#include "llvm/IR/Use.h"
62#include "llvm/IR/User.h"
63#include "llvm/IR/Value.h"
64#include "llvm/IR/ValueHandle.h"
65#include "llvm/Support/Casting.h"
66#include "llvm/Support/Debug.h"
67#include "llvm/Support/MathExtras.h"
68#include "llvm/Support/raw_ostream.h"
69#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
70#include "llvm/Transforms/Utils/BasicBlockUtils.h"
71#include "llvm/Transforms/Utils/Local.h"
72#include "llvm/Transforms/Utils/LoopUtils.h"
73#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
74#include "llvm/Transforms/Utils/SimplifyIndVar.h"
75#include <cassert>
76#include <cstdint>
77#include <utility>
78
79using namespace llvm;
80using namespace PatternMatch;
81using namespace SCEVPatternMatch;
82
83#define DEBUG_TYPE "indvars"
84
85STATISTIC(NumWidened , "Number of indvars widened");
86STATISTIC(NumReplaced , "Number of exit values replaced");
87STATISTIC(NumLFTR , "Number of loop exit tests replaced");
88STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated");
89STATISTIC(NumElimIV , "Number of congruent IVs eliminated");
90
91namespace {
92
93class IndVarSimplify {
94 const ScalarOptions &Opts;
95 LoopInfo *LI;
96 ScalarEvolution *SE;
97 DominatorTree *DT;
98 const DataLayout &DL;
99 TargetLibraryInfo *TLI;
100 const TargetTransformInfo *TTI;
101 std::unique_ptr<MemorySSAUpdater> MSSAU;
102
103 SmallVector<WeakTrackingVH, 16> DeadInsts;
104 bool WidenIndVars;
105
106 bool RunUnswitching = false;
107
108 bool handleFloatingPointIV(Loop *L, PHINode *PH);
109 bool rewriteNonIntegerIVs(Loop *L);
110
111 bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
112 /// Try to improve our exit conditions by converting condition from signed
113 /// to unsigned or rotating computation out of the loop.
114 /// (See inline comment about why this is duplicated from simplifyAndExtend)
115 bool canonicalizeExitCondition(Loop *L);
116 /// Try to eliminate loop exits based on analyzeable exit counts
117 bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter);
118 /// Try to form loop invariant tests for loop exits by changing how many
119 /// iterations of the loop run when that is unobservable.
120 bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);
121
122 bool rewriteFirstIterationLoopExitValues(Loop *L);
123
124 bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
125 const SCEV *ExitCount,
126 PHINode *IndVar, SCEVExpander &Rewriter);
127
128 bool sinkUnusedInvariants(Loop *L);
129
130public:
131 IndVarSimplify(const ScalarOptions &Opts, LoopInfo *LI, ScalarEvolution *SE,
132 DominatorTree *DT, const DataLayout &DL,
133 TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
134 MemorySSA *MSSA, bool WidenIndVars)
135 : Opts(Opts), LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI),
136 WidenIndVars(WidenIndVars) {
137 if (MSSA)
138 MSSAU = std::make_unique<MemorySSAUpdater>(args&: MSSA);
139 }
140
141 bool run(Loop *L);
142
143 bool runUnswitching() const { return RunUnswitching; }
144};
145
146} // end anonymous namespace
147
148//===----------------------------------------------------------------------===//
149// rewriteNonIntegerIVs and helpers. Prefer integer IVs.
150//===----------------------------------------------------------------------===//
151
152/// Convert APF to an integer, if possible.
153static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
154 bool isExact = false;
155 // See if we can convert this to an int64_t
156 uint64_t UIntVal;
157 if (APF.convertToInteger(Input: MutableArrayRef(UIntVal), Width: 64, IsSigned: true,
158 RM: APFloat::rmTowardZero, IsExact: &isExact) != APFloat::opOK ||
159 !isExact)
160 return false;
161 IntVal = UIntVal;
162 return true;
163}
164
165/// Ensure we stay within the bounds of fp values that can be represented as
166/// integers without gaps, which are 2^24 and 2^53 for IEEE-754 single and
167/// double precision respectively (both on negative and positive side).
168static bool isRepresentableAsExactInteger(const APFloat &FPVal,
169 int64_t IntVal) {
170 const auto &FltSema = FPVal.getSemantics();
171 if (!APFloat::isIEEELikeFP(FltSema))
172 return false;
173 return isUIntN(N: APFloat::semanticsPrecision(FltSema), x: AbsoluteValue(X: IntVal));
174}
175
176/// Represents a floating-point induction variable pattern that may be
177/// convertible to integer form.
178struct FloatingPointIV {
179 APFloat InitValue;
180 APFloat IncrValue;
181 APFloat ExitValue;
182 FCmpInst *Compare;
183 BinaryOperator *Add;
184 bool ExitsOnTrue;
185
186 FloatingPointIV(APFloat Init, APFloat Incr, APFloat Exit, FCmpInst *Compare,
187 BinaryOperator *Add, bool ExitsOnTrue)
188 : InitValue(std::move(Init)), IncrValue(std::move(Incr)),
189 ExitValue(std::move(Exit)), Compare(Compare), Add(Add),
190 ExitsOnTrue(ExitsOnTrue) {}
191};
192
193/// Represents the integer values for a converted IV.
194struct IntegerIV {
195 int64_t InitValue;
196 int64_t IncrValue;
197 int64_t ExitValue;
198 CmpInst::Predicate NewPred;
199};
200
201static CmpInst::Predicate getIntegerPredicate(CmpInst::Predicate FPPred) {
202 switch (FPPred) {
203 case CmpInst::FCMP_OEQ:
204 case CmpInst::FCMP_UEQ:
205 return CmpInst::ICMP_EQ;
206 case CmpInst::FCMP_ONE:
207 case CmpInst::FCMP_UNE:
208 return CmpInst::ICMP_NE;
209 case CmpInst::FCMP_OGT:
210 case CmpInst::FCMP_UGT:
211 return CmpInst::ICMP_SGT;
212 case CmpInst::FCMP_OGE:
213 case CmpInst::FCMP_UGE:
214 return CmpInst::ICMP_SGE;
215 case CmpInst::FCMP_OLT:
216 case CmpInst::FCMP_ULT:
217 return CmpInst::ICMP_SLT;
218 case CmpInst::FCMP_OLE:
219 case CmpInst::FCMP_ULE:
220 return CmpInst::ICMP_SLE;
221 default:
222 return CmpInst::BAD_ICMP_PREDICATE;
223 }
224}
225
226/// Analyze a PN to determine whether it represents a simple floating-point
227/// induction variable, with constant fp init, increment, and exit values,
228/// whose exit condition is to be evaluated on every iteration of the loop.
229///
230/// Returns a FloatingPointIV struct if matched, std::nullopt otherwise.
231static std::optional<FloatingPointIV>
232maybeFloatingPointRecurrence(Loop *L, PHINode *PN, const DominatorTree &DT) {
233 assert(L->getLoopLatch() && "Must be in simplified form.");
234
235 // Identify incoming and backedge for the PN.
236 unsigned IncomingEdge = L->contains(BB: PN->getIncomingBlock(i: 0));
237 unsigned BackEdge = IncomingEdge ^ 1;
238
239 // Check incoming value.
240 auto *InitValueVal = dyn_cast<ConstantFP>(Val: PN->getIncomingValue(i: IncomingEdge));
241 if (!InitValueVal)
242 return std::nullopt;
243
244 // Check IV increment. Reject this PN if increment operation is not
245 // an add or increment value can not be represented by an integer.
246 auto *Incr = dyn_cast<BinaryOperator>(Val: PN->getIncomingValue(i: BackEdge));
247 if (!Incr || Incr->getOpcode() != Instruction::FAdd)
248 return std::nullopt;
249
250 // If this is not an add of the PHI with a constantfp, or if the constant fp
251 // is not an integer, bail out.
252 auto *IncValueVal = dyn_cast<ConstantFP>(Val: Incr->getOperand(i_nocapture: 1));
253 if (!IncValueVal || Incr->getOperand(i_nocapture: 0) != PN)
254 return std::nullopt;
255
256 // Check Incr uses. One user is PN and the other user is an exit condition
257 // used by the conditional terminator.
258 // TODO: Should relax this, so as to allow any `fpext` that may occur.
259 if (!Incr->hasNUses(N: 2))
260 return std::nullopt;
261
262 // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't
263 // only used by a branch, we can't transform it.
264 auto It = llvm::find_if(Range: Incr->users(),
265 P: [](const User *U) { return isa<FCmpInst>(Val: U); });
266 if (It == Incr->users().end())
267 return std::nullopt;
268
269 FCmpInst *Compare = cast<FCmpInst>(Val: *It);
270 if (!Compare->hasOneUse())
271 return std::nullopt;
272
273 // We need to verify that the branch actually controls the iteration count
274 // of the loop. If not, the new IV can overflow and no one will notice.
275 // The branch block must be in the loop and one of the successors must be out
276 // of the loop.
277 auto *BI = dyn_cast<CondBrInst>(Val: Compare->user_back());
278 if (!BI)
279 return std::nullopt;
280
281 BasicBlock *ExitingBB = BI->getParent();
282 if (!L->contains(BB: ExitingBB) ||
283 (L->contains(BB: BI->getSuccessor(i: 0)) && L->contains(BB: BI->getSuccessor(i: 1))))
284 return std::nullopt;
285
286 // Ensure that the fcmp exit comparison runs on every iteration of the loop,
287 // otherwise the IV may be incremented past the exit value, thus overflowing.
288 if (!DT.dominates(A: ExitingBB, B: L->getLoopLatch()))
289 return std::nullopt;
290
291 bool ExitsOnTrue = !L->contains(BB: BI->getSuccessor(i: 0));
292 // If it isn't a comparison with an integer-as-fp (the exit value), we can't
293 // transform it.
294 auto *ExitValueVal = dyn_cast<ConstantFP>(Val: Compare->getOperand(i_nocapture: 1));
295 if (!ExitValueVal)
296 return std::nullopt;
297
298 return FloatingPointIV(
299 InitValueVal->getValueAPF(), IncValueVal->getValueAPF(),
300 ExitValueVal->getValueAPF(), Compare, Incr, ExitsOnTrue);
301}
302
303/// Ensure that the floating-point IV can be converted to a semantics-preserving
304/// signed 32-bit integer IV.
305///
306/// Returns a IntegerIV struct if possible, std::nullopt otherwise.
307static std::optional<IntegerIV>
308tryConvertToIntegerIV(const FloatingPointIV &FPIV) {
309 // Convert floating-point predicate to integer.
310 auto NewPred = getIntegerPredicate(FPPred: FPIV.Compare->getPredicate());
311 if (NewPred == CmpInst::BAD_ICMP_PREDICATE)
312 return std::nullopt;
313
314 // Convert APFloat values to signed integers.
315 int64_t InitValue, IncrValue, ExitValue;
316 if (!ConvertToSInt(APF: FPIV.InitValue, IntVal&: InitValue) ||
317 !ConvertToSInt(APF: FPIV.IncrValue, IntVal&: IncrValue) ||
318 !ConvertToSInt(APF: FPIV.ExitValue, IntVal&: ExitValue))
319 return std::nullopt;
320
321 // Bail out if integers cannot be represented exactly.
322 if (!isRepresentableAsExactInteger(FPVal: FPIV.InitValue, IntVal: InitValue) ||
323 !isRepresentableAsExactInteger(FPVal: FPIV.ExitValue, IntVal: ExitValue))
324 return std::nullopt;
325
326 // We convert the floating point induction variable to a signed i32 value if
327 // we can. This is only safe if the comparison will not overflow in a way that
328 // won't be trapped by the integer equivalent operations. Check for this now.
329 // TODO: We could use i64 if it is native and the range requires it.
330
331 // The start/stride/exit values must all fit in signed i32.
332 if (!isInt<32>(x: InitValue) || !isInt<32>(x: IncrValue) || !isInt<32>(x: ExitValue))
333 return std::nullopt;
334
335 // If not actually striding (add x, 0.0), avoid touching the code.
336 if (IncrValue == 0)
337 return std::nullopt;
338
339 // Compute the predicate under which the loop keeps iterating.
340 CmpInst::Predicate ContinuePred =
341 FPIV.ExitsOnTrue ? CmpInst::getInversePredicate(pred: NewPred) : NewPred;
342
343 // Normalize to positive stride.
344 int64_t Start = InitValue, Step = IncrValue, Bound = ExitValue;
345 if (Step < 0) {
346 Start = -Start;
347 Step = -Step;
348 Bound = -Bound;
349 ContinuePred = CmpInst::getSwappedPredicate(pred: ContinuePred);
350 }
351
352 // Start of IV is below the exit value.
353 if (Start >= Bound)
354 return std::nullopt;
355
356 // Compute the last value of the incremented IV.
357 uint64_t Dist = Bound - Start;
358 int64_t Last;
359 switch (ContinuePred) {
360 case CmpInst::ICMP_SLT:
361 Last = Start + alignTo(Value: Dist, Align: Step);
362 break;
363 case CmpInst::ICMP_SLE:
364 Last = Start + alignTo(Value: Dist + 1, Align: Step);
365 break;
366 case CmpInst::ICMP_NE:
367 // The strided value must exactly land on the exit value.
368 if (Dist % Step != 0)
369 return std::nullopt;
370 Last = Bound;
371 break;
372 case CmpInst::ICMP_EQ:
373 Last = Start + Step == Bound ? Bound + Step : Start + Step;
374 break;
375 default:
376 return std::nullopt;
377 }
378
379 // The integer IV must not overflow before the loop exits.
380 if (!isInt<32>(x: Last))
381 return std::nullopt;
382
383 return IntegerIV{.InitValue: InitValue, .IncrValue: IncrValue, .ExitValue: ExitValue, .NewPred: NewPred};
384}
385
386/// Rewrite the floating-point IV as an integer IV.
387static void canonicalizeToIntegerIV(Loop *L, PHINode *PN,
388 const FloatingPointIV &FPIV,
389 const IntegerIV &IIV,
390 const TargetLibraryInfo *TLI,
391 std::unique_ptr<MemorySSAUpdater> &MSSAU) {
392 unsigned IncomingEdge = L->contains(BB: PN->getIncomingBlock(i: 0));
393 unsigned BackEdge = IncomingEdge ^ 1;
394
395 IntegerType *Int32Ty = Type::getInt32Ty(C&: PN->getContext());
396 auto *Incr = cast<BinaryOperator>(Val: PN->getIncomingValue(i: BackEdge));
397 auto *BI = cast<CondBrInst>(Val: FPIV.Compare->user_back());
398
399 LLVM_DEBUG(dbgs() << "INDVARS: Rewriting floating-point IV to integer IV:\n"
400 << " Init: " << IIV.InitValue << "\n"
401 << " Incr: " << IIV.IncrValue << "\n"
402 << " Exit: " << IIV.ExitValue << "\n"
403 << " Pred: " << CmpInst::getPredicateName(IIV.NewPred)
404 << "\n"
405 << " Original PN: " << *PN << "\n");
406
407 // Insert new integer induction variable.
408 PHINode *NewPHI =
409 PHINode::Create(Ty: Int32Ty, NumReservedValues: 2, NameStr: PN->getName() + ".int", InsertBefore: PN->getIterator());
410 NewPHI->addIncoming(V: ConstantInt::getSigned(Ty: Int32Ty, V: IIV.InitValue),
411 BB: PN->getIncomingBlock(i: IncomingEdge));
412 NewPHI->setDebugLoc(PN->getDebugLoc());
413
414 Instruction *NewAdd = BinaryOperator::CreateAdd(
415 V1: NewPHI, V2: ConstantInt::getSigned(Ty: Int32Ty, V: IIV.IncrValue),
416 Name: Incr->getName() + ".int", InsertBefore: Incr->getIterator());
417 NewAdd->setDebugLoc(Incr->getDebugLoc());
418 NewPHI->addIncoming(V: NewAdd, BB: PN->getIncomingBlock(i: BackEdge));
419
420 ICmpInst *NewCompare = new ICmpInst(
421 BI->getIterator(), IIV.NewPred, NewAdd,
422 ConstantInt::getSigned(Ty: Int32Ty, V: IIV.ExitValue), FPIV.Compare->getName());
423 NewCompare->setDebugLoc(FPIV.Compare->getDebugLoc());
424
425 // In the following deletions, PN may become dead and may be deleted.
426 // Use a WeakTrackingVH to observe whether this happens.
427 WeakTrackingVH WeakPH = PN;
428
429 // Delete the old floating point exit comparison. The branch starts using the
430 // new comparison.
431 NewCompare->takeName(V: FPIV.Compare);
432 FPIV.Compare->replaceAllUsesWith(V: NewCompare);
433 RecursivelyDeleteTriviallyDeadInstructions(V: FPIV.Compare, TLI, MSSAU: MSSAU.get());
434
435 // Delete the old floating point increment.
436 Incr->replaceAllUsesWith(V: PoisonValue::get(T: Incr->getType()));
437 RecursivelyDeleteTriviallyDeadInstructions(V: Incr, TLI, MSSAU: MSSAU.get());
438
439 // If the FP induction variable still has uses, this is because something else
440 // in the loop uses its value. In order to canonicalize the induction
441 // variable, we chose to eliminate the IV and rewrite it in terms of an
442 // int->fp cast.
443 //
444 // We give preference to sitofp over uitofp because it is faster on most
445 // platforms.
446 if (WeakPH) {
447 Instruction *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",
448 PN->getParent()->getFirstInsertionPt());
449 Conv->setDebugLoc(PN->getDebugLoc());
450 PN->replaceAllUsesWith(V: Conv);
451 RecursivelyDeleteTriviallyDeadInstructions(V: PN, TLI, MSSAU: MSSAU.get());
452 }
453}
454
455/// If the loop has a floating induction variable, then insert corresponding
456/// integer induction variable if possible. For example, the following:
457/// for(double i = 0; i < 10000; ++i)
458/// bar(i)
459/// is converted into
460/// for(int i = 0; i < 10000; ++i)
461/// bar((double)i);
462bool IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
463 // See if the PN matches a floating-point IV pattern.
464 auto FPIV = maybeFloatingPointRecurrence(L, PN, DT: *DT);
465 if (!FPIV)
466 return false;
467
468 // Can we safely convert the floating-point values to integer ones?
469 auto IIV = tryConvertToIntegerIV(FPIV: *FPIV);
470 if (!IIV)
471 return false;
472
473 // Perform the rewriting.
474 canonicalizeToIntegerIV(L, PN, FPIV: *FPIV, IIV: *IIV, TLI, MSSAU);
475 return true;
476}
477
478bool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
479 // First step. Check to see if there are any floating-point recurrences.
480 // If there are, change them into integer recurrences, permitting analysis by
481 // the SCEV routines.
482 BasicBlock *Header = L->getHeader();
483
484 SmallVector<WeakTrackingVH, 8> PHIs(llvm::make_pointer_range(Range: Header->phis()));
485
486 bool Changed = false;
487 for (WeakTrackingVH &PHI : PHIs)
488 if (PHINode *PN = dyn_cast_or_null<PHINode>(Val: &*PHI))
489 Changed |= handleFloatingPointIV(L, PN);
490
491 // If the loop previously had floating-point IV, ScalarEvolution
492 // may not have been able to compute a trip count. Now that we've done some
493 // re-writing, the trip count may be computable.
494 if (Changed)
495 SE->forgetLoop(L);
496 return Changed;
497}
498
499//===---------------------------------------------------------------------===//
500// rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know
501// they will exit at the first iteration.
502//===---------------------------------------------------------------------===//
503
504/// Check to see if this loop has loop invariant conditions which lead to loop
505/// exits. If so, we know that if the exit path is taken, it is at the first
506/// loop iteration. This lets us predict exit values of PHI nodes that live in
507/// loop header.
508bool IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {
509 // Verify the input to the pass is already in LCSSA form.
510 assert(L->isLCSSAForm(*DT));
511
512 SmallVector<BasicBlock *, 8> ExitBlocks;
513 L->getUniqueExitBlocks(ExitBlocks);
514
515 bool MadeAnyChanges = false;
516 for (auto *ExitBB : ExitBlocks) {
517 // If there are no more PHI nodes in this exit block, then no more
518 // values defined inside the loop are used on this path.
519 for (PHINode &PN : ExitBB->phis()) {
520 for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues();
521 IncomingValIdx != E; ++IncomingValIdx) {
522 auto *IncomingBB = PN.getIncomingBlock(i: IncomingValIdx);
523
524 // Can we prove that the exit must run on the first iteration if it
525 // runs at all? (i.e. early exits are fine for our purposes, but
526 // traces which lead to this exit being taken on the 2nd iteration
527 // aren't.) Note that this is about whether the exit branch is
528 // executed, not about whether it is taken.
529 if (!L->getLoopLatch() ||
530 !DT->dominates(A: IncomingBB, B: L->getLoopLatch()))
531 continue;
532
533 // Get condition that leads to the exit path.
534 auto *TermInst = IncomingBB->getTerminator();
535
536 Value *Cond = nullptr;
537 if (auto *BI = dyn_cast<CondBrInst>(Val: TermInst)) {
538 // Must be a conditional branch, otherwise the block
539 // should not be in the loop.
540 Cond = BI->getCondition();
541 } else if (auto *SI = dyn_cast<SwitchInst>(Val: TermInst))
542 Cond = SI->getCondition();
543 else
544 continue;
545
546 if (!L->isLoopInvariant(V: Cond))
547 continue;
548
549 auto *ExitVal = dyn_cast<PHINode>(Val: PN.getIncomingValue(i: IncomingValIdx));
550
551 // Only deal with PHIs in the loop header.
552 if (!ExitVal || ExitVal->getParent() != L->getHeader())
553 continue;
554
555 // If ExitVal is a PHI on the loop header, then we know its
556 // value along this exit because the exit can only be taken
557 // on the first iteration.
558 auto *LoopPreheader = L->getLoopPreheader();
559 assert(LoopPreheader && "Invalid loop");
560 int PreheaderIdx = ExitVal->getBasicBlockIndex(BB: LoopPreheader);
561 if (PreheaderIdx != -1) {
562 assert(ExitVal->getParent() == L->getHeader() &&
563 "ExitVal must be in loop header");
564 MadeAnyChanges = true;
565 PN.setIncomingValue(i: IncomingValIdx,
566 V: ExitVal->getIncomingValue(i: PreheaderIdx));
567 SE->forgetValue(V: &PN);
568 }
569 }
570 }
571 }
572 return MadeAnyChanges;
573}
574
575//===----------------------------------------------------------------------===//
576// IV Widening - Extend the width of an IV to cover its widest uses.
577//===----------------------------------------------------------------------===//
578
579/// Update information about the induction variable that is extended by this
580/// sign or zero extend operation. This is used to determine the final width of
581/// the IV before actually widening it.
582static void visitIVCast(CastInst *Cast, WideIVInfo &WI,
583 ScalarEvolution *SE,
584 const TargetTransformInfo *TTI) {
585 bool IsSigned = Cast->getOpcode() == Instruction::SExt;
586 if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)
587 return;
588
589 Type *Ty = Cast->getType();
590 uint64_t Width = SE->getTypeSizeInBits(Ty);
591 if (!Cast->getDataLayout().isLegalInteger(Width))
592 return;
593
594 // Check that `Cast` actually extends the induction variable (we rely on this
595 // later). This takes care of cases where `Cast` is extending a truncation of
596 // the narrow induction variable, and thus can end up being narrower than the
597 // "narrow" induction variable.
598 uint64_t NarrowIVWidth = SE->getTypeSizeInBits(Ty: WI.NarrowIV->getType());
599 if (NarrowIVWidth >= Width)
600 return;
601
602 // Cast is either an sext or zext up to this point.
603 // We should not widen an indvar if arithmetics on the wider indvar are more
604 // expensive than those on the narrower indvar. We check only the cost of ADD
605 // because at least an ADD is required to increment the induction variable. We
606 // could compute more comprehensively the cost of all instructions on the
607 // induction variable when necessary.
608 TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
609 if (TTI && TTI->getArithmeticInstrCost(Opcode: Instruction::Add, Ty, CostKind) >
610 TTI->getArithmeticInstrCost(Opcode: Instruction::Add,
611 Ty: Cast->getOperand(i_nocapture: 0)->getType(),
612 CostKind)) {
613 return;
614 }
615
616 if (!WI.WidestNativeType ||
617 Width > SE->getTypeSizeInBits(Ty: WI.WidestNativeType)) {
618 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
619 WI.IsSigned = IsSigned;
620 return;
621 }
622
623 // We extend the IV to satisfy the sign of its user(s), or 'signed'
624 // if there are multiple users with both sign- and zero extensions,
625 // in order not to introduce nondeterministic behaviour based on the
626 // unspecified order of a PHI nodes' users-iterator.
627 WI.IsSigned |= IsSigned;
628}
629
630//===----------------------------------------------------------------------===//
631// Live IV Reduction - Minimize IVs live across the loop.
632//===----------------------------------------------------------------------===//
633
634//===----------------------------------------------------------------------===//
635// Simplification of IV users based on SCEV evaluation.
636//===----------------------------------------------------------------------===//
637
638namespace {
639
640class IndVarSimplifyVisitor : public IVVisitor {
641 ScalarEvolution *SE;
642 const TargetTransformInfo *TTI;
643 PHINode *IVPhi;
644
645public:
646 WideIVInfo WI;
647
648 IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,
649 const TargetTransformInfo *TTI,
650 const DominatorTree *DTree)
651 : SE(SCEV), TTI(TTI), IVPhi(IV) {
652 DT = DTree;
653 WI.NarrowIV = IVPhi;
654 }
655
656 // Implement the interface used by simplifyUsersOfIV.
657 void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }
658};
659
660} // end anonymous namespace
661
662/// Iteratively perform simplification on a worklist of IV users. Each
663/// successive simplification may push more users which may themselves be
664/// candidates for simplification.
665///
666/// Sign/Zero extend elimination is interleaved with IV simplification.
667bool IndVarSimplify::simplifyAndExtend(Loop *L,
668 SCEVExpander &Rewriter,
669 LoopInfo *LI) {
670 SmallVector<WideIVInfo, 8> WideIVs;
671
672 auto *GuardDecl = Intrinsic::getDeclarationIfExists(
673 M: L->getBlocks()[0]->getModule(), id: Intrinsic::experimental_guard);
674 bool HasGuards = GuardDecl && !GuardDecl->use_empty();
675
676 SmallVector<PHINode *, 8> LoopPhis(
677 llvm::make_pointer_range(Range: L->getHeader()->phis()));
678
679 // Each round of simplification iterates through the SimplifyIVUsers worklist
680 // for all current phis, then determines whether any IVs can be
681 // widened. Widening adds new phis to LoopPhis, inducing another round of
682 // simplification on the wide IVs.
683 bool Changed = false;
684 while (!LoopPhis.empty()) {
685 // Evaluate as many IV expressions as possible before widening any IVs. This
686 // forces SCEV to set no-wrap flags before evaluating sign/zero
687 // extension. The first time SCEV attempts to normalize sign/zero extension,
688 // the result becomes final. So for the most predictable results, we delay
689 // evaluation of sign/zero extend evaluation until needed, and avoid running
690 // other SCEV based analysis prior to simplifyAndExtend.
691 do {
692 PHINode *CurrIV = LoopPhis.pop_back_val();
693
694 // Information about sign/zero extensions of CurrIV.
695 IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);
696
697 const auto &[C, U] = simplifyUsersOfIV(CurrIV, SE, DT, LI, TTI, Dead&: DeadInsts,
698 Rewriter, V: &Visitor);
699
700 Changed |= C;
701 RunUnswitching |= U;
702 if (Visitor.WI.WidestNativeType) {
703 WideIVs.push_back(Elt: Visitor.WI);
704 }
705 } while(!LoopPhis.empty());
706
707 // Continue if we disallowed widening.
708 if (!WidenIndVars)
709 continue;
710
711 for (; !WideIVs.empty(); WideIVs.pop_back()) {
712 unsigned ElimExt;
713 unsigned Widened;
714 if (PHINode *WidePhi = createWideIV(
715 WI: WideIVs.back(), LI, SE, Rewriter, DT, DeadInsts, NumElimExt&: ElimExt, NumWidened&: Widened,
716 HasGuards, UsePostIncrementRanges: Opts.indvars_post_increment_ranges)) {
717 NumElimExt += ElimExt;
718 NumWidened += Widened;
719 Changed = true;
720 LoopPhis.push_back(Elt: WidePhi);
721 }
722 }
723 }
724 return Changed;
725}
726
727//===----------------------------------------------------------------------===//
728// linearFunctionTestReplace and its kin. Rewrite the loop exit condition.
729//===----------------------------------------------------------------------===//
730
731/// Given an Value which is hoped to be part of an add recurance in the given
732/// loop, return the associated Phi node if so. Otherwise, return null. Note
733/// that this is less general than SCEVs AddRec checking.
734static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L) {
735 Instruction *IncI = dyn_cast<Instruction>(Val: IncV);
736 if (!IncI)
737 return nullptr;
738
739 switch (IncI->getOpcode()) {
740 case Instruction::Add:
741 case Instruction::Sub:
742 break;
743 case Instruction::GetElementPtr:
744 // An IV counter must preserve its type.
745 if (IncI->getNumOperands() == 2)
746 break;
747 [[fallthrough]];
748 default:
749 return nullptr;
750 }
751
752 PHINode *Phi = dyn_cast<PHINode>(Val: IncI->getOperand(i: 0));
753 if (Phi && Phi->getParent() == L->getHeader()) {
754 if (L->isLoopInvariant(V: IncI->getOperand(i: 1)))
755 return Phi;
756 return nullptr;
757 }
758 if (IncI->getOpcode() == Instruction::GetElementPtr)
759 return nullptr;
760
761 // Allow add/sub to be commuted.
762 Phi = dyn_cast<PHINode>(Val: IncI->getOperand(i: 1));
763 if (Phi && Phi->getParent() == L->getHeader()) {
764 if (L->isLoopInvariant(V: IncI->getOperand(i: 0)))
765 return Phi;
766 }
767 return nullptr;
768}
769
770/// Whether the current loop exit test is based on this value. Currently this
771/// is limited to a direct use in the loop condition.
772static bool isLoopExitTestBasedOn(Value *V, BasicBlock *ExitingBB) {
773 CondBrInst *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
774 ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: BI->getCondition());
775 // TODO: Allow non-icmp loop test.
776 if (!ICmp)
777 return false;
778
779 // TODO: Allow indirect use.
780 return ICmp->getOperand(i_nocapture: 0) == V || ICmp->getOperand(i_nocapture: 1) == V;
781}
782
783/// linearFunctionTestReplace policy. Return true unless we can show that the
784/// current exit test is already sufficiently canonical.
785static bool needsLFTR(Loop *L, BasicBlock *ExitingBB) {
786 assert(L->getLoopLatch() && "Must be in simplified form");
787
788 // Avoid converting a constant or loop invariant test back to a runtime
789 // test. This is critical for when SCEV's cached ExitCount is less precise
790 // than the current IR (such as after we've proven a particular exit is
791 // actually dead and thus the BE count never reaches our ExitCount.)
792 CondBrInst *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
793 if (L->isLoopInvariant(V: BI->getCondition()))
794 return false;
795
796 // Do LFTR to simplify the exit condition to an ICMP.
797 ICmpInst *Cond = dyn_cast<ICmpInst>(Val: BI->getCondition());
798 if (!Cond)
799 return true;
800
801 // Do LFTR to simplify the exit ICMP to EQ/NE
802 ICmpInst::Predicate Pred = Cond->getPredicate();
803 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
804 return true;
805
806 // Look for a loop invariant RHS
807 Value *LHS = Cond->getOperand(i_nocapture: 0);
808 Value *RHS = Cond->getOperand(i_nocapture: 1);
809 if (!L->isLoopInvariant(V: RHS)) {
810 if (!L->isLoopInvariant(V: LHS))
811 return true;
812 std::swap(a&: LHS, b&: RHS);
813 }
814 // Look for a simple IV counter LHS
815 PHINode *Phi = dyn_cast<PHINode>(Val: LHS);
816 if (!Phi)
817 Phi = getLoopPhiForCounter(IncV: LHS, L);
818
819 if (!Phi)
820 return true;
821
822 // Do LFTR if PHI node is defined in the loop, but is *not* a counter.
823 int Idx = Phi->getBasicBlockIndex(BB: L->getLoopLatch());
824 if (Idx < 0)
825 return true;
826
827 // Do LFTR if the exit condition's IV is *not* a simple counter.
828 Value *IncV = Phi->getIncomingValue(i: Idx);
829 return Phi != getLoopPhiForCounter(IncV, L);
830}
831
832/// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
833/// down to checking that all operands are constant and listing instructions
834/// that may hide undef.
835static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited,
836 unsigned Depth) {
837 if (isa<Constant>(Val: V))
838 return !isa<UndefValue>(Val: V);
839
840 if (Depth >= 6)
841 return false;
842
843 // Conservatively handle non-constant non-instructions. For example, Arguments
844 // may be undef.
845 Instruction *I = dyn_cast<Instruction>(Val: V);
846 if (!I)
847 return false;
848
849 // Load and return values may be undef.
850 if(I->mayReadFromMemory() || isa<CallInst>(Val: I) || isa<InvokeInst>(Val: I))
851 return false;
852
853 // Optimistically handle other instructions.
854 for (Value *Op : I->operands()) {
855 if (!Visited.insert(Ptr: Op).second)
856 continue;
857 if (!hasConcreteDefImpl(V: Op, Visited, Depth: Depth+1))
858 return false;
859 }
860 return true;
861}
862
863/// Return true if the given value is concrete. We must prove that undef can
864/// never reach it.
865///
866/// TODO: If we decide that this is a good approach to checking for undef, we
867/// may factor it into a common location.
868static bool hasConcreteDef(Value *V) {
869 SmallPtrSet<Value*, 8> Visited;
870 Visited.insert(Ptr: V);
871 return hasConcreteDefImpl(V, Visited, Depth: 0);
872}
873
874/// Return true if the given phi is a "counter" in L. A counter is an
875/// add recurance (of integer or pointer type) with an arbitrary start, and a
876/// step of 1. Note that L must have exactly one latch.
877static bool isLoopCounter(PHINode* Phi, Loop *L,
878 ScalarEvolution *SE) {
879 assert(Phi->getParent() == L->getHeader());
880 assert(L->getLoopLatch());
881
882 if (!SE->isSCEVable(Ty: Phi->getType()))
883 return false;
884
885 const SCEV *S = SE->getSCEV(V: Phi);
886 if (!match(S, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_scev_One(), L: m_SpecificLoop(L))))
887 return false;
888
889 int LatchIdx = Phi->getBasicBlockIndex(BB: L->getLoopLatch());
890 Value *IncV = Phi->getIncomingValue(i: LatchIdx);
891 return (getLoopPhiForCounter(IncV, L) == Phi &&
892 isa<SCEVAddRecExpr>(Val: SE->getSCEV(V: IncV)));
893}
894
895/// Search the loop header for a loop counter (anadd rec w/step of one)
896/// suitable for use by LFTR. If multiple counters are available, select the
897/// "best" one based profitable heuristics.
898///
899/// BECount may be an i8* pointer type. The pointer difference is already
900/// valid count without scaling the address stride, so it remains a pointer
901/// expression as far as SCEV is concerned.
902static PHINode *FindLoopCounter(Loop *L, BasicBlock *ExitingBB,
903 const SCEV *BECount,
904 ScalarEvolution *SE, DominatorTree *DT) {
905 uint64_t BCWidth = SE->getTypeSizeInBits(Ty: BECount->getType());
906
907 Value *Cond = cast<CondBrInst>(Val: ExitingBB->getTerminator())->getCondition();
908
909 // Loop over all of the PHI nodes, looking for a simple counter.
910 PHINode *BestPhi = nullptr;
911 const SCEV *BestInit = nullptr;
912 BasicBlock *LatchBlock = L->getLoopLatch();
913 assert(LatchBlock && "Must be in simplified form");
914 const DataLayout &DL = L->getHeader()->getDataLayout();
915
916 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(Val: I); ++I) {
917 PHINode *Phi = cast<PHINode>(Val&: I);
918 if (!isLoopCounter(Phi, L, SE))
919 continue;
920
921 const auto *AR = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: Phi));
922
923 // AR may be a pointer type, while BECount is an integer type.
924 // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
925 // AR may not be a narrower type, or we may never exit.
926 uint64_t PhiWidth = SE->getTypeSizeInBits(Ty: AR->getType());
927 if (PhiWidth < BCWidth || !DL.isLegalInteger(Width: PhiWidth))
928 continue;
929
930 // Avoid reusing a potentially undef value to compute other values that may
931 // have originally had a concrete definition.
932 if (!hasConcreteDef(V: Phi)) {
933 // We explicitly allow unknown phis as long as they are already used by
934 // the loop exit test. This is legal since performing LFTR could not
935 // increase the number of undef users.
936 Value *IncPhi = Phi->getIncomingValueForBlock(BB: LatchBlock);
937 if (!isLoopExitTestBasedOn(V: Phi, ExitingBB) &&
938 !isLoopExitTestBasedOn(V: IncPhi, ExitingBB))
939 continue;
940 }
941
942 // Avoid introducing undefined behavior due to poison which didn't exist in
943 // the original program. (Annoyingly, the rules for poison and undef
944 // propagation are distinct, so this does NOT cover the undef case above.)
945 // We have to ensure that we don't introduce UB by introducing a use on an
946 // iteration where said IV produces poison. Our strategy here differs for
947 // pointers and integer IVs. For integers, we strip and reinfer as needed,
948 // see code in linearFunctionTestReplace. For pointers, we restrict
949 // transforms as there is no good way to reinfer inbounds once lost.
950 if (!Phi->getType()->isIntegerTy() &&
951 !mustExecuteUBIfPoisonOnPathTo(Root: Phi, OnPathTo: ExitingBB->getTerminator(), DT))
952 continue;
953
954 const SCEV *Init = AR->getStart();
955
956 if (BestPhi && !isAlmostDeadIV(IV: BestPhi, LatchBlock, Cond)) {
957 // Don't force a live loop counter if another IV can be used.
958 if (isAlmostDeadIV(IV: Phi, LatchBlock, Cond))
959 continue;
960
961 // Prefer to count-from-zero. This is a more "canonical" counter form. It
962 // also prefers integer to pointer IVs.
963 if (BestInit->isZero() != Init->isZero()) {
964 if (BestInit->isZero())
965 continue;
966 }
967 // If two IVs both count from zero or both count from nonzero then the
968 // narrower is likely a dead phi that has been widened. Use the wider phi
969 // to allow the other to be eliminated.
970 else if (PhiWidth <= SE->getTypeSizeInBits(Ty: BestPhi->getType()))
971 continue;
972 }
973 BestPhi = Phi;
974 BestInit = Init;
975 }
976 return BestPhi;
977}
978
979/// Insert an IR expression which computes the value held by the IV IndVar
980/// (which must be an loop counter w/unit stride) after the backedge of loop L
981/// is taken ExitCount times.
982static Value *genLoopLimit(PHINode *IndVar, BasicBlock *ExitingBB,
983 const SCEV *ExitCount, bool UsePostInc, Loop *L,
984 SCEVExpander &Rewriter, ScalarEvolution *SE) {
985 assert(isLoopCounter(IndVar, L, SE));
986 assert(ExitCount->getType()->isIntegerTy() && "exit count must be integer");
987 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: IndVar));
988 assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride");
989
990 // For integer IVs, truncate the IV before computing the limit unless we
991 // know apriori that the limit must be a constant when evaluated in the
992 // bitwidth of the IV. We prefer (potentially) keeping a truncate of the
993 // IV in the loop over a (potentially) expensive expansion of the widened
994 // exit count add(zext(add)) expression.
995 if (IndVar->getType()->isIntegerTy() &&
996 SE->getTypeSizeInBits(Ty: AR->getType()) >
997 SE->getTypeSizeInBits(Ty: ExitCount->getType())) {
998 const SCEV *IVInit = AR->getStart();
999 if (!isa<SCEVConstant>(Val: IVInit) || !isa<SCEVConstant>(Val: ExitCount)) {
1000 const SCEV *TruncExpr = SE->getTruncateExpr(Op: AR, Ty: ExitCount->getType());
1001
1002 // The following bailout is necessary due to the interaction with
1003 // the depth limit in SCEV analysis.
1004 if (!isa<SCEVAddRecExpr>(Val: TruncExpr))
1005 return nullptr;
1006 AR = cast<SCEVAddRecExpr>(Val: TruncExpr);
1007 }
1008 }
1009
1010 const SCEVAddRecExpr *ARBase = UsePostInc ? AR->getPostIncExpr(SE&: *SE) : AR;
1011 const SCEV *IVLimit = ARBase->evaluateAtIteration(It: ExitCount, SE&: *SE);
1012 assert(SE->isLoopInvariant(IVLimit, L) &&
1013 "Computed iteration count is not loop invariant!");
1014 return Rewriter.expandCodeFor(SH: IVLimit, Ty: ARBase->getType(),
1015 I: ExitingBB->getTerminator());
1016}
1017
1018/// This method rewrites the exit condition of the loop to be a canonical !=
1019/// comparison against the incremented loop induction variable. This pass is
1020/// able to rewrite the exit tests of any loop where the SCEV analysis can
1021/// determine a loop-invariant trip count of the loop, which is actually a much
1022/// broader range than just linear tests.
1023bool IndVarSimplify::
1024linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
1025 const SCEV *ExitCount,
1026 PHINode *IndVar, SCEVExpander &Rewriter) {
1027 assert(L->getLoopLatch() && "Loop no longer in simplified form?");
1028 assert(isLoopCounter(IndVar, L, SE));
1029 Instruction * const IncVar =
1030 cast<Instruction>(Val: IndVar->getIncomingValueForBlock(BB: L->getLoopLatch()));
1031
1032 // Initialize CmpIndVar to the preincremented IV.
1033 Value *CmpIndVar = IndVar;
1034 bool UsePostInc = false;
1035
1036 // If the exiting block is the same as the backedge block, we prefer to
1037 // compare against the post-incremented value, otherwise we must compare
1038 // against the preincremented value.
1039 if (ExitingBB == L->getLoopLatch()) {
1040 // For pointer IVs, we chose to not strip inbounds which requires us not
1041 // to add a potentially UB introducing use. We need to either a) show
1042 // the loop test we're modifying is already in post-inc form, or b) show
1043 // that adding a use must not introduce UB.
1044 bool SafeToPostInc =
1045 IndVar->getType()->isIntegerTy() ||
1046 isLoopExitTestBasedOn(V: IncVar, ExitingBB) ||
1047 mustExecuteUBIfPoisonOnPathTo(Root: IncVar, OnPathTo: ExitingBB->getTerminator(), DT);
1048 if (SafeToPostInc) {
1049 UsePostInc = true;
1050 CmpIndVar = IncVar;
1051 }
1052 }
1053
1054 Value *ExitCnt =
1055 genLoopLimit(IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);
1056 if (!ExitCnt)
1057 return false;
1058
1059 assert(ExitCnt->getType()->isPointerTy() ==
1060 IndVar->getType()->isPointerTy() &&
1061 "genLoopLimit missed a cast");
1062
1063 // It may be necessary to drop nowrap flags on the incrementing instruction
1064 // if either LFTR moves from a pre-inc check to a post-inc check (in which
1065 // case the increment might have previously been poison on the last iteration
1066 // only) or if LFTR switches to a different IV that was previously dynamically
1067 // dead (and as such may be arbitrarily poison). We remove any nowrap flags
1068 // that SCEV didn't infer for the post-inc addrec (even if we use a pre-inc
1069 // check), because the pre-inc addrec flags may be adopted from the original
1070 // instruction, while SCEV has to explicitly prove the post-inc nowrap flags.
1071 // TODO: This handling is inaccurate for one case: If we switch to a
1072 // dynamically dead IV that wraps on the first loop iteration only, which is
1073 // not covered by the post-inc addrec. (If the new IV was not dynamically
1074 // dead, it could not be poison on the first iteration in the first place.)
1075 if (auto *BO = dyn_cast<BinaryOperator>(Val: IncVar)) {
1076 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: IncVar));
1077 if (BO->hasNoUnsignedWrap())
1078 BO->setHasNoUnsignedWrap(AR->hasNoUnsignedWrap());
1079 if (BO->hasNoSignedWrap())
1080 BO->setHasNoSignedWrap(AR->hasNoSignedWrap());
1081 }
1082
1083 // Insert a new icmp_ne or icmp_eq instruction before the branch.
1084 CondBrInst *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1085 ICmpInst::Predicate P;
1086 if (L->contains(BB: BI->getSuccessor(i: 0)))
1087 P = ICmpInst::ICMP_NE;
1088 else
1089 P = ICmpInst::ICMP_EQ;
1090
1091 IRBuilder<> Builder(BI);
1092
1093 // The new loop exit condition should reuse the debug location of the
1094 // original loop exit condition.
1095 if (auto *Cond = dyn_cast<Instruction>(Val: BI->getCondition()))
1096 Builder.SetCurrentDebugLocation(Cond->getDebugLoc());
1097
1098 // For integer IVs, if we evaluated the limit in the narrower bitwidth to
1099 // avoid the expensive expansion of the limit expression in the wider type,
1100 // emit a truncate to narrow the IV to the ExitCount type. This is safe
1101 // since we know (from the exit count bitwidth), that we can't self-wrap in
1102 // the narrower type.
1103 unsigned CmpIndVarSize = SE->getTypeSizeInBits(Ty: CmpIndVar->getType());
1104 unsigned ExitCntSize = SE->getTypeSizeInBits(Ty: ExitCnt->getType());
1105 if (CmpIndVarSize > ExitCntSize) {
1106 assert(!CmpIndVar->getType()->isPointerTy() &&
1107 !ExitCnt->getType()->isPointerTy());
1108
1109 // Before resorting to actually inserting the truncate, use the same
1110 // reasoning as from SimplifyIndvar::eliminateTrunc to see if we can extend
1111 // the other side of the comparison instead. We still evaluate the limit
1112 // in the narrower bitwidth, we just prefer a zext/sext outside the loop to
1113 // a truncate within in.
1114 bool Extended = false;
1115 const SCEV *IV = SE->getSCEV(V: CmpIndVar);
1116 const SCEV *TruncatedIV = SE->getTruncateExpr(Op: IV, Ty: ExitCnt->getType());
1117 const SCEV *ZExtTrunc =
1118 SE->getZeroExtendExpr(Op: TruncatedIV, Ty: CmpIndVar->getType());
1119
1120 if (ZExtTrunc == IV) {
1121 Extended = true;
1122 ExitCnt = Builder.CreateZExt(V: ExitCnt, DestTy: IndVar->getType(),
1123 Name: "wide.trip.count");
1124 } else {
1125 const SCEV *SExtTrunc =
1126 SE->getSignExtendExpr(Op: TruncatedIV, Ty: CmpIndVar->getType());
1127 if (SExtTrunc == IV) {
1128 Extended = true;
1129 ExitCnt = Builder.CreateSExt(V: ExitCnt, DestTy: IndVar->getType(),
1130 Name: "wide.trip.count");
1131 }
1132 }
1133
1134 if (Extended) {
1135 bool Discard;
1136 L->makeLoopInvariant(V: ExitCnt, Changed&: Discard);
1137 } else
1138 CmpIndVar = Builder.CreateTrunc(V: CmpIndVar, DestTy: ExitCnt->getType(),
1139 Name: "lftr.wideiv");
1140 }
1141 LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
1142 << " LHS:" << *CmpIndVar << '\n'
1143 << " op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==")
1144 << "\n"
1145 << " RHS:\t" << *ExitCnt << "\n"
1146 << "ExitCount:\t" << *ExitCount << "\n"
1147 << " was: " << *BI->getCondition() << "\n");
1148
1149 Value *Cond = Builder.CreateICmp(P, LHS: CmpIndVar, RHS: ExitCnt, Name: "exitcond");
1150 Value *OrigCond = BI->getCondition();
1151 // It's tempting to use replaceAllUsesWith here to fully replace the old
1152 // comparison, but that's not immediately safe, since users of the old
1153 // comparison may not be dominated by the new comparison. Instead, just
1154 // update the branch to use the new comparison; in the common case this
1155 // will make old comparison dead.
1156 BI->setCondition(Cond);
1157 DeadInsts.emplace_back(Args&: OrigCond);
1158
1159 ++NumLFTR;
1160 return true;
1161}
1162
1163//===----------------------------------------------------------------------===//
1164// sinkUnusedInvariants. A late subpass to cleanup loop preheaders.
1165//===----------------------------------------------------------------------===//
1166
1167/// If there's a single exit block, sink any loop-invariant values that
1168/// were defined in the preheader but not used inside the loop into the
1169/// exit block to reduce register pressure in the loop.
1170bool IndVarSimplify::sinkUnusedInvariants(Loop *L) {
1171 BasicBlock *ExitBlock = L->getExitBlock();
1172 if (!ExitBlock) return false;
1173
1174 BasicBlock *Preheader = L->getLoopPreheader();
1175 if (!Preheader) return false;
1176
1177 bool MadeAnyChanges = false;
1178 SmallVector<Value *, 16> SunkInsts;
1179 for (Instruction &I : llvm::make_early_inc_range(Range: llvm::reverse(C&: *Preheader))) {
1180
1181 // Skip BB Terminator.
1182 if (Preheader->getTerminator() == &I)
1183 continue;
1184
1185 // New instructions were inserted at the end of the preheader.
1186 if (isa<PHINode>(Val: I))
1187 break;
1188
1189 // Don't move instructions which might have side effects, since the side
1190 // effects need to complete before instructions inside the loop. Also don't
1191 // move instructions which might read memory, since the loop may modify
1192 // memory. Note that it's okay if the instruction might have undefined
1193 // behavior: LoopSimplify guarantees that the preheader dominates the exit
1194 // block.
1195 if (I.mayHaveSideEffects() || I.mayReadFromMemory())
1196 continue;
1197
1198 // Don't sink convergent calls. Not every thread that executes the
1199 // preheader necessarily reaches the exit block (e.g. a thread may be
1200 // terminated inside the loop), so sinking could change the set of threads
1201 // that execute the call together.
1202 if (auto *CI = dyn_cast<CallInst>(Val: &I); CI && CI->isConvergent())
1203 continue;
1204
1205 // Skip eh pad instructions.
1206 if (I.isEHPad())
1207 continue;
1208
1209 // Don't sink alloca: we never want to sink static alloca's out of the
1210 // entry block, and correctly sinking dynamic alloca's requires
1211 // checks for stacksave/stackrestore intrinsics.
1212 // FIXME: Refactor this check somehow?
1213 if (isa<AllocaInst>(Val: &I))
1214 continue;
1215
1216 // Determine if there is a use in or before the loop (direct or
1217 // otherwise).
1218 bool UsedInLoop = false;
1219 for (Use &U : I.uses()) {
1220 Instruction *User = cast<Instruction>(Val: U.getUser());
1221 BasicBlock *UseBB = User->getParent();
1222 if (PHINode *P = dyn_cast<PHINode>(Val: User)) {
1223 unsigned i =
1224 PHINode::getIncomingValueNumForOperand(i: U.getOperandNo());
1225 UseBB = P->getIncomingBlock(i);
1226 }
1227 if (UseBB == Preheader || L->contains(BB: UseBB)) {
1228 UsedInLoop = true;
1229 break;
1230 }
1231 }
1232
1233 // If there is, the def must remain in the preheader.
1234 if (UsedInLoop)
1235 continue;
1236
1237 // Otherwise, sink it to the exit block.
1238 I.moveBefore(InsertPos: ExitBlock->getFirstInsertionPt());
1239 SunkInsts.push_back(Elt: &I);
1240 MadeAnyChanges = true;
1241 }
1242
1243 if (!SunkInsts.empty())
1244 SE->forgetValues(Values: SunkInsts);
1245
1246 return MadeAnyChanges;
1247}
1248
1249static void replaceExitCond(CondBrInst *BI, Value *NewCond,
1250 SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
1251 auto *OldCond = BI->getCondition();
1252 LLVM_DEBUG(dbgs() << "Replacing condition of loop-exiting branch " << *BI
1253 << " with " << *NewCond << "\n");
1254 BI->setCondition(NewCond);
1255 if (OldCond->use_empty())
1256 DeadInsts.emplace_back(Args&: OldCond);
1257}
1258
1259static Constant *createFoldedExitCond(const Loop *L, BasicBlock *ExitingBB,
1260 bool IsTaken) {
1261 CondBrInst *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1262 bool ExitIfTrue = !L->contains(BB: *succ_begin(BB: ExitingBB));
1263 auto *OldCond = BI->getCondition();
1264 return ConstantInt::get(Ty: OldCond->getType(),
1265 V: IsTaken ? ExitIfTrue : !ExitIfTrue);
1266}
1267
1268static void foldExit(const Loop *L, BasicBlock *ExitingBB, bool IsTaken,
1269 SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
1270 CondBrInst *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1271 auto *NewCond = createFoldedExitCond(L, ExitingBB, IsTaken);
1272 replaceExitCond(BI, NewCond, DeadInsts);
1273}
1274
1275static void replaceLoopPHINodesWithPreheaderValues(
1276 LoopInfo *LI, Loop *L, SmallVectorImpl<WeakTrackingVH> &DeadInsts,
1277 ScalarEvolution &SE) {
1278 assert(L->isLoopSimplifyForm() && "Should only do it in simplify form!");
1279 auto *LoopPreheader = L->getLoopPreheader();
1280 auto *LoopHeader = L->getHeader();
1281 SmallVector<Instruction *> Worklist;
1282 for (auto &PN : LoopHeader->phis()) {
1283 auto *PreheaderIncoming = PN.getIncomingValueForBlock(BB: LoopPreheader);
1284 for (User *U : PN.users())
1285 Worklist.push_back(Elt: cast<Instruction>(Val: U));
1286 SE.forgetValue(V: &PN);
1287 PN.replaceAllUsesWith(V: PreheaderIncoming);
1288 DeadInsts.emplace_back(Args: &PN);
1289 }
1290
1291 // Replacing with the preheader value will often allow IV users to simplify
1292 // (especially if the preheader value is a constant).
1293 SmallPtrSet<Instruction *, 16> Visited;
1294 while (!Worklist.empty()) {
1295 auto *I = cast<Instruction>(Val: Worklist.pop_back_val());
1296 if (!Visited.insert(Ptr: I).second)
1297 continue;
1298
1299 // Don't simplify instructions outside the loop.
1300 if (!L->contains(Inst: I))
1301 continue;
1302
1303 Value *Res = simplifyInstruction(I, Q: I->getDataLayout());
1304 if (Res && LI->replacementPreservesLCSSAForm(From: I, To: Res)) {
1305 for (User *U : I->users())
1306 Worklist.push_back(Elt: cast<Instruction>(Val: U));
1307 I->replaceAllUsesWith(V: Res);
1308 DeadInsts.emplace_back(Args&: I);
1309 }
1310 }
1311}
1312
1313static Value *
1314createInvariantCond(const Loop *L, BasicBlock *ExitingBB,
1315 const ScalarEvolution::LoopInvariantPredicate &LIP,
1316 SCEVExpander &Rewriter) {
1317 ICmpInst::Predicate InvariantPred = LIP.Pred;
1318 BasicBlock *Preheader = L->getLoopPreheader();
1319 assert(Preheader && "Preheader doesn't exist");
1320 Rewriter.setInsertPoint(Preheader->getTerminator());
1321 auto *LHSV = Rewriter.expandCodeFor(SH: LIP.LHS);
1322 auto *RHSV = Rewriter.expandCodeFor(SH: LIP.RHS);
1323 bool ExitIfTrue = !L->contains(BB: *succ_begin(BB: ExitingBB));
1324 if (ExitIfTrue)
1325 InvariantPred = ICmpInst::getInversePredicate(pred: InvariantPred);
1326 IRBuilder<> Builder(Preheader->getTerminator());
1327 CondBrInst *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1328 return Builder.CreateICmp(P: InvariantPred, LHS: LHSV, RHS: RHSV,
1329 Name: BI->getCondition()->getName());
1330}
1331
1332static std::optional<Value *>
1333createReplacement(ICmpInst *ICmp, const Loop *L, BasicBlock *ExitingBB,
1334 const SCEV *MaxIter, bool Inverted, bool SkipLastIter,
1335 ScalarEvolution *SE, SCEVExpander &Rewriter) {
1336 CmpPredicate Pred = ICmp->getCmpPredicate();
1337 Value *LHS = ICmp->getOperand(i_nocapture: 0);
1338 Value *RHS = ICmp->getOperand(i_nocapture: 1);
1339
1340 // 'LHS pred RHS' should now mean that we stay in loop.
1341 auto *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1342 if (Inverted)
1343 Pred = ICmpInst::getInverseCmpPredicate(Pred);
1344
1345 const SCEV *LHSS = SE->getSCEVAtScope(V: LHS, L);
1346 const SCEV *RHSS = SE->getSCEVAtScope(V: RHS, L);
1347 // Can we prove it to be trivially true or false?
1348 if (auto EV = SE->evaluatePredicateAt(Pred, LHS: LHSS, RHS: RHSS, CtxI: BI))
1349 return createFoldedExitCond(L, ExitingBB, /*IsTaken*/ !*EV);
1350
1351 auto *ARTy = LHSS->getType();
1352 auto *MaxIterTy = MaxIter->getType();
1353 // If possible, adjust types.
1354 if (SE->getTypeSizeInBits(Ty: ARTy) > SE->getTypeSizeInBits(Ty: MaxIterTy))
1355 MaxIter = SE->getZeroExtendExpr(Op: MaxIter, Ty: ARTy);
1356 else if (SE->getTypeSizeInBits(Ty: ARTy) < SE->getTypeSizeInBits(Ty: MaxIterTy)) {
1357 const SCEV *MinusOne = SE->getMinusOne(Ty: ARTy);
1358 const SCEV *MaxAllowedIter = SE->getZeroExtendExpr(Op: MinusOne, Ty: MaxIterTy);
1359 if (SE->isKnownPredicateAt(Pred: ICmpInst::ICMP_ULE, LHS: MaxIter, RHS: MaxAllowedIter, CtxI: BI))
1360 MaxIter = SE->getTruncateExpr(Op: MaxIter, Ty: ARTy);
1361 }
1362
1363 if (SkipLastIter) {
1364 // Semantically skip last iter is "subtract 1, do not bother about unsigned
1365 // wrap". getLoopInvariantExitCondDuringFirstIterations knows how to deal
1366 // with umin in a smart way, but umin(a, b) - 1 will likely not simplify.
1367 // So we manually construct umin(a - 1, b - 1).
1368 SmallVector<SCEVUse, 4> Elements;
1369 if (auto *UMin = dyn_cast<SCEVUMinExpr>(Val: MaxIter)) {
1370 for (SCEVUse Op : UMin->operands())
1371 Elements.push_back(Elt: SE->getMinusSCEV(LHS: Op, RHS: SE->getOne(Ty: Op->getType())));
1372 MaxIter = SE->getUMinFromMismatchedTypes(Ops&: Elements);
1373 } else
1374 MaxIter = SE->getMinusSCEV(LHS: MaxIter, RHS: SE->getOne(Ty: MaxIter->getType()));
1375 }
1376
1377 // Check if there is a loop-invariant predicate equivalent to our check.
1378 auto LIP = SE->getLoopInvariantExitCondDuringFirstIterations(Pred, LHS: LHSS, RHS: RHSS,
1379 L, CtxI: BI, MaxIter);
1380 if (!LIP)
1381 return std::nullopt;
1382
1383 // Can we prove it to be trivially true?
1384 if (SE->isKnownPredicateAt(Pred: LIP->Pred, LHS: LIP->LHS, RHS: LIP->RHS, CtxI: BI))
1385 return createFoldedExitCond(L, ExitingBB, /*IsTaken*/ false);
1386 else
1387 return createInvariantCond(L, ExitingBB, LIP: *LIP, Rewriter);
1388}
1389
1390static bool optimizeLoopExitWithUnknownExitCount(
1391 const Loop *L, CondBrInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter,
1392 bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter,
1393 SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
1394 assert(
1395 (L->contains(BI->getSuccessor(0)) != L->contains(BI->getSuccessor(1))) &&
1396 "Not a loop exit!");
1397
1398 // For branch that stays in loop by TRUE condition, go through AND. For branch
1399 // that stays in loop by FALSE condition, go through OR. Both gives the
1400 // similar logic: "stay in loop iff all conditions are true(false)".
1401 bool Inverted = L->contains(BB: BI->getSuccessor(i: 1));
1402 SmallVector<ICmpInst *, 4> LeafConditions;
1403 SmallVector<Value *, 4> Worklist;
1404 SmallPtrSet<Value *, 4> Visited;
1405 Value *OldCond = BI->getCondition();
1406 Visited.insert(Ptr: OldCond);
1407 Worklist.push_back(Elt: OldCond);
1408
1409 auto GoThrough = [&](Value *V) {
1410 Value *LHS = nullptr, *RHS = nullptr;
1411 if (Inverted) {
1412 if (!match(V, P: m_LogicalOr(L: m_Value(V&: LHS), R: m_Value(V&: RHS))))
1413 return false;
1414 } else {
1415 if (!match(V, P: m_LogicalAnd(L: m_Value(V&: LHS), R: m_Value(V&: RHS))))
1416 return false;
1417 }
1418 if (Visited.insert(Ptr: LHS).second)
1419 Worklist.push_back(Elt: LHS);
1420 if (Visited.insert(Ptr: RHS).second)
1421 Worklist.push_back(Elt: RHS);
1422 return true;
1423 };
1424
1425 do {
1426 Value *Curr = Worklist.pop_back_val();
1427 // Go through AND/OR conditions. Collect leaf ICMPs. We only care about
1428 // those with one use, to avoid instruction duplication.
1429 if (Curr->hasOneUse())
1430 if (!GoThrough(Curr))
1431 if (auto *ICmp = dyn_cast<ICmpInst>(Val: Curr))
1432 LeafConditions.push_back(Elt: ICmp);
1433 } while (!Worklist.empty());
1434
1435 // If the current basic block has the same exit count as the whole loop, and
1436 // it consists of multiple icmp's, try to collect all icmp's that give exact
1437 // same exit count. For all other icmp's, we could use one less iteration,
1438 // because their value on the last iteration doesn't really matter.
1439 SmallPtrSet<ICmpInst *, 4> ICmpsFailingOnLastIter;
1440 if (!SkipLastIter && LeafConditions.size() > 1 &&
1441 SE->getExitCount(L, ExitingBlock: ExitingBB,
1442 Kind: ScalarEvolution::ExitCountKind::SymbolicMaximum) ==
1443 MaxIter)
1444 for (auto *ICmp : LeafConditions) {
1445 auto EL = SE->computeExitLimitFromCond(L, ExitCond: ICmp, ExitIfTrue: Inverted,
1446 /*ControlsExit*/ ControlsOnlyExit: false);
1447 const SCEV *ExitMax = EL.SymbolicMaxNotTaken;
1448 if (isa<SCEVCouldNotCompute>(Val: ExitMax))
1449 continue;
1450 // They could be of different types (specifically this happens after
1451 // IV widening).
1452 auto *WiderType =
1453 SE->getWiderType(Ty1: ExitMax->getType(), Ty2: MaxIter->getType());
1454 const SCEV *WideExitMax = SE->getNoopOrZeroExtend(V: ExitMax, Ty: WiderType);
1455 const SCEV *WideMaxIter = SE->getNoopOrZeroExtend(V: MaxIter, Ty: WiderType);
1456 if (WideExitMax == WideMaxIter)
1457 ICmpsFailingOnLastIter.insert(Ptr: ICmp);
1458 }
1459
1460 bool Changed = false;
1461 for (auto *OldCond : LeafConditions) {
1462 // Skip last iteration for this icmp under one of two conditions:
1463 // - We do it for all conditions;
1464 // - There is another ICmp that would fail on last iter, so this one doesn't
1465 // really matter.
1466 bool OptimisticSkipLastIter = SkipLastIter;
1467 if (!OptimisticSkipLastIter) {
1468 if (ICmpsFailingOnLastIter.size() > 1)
1469 OptimisticSkipLastIter = true;
1470 else if (ICmpsFailingOnLastIter.size() == 1)
1471 OptimisticSkipLastIter = !ICmpsFailingOnLastIter.count(Ptr: OldCond);
1472 }
1473 if (auto Replaced =
1474 createReplacement(ICmp: OldCond, L, ExitingBB, MaxIter, Inverted,
1475 SkipLastIter: OptimisticSkipLastIter, SE, Rewriter)) {
1476 Changed = true;
1477 auto *NewCond = *Replaced;
1478 if (auto *NCI = dyn_cast<Instruction>(Val: NewCond)) {
1479 NCI->setName(OldCond->getName() + ".first_iter");
1480 }
1481 LLVM_DEBUG(dbgs() << "Unknown exit count: Replacing " << *OldCond
1482 << " with " << *NewCond << "\n");
1483 assert(OldCond->hasOneUse() && "Must be!");
1484 OldCond->replaceAllUsesWith(V: NewCond);
1485 DeadInsts.push_back(Elt: OldCond);
1486 // Make sure we no longer consider this condition as failing on last
1487 // iteration.
1488 ICmpsFailingOnLastIter.erase(Ptr: OldCond);
1489 }
1490 }
1491 return Changed;
1492}
1493
1494bool IndVarSimplify::canonicalizeExitCondition(Loop *L) {
1495 // Note: This is duplicating a particular part on SimplifyIndVars reasoning.
1496 // We need to duplicate it because given icmp zext(small-iv), C, IVUsers
1497 // never reaches the icmp since the zext doesn't fold to an AddRec unless
1498 // it already has flags. The alternative to this would be to extending the
1499 // set of "interesting" IV users to include the icmp, but doing that
1500 // regresses results in practice by querying SCEVs before trip counts which
1501 // rely on them which results in SCEV caching sub-optimal answers. The
1502 // concern about caching sub-optimal results is why we only query SCEVs of
1503 // the loop invariant RHS here.
1504 SmallVector<BasicBlock*, 16> ExitingBlocks;
1505 L->getExitingBlocks(ExitingBlocks);
1506 bool Changed = false;
1507 for (auto *ExitingBB : ExitingBlocks) {
1508 auto *BI = dyn_cast<CondBrInst>(Val: ExitingBB->getTerminator());
1509 if (!BI)
1510 continue;
1511
1512 auto *ICmp = dyn_cast<ICmpInst>(Val: BI->getCondition());
1513 if (!ICmp || !ICmp->hasOneUse())
1514 continue;
1515
1516 auto *LHS = ICmp->getOperand(i_nocapture: 0);
1517 auto *RHS = ICmp->getOperand(i_nocapture: 1);
1518 // For the range reasoning, avoid computing SCEVs in the loop to avoid
1519 // poisoning cache with sub-optimal results. For the must-execute case,
1520 // this is a neccessary precondition for correctness.
1521 if (!L->isLoopInvariant(V: RHS)) {
1522 if (!L->isLoopInvariant(V: LHS))
1523 continue;
1524 // Same logic applies for the inverse case
1525 std::swap(a&: LHS, b&: RHS);
1526 }
1527
1528 // Match (icmp signed-cond zext, RHS)
1529 Value *LHSOp = nullptr;
1530 if (!match(V: LHS, P: m_ZExt(Op: m_Value(V&: LHSOp))) || !ICmp->isSigned())
1531 continue;
1532
1533 const unsigned InnerBitWidth = DL.getTypeSizeInBits(Ty: LHSOp->getType());
1534 const unsigned OuterBitWidth = DL.getTypeSizeInBits(Ty: RHS->getType());
1535 auto FullCR = ConstantRange::getFull(BitWidth: InnerBitWidth);
1536 FullCR = FullCR.zeroExtend(BitWidth: OuterBitWidth);
1537 auto RHSCR = SE->getUnsignedRange(S: SE->applyLoopGuards(Expr: SE->getSCEV(V: RHS), L));
1538 if (FullCR.contains(CR: RHSCR)) {
1539 // We have now matched icmp signed-cond zext(X), zext(Y'), and can thus
1540 // replace the signed condition with the unsigned version.
1541 ICmp->setPredicate(ICmp->getUnsignedPredicate());
1542 Changed = true;
1543 // Note: No SCEV invalidation needed. We've changed the predicate, but
1544 // have not changed exit counts, or the values produced by the compare.
1545 continue;
1546 }
1547 }
1548
1549 // Now that we've canonicalized the condition to match the extend,
1550 // see if we can rotate the extend out of the loop.
1551 for (auto *ExitingBB : ExitingBlocks) {
1552 auto *BI = dyn_cast<CondBrInst>(Val: ExitingBB->getTerminator());
1553 if (!BI)
1554 continue;
1555
1556 auto *ICmp = dyn_cast<ICmpInst>(Val: BI->getCondition());
1557 if (!ICmp || !ICmp->hasOneUse() || !ICmp->isUnsigned())
1558 continue;
1559
1560 bool Swapped = false;
1561 auto *LHS = ICmp->getOperand(i_nocapture: 0);
1562 auto *RHS = ICmp->getOperand(i_nocapture: 1);
1563 if (L->isLoopInvariant(V: LHS) == L->isLoopInvariant(V: RHS))
1564 // Nothing to rotate
1565 continue;
1566 if (L->isLoopInvariant(V: LHS)) {
1567 // Same logic applies for the inverse case until we actually pick
1568 // which operand of the compare to update.
1569 Swapped = true;
1570 std::swap(a&: LHS, b&: RHS);
1571 }
1572 assert(!L->isLoopInvariant(LHS) && L->isLoopInvariant(RHS));
1573
1574 // Match (icmp unsigned-cond zext, RHS)
1575 // TODO: Extend to handle corresponding sext/signed-cmp case
1576 // TODO: Extend to other invertible functions
1577 Value *LHSOp = nullptr;
1578 if (!match(V: LHS, P: m_ZExt(Op: m_Value(V&: LHSOp))))
1579 continue;
1580
1581 // In general, we only rotate if we can do so without increasing the number
1582 // of instructions. The exception is when we have an zext(add-rec). The
1583 // reason for allowing this exception is that we know we need to get rid
1584 // of the zext for SCEV to be able to compute a trip count for said loops;
1585 // we consider the new trip count valuable enough to increase instruction
1586 // count by one.
1587 if (!LHS->hasOneUse() && !isa<SCEVAddRecExpr>(Val: SE->getSCEV(V: LHSOp)))
1588 continue;
1589
1590 // Given a icmp unsigned-cond zext(Op) where zext(trunc(RHS)) == RHS
1591 // replace with an icmp of the form icmp unsigned-cond Op, trunc(RHS)
1592 // when zext is loop varying and RHS is loop invariant. This converts
1593 // loop varying work to loop-invariant work.
1594 auto doRotateTransform = [&]() {
1595 assert(ICmp->isUnsigned() && "must have proven unsigned already");
1596 auto *NewRHS = CastInst::Create(
1597 Instruction::Trunc, S: RHS, Ty: LHSOp->getType(), Name: "",
1598 InsertBefore: L->getLoopPreheader()->getTerminator()->getIterator());
1599 // NewRHS is an operation that has been hoisted out of the loop, and
1600 // therefore should have a dropped location.
1601 NewRHS->setDebugLoc(DebugLoc::getDropped());
1602 ICmp->setOperand(i_nocapture: Swapped ? 1 : 0, Val_nocapture: LHSOp);
1603 ICmp->setOperand(i_nocapture: Swapped ? 0 : 1, Val_nocapture: NewRHS);
1604 // Samesign flag cannot be preserved after narrowing the compare.
1605 ICmp->setSameSign(false);
1606 if (LHS->use_empty())
1607 DeadInsts.push_back(Elt: LHS);
1608 };
1609
1610 const unsigned InnerBitWidth = DL.getTypeSizeInBits(Ty: LHSOp->getType());
1611 const unsigned OuterBitWidth = DL.getTypeSizeInBits(Ty: RHS->getType());
1612 auto FullCR = ConstantRange::getFull(BitWidth: InnerBitWidth);
1613 FullCR = FullCR.zeroExtend(BitWidth: OuterBitWidth);
1614 auto RHSCR = SE->getUnsignedRange(S: SE->applyLoopGuards(Expr: SE->getSCEV(V: RHS), L));
1615 if (FullCR.contains(CR: RHSCR)) {
1616 doRotateTransform();
1617 Changed = true;
1618 // Note, we are leaving SCEV in an unfortunately imprecise case here
1619 // as rotation tends to reveal information about trip counts not
1620 // previously visible.
1621 continue;
1622 }
1623 }
1624
1625 return Changed;
1626}
1627
1628bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) {
1629 SmallVector<BasicBlock*, 16> ExitingBlocks;
1630 L->getExitingBlocks(ExitingBlocks);
1631
1632 // Remove all exits which aren't both rewriteable and execute on every
1633 // iteration.
1634 llvm::erase_if(C&: ExitingBlocks, P: [&](BasicBlock *ExitingBB) {
1635 // If our exitting block exits multiple loops, we can only rewrite the
1636 // innermost one. Otherwise, we're changing how many times the innermost
1637 // loop runs before it exits.
1638 if (LI->getLoopFor(BB: ExitingBB) != L)
1639 return true;
1640
1641 // Can't rewrite non-branch yet.
1642 CondBrInst *BI = dyn_cast<CondBrInst>(Val: ExitingBB->getTerminator());
1643 if (!BI)
1644 return true;
1645
1646 // Likewise, the loop latch must be dominated by the exiting BB.
1647 if (!DT->dominates(A: ExitingBB, B: L->getLoopLatch()))
1648 return true;
1649
1650 if (auto *CI = dyn_cast<ConstantInt>(Val: BI->getCondition())) {
1651 // If already constant, nothing to do. However, if this is an
1652 // unconditional exit, we can still replace header phis with their
1653 // preheader value.
1654 if (!L->contains(BB: BI->getSuccessor(i: CI->isNullValue())))
1655 replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, SE&: *SE);
1656 return true;
1657 }
1658
1659 return false;
1660 });
1661
1662 if (ExitingBlocks.empty())
1663 return false;
1664
1665 // Get a symbolic upper bound on the loop backedge taken count.
1666 const SCEV *MaxBECount = SE->getSymbolicMaxBackedgeTakenCount(L);
1667 if (isa<SCEVCouldNotCompute>(Val: MaxBECount))
1668 return false;
1669
1670 // Visit our exit blocks in order of dominance. We know from the fact that
1671 // all exits must dominate the latch, so there is a total dominance order
1672 // between them.
1673 llvm::sort(C&: ExitingBlocks, Comp: [&](BasicBlock *A, BasicBlock *B) {
1674 // std::sort sorts in ascending order, so we want the inverse of
1675 // the normal dominance relation.
1676 if (A == B) return false;
1677 if (DT->properlyDominates(A, B))
1678 return true;
1679 else {
1680 assert(DT->properlyDominates(B, A) &&
1681 "expected total dominance order!");
1682 return false;
1683 }
1684 });
1685#ifdef ASSERT
1686 for (unsigned i = 1; i < ExitingBlocks.size(); i++) {
1687 assert(DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]));
1688 }
1689#endif
1690
1691 bool Changed = false;
1692 bool SkipLastIter = false;
1693 const SCEV *CurrMaxExit = SE->getCouldNotCompute();
1694 auto UpdateSkipLastIter = [&](const SCEV *MaxExitCount) {
1695 if (SkipLastIter || isa<SCEVCouldNotCompute>(Val: MaxExitCount))
1696 return;
1697 if (isa<SCEVCouldNotCompute>(Val: CurrMaxExit))
1698 CurrMaxExit = MaxExitCount;
1699 else
1700 CurrMaxExit = SE->getUMinFromMismatchedTypes(LHS: CurrMaxExit, RHS: MaxExitCount);
1701 // If the loop has more than 1 iteration, all further checks will be
1702 // executed 1 iteration less.
1703 if (CurrMaxExit == MaxBECount)
1704 SkipLastIter = true;
1705 };
1706 SmallPtrSet<const SCEV *, 8> DominatingExactExitCounts;
1707 for (BasicBlock *ExitingBB : ExitingBlocks) {
1708 const SCEV *ExactExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB);
1709 const SCEV *MaxExitCount = SE->getExitCount(
1710 L, ExitingBlock: ExitingBB, Kind: ScalarEvolution::ExitCountKind::SymbolicMaximum);
1711 if (isa<SCEVCouldNotCompute>(Val: ExactExitCount)) {
1712 // Okay, we do not know the exit count here. Can we at least prove that it
1713 // will remain the same within iteration space?
1714 auto *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1715 auto OptimizeCond = [&](bool SkipLastIter) {
1716 return optimizeLoopExitWithUnknownExitCount(L, BI, ExitingBB,
1717 MaxIter: MaxBECount, SkipLastIter,
1718 SE, Rewriter, DeadInsts);
1719 };
1720
1721 // TODO: We might have proved that we can skip the last iteration for
1722 // this check. In this case, we only want to check the condition on the
1723 // pre-last iteration (MaxBECount - 1). However, there is a nasty
1724 // corner case:
1725 //
1726 // for (i = len; i != 0; i--) { ... check (i ult X) ... }
1727 //
1728 // If we could not prove that len != 0, then we also could not prove that
1729 // (len - 1) is not a UINT_MAX. If we simply query (len - 1), then
1730 // OptimizeCond will likely not prove anything for it, even if it could
1731 // prove the same fact for len.
1732 //
1733 // As a temporary solution, we query both last and pre-last iterations in
1734 // hope that we will be able to prove triviality for at least one of
1735 // them. We can stop querying MaxBECount for this case once SCEV
1736 // understands that (MaxBECount - 1) will not overflow here.
1737 if (OptimizeCond(false))
1738 Changed = true;
1739 else if (SkipLastIter && OptimizeCond(true))
1740 Changed = true;
1741 UpdateSkipLastIter(MaxExitCount);
1742 continue;
1743 }
1744
1745 UpdateSkipLastIter(ExactExitCount);
1746
1747 // If we know we'd exit on the first iteration, rewrite the exit to
1748 // reflect this. This does not imply the loop must exit through this
1749 // exit; there may be an earlier one taken on the first iteration.
1750 // We know that the backedge can't be taken, so we replace all
1751 // the header PHIs with values coming from the preheader.
1752 if (ExactExitCount->isZero()) {
1753 foldExit(L, ExitingBB, IsTaken: true, DeadInsts);
1754 replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, SE&: *SE);
1755 Changed = true;
1756 continue;
1757 }
1758
1759 assert(ExactExitCount->getType()->isIntegerTy() &&
1760 MaxBECount->getType()->isIntegerTy() &&
1761 "Exit counts must be integers");
1762
1763 Type *WiderType =
1764 SE->getWiderType(Ty1: MaxBECount->getType(), Ty2: ExactExitCount->getType());
1765 ExactExitCount = SE->getNoopOrZeroExtend(V: ExactExitCount, Ty: WiderType);
1766 MaxBECount = SE->getNoopOrZeroExtend(V: MaxBECount, Ty: WiderType);
1767 assert(MaxBECount->getType() == ExactExitCount->getType());
1768
1769 // Can we prove that some other exit must be taken strictly before this
1770 // one?
1771 if (SE->isLoopEntryGuardedByCond(L, Pred: CmpInst::ICMP_ULT, LHS: MaxBECount,
1772 RHS: ExactExitCount)) {
1773 foldExit(L, ExitingBB, IsTaken: false, DeadInsts);
1774 Changed = true;
1775 continue;
1776 }
1777
1778 // As we run, keep track of which exit counts we've encountered. If we
1779 // find a duplicate, we've found an exit which would have exited on the
1780 // exiting iteration, but (from the visit order) strictly follows another
1781 // which does the same and is thus dead.
1782 if (!DominatingExactExitCounts.insert(Ptr: ExactExitCount).second) {
1783 foldExit(L, ExitingBB, IsTaken: false, DeadInsts);
1784 Changed = true;
1785 continue;
1786 }
1787
1788 // TODO: There might be another oppurtunity to leverage SCEV's reasoning
1789 // here. If we kept track of the min of dominanting exits so far, we could
1790 // discharge exits with EC >= MDEC. This is less powerful than the existing
1791 // transform (since later exits aren't considered), but potentially more
1792 // powerful for any case where SCEV can prove a >=u b, but neither a == b
1793 // or a >u b. Such a case is not currently known.
1794 }
1795 return Changed;
1796}
1797
1798static bool crashingBBWithoutEffect(const BasicBlock &BB) {
1799 return llvm::all_of(Range: BB, P: [](const Instruction &I) {
1800 // TODO: for now this is overly restrictive, to make sure nothing in this
1801 // BB can depend on the loop body.
1802 // It's not enough to check for !I.mayHaveSideEffects(), because e.g. a
1803 // load does not have a side effect, but we could have
1804 // %a = load ptr, ptr %ptr
1805 // %b = load i32, ptr %a
1806 // Now if the loop stored a non-nullptr to %a, we could cause a nullptr
1807 // dereference by skipping over loop iterations.
1808 if (const auto *CB = dyn_cast<CallBase>(Val: &I)) {
1809 if (CB->onlyAccessesInaccessibleMemory())
1810 return true;
1811 }
1812 return isa<UnreachableInst>(Val: I);
1813 });
1814}
1815
1816bool IndVarSimplify::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) {
1817 SmallVector<BasicBlock*, 16> ExitingBlocks;
1818 L->getExitingBlocks(ExitingBlocks);
1819
1820 // Finally, see if we can rewrite our exit conditions into a loop invariant
1821 // form. If we have a read-only loop, and we can tell that we must exit down
1822 // a path which does not need any of the values computed within the loop, we
1823 // can rewrite the loop to exit on the first iteration. Note that this
1824 // doesn't either a) tell us the loop exits on the first iteration (unless
1825 // *all* exits are predicateable) or b) tell us *which* exit might be taken.
1826 // This transformation looks a lot like a restricted form of dead loop
1827 // elimination, but restricted to read-only loops and without neccesssarily
1828 // needing to kill the loop entirely.
1829 if (!Opts.indvars_predicate_loops)
1830 return false;
1831
1832 // Note: ExactBTC is the exact backedge taken count *iff* the loop exits
1833 // through *explicit* control flow. We have to eliminate the possibility of
1834 // implicit exits (see below) before we know it's truly exact.
1835 const SCEV *ExactBTC = SE->getBackedgeTakenCount(L);
1836 if (isa<SCEVCouldNotCompute>(Val: ExactBTC) || !Rewriter.isSafeToExpand(S: ExactBTC))
1837 return false;
1838
1839 assert(SE->isLoopInvariant(ExactBTC, L) && "BTC must be loop invariant");
1840 assert(ExactBTC->getType()->isIntegerTy() && "BTC must be integer");
1841
1842 auto BadExit = [&](BasicBlock *ExitingBB) {
1843 // If our exiting block exits multiple loops, we can only rewrite the
1844 // innermost one. Otherwise, we're changing how many times the innermost
1845 // loop runs before it exits.
1846 if (LI->getLoopFor(BB: ExitingBB) != L)
1847 return true;
1848
1849 // Can't rewrite non-branch yet.
1850 CondBrInst *BI = dyn_cast<CondBrInst>(Val: ExitingBB->getTerminator());
1851 if (!BI)
1852 return true;
1853
1854 // If already constant, nothing to do.
1855 if (isa<Constant>(Val: BI->getCondition()))
1856 return true;
1857
1858 // If the exit block has phis, we need to be able to compute the values
1859 // within the loop which contains them. This assumes trivially lcssa phis
1860 // have already been removed; TODO: generalize
1861 BasicBlock *ExitBlock =
1862 BI->getSuccessor(i: L->contains(BB: BI->getSuccessor(i: 0)) ? 1 : 0);
1863 if (!ExitBlock->phis().empty())
1864 return true;
1865
1866 const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB);
1867 if (isa<SCEVCouldNotCompute>(Val: ExitCount) ||
1868 !Rewriter.isSafeToExpand(S: ExitCount))
1869 return true;
1870
1871 assert(SE->isLoopInvariant(ExitCount, L) &&
1872 "Exit count must be loop invariant");
1873 assert(ExitCount->getType()->isIntegerTy() && "Exit count must be integer");
1874 return false;
1875 };
1876
1877 // Make sure all exits dominate the latch. This means there is a linear chain
1878 // of exits. We check this before sorting so we have a total order.
1879 BasicBlock *Latch = L->getLoopLatch();
1880 for (BasicBlock *ExitingBB : ExitingBlocks)
1881 if (!DT->dominates(A: ExitingBB, B: Latch))
1882 return false;
1883
1884 // If we have any exits which can't be predicated themselves, than we can't
1885 // predicate any exit which isn't guaranteed to execute before it. Consider
1886 // two exits (a) and (b) which would both exit on the same iteration. If we
1887 // can predicate (b), but not (a), and (a) preceeds (b) along some path, then
1888 // we could convert a loop from exiting through (a) to one exiting through
1889 // (b). Note that this problem exists only for exits with the same exit
1890 // count, and we could be more aggressive when exit counts are known inequal.
1891 llvm::sort(C&: ExitingBlocks, Comp: [&](BasicBlock *A, BasicBlock *B) {
1892 // llvm::sort sorts in ascending order, so we want the inverse of
1893 // the normal dominance relation.
1894 if (A == B)
1895 return false;
1896 if (DT->properlyDominates(A, B))
1897 return true;
1898 if (DT->properlyDominates(A: B, B: A))
1899 return false;
1900 llvm_unreachable("Should have total dominance order");
1901 });
1902
1903 // Make sure our exit blocks are really a total order (i.e. a linear chain of
1904 // exits before the backedge).
1905 for (unsigned i = 1; i < ExitingBlocks.size(); i++)
1906 assert(DT->dominates(ExitingBlocks[i - 1], ExitingBlocks[i]) &&
1907 "Not sorted by dominance");
1908
1909 // Given our sorted total order, we know that exit[j] must be evaluated
1910 // after all exit[i] such j > i.
1911 for (unsigned i = 0, e = ExitingBlocks.size(); i < e; i++)
1912 if (BadExit(ExitingBlocks[i])) {
1913 ExitingBlocks.resize(N: i);
1914 break;
1915 }
1916
1917 if (ExitingBlocks.empty())
1918 return false;
1919
1920 // Predication may skip iterations of L, which is only safe if none of them
1921 // would run forever. Calls that may not return are rejected below.
1922 if (!isLoopNestFinite(L, SE&: *SE, LI: *LI))
1923 return false;
1924
1925 // At this point, ExitingBlocks consists of only those blocks which are
1926 // predicatable. Given that, we know we have at least one exit we can
1927 // predicate if the loop is doesn't have side effects and doesn't have any
1928 // implicit exits (because then our exact BTC isn't actually exact).
1929 // @Reviewers - As structured, this is O(I^2) for loop nests. Any
1930 // suggestions on how to improve this? I can obviously bail out for outer
1931 // loops, but that seems less than ideal. MemorySSA can find memory writes,
1932 // is that enough for *all* side effects?
1933 bool HasThreadLocalSideEffects = false;
1934 for (BasicBlock *BB : L->blocks())
1935 for (auto &I : *BB) {
1936 // TODO:isGuaranteedToTransfer
1937 if (I.mayHaveSideEffects()) {
1938 if (!Opts.indvars_predicate_loop_traps)
1939 return false;
1940 HasThreadLocalSideEffects = true;
1941 if (StoreInst *SI = dyn_cast<StoreInst>(Val: &I)) {
1942 // Simple stores cannot be observed by other threads.
1943 // If HasThreadLocalSideEffects is set, we check
1944 // crashingBBWithoutEffect to make sure that the crashing BB cannot
1945 // observe them either.
1946 if (!SI->isSimple())
1947 return false;
1948 } else {
1949 return false;
1950 }
1951 }
1952
1953 // Skip if the loop has tokens referenced outside the loop to avoid
1954 // changing convergence behavior.
1955 if (I.getType()->isTokenTy()) {
1956 for (User *U : I.users()) {
1957 Instruction *UserInst = dyn_cast<Instruction>(Val: U);
1958 if (UserInst && !L->contains(Inst: UserInst)) {
1959 return false;
1960 }
1961 }
1962 }
1963 }
1964
1965 bool Changed = false;
1966 // Finally, do the actual predication for all predicatable blocks. A couple
1967 // of notes here:
1968 // 1) We don't bother to constant fold dominated exits with identical exit
1969 // counts; that's simply a form of CSE/equality propagation and we leave
1970 // it for dedicated passes.
1971 // 2) We insert the comparison at the branch. Hoisting introduces additional
1972 // legality constraints and we leave that to dedicated logic. We want to
1973 // predicate even if we can't insert a loop invariant expression as
1974 // peeling or unrolling will likely reduce the cost of the otherwise loop
1975 // varying check.
1976 Rewriter.setInsertPoint(L->getLoopPreheader()->getTerminator());
1977 IRBuilder<> B(L->getLoopPreheader()->getTerminator());
1978 Value *ExactBTCV = nullptr; // Lazily generated if needed.
1979 for (BasicBlock *ExitingBB : ExitingBlocks) {
1980 const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB);
1981
1982 auto *BI = cast<CondBrInst>(Val: ExitingBB->getTerminator());
1983 if (HasThreadLocalSideEffects) {
1984 const BasicBlock *Unreachable = nullptr;
1985 for (const BasicBlock *Succ : BI->successors()) {
1986 if (isa<UnreachableInst>(Val: Succ->getTerminator()))
1987 Unreachable = Succ;
1988 }
1989 // Exit BB which have one branch back into the loop and another one to
1990 // a trap can still be optimized, because local side effects cannot
1991 // be observed in the exit case (the trap). We could be smarter about
1992 // this, but for now lets pattern match common cases that directly trap.
1993 if (Unreachable == nullptr || !crashingBBWithoutEffect(BB: *Unreachable))
1994 return Changed;
1995 }
1996 Value *NewCond;
1997 if (ExitCount == ExactBTC) {
1998 NewCond = L->contains(BB: BI->getSuccessor(i: 0)) ?
1999 B.getFalse() : B.getTrue();
2000 } else {
2001 Value *ECV = Rewriter.expandCodeFor(SH: ExitCount);
2002 if (!ExactBTCV)
2003 ExactBTCV = Rewriter.expandCodeFor(SH: ExactBTC);
2004 Value *RHS = ExactBTCV;
2005 if (ECV->getType() != RHS->getType()) {
2006 Type *WiderTy = SE->getWiderType(Ty1: ECV->getType(), Ty2: RHS->getType());
2007 ECV = B.CreateZExt(V: ECV, DestTy: WiderTy);
2008 RHS = B.CreateZExt(V: RHS, DestTy: WiderTy);
2009 }
2010 auto Pred = L->contains(BB: BI->getSuccessor(i: 0)) ?
2011 ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
2012 NewCond = B.CreateICmp(P: Pred, LHS: ECV, RHS);
2013 }
2014 Value *OldCond = BI->getCondition();
2015 BI->setCondition(NewCond);
2016 if (OldCond->use_empty())
2017 DeadInsts.emplace_back(Args&: OldCond);
2018 Changed = true;
2019 RunUnswitching = true;
2020 }
2021
2022 return Changed;
2023}
2024
2025//===----------------------------------------------------------------------===//
2026// IndVarSimplify driver. Manage several subpasses of IV simplification.
2027//===----------------------------------------------------------------------===//
2028
2029bool IndVarSimplify::run(Loop *L) {
2030 // We need (and expect!) the incoming loop to be in LCSSA.
2031 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2032 "LCSSA required to run indvars!");
2033
2034 // If LoopSimplify form is not available, stay out of trouble. Some notes:
2035 // - LSR currently only supports LoopSimplify-form loops. Indvars'
2036 // canonicalization can be a pessimization without LSR to "clean up"
2037 // afterwards.
2038 // - We depend on having a preheader; in particular,
2039 // Loop::getCanonicalInductionVariable only supports loops with preheaders,
2040 // and we're in trouble if we can't find the induction variable even when
2041 // we've manually inserted one.
2042 // - LFTR relies on having a single backedge.
2043 if (!L->isLoopSimplifyForm())
2044 return false;
2045
2046 bool Changed = false;
2047 // If there are any floating-point recurrences, attempt to
2048 // transform them to use integer recurrences.
2049 Changed |= rewriteNonIntegerIVs(L);
2050
2051 // Create a rewriter object which we'll use to transform the code with.
2052 SCEVExpander Rewriter(*SE, "indvars");
2053#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2054 Rewriter.setDebugType(DEBUG_TYPE);
2055#endif
2056
2057 // Eliminate redundant IV users.
2058 //
2059 // Simplification works best when run before other consumers of SCEV. We
2060 // attempt to avoid evaluating SCEVs for sign/zero extend operations until
2061 // other expressions involving loop IVs have been evaluated. This helps SCEV
2062 // set no-wrap flags before normalizing sign/zero extension.
2063 Rewriter.disableCanonicalMode();
2064 Changed |= simplifyAndExtend(L, Rewriter, LI);
2065
2066 // Check to see if we can compute the final value of any expressions
2067 // that are recurrent in the loop, and substitute the exit values from the
2068 // loop into any instructions outside of the loop that use the final values
2069 // of the current expressions.
2070 if (Opts.replexitval != NeverRepl) {
2071 if (int Rewrites = rewriteLoopExitValues(L, LI, TLI, SE, TTI, Rewriter, DT,
2072 ReplaceExitValue: Opts.replexitval, DeadInsts)) {
2073 NumReplaced += Rewrites;
2074 Changed = true;
2075 }
2076 }
2077
2078 // Eliminate redundant IV cycles.
2079 NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts, TTI);
2080
2081 // Try to convert exit conditions to unsigned and rotate computation
2082 // out of the loop. Note: Handles invalidation internally if needed.
2083 Changed |= canonicalizeExitCondition(L);
2084
2085 // Try to eliminate loop exits based on analyzeable exit counts
2086 if (optimizeLoopExits(L, Rewriter)) {
2087 Changed = true;
2088 // Given we've changed exit counts, notify SCEV
2089 // Some nested loops may share same folded exit basic block,
2090 // thus we need to notify top most loop.
2091 SE->forgetTopmostLoop(L);
2092 }
2093
2094 // Try to form loop invariant tests for loop exits by changing how many
2095 // iterations of the loop run when that is unobservable.
2096 if (predicateLoopExits(L, Rewriter)) {
2097 Changed = true;
2098 // Given we've changed exit counts, notify SCEV
2099 SE->forgetLoop(L);
2100 }
2101
2102 // If we have a trip count expression, rewrite the loop's exit condition
2103 // using it.
2104 if (!Opts.disable_lftr) {
2105 BasicBlock *PreHeader = L->getLoopPreheader();
2106
2107 SmallVector<BasicBlock*, 16> ExitingBlocks;
2108 L->getExitingBlocks(ExitingBlocks);
2109 for (BasicBlock *ExitingBB : ExitingBlocks) {
2110 // Can't rewrite non-branch yet.
2111 if (!isa<CondBrInst>(Val: ExitingBB->getTerminator()))
2112 continue;
2113
2114 // If our exitting block exits multiple loops, we can only rewrite the
2115 // innermost one. Otherwise, we're changing how many times the innermost
2116 // loop runs before it exits.
2117 if (LI->getLoopFor(BB: ExitingBB) != L)
2118 continue;
2119
2120 if (!needsLFTR(L, ExitingBB))
2121 continue;
2122
2123 const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB);
2124 if (isa<SCEVCouldNotCompute>(Val: ExitCount))
2125 continue;
2126
2127 // This was handled above, but as we form SCEVs, we can sometimes refine
2128 // existing ones; this allows exit counts to be folded to zero which
2129 // weren't when optimizeLoopExits saw them. Arguably, we should iterate
2130 // until stable to handle cases like this better.
2131 if (ExitCount->isZero())
2132 continue;
2133
2134 PHINode *IndVar = FindLoopCounter(L, ExitingBB, BECount: ExitCount, SE, DT);
2135 if (!IndVar)
2136 continue;
2137
2138 // Avoid high cost expansions. Note: This heuristic is questionable in
2139 // that our definition of "high cost" is not exactly principled.
2140 if (Rewriter.isHighCostExpansion(Exprs: ExitCount, L, Budget: SCEVCheapExpansionBudget,
2141 TTI, At: PreHeader->getTerminator()))
2142 continue;
2143
2144 if (!Rewriter.isSafeToExpand(S: ExitCount))
2145 continue;
2146
2147 Changed |= linearFunctionTestReplace(L, ExitingBB,
2148 ExitCount, IndVar,
2149 Rewriter);
2150 }
2151 }
2152 // Clear the rewriter cache, because values that are in the rewriter's cache
2153 // can be deleted in the loop below, causing the AssertingVH in the cache to
2154 // trigger.
2155 Rewriter.clear();
2156
2157 // Now that we're done iterating through lists, clean up any instructions
2158 // which are now dead.
2159 while (!DeadInsts.empty()) {
2160 Value *V = DeadInsts.pop_back_val();
2161
2162 if (PHINode *PHI = dyn_cast_or_null<PHINode>(Val: V))
2163 Changed |= RecursivelyDeleteDeadPHINode(PN: PHI, TLI, MSSAU: MSSAU.get());
2164 else if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: V))
2165 Changed |=
2166 RecursivelyDeleteTriviallyDeadInstructions(V: Inst, TLI, MSSAU: MSSAU.get());
2167 }
2168
2169 // The Rewriter may not be used from this point on.
2170
2171 // Loop-invariant instructions in the preheader that aren't used in the
2172 // loop may be sunk below the loop to reduce register pressure.
2173 Changed |= sinkUnusedInvariants(L);
2174
2175 // rewriteFirstIterationLoopExitValues does not rely on the computation of
2176 // trip count and therefore can further simplify exit values in addition to
2177 // rewriteLoopExitValues.
2178 Changed |= rewriteFirstIterationLoopExitValues(L);
2179
2180 // Clean up dead instructions.
2181 Changed |= DeleteDeadPHIs(BB: L->getHeader(), TLI, MSSAU: MSSAU.get());
2182
2183 // Check a post-condition.
2184 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2185 "Indvars did not preserve LCSSA!");
2186 if (VerifyMemorySSA && MSSAU)
2187 MSSAU->getMemorySSA()->verifyMemorySSA();
2188
2189 return Changed;
2190}
2191
2192PreservedAnalyses IndVarSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
2193 LoopStandardAnalysisResults &AR,
2194 LPMUpdater &) {
2195 Function *F = L.getHeader()->getParent();
2196 const DataLayout &DL = F->getDataLayout();
2197 const ScalarOptions &Opts = getScalarOptions(F: *F);
2198
2199 IndVarSimplify IVS(Opts, &AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI,
2200 AR.MSSA, WidenIndVars && Opts.indvars_widen_indvars);
2201 if (!IVS.run(L: &L))
2202 return PreservedAnalyses::all();
2203
2204 auto PA = getLoopPassPreservedAnalyses();
2205 PA.preserveSet<CFGAnalyses>();
2206 if (IVS.runUnswitching()) {
2207 AM.getResult<ShouldRunExtraSimpleLoopUnswitch>(IR&: L, ExtraArgs&: AR);
2208 PA.preserve<ShouldRunExtraSimpleLoopUnswitch>();
2209 }
2210
2211 if (AR.MSSA)
2212 PA.preserve<MemorySSAAnalysis>();
2213 return PA;
2214}
2215