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