Bugfix: ScalarEvolution incorrectly assumes that the start of certain

add recurrences don't overflow.

This change makes the optimization more restrictive.  It still assumes
that an overflowing `add nsw` is undefined behavior; and this change
will need revisiting once we have a consistent semantics for poison
values.

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

llvm-svn: 228552

1 files changed, 18 insertions, 1 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 9b9e7dc5eea..8f2e4f2ba28 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -1364,7 +1364,24 @@ static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
   const SCEVAddRecExpr *PreAR = dyn_cast<SCEVAddRecExpr>(
     SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
 
-  if (PreAR && PreAR->getNoWrapFlags(SCEV::FlagNSW))
+  // WARNING: FIXME: the optimization below assumes that a sign-overflowing nsw
+  // 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 arithmetic through control flow).  This logic
+  // needs to be revisited once we have a consistent semantics for poison
+  // values.
+  //
+  // "{S,+,X} is <nsw>" and "{S,+,X} is evaluated at least once" implies "S+X
+  // does not sign-overflow" (we'd have undefined behavior if it did).  If
+  // `L->getExitingBlock() == L->getLoopLatch()` then `PreAR` (= {S,+,X}<nsw>)
+  // 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-overflow.
+  //
+
+  BasicBlock *ExitingBlock = L->getExitingBlock();
+  BasicBlock *LatchBlock = L->getLoopLatch();
+  if (PreAR && PreAR->getNoWrapFlags(SCEV::FlagNSW) &&
+      ExitingBlock != nullptr && ExitingBlock == LatchBlock)
     return PreStart;
 
   // 2. Direct overflow check on the step operation's expression.