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