[SCEV] Keep common NUW flags when inlining Add operands.

[fhahn]

Summary

Currently, NoWrapFlags are dropped if we inline operands of SCEVAddExpr
operands. As a consequence, we always drop flags when building
expressions like getAddExpr(A, getAddExpr(B, C, NUW), NUW).

We should be able to retain NUW flags common among all inlined
SCEVAddExpr and the original flags.

[mkazantsev]

As far as I understand what is a nsw for multi-argument add, it means that there should be no wrap in between if we add the operands one by one in any order. Imagine the case when a = c = SINT_MIN and b = d = SINT_MAX. We can say that a+b has <nsw>, c+d has <nsw>, and (a+b) + (c+d) also has nsw. But if we say that getAddExpr(getAddExpr(a, b, nsw), getAddExpr(c, d, nsw), nsw) = getAddExpr(a, b, c, d, nsw), it's not true if we compute the latter as a + c + b + d. It will overflow on a + c already. Is my understanding wrong here?

[fhahn]

In D103877#2805474, @mkazantsev wrote:

As far as I understand what is a nsw for multi-argument add, it means that there should be no wrap in between if we add the operands one by one in any order. Imagine the case when a = c = SINT_MIN and b = d = SINT_MAX. We can say that a+b has <nsw>, c+d has <nsw>, and (a+b) + (c+d) also has nsw. But if we say that getAddExpr(getAddExpr(a, b, nsw), getAddExpr(c, d, nsw), nsw) = getAddExpr(a, b, c, d, nsw), it's not true if we compute the latter as a + c + b + d. It will overflow on a + c already. Is my understanding wrong here?

Good point, I was not aware that the flags need to apply for any order of evaluation, but it makes sense! I couldn't find any reference of that, do you think it would be worth to spell that out somewhere?

I think for NUW we should not have the same problem, right? I updated the patch to only consider common NUW flags for now.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

2547

nit: are have, should be only one of them.

2548

I think it would be good to explicitly mention why NSW is not preserved here.

[mkazantsev]

For nuw it should be fine. LGTM!

[mkazantsev]

Good point, I was not aware that the flags need to apply for any order of evaluation

Technically, SCEV's commutative operations don't have order of operand, we only sort them to make simplification easier. So I guess it's a reasonable thing to assume. Expander, for example, may use any order to expand it.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

2547

Thanks, I'll fix that!

2548

Sounds good, I'll add a comment in the committed version.

llvm/lib/Analysis/ScalarEvolution.cpp

#endif
 
   // Skip past any other cast SCEVs.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
     ++Idx;
 
   // If there are add operands they would be next.
   if (Idx < Ops.size()) {
     bool DeletedAdd = false;
+    // If the original flags and all inlined SCEVAddExprs are NUW, use the
+    // common NUW flag for expression after inlining. Other flags cannot be
+    // preserved, because they may depend on the original order of operations.
+    SCEV::NoWrapFlags CommonFlags = maskFlags(OrigFlags, SCEV::FlagNUW);
     while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
       if (Ops.size() > AddOpsInlineThreshold ||
           Add->getNumOperands() > AddOpsInlineThreshold)
         break;
       // If we have an add, expand the add operands onto the end of the operands
       // list.
       Ops.erase(Ops.begin()+Idx);
       Ops.append(Add->op_begin(), Add->op_end());
       DeletedAdd = true;
+      CommonFlags = maskFlags(CommonFlags, Add->getNoWrapFlags());
     }
 
     // If we deleted at least one add, we added operands to the end of the list,
     // and they are not necessarily sorted.  Recurse to resort and resimplify
     // any operands we just acquired.
     if (DeletedAdd)
-      return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
+      return getAddExpr(Ops, CommonFlags, Depth + 1);
   }
 
   // Skip over the add expression until we get to a multiply.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
     ++Idx;
 
   // Check to see if there are any folding opportunities present with
   // operands multiplied by constant values.

llvm/test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll

 ; CHECK-NEXT:    --> (4 + (4 * (%tmp /u 4))<nuw>) U: [0,-3) S: [-2147483648,2147483645)
 ; CHECK-NEXT:    %add4.zext = zext i32 %add4 to i64
 ; CHECK-NEXT:    --> (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64) U: [0,4294967293) S: [0,4294967296)
 ; CHECK-NEXT:    %sunkaddr3 = mul i64 %add4.zext, 4
 ; CHECK-NEXT:    --> (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> U: [0,17179869169) S: [0,17179869181)
 ; CHECK-NEXT:    %sunkaddr4 = getelementptr inbounds i8, i8* bitcast ({ %union, [2000 x i8] }* @tmp_addr to i8*), i64 %sunkaddr3
 ; CHECK-NEXT:    --> ((4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr)<nuw> U: [0,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %sunkaddr5 = getelementptr inbounds i8, i8* %sunkaddr4, i64 4096
-; CHECK-NEXT:    --> (4096 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr) U: [0,-3) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (4096 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr)<nuw> U: [4096,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %addr4.cast = bitcast i8* %sunkaddr5 to i32*
-; CHECK-NEXT:    --> (4096 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr) U: [0,-3) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (4096 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr)<nuw> U: [4096,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %addr4.incr = getelementptr i32, i32* %addr4.cast, i64 1
 ; CHECK-NEXT:    --> (4100 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr) U: [0,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %add5 = add i32 %mul, 5
 ; CHECK-NEXT:    --> (5 + (4 * (%tmp /u 4))<nuw>) U: [5,2) S: [-2147483643,-2147483646)
 ; CHECK-NEXT:    %add5.zext = zext i32 %add5 to i64
 ; CHECK-NEXT:    --> (1 + (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> U: [1,4294967294) S: [1,4294967297)
 ; CHECK-NEXT:    %sunkaddr0 = mul i64 %add5.zext, 4
 ; CHECK-NEXT:    --> (4 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw>)<nuw><nsw> U: [4,17179869173) S: [4,17179869185)
 ; CHECK-NEXT:    %sunkaddr1 = getelementptr inbounds i8, i8* bitcast ({ %union, [2000 x i8] }* @tmp_addr to i8*), i64 %sunkaddr0
-; CHECK-NEXT:    --> (4 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr) U: [0,-3) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (4 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr)<nuw> U: [4,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %sunkaddr2 = getelementptr inbounds i8, i8* %sunkaddr1, i64 4096
-; CHECK-NEXT:    --> (4100 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr) U: [0,-3) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (4100 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr)<nuw> U: [0,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %addr5.cast = bitcast i8* %sunkaddr2 to i32*
-; CHECK-NEXT:    --> (4100 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr) U: [0,-3) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (4100 + (4 * (zext i32 (4 + (4 * (%tmp /u 4))<nuw>) to i64))<nuw><nsw> + @tmp_addr)<nuw> U: [0,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:  Determining loop execution counts for: @f3
 ;
   entry:
   %x = load i8, i8* %x_addr
   %t0 = mul i8 %x, 4
   %t1 = add i8 %t0, 5
   %t1.zext = zext i8 %t1 to i16
 

llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll

 
 define void @pointer_iv_nowrap(i8* %startptr, i8* %endptr) local_unnamed_addr {
 ; CHECK-LABEL: Classifying expressions for: @pointer_iv_nowrap
 ; CHECK-NEXT:  %init = getelementptr inbounds i8, i8* %startptr, i64 2000
 ; CHECK-NEXT:  -->  (2000 + %startptr)<nuw> U: [2000,0) S: [2000,0)
 ; CHECK-NEXT:  %iv = phi i8* [ %init, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:  -->  {(2000 + %startptr)<nuw>,+,1}<nuw><%loop> U: [2000,0) S: [2000,0)
 ; CHECK-NEXT:  %iv.next = getelementptr inbounds i8, i8* %iv, i64 1
-; CHECK-NEXT:  -->  {(2001 + %startptr),+,1}<nuw><%loop> U: full-set S: full-set
+; CHECK-NEXT:  -->  {(2001 + %startptr)<nuw>,+,1}<nuw><%loop> U: [2001,0) S: [2001,0)
 
 ; CHECK-NEXT:Determining loop execution counts for: @pointer_iv_nowrap
-; CHECK-NEXT:Loop %loop: Unpredictable backedge-taken count.
-; CHECK-NEXT:Loop %loop: Unpredictable max backedge-taken count.
-; CHECK-NEXT:Loop %loop: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:Loop %loop: backedge-taken count is (-2000 + (-1 * %startptr) + ((2000 + %startptr)<nuw> umax %endptr))
+; CHECK-NEXT:Loop %loop: max backedge-taken count is -2001
+; CHECK-NEXT:Loop %loop: Predicated backedge-taken count is (-2000 + (-1 * %startptr) + ((2000 + %startptr)<nuw> umax %endptr))
 ;
 entry:
   %init = getelementptr inbounds i8, i8* %startptr, i64 2000
   br label %loop
 
 loop:
   %iv = phi i8* [ %init, %entry ], [ %iv.next, %loop ]
   %iv.next = getelementptr inbounds i8, i8* %iv, i64 1
   %ec = icmp ugt i8* %iv.next, %endptr
   br i1 %ec, label %end, label %loop
 
 end:
   ret void
 }

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, CompareValueComplexity) {
   ScalarEvolution SE = buildSE(*F);
   auto *A = SE.getSCEV(MulA);
   auto *B = SE.getSCEV(MulB);
   EXPECT_NE(A, B);
 }
 
 TEST_F(ScalarEvolutionsTest, SCEVAddExpr) {
   Type *Ty32 = Type::getInt32Ty(Context);
-  Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32};
+  Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32, Ty32, Ty32, Ty32, Ty32};
 
   FunctionType *FTy =
       FunctionType::get(Type::getVoidTy(Context), ArgTys, false);
   Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
 
   Argument *A1 = &*F->arg_begin();
   Argument *A2 = &*(std::next(F->arg_begin()));
   BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
for (int i = 0; i < 10; i++) {
     Mul1 = BinaryOperator::CreateMul(Add2, Add1, "", EntryBB);
     Add1 = Add2;
     Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);
   }
 
   ReturnInst::Create(Context, nullptr, EntryBB);
   ScalarEvolution SE = buildSE(*F);
   EXPECT_NE(nullptr, SE.getSCEV(Mul1));
+
+  Argument *A3 = &*(std::next(F->arg_begin(), 2));
+  Argument *A4 = &*(std::next(F->arg_begin(), 3));
+  Argument *A5 = &*(std::next(F->arg_begin(), 4));
+  Argument *A6 = &*(std::next(F->arg_begin(), 5));
+
+  auto *AddWithNUW = cast<SCEVAddExpr>(SE.getAddExpr(
+      SE.getAddExpr(SE.getSCEV(A2), SE.getSCEV(A3), SCEV::FlagNUW),
+      SE.getConstant(APInt(/*numBits=*/32, 5)), SCEV::FlagNUW));
+  EXPECT_EQ(AddWithNUW->getNumOperands(), 3u);
+  EXPECT_EQ(AddWithNUW->getNoWrapFlags(), SCEV::FlagNUW);
+
+  auto *AddWithAnyWrap =
+      SE.getAddExpr(SE.getSCEV(A3), SE.getSCEV(A4), SCEV::FlagAnyWrap);
+  auto *AddWithAnyWrapNUW = cast<SCEVAddExpr>(
+      SE.getAddExpr(AddWithAnyWrap, SE.getSCEV(A5), SCEV::FlagNUW));
+  EXPECT_EQ(AddWithAnyWrapNUW->getNumOperands(), 3u);
+  EXPECT_EQ(AddWithAnyWrapNUW->getNoWrapFlags(), SCEV::FlagAnyWrap);
+
+  auto *AddWithNSW = SE.getAddExpr(
+      SE.getSCEV(A2), SE.getConstant(APInt(32, 99)), SCEV::FlagNSW);
+  auto *AddWithNSW_NUW = cast<SCEVAddExpr>(
+      SE.getAddExpr(AddWithNSW, SE.getSCEV(A5), SCEV::FlagNUW));
+  EXPECT_EQ(AddWithNSW_NUW->getNumOperands(), 3u);
+  EXPECT_EQ(AddWithNSW_NUW->getNoWrapFlags(), SCEV::FlagAnyWrap);
+
+  auto *AddWithNSWNUW =
+      SE.getAddExpr(SE.getSCEV(A2), SE.getSCEV(A4),
+                    ScalarEvolution::setFlags(SCEV::FlagNUW, SCEV::FlagNSW));
+  auto *AddWithNSWNUW_NUW = cast<SCEVAddExpr>(
+      SE.getAddExpr(AddWithNSWNUW, SE.getSCEV(A5), SCEV::FlagNUW));
+  EXPECT_EQ(AddWithNSWNUW_NUW->getNumOperands(), 3u);
+  EXPECT_EQ(AddWithNSWNUW_NUW->getNoWrapFlags(), SCEV::FlagNUW);
+
+  auto *AddWithNSW_NSWNUW = cast<SCEVAddExpr>(
+      SE.getAddExpr(AddWithNSW, SE.getSCEV(A6),
+                    ScalarEvolution::setFlags(SCEV::FlagNUW, SCEV::FlagNSW)));
+  EXPECT_EQ(AddWithNSW_NSWNUW->getNumOperands(), 3u);
+  EXPECT_EQ(AddWithNSW_NSWNUW->getNoWrapFlags(), SCEV::FlagAnyWrap);
 }
 
 static Instruction &GetInstByName(Function &F, StringRef Name) {
   for (auto &I : instructions(F))
     if (I.getName() == Name)
       return I;
   llvm_unreachable("Could not find instructions!");
 }