SCEVExpander incorrectly marks generated subtractions as nuw/nsw

[sanjoy]

Summary

It is not sound to mark the increment operation as nuw or nsw
based on a proof off of the add recurrence if the increment operation
we emit happens to be a sub instruction.

I could not come up with a test case for this -- the cases where
SCEVExpander decides to emit a sub instruction is quite small, and I
cannot think of a way I'd be able to get SCEV to prove that the
increment does not overflow in those cases.

[atrick]

LGTM

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

if (AddRecPhiMatch) {
       // Remember this PHI, even in post-inc mode.
       InsertedValues.insert(AddRecPhiMatch);
       // Remember the increment.
       rememberInstruction(IncV);
       return AddRecPhiMatch;
     }
   }
 
-  bool IncrementIsNUW = IsIncrementNUW(SE, Normalized);
-  bool IncrementIsNSW = IsIncrementNSW(SE, Normalized);
-
   // Save the original insertion point so we can restore it when we're done.
   BuilderType::InsertPointGuard Guard(Builder);
 
   // Another AddRec may need to be recursively expanded below. For example, if
   // this AddRec is quadratic, the StepV may itself be an AddRec in this
   // loop. Remove this loop from the PostIncLoops set before expanding such
   // AddRecs. Otherwise, we cannot find a valid position for the step
   // (i.e. StepV can never dominate its loop header).  Ideally, we could do
SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
   // (unless it's a constant, because subtracts of constants are canonicalized
   // to adds).
   bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
   if (useSubtract)
     Step = SE.getNegativeSCEV(Step);
   // Expand the step somewhere that dominates the loop header.
   Value *StepV = expandCodeFor(Step, IntTy, L->getHeader()->begin());
 
+  // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
+  // we actually do emit an addition.  It does not apply if we emit a
+  // subtraction.
+  bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
+  bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
+
   // Create the PHI.
   BasicBlock *Header = L->getHeader();
   Builder.SetInsertPoint(Header, Header->begin());
   pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
   PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
                                   Twine(IVName) + ".iv");
   rememberInstruction(PN);