; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=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(ptr %dst) {
; CHECK-LABEL: @overflow_check_1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
; CHECK-NEXT:    br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
; CHECK:       else:
; CHECK-NEXT:    ret i1 false
;
entry:
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.uge = icmp uge ptr %dst.5, %dst
  br i1 %dst.5.uge, label %then, label %else

then:
  %dst.4 = getelementptr i32, ptr %dst, i64 4
  %true.dst.4.uge = icmp uge ptr %dst.4, %dst
  ret i1 %true.dst.4.uge

else:
  ret i1 0
}

define i1 @overflow_check_2_and(ptr %dst) {
; CHECK-LABEL: @overflow_check_2_and(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 4
; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.uge = icmp uge ptr %dst.5, %dst
  %and = and i1 %dst.5.uge, %dst.5.uge
  br i1 %and, label %then, label %else

then:
  %dst.4 = getelementptr i32, ptr %dst, i64 4
  %true.dst.4.uge = icmp uge ptr %dst.4, %dst
  ret i1 %true.dst.4.uge

else:
  ret i1 true
}

define i1 @overflow_check_3_and(ptr %dst) {
; CHECK-LABEL: @overflow_check_3_and(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 4
; CHECK-NEXT:    [[DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
; CHECK-NEXT:    ret i1 [[DST_4_UGE]]
; CHECK:       else:
; CHECK-NEXT:    [[ELSE_DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge ptr [[ELSE_DST_4]], [[DST]]
; CHECK-NEXT:    ret i1 [[ELSE_DST_4_UGE]]
;
entry:
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.uge = icmp uge ptr %dst.5, %dst
  %and = and i1 %dst.5.uge, %dst.5.uge
  br i1 %and, label %then, label %else

then:
  %dst.4 = getelementptr i32, ptr %dst, i64 4
  %dst.4.uge = icmp uge ptr %dst.4, %dst
  ret i1 %dst.4.uge

else:
  %else.dst.4 = getelementptr i32, ptr %dst, i64 4
  %else.dst.4.uge = icmp uge ptr %else.dst.4, %dst
  ret i1 %else.dst.4.uge
}

define i1 @overflow_check_4_and(ptr %dst) {
; CHECK-LABEL: @overflow_check_4_and(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 4
; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
; CHECK-NEXT:    [[DST_5_2:%.*]] = getelementptr i32, ptr [[DST]], i64 5
; CHECK-NEXT:    [[TRUE_DST_5_UGE:%.*]] = icmp uge ptr [[DST_5_2]], [[DST]]
; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[TRUE_DST_4_UGE]], [[TRUE_DST_5_UGE]]
; CHECK-NEXT:    [[DST_6:%.*]] = getelementptr i32, ptr [[DST]], i64 6
; CHECK-NEXT:    [[C_DST_6_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 4
; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge ptr [[ELSE_DST_4]], [[DST]]
; CHECK-NEXT:    [[ELSE_DST_6:%.*]] = getelementptr i32, ptr [[DST]], i64 6
; CHECK-NEXT:    [[ELSE_DST_6_UGE:%.*]] = icmp uge ptr [[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, ptr %dst, i64 5
  %dst.5.uge = icmp uge ptr %dst.5, %dst
  %and = and i1 %dst.5.uge, %dst.5.uge
  br i1 %and, label %then, label %else

then:
  %dst.4 = getelementptr i32, ptr %dst, i64 4
  %true.dst.4.uge = icmp uge ptr %dst.4, %dst
  %dst.5.2 = getelementptr i32, ptr %dst, i64 5
  %true.dst.5.uge = icmp uge ptr %dst.5.2, %dst
  %res.0 = xor i1 %true.dst.4.uge, %true.dst.5.uge

  %dst.6 = getelementptr i32, ptr %dst, i64 6
  %c.dst.6.uge = icmp uge ptr %dst.6, %dst
  %res.1 = xor i1 %res.0, %c.dst.6.uge

  ret i1 %res.1

else:
  %else.dst.4 = getelementptr i32, ptr %dst, i64 4
  %else.dst.4.uge = icmp uge ptr %else.dst.4, %dst
  %else.dst.6 = getelementptr i32, ptr %dst, i64 6
  %else.dst.6.uge = icmp uge ptr %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(ptr %dst) {
; CHECK-LABEL: @overflow_check_3_or(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 4
; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
; CHECK:       else:
; CHECK-NEXT:    ret i1 false
;
entry:
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.uge = icmp uge ptr %dst.5, %dst
  %or = or i1 %dst.5.uge, %dst.5.uge
  br i1 %or, label %then, label %else

then:
  %dst.4 = getelementptr i32, ptr %dst, i64 4
  %true.dst.4.uge = icmp uge ptr %dst.4, %dst
  ret i1 %true.dst.4.uge

else:
  ret i1 0
}

define i1 @upper_and_lower_checks_1(ptr %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, ptr [[DST:%.*]], i64 [[N_EXT]]
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST]], i64 5
; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult ptr [[DST_5]], [[UPPER]]
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 4
; CHECK-NEXT:    [[TRUE_DST_4_ULT:%.*]] = icmp ult ptr [[DST_4]], [[UPPER]]
; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[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, ptr %dst, i64 %n.ext
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.ult = icmp ult ptr %dst.5, %upper
  %dst.5.uge = icmp uge ptr %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, ptr %dst, i64 4
  %true.dst.4.ult = icmp ult ptr %dst.4, %upper
  %true.dst.4.uge = icmp uge ptr %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(ptr %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, ptr [[DST:%.*]], i64 [[N_EXT]]
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST]], i64 5
; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult ptr [[DST_5]], [[UPPER]]
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 6
; CHECK-NEXT:    [[C_DST_6_ULT:%.*]] = icmp ult ptr [[DST_6]], [[UPPER]]
; CHECK-NEXT:    [[TRUE_DST_6_UGE:%.*]] = icmp uge ptr [[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, ptr %dst, i64 %n.ext
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.ult = icmp ult ptr %dst.5, %upper
  %dst.5.uge = icmp uge ptr %dst.5, %dst
  %and = and i1 %dst.5.ult, %dst.5.uge
  br i1 %and, label %then, label %else

then:
  %dst.6 = getelementptr i32, ptr %dst, i64 6
  %c.dst.6.ult = icmp ult ptr %dst.6, %upper
  %true.dst.6.uge = icmp uge ptr %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(ptr %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, ptr [[DST:%.*]], i64 [[N_EXT]]
; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST]], i64 5
; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult ptr [[DST_5]], [[UPPER]]
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 7
; CHECK-NEXT:    [[C_DST_7_ULT:%.*]] = icmp ult ptr [[DST_7]], [[UPPER]]
; CHECK-NEXT:    [[C_DST_7_UGE:%.*]] = icmp uge ptr [[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, ptr %dst, i64 %n.ext
  %dst.5 = getelementptr i32, ptr %dst, i64 5
  %dst.5.ult = icmp ult ptr %dst.5, %upper
  %dst.5.uge = icmp uge ptr %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, ptr %dst, i64 7
  %c.dst.7.ult = icmp ult ptr %dst.7, %upper
  %c.dst.7.uge = icmp uge ptr %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(ptr %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, ptr [[DST:%.*]], i64 [[N_EXT]]
; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[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, ptr [[DST]], i64 3
; CHECK-NEXT:    [[TRUE_DST_3_UGE:%.*]] = icmp uge ptr [[DST_3]], [[DST]]
; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
; CHECK-NEXT:    [[C_DST_4_UGE:%.*]] = icmp uge ptr [[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, ptr %dst, i64 %n.ext
  %dst.5.uge = icmp uge ptr %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, ptr %dst, i64 3
  %true.dst.3.uge = icmp uge ptr %dst.3, %dst
  %dst.4 = getelementptr i32, ptr %dst, i64 4
  %c.dst.4.uge = icmp uge ptr %dst.4, %dst
  %res.0 = xor i1 %true.dst.3.uge, %c.dst.4.uge
  ret i1 %res.0

else:
  ret i1 0
}