1//===- InductiveRangeCheckElimination.cpp - -------------------------------===//
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// The InductiveRangeCheckElimination pass splits a loop's iteration space into
10// three disjoint ranges. It does that in a way such that the loop running in
11// the middle loop provably does not need range checks. As an example, it will
12// convert
13//
14// len = < known positive >
15// for (i = 0; i < n; i++) {
16// if (0 <= i && i < len) {
17// do_something();
18// } else {
19// throw_out_of_bounds();
20// }
21// }
22//
23// to
24//
25// len = < known positive >
26// limit = smin(n, len)
27// // no first segment
28// for (i = 0; i < limit; i++) {
29// if (0 <= i && i < len) { // this check is fully redundant
30// do_something();
31// } else {
32// throw_out_of_bounds();
33// }
34// }
35// for (i = limit; i < n; i++) {
36// if (0 <= i && i < len) {
37// do_something();
38// } else {
39// throw_out_of_bounds();
40// }
41// }
42//
43//===----------------------------------------------------------------------===//
44
45#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
46#include "llvm/ADT/APInt.h"
47#include "llvm/ADT/ArrayRef.h"
48#include "llvm/ADT/PriorityWorklist.h"
49#include "llvm/ADT/SmallPtrSet.h"
50#include "llvm/ADT/SmallVector.h"
51#include "llvm/ADT/StringRef.h"
52#include "llvm/ADT/Twine.h"
53#include "llvm/Analysis/BlockFrequencyInfo.h"
54#include "llvm/Analysis/BranchProbabilityInfo.h"
55#include "llvm/Analysis/LoopAnalysisManager.h"
56#include "llvm/Analysis/LoopInfo.h"
57#include "llvm/Analysis/ScalarEvolution.h"
58#include "llvm/Analysis/ScalarEvolutionExpressions.h"
59#include "llvm/IR/BasicBlock.h"
60#include "llvm/IR/CFG.h"
61#include "llvm/IR/Constants.h"
62#include "llvm/IR/DerivedTypes.h"
63#include "llvm/IR/Dominators.h"
64#include "llvm/IR/Function.h"
65#include "llvm/IR/IRBuilder.h"
66#include "llvm/IR/InstrTypes.h"
67#include "llvm/IR/Instructions.h"
68#include "llvm/IR/Metadata.h"
69#include "llvm/IR/Module.h"
70#include "llvm/IR/PatternMatch.h"
71#include "llvm/IR/Type.h"
72#include "llvm/IR/Use.h"
73#include "llvm/IR/User.h"
74#include "llvm/IR/Value.h"
75#include "llvm/Support/BranchProbability.h"
76#include "llvm/Support/Casting.h"
77#include "llvm/Support/CommandLine.h"
78#include "llvm/Support/Compiler.h"
79#include "llvm/Support/Debug.h"
80#include "llvm/Support/ErrorHandling.h"
81#include "llvm/Support/raw_ostream.h"
82#include "llvm/Transforms/Utils/BasicBlockUtils.h"
83#include "llvm/Transforms/Utils/Cloning.h"
84#include "llvm/Transforms/Utils/LoopConstrainer.h"
85#include "llvm/Transforms/Utils/LoopSimplify.h"
86#include "llvm/Transforms/Utils/LoopUtils.h"
87#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
88#include "llvm/Transforms/Utils/ValueMapper.h"
89#include <algorithm>
90#include <cassert>
91#include <iterator>
92#include <optional>
93#include <utility>
94
95using namespace llvm;
96using namespace llvm::PatternMatch;
97
98static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
99 cl::init(Val: 64));
100
101static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
102 cl::init(Val: false));
103
104static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
105 cl::init(Val: false));
106
107static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
108 cl::Hidden, cl::init(Val: false));
109
110static cl::opt<unsigned> MinRuntimeIterations("irce-min-runtime-iterations",
111 cl::Hidden, cl::init(Val: 10));
112
113static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
114 cl::Hidden, cl::init(Val: true));
115
116static cl::opt<bool> AllowNarrowLatchCondition(
117 "irce-allow-narrow-latch", cl::Hidden, cl::init(Val: true),
118 cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
119 "with narrow latch condition."));
120
121static cl::opt<unsigned> MaxTypeSizeForOverflowCheck(
122 "irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(Val: 32),
123 cl::desc(
124 "Maximum size of range check type for which can be produced runtime "
125 "overflow check of its limit's computation"));
126
127static cl::opt<bool>
128 PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks",
129 cl::Hidden, cl::init(Val: false));
130
131#define DEBUG_TYPE "irce"
132
133namespace {
134
135/// An inductive range check is conditional branch in a loop with
136///
137/// 1. a very cold successor (i.e. the branch jumps to that successor very
138/// rarely)
139///
140/// and
141///
142/// 2. a condition that is provably true for some contiguous range of values
143/// taken by the containing loop's induction variable.
144///
145class InductiveRangeCheck {
146
147 const SCEV *Begin = nullptr;
148 const SCEV *Step = nullptr;
149 const SCEV *End = nullptr;
150 Use *CheckUse = nullptr;
151
152 static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
153 const SCEVAddRecExpr *&Index,
154 const SCEV *&End);
155
156 static void
157 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
158 SmallVectorImpl<InductiveRangeCheck> &Checks,
159 SmallPtrSetImpl<Value *> &Visited);
160
161 static bool parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
162 ICmpInst::Predicate Pred, ScalarEvolution &SE,
163 const SCEVAddRecExpr *&Index,
164 const SCEV *&End);
165
166 static bool reassociateSubLHS(Loop *L, Value *VariantLHS, Value *InvariantRHS,
167 ICmpInst::Predicate Pred, ScalarEvolution &SE,
168 const SCEVAddRecExpr *&Index, const SCEV *&End);
169
170public:
171 const SCEV *getBegin() const { return Begin; }
172 const SCEV *getStep() const { return Step; }
173 const SCEV *getEnd() const { return End; }
174
175 void print(raw_ostream &OS) const {
176 OS << "InductiveRangeCheck:\n";
177 OS << " Begin: ";
178 Begin->print(OS);
179 OS << " Step: ";
180 Step->print(OS);
181 OS << " End: ";
182 End->print(OS);
183 OS << "\n CheckUse: ";
184 getCheckUse()->getUser()->print(O&: OS);
185 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
186 }
187
188 LLVM_DUMP_METHOD
189 void dump() {
190 print(OS&: dbgs());
191 }
192
193 Use *getCheckUse() const { return CheckUse; }
194
195 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
196 /// R.getEnd() le R.getBegin(), then R denotes the empty range.
197
198 class Range {
199 const SCEV *Begin;
200 const SCEV *End;
201
202 public:
203 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
204 assert(Begin->getType() == End->getType() && "ill-typed range!");
205 }
206
207 Type *getType() const { return Begin->getType(); }
208 const SCEV *getBegin() const { return Begin; }
209 const SCEV *getEnd() const { return End; }
210 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
211 if (Begin == End)
212 return true;
213 if (IsSigned)
214 return SE.isKnownPredicate(Pred: ICmpInst::ICMP_SGE, LHS: Begin, RHS: End);
215 else
216 return SE.isKnownPredicate(Pred: ICmpInst::ICMP_UGE, LHS: Begin, RHS: End);
217 }
218 };
219
220 /// This is the value the condition of the branch needs to evaluate to for the
221 /// branch to take the hot successor (see (1) above).
222 bool getPassingDirection() { return true; }
223
224 /// Computes a range for the induction variable (IndVar) in which the range
225 /// check is redundant and can be constant-folded away. The induction
226 /// variable is not required to be the canonical {0,+,1} induction variable.
227 std::optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
228 const SCEVAddRecExpr *IndVar,
229 bool IsLatchSigned) const;
230
231 /// Parse out a set of inductive range checks from \p BI and append them to \p
232 /// Checks.
233 ///
234 /// NB! There may be conditions feeding into \p BI that aren't inductive range
235 /// checks, and hence don't end up in \p Checks.
236 static void extractRangeChecksFromBranch(
237 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
238 SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed);
239};
240
241class InductiveRangeCheckElimination {
242 ScalarEvolution &SE;
243 BranchProbabilityInfo *BPI;
244 DominatorTree &DT;
245 LoopInfo &LI;
246
247 using GetBFIFunc =
248 std::optional<llvm::function_ref<llvm::BlockFrequencyInfo &()>>;
249 GetBFIFunc GetBFI;
250
251 // Returns true if it is profitable to do a transform basing on estimation of
252 // number of iterations.
253 bool isProfitableToTransform(const Loop &L, LoopStructure &LS);
254
255public:
256 InductiveRangeCheckElimination(ScalarEvolution &SE,
257 BranchProbabilityInfo *BPI, DominatorTree &DT,
258 LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
259 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
260
261 bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
262};
263
264} // end anonymous namespace
265
266/// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
267/// be interpreted as a range check, return false. Otherwise set `Index` to the
268/// SCEV being range checked, and set `End` to the upper or lower limit `Index`
269/// is being range checked.
270bool InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
271 ScalarEvolution &SE,
272 const SCEVAddRecExpr *&Index,
273 const SCEV *&End) {
274 auto IsLoopInvariant = [&SE, L](Value *V) {
275 return SE.isLoopInvariant(S: SE.getSCEV(V), L);
276 };
277
278 ICmpInst::Predicate Pred = ICI->getPredicate();
279 Value *LHS = ICI->getOperand(i_nocapture: 0);
280 Value *RHS = ICI->getOperand(i_nocapture: 1);
281
282 if (!LHS->getType()->isIntegerTy())
283 return false;
284
285 // Canonicalize to the `Index Pred Invariant` comparison
286 if (IsLoopInvariant(LHS)) {
287 std::swap(a&: LHS, b&: RHS);
288 Pred = CmpInst::getSwappedPredicate(pred: Pred);
289 } else if (!IsLoopInvariant(RHS))
290 // Both LHS and RHS are loop variant
291 return false;
292
293 if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
294 return true;
295
296 if (reassociateSubLHS(L, VariantLHS: LHS, InvariantRHS: RHS, Pred, SE, Index, End))
297 return true;
298
299 // TODO: support ReassociateAddLHS
300 return false;
301}
302
303// Try to parse range check in the form of "IV vs Limit"
304bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
305 ICmpInst::Predicate Pred,
306 ScalarEvolution &SE,
307 const SCEVAddRecExpr *&Index,
308 const SCEV *&End) {
309
310 auto SIntMaxSCEV = [&](Type *T) {
311 unsigned BitWidth = cast<IntegerType>(Val: T)->getBitWidth();
312 return SE.getConstant(Val: APInt::getSignedMaxValue(numBits: BitWidth));
313 };
314
315 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: SE.getSCEV(V: LHS));
316 if (!AddRec)
317 return false;
318
319 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
320 // We can potentially do much better here.
321 // If we want to adjust upper bound for the unsigned range check as we do it
322 // for signed one, we will need to pick Unsigned max
323 switch (Pred) {
324 default:
325 return false;
326
327 case ICmpInst::ICMP_SGE:
328 if (match(V: RHS, P: m_ConstantInt<0>())) {
329 Index = AddRec;
330 End = SIntMaxSCEV(Index->getType());
331 return true;
332 }
333 return false;
334
335 case ICmpInst::ICMP_SGT:
336 if (match(V: RHS, P: m_ConstantInt<-1>())) {
337 Index = AddRec;
338 End = SIntMaxSCEV(Index->getType());
339 return true;
340 }
341 return false;
342
343 case ICmpInst::ICMP_SLT:
344 case ICmpInst::ICMP_ULT:
345 Index = AddRec;
346 End = SE.getSCEV(V: RHS);
347 return true;
348
349 case ICmpInst::ICMP_SLE:
350 case ICmpInst::ICMP_ULE:
351 const SCEV *One = SE.getOne(Ty: RHS->getType());
352 const SCEV *RHSS = SE.getSCEV(V: RHS);
353 bool Signed = Pred == ICmpInst::ICMP_SLE;
354 if (SE.willNotOverflow(BinOp: Instruction::BinaryOps::Add, Signed, LHS: RHSS, RHS: One)) {
355 Index = AddRec;
356 End = SE.getAddExpr(LHS: RHSS, RHS: One);
357 return true;
358 }
359 return false;
360 }
361
362 llvm_unreachable("default clause returns!");
363}
364
365// Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
366// IV vs Limit"
367bool InductiveRangeCheck::reassociateSubLHS(
368 Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred,
369 ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
370 Value *LHS, *RHS;
371 if (!match(V: VariantLHS, P: m_Sub(L: m_Value(V&: LHS), R: m_Value(V&: RHS))))
372 return false;
373
374 const SCEV *IV = SE.getSCEV(V: LHS);
375 const SCEV *Offset = SE.getSCEV(V: RHS);
376 const SCEV *Limit = SE.getSCEV(V: InvariantRHS);
377
378 bool OffsetSubtracted = false;
379 if (SE.isLoopInvariant(S: IV, L))
380 // "Offset - IV vs Limit"
381 std::swap(a&: IV, b&: Offset);
382 else if (SE.isLoopInvariant(S: Offset, L))
383 // "IV - Offset vs Limit"
384 OffsetSubtracted = true;
385 else
386 return false;
387
388 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: IV);
389 if (!AddRec)
390 return false;
391
392 // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need
393 // to be able to freely move values from left side of inequality to right side
394 // (just as in normal linear arithmetics). Overflows make things much more
395 // complicated, so we want to avoid this.
396 //
397 // Let's prove that the initial subtraction doesn't overflow with all IV's
398 // values from the safe range constructed for that check.
399 //
400 // [Case 1] IV - Offset < Limit
401 // It doesn't overflow if:
402 // SINT_MIN <= IV - Offset <= SINT_MAX
403 // In terms of scaled SINT we need to prove:
404 // SINT_MIN + Offset <= IV <= SINT_MAX + Offset
405 // Safe range will be constructed:
406 // 0 <= IV < Limit + Offset
407 // It means that 'IV - Offset' doesn't underflow, because:
408 // SINT_MIN + Offset < 0 <= IV
409 // and doesn't overflow:
410 // IV < Limit + Offset <= SINT_MAX + Offset
411 //
412 // [Case 2] Offset - IV > Limit
413 // It doesn't overflow if:
414 // SINT_MIN <= Offset - IV <= SINT_MAX
415 // In terms of scaled SINT we need to prove:
416 // -SINT_MIN >= IV - Offset >= -SINT_MAX
417 // Offset - SINT_MIN >= IV >= Offset - SINT_MAX
418 // Safe range will be constructed:
419 // 0 <= IV < Offset - Limit
420 // It means that 'Offset - IV' doesn't underflow, because
421 // Offset - SINT_MAX < 0 <= IV
422 // and doesn't overflow:
423 // IV < Offset - Limit <= Offset - SINT_MIN
424 //
425 // For the computed upper boundary of the IV's range (Offset +/- Limit) we
426 // don't know exactly whether it overflows or not. So if we can't prove this
427 // fact at compile time, we scale boundary computations to a wider type with
428 // the intention to add runtime overflow check.
429
430 auto getExprScaledIfOverflow = [&](Instruction::BinaryOps BinOp,
431 const SCEV *LHS,
432 const SCEV *RHS) -> const SCEV * {
433 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
434 SCEV::NoWrapFlags, unsigned);
435 switch (BinOp) {
436 default:
437 llvm_unreachable("Unsupported binary op");
438 case Instruction::Add:
439 Operation = &ScalarEvolution::getAddExpr;
440 break;
441 case Instruction::Sub:
442 Operation = &ScalarEvolution::getMinusSCEV;
443 break;
444 }
445
446 if (SE.willNotOverflow(BinOp, Signed: ICmpInst::isSigned(predicate: Pred), LHS, RHS,
447 CtxI: cast<Instruction>(Val: VariantLHS)))
448 return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
449
450 // We couldn't prove that the expression does not overflow.
451 // Than scale it to a wider type to check overflow at runtime.
452 auto *Ty = cast<IntegerType>(Val: LHS->getType());
453 if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck)
454 return nullptr;
455
456 auto WideTy = IntegerType::get(C&: Ty->getContext(), NumBits: Ty->getBitWidth() * 2);
457 return (SE.*Operation)(SE.getSignExtendExpr(Op: LHS, Ty: WideTy),
458 SE.getSignExtendExpr(Op: RHS, Ty: WideTy), SCEV::FlagAnyWrap,
459 0);
460 };
461
462 if (OffsetSubtracted)
463 // "IV - Offset < Limit" -> "IV" < Offset + Limit
464 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit);
465 else {
466 // "Offset - IV > Limit" -> "IV" < Offset - Limit
467 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit);
468 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
469 }
470
471 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
472 // "Expr <= Limit" -> "Expr < Limit + 1"
473 if (Pred == ICmpInst::ICMP_SLE && Limit)
474 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
475 SE.getOne(Ty: Limit->getType()));
476 if (Limit) {
477 Index = AddRec;
478 End = Limit;
479 return true;
480 }
481 }
482 return false;
483}
484
485void InductiveRangeCheck::extractRangeChecksFromCond(
486 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
487 SmallVectorImpl<InductiveRangeCheck> &Checks,
488 SmallPtrSetImpl<Value *> &Visited) {
489 Value *Condition = ConditionUse.get();
490 if (!Visited.insert(Ptr: Condition).second)
491 return;
492
493 // TODO: Do the same for OR, XOR, NOT etc?
494 if (match(V: Condition, P: m_LogicalAnd(L: m_Value(), R: m_Value()))) {
495 extractRangeChecksFromCond(L, SE, ConditionUse&: cast<User>(Val: Condition)->getOperandUse(i: 0),
496 Checks, Visited);
497 extractRangeChecksFromCond(L, SE, ConditionUse&: cast<User>(Val: Condition)->getOperandUse(i: 1),
498 Checks, Visited);
499 return;
500 }
501
502 ICmpInst *ICI = dyn_cast<ICmpInst>(Val: Condition);
503 if (!ICI)
504 return;
505
506 const SCEV *End = nullptr;
507 const SCEVAddRecExpr *IndexAddRec = nullptr;
508 if (!parseRangeCheckICmp(L, ICI, SE, Index&: IndexAddRec, End))
509 return;
510
511 assert(IndexAddRec && "IndexAddRec was not computed");
512 assert(End && "End was not computed");
513
514 if ((IndexAddRec->getLoop() != L) || !IndexAddRec->isAffine())
515 return;
516
517 InductiveRangeCheck IRC;
518 IRC.End = End;
519 IRC.Begin = IndexAddRec->getStart();
520 IRC.Step = IndexAddRec->getStepRecurrence(SE);
521 IRC.CheckUse = &ConditionUse;
522 Checks.push_back(Elt: IRC);
523}
524
525void InductiveRangeCheck::extractRangeChecksFromBranch(
526 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
527 SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed) {
528 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
529 return;
530
531 unsigned IndexLoopSucc = L->contains(BB: BI->getSuccessor(i: 0)) ? 0 : 1;
532 assert(L->contains(BI->getSuccessor(IndexLoopSucc)) &&
533 "No edges coming to loop?");
534 BranchProbability LikelyTaken(15, 16);
535
536 if (!SkipProfitabilityChecks && BPI &&
537 BPI->getEdgeProbability(Src: BI->getParent(), IndexInSuccessors: IndexLoopSucc) < LikelyTaken)
538 return;
539
540 // IRCE expects branch's true edge comes to loop. Invert branch for opposite
541 // case.
542 if (IndexLoopSucc != 0) {
543 IRBuilder<> Builder(BI);
544 InvertBranch(PBI: BI, Builder);
545 if (BPI)
546 BPI->swapSuccEdgesProbabilities(Src: BI->getParent());
547 Changed = true;
548 }
549
550 SmallPtrSet<Value *, 8> Visited;
551 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, ConditionUse&: BI->getOperandUse(i: 0),
552 Checks, Visited);
553}
554
555/// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
556/// signed or unsigned extension of \p S to type \p Ty.
557static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
558 bool Signed) {
559 return Signed ? SE.getNoopOrSignExtend(V: S, Ty) : SE.getNoopOrZeroExtend(V: S, Ty);
560}
561
562// Compute a safe set of limits for the main loop to run in -- effectively the
563// intersection of `Range' and the iteration space of the original loop.
564// Return std::nullopt if unable to compute the set of subranges.
565static std::optional<LoopConstrainer::SubRanges>
566calculateSubRanges(ScalarEvolution &SE, const Loop &L,
567 InductiveRangeCheck::Range &Range,
568 const LoopStructure &MainLoopStructure) {
569 auto *RTy = cast<IntegerType>(Val: Range.getType());
570 // We only support wide range checks and narrow latches.
571 if (!AllowNarrowLatchCondition && RTy != MainLoopStructure.ExitCountTy)
572 return std::nullopt;
573 if (RTy->getBitWidth() < MainLoopStructure.ExitCountTy->getBitWidth())
574 return std::nullopt;
575
576 LoopConstrainer::SubRanges Result;
577
578 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
579 // I think we can be more aggressive here and make this nuw / nsw if the
580 // addition that feeds into the icmp for the latch's terminating branch is nuw
581 // / nsw. In any case, a wrapping 2's complement addition is safe.
582 const SCEV *Start = NoopOrExtend(S: SE.getSCEV(V: MainLoopStructure.IndVarStart),
583 Ty: RTy, SE, Signed: IsSignedPredicate);
584 const SCEV *End = NoopOrExtend(S: SE.getSCEV(V: MainLoopStructure.LoopExitAt), Ty: RTy,
585 SE, Signed: IsSignedPredicate);
586
587 bool Increasing = MainLoopStructure.IndVarIncreasing;
588
589 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
590 // [Smallest, GreatestSeen] is the range of values the induction variable
591 // takes.
592
593 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
594
595 const SCEV *One = SE.getOne(Ty: RTy);
596 if (Increasing) {
597 Smallest = Start;
598 Greatest = End;
599 // No overflow, because the range [Smallest, GreatestSeen] is not empty.
600 GreatestSeen = SE.getMinusSCEV(LHS: End, RHS: One);
601 } else {
602 // These two computations may sign-overflow. Here is why that is okay:
603 //
604 // We know that the induction variable does not sign-overflow on any
605 // iteration except the last one, and it starts at `Start` and ends at
606 // `End`, decrementing by one every time.
607 //
608 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
609 // induction variable is decreasing we know that the smallest value
610 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
611 //
612 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
613 // that case, `Clamp` will always return `Smallest` and
614 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
615 // will be an empty range. Returning an empty range is always safe.
616
617 Smallest = SE.getAddExpr(LHS: End, RHS: One);
618 Greatest = SE.getAddExpr(LHS: Start, RHS: One);
619 GreatestSeen = Start;
620 }
621
622 auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
623 return IsSignedPredicate
624 ? SE.getSMaxExpr(LHS: Smallest, RHS: SE.getSMinExpr(LHS: Greatest, RHS: S))
625 : SE.getUMaxExpr(LHS: Smallest, RHS: SE.getUMinExpr(LHS: Greatest, RHS: S));
626 };
627
628 // In some cases we can prove that we don't need a pre or post loop.
629 ICmpInst::Predicate PredLE =
630 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
631 ICmpInst::Predicate PredLT =
632 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
633
634 bool ProvablyNoPreloop =
635 SE.isKnownPredicate(Pred: PredLE, LHS: Range.getBegin(), RHS: Smallest);
636 if (!ProvablyNoPreloop)
637 Result.LowLimit = Clamp(Range.getBegin());
638
639 bool ProvablyNoPostLoop =
640 SE.isKnownPredicate(Pred: PredLT, LHS: GreatestSeen, RHS: Range.getEnd());
641 if (!ProvablyNoPostLoop)
642 Result.HighLimit = Clamp(Range.getEnd());
643
644 return Result;
645}
646
647/// Computes and returns a range of values for the induction variable (IndVar)
648/// in which the range check can be safely elided. If it cannot compute such a
649/// range, returns std::nullopt.
650std::optional<InductiveRangeCheck::Range>
651InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
652 const SCEVAddRecExpr *IndVar,
653 bool IsLatchSigned) const {
654 // We can deal when types of latch check and range checks don't match in case
655 // if latch check is more narrow.
656 auto *IVType = dyn_cast<IntegerType>(Val: IndVar->getType());
657 auto *RCType = dyn_cast<IntegerType>(Val: getBegin()->getType());
658 auto *EndType = dyn_cast<IntegerType>(Val: getEnd()->getType());
659 // Do not work with pointer types.
660 if (!IVType || !RCType)
661 return std::nullopt;
662 if (IVType->getBitWidth() > RCType->getBitWidth())
663 return std::nullopt;
664
665 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
666 // variable, that may or may not exist as a real llvm::Value in the loop) and
667 // this inductive range check is a range check on the "C + D * I" ("C" is
668 // getBegin() and "D" is getStep()). We rewrite the value being range
669 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
670 //
671 // The actual inequalities we solve are of the form
672 //
673 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
674 //
675 // Here L stands for upper limit of the safe iteration space.
676 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
677 // overflows when calculating (0 - M) and (L - M) we, depending on type of
678 // IV's iteration space, limit the calculations by borders of the iteration
679 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
680 // If we figured out that "anything greater than (-M) is safe", we strengthen
681 // this to "everything greater than 0 is safe", assuming that values between
682 // -M and 0 just do not exist in unsigned iteration space, and we don't want
683 // to deal with overflown values.
684
685 if (!IndVar->isAffine())
686 return std::nullopt;
687
688 const SCEV *A = NoopOrExtend(S: IndVar->getStart(), Ty: RCType, SE, Signed: IsLatchSigned);
689 const SCEVConstant *B = dyn_cast<SCEVConstant>(
690 Val: NoopOrExtend(S: IndVar->getStepRecurrence(SE), Ty: RCType, SE, Signed: IsLatchSigned));
691 if (!B)
692 return std::nullopt;
693 assert(!B->isZero() && "Recurrence with zero step?");
694
695 const SCEV *C = getBegin();
696 const SCEVConstant *D = dyn_cast<SCEVConstant>(Val: getStep());
697 if (D != B)
698 return std::nullopt;
699
700 assert(!D->getValue()->isZero() && "Recurrence with zero step?");
701 unsigned BitWidth = RCType->getBitWidth();
702 const SCEV *SIntMax = SE.getConstant(Val: APInt::getSignedMaxValue(numBits: BitWidth));
703 const SCEV *SIntMin = SE.getConstant(Val: APInt::getSignedMinValue(numBits: BitWidth));
704
705 // Subtract Y from X so that it does not go through border of the IV
706 // iteration space. Mathematically, it is equivalent to:
707 //
708 // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
709 //
710 // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
711 // any width of bit grid). But after we take min/max, the result is
712 // guaranteed to be within [INT_MIN, INT_MAX].
713 //
714 // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
715 // values, depending on type of latch condition that defines IV iteration
716 // space.
717 auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
718 // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
719 // This is required to ensure that SINT_MAX - X does not overflow signed and
720 // that X - Y does not overflow unsigned if Y is negative. Can we lift this
721 // restriction and make it work for negative X either?
722 if (IsLatchSigned) {
723 // X is a number from signed range, Y is interpreted as signed.
724 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
725 // thing we should care about is that we didn't cross SINT_MAX.
726 // So, if Y is positive, we subtract Y safely.
727 // Rule 1: Y > 0 ---> Y.
728 // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
729 // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
730 // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
731 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
732 // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
733 const SCEV *XMinusSIntMax = SE.getMinusSCEV(LHS: X, RHS: SIntMax);
734 return SE.getMinusSCEV(LHS: X, RHS: SE.getSMaxExpr(LHS: Y, RHS: XMinusSIntMax),
735 Flags: SCEV::FlagNSW);
736 } else
737 // X is a number from unsigned range, Y is interpreted as signed.
738 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
739 // thing we should care about is that we didn't cross zero.
740 // So, if Y is negative, we subtract Y safely.
741 // Rule 1: Y <s 0 ---> Y.
742 // If 0 <= Y <= X, we subtract Y safely.
743 // Rule 2: Y <=s X ---> Y.
744 // If 0 <= X < Y, we should stop at 0 and can only subtract X.
745 // Rule 3: Y >s X ---> X.
746 // It gives us smin(X, Y) to subtract in all cases.
747 return SE.getMinusSCEV(LHS: X, RHS: SE.getSMinExpr(LHS: X, RHS: Y), Flags: SCEV::FlagNUW);
748 };
749 const SCEV *M = SE.getMinusSCEV(LHS: C, RHS: A);
750 const SCEV *Zero = SE.getZero(Ty: M->getType());
751
752 // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
753 auto SCEVCheckNonNegative = [&](const SCEV *X) {
754 const Loop *L = IndVar->getLoop();
755 const SCEV *Zero = SE.getZero(Ty: X->getType());
756 const SCEV *One = SE.getOne(Ty: X->getType());
757 // Can we trivially prove that X is a non-negative or negative value?
758 if (isKnownNonNegativeInLoop(S: X, L, SE))
759 return One;
760 else if (isKnownNegativeInLoop(S: X, L, SE))
761 return Zero;
762 // If not, we will have to figure it out during the execution.
763 // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
764 const SCEV *NegOne = SE.getNegativeSCEV(V: One);
765 return SE.getAddExpr(LHS: SE.getSMaxExpr(LHS: SE.getSMinExpr(LHS: X, RHS: Zero), RHS: NegOne), RHS: One);
766 };
767
768 // This function returns SCEV equal to 1 if X will not overflow in terms of
769 // range check type, 0 otherwise.
770 auto SCEVCheckWillNotOverflow = [&](const SCEV *X) {
771 // X doesn't overflow if SINT_MAX >= X.
772 // Then if (SINT_MAX - X) >= 0, X doesn't overflow
773 const SCEV *SIntMaxExt = SE.getSignExtendExpr(Op: SIntMax, Ty: X->getType());
774 const SCEV *OverflowCheck =
775 SCEVCheckNonNegative(SE.getMinusSCEV(LHS: SIntMaxExt, RHS: X));
776
777 // X doesn't underflow if X >= SINT_MIN.
778 // Then if (X - SINT_MIN) >= 0, X doesn't underflow
779 const SCEV *SIntMinExt = SE.getSignExtendExpr(Op: SIntMin, Ty: X->getType());
780 const SCEV *UnderflowCheck =
781 SCEVCheckNonNegative(SE.getMinusSCEV(LHS: X, RHS: SIntMinExt));
782
783 return SE.getMulExpr(LHS: OverflowCheck, RHS: UnderflowCheck);
784 };
785
786 // FIXME: Current implementation of ClampedSubtract implicitly assumes that
787 // X is non-negative (in sense of a signed value). We need to re-implement
788 // this function in a way that it will correctly handle negative X as well.
789 // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
790 // end up with a negative X and produce wrong results. So currently we ensure
791 // that if getEnd() is negative then both ends of the safe range are zero.
792 // Note that this may pessimize elimination of unsigned range checks against
793 // negative values.
794 const SCEV *REnd = getEnd();
795 const SCEV *EndWillNotOverflow = SE.getOne(Ty: RCType);
796
797 auto PrintRangeCheck = [&](raw_ostream &OS) {
798 auto L = IndVar->getLoop();
799 OS << "irce: in function ";
800 OS << L->getHeader()->getParent()->getName();
801 OS << ", in ";
802 L->print(OS);
803 OS << "there is range check with scaled boundary:\n";
804 print(OS);
805 };
806
807 if (EndType->getBitWidth() > RCType->getBitWidth()) {
808 assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
809 if (PrintScaledBoundaryRangeChecks)
810 PrintRangeCheck(errs());
811 // End is computed with extended type but will be truncated to a narrow one
812 // type of range check. Therefore we need a check that the result will not
813 // overflow in terms of narrow type.
814 EndWillNotOverflow =
815 SE.getTruncateExpr(Op: SCEVCheckWillNotOverflow(REnd), Ty: RCType);
816 REnd = SE.getTruncateExpr(Op: REnd, Ty: RCType);
817 }
818
819 const SCEV *RuntimeChecks =
820 SE.getMulExpr(LHS: SCEVCheckNonNegative(REnd), RHS: EndWillNotOverflow);
821 const SCEV *Begin = SE.getMulExpr(LHS: ClampedSubtract(Zero, M), RHS: RuntimeChecks);
822 const SCEV *End = SE.getMulExpr(LHS: ClampedSubtract(REnd, M), RHS: RuntimeChecks);
823
824 return InductiveRangeCheck::Range(Begin, End);
825}
826
827static std::optional<InductiveRangeCheck::Range>
828IntersectSignedRange(ScalarEvolution &SE,
829 const std::optional<InductiveRangeCheck::Range> &R1,
830 const InductiveRangeCheck::Range &R2) {
831 if (R2.isEmpty(SE, /* IsSigned */ true))
832 return std::nullopt;
833 if (!R1)
834 return R2;
835 auto &R1Value = *R1;
836 // We never return empty ranges from this function, and R1 is supposed to be
837 // a result of intersection. Thus, R1 is never empty.
838 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
839 "We should never have empty R1!");
840
841 // TODO: we could widen the smaller range and have this work; but for now we
842 // bail out to keep things simple.
843 if (R1Value.getType() != R2.getType())
844 return std::nullopt;
845
846 const SCEV *NewBegin = SE.getSMaxExpr(LHS: R1Value.getBegin(), RHS: R2.getBegin());
847 const SCEV *NewEnd = SE.getSMinExpr(LHS: R1Value.getEnd(), RHS: R2.getEnd());
848
849 // If the resulting range is empty, just return std::nullopt.
850 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
851 if (Ret.isEmpty(SE, /* IsSigned */ true))
852 return std::nullopt;
853 return Ret;
854}
855
856static std::optional<InductiveRangeCheck::Range>
857IntersectUnsignedRange(ScalarEvolution &SE,
858 const std::optional<InductiveRangeCheck::Range> &R1,
859 const InductiveRangeCheck::Range &R2) {
860 if (R2.isEmpty(SE, /* IsSigned */ false))
861 return std::nullopt;
862 if (!R1)
863 return R2;
864 auto &R1Value = *R1;
865 // We never return empty ranges from this function, and R1 is supposed to be
866 // a result of intersection. Thus, R1 is never empty.
867 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
868 "We should never have empty R1!");
869
870 // TODO: we could widen the smaller range and have this work; but for now we
871 // bail out to keep things simple.
872 if (R1Value.getType() != R2.getType())
873 return std::nullopt;
874
875 const SCEV *NewBegin = SE.getUMaxExpr(LHS: R1Value.getBegin(), RHS: R2.getBegin());
876 const SCEV *NewEnd = SE.getUMinExpr(LHS: R1Value.getEnd(), RHS: R2.getEnd());
877
878 // If the resulting range is empty, just return std::nullopt.
879 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
880 if (Ret.isEmpty(SE, /* IsSigned */ false))
881 return std::nullopt;
882 return Ret;
883}
884
885PreservedAnalyses IRCEPass::run(Function &F, FunctionAnalysisManager &AM) {
886 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
887 LoopInfo &LI = AM.getResult<LoopAnalysis>(IR&: F);
888 // There are no loops in the function. Return before computing other expensive
889 // analyses.
890 if (LI.empty())
891 return PreservedAnalyses::all();
892 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
893 auto &BPI = AM.getResult<BranchProbabilityAnalysis>(IR&: F);
894
895 // Get BFI analysis result on demand. Please note that modification of
896 // CFG invalidates this analysis and we should handle it.
897 auto getBFI = [&F, &AM ]()->BlockFrequencyInfo & {
898 return AM.getResult<BlockFrequencyAnalysis>(IR&: F);
899 };
900 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
901
902 bool Changed = false;
903 {
904 bool CFGChanged = false;
905 for (const auto &L : LI) {
906 CFGChanged |= simplifyLoop(L, DT: &DT, LI: &LI, SE: &SE, AC: nullptr, MSSAU: nullptr,
907 /*PreserveLCSSA=*/false);
908 Changed |= formLCSSARecursively(L&: *L, DT, LI: &LI, SE: &SE);
909 }
910 Changed |= CFGChanged;
911
912 if (CFGChanged && !SkipProfitabilityChecks) {
913 PreservedAnalyses PA = PreservedAnalyses::all();
914 PA.abandon<BlockFrequencyAnalysis>();
915 AM.invalidate(IR&: F, PA);
916 }
917 }
918
919 SmallPriorityWorklist<Loop *, 4> Worklist;
920 appendLoopsToWorklist(LI, Worklist);
921 auto LPMAddNewLoop = [&Worklist](Loop *NL, bool IsSubloop) {
922 if (!IsSubloop)
923 appendLoopsToWorklist(*NL, Worklist);
924 };
925
926 while (!Worklist.empty()) {
927 Loop *L = Worklist.pop_back_val();
928 if (IRCE.run(L, LPMAddNewLoop)) {
929 Changed = true;
930 if (!SkipProfitabilityChecks) {
931 PreservedAnalyses PA = PreservedAnalyses::all();
932 PA.abandon<BlockFrequencyAnalysis>();
933 AM.invalidate(IR&: F, PA);
934 }
935 }
936 }
937
938 if (!Changed)
939 return PreservedAnalyses::all();
940 return getLoopPassPreservedAnalyses();
941}
942
943bool
944InductiveRangeCheckElimination::isProfitableToTransform(const Loop &L,
945 LoopStructure &LS) {
946 if (SkipProfitabilityChecks)
947 return true;
948 if (GetBFI) {
949 BlockFrequencyInfo &BFI = (*GetBFI)();
950 uint64_t hFreq = BFI.getBlockFreq(BB: LS.Header).getFrequency();
951 uint64_t phFreq = BFI.getBlockFreq(BB: L.getLoopPreheader()).getFrequency();
952 if (phFreq != 0 && hFreq != 0 && (hFreq / phFreq < MinRuntimeIterations)) {
953 LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
954 << "the estimated number of iterations basing on "
955 "frequency info is " << (hFreq / phFreq) << "\n";);
956 return false;
957 }
958 return true;
959 }
960
961 if (!BPI)
962 return true;
963 BranchProbability ExitProbability =
964 BPI->getEdgeProbability(Src: LS.Latch, IndexInSuccessors: LS.LatchBrExitIdx);
965 if (ExitProbability > BranchProbability(1, MinRuntimeIterations)) {
966 LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
967 << "the exit probability is too big " << ExitProbability
968 << "\n";);
969 return false;
970 }
971 return true;
972}
973
974bool InductiveRangeCheckElimination::run(
975 Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
976 if (L->getBlocks().size() >= LoopSizeCutoff) {
977 LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
978 return false;
979 }
980
981 BasicBlock *Preheader = L->getLoopPreheader();
982 if (!Preheader) {
983 LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
984 return false;
985 }
986
987 LLVMContext &Context = Preheader->getContext();
988 SmallVector<InductiveRangeCheck, 16> RangeChecks;
989 bool Changed = false;
990
991 for (auto *BBI : L->getBlocks())
992 if (BranchInst *TBI = dyn_cast<BranchInst>(Val: BBI->getTerminator()))
993 InductiveRangeCheck::extractRangeChecksFromBranch(BI: TBI, L, SE, BPI,
994 Checks&: RangeChecks, Changed);
995
996 if (RangeChecks.empty())
997 return Changed;
998
999 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1000 OS << "irce: looking at loop "; L->print(OS);
1001 OS << "irce: loop has " << RangeChecks.size()
1002 << " inductive range checks: \n";
1003 for (InductiveRangeCheck &IRC : RangeChecks)
1004 IRC.print(OS);
1005 };
1006
1007 LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
1008
1009 if (PrintRangeChecks)
1010 PrintRecognizedRangeChecks(errs());
1011
1012 const char *FailureReason = nullptr;
1013 std::optional<LoopStructure> MaybeLoopStructure =
1014 LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition,
1015 FailureReason);
1016 if (!MaybeLoopStructure) {
1017 LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
1018 << FailureReason << "\n";);
1019 return Changed;
1020 }
1021 LoopStructure LS = *MaybeLoopStructure;
1022 if (!isProfitableToTransform(L: *L, LS))
1023 return Changed;
1024 const SCEVAddRecExpr *IndVar =
1025 cast<SCEVAddRecExpr>(Val: SE.getMinusSCEV(LHS: SE.getSCEV(V: LS.IndVarBase), RHS: SE.getSCEV(V: LS.IndVarStep)));
1026
1027 std::optional<InductiveRangeCheck::Range> SafeIterRange;
1028
1029 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1030 // Basing on the type of latch predicate, we interpret the IV iteration range
1031 // as signed or unsigned range. We use different min/max functions (signed or
1032 // unsigned) when intersecting this range with safe iteration ranges implied
1033 // by range checks.
1034 auto IntersectRange =
1035 LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1036
1037 for (InductiveRangeCheck &IRC : RangeChecks) {
1038 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1039 IsLatchSigned: LS.IsSignedPredicate);
1040 if (Result) {
1041 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1042 if (MaybeSafeIterRange) {
1043 assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) &&
1044 "We should never return empty ranges!");
1045 RangeChecksToEliminate.push_back(Elt: IRC);
1046 SafeIterRange = *MaybeSafeIterRange;
1047 }
1048 }
1049 }
1050
1051 if (!SafeIterRange)
1052 return Changed;
1053
1054 std::optional<LoopConstrainer::SubRanges> MaybeSR =
1055 calculateSubRanges(SE, L: *L, Range&: *SafeIterRange, MainLoopStructure: LS);
1056 if (!MaybeSR) {
1057 LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
1058 return false;
1059 }
1060
1061 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1062 SafeIterRange->getBegin()->getType(), *MaybeSR);
1063
1064 if (LC.run()) {
1065 Changed = true;
1066
1067 auto PrintConstrainedLoopInfo = [L]() {
1068 dbgs() << "irce: in function ";
1069 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1070 dbgs() << "constrained ";
1071 L->print(OS&: dbgs());
1072 };
1073
1074 LLVM_DEBUG(PrintConstrainedLoopInfo());
1075
1076 if (PrintChangedLoops)
1077 PrintConstrainedLoopInfo();
1078
1079 // Optimize away the now-redundant range checks.
1080
1081 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1082 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1083 ? ConstantInt::getTrue(Context)
1084 : ConstantInt::getFalse(Context);
1085 IRC.getCheckUse()->set(FoldedRangeCheck);
1086 }
1087 }
1088
1089 return Changed;
1090}
1091