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