From 46b055287b80d038e5475e9c4c97603a62c91b80 Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Mon, 15 Mar 2021 11:22:50 +0000
Subject: [PATCH] [ConstraintElimination] Add gep tests without inbounds.

Add a set of interesting test cases for GEPs without inbounds for
upcoming patches.
---
 .../geps-inbounds-precondition.ll                  | 344 +++++++++++++++++++++
 .../geps-precondition-overflow-check.ll            | 333 ++++++++++++++++++++
 2 files changed, 677 insertions(+)
 create mode 100644 llvm/test/Transforms/ConstraintElimination/geps-inbounds-precondition.ll
 create mode 100644 llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll

diff --git a/llvm/test/Transforms/ConstraintElimination/geps-inbounds-precondition.ll b/llvm/test/Transforms/ConstraintElimination/geps-inbounds-precondition.ll
new file mode 100644
index 0000000..63e32d2
--- /dev/null
+++ b/llvm/test/Transforms/ConstraintElimination/geps-inbounds-precondition.ll
@@ -0,0 +1,344 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
+
+; Tests for using inbounds information from GEPs.
+
+declare void @noundef(i32* noundef)
+
+define i1 @inbounds_poison_is_ub1(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @inbounds_poison_is_ub1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 5
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER]])
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i32 [[IDX:%.*]], [[N:%.*]]
+; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[IDX]] to i64
+; CHECK-NEXT:    [[SRC_IDX_4:%.*]] = getelementptr i32, i32* [[SRC]], i64 4
+; CHECK-NEXT:    [[CMP_UPPER_4:%.*]] = icmp ule i32* [[SRC_IDX_4]], [[UPPER]]
+; CHECK-NEXT:    [[SRC_IDX_5:%.*]] = getelementptr i32, i32* [[SRC]], i64 5
+; CHECK-NEXT:    [[CMP_UPPER_5:%.*]] = icmp ule i32* [[SRC_IDX_5]], [[UPPER]]
+; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[CMP_UPPER_4]], [[CMP_UPPER_5]]
+; CHECK-NEXT:    [[SRC_IDX_6:%.*]] = getelementptr i32, i32* [[SRC]], i64 6
+; CHECK-NEXT:    [[CMP_UPPER_6:%.*]] = icmp ule i32* [[SRC_IDX_6]], [[UPPER]]
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[RES_0]], [[CMP_UPPER_6]]
+; CHECK-NEXT:    [[SRC_IDX_NEG_1:%.*]] = getelementptr i32, i32* [[SRC]], i64 -1
+; CHECK-NEXT:    [[CMP_UPPER_NEG_1:%.*]] = icmp ule i32* [[SRC_IDX_NEG_1]], [[UPPER]]
+; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[CMP_UPPER_NEG_1]]
+; CHECK-NEXT:    ret i1 [[RES_2]]
+;
+entry:
+  %upper = getelementptr inbounds i32, i32* %src, i64 5
+  call void @noundef(i32* %upper)
+  %cmp.idx = icmp ult i32 %idx, %n
+  %idx.ext = zext i32 %idx to i64
+  %src.idx.4 = getelementptr i32, i32* %src, i64 4
+  %cmp.upper.4 = icmp ule i32* %src.idx.4, %upper
+  %src.idx.5 = getelementptr i32, i32* %src, i64 5
+  %cmp.upper.5 = icmp ule i32* %src.idx.5, %upper
+  %res.0 = xor i1 %cmp.upper.4, %cmp.upper.5
+
+  %src.idx.6 = getelementptr i32, i32* %src, i64 6
+  %cmp.upper.6 = icmp ule i32* %src.idx.6, %upper
+  %res.1 = xor i1 %res.0, %cmp.upper.6
+
+  %src.idx.neg.1 = getelementptr i32, i32* %src, i64 -1
+  %cmp.upper.neg.1 = icmp ule i32* %src.idx.neg.1, %upper
+  %res.2 = xor i1 %res.1, %cmp.upper.neg.1
+  ret i1 %res.2
+}
+
+; %start + %n.ext is guaranteed to not overflow (due to inbounds).
+; %start + %idx.ext does not overflow if %idx.ext <= %n.ext.
+define i1 @inbounds_poison_is_ub2(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @inbounds_poison_is_ub2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER]])
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i32 [[IDX:%.*]], [[N]]
+; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[IDX]] to i64
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[CMP_UPPER_2:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_2]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  call void @noundef(i32* %upper)
+  %cmp.idx = icmp ult i32 %idx, %n
+  %idx.ext = zext i32 %idx to i64
+  %src.idx = getelementptr i32, i32* %src, i64 %idx.ext
+  br i1 %cmp.idx, label %then, label %else
+
+then:
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper
+  ret i1 %cmp.upper.1
+
+else:
+  %cmp.upper.2 = icmp ule i32* %src.idx, %upper
+  ret i1 %cmp.upper.2
+}
+
+; Same as inbounds_poison_is_ub2, but with individual GEPs in the %then and
+; %else blocks.
+define i1 @inbounds_poison_is_ub3(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @inbounds_poison_is_ub3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i64 [[IDX_EXT]], [[N_EXT]]
+; CHECK-NEXT:    br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[UPPER_1:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_1]])
+; CHECK-NEXT:    [[SRC_IDX_1:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX_1]], [[UPPER_1]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[UPPER_2:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 [[N_EXT]]
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_2]])
+; CHECK-NEXT:    [[SRC_IDX_2:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    [[CMP_UPPER_2:%.*]] = icmp ule i32* [[SRC_IDX_2]], [[UPPER_2]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_2]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %idx.ext = zext i32 %idx to i64
+  %cmp.idx = icmp ult i64 %idx.ext, %n.ext
+  br i1 %cmp.idx, label %then, label %else
+
+then:
+  %upper.1 = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  call void @noundef(i32* %upper.1)
+  %src.idx.1 = getelementptr i32, i32* %src, i64 %idx.ext
+  %cmp.upper.1 = icmp ule i32* %src.idx.1, %upper.1
+  ret i1 %cmp.upper.1
+
+else:
+  %upper.2 = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  call void @noundef(i32* %upper.2)
+  %src.idx.2 = getelementptr i32, i32* %src, i64 %idx.ext
+  %cmp.upper.2 = icmp ule i32* %src.idx.2, %upper.2
+  ret i1 %cmp.upper.2
+}
+
+; The function does not have UB if %upper is poison because of an overflow. Do
+; not simplify anything. In this particular case, the returned result will be
+; poison in this case, so it could be simplified, but currently we cannot
+; distinguish that case.
+define i1 @inbounds_poison_does_not_cause_ub(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @inbounds_poison_does_not_cause_ub(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i64 [[IDX_EXT]], [[N_EXT]]
+; CHECK-NEXT:    br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[CMP_UPPER_2:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_2]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %idx.ext = zext i32 %idx to i64
+  %upper = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  %src.idx = getelementptr i32, i32* %src, i64 %idx.ext
+  %cmp.idx = icmp ult i64 %idx.ext, %n.ext
+  br i1 %cmp.idx, label %then, label %else
+
+then:
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper
+  ret i1 %cmp.upper.1
+
+else:
+  %cmp.upper.2 = icmp ule i32* %src.idx, %upper
+  ret i1 %cmp.upper.2
+}
+
+; Same as @inbounds_poison_does_not_cause_ub, but with separate GEPs in the
+; %then and %else blocks.
+define i1 @inbounds_poison_does_not_cause_ub2(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @inbounds_poison_does_not_cause_ub2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i64 [[IDX_EXT]], [[N_EXT]]
+; CHECK-NEXT:    br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[UPPER_1:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[SRC_IDX_1:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX_1]], [[UPPER_1]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[SRC_IDX_2:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    [[UPPER_2:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[CMP_UPPER_2:%.*]] = icmp ule i32* [[SRC_IDX_2]], [[UPPER_2]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_2]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %idx.ext = zext i32 %idx to i64
+  %cmp.idx = icmp ult i64 %idx.ext, %n.ext
+  br i1 %cmp.idx, label %then, label %else
+
+then:
+  %upper.1 = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  %src.idx.1 = getelementptr i32, i32* %src, i64 %idx.ext
+  %cmp.upper.1 = icmp ule i32* %src.idx.1, %upper.1
+  ret i1 %cmp.upper.1
+
+else:
+  %src.idx.2 = getelementptr i32, i32* %src, i64 %idx.ext
+  %upper.2 = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  %cmp.upper.2 = icmp ule i32* %src.idx.2, %upper.2
+  ret i1 %cmp.upper.2
+}
+
+define i1 @no_zexts_indices_may_be_negative(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @no_zexts_indices_may_be_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i32 [[N:%.*]]
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER]])
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i32 [[IDX:%.*]]
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i32 [[IDX]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[CMP_UPPER_2:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_2]]
+;
+entry:
+  %upper = getelementptr inbounds i32, i32* %src, i32 %n
+  call void @noundef(i32* %upper)
+  %src.idx = getelementptr i32, i32* %src, i32 %idx
+  %cmp.idx = icmp ult i32 %idx, %n
+  br i1 %cmp.idx, label %then, label %else
+
+then:
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper
+  ret i1 %cmp.upper.1
+
+else:
+  %cmp.upper.2 = icmp ule i32* %src.idx, %upper
+  ret i1 %cmp.upper.2
+}
+
+; Tests for multiple inbound GEPs, make sure the largest upper bound is used.
+define i1 @multiple_upper_bounds(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @multiple_upper_bounds(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER_1:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 1
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_1]])
+; CHECK-NEXT:    [[UPPER_2:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 [[N_EXT]]
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_2]])
+; CHECK-NEXT:    [[CMP_IDX:%.*]] = icmp ult i32 [[IDX:%.*]], [[N]]
+; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[IDX]] to i64
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i64 [[IDX_EXT]]
+; CHECK-NEXT:    br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER_2]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[CMP_UPPER_2:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER_2]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_2]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper.1 = getelementptr inbounds i32, i32* %src, i64 1
+  call void @noundef(i32* %upper.1)
+  %upper.2 = getelementptr inbounds i32, i32* %src, i64 %n.ext
+  call void @noundef(i32* %upper.2)
+  %cmp.idx = icmp ult i32 %idx, %n
+  %idx.ext = zext i32 %idx to i64
+  %src.idx = getelementptr i32, i32* %src, i64 %idx.ext
+  br i1 %cmp.idx, label %then, label %else
+
+then:
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper.2
+  ret i1 %cmp.upper.1
+
+else:
+  %cmp.upper.2 = icmp ule i32* %src.idx, %upper.2
+  ret i1 %cmp.upper.2
+}
+
+define i1 @multiple_upper_bounds2(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @multiple_upper_bounds2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER_1:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 1
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_1]])
+; CHECK-NEXT:    [[UPPER_2:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 4
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_2]])
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i64 4
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER_2]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper.1 = getelementptr inbounds i32, i32* %src, i64 1
+  call void @noundef(i32* %upper.1)
+  %upper.2 = getelementptr inbounds i32, i32* %src, i64 4
+  call void @noundef(i32* %upper.2)
+  %src.idx = getelementptr i32, i32* %src, i64 4
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper.2
+  ret i1 %cmp.upper.1
+}
+
+define i1 @multiple_upper_bounds3(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @multiple_upper_bounds3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER_1:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 4
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_1]])
+; CHECK-NEXT:    [[UPPER_2:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 1
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_2]])
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i64 4
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER_1]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper.1 = getelementptr inbounds i32, i32* %src, i64 4
+  call void @noundef(i32* %upper.1)
+  %upper.2 = getelementptr inbounds i32, i32* %src, i64 1
+  call void @noundef(i32* %upper.2)
+  %src.idx = getelementptr i32, i32* %src, i64 4
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper.1
+  ret i1 %cmp.upper.1
+}
+
+; %src.idx + 5 may overflow.
+define i1 @multiple_upper_bounds4(i32* %src, i32 %n, i32 %idx) {
+; CHECK-LABEL: @multiple_upper_bounds4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER_1:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 1
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_1]])
+; CHECK-NEXT:    [[UPPER_2:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 4
+; CHECK-NEXT:    call void @noundef(i32* [[UPPER_2]])
+; CHECK-NEXT:    [[SRC_IDX:%.*]] = getelementptr i32, i32* [[SRC]], i64 5
+; CHECK-NEXT:    [[CMP_UPPER_1:%.*]] = icmp ule i32* [[SRC_IDX]], [[UPPER_2]]
+; CHECK-NEXT:    ret i1 [[CMP_UPPER_1]]
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper.1 = getelementptr inbounds i32, i32* %src, i64 1
+  call void @noundef(i32* %upper.1)
+  %upper.2 = getelementptr inbounds i32, i32* %src, i64 4
+  call void @noundef(i32* %upper.2)
+  %src.idx = getelementptr i32, i32* %src, i64 5
+  %cmp.upper.1 = icmp ule i32* %src.idx, %upper.2
+  ret i1 %cmp.upper.1
+}
diff --git a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
new file mode 100644
index 0000000..9f4e98f
--- /dev/null
+++ b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
@@ -0,0 +1,333 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
+
+; Tests for cases with explicit checks that %ptr + x >= %ptr. The information can
+; be used to determine that certain GEPs do not overflow.
+
+define i1 @overflow_check_1(i32* %dst) {
+; CHECK-LABEL: @overflow_check_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  br i1 %dst.5.uge, label %then, label %else
+
+then:
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
+  ret i1 %true.dst.4.uge
+
+else:
+  ret i1 0
+}
+
+define i1 @overflow_check_2_and(i32* %dst) {
+; CHECK-LABEL: @overflow_check_2_and(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %and = and i1 %dst.5.uge, %dst.5.uge
+  br i1 %and, label %then, label %else
+
+then:
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
+  ret i1 %true.dst.4.uge
+
+else:
+  ret i1 true
+}
+
+define i1 @overflow_check_3_and(i32* %dst) {
+; CHECK-LABEL: @overflow_check_3_and(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    ret i1 [[DST_4_UGE]]
+; CHECK:       else:
+; CHECK-NEXT:    [[ELSE_DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge i32* [[ELSE_DST_4]], [[DST]]
+; CHECK-NEXT:    ret i1 [[ELSE_DST_4_UGE]]
+;
+entry:
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %and = and i1 %dst.5.uge, %dst.5.uge
+  br i1 %and, label %then, label %else
+
+then:
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %dst.4.uge = icmp uge i32* %dst.4, %dst
+  ret i1 %dst.4.uge
+
+else:
+  %else.dst.4 = getelementptr i32, i32* %dst, i64 4
+  %else.dst.4.uge = icmp uge i32* %else.dst.4, %dst
+  ret i1 %else.dst.4.uge
+}
+
+define i1 @overflow_check_4_and(i32* %dst) {
+; CHECK-LABEL: @overflow_check_4_and(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    [[DST_5_2:%.*]] = getelementptr i32, i32* [[DST]], i64 5
+; CHECK-NEXT:    [[TRUE_DST_5_UGE:%.*]] = icmp uge i32* [[DST_5_2]], [[DST]]
+; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[TRUE_DST_4_UGE]], [[TRUE_DST_5_UGE]]
+; CHECK-NEXT:    [[DST_6:%.*]] = getelementptr i32, i32* [[DST]], i64 6
+; CHECK-NEXT:    [[C_DST_6_UGE:%.*]] = icmp uge i32* [[DST_6]], [[DST]]
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[RES_0]], [[C_DST_6_UGE]]
+; CHECK-NEXT:    ret i1 [[RES_1]]
+; CHECK:       else:
+; CHECK-NEXT:    [[ELSE_DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge i32* [[ELSE_DST_4]], [[DST]]
+; CHECK-NEXT:    [[ELSE_DST_6:%.*]] = getelementptr i32, i32* [[DST]], i64 6
+; CHECK-NEXT:    [[ELSE_DST_6_UGE:%.*]] = icmp uge i32* [[ELSE_DST_6]], [[DST]]
+; CHECK-NEXT:    [[ELSE_RES_0:%.*]] = xor i1 [[ELSE_DST_4_UGE]], [[ELSE_DST_6_UGE]]
+; CHECK-NEXT:    ret i1 [[ELSE_RES_0]]
+;
+entry:
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %and = and i1 %dst.5.uge, %dst.5.uge
+  br i1 %and, label %then, label %else
+
+then:
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
+  %dst.5.2 = getelementptr i32, i32* %dst, i64 5
+  %true.dst.5.uge = icmp uge i32* %dst.5.2, %dst
+  %res.0 = xor i1 %true.dst.4.uge, %true.dst.5.uge
+
+  %dst.6 = getelementptr i32, i32* %dst, i64 6
+  %c.dst.6.uge = icmp uge i32* %dst.6, %dst
+  %res.1 = xor i1 %res.0, %c.dst.6.uge
+
+  ret i1 %res.1
+
+else:
+  %else.dst.4 = getelementptr i32, i32* %dst, i64 4
+  %else.dst.4.uge = icmp uge i32* %else.dst.4, %dst
+  %else.dst.6 = getelementptr i32, i32* %dst, i64 6
+  %else.dst.6.uge = icmp uge i32* %else.dst.6, %dst
+  %else.res.0 = xor i1 %else.dst.4.uge, %else.dst.6.uge
+
+  ret i1 %else.res.0
+}
+
+define i1 @overflow_check_3_or(i32* %dst) {
+; CHECK-LABEL: @overflow_check_3_or(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[OR]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %or = or i1 %dst.5.uge, %dst.5.uge
+  br i1 %or, label %then, label %else
+
+then:
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
+  ret i1 %true.dst.4.uge
+
+else:
+  ret i1 0
+}
+
+define i1 @upper_and_lower_checks_1(i32* %dst, i32 %n) {
+; CHECK-LABEL: @upper_and_lower_checks_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST]], i64 5
+; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult i32* [[DST_5]], [[UPPER]]
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[AND_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[TRUE_DST_4_ULT:%.*]] = icmp ult i32* [[DST_4]], [[UPPER]]
+; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[TRUE_DST_4_ULT]], [[TRUE_DST_4_UGE]]
+; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper = getelementptr inbounds i32, i32* %dst, i64 %n.ext
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.ult = icmp ult i32* %dst.5, %upper
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %and.1 = and i1 %dst.5.ult, %dst.5.uge
+  br i1 %and.1, label %then, label %else
+
+then:
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %true.dst.4.ult = icmp ult i32* %dst.4, %upper
+  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
+  %and = and i1 %true.dst.4.ult, %true.dst.4.uge
+  ret i1 %and
+
+else:
+  ret i1 0
+}
+
+define i1 @upper_and_lower_checks_2_dst6(i32* %dst, i32 %n) {
+; CHECK-LABEL: @upper_and_lower_checks_2_dst6(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST]], i64 5
+; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult i32* [[DST_5]], [[UPPER]]
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_6:%.*]] = getelementptr i32, i32* [[DST]], i64 6
+; CHECK-NEXT:    [[C_DST_6_ULT:%.*]] = icmp ult i32* [[DST_6]], [[UPPER]]
+; CHECK-NEXT:    [[TRUE_DST_6_UGE:%.*]] = icmp uge i32* [[DST_6]], [[DST]]
+; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C_DST_6_ULT]], [[TRUE_DST_6_UGE]]
+; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper = getelementptr inbounds i32, i32* %dst, i64 %n.ext
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.ult = icmp ult i32* %dst.5, %upper
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %and = and i1 %dst.5.ult, %dst.5.uge
+  br i1 %and, label %then, label %else
+
+then:
+  %dst.6 = getelementptr i32, i32* %dst, i64 6
+  %c.dst.6.ult = icmp ult i32* %dst.6, %upper
+  %true.dst.6.uge = icmp uge i32* %dst.6, %dst
+  %res = and i1 %c.dst.6.ult, %true.dst.6.uge
+  ret i1 %res
+
+else:
+  ret i1 0
+}
+
+define i1 @upper_and_lower_checks_2_dst7(i32* %dst, i32 %n) {
+; CHECK-LABEL: @upper_and_lower_checks_2_dst7(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST]], i64 5
+; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult i32* [[DST_5]], [[UPPER]]
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_7:%.*]] = getelementptr i32, i32* [[DST]], i64 7
+; CHECK-NEXT:    [[C_DST_7_ULT:%.*]] = icmp ult i32* [[DST_7]], [[UPPER]]
+; CHECK-NEXT:    [[C_DST_7_UGE:%.*]] = icmp uge i32* [[DST_7]], [[DST]]
+; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C_DST_7_ULT]], [[C_DST_7_UGE]]
+; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %upper = getelementptr inbounds i32, i32* %dst, i64 %n.ext
+  %dst.5 = getelementptr i32, i32* %dst, i64 5
+  %dst.5.ult = icmp ult i32* %dst.5, %upper
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %or.cond = and i1 %dst.5.ult, %dst.5.uge
+  br i1 %or.cond, label %then, label %else
+
+then:
+  %dst.7 = getelementptr i32, i32* %dst, i64 7
+  %c.dst.7.ult = icmp ult i32* %dst.7, %upper
+  %c.dst.7.uge = icmp uge i32* %dst.7, %dst
+  %res = and i1 %c.dst.7.ult, %c.dst.7.uge
+  ret i1 %res
+
+else:
+  ret i1 0
+}
+
+define i1 @upper_and_lower_checks_lt(i32* %dst, i32 %n) {
+; CHECK-LABEL: @upper_and_lower_checks_lt(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[N_EXT]]
+; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
+; CHECK-NEXT:    [[N_EXT_UGE:%.*]] = icmp uge i64 [[N_EXT]], 3
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[DST_5_UGE]], [[N_EXT_UGE]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[DST_3:%.*]] = getelementptr i32, i32* [[DST]], i64 3
+; CHECK-NEXT:    [[TRUE_DST_3_UGE:%.*]] = icmp uge i32* [[DST_3]], [[DST]]
+; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
+; CHECK-NEXT:    [[C_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
+; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[TRUE_DST_3_UGE]], [[C_DST_4_UGE]]
+; CHECK-NEXT:    ret i1 [[RES_0]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %n.ext = zext i32 %n to i64
+  %dst.5 = getelementptr i32, i32* %dst, i64 %n.ext
+  %dst.5.uge = icmp uge i32* %dst.5, %dst
+  %n.ext.uge = icmp uge i64 %n.ext, 3
+  %or.cond = and i1 %dst.5.uge, %n.ext.uge
+  br i1 %or.cond, label %then, label %else
+
+then:
+  %dst.3 = getelementptr i32, i32* %dst, i64 3
+  %true.dst.3.uge = icmp uge i32* %dst.3, %dst
+  %dst.4 = getelementptr i32, i32* %dst, i64 4
+  %c.dst.4.uge = icmp uge i32* %dst.4, %dst
+  %res.0 = xor i1 %true.dst.3.uge, %c.dst.4.uge
+  ret i1 %res.0
+
+else:
+  ret i1 0
+}
-- 
2.7.4