shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Transforms/ConstraintElimination/reason-about-add-operands.ll
Florian Hahn fbcf8a8cbb
[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262) 
The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimization in the
unsigned system, due to missing the information that all variables are
unsigned (non-negative).

Variables can be marked as non-negative by adding Var >= 0 for all
variables. This is done for arguments on ConstraintInfo construction and
after adding new variables. This handles cases like the ones outlined in
https://discourse.llvm.org/t/why-does-llvm-not-perform-range-analysis-on-integer-values/74341

The original example shared above is now handled without this change,
but adding another variable means that instcombine won't be able to
simplify examples like https://godbolt.org/z/hTnra7zdY

Adding the extra variables comes with a slight compile-time increase
https://llvm-compile-time-tracker.com/compare.php?from=7568b36a2bc1a1e496ec29246966ffdfc3a8b87f&to=641a47f0acce7755e340447386013a2e086f03d9&stat=instructions:u

stage1-O3    stage1-ReleaseThinLTO    stage1-ReleaseLTO-g  stage1-O0-g
 +0.04%           +0.07%                   +0.05%           +0.02%
stage2-O3    stage2-O0-g    stage2-clang
  +0.05%         +0.05%        +0.05%

https://github.com/llvm/llvm-project/pull/76262
2023-12-23 15:53:48 +01:00

390 lines
14 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3
; RUN: opt -p constraint-elimination -S %s | FileCheck %s
declare void @llvm.assume(i1)
define i1 @addition_with_extra_facts_and_args_ult_i64(i64 noundef %a, i64 noundef %b, i64 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_i64(
; CHECK-SAME: i64 noundef [[A:%.*]], i64 noundef [[B:%.*]], i64 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i64 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i64 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i64 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i64 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 true
;
entry:
%cmp.a = icmp ule i64 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i64 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i64 %b, %a
%cmp.add = icmp ult i64 %add, %c
call void @llvm.assume(i1 %cmp.add)
%t = icmp ult i64 %a, %c
ret i1 %t
}
define i1 @addition_with_extra_facts_and_args_ult_1(i16 noundef %a, i16 noundef %b, i16 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_1(
; CHECK-SAME: i16 noundef [[A:%.*]], i16 noundef [[B:%.*]], i16 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 true
;
entry:
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%t = icmp ult i16 %a, %c
ret i1 %t
}
define i1 @addition_with_extra_facts_and_args_ult_2(i16 noundef %a, i16 noundef %b, i16 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_2(
; CHECK-SAME: i16 noundef [[A:%.*]], i16 noundef [[B:%.*]], i16 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 true
;
entry:
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%t = icmp ult i16 %b, %c
ret i1 %t
}
define i1 @addition_with_extra_facts_and_args_ult_3(i16 noundef %a, i16 noundef %b, i16 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_3(
; CHECK-SAME: i16 noundef [[A:%.*]], i16 noundef [[B:%.*]], i16 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 false
;
entry:
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%f = icmp uge i16 %a, %c
ret i1 %f
}
define i1 @addition_with_extra_facts_and_args_ult_4(i16 noundef %a, i16 noundef %b, i16 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_4(
; CHECK-SAME: i16 noundef [[A:%.*]], i16 noundef [[B:%.*]], i16 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 false
;
entry:
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%f = icmp uge i16 %b, %c
ret i1 %f
}
define i1 @addition_with_extra_facts_and_args_ult_5(i16 noundef %a, i16 noundef %b, i16 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_5(
; CHECK-SAME: i16 noundef [[A:%.*]], i16 noundef [[B:%.*]], i16 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: [[CMP:%.*]] = icmp uge i16 [[A]], 10
; CHECK-NEXT: ret i1 [[CMP]]
;
entry:
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%cmp = icmp uge i16 %a, 10
ret i1 %cmp
}
define i1 @addition_with_extra_facts_and_args_ult_6(i16 noundef %a, i16 noundef %b, i16 noundef %c) {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_args_ult_6(
; CHECK-SAME: i16 noundef [[A:%.*]], i16 noundef [[B:%.*]], i16 noundef [[C:%.*]]) {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[A]], [[B]]
; CHECK-NEXT: ret i1 [[CMP]]
;
entry:
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%cmp = icmp ult i16 %a, %b
ret i1 %cmp
}
declare i16 @get()
define i1 @addition_with_extra_facts_and_return_value_ult_1() {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_return_value_ult_1() {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = call i16 @get()
; CHECK-NEXT: [[B:%.*]] = call i16 @get()
; CHECK-NEXT: [[C:%.*]] = call i16 @get()
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 true
;
entry:
%a = call i16 @get()
%b = call i16 @get()
%c = call i16 @get()
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%t = icmp ult i16 %a, %c
ret i1 %t
}
define i1 @addition_with_extra_facts_and_return_value_ult_2() {
; CHECK-LABEL: define i1 @addition_with_extra_facts_and_return_value_ult_2() {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = call i16 @get()
; CHECK-NEXT: [[B:%.*]] = call i16 @get()
; CHECK-NEXT: [[C:%.*]] = call i16 @get()
; CHECK-NEXT: [[CMP_A:%.*]] = icmp ule i16 [[A]], 2048
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_A]])
; CHECK-NEXT: [[CMP_B:%.*]] = icmp ule i16 [[B]], 1024
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_B]])
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 false
;
entry:
%a = call i16 @get()
%b = call i16 @get()
%c = call i16 @get()
%cmp.a = icmp ule i16 %a, 2048
call void @llvm.assume(i1 %cmp.a)
%cmp.b = icmp ule i16 %b, 1024
call void @llvm.assume(i1 %cmp.b)
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%f = icmp uge i16 %a, %c
ret i1 %f
}
define i1 @addition_no_extra_facts_with_return_value_ult_1() {
; CHECK-LABEL: define i1 @addition_no_extra_facts_with_return_value_ult_1() {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = call i16 @get()
; CHECK-NEXT: [[B:%.*]] = call i16 @get()
; CHECK-NEXT: [[C:%.*]] = call i16 @get()
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 true
;
entry:
%a = call i16 @get()
%b = call i16 @get()
%c = call i16 @get()
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%t = icmp ult i16 %a, %c
ret i1 %t
}
define i1 @addition_no_extra_facts_with_return_value_ult_2() {
; CHECK-LABEL: define i1 @addition_no_extra_facts_with_return_value_ult_2() {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = call i16 @get()
; CHECK-NEXT: [[B:%.*]] = call i16 @get()
; CHECK-NEXT: [[C:%.*]] = call i16 @get()
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: ret i1 false
;
entry:
%a = call i16 @get()
%b = call i16 @get()
%c = call i16 @get()
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%f = icmp uge i16 %a, %c
ret i1 %f
}
define i1 @addition_no_extra_facts_with_return_value_ult_3() {
; CHECK-LABEL: define i1 @addition_no_extra_facts_with_return_value_ult_3() {
; CHECK-NEXT: entry:
; CHECK-NEXT: [[A:%.*]] = call i16 @get()
; CHECK-NEXT: [[B:%.*]] = call i16 @get()
; CHECK-NEXT: [[C:%.*]] = call i16 @get()
; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[B]], [[A]]
; CHECK-NEXT: [[CMP_ADD:%.*]] = icmp ult i16 [[ADD]], [[C]]
; CHECK-NEXT: call void @llvm.assume(i1 [[CMP_ADD]])
; CHECK-NEXT: [[CMP:%.*]] = icmp uge i16 [[A]], 9
; CHECK-NEXT: ret i1 [[CMP]]
;
entry:
%a = call i16 @get()
%b = call i16 @get()
%c = call i16 @get()
%add = add nuw nsw i16 %b, %a
%cmp.add = icmp ult i16 %add, %c
call void @llvm.assume(i1 %cmp.add)
%cmp = icmp uge i16 %a, 9
ret i1 %cmp
}
; Test for https://github.com/llvm/llvm-project/issues/63490.
define i1 @assume_x_ugt_y_plus_y_via_shl_eq(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @assume_x_ugt_y_plus_y_via_shl_eq(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT: [[S:%.*]] = shl nuw i8 [[Y]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X]], [[S]]
; CHECK-NEXT: tail call void @llvm.assume(i1 [[C_1]])
; CHECK-NEXT: ret i1 false
;
%s = shl nuw i8 %y, 1
%c.1 = icmp ugt i8 %x, %s
tail call void @llvm.assume(i1 %c.1)
%c.2 = icmp eq i8 %x, %y
ret i1 %c.2
}
define i1 @assume_x_ugt_y_plus_y_via_shl_eq_no_nuw(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @assume_x_ugt_y_plus_y_via_shl_eq_no_nuw(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT: [[S:%.*]] = shl i8 [[Y]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X]], [[S]]
; CHECK-NEXT: tail call void @llvm.assume(i1 [[C_1]])
; CHECK-NEXT: [[C_2:%.*]] = icmp eq i8 [[X]], [[Y]]
; CHECK-NEXT: ret i1 [[C_2]]
;
%s = shl i8 %y, 1
%c.1 = icmp ugt i8 %x, %s
tail call void @llvm.assume(i1 %c.1)
%c.2 = icmp eq i8 %x, %y
ret i1 %c.2
}
define i1 @assume_x_ugt_y_plus_y_via_add_eq(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @assume_x_ugt_y_plus_y_via_add_eq(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT: [[S:%.*]] = add nuw i8 [[Y]], [[Y]]
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X]], [[S]]
; CHECK-NEXT: tail call void @llvm.assume(i1 [[C_1]])
; CHECK-NEXT: ret i1 false
;
%s = add nuw i8 %y, %y
%c.1 = icmp ugt i8 %x, %s
tail call void @llvm.assume(i1 %c.1)
%c.2 = icmp eq i8 %x, %y
ret i1 %c.2
}
define i1 @assume_x_ugt_y_plus_y_via_add_eq_no_nuw(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @assume_x_ugt_y_plus_y_via_add_eq_no_nuw(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT: [[S:%.*]] = add i8 [[Y]], [[Y]]
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X]], [[S]]
; CHECK-NEXT: tail call void @llvm.assume(i1 [[C_1]])
; CHECK-NEXT: [[C_2:%.*]] = icmp eq i8 [[X]], [[Y]]
; CHECK-NEXT: ret i1 [[C_2]]
;
%s = add i8 %y, %y
%c.1 = icmp ugt i8 %x, %s
tail call void @llvm.assume(i1 %c.1)
%c.2 = icmp eq i8 %x, %y
ret i1 %c.2
}
define i1 @assume_x_ugt_y_plus_y_via_shl_ne(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @assume_x_ugt_y_plus_y_via_shl_ne(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT: [[S:%.*]] = shl nuw i8 [[Y]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X]], [[S]]
; CHECK-NEXT: tail call void @llvm.assume(i1 [[C_1]])
; CHECK-NEXT: ret i1 true
;
%s = shl nuw i8 %y, 1
%c.1 = icmp ugt i8 %x, %s
tail call void @llvm.assume(i1 %c.1)
%c.2 = icmp ne i8 %x, %y
ret i1 %c.2
}
Reference in New Issue View Git Blame Copy Permalink