Fix bug 22641

The bug was a result of getPreStartForExtend interpreting nsw/nuw
flags on an add recurrence more strongly than is legal.  {S,+,X}<nsw>
implies S+X is nsw only if the backedge of the loop is taken at least
once.

NOTE: I had accidentally committed an unrelated change with the commit
message of this change in r230275 (r230275 was reverted in r230279).
This is the correct change for this commit message.

Differential Revision: http://reviews.llvm.org/D7808

llvm-svn: 230291

1 files changed, 5 insertions, 17 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 22e361c22de..9e4eb111c2e 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -1274,25 +1274,13 @@ static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty,
   const SCEVAddRecExpr *PreAR = dyn_cast<SCEVAddRecExpr>(
       SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
 
-  // WARNING: FIXME: the optimization below assumes that a sign/zero-overflowing
-  // nsw/nuw operation is undefined behavior.  This is strictly more aggressive
-  // than the interpretation of nsw in other parts of LLVM (for instance, they
-  // may unconditionally hoist nsw/nuw arithmetic through control flow).  This
-  // logic needs to be revisited once we have a consistent semantics for poison
-  // values.
-  //
-  // "{S,+,X} is <nsw>/<nuw>" and "{S,+,X} is evaluated at least once" implies
-  // "S+X does not sign/unsign-overflow" (we'd have undefined behavior if it
-  // did).  If `L->getExitingBlock() == L->getLoopLatch()` then `PreAR` (=
-  // {S,+,X}<nsw>/<nuw>) is evaluated every-time `AR` (= {S+X,+,X}) is
-  // evaluated, and hence within `AR` we are safe to assume that "S+X" will not
-  // sign/unsign-overflow.
+  // "{S,+,X} is <nsw>/<nuw>" and "the backedge is taken at least once" implies
+  // "S+X does not sign/unsign-overflow".
   //
 
-  BasicBlock *ExitingBlock = L->getExitingBlock();
-  BasicBlock *LatchBlock = L->getLoopLatch();
-  if (PreAR && PreAR->getNoWrapFlags(WrapType) && ExitingBlock != nullptr &&
-      ExitingBlock == LatchBlock)
+  const SCEV *BECount = SE->getBackedgeTakenCount(L);
+  if (PreAR && PreAR->getNoWrapFlags(WrapType) &&
+      !isa<SCEVCouldNotCompute>(BECount) && SE->isKnownPositive(BECount))
     return PreStart;
 
   // 2. Direct overflow check on the step operation's expression.