[SCEV] Don't always add no-wrap flags to post-inc add recs

[sanjoy]

Summary

Fixes PR27315.

The post-inc version of an add recurrence needs to "follow the same
rules" as a normal add or subtract expression. Otherwise we miscompile
programs like

int main() {
  int a = 0;
  unsigned a_u = 0;
  volatile long last_value;
  do {
    a_u += 3;
    last_value = (long) ((int) a_u);
    if (will_add_overflow(a, 3)) {
      // Leave, and don't actually do the increment, so no UB.
      printf("last_value = %ld\n", last_value);
      exit(0);
    }
    a += 3;
  } while (a != 46);
  return 0;
}

Some previous patches (added as dependencies here) are needed for this
not regress performance too much.

Depends on: D19209
Depends on: D19210
Depends on: D19211
Depends on: D19212

[hfinkel]

LGTM.

lib/Analysis/ScalarEvolution.cpp

3990

Indentation looks odd here.

[sanjoy]

In D19213#412351, @hfinkel wrote:

LGTM.

Hi Hal,

Thanks for the review; but just FYI: it looks like one of the key changes I was relying on to have this pass not regress too much performance is incorrect (D19211). I'm now exploring other, less performance hurting ways to fix the same underlying issue as this bug.

[sanjoy]

I've checked in a somewhat modified form of this in rL271151

lib/Analysis/ScalarEvolution.cpp

if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
 
         // This is not a valid addrec if the step amount is varying each
         // loop iteration, but is not itself an addrec in this loop.
         if (isLoopInvariant(Accum, L) ||
             (isa<SCEVAddRecExpr>(Accum) &&
              cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
 
-          // If the increment doesn't overflow, then neither the addrec nor
-          // the post-increment will overflow.
           if (auto BO = MatchBinaryOp(BEValueV)) {
             if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
               if (BO->IsNUW)
                 Flags = setFlags(Flags, SCEV::FlagNUW);
               if (BO->IsNSW)
                 Flags = setFlags(Flags, SCEV::FlagNSW);
             }
           } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(BEValueV)) {
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
             // We cannot transfer nuw and nsw flags from subtraction
             // operations -- sub nuw X, Y is not the same as add nuw X, -Y
             // for instance.
           }
 
           const SCEV *StartVal = getSCEV(StartValueV);
           const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
 
-          // Since the no-wrap flags are on the increment, they apply to the
-          // post-incremented value as well.
-          if (isLoopInvariant(Accum, L))
-            (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
-
           // 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.
           forgetSymbolicName(PN, SymbolicName);
           ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
+
+    // We can add Flags to the post-inc expression only if we
+    // know that it us *undefined behavior* for BEValueV to
+    // overflow.
+          if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
+            if (isLoopInvariant(Accum, L) && isSCEVExprNeverPoison(BEInst))
+              (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
+
           return PHISCEV;
         }
       }
     } else {
       // Otherwise, this could be a loop like this:
       //     i = 0;  for (j = 1; ..; ++j) { ....  i = j; }
       // In this case, j = {1,+,1}  and BEValue is j.
       // Because the other in-value of i (0) fits the evolution of BEValue

test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll

 ; ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
 
-define void @infer.sext.0(i1* %c, i32 %start) {
+define void @infer.sext.0(i1* %c, i32 %start, i32* %buf) {
 ; CHECK-LABEL: Classifying expressions for: @infer.sext.0
  entry:
   br label %loop
 
  loop:
   %counter = phi i32 [ 0, %entry ], [ %counter.inc, %loop ]
   %idx = phi i32 [ %start, %entry ], [ %idx.inc, %loop ]
   %idx.inc = add nsw i32 %idx, 1
   %idx.inc.sext = sext i32 %idx.inc to i64
 ; CHECK: %idx.inc.sext = sext i32 %idx.inc to i64
 ; CHECK-NEXT: -->  {(1 + (sext i32 %start to i64))<nsw>,+,1}<nsw><%loop>
+
+  %buf.gep = getelementptr inbounds i32, i32* %buf, i32 %idx.inc
+  %val = load i32, i32* %buf.gep
+
   %condition = icmp eq i32 %counter, 1
   %counter.inc = add i32 %counter, 1
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 
-define void @infer.zext.0(i1* %c, i32 %start) {
+define void @infer.zext.0(i1* %c, i32 %start, i32* %buf) {
 ; CHECK-LABEL: Classifying expressions for: @infer.zext.0
  entry:
   br label %loop
 
  loop:
   %counter = phi i32 [ 0, %entry ], [ %counter.inc, %loop ]
   %idx = phi i32 [ %start, %entry ], [ %idx.inc, %loop ]
   %idx.inc = add nuw i32 %idx, 1
   %idx.inc.sext = zext i32 %idx.inc to i64
 ; CHECK: %idx.inc.sext = zext i32 %idx.inc to i64
 ; CHECK-NEXT: -->  {(1 + (zext i32 %start to i64))<nuw><nsw>,+,1}<nuw><%loop>
+
+  %buf.gep = getelementptr inbounds i32, i32* %buf, i32 %idx.inc
+  %val = load i32, i32* %buf.gep
+
   %condition = icmp eq i32 %counter, 1
   %counter.inc = add i32 %counter, 1
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 

test/Analysis/ScalarEvolution/nowrap-preinc-limits.ll

loop:
   %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop ]
   %idx.inc = add nsw i32 %idx, 3
 
   %idx.inc2 = add i32 %idx.inc, -1
   %idx.inc2.sext = sext i32 %idx.inc2 to i64
 ; CHECK: %idx.inc2.sext = sext i32 %idx.inc2 to i64
 ; CHECK-NEXT: -->  {2,+,3}<nuw><nsw><%loop>
 
-  %c = load volatile i1, i1* %condition
+  %cond.gep = getelementptr inbounds i1, i1* %condition, i32 %idx.inc
+  %c = load volatile i1, i1* %cond.gep
   br i1 %c, label %loop, label %exit
 
  exit:
   ret void
 }

test/Analysis/ScalarEvolution/nsw.ll

; CHECK-NEXT: -->  {0,+,1}<nuw><nsw><%bb>
   %tmp6 = sext i32 %i.01 to i64   ; <i64> [#uses=1]
   %tmp7 = getelementptr double, double* %p, i64 %tmp6    ; <double*> [#uses=1]
 ; CHECK: %tmp7
 ; CHECK-NEXT:   -->  {%p,+,8}<%bb>
   store double %tmp5, double* %tmp7, align 8
   %tmp8 = add nsw i32 %i.01, 1    ; <i32> [#uses=2]
 ; CHECK: %tmp8
 ; CHECK-NEXT: -->  {1,+,1}<nuw><nsw><%bb>
+  %p.gep = getelementptr double, double* %p, i32 %tmp8
+  %p.val = load double, double* %p.gep
   br label %bb1
 
 bb1:    ; preds = %bb
   %phitmp = sext i32 %tmp8 to i64   ; <i64> [#uses=1]
 ; CHECK: %phitmp
 ; CHECK-NEXT: -->  {1,+,1}<nuw><nsw><%bb>
-  %tmp9 = getelementptr double, double* %p, i64 %phitmp    ; <double*> [#uses=1]
+  %tmp9 = getelementptr inbounds double, double* %p, i64 %phitmp    ; <double*> [#uses=1]
 ; CHECK: %tmp9
-; CHECK-NEXT:  -->  {(8 + %p),+,8}<%bb>
+; CHECK-NEXT:  -->  {(8 + %p),+,8}<nsw><%bb>
   %tmp10 = load double, double* %tmp9, align 8    ; <double> [#uses=1]
   %tmp11 = fcmp ogt double %tmp10, 2.000000e+00    ; <i1> [#uses=1]
   br i1 %tmp11, label %bb, label %bb1.return_crit_edge
 
 bb1.return_crit_edge:   ; preds = %bb1
   br label %return
 
 return:   ; preds = %bb1.return_crit_edge, %entry
bb1:                                              ; preds = %bb1, %bb
   %tmp6 = icmp ult i32* %tmp5, %tmp
   br i1 %tmp6, label %bb1, label %bb7
 
 bb7:                                              ; preds = %bb1
   ret i32 %tmp4
 }
 
 ; CHECK-LABEL: PR12376
-; CHECK: -->  {(4 + %arg),+,4}<nuw><%bb2>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((3 + (-1 * %arg) + (%arg umax %arg1)) /u 4)) + %arg)
+; CHECK: -->  {(4 + %arg),+,4}<nuw><%bb2>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((-1 + (-1 * %arg) + ((4 + %arg) umax %arg1)) /u 4)) + %arg)
 define void @PR12376(i32* nocapture %arg, i32* nocapture %arg1)  {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb2, %bb
   %tmp = phi i32* [ %arg, %bb ], [ %tmp4, %bb2 ]
-  %tmp3 = icmp ult i32* %tmp, %arg1
   %tmp4 = getelementptr inbounds i32, i32* %tmp, i64 1
+  %tmp3 = icmp ult i32* %tmp4, %arg1
   br i1 %tmp3, label %bb2, label %bb5
 
 bb5:                                              ; preds = %bb2
   ret void
 }
 
 declare void @f(i32)
 
 ; CHECK-LABEL: nswnowrap
 ; CHECK: --> {(1 + %v),+,1}<nsw><%for.body>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (2 + %v)
-define void @nswnowrap(i32 %v) {
+define void @nswnowrap(i32 %v, i32* %buf) {
 entry:
   %add = add nsw i32 %v, 1
   br label %for.body
 
 for.body:
   %i.04 = phi i32 [ %v, %entry ], [ %inc, %for.body ]
   %inc = add nsw i32 %i.04, 1
-  tail call void @f(i32 %i.04)
+  %buf.gep = getelementptr inbounds i32, i32* %buf, i32 %inc
+  %buf.val = load i32, i32* %buf.gep
   %cmp = icmp slt i32 %i.04, %add
+  tail call void @f(i32 %i.04)
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }

test/Analysis/ScalarEvolution/pr27315.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+declare i1 @use(i64)
+
+define void @f_0() {
+; CHECK-LABEL: Classifying expressions for: @f_0
+
+; CHECK:  %iv = phi i32 [ 0, %entry ], [ %iv.inc.nowrap, %be ]
+; CHECK-NEXT: -->  {0,+,1}<nuw><nsw><%loop>
+; CHECK: %iv.inc.maywrap = add i32 %iv, 1
+; CHECK-NEXT: -->  {1,+,1}<nuw><%loop>
+; CHECK:  %iv.inc.maywrap.sext = sext i32 %iv.inc.maywrap to i64
+; CHECK-NEXT:  -->  (sext i32 {1,+,1}<nuw><%loop> to i64)
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc.nowrap, %be ]
+  %iv.inc.maywrap = add i32 %iv, 1
+  %iv.inc.maywrap.sext = sext i32 %iv.inc.maywrap to i64
+  %cond0 = call i1 @use(i64 %iv.inc.maywrap.sext)
+  br i1 %cond0, label %be, label %leave
+
+be:
+  %iv.inc.nowrap = add nsw i32 %iv, 1
+  %be.cond = call i1 @use(i64 0) ;; Get an unanalyzable value
+  br i1 %be.cond, label %loop, label %leave
+
+leave:
+  ret void
+}

test/Transforms/IndVarSimplify/elim-extend.ll

loop:
   %preadr = getelementptr i8, i8* %base, i64 %preofs
   store i8 0, i8* %preadr
   %postiv = add i32 %iv, 1
   %postofs = sext i32 %postiv to i64
   %postadr = getelementptr i8, i8* %base, i64 %postofs
   store i8 0, i8* %postadr
   %postivnsw = add nsw i32 %ivnsw, 1
   %postofsnsw = sext i32 %postivnsw to i64
-  %postadrnsw = getelementptr i8, i8* %base, i64 %postofsnsw
+  %postadrnsw = getelementptr inbounds i8, i8* %base, i64 %postofsnsw
   store i8 0, i8* %postadrnsw
   %cond = icmp sgt i32 %limit, %iv
   br i1 %cond, label %loop, label %exit
 exit:
   br label %return
 return:
   ret void
 }