shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Transforms/ConstraintElimination/gep-add-multiple-indices.ll
Florian Hahn d045e23c2d
[ConstraintElim] Refactor GEP offset collection. 
Move GEP offset collection to separate helper function and collect
variable and constant offsets in OffsetResult. For now, this only
supports 1 VariableOffset, but the new code structure can be more easily
extended to handle more offsets in the future.

The refactoring drops the check that the VariableOffset >= -1 * constant
offset. This is not needed to check whether the constraint is
monotonically increasing. The constant factors can be ignored, the
constraint will be monotonically increasing if all variables are
positive.

See https://alive2.llvm.org/ce/z/ah2uSQ,
    https://alive2.llvm.org/ce/z/NCADNZ
2023-11-27 09:05:58 +00:00

325 lines
15 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
define i1 @test_outer_gep_last_index_no_overflow_all_inbounds_1(ptr %dst) {
; CHECK-LABEL: @test_outer_gep_last_index_no_overflow_all_inbounds_1(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds ptr, ptr [[DST:%.*]], i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds ptr, ptr [[DST]], i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST_0]], i64 1, i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds ptr, ptr %dst, i64 0
%upper = getelementptr inbounds ptr, ptr %dst, i64 2
%gep.1 = getelementptr inbounds [2 x i32] , ptr %dst.0, i64 1, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_outer_gep_last_index_no_overflow_all_inbounds_2(ptr %dst) {
; CHECK-LABEL: @test_outer_gep_last_index_no_overflow_all_inbounds_2(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds ptr, ptr [[DST:%.*]], i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds ptr, ptr [[DST]], i64 3
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST_0]], i64 1, i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds ptr, ptr %dst, i64 0
%upper = getelementptr inbounds ptr, ptr %dst, i64 3
%gep.1 = getelementptr inbounds [2 x i32] , ptr %dst.0, i64 1, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_outer_gep_last_index_overflow_all_inbounds(ptr %dst) {
; CHECK-LABEL: @test_outer_gep_last_index_overflow_all_inbounds(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds ptr, ptr [[DST:%.*]], i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds ptr, ptr [[DST]], i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST_0]], i64 1, i64 2
; CHECK-NEXT: ret i1 false
;
%dst.0 = getelementptr inbounds ptr, ptr %dst, i64 0
%upper = getelementptr inbounds ptr, ptr %dst, i64 2
%gep.1 = getelementptr inbounds [2 x i32] , ptr %dst.0, i64 1, i64 2
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_ult_true_all_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_ult_true_all_inbounds(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_uge_true_all_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_uge_true_all_inbounds(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c = icmp uge ptr %gep.1, %dst.0
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_ult_false_all_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_ult_false_all_inbounds(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 2
; CHECK-NEXT: ret i1 false
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 2
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_uge_true_all_inbounds_2(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_uge_true_all_inbounds_2(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 2
; CHECK-NEXT: ret i1 true
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 2
%c = icmp uge ptr %gep.1, %dst.0
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_ult_true_inc_gep_all_inbounds_overflow(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_ult_true_inc_gep_all_inbounds_overflow(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 6
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr i32, ptr [[DST_0]], i64 2
; CHECK-NEXT: [[C:%.*]] = icmp ult ptr [[GEP_1]], [[UPPER]]
; CHECK-NEXT: ret i1 [[C]]
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 6
%gep.1 = getelementptr i32, ptr %dst.0, i64 2
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_ult_true_inc_gep_not_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_ult_true_inc_gep_not_inbounds(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: [[C:%.*]] = icmp ult ptr [[GEP_1]], [[UPPER]]
; CHECK-NEXT: ret i1 [[C]]
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr i32, ptr %dst.0, i64 1
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_uge_true_inc_gep_not_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_uge_true_inc_gep_not_inbounds(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: [[C:%.*]] = icmp ult ptr [[GEP_1]], [[UPPER]]
; CHECK-NEXT: ret i1 [[C]]
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr i32, ptr %dst.0, i64 1
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_ult_false_inc_gep_not_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_ult_false_inc_gep_not_inbounds(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr i32, ptr [[DST_0]], i64 2
; CHECK-NEXT: [[C:%.*]] = icmp ult ptr [[GEP_1]], [[UPPER]]
; CHECK-NEXT: ret i1 [[C]]
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 2
%gep.1 = getelementptr i32, ptr %dst.0, i64 2
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multiple_indices_ult_true_inc_gep_not_inbounds_overflow(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multiple_indices_ult_true_inc_gep_not_inbounds_overflow(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST]], i64 0, i64 5
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr i32, ptr [[DST_0]], i64 2
; CHECK-NEXT: [[C:%.*]] = icmp ult ptr [[GEP_1]], [[UPPER]]
; CHECK-NEXT: ret i1 [[C]]
;
entry:
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 5
%gep.1 = getelementptr i32, ptr %dst.0, i64 2
%c = icmp ult ptr %gep.1, %upper
ret i1 %c
}
define i1 @test_inner_gep_multi_index(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds ptr, ptr [[DST:%.*]], i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds ptr, ptr [[DST]], i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST_0]], i64 1, i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds ptr, ptr %dst, i64 0
%upper = getelementptr inbounds ptr, ptr %dst, i64 2
%gep.1 = getelementptr inbounds [2 x i32] , ptr %dst.0, i64 1, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_outer_gep_last_index_no_overflow_all_inbounds(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_outer_gep_last_index_no_overflow_all_inbounds(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds ptr, ptr [[DST]], i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST_0]], i64 1, i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 0
%upper = getelementptr inbounds ptr, ptr %dst, i64 2
%gep.1 = getelementptr inbounds [2 x i32] , ptr %dst.0, i64 1, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_1(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_1(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 0, i64 1
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 false
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 0, i64 1
%upper = getelementptr inbounds i32, ptr %dst, i64 2
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_2(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_2(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 1, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 2
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 false
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 1, i64 0
%upper = getelementptr inbounds i32, ptr %dst, i64 2
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_3(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_3(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 1, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 3
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 false
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 1, i64 0
%upper = getelementptr inbounds i32, ptr %dst, i64 3
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_4(ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_4(
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 1, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 4
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 true
;
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 1, i64 0
%upper = getelementptr inbounds i32, ptr %dst, i64 4
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_5(i64 %off, ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_5(
; CHECK-NEXT: [[OFF_ULT:%.*]] = icmp ule i64 [[OFF:%.*]], 2
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 2, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 5
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 true
;
%off.ult = icmp ule i64 %off, 2
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 2, i64 0
%upper = getelementptr inbounds i32, ptr %dst, i64 5
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ule ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_6(i64 %off, ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_6(
; CHECK-NEXT: [[OFF_ULT:%.*]] = icmp ule i64 [[OFF:%.*]], 2
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 2, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 5
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: ret i1 false
;
%off.ult = icmp ule i64 %off, 2
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 2, i64 0
%upper = getelementptr inbounds i32, ptr %dst, i64 5
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
define i1 @test_inner_gep_multi_index_no_overflow_all_inbounds_7(i64 %off, ptr %dst) {
; CHECK-LABEL: @test_inner_gep_multi_index_no_overflow_all_inbounds_7(
; CHECK-NEXT: [[OFF_ULT:%.*]] = icmp ule i64 [[OFF:%.*]], 2
; CHECK-NEXT: [[DST_0:%.*]] = getelementptr inbounds [2 x i32], ptr [[DST:%.*]], i64 2, i64 0
; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[OFF]]
; CHECK-NEXT: [[GEP_1:%.*]] = getelementptr inbounds i32, ptr [[DST_0]], i64 1
; CHECK-NEXT: [[C_1:%.*]] = icmp ult ptr [[GEP_1]], [[UPPER]]
; CHECK-NEXT: ret i1 [[C_1]]
;
%off.ult = icmp ule i64 %off, 2
%dst.0 = getelementptr inbounds [2 x i32], ptr %dst, i64 2, i64 0
%upper = getelementptr inbounds i32, ptr %dst, i64 %off
%gep.1 = getelementptr inbounds i32, ptr %dst.0, i64 1
%c.1 = icmp ult ptr %gep.1, %upper
ret i1 %c.1
}
Reference in New Issue View Git Blame Copy Permalink