From 7dcc8899174f44b7447bc48a9f2ff27f5458f8b7 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Wed, 11 Nov 2020 11:17:13 +0700 Subject: [PATCH] [SCEV] Generalize no-self-wrap check in isLoopInvariantExitCondDuringFirstIterations Lift limitation on step being `+/- 1`. In fact, the only thing it is needed for is proving no-self-wrap. We can instead check this flag directly. Theoretically it can increase the scope of the transform, but I could not construct such test easily. Differential Revision: https://reviews.llvm.org/D91126 Reviewed By: apilipenko --- llvm/lib/Analysis/ScalarEvolution.cpp | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 42d6a10..dc73b71 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -9589,17 +9589,19 @@ bool ScalarEvolution::isLoopInvariantExitCondDuringFirstIterations( if (!ICmpInst::isRelational(Pred)) return false; - // TODO: Support steps other than +/- 1. const SCEV *Step = AR->getStepRecurrence(*this); - auto *One = getOne(Step->getType()); - auto *MinusOne = getNegativeSCEV(One); - if (Step != One && Step != MinusOne) + bool IsStepNonPositive = isKnownNonPositive(Step); + if (!IsStepNonPositive && !isKnownNonNegative(Step)) return false; - - // 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()) + 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) return false; // Value of IV on suggested last iteration. @@ -9607,14 +9609,13 @@ bool ScalarEvolution::isLoopInvariantExitCondDuringFirstIterations( // Does it still meet the requirement? if (!isKnownPredicateAt(Pred, Last, RHS, Context)) return false; - // 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. + // 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. ICmpInst::Predicate NoOverflowPred = CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; - if (Step == MinusOne) + if (IsStepNonPositive) NoOverflowPred = CmpInst::getSwappedPredicate(NoOverflowPred); const SCEV *Start = AR->getStart(); if (!isKnownPredicateAt(NoOverflowPred, Start, Last, Context)) -- 2.7.4