Fix PR22179

[sanjoy]

Summary

We were incorrectly inferring nsw for certain SCEVs. We can be more aggressive here (see Richard Smith's comment on http://llvm.org/bugs/show_bug.cgi?id=22179) but this change just focuses on correctness.

[majnemer]

lib/Analysis/ScalarEvolution.cpp

1748–1749

The extra parens don't really add to readability here and the expression is formatted a little funny, consider using clang-format here.

1757–1758

Why isn't this just equivalent to if (SignOrUnsignWrap == SCEV::FlagNSW) ?

[sanjoy]

Address David's review. Functionally this exactly the same as the previous patch.

[majnemer]

LGTM with nits.

lib/Analysis/ScalarEvolution.cpp

1758

std::bind1st and std::mem_fun are deprecated in C++11, we should probably avoid new references to them.

How about:

auto IsKnownNonNegative =
    std::bind(std::mem_fn(&ScalarEvolution::isKnownNonNegative), SE));

1761

This looks way nicer :)

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

1758

Done.

1761

I changed this to if (SignOrUnsignWrap == SCEV::FlagNSW && std::all_of(Ops.begin(), Ops.end(), IsKnownNonNegative)) before checking in -- that reduces one level of nesting.

lib/Analysis/ScalarEvolution.cpp

 namespace {
   struct APIntCompare {
     bool operator()(const APInt &LHS, const APInt &RHS) const {
       return LHS.ult(RHS);
     }
   };
 }
 
+// We're trying to construct a SCEV of type `Type' with `Ops' as operands and
+// `OldFlags' as can't-wrap behavior.  Infer a more aggressive set of
+// can't-overflow flags for the operation if possible.
+static SCEV::NoWrapFlags
+StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
+                      const SmallVectorImpl<const SCEV *> &Ops,
+                      SCEV::NoWrapFlags OldFlags) {
+  bool CanAnalyze =
+      Type == scAddExpr || Type == scAddRecExpr || Type == scMulExpr;
+  (void)CanAnalyze;
+  assert(CanAnalyze && "don't call from other places!");
+
+  // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
+  int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
+  SCEV::NoWrapFlags SignOrUnsignWrap =
+      ScalarEvolution::maskFlags(OldFlags, SignOrUnsignMask);
+
+  auto IsKnownNonNegative =
+      std::bind1st(std::mem_fun(&ScalarEvolution::isKnownNonNegative), SE);
+
+  if (SignOrUnsignWrap == SCEV::FlagNSW)
+    if (std::all_of(Ops.begin(), Ops.end(), IsKnownNonNegative))
+      return ScalarEvolution::setFlags(OldFlags,
+                                       (SCEV::NoWrapFlags)SignOrUnsignMask);
+
+  return OldFlags;
+}
+
 /// getAddExpr - Get a canonical add expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags Flags) {
   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];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "SCEVAddExpr operand types don't match!");
 #endif
 
-  // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
-  // And vice-versa.
-  int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
-  SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
-  if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
-    bool All = true;
-    for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
-         E = Ops.end(); I != E; ++I)
-      if (!isKnownNonNegative(*I)) {
-        All = false;
-        break;
-      }
-    if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
-  }
+  Flags = StrengthenNoWrapFlags(this, scAddExpr, Ops, Flags);
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, LI);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
     ++Idx;
const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "SCEVMulExpr operand types don't match!");
 #endif
 
-  // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
-  // And vice-versa.
-  int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
-  SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
-  if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
-    bool All = true;
-    for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
-         E = Ops.end(); I != E; ++I)
-      if (!isKnownNonNegative(*I)) {
-        All = false;
-        break;
-      }
-    if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
-  }
+  Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags);
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, LI);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 
#endif
   }
 
   // It's tempting to want to call getMaxBackedgeTakenCount count here and
   // use that information to infer NUW and NSW flags. However, computing a
   // BE count requires calling getAddRecExpr, so we may not yet have a
   // meaningful BE count at this point (and if we don't, we'd be stuck
   // with a SCEVCouldNotCompute as the cached BE count).
 
-  // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
-  // And vice-versa.
-  int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
-  SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
-  if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
-    bool All = true;
-    for (SmallVectorImpl<const SCEV *>::const_iterator I = Operands.begin(),
-         E = Operands.end(); I != E; ++I)
-      if (!isKnownNonNegative(*I)) {
-        All = false;
-        break;
-      }
-    if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
-  }
+  Flags = StrengthenNoWrapFlags(this, scAddRecExpr, Operands, Flags);
 
   // Canonicalize nested AddRecs in by nesting them in order of loop depth.
   if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
     const Loop *NestedLoop = NestedAR->getLoop();
     if (L->contains(NestedLoop) ?
         (L->getLoopDepth() < NestedLoop->getLoopDepth()) :
         (!NestedLoop->contains(L) &&
          DT->dominates(L->getHeader(), NestedLoop->getHeader()))) {

test/Analysis/ScalarEvolution/pr22179.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+%struct.anon = type { i8 }
+%struct.S = type { i32 }
+
+@a = common global %struct.anon zeroinitializer, align 1
+@b = common global %struct.S zeroinitializer, align 4
+
+; Function Attrs: nounwind ssp uwtable
+define i32 @main() {
+; CHECK-LABEL: Classifying expressions for: @main
+  store i8 0, i8* getelementptr inbounds (%struct.anon* @a, i64 0, i32 0), align 1
+  br label %loop
+
+loop:
+  %storemerge1 = phi i8 [ 0, %0 ], [ %inc, %loop ]
+  %m = load volatile i32* getelementptr inbounds (%struct.S* @b, i64 0, i32 0), align 4
+  %inc = add nuw i8 %storemerge1, 1
+; CHECK:   %inc = add nuw i8 %storemerge1, 1
+; CHECK-NEXT: -->  {1,+,1}<nuw><%loop>
+; CHECK-NOT: -->  {1,+,1}<nuw><nsw><%loop>
+  %exitcond = icmp eq i8 %inc, -128
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  store i8 -128, i8* getelementptr inbounds (%struct.anon* @a, i64 0, i32 0), align 1
+  ret i32 0
+}

test/CodeGen/X86/avoid_complex_am.ll

 ; CHECK: [[IV:%[^ ]+]] = phi i64 [ [[IVNEXT:%[^,]+]], %for.body ], [ 0, %entry ]
 ; Only one induction variable should have been generated.
 ; CHECK-NOT: phi
   %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
   %tmp = add nsw i64 %indvars.iv, -1
   %arrayidx = getelementptr inbounds double* %b, i64 %tmp
   %tmp1 = load double* %arrayidx, align 8
 ; The induction variable should carry the scaling factor: 1.
-; CHECK: [[IVNEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK: [[IVNEXT]] = add nuw i64 [[IV]], 1
   %indvars.iv.next = add i64 %indvars.iv, 1
   %arrayidx2 = getelementptr inbounds double* %c, i64 %indvars.iv.next
   %tmp2 = load double* %arrayidx2, align 8
   %mul = fmul double %tmp1, %tmp2
   %arrayidx4 = getelementptr inbounds double* %a, i64 %indvars.iv
   store double %mul, double* %arrayidx4, align 8
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 ; Comparison should be 19 * 1 = 19.
 ; CHECK: icmp eq i32 {{%[^,]+}}, 19
   %exitcond = icmp eq i32 %lftr.wideiv, 20
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }