[SCEV] Also strengthen flags for post-increment.

[fhahn]

Summary

Also strengthen the flags for the post-increment SCEV, as suggested by
@mkazantsev.

Depends on D144050.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll

12

It's amazing how pessimistic we are here. Everything is going through nsw, but we still manage to cross upper bound of signed range. Sigh...

[nikic]

llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll

12

It's a half-open range, so this doesn't actually cross the upper bound.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

5673

It's not really obvious to me why this is correct. Can't the extra addition of the post-inc addrec overflow, even if the pre-inc addrec can't? I believe the current reasoning for setting flags on the post-inc addrec is specifically about nowrap flags present in IR that would result in UB if violated. I don't think this would hold up for flags inferred from the pre-inc addrec range.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

5673

It's also not really obvious to me as mentioned here: https://reviews.llvm.org/D144050#inline-1404195

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
   if (BO->IsNSW)
     Flags = setFlags(Flags, SCEV::FlagNSW);
 
   const SCEV *StartVal = getSCEV(StartValueV);
   const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
   insertValueToMap(PN, PHISCEV);
 
   if (auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
-    setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR),
-                   (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
-                                       proveNoWrapViaConstantRanges(AR)));
+    Flags = (SCEV::NoWrapFlags)(Flags | proveNoWrapViaConstantRanges(AR));
+    setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), Flags);
   }
 
   // We can add Flags to the post-inc expression only if we
   // know that it is *undefined behavior* for BEValueV to
   // overflow.
   if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
     assert(isLoopInvariant(Accum, L) &&
            "Accum is defined outside L, but is not invariant?");
if (FoundIndex != Add->getNumOperands()) {
 
         // Okay, for the entire analysis of this edge we assumed the PHI
         // to be symbolic.  We now need to go back and purge all of the
         // entries for the scalars that use the symbolic expression.
         forgetMemoizedResults(SymbolicName);
         insertValueToMap(PN, PHISCEV);
 
         if (auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
-          setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR),
-                         (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
-                                             proveNoWrapViaConstantRanges(AR)));
+
+          Flags = (SCEV::NoWrapFlags)(Flags | proveNoWrapViaConstantRanges(AR));
+          setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), Flags);
         }
 
         // We can add Flags to the post-inc expression only if we
         // know that it is *undefined behavior* for BEValueV to
         // overflow.
         if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
           if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
             (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);

llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @f0() {
 ; CHECK-LABEL: 'f0'
 ; CHECK-NEXT:  Classifying expressions for: @f0
 ; CHECK-NEXT:    %v0 = phi i16 [ 2, %b0 ], [ %v2, %b1 ]
 ; CHECK-NEXT:    --> {2,+,1}<nuw><nsw><%b1> U: [2,4) S: [2,4) Exits: 3 LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:    %v1 = phi i16 [ 1, %b0 ], [ %v3, %b1 ]
-; CHECK-NEXT:    --> {1,+,2,+,1}<%b1> U: full-set S: full-set Exits: 3 LoopDispositions: { %b1: Computable }
+; CHECK-NEXT:    --> {1,+,2,+,1}<nsw><%b1> U: [1,-32768) S: [1,-32768) Exits: 3 LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:    %v2 = add nsw i16 %v0, 1
 ; CHECK-NEXT:    --> {3,+,1}<nuw><nsw><%b1> U: [3,5) S: [3,5) Exits: 4 LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:    %v3 = add nsw i16 %v1, %v0
 ; CHECK-NEXT:    --> {3,+,3,+,1}<%b1> U: full-set S: full-set Exits: 6 LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:    %v4 = and i16 %v3, 1
 ; CHECK-NEXT:    --> (zext i1 {true,+,true,+,true}<%b1> to i16) U: [0,2) S: [0,2) Exits: 0 LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @f0
 ; CHECK-NEXT:  Loop %b1: backedge-taken count is 1