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