From 62c19284371c3b90fc818b883ab4ef771e6aa362 Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Wed, 14 Sep 2022 09:27:17 +0100
Subject: [PATCH] [ConstraintElimination] Add tests for chained adds.

Add test coverage for reasoning about chains of adds.
---
 .../Transforms/ConstraintElimination/add-nuw.ll    | 203 +++++++++++++++++++++
 .../ConstraintElimination/wrapping-math.ll         |  83 +++++++++
 2 files changed, 286 insertions(+)

diff --git a/llvm/test/Transforms/ConstraintElimination/add-nuw.ll b/llvm/test/Transforms/ConstraintElimination/add-nuw.ll
index bf79a52..c823d09 100644
--- a/llvm/test/Transforms/ConstraintElimination/add-nuw.ll
+++ b/llvm/test/Transforms/ConstraintElimination/add-nuw.ll
@@ -578,3 +578,206 @@ exit.2:
   %res.2 = xor i1 %c.3, %f.1
   ret i1 %res.2
 }
+
+define i1 @test_chained_adds_nuw_1(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_nuw_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], [[B]]
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[ADD_1]], 2
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[ADD_2]], 13
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_2]], 14
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[C_1]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add nuw i8 %a, %b
+  %add.2 = add nuw i8 %add.1, 2
+  %t.1 = icmp uge i8 %add.2, 13
+  %c.1 = icmp uge i8 %add.2, 14
+  %res.1 = xor i1 %t.1, %c.1
+  ret i1 %res.1
+}
+
+define i1 @test_chained_adds_nuw_2(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_nuw_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], [[B]]
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[ADD_1]], 2
+; CHECK-NEXT:    [[ADD_3:%.*]] = add nuw i8 [[ADD_2]], [[A]]
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[ADD_3]], 18
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_3]], 19
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[C_1]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add nuw i8 %a, %b
+  %add.2 = add nuw i8 %add.1, 2
+  %add.3 = add nuw i8 %add.2, %a
+  %t.1 = icmp uge i8 %add.3, 18
+  %c.1 = icmp uge i8 %add.3, 19
+  %res.1 = xor i1 %t.1, %c.1
+  ret i1 %res.1
+}
+
+define i1 @test_chained_adds_nuw_3(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_nuw_3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], 2
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[ADD_1]], [[B]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = add nuw i8 [[ADD_2]], [[A]]
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[ADD_3]], 18
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_3]], 19
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[C_1]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add nuw i8 %a, 2
+  %add.2 = add nuw i8 %add.1, %b
+  %add.3 = add nuw i8 %add.2, %a
+  %t.1 = icmp uge i8 %add.3, 18
+  %c.1 = icmp uge i8 %add.3, 19
+  %res.1 = xor i1 %t.1, %c.1
+  ret i1 %res.1
+}
+
+define i1 @test_chained_adds_nuw_4(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_nuw_4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], 2
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[ADD_1]], [[B]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = add nuw i8 [[ADD_2]], 10
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[ADD_3]], 23
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_3]], 24
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[C_1]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add nuw i8 %a, 2
+  %add.2 = add nuw i8 %add.1, %b
+  %add.3 = add nuw i8 %add.2, 10
+  %t.1 = icmp uge i8 %add.3, 23
+  %c.1 = icmp uge i8 %add.3, 24
+  %res.1 = xor i1 %t.1, %c.1
+  ret i1 %res.1
+}
+
+define i1 @test_chained_adds_missing_nuw_1(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_missing_nuw_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add i8 [[A]], 2
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[ADD_1]], [[B]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = add nuw i8 [[ADD_2]], [[A]]
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_3]], 18
+; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i8 [[ADD_3]], 19
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], [[C_2]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add i8 %a, 2
+  %add.2 = add nuw i8 %add.1, %b
+  %add.3 = add nuw i8 %add.2, %a
+  %c.1 = icmp uge i8 %add.3, 18
+  %c.2 = icmp uge i8 %add.3, 19
+  %res.1 = xor i1 %c.1, %c.2
+  ret i1 %res.1
+}
+
+define i1 @test_chained_adds_missing_nuw_2(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_missing_nuw_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], 2
+; CHECK-NEXT:    [[ADD_2:%.*]] = add i8 [[ADD_1]], [[B]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = add nuw i8 [[ADD_2]], [[A]]
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_3]], 18
+; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i8 [[ADD_3]], 19
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], [[C_2]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add nuw i8 %a, 2
+  %add.2 = add i8 %add.1, %b
+  %add.3 = add nuw i8 %add.2, %a
+  %c.1 = icmp uge i8 %add.3, 18
+  %c.2 = icmp uge i8 %add.3, 19
+  %res.1 = xor i1 %c.1, %c.2
+  ret i1 %res.1
+}
+
+define i1 @test_chained_adds_missing_nuw_3(i8 %a, i8 %b) {
+; CHECK-LABEL: @test_chained_adds_missing_nuw_3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_A:%.*]] = icmp uge i8 [[A:%.*]], 5
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_A]])
+; CHECK-NEXT:    [[C_B:%.*]] = icmp uge i8 [[B:%.*]], 6
+; CHECK-NEXT:    call void @llvm.assume(i1 [[C_B]])
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], 2
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[ADD_1]], [[B]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = add i8 [[ADD_2]], [[A]]
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8 [[ADD_3]], 18
+; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i8 [[ADD_3]], 19
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], [[C_2]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+;
+entry:
+  %c.a = icmp uge i8 %a, 5
+  call void @llvm.assume(i1 %c.a)
+  %c.b = icmp uge i8 %b, 6
+  call void @llvm.assume(i1 %c.b)
+  %add.1 = add nuw i8 %a, 2
+  %add.2 = add nuw i8 %add.1, %b
+  %add.3 = add i8 %add.2, %a
+  %c.1 = icmp uge i8 %add.3, 18
+  %c.2 = icmp uge i8 %add.3, 19
+  %res.1 = xor i1 %c.1, %c.2
+  ret i1 %res.1
+}
+
+declare void @llvm.assume(i1)
diff --git a/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll b/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll
index 9e745a8..91708e1 100644
--- a/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll
+++ b/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll
@@ -271,3 +271,86 @@ exit.1:
   %xor.8 = xor i1 %xor.7, %c.7
   ret i1 %xor.8
 }
+
+define i1 @wrapping_add_known_1_add_nuw(i8 %a) {
+; CHECK-LABEL: @wrapping_add_known_1_add_nuw(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PRE:%.*]] = icmp eq i8 [[A:%.*]], 1
+; CHECK-NEXT:    call void @llvm.assume(i1 [[PRE]])
+; CHECK-NEXT:    [[SUB_1:%.*]] = add i8 [[A]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[ADD]], 10
+; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[ADD]], 10
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[T_2]]
+; CHECK-NEXT:    [[F_1:%.*]] = icmp ult i8 [[ADD]], 10
+; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[F_1]]
+; CHECK-NEXT:    ret i1 [[RES_2]]
+;
+entry:
+  %pre = icmp eq i8 %a, 1
+  call void @llvm.assume(i1 %pre)
+  %sub.1 = add i8 %a, -1
+  %add = add nuw i8 %sub.1, 10
+  %t.1 = icmp uge i8 %add, 10
+  %t.2 = icmp ule i8 %add, 10
+  %res.1 = xor i1 %t.1, %t.2
+  %f.1 = icmp ult i8 %add, 10
+  %res.2 = xor i1 %res.1, %f.1
+  ret i1 %res.2
+}
+
+define i1 @add_nuw_wrapping_add_known_1(i8 %a) {
+; CHECK-LABEL: @add_nuw_wrapping_add_known_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PRE:%.*]] = icmp eq i8 [[A:%.*]], 1
+; CHECK-NEXT:    call void @llvm.assume(i1 [[PRE]])
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[A]], 10
+; CHECK-NEXT:    [[SUB_1:%.*]] = add i8 [[ADD]], -1
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[T_2]]
+; CHECK-NEXT:    [[F_1:%.*]] = icmp ult i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[F_1]]
+; CHECK-NEXT:    ret i1 [[RES_2]]
+;
+entry:
+  %pre = icmp eq i8 %a, 1
+  call void @llvm.assume(i1 %pre)
+  %add = add nuw i8 %a, 10
+  %sub.1 = add i8 %add, -1
+  %t.1 = icmp uge i8 %sub.1, 10
+  %t.2 = icmp ule i8 %sub.1, 10
+  %res.1 = xor i1 %t.1, %t.2
+  %f.1 = icmp ult i8 %sub.1, 10
+  %res.2 = xor i1 %res.1, %f.1
+  ret i1 %res.2
+}
+
+define i1 @add_nuw_wrapping_add_not_known_1(i8 %a) {
+; CHECK-LABEL: @add_nuw_wrapping_add_not_known_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PRE:%.*]] = icmp sge i8 [[A:%.*]], -1
+; CHECK-NEXT:    call void @llvm.assume(i1 [[PRE]])
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[A]], 10
+; CHECK-NEXT:    [[SUB_1:%.*]] = add i8 [[ADD]], -1
+; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[T_2]]
+; CHECK-NEXT:    [[F_1:%.*]] = icmp ult i8 [[SUB_1]], 10
+; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[F_1]]
+; CHECK-NEXT:    ret i1 [[RES_2]]
+;
+entry:
+  %pre = icmp sge i8 %a, -1
+  call void @llvm.assume(i1 %pre)
+  %add = add nuw i8 %a, 10
+  %sub.1 = add i8 %add, -1
+  %t.1 = icmp uge i8 %sub.1, 10
+  %t.2 = icmp ule i8 %sub.1, 10
+  %res.1 = xor i1 %t.1, %t.2
+  %f.1 = icmp ult i8 %sub.1, 10
+  %res.2 = xor i1 %res.1, %f.1
+  ret i1 %res.2
+}
+
+declare void @llvm.assume(i1)
-- 
2.7.4