[InstCombine] Conditionally emitting nsw/nuw flags when combining two add operations

[MehrHeidar]

Summary

Currently, the InstCombineCompare is combining two add operations into a single add operation which always has a nsw flag, without checking the conditions to see if this flag should be present according to the original two add operations or not. This flag can cause future passes in the pipeline to apply incorrect optimization and generate an incorrect IR.
The following figure shows the IR before, on the right, and after, on the left, this wrong optimization and is the main motivation for this patch:

As we can see non of the add operations have the nsw falg and it was added incorrectly by InstCombine pass. A correct IR for this combined add should be %2 = add i8 %m, 2.

With the wrong IR presented in previous figure, later on the pipeline because of the misleading nsw the conditional branch instruction has changed to an unconditional branch and causing the InstCombine to delete the instructions inside a BasicBlock that contains load and store instructions. This can be seen in the following figure:

This patch will change the InstCombineCompare to emit the nsw or nuw only when these flags are allowed to be generated according to the original add operations and delete the possibility of applying wrong optimization with passes that will perform on the IR later in the pipeline.

To confirm that the current results are buggy and the results after proposed patch are the correct IR the following examples from Alive2 are attached; the same results can be seen in the case of nuw flag and nsw is just used as an example. The following link shows that the generated IR with current LLVM is a buggy IR when non of the original add operations have nsw flag.
https://alive2.llvm.org/ce/z/WGaDrm
The following link proves that the generated IR after the patch in the former case is the correct IR.
https://alive2.llvm.org/ce/z/wQ7G_e

[nikic]

llvm/test/Transforms/InstCombine/icmp-emit-nsw-nuw.ll

1 ↗

(On Diff #336042)

Please use llvm/utils/update_test_checks.py.

[spatel]

These transforms appear to be untested, so I pushed the tests here:
6fccfd7cbdca

So now you can rebase, run llvm/utils/update_test_checks.py on that file, and we'll see the diffs.
It would also be good to use Alive2 to confirm that the current results are buggy and the updated results are as expected. For example:
https://alive2.llvm.org/ce/z/c3BeYv

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3913

I don't think the nuw preservation is correct if the numbers are negative. Consider this case: https://alive2.llvm.org/ce/z/r3s3bw

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3913

I guess that if I change the condition for emitting nuw as follows:

C3.isPositive() && BO1->hasNoUnsignedWrap()

the preservation for nuw will be correct. Will it satisfy all the cases?

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3913

I guess that if I change the condition for emitting nuw as follows:

C3.isNegative() && BO1->hasNoUnsignedWrap()

the preservation for nuw will be correct. Will it satisfy all the cases?

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3913

I guess that if I change the condition for emitting nuw as follows:

!C3.isNegative() && BO1->hasNoUnsignedWrap()

the preservation for nuw will be correct. Will it satisfy all the cases?

[MehrHeidar]

I have updated the condition for preserving the nuw flag.
@nikic Do you think it looks good now?

[nikic]

Yeah, the implementation looks good to me now. Could you please also add a test for this case (that shows nuw is not preserved for negative numbers)?

If you don't have commit access, please also share your Name <and@email> to use when landing this change.

[MehrHeidar]

The test case for negative values with nuw flag is added.

Mehrnoosh Heidarpour
email: [e-mail]

[nikic]

llvm/test/Transforms/InstCombine/icmp-add.ll

747

These should be %t2, %t1 (this causes the build failure).

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (ConstantInt *C1 = dyn_cast<ConstantInt>(B))
       if (ConstantInt *C2 = dyn_cast<ConstantInt>(D)) {
         const APInt &AP1 = C1->getValue();
         const APInt &AP2 = C2->getValue();
         if (AP1.isNegative() == AP2.isNegative()) {
           APInt AP1Abs = C1->getValue().abs();
           APInt AP2Abs = C2->getValue().abs();
           if (AP1Abs.uge(AP2Abs)) {
             ConstantInt *C3 = Builder.getInt(AP1 - AP2);
-            Value *NewAdd = Builder.CreateNSWAdd(A, C3);
+            bool HasNUW = BO0->hasNoUnsignedWrap() && C3->getValue().ule(AP1);
+            bool HasNSW = BO0->hasNoSignedWrap();
+            Value *NewAdd = Builder.CreateAdd(A, C3, "", HasNUW, HasNSW);
             return new ICmpInst(Pred, NewAdd, C);
           } else {
             ConstantInt *C3 = Builder.getInt(AP2 - AP1);
-            Value *NewAdd = Builder.CreateNSWAdd(C, C3);
+            bool HasNUW = BO1->hasNoUnsignedWrap() && C3->getValue().ule(AP2);
+            bool HasNSW = BO1->hasNoSignedWrap();
+            Value *NewAdd = Builder.CreateAdd(C, C3, "", HasNUW, HasNSW);
             return new ICmpInst(Pred, A, NewAdd);
           }
         }
       }
 
   // Analyze the case when either Op0 or Op1 is a sub instruction.
   // Op0 = A - B (or A and B are null); Op1 = C - D (or C and D are null).
   A = nullptr;
   B = nullptr;

llvm/test/Transforms/InstCombine/icmp-add.ll

 ;
   %add = add <2 x i32> %a, <i32 5, i32 5>
   %cmp = icmp eq <2 x i32> %add, <i32 10, i32 11>
   ret <2 x i1> %cmp
 }
 
 define i1 @without_nsw_nuw(i8 %x, i8 %y) {
 ; CHECK-LABEL: @without_nsw_nuw(
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], 2
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
   %t1 = add i8 %x, 37
   %t2 = add i8 %y, 35
   %tobool = icmp eq i8 %t2, %t1
   ret i1 %tobool
 }
 
 define i1 @with_nsw_nuw(i8 %x, i8 %y) {
 ; CHECK-LABEL: @with_nsw_nuw(
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i8 [[X:%.*]], 2
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
   %t1 = add nsw nuw i8 %x, 37
   %t2 = add i8 %y, 35
   %tobool = icmp eq i8 %t2, %t1
   ret i1 %tobool
 }
 
 define i1 @with_nsw_large(i8 %x, i8 %y) {
 ; CHECK-LABEL: @with_nsw_large(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X:%.*]], 2
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
   %t1 = add nsw i8 %x, 37
   %t2 = add i8 %y, 35
   %tobool = icmp eq i8 %t2, %t1
   ret i1 %tobool
 }
 
 define i1 @with_nsw_small(i8 %x, i8 %y) {
 ; CHECK-LABEL: @with_nsw_small(
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[Y:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[Y:%.*]], 2
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
   %t1 = add nsw i8 %x, 35
   %t2 = add i8 %y, 37
   %tobool = icmp eq i8 %t2, %t1
   ret i1 %tobool
 }
 
 define i1 @with_nuw_large(i8 %x, i8 %y) {
 ; CHECK-LABEL: @with_nuw_large(
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i8 [[X:%.*]], 2
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
   %t1 = add nuw i8 %x, 37
   %t2 = add i8 %y, 35
   %tobool = icmp eq i8 %t2, %t1
   ret i1 %tobool
 }
 
 define i1 @with_nuw_small(i8 %x, i8 %y) {
 ; CHECK-LABEL: @with_nuw_small(
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[Y:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[Y:%.*]], 2
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
   %t1 = add nuw i8 %x, 35
   %t2 = add i8 %y, 37
   %tobool = icmp eq i8 %t2, %t1
   ret i1 %tobool
 }