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