[SCEV][WIP] Simplify Add and Mul expressions with Undef

[mkazantsev]

Summary

This patch teaches SCEV do following simplifications:

any + undef = undef
any * undef = undef

WIP because a lot of tests need update.

[fhahn]

I think it might be slightly better to refer to the result as unknown (SCEVUnknown) rather than undef, to avoid confusion with LLVM's undef semantics. IIUC, it looks like the patch propose the following

any + Expr with any unknown or undef operand = unknown
any * Expr with any unknown or undef operand = unknown

This in itself should be sound (Unknown is the most pessimistic value for SCEV), but might be unnecessarily pessimistic in some cases, e.g. 0 * undef/unknown == 0. If the simplification happens before the one proposed in the patch it should be fine.

[sanjoy]

I don't think we can fold undef within SCEV since SCEV's choice for undef might not be what other transformations choose. For instance if you have a loop:

// This program prints "hi" N times an then prints N where N is some
// non-deterministic value.
int i;
for (i = 0; i < undef; i++) {
  print('hi');
}
print(i)

and say SCEV internally folds undef to 5 "proving" the loop has trip count 5. Then IndVarSimplify can change the print(i) to print(5). However, InstCombine can later transform the i < undef to i < 1000 which would violate the program invariant (it will print hi 1000 times but then print 5).

[fhahn]

In my earlier comment, I missed that we might use the fact that the underlying value of SCEVUnknown is undef to fold it. In that case, the values chosen for the same use of an undef could diverge between SCEV and other transforms as mentioned by Sanjoy. Instcombine does not have this problem, as it does the replacements in place, but there is a similar problem in NewGVN.

[mkazantsev]

In D57578#1381929, @sanjoy wrote:

I don't think we can fold undef within SCEV since SCEV's choice for undef might not be what other transformations choose. For instance if you have a loop:

// This program prints "hi" N times an then prints N where N is some
// non-deterministic value.
int i;
for (i = 0; i < undef; i++) {
  print('hi');
}
print(i)

and say SCEV internally folds undef to 5 "proving" the loop has trip count 5. Then IndVarSimplify can change the print(i) to print(5). However, InstCombine can later transform the i < undef to i < 1000 which would violate the program invariant (it will print hi 1000 times but then print 5).

And how is that connected with this patch? :) In your example, there is no Add or Mul in SCEVs, the only (non-SCEVUnknown) SCEV will be SCEVAddRec. And yes, this problem exists even now. We seem to be lucky not stumbling over it.

The point of this patch is that undef + X is still undef, because we can always choose such value of undef to make it any value we want.

lib/Analysis/ScalarEvolution.cpp

StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
 
   return Flags;
 }
 
 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) {
   return isLoopInvariant(S, L) && properlyDominates(S, L->getHeader());
 }
 
+static Optional<const SCEVUnknown *> FindUndef(ArrayRef<const SCEV *> Args) {
+  auto It = find_if(Args, [](const SCEV *S) {
+    const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(S);
+    return SU && isa<UndefValue>(SU->getValue());
+  });
+  if (It == Args.end())
+    return None;
+  return cast<SCEVUnknown>(*It);
+}
+
 /// Get a canonical add expression, or something simpler if possible.
 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags Flags,
                                         unsigned Depth) {
   assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty add!");
   if (Ops.size() == 1) return Ops[0];
for (unsigned OtherIdx = Idx+1;
         return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
       }
     }
 
     // Otherwise couldn't fold anything into this recurrence.  Move onto the
     // next one.
   }
 
+  // Undef + anything = Undef.
+  auto SU = FindUndef(ArrayRef<const SCEV *>(Ops.begin() + Idx, Ops.end()));
+  if (SU)
+    return *SU;
+
   // Okay, it looks like we really DO need an add expr.  Check to see if we
   // already have one, otherwise create a new one.
   return getOrCreateAddExpr(Ops, Flags);
 }
 
 const SCEV *
 ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
                                     SCEV::NoWrapFlags Flags) {
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
     }
     if (OpsModified)
       return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
 
     // Otherwise couldn't fold anything into this recurrence.  Move onto the
     // next one.
   }
 
+  // Undef + anything = Undef.
+  auto SU = FindUndef(ArrayRef<const SCEV *>(Ops.begin() + Idx, Ops.end()));
+  if (SU)
+    return *SU;
+
   // Okay, it looks like we really DO need an mul expr.  Check to see if we
   // already have one, otherwise create a new one.
   return getOrCreateMulExpr(Ops, Flags);
 }
 
 /// Represents an unsigned remainder expression based on unsigned division.
 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
                                          const SCEV *RHS) {

test/Analysis/ScalarEvolution/different-loops-recs.ll

 ; CHECK-NEXT:  -->  {2,+,1}<%loop1>
 ; CHECK:       %tmp4 = add nuw nsw i64 %tmp, 1
 ; CHECK-NEXT:  -->  {3,+,1}<nuw><%loop1>
 ; CHECK:       %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ]
 ; CHECK-NEXT:  -->  {2,+,1}<nuw><nsw><%loop2>
 ; CHECK:       %tmp10 = sub i64 %tmp9, %tmp7
 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {-2,+,-1}<nw><%loop2>)
 ; CHECK:       %tmp11 = add i64 %tmp10, undef
-; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<nw><%loop2>)
+; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {undef,+,-1}<nw><%loop2>)
 ; CHECK:       %tmp13 = trunc i64 %tmp11 to i32
-; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {(-2 + (trunc i64 undef to i32)),+,-1}<%loop2>)
+; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {(trunc i64 undef to i32),+,-1}<%loop2>)
 ; CHECK:       %tmp14 = sub i32 %tmp13, %tmp2
 ; `{{[{][{]}}` is the ugliness needed to match `{{`
-; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {{[{][{]}}(-4 + (trunc i64 undef to i32)),+,-1}<%loop1>,+,-1}<%loop2>)
+; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {{[{][{]}}(trunc i64 undef to i32),+,-1}<%loop1>,+,-1}<%loop2>)
 ; CHECK:       %tmp15 = add nuw nsw i64 %tmp7, 1
 ; CHECK-NEXT:  -->  {3,+,1}<nuw><nsw><%loop2>
 
 bb:
   br label %loop1
 
 loop1:
   %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ]

test/Analysis/ScalarEvolution/scev-expander-reuse-gep.ll

 ; PR30213. Check scev expand will generate correct code if the value
 ; in ValueOffsetPair is of pointer type.
 ; RUN: opt -mtriple=i386-apple-macosx10.12.0 < %s -loop-reduce -S | FileCheck %s
 
 ; CHECK: %ptr4.ptr1 = select i1 %cmp.i, i8* %ptr4, i8* %ptr1
-; CHECK-NEXT: %scevgep = getelementptr i8, i8* %ptr4.ptr1, i32 1
 ; CHECK-NEXT: br label %while.cond.i
 
 target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
 target triple = "i386-apple-macosx10.12.0"
 
 ; Function Attrs: nounwind optsize ssp
 define void @Foo() {
 entry:

test/Analysis/ScalarEvolution/undefined.ll

 ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
 
 ; ScalarEvolution shouldn't attempt to interpret expressions which have
 ; undefined results.
 
 define void @foo(i64 %x) {
 
+; CHECK-LABEL: 'foo'
   %a = udiv i64 %x, 0
 ; CHECK: -->  (%x /u 0)
 
   %B = shl i64 %x, 64
 ; CHECK: -->  %B
 
   %b = ashr i64 %B, 64
 ; CHECK: -->  %b
; CHECK: -->  %f
   %g = shl i64 %x, -1
 ; CHECK: -->  %g
 
   %h = bitcast i64 undef to i64
 ; CHECK: -->  undef
 
   ret void
 }
+
+define void @add_mul(i32 %x) {
+
+; CHECK-LABEL: 'add_mul'
+; CHECK-NEXT:  Classifying expressions for: @add_mul
+; CHECK-NEXT:    %s1 = add i32 %x, undef
+; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    %s2 = mul i32 %s1, undef
+; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    %s3 = add i32 %s2, undef
+; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    %s4 = mul i32 %s3, undef
+; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    %s5 = add i32 %s4, undef
+; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:  Determining loop execution counts for: @add_mul
+;
+
+  %s1 = add i32 %x, undef
+  %s2 = mul i32 %s1, undef
+  %s3 = add i32 %s2, undef
+  %s4 = mul i32 %s3, undef
+  %s5 = add i32 %s4, undef
+  ret void
+}
 No newline at end of file

test/CodeGen/X86/coalesce-esp.ll

-; RUN: llc < %s | grep "movl  %esp, %ebp"
+; RUN: llc < %s | FileCheck %s
 ; PR4572
 
 ; Don't coalesce with %esp if it would end up putting %esp in
 ; the index position of an address, because that can't be
 ; encoded on x86. It would actually be slightly better to
 ; swap the address operands though, since there's no scale.
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
 target triple = "i386-pc-mingw32"
   %"struct.std::valarray<unsigned int>" = type { i32, i32* }
 
 define void @_ZSt17__gslice_to_indexjRKSt8valarrayIjES2_RS0_(i32 %__o, %"struct.std::valarray<unsigned int>"* nocapture %__l, %"struct.std::valarray<unsigned int>"* nocapture %__s, %"struct.std::valarray<unsigned int>"* nocapture %__i) nounwind {
+
+; CHECK-NOT: esp
+
 entry:
   %0 = alloca i32, i32 undef, align 4    ; <i32*> [#uses=1]
   br i1 undef, label %return, label %bb4
 
 bb4:    ; preds = %bb7.backedge, %entry
   %indvar = phi i32 [ %indvar.next, %bb7.backedge ], [ 0, %entry ]    ; <i32> [#uses=2]
   %scevgep24.sum = sub i32 undef, %indvar   ; <i32> [#uses=2]
   %scevgep25 = getelementptr i32, i32* %0, i32 %scevgep24.sum    ; <i32*> [#uses=1]

test/Transforms/IRCE/correct-loop-info.ll

 ; CHECK:       outerheader:
 ; CHECK-NEXT:    [[TMP:%.*]] = icmp slt i32 undef, 84
 ; CHECK-NEXT:    br i1 [[TMP]], label [[BB2:%.*]], label [[BB16:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br i1 false, label [[INNERHEADER_PRELOOP_PREHEADER:%.*]], label [[PRELOOP_PSEUDO_EXIT:%.*]]
 ; CHECK:       innerheader.preloop.preheader:
 ; CHECK-NEXT:    br label [[INNERHEADER_PRELOOP:%.*]]
 ; CHECK:       mainloop:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[INDVAR_END:%.*]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[INDVAR_END:%.*]], 1
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[INNERHEADER_PREHEADER:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
 ; CHECK:       innerheader.preheader:
 ; CHECK-NEXT:    br label [[INNERHEADER:%.*]]
 ; CHECK:       innerheader:
 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[TMP6:%.*]], [[BB8:%.*]] ], [ [[TMP4_PRELOOP_COPY:%.*]], [[INNERHEADER_PREHEADER]] ]
 ; CHECK-NEXT:    invoke void @pluto()
-; CHECK-NEXT:    to label [[BB5:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit.split-lp
+; CHECK-NEXT:    to label [[BB5:%.*]] unwind label [[OUTER_EXITING_LOOPEXIT_SPLIT_LP_LOOPEXIT_SPLIT_LP:%.*]]
 ; CHECK:       bb5:
 ; CHECK-NEXT:    [[TMP6]] = add i32 [[TMP4]], 1
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i32 [[TMP6]], 1
 ; CHECK-NEXT:    br i1 true, label [[BB8]], label [[EXIT3_LOOPEXIT5:%.*]]
 ; CHECK:       bb8:
 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i32 [[TMP6]], 84
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[TMP6]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[TMP6]], 1
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[INNERHEADER]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
 ; CHECK-NEXT:    [[TMP6_LCSSA:%.*]] = phi i32 [ [[TMP6]], [[BB8]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP6_LCSSA]], 84
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[MAIN_PSEUDO_EXIT]], label [[BB13:%.*]]
 ; CHECK:       main.pseudo.exit:
 ; CHECK-NEXT:    [[TMP4_COPY:%.*]] = phi i32 [ [[TMP4_PRELOOP_COPY]], [[MAINLOOP:%.*]] ], [ [[TMP6_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END1:%.*]] = phi i32 [ [[INDVAR_END]], [[MAINLOOP]] ], [ [[TMP6_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 ; CHECK:       outer_exiting.loopexit:
 ; CHECK-NEXT:    [[LPAD_LOOPEXIT:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    cleanup
 ; CHECK-NEXT:    br label [[OUTER_EXITING:%.*]]
 ; CHECK:       outer_exiting.loopexit.split-lp.loopexit:
 ; CHECK-NEXT:    [[LPAD_LOOPEXIT2:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    cleanup
-; CHECK-NEXT:    br label %outer_exiting.loopexit.split-lp
+; CHECK-NEXT:    br label [[OUTER_EXITING_LOOPEXIT_SPLIT_LP:%.*]]
 ; CHECK:       outer_exiting.loopexit.split-lp.loopexit.split-lp:
-; CHECK-NEXT:    %lpad.loopexit.split-lp3 = landingpad { i8*, i32 }
+; CHECK-NEXT:    [[LPAD_LOOPEXIT_SPLIT_LP3:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    cleanup
-; CHECK-NEXT:    br label %outer_exiting.loopexit.split-lp
+; CHECK-NEXT:    br label [[OUTER_EXITING_LOOPEXIT_SPLIT_LP]]
 ; CHECK:       outer_exiting.loopexit.split-lp:
 ; CHECK-NEXT:    br label [[OUTER_EXITING]]
 ; CHECK:       outer_exiting:
 ; CHECK-NEXT:    switch i32 undef, label [[EXIT2:%.*]] [
 ; CHECK-NEXT:    i32 142, label [[BB14:%.*]]
 ; CHECK-NEXT:    i32 448, label [[EXIT:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       exit3.loopexit:

 ; CHECK-NEXT:    invoke void @pluto()
 ; CHECK-NEXT:    to label [[BB5_PRELOOP:%.*]] unwind label [[OUTER_EXITING_LOOPEXIT:%.*]]
 ; CHECK:       bb5.preloop:
 ; CHECK-NEXT:    [[TMP6_PRELOOP]] = add i32 [[TMP4_PRELOOP]], 1
 ; CHECK-NEXT:    [[TMP7_PRELOOP:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 1
 ; CHECK-NEXT:    br i1 [[TMP7_PRELOOP]], label [[BB8_PRELOOP]], label [[EXIT3_LOOPEXIT:%.*]]
 ; CHECK:       bb8.preloop:
 ; CHECK-NEXT:    [[TMP9_PRELOOP:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 84
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], -1
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 0
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[INNERHEADER_PRELOOP]], label [[PRELOOP_EXIT_SELECTOR:%.*]], !llvm.loop !0, !irce.loop.clone !5
 ; CHECK:       preloop.exit.selector:
 ; CHECK-NEXT:    [[TMP6_PRELOOP_LCSSA:%.*]] = phi i32 [ [[TMP6_PRELOOP]], [[BB8_PRELOOP]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i32 [[TMP6_PRELOOP_LCSSA]], 84
 ; CHECK-NEXT:    br i1 [[TMP4]], label [[PRELOOP_PSEUDO_EXIT]], label [[BB13]]
 ; CHECK:       preloop.pseudo.exit:
 ; CHECK-NEXT:    [[TMP4_PRELOOP_COPY]] = phi i32 [ undef, [[BB2]] ], [ [[TMP6_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END]] = phi i32 [ undef, [[BB2]] ], [ [[TMP6_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[MAINLOOP]]
 ; CHECK:       postloop:
 ; CHECK-NEXT:    br label [[INNERHEADER_POSTLOOP:%.*]]
 ; CHECK:       innerheader.postloop:
 ; CHECK-NEXT:    [[TMP4_POSTLOOP:%.*]] = phi i32 [ [[TMP6_POSTLOOP:%.*]], [[BB8_POSTLOOP:%.*]] ], [ [[TMP4_COPY]], [[POSTLOOP]] ]
 ; CHECK-NEXT:    invoke void @pluto()
-; CHECK-NEXT:    to label [[BB5_POSTLOOP:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit
+; CHECK-NEXT:    to label [[BB5_POSTLOOP:%.*]] unwind label [[OUTER_EXITING_LOOPEXIT_SPLIT_LP_LOOPEXIT:%.*]]
 ; CHECK:       bb5.postloop:
 ; CHECK-NEXT:    [[TMP6_POSTLOOP]] = add i32 [[TMP4_POSTLOOP]], 1
 ; CHECK-NEXT:    [[TMP7_POSTLOOP:%.*]] = icmp slt i32 [[TMP6_POSTLOOP]], 1
 ; CHECK-NEXT:    br i1 [[TMP7_POSTLOOP]], label [[BB8_POSTLOOP]], label [[EXIT3_LOOPEXIT4:%.*]]
 ; CHECK:       bb8.postloop:
 ; CHECK-NEXT:    [[TMP9_POSTLOOP:%.*]] = icmp slt i32 [[TMP6_POSTLOOP]], 84
 ; CHECK-NEXT:    br i1 [[TMP9_POSTLOOP]], label [[INNERHEADER_POSTLOOP]], label [[BB13_LOOPEXIT:%.*]], !llvm.loop !6, !irce.loop.clone !5
 ;

test/Transforms/IndVarSimplify/lcssa-preservation.ll

 ; CHECK: outer.header:
   %outer.iv = phi i32 [ 0, %entry ], [ %x, %outer.latch ]
   br label %inner.header
 ; CHECK:   %[[SCEV_EXPANDED:.*]] = add i32
 ; CHECK:   br label %inner.header
 
 inner.header:
 ; CHECK: inner.header:
-  %inner.iv = phi i32 [ undef, %outer.header ], [ %inc, %inner.latch ]
+  %inner.iv = phi i32 [ %x, %outer.header ], [ %inc, %inner.latch ]
   %cmp1 = icmp slt i32 %inner.iv, %outer.iv
   br i1 %cmp1, label %inner.latch, label %outer.latch
 ; CHECK:   br i1 {{.*}}, label %inner.latch, label %outer.latch
 
 inner.latch:
 ; CHECK: inner.latch:
   %inc = add nsw i32 %inner.iv, 1
   %cmp2 = icmp slt i32 %inner.iv, %outer.iv