Author: Max Kazantsev Date: 2020-11-25T13:26:17+07:00 New Revision: 9130651126b745b18138b816487cdeb8a689a27f
URL: https://github.com/llvm/llvm-project/commit/9130651126b745b18138b816487cdeb8a689a27f DIFF: https://github.com/llvm/llvm-project/commit/9130651126b745b18138b816487cdeb8a689a27f.diff LOG: Revert "[SCEV] Generalize no-self-wrap check in isLoopInvariantExitCondDuringFirstIterations" This reverts commit 7dcc8899174f44b7447bc48a9f2ff27f5458f8b7. This patch introduced a logical error that breaks whole logic of this analysis. All checks we are making are supposed to be loop-independent, so that we could safely remove the range check. The 'nw' fact is loop-dependent, so we can remove the check basing on facts from this very check. Motivating examples will follow-up. Added: Modified: llvm/lib/Analysis/ScalarEvolution.cpp Removed: ################################################################################ diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 08ed363918a9..5f77f4aa05c2 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -9643,19 +9643,17 @@ ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations( if (!ICmpInst::isRelational(Pred)) return None; + // TODO: Support steps other than +/- 1. const SCEV *Step = AR->getStepRecurrence(*this); - bool IsStepNonPositive = isKnownNonPositive(Step); - if (!IsStepNonPositive && !isKnownNonNegative(Step)) + auto *One = getOne(Step->getType()); + auto *MinusOne = getNegativeSCEV(One); + if (Step != One && Step != MinusOne) return None; - bool HasNoSelfWrap = AR->hasNoSelfWrap(); - if (!HasNoSelfWrap) - // If num iter has same type as the AddRec, and step is +/- 1, even max - // possible number of iterations is not enough to self-wrap. - if (MaxIter->getType() == AR->getType()) - if (Step == getOne(AR->getType()) || Step == getMinusOne(AR->getType())) - HasNoSelfWrap = true; - // Only proceed with non-self-wrapping ARs. - if (!HasNoSelfWrap) + + // Type mismatch here means that MaxIter is potentially larger than max + // unsigned value in start type, which mean we cannot prove no wrap for the + // indvar. + if (AR->getType() != MaxIter->getType()) return None; // Value of IV on suggested last iteration. @@ -9663,13 +9661,14 @@ ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations( // Does it still meet the requirement? if (!isKnownPredicateAt(Pred, Last, RHS, Context)) return None; - // We know that the addrec does not have a self-wrap. To prove that there is - // no signed/unsigned wrap, we need to check that - // Start <= Last for positive step or Start >= Last for negative step. Either - // works for zero step. + // Because step is +/- 1 and MaxIter has same type as Start (i.e. it does + // not exceed max unsigned value of this type), this effectively proves + // that there is no wrap during the iteration. To prove that there is no + // signed/unsigned wrap, we need to check that + // Start <= Last for step = 1 or Start >= Last for step = -1. ICmpInst::Predicate NoOverflowPred = CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; - if (IsStepNonPositive) + if (Step == MinusOne) NoOverflowPred = CmpInst::getSwappedPredicate(NoOverflowPred); const SCEV *Start = AR->getStart(); if (!isKnownPredicateAt(NoOverflowPred, Start, Last, Context)) _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
