Lines Matching +full:offset +full:- +full:y
1 //===- InductiveRangeCheckElimination.cpp - -------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
43 //===----------------------------------------------------------------------===//
98 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
101 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
104 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
107 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
110 static cl::opt<unsigned> MinRuntimeIterations("irce-min-runtime-iterations",
113 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
117 "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
122 "irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32),
128 PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks",
178 Begin->print(OS); in print()
180 Step->print(OS); in print()
182 End->print(OS); in print()
184 getCheckUse()->getUser()->print(OS); in print()
185 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n"; in print()
204 assert(Begin->getType() == End->getType() && "ill-typed range!"); in Range()
207 Type *getType() const { return Begin->getType(); } in getType()
225 /// check is redundant and can be constant-folded away. The induction
278 ICmpInst::Predicate Pred = ICI->getPredicate(); in parseRangeCheckICmp()
279 Value *LHS = ICI->getOperand(0); in parseRangeCheckICmp()
280 Value *RHS = ICI->getOperand(1); in parseRangeCheckICmp()
282 if (!LHS->getType()->isIntegerTy()) in parseRangeCheckICmp()
311 unsigned BitWidth = cast<IntegerType>(T)->getBitWidth(); in parseIvAgaisntLimit()
330 End = SIntMaxSCEV(Index->getType()); in parseIvAgaisntLimit()
336 if (match(RHS, m_ConstantInt<-1>())) { in parseIvAgaisntLimit()
338 End = SIntMaxSCEV(Index->getType()); in parseIvAgaisntLimit()
351 const SCEV *One = SE.getOne(RHS->getType()); in parseIvAgaisntLimit()
365 // Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
375 const SCEV *Offset = SE.getSCEV(RHS); in reassociateSubLHS() local
380 // "Offset - IV vs Limit" in reassociateSubLHS()
381 std::swap(IV, Offset); in reassociateSubLHS()
382 else if (SE.isLoopInvariant(Offset, L)) in reassociateSubLHS()
383 // "IV - Offset vs Limit" in reassociateSubLHS()
392 // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need in reassociateSubLHS()
400 // [Case 1] IV - Offset < Limit in reassociateSubLHS()
402 // SINT_MIN <= IV - Offset <= SINT_MAX in reassociateSubLHS()
404 // SINT_MIN + Offset <= IV <= SINT_MAX + Offset in reassociateSubLHS()
406 // 0 <= IV < Limit + Offset in reassociateSubLHS()
407 // It means that 'IV - Offset' doesn't underflow, because: in reassociateSubLHS()
408 // SINT_MIN + Offset < 0 <= IV in reassociateSubLHS()
410 // IV < Limit + Offset <= SINT_MAX + Offset in reassociateSubLHS()
412 // [Case 2] Offset - IV > Limit in reassociateSubLHS()
414 // SINT_MIN <= Offset - IV <= SINT_MAX in reassociateSubLHS()
416 // -SINT_MIN >= IV - Offset >= -SINT_MAX in reassociateSubLHS()
417 // Offset - SINT_MIN >= IV >= Offset - SINT_MAX in reassociateSubLHS()
419 // 0 <= IV < Offset - Limit in reassociateSubLHS()
420 // It means that 'Offset - IV' doesn't underflow, because in reassociateSubLHS()
421 // Offset - SINT_MAX < 0 <= IV in reassociateSubLHS()
423 // IV < Offset - Limit <= Offset - SINT_MIN in reassociateSubLHS()
425 // For the computed upper boundary of the IV's range (Offset +/- Limit) we in reassociateSubLHS()
432 const SCEV *RHS) -> const SCEV * { in reassociateSubLHS()
452 auto *Ty = cast<IntegerType>(LHS->getType()); in reassociateSubLHS()
453 if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck) in reassociateSubLHS()
456 auto WideTy = IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2); in reassociateSubLHS()
463 // "IV - Offset < Limit" -> "IV" < Offset + Limit in reassociateSubLHS()
464 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit); in reassociateSubLHS()
466 // "Offset - IV > Limit" -> "IV" < Offset - Limit in reassociateSubLHS()
467 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit); in reassociateSubLHS()
472 // "Expr <= Limit" -> "Expr < Limit + 1" in reassociateSubLHS()
475 SE.getOne(Limit->getType())); in reassociateSubLHS()
495 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0), in extractRangeChecksFromCond()
497 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1), in extractRangeChecksFromCond()
514 if ((IndexAddRec->getLoop() != L) || !IndexAddRec->isAffine()) in extractRangeChecksFromCond()
519 IRC.Begin = IndexAddRec->getStart(); in extractRangeChecksFromCond()
520 IRC.Step = IndexAddRec->getStepRecurrence(SE); in extractRangeChecksFromCond()
528 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch()) in extractRangeChecksFromBranch()
531 unsigned IndexLoopSucc = L->contains(BI->getSuccessor(0)) ? 0 : 1; in extractRangeChecksFromBranch()
532 assert(L->contains(BI->getSuccessor(IndexLoopSucc)) && in extractRangeChecksFromBranch()
537 BPI->getEdgeProbability(BI->getParent(), IndexLoopSucc) < LikelyTaken) in extractRangeChecksFromBranch()
546 BPI->swapSuccEdgesProbabilities(BI->getParent()); in extractRangeChecksFromBranch()
551 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0), in extractRangeChecksFromBranch()
562 // Compute a safe set of limits for the main loop to run in -- effectively the
573 if (RTy->getBitWidth() < MainLoopStructure.ExitCountTy->getBitWidth()) in calculateSubRanges()
602 // These two computations may sign-overflow. Here is why that is okay: in calculateSubRanges()
604 // We know that the induction variable does not sign-overflow on any in calculateSubRanges()
608 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the in calculateSubRanges()
612 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In in calculateSubRanges()
656 auto *IVType = dyn_cast<IntegerType>(IndVar->getType()); in computeSafeIterationSpace()
657 auto *RCType = dyn_cast<IntegerType>(getBegin()->getType()); in computeSafeIterationSpace()
658 auto *EndType = dyn_cast<IntegerType>(getEnd()->getType()); in computeSafeIterationSpace()
662 if (IVType->getBitWidth() > RCType->getBitWidth()) in computeSafeIterationSpace()
669 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA". in computeSafeIterationSpace()
676 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid in computeSafeIterationSpace()
677 // overflows when calculating (0 - M) and (L - M) we, depending on type of in computeSafeIterationSpace()
679 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0. in computeSafeIterationSpace()
680 // If we figured out that "anything greater than (-M) is safe", we strengthen in computeSafeIterationSpace()
682 // -M and 0 just do not exist in unsigned iteration space, and we don't want in computeSafeIterationSpace()
685 if (!IndVar->isAffine()) in computeSafeIterationSpace()
688 const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned); in computeSafeIterationSpace()
690 NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned)); in computeSafeIterationSpace()
693 assert(!B->isZero() && "Recurrence with zero step?"); in computeSafeIterationSpace()
700 assert(!D->getValue()->isZero() && "Recurrence with zero step?"); in computeSafeIterationSpace()
701 unsigned BitWidth = RCType->getBitWidth(); in computeSafeIterationSpace()
705 // Subtract Y from X so that it does not go through border of the IV in computeSafeIterationSpace()
708 // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1] in computeSafeIterationSpace()
710 // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to in computeSafeIterationSpace()
717 auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) { in computeSafeIterationSpace() argument
719 // This is required to ensure that SINT_MAX - X does not overflow signed and in computeSafeIterationSpace()
720 // that X - Y does not overflow unsigned if Y is negative. Can we lift this in computeSafeIterationSpace()
723 // X is a number from signed range, Y is interpreted as signed. in computeSafeIterationSpace()
724 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only in computeSafeIterationSpace()
726 // So, if Y is positive, we subtract Y safely. in computeSafeIterationSpace()
727 // Rule 1: Y > 0 ---> Y. in computeSafeIterationSpace()
728 // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely. in computeSafeIterationSpace()
729 // Rule 2: Y >=s (X - SINT_MAX) ---> Y. in computeSafeIterationSpace()
730 // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX). in computeSafeIterationSpace()
731 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX). in computeSafeIterationSpace()
732 // It gives us smax(Y, X - SINT_MAX) to subtract in all cases. in computeSafeIterationSpace()
734 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax), in computeSafeIterationSpace()
737 // X is a number from unsigned range, Y is interpreted as signed. in computeSafeIterationSpace()
738 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only in computeSafeIterationSpace()
740 // So, if Y is negative, we subtract Y safely. in computeSafeIterationSpace()
741 // Rule 1: Y <s 0 ---> Y. in computeSafeIterationSpace()
742 // If 0 <= Y <= X, we subtract Y safely. in computeSafeIterationSpace()
743 // Rule 2: Y <=s X ---> Y. in computeSafeIterationSpace()
744 // If 0 <= X < Y, we should stop at 0 and can only subtract X. in computeSafeIterationSpace()
745 // Rule 3: Y >s X ---> X. in computeSafeIterationSpace()
746 // It gives us smin(X, Y) to subtract in all cases. in computeSafeIterationSpace()
747 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW); in computeSafeIterationSpace()
750 const SCEV *Zero = SE.getZero(M->getType()); in computeSafeIterationSpace()
752 // This function returns SCEV equal to 1 if X is non-negative 0 otherwise. in computeSafeIterationSpace()
754 const Loop *L = IndVar->getLoop(); in computeSafeIterationSpace()
755 const SCEV *Zero = SE.getZero(X->getType()); in computeSafeIterationSpace()
756 const SCEV *One = SE.getOne(X->getType()); in computeSafeIterationSpace()
757 // Can we trivially prove that X is a non-negative or negative value? in computeSafeIterationSpace()
763 // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0. in computeSafeIterationSpace()
772 // Then if (SINT_MAX - X) >= 0, X doesn't overflow in computeSafeIterationSpace()
773 const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType()); in computeSafeIterationSpace()
778 // Then if (X - SINT_MIN) >= 0, X doesn't underflow in computeSafeIterationSpace()
779 const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType()); in computeSafeIterationSpace()
787 // X is non-negative (in sense of a signed value). We need to re-implement in computeSafeIterationSpace()
798 auto L = IndVar->getLoop(); in computeSafeIterationSpace()
800 OS << L->getHeader()->getParent()->getName(); in computeSafeIterationSpace()
802 L->print(OS); in computeSafeIterationSpace()
807 if (EndType->getBitWidth() > RCType->getBitWidth()) { in computeSafeIterationSpace()
808 assert(EndType->getBitWidth() == RCType->getBitWidth() * 2); in computeSafeIterationSpace()
897 auto getBFI = [&F, &AM ]()->BlockFrequencyInfo & { in run()
964 BPI->getEdgeProbability(LS.Latch, LS.LatchBrExitIdx); in isProfitableToTransform()
976 if (L->getBlocks().size() >= LoopSizeCutoff) { in run()
981 BasicBlock *Preheader = L->getLoopPreheader(); in run()
987 LLVMContext &Context = Preheader->getContext(); in run()
991 for (auto *BBI : L->getBlocks()) in run()
992 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator())) in run()
1000 OS << "irce: looking at loop "; L->print(OS); in run()
1043 assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) && in run()
1062 SafeIterRange->getBegin()->getType(), *MaybeSR); in run()
1069 dbgs() << L->getHeader()->getParent()->getName() << ": "; in run()
1071 L->print(dbgs()); in run()
1079 // Optimize away the now-redundant range checks. in run()
1085 IRC.getCheckUse()->set(FoldedRangeCheck); in run()