llvm/test/Transforms/ConstraintElimination/materialize-flags.ll - llvm-project - Git at Google

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
 ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s

 define i64 @sext_to_zext_nneg(i32 %n, i32 %m) {
 ; CHECK-LABEL: define i64 @sext_to_zext_nneg(
 ; CHECK-SAME: i32 [[N:%.*]], i32 [[M:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[N]], [[M]]
 ; CHECK-NEXT:    br i1 [[C]], label %[[EXIT:.*]], label %[[THEN:.*]]
 ; CHECK:       [[THEN]]:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[N]], [[M]]
 ; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[SUB]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret i64 0
 ;
 entry:
   %c = icmp slt i32 %n, %m
   br i1 %c, label %exit, label %then

 then:
   %sub = sub nsw i32 %n, %m
   %ext = sext i32 %sub to i64
   ret i64 %ext

 exit:
   ret i64 0
 }

 define i64 @sext_to_zext_nneg_negated_condition(i32 %n, i32 %m) {
 ; CHECK-LABEL: define i64 @sext_to_zext_nneg_negated_condition(
 ; CHECK-SAME: i32 [[N:%.*]], i32 [[M:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[N]], [[M]]
 ; CHECK-NEXT:    br i1 [[C]], label %[[THEN:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[THEN]]:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[N]], [[M]]
 ; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[SUB]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret i64 0
 ;
 entry:
   %c = icmp slt i32 %n, %m
   br i1 %c, label %then, label %exit

 then:
   %sub = sub nsw i32 %n, %m
   %ext = sext i32 %sub to i64
   ret i64 %ext

 exit:
   ret i64 0
 }

 define i64 @sext_no_conversion_known_via_value_tracking(i32 %n) {
 ; CHECK-LABEL: define i64 @sext_no_conversion_known_via_value_tracking(
 ; CHECK-SAME: i32 [[N:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[N]], 255
 ; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[AND]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT]]
 ;
 entry:
   %and = and i32 %n, 255
   %ext = sext i32 %and to i64
   ret i64 %ext
 }

 define i32 @sub_nuw_relational(i32 %a, i32 %b) {
 ; CHECK-LABEL: define i32 @sub_nuw_relational(
 ; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp uge i32 [[A]], [[B]]
 ; CHECK-NEXT:    br i1 [[C]], label %[[THEN:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[THEN]]:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[A]], [[B]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %c = icmp uge i32 %a, %b
   br i1 %c, label %then, label %exit

 then:
   %sub = sub i32 %a, %b
   ret i32 %sub

 exit:
   ret i32 0
 }

 define i32 @sub_nuw_transitive(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define i32 @sub_nuw_transitive(
 ; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp uge i32 [[A]], [[B]]
 ; CHECK-NEXT:    br i1 [[C_0]], label %[[BB_1:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[BB_1]]:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i32 [[B]], [[C]]
 ; CHECK-NEXT:    br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
 ; CHECK:       [[BB_2]]:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[A]], [[C]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %c.0 = icmp uge i32 %a, %b
   br i1 %c.0, label %bb.1, label %exit

 bb.1:
   %c.1 = icmp uge i32 %b, %c
   br i1 %c.1, label %bb.2, label %exit

 bb.2:
   %sub = sub i32 %a, %c
   ret i32 %sub

 exit:
   ret i32 0
 }

 ; A signed fact does not imply the unsigned no-wrap flag.
 define i32 @sub_no_nuw_signed_fact(i32 %a, i32 %b) {
 ; CHECK-LABEL: define i32 @sub_no_nuw_signed_fact(
 ; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp sge i32 [[A]], [[B]]
 ; CHECK-NEXT:    br i1 [[C]], label %[[THEN:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[THEN]]:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[A]], [[B]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %c = icmp sge i32 %a, %b
   br i1 %c, label %then, label %exit

 then:
   %sub = sub i32 %a, %b
   ret i32 %sub

 exit:
   ret i32 0
 }

 define ptr @gep_nuw_transitive(ptr %p, i64 %i, i64 %j) {
 ; CHECK-LABEL: define ptr @gep_nuw_transitive(
 ; CHECK-SAME: ptr [[P:%.*]], i64 [[I:%.*]], i64 [[J:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
 ; CHECK-NEXT:    br i1 [[C_0]], label %[[BB_1:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[BB_1]]:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i64 [[J]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
 ; CHECK:       [[BB_2]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[I]]
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c.0 = icmp sgt i64 %i, %j
   br i1 %c.0, label %bb.1, label %exit

 bb.1:
   %c.1 = icmp sgt i64 %j, 0
   br i1 %c.1, label %bb.2, label %exit

 bb.2:
   %gep = getelementptr nusw i32, ptr %p, i64 %i
   ret ptr %gep

 exit:
   ret ptr null
 }

 define ptr @gep_no_nuw_unknown_index(ptr %p, i64 %i, i64 %n) {
 ; CHECK-LABEL: define ptr @gep_no_nuw_unknown_index(
 ; CHECK-SAME: ptr [[P:%.*]], i64 [[I:%.*]], i64 [[N:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp sge i64 [[I]], [[N]]
 ; CHECK-NEXT:    br i1 [[C]], label %[[EXIT:.*]], label %[[THEN:.*]]
 ; CHECK:       [[THEN]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[I]]
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c = icmp sge i64 %i, %n
   br i1 %c, label %exit, label %then

 then:
   %gep = getelementptr nusw i32, ptr %p, i64 %i
   ret ptr %gep

 exit:
   ret ptr null
 }

 ; The negative constant index means the GEP wraps in the unsigned sense.
 define ptr @gep_no_nuw_negative_constant_index(ptr %p, i64 %i, i64 %j) {
 ; CHECK-LABEL: define ptr @gep_no_nuw_negative_constant_index(
 ; CHECK-SAME: ptr [[P:%.*]], i64 [[I:%.*]], i64 [[J:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
 ; CHECK-NEXT:    br i1 [[C_0]], label %[[BB_1:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[BB_1]]:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i64 [[J]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
 ; CHECK:       [[BB_2]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[I]]
 ; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr nusw i32, ptr [[GEP]], i64 -1
 ; CHECK-NEXT:    ret ptr [[GEP_2]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c.0 = icmp sgt i64 %i, %j
   br i1 %c.0, label %bb.1, label %exit

 bb.1:
   %c.1 = icmp sgt i64 %j, 0
   br i1 %c.1, label %bb.2, label %exit

 bb.2:
   %gep = getelementptr nusw i32, ptr %p, i64 %i
   %gep.2 = getelementptr nusw i32, ptr %gep, i64 -1
   ret ptr %gep.2

 exit:
   ret ptr null
 }

 ; Without nusw, nuw cannot be implied by non-negative offsets.
 define ptr @gep_no_nusw(ptr %p, i64 %i, i64 %j) {
 ; CHECK-LABEL: define ptr @gep_no_nusw(
 ; CHECK-SAME: ptr [[P:%.*]], i64 [[I:%.*]], i64 [[J:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
 ; CHECK-NEXT:    br i1 [[C_0]], label %[[BB_1:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[BB_1]]:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i64 [[J]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
 ; CHECK:       [[BB_2]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr [[P]], i64 [[I]]
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c.0 = icmp sgt i64 %i, %j
   br i1 %c.0, label %bb.1, label %exit

 bb.1:
   %c.1 = icmp sgt i64 %j, 0
   br i1 %c.1, label %bb.2, label %exit

 bb.2:
   %gep = getelementptr i32, ptr %p, i64 %i
   ret ptr %gep

 exit:
   ret ptr null
 }

 define ptr @gep_no_nuw_constant_index(ptr %p) {
 ; CHECK-LABEL: define ptr @gep_no_nuw_constant_index(
 ; CHECK-SAME: ptr [[P:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp ne ptr [[P]], null
 ; CHECK-NEXT:    br i1 [[C]], label %[[THEN:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[THEN]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 3
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c = icmp ne ptr %p, null
   br i1 %c, label %then, label %exit

 then:
   %gep = getelementptr nusw i32, ptr %p, i64 3
   ret ptr %gep

 exit:
   ret ptr null
 }

 define i64 @no_facts(i32 %n, i32 %m, ptr %p) {
 ; CHECK-LABEL: define i64 @no_facts(
 ; CHECK-SAME: i32 [[N:%.*]], i32 [[M:%.*]], ptr [[P:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[N]], [[M]]
 ; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[SUB]] to i64
 ; CHECK-NEXT:    [[SUB_2:%.*]] = sub i32 [[N]], [[M]]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i32 [[SUB_2]]
 ; CHECK-NEXT:    store i32 0, ptr [[GEP]], align 4
 ; CHECK-NEXT:    ret i64 [[EXT]]
 ;
 entry:
   %sub = sub nsw i32 %n, %m
   %ext = sext i32 %sub to i64
   %sub.2 = sub i32 %n, %m
   %gep = getelementptr nusw i32, ptr %p, i32 %sub.2
   store i32 0, ptr %gep, align 4
   ret i64 %ext
 }

 define void @induction_start_bound(ptr %p, i32 %start, i32 %n) {
 ; CHECK-LABEL: define void @induction_start_bound(
 ; CHECK-SAME: ptr [[P:%.*]], i32 [[START:%.*]], i32 [[N:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*]]:
 ; CHECK-NEXT:    br label %[[LOOP:.*]]
 ; CHECK:       [[LOOP]]:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LOOP]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[IV]], [[START]]
 ; CHECK-NEXT:    [[IDX:%.*]] = sext i32 [[SUB]] to i64
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[IDX]]
 ; CHECK-NEXT:    store i32 0, ptr [[GEP]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp slt i32 [[IV_NEXT]], [[N]]
 ; CHECK-NEXT:    br i1 [[EC]], label %[[LOOP]], label %[[EXIT:.*]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop

 loop:
   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
   %sub = sub nsw i32 %iv, %start
   %idx = sext i32 %sub to i64
   %gep = getelementptr nusw i32, ptr %p, i64 %idx
   store i32 0, ptr %gep, align 4
   %iv.next = add nsw i32 %iv, 1
   %ec = icmp slt i32 %iv.next, %n
   br i1 %ec, label %loop, label %exit

 exit:
   ret void
 }

 define void @induction_start_bound_ne_latch(ptr %p, i32 %start, i32 %n) {
 ; CHECK-LABEL: define void @induction_start_bound_ne_latch(
 ; CHECK-SAME: ptr [[P:%.*]], i32 [[START:%.*]], i32 [[N:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*]]:
 ; CHECK-NEXT:    br label %[[LOOP_HEADER:.*]]
 ; CHECK:       [[LOOP_HEADER]]:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LOOP_LATCH:.*]] ]
 ; CHECK-NEXT:    [[EC:%.*]] = icmp ne i32 [[IV]], [[N]]
 ; CHECK-NEXT:    br i1 [[EC]], label %[[LOOP_BODY:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[LOOP_BODY]]:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[IV]], [[START]]
 ; CHECK-NEXT:    [[IDX:%.*]] = sext i32 [[SUB]] to i64
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[IDX]]
 ; CHECK-NEXT:    store i32 0, ptr [[GEP]], align 4
 ; CHECK-NEXT:    br label %[[LOOP_LATCH]]
 ; CHECK:       [[LOOP_LATCH]]:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br label %[[LOOP_HEADER]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop.header

 loop.header:
   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop.latch ]
   %ec = icmp ne i32 %iv, %n
   br i1 %ec, label %loop.body, label %exit

 loop.body:
   %sub = sub nsw i32 %iv, %start
   %idx = sext i32 %sub to i64
   %gep = getelementptr nusw i32, ptr %p, i64 %idx
   store i32 0, ptr %gep, align 4
   br label %loop.latch

 loop.latch:
   %iv.next = add nsw i32 %iv, 1
   br label %loop.header

 exit:
   ret void
 }

 ; The stride 2^63 is negative when interpreted in the pointer index type, so a
 ; non-negative index does not imply a non-negative offset and nuw must not be
 ; added.
 define ptr @gep_no_nuw_stride_negative_in_index_type(ptr %p, i64 %i, i64 %j) {
 ; CHECK-LABEL: define ptr @gep_no_nuw_stride_negative_in_index_type(
 ; CHECK-SAME: ptr [[P:%.*]], i64 [[I:%.*]], i64 [[J:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
 ; CHECK-NEXT:    br i1 [[C_0]], label %[[BB_1:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[BB_1]]:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i64 [[J]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
 ; CHECK:       [[BB_2]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw [9223372036854775808 x i8], ptr [[P]], i64 [[I]]
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c.0 = icmp sgt i64 %i, %j
   br i1 %c.0, label %bb.1, label %exit

 bb.1:
   %c.1 = icmp sgt i64 %j, 0
   br i1 %c.1, label %bb.2, label %exit

 bb.2:
   %gep = getelementptr nusw [9223372036854775808 x i8], ptr %p, i64 %i
   ret ptr %gep

 exit:
   ret ptr null
 }

 ; The sign of a scalable stride in the pointer index type is not known.
 define ptr @gep_no_nuw_scalable_stride(ptr %p, i64 %i, i64 %j) {
 ; CHECK-LABEL: define ptr @gep_no_nuw_scalable_stride(
 ; CHECK-SAME: ptr [[P:%.*]], i64 [[I:%.*]], i64 [[J:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
 ; CHECK-NEXT:    br i1 [[C_0]], label %[[BB_1:.*]], label %[[EXIT:.*]]
 ; CHECK:       [[BB_1]]:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i64 [[J]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
 ; CHECK:       [[BB_2]]:
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr nusw <vscale x 2 x i8>, ptr [[P]], i64 [[I]]
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ; CHECK:       [[EXIT]]:
 ; CHECK-NEXT:    ret ptr null
 ;
 entry:
   %c.0 = icmp sgt i64 %i, %j
   br i1 %c.0, label %bb.1, label %exit

 bb.1:
   %c.1 = icmp sgt i64 %j, 0
   br i1 %c.1, label %bb.2, label %exit

 bb.2:
   %gep = getelementptr nusw <vscale x 2 x i8>, ptr %p, i64 %i
   ret ptr %gep

 exit:
   ret ptr null
 }

 ; %x <u %n <u 1024, hence %x * 3 fits an i64 unsigned and signed.
 define i64 @mul_from_transitive_unsigned_bound(i64 %x, i64 %n) {
 ; CHECK-LABEL: define i64 @mul_from_transitive_unsigned_bound(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[N:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp ult i64 [[N]], 1024
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i64 [[X]], [[N]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i64 [[X]], 3
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
 entry:
   %c.0 = icmp ult i64 %n, 1024
   call void @llvm.assume(i1 %c.0)
   %c.1 = icmp ult i64 %x, %n
   call void @llvm.assume(i1 %c.1)
   %mul = mul i64 %x, 3
   ret i64 %mul
 }

 ; Same as above, but there is no upper bound for %n.
 define i64 @mul_no_flags_unbounded_transitive_operand(i64 %x, i64 %n) {
 ; CHECK-LABEL: define i64 @mul_no_flags_unbounded_transitive_operand(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[N:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i64 [[X]], [[N]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[X]], 3
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
 entry:
   %c.1 = icmp ult i64 %x, %n
   call void @llvm.assume(i1 %c.1)
   %mul = mul i64 %x, 3
   ret i64 %mul
 }

 ; %x <=u %x + %y <u 1024 due to the nuw add, hence %x << 3 fits an i64 unsigned.
 define i64 @shl_nuw_from_sum_bound(i64 %x, i64 %y) {
 ; CHECK-LABEL: define i64 @shl_nuw_from_sum_bound(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[S:%.*]] = add nuw i64 [[X]], [[Y]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp ult i64 [[S]], 1024
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i64 [[X]], 3
 ; CHECK-NEXT:    ret i64 [[SHL]]
 ;
 entry:
   %s = add nuw i64 %x, %y
   %c.0 = icmp ult i64 %s, 1024
   call void @llvm.assume(i1 %c.0)
   %shl = shl i64 %x, 3
   ret i64 %shl
 }

 ; The bound on %x is one too weak for %x << 3 to fit an i64 unsigned.
 define i64 @shl_no_nuw_bound_too_weak(i64 %x) {
 ; CHECK-LABEL: define i64 @shl_no_nuw_bound_too_weak(
 ; CHECK-SAME: i64 [[X:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp ult i64 [[X]], 2305843009213693953
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[X]], 3
 ; CHECK-NEXT:    ret i64 [[SHL]]
 ;
 entry:
   %c.0 = icmp ult i64 %x, 2305843009213693953
   call void @llvm.assume(i1 %c.0)
   %shl = shl i64 %x, 3
   ret i64 %shl
 }

 ; %x >=s %z >=s 0 and %y >=s 0, hence the nsw product also fits unsigned.
 define i64 @mul_nuw_from_nsw_and_non_negative(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: define i64 @mul_nuw_from_nsw_and_non_negative(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], i64 [[Z:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i64 [[Z]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i64 [[Y]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_2]])
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
 entry:
   %c.0 = icmp sge i64 %x, %z
   call void @llvm.assume(i1 %c.0)
   %c.1 = icmp sge i64 %z, 0
   call void @llvm.assume(i1 %c.1)
   %c.2 = icmp sge i64 %y, 0
   call void @llvm.assume(i1 %c.2)
   %mul = mul nsw i64 %x, %y
   ret i64 %mul
 }

 ; Same as above, but %y may be negative.
 define i64 @mul_no_nuw_from_nsw_second_operand_may_be_negative(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: define i64 @mul_no_nuw_from_nsw_second_operand_may_be_negative(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], i64 [[Z:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i64 [[Z]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
 entry:
   %c.0 = icmp sge i64 %x, %z
   call void @llvm.assume(i1 %c.0)
   %c.1 = icmp sge i64 %z, 0
   call void @llvm.assume(i1 %c.1)
   %mul = mul nsw i64 %x, %y
   ret i64 %mul
 }

 ; %x >=s %z >=s 0, hence the nsw shift also fits unsigned, for any shift amount.
 define i64 @shl_nuw_from_nsw_and_non_negative(i64 %x, i64 %s, i64 %z) {
 ; CHECK-LABEL: define i64 @shl_nuw_from_nsw_and_non_negative(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[S:%.*]], i64 [[Z:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i64 [[Z]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[SHL:%.*]] = shl nsw i64 [[X]], [[S]]
 ; CHECK-NEXT:    ret i64 [[SHL]]
 ;
 entry:
   %c.0 = icmp sge i64 %x, %z
   call void @llvm.assume(i1 %c.0)
   %c.1 = icmp sge i64 %z, 0
   call void @llvm.assume(i1 %c.1)
   %shl = shl nsw i64 %x, %s
   ret i64 %shl
 }

 ; Same as above, but the shift does not have nsw.
 define i64 @shl_no_nuw_non_negative_without_nsw(i64 %x, i64 %s, i64 %z) {
 ; CHECK-LABEL: define i64 @shl_no_nuw_non_negative_without_nsw(
 ; CHECK-SAME: i64 [[X:%.*]], i64 [[S:%.*]], i64 [[Z:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i64 [[Z]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[X]], [[S]]
 ; CHECK-NEXT:    ret i64 [[SHL]]
 ;
 entry:
   %c.0 = icmp sge i64 %x, %z
   call void @llvm.assume(i1 %c.0)
   %c.1 = icmp sge i64 %z, 0
   call void @llvm.assume(i1 %c.1)
   %shl = shl i64 %x, %s
   ret i64 %shl
 }

 ; -8 <=s %x <=s 7 implies %x * 16 does not wrap signed, but it may wrap
 ; unsigned.
 define i8 @mul_nsw_only_from_signed_bounds(i8 %x) {
 ; CHECK-LABEL: define i8 @mul_nsw_only_from_signed_bounds(
 ; CHECK-SAME: i8 [[X:%.*]]) {
 ; CHECK-NEXT:  [[ENTRY:.*:]]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sle i8 [[X]], 7
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_0]])
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i8 [[X]], -8
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C_1]])
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i8 [[X]], 16
 ; CHECK-NEXT:    ret i8 [[MUL]]
 ;
 entry:
   %c.0 = icmp sle i8 %x, 7
   call void @llvm.assume(i1 %c.0)
   %c.1 = icmp sge i8 %x, -8
   call void @llvm.assume(i1 %c.1)
   %mul = mul i8 %x, 16
   ret i8 %mul
 }
	; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
	; RUN: opt -passes=constraint-elimination -S %s \| FileCheck %s

	define i64 @sext_to_zext_nneg(i32 %n, i32 %m) {
	; CHECK-LABEL: define i64 @sext_to_zext_nneg(
	; CHECK-SAME: i32 [[N:%.]], i32 [[M:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C:%.*]] = icmp slt i32 [[N]], [[M]]
	; CHECK-NEXT: br i1 [[C]], label %[[EXIT:.]], label %[[THEN:.]]
	; CHECK: [[THEN]]:
	; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[N]], [[M]]
	; CHECK-NEXT: [[EXT:%.*]] = sext i32 [[SUB]] to i64
	; CHECK-NEXT: ret i64 [[EXT]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret i64 0
	;
	entry:
	%c = icmp slt i32 %n, %m
	br i1 %c, label %exit, label %then

	then:
	%sub = sub nsw i32 %n, %m
	%ext = sext i32 %sub to i64
	ret i64 %ext

	exit:
	ret i64 0
	}

	define i64 @sext_to_zext_nneg_negated_condition(i32 %n, i32 %m) {
	; CHECK-LABEL: define i64 @sext_to_zext_nneg_negated_condition(
	; CHECK-SAME: i32 [[N:%.]], i32 [[M:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C:%.*]] = icmp slt i32 [[N]], [[M]]
	; CHECK-NEXT: br i1 [[C]], label %[[THEN:.]], label %[[EXIT:.]]
	; CHECK: [[THEN]]:
	; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[N]], [[M]]
	; CHECK-NEXT: [[EXT:%.*]] = sext i32 [[SUB]] to i64
	; CHECK-NEXT: ret i64 [[EXT]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret i64 0
	;
	entry:
	%c = icmp slt i32 %n, %m
	br i1 %c, label %then, label %exit

	then:
	%sub = sub nsw i32 %n, %m
	%ext = sext i32 %sub to i64
	ret i64 %ext

	exit:
	ret i64 0
	}

	define i64 @sext_no_conversion_known_via_value_tracking(i32 %n) {
	; CHECK-LABEL: define i64 @sext_no_conversion_known_via_value_tracking(
	; CHECK-SAME: i32 [[N:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[AND:%.*]] = and i32 [[N]], 255
	; CHECK-NEXT: [[EXT:%.*]] = sext i32 [[AND]] to i64
	; CHECK-NEXT: ret i64 [[EXT]]
	;
	entry:
	%and = and i32 %n, 255
	%ext = sext i32 %and to i64
	ret i64 %ext
	}

	define i32 @sub_nuw_relational(i32 %a, i32 %b) {
	; CHECK-LABEL: define i32 @sub_nuw_relational(
	; CHECK-SAME: i32 [[A:%.]], i32 [[B:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C:%.*]] = icmp uge i32 [[A]], [[B]]
	; CHECK-NEXT: br i1 [[C]], label %[[THEN:.]], label %[[EXIT:.]]
	; CHECK: [[THEN]]:
	; CHECK-NEXT: [[SUB:%.*]] = sub nuw i32 [[A]], [[B]]
	; CHECK-NEXT: ret i32 [[SUB]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret i32 0
	;
	entry:
	%c = icmp uge i32 %a, %b
	br i1 %c, label %then, label %exit

	then:
	%sub = sub i32 %a, %b
	ret i32 %sub

	exit:
	ret i32 0
	}

	define i32 @sub_nuw_transitive(i32 %a, i32 %b, i32 %c) {
	; CHECK-LABEL: define i32 @sub_nuw_transitive(
	; CHECK-SAME: i32 [[A:%.]], i32 [[B:%.]], i32 [[C:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp uge i32 [[A]], [[B]]
	; CHECK-NEXT: br i1 [[C_0]], label %[[BB_1:.]], label %[[EXIT:.]]
	; CHECK: [[BB_1]]:
	; CHECK-NEXT: [[C_1:%.*]] = icmp uge i32 [[B]], [[C]]
	; CHECK-NEXT: br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
	; CHECK: [[BB_2]]:
	; CHECK-NEXT: [[SUB:%.*]] = sub nuw i32 [[A]], [[C]]
	; CHECK-NEXT: ret i32 [[SUB]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret i32 0
	;
	entry:
	%c.0 = icmp uge i32 %a, %b
	br i1 %c.0, label %bb.1, label %exit

	bb.1:
	%c.1 = icmp uge i32 %b, %c
	br i1 %c.1, label %bb.2, label %exit

	bb.2:
	%sub = sub i32 %a, %c
	ret i32 %sub

	exit:
	ret i32 0
	}

	; A signed fact does not imply the unsigned no-wrap flag.
	define i32 @sub_no_nuw_signed_fact(i32 %a, i32 %b) {
	; CHECK-LABEL: define i32 @sub_no_nuw_signed_fact(
	; CHECK-SAME: i32 [[A:%.]], i32 [[B:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C:%.*]] = icmp sge i32 [[A]], [[B]]
	; CHECK-NEXT: br i1 [[C]], label %[[THEN:.]], label %[[EXIT:.]]
	; CHECK: [[THEN]]:
	; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[A]], [[B]]
	; CHECK-NEXT: ret i32 [[SUB]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret i32 0
	;
	entry:
	%c = icmp sge i32 %a, %b
	br i1 %c, label %then, label %exit

	then:
	%sub = sub i32 %a, %b
	ret i32 %sub

	exit:
	ret i32 0
	}

	define ptr @gep_nuw_transitive(ptr %p, i64 %i, i64 %j) {
	; CHECK-LABEL: define ptr @gep_nuw_transitive(
	; CHECK-SAME: ptr [[P:%.]], i64 [[I:%.]], i64 [[J:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
	; CHECK-NEXT: br i1 [[C_0]], label %[[BB_1:.]], label %[[EXIT:.]]
	; CHECK: [[BB_1]]:
	; CHECK-NEXT: [[C_1:%.*]] = icmp sgt i64 [[J]], 0
	; CHECK-NEXT: br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
	; CHECK: [[BB_2]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[I]]
	; CHECK-NEXT: ret ptr [[GEP]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c.0 = icmp sgt i64 %i, %j
	br i1 %c.0, label %bb.1, label %exit

	bb.1:
	%c.1 = icmp sgt i64 %j, 0
	br i1 %c.1, label %bb.2, label %exit

	bb.2:
	%gep = getelementptr nusw i32, ptr %p, i64 %i
	ret ptr %gep

	exit:
	ret ptr null
	}

	define ptr @gep_no_nuw_unknown_index(ptr %p, i64 %i, i64 %n) {
	; CHECK-LABEL: define ptr @gep_no_nuw_unknown_index(
	; CHECK-SAME: ptr [[P:%.]], i64 [[I:%.]], i64 [[N:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C:%.*]] = icmp sge i64 [[I]], [[N]]
	; CHECK-NEXT: br i1 [[C]], label %[[EXIT:.]], label %[[THEN:.]]
	; CHECK: [[THEN]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[I]]
	; CHECK-NEXT: ret ptr [[GEP]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c = icmp sge i64 %i, %n
	br i1 %c, label %exit, label %then

	then:
	%gep = getelementptr nusw i32, ptr %p, i64 %i
	ret ptr %gep

	exit:
	ret ptr null
	}

	; The negative constant index means the GEP wraps in the unsigned sense.
	define ptr @gep_no_nuw_negative_constant_index(ptr %p, i64 %i, i64 %j) {
	; CHECK-LABEL: define ptr @gep_no_nuw_negative_constant_index(
	; CHECK-SAME: ptr [[P:%.]], i64 [[I:%.]], i64 [[J:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
	; CHECK-NEXT: br i1 [[C_0]], label %[[BB_1:.]], label %[[EXIT:.]]
	; CHECK: [[BB_1]]:
	; CHECK-NEXT: [[C_1:%.*]] = icmp sgt i64 [[J]], 0
	; CHECK-NEXT: br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
	; CHECK: [[BB_2]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[I]]
	; CHECK-NEXT: [[GEP_2:%.*]] = getelementptr nusw i32, ptr [[GEP]], i64 -1
	; CHECK-NEXT: ret ptr [[GEP_2]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c.0 = icmp sgt i64 %i, %j
	br i1 %c.0, label %bb.1, label %exit

	bb.1:
	%c.1 = icmp sgt i64 %j, 0
	br i1 %c.1, label %bb.2, label %exit

	bb.2:
	%gep = getelementptr nusw i32, ptr %p, i64 %i
	%gep.2 = getelementptr nusw i32, ptr %gep, i64 -1
	ret ptr %gep.2

	exit:
	ret ptr null
	}

	; Without nusw, nuw cannot be implied by non-negative offsets.
	define ptr @gep_no_nusw(ptr %p, i64 %i, i64 %j) {
	; CHECK-LABEL: define ptr @gep_no_nusw(
	; CHECK-SAME: ptr [[P:%.]], i64 [[I:%.]], i64 [[J:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
	; CHECK-NEXT: br i1 [[C_0]], label %[[BB_1:.]], label %[[EXIT:.]]
	; CHECK: [[BB_1]]:
	; CHECK-NEXT: [[C_1:%.*]] = icmp sgt i64 [[J]], 0
	; CHECK-NEXT: br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
	; CHECK: [[BB_2]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr i32, ptr [[P]], i64 [[I]]
	; CHECK-NEXT: ret ptr [[GEP]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c.0 = icmp sgt i64 %i, %j
	br i1 %c.0, label %bb.1, label %exit

	bb.1:
	%c.1 = icmp sgt i64 %j, 0
	br i1 %c.1, label %bb.2, label %exit

	bb.2:
	%gep = getelementptr i32, ptr %p, i64 %i
	ret ptr %gep

	exit:
	ret ptr null
	}

	define ptr @gep_no_nuw_constant_index(ptr %p) {
	; CHECK-LABEL: define ptr @gep_no_nuw_constant_index(
	; CHECK-SAME: ptr [[P:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C:%.*]] = icmp ne ptr [[P]], null
	; CHECK-NEXT: br i1 [[C]], label %[[THEN:.]], label %[[EXIT:.]]
	; CHECK: [[THEN]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 3
	; CHECK-NEXT: ret ptr [[GEP]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c = icmp ne ptr %p, null
	br i1 %c, label %then, label %exit

	then:
	%gep = getelementptr nusw i32, ptr %p, i64 3
	ret ptr %gep

	exit:
	ret ptr null
	}

	define i64 @no_facts(i32 %n, i32 %m, ptr %p) {
	; CHECK-LABEL: define i64 @no_facts(
	; CHECK-SAME: i32 [[N:%.]], i32 [[M:%.]], ptr [[P:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[N]], [[M]]
	; CHECK-NEXT: [[EXT:%.*]] = sext i32 [[SUB]] to i64
	; CHECK-NEXT: [[SUB_2:%.*]] = sub i32 [[N]], [[M]]
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i32 [[SUB_2]]
	; CHECK-NEXT: store i32 0, ptr [[GEP]], align 4
	; CHECK-NEXT: ret i64 [[EXT]]
	;
	entry:
	%sub = sub nsw i32 %n, %m
	%ext = sext i32 %sub to i64
	%sub.2 = sub i32 %n, %m
	%gep = getelementptr nusw i32, ptr %p, i32 %sub.2
	store i32 0, ptr %gep, align 4
	ret i64 %ext
	}

	define void @induction_start_bound(ptr %p, i32 %start, i32 %n) {
	; CHECK-LABEL: define void @induction_start_bound(
	; CHECK-SAME: ptr [[P:%.]], i32 [[START:%.]], i32 [[N:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*]]:
	; CHECK-NEXT: br label %[[LOOP:.*]]
	; CHECK: [[LOOP]]:
	; CHECK-NEXT: [[IV:%.]] = phi i32 [ [[START]], %[[ENTRY]] ], [ [[IV_NEXT:%.]], %[[LOOP]] ]
	; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[IV]], [[START]]
	; CHECK-NEXT: [[IDX:%.*]] = sext i32 [[SUB]] to i64
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[IDX]]
	; CHECK-NEXT: store i32 0, ptr [[GEP]], align 4
	; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1
	; CHECK-NEXT: [[EC:%.*]] = icmp slt i32 [[IV_NEXT]], [[N]]
	; CHECK-NEXT: br i1 [[EC]], label %[[LOOP]], label %[[EXIT:.*]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret void
	;
	entry:
	br label %loop

	loop:
	%iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
	%sub = sub nsw i32 %iv, %start
	%idx = sext i32 %sub to i64
	%gep = getelementptr nusw i32, ptr %p, i64 %idx
	store i32 0, ptr %gep, align 4
	%iv.next = add nsw i32 %iv, 1
	%ec = icmp slt i32 %iv.next, %n
	br i1 %ec, label %loop, label %exit

	exit:
	ret void
	}

	define void @induction_start_bound_ne_latch(ptr %p, i32 %start, i32 %n) {
	; CHECK-LABEL: define void @induction_start_bound_ne_latch(
	; CHECK-SAME: ptr [[P:%.]], i32 [[START:%.]], i32 [[N:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*]]:
	; CHECK-NEXT: br label %[[LOOP_HEADER:.*]]
	; CHECK: [[LOOP_HEADER]]:
	; CHECK-NEXT: [[IV:%.]] = phi i32 [ [[START]], %[[ENTRY]] ], [ [[IV_NEXT:%.]], %[[LOOP_LATCH:.*]] ]
	; CHECK-NEXT: [[EC:%.*]] = icmp ne i32 [[IV]], [[N]]
	; CHECK-NEXT: br i1 [[EC]], label %[[LOOP_BODY:.]], label %[[EXIT:.]]
	; CHECK: [[LOOP_BODY]]:
	; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[IV]], [[START]]
	; CHECK-NEXT: [[IDX:%.*]] = sext i32 [[SUB]] to i64
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw i32, ptr [[P]], i64 [[IDX]]
	; CHECK-NEXT: store i32 0, ptr [[GEP]], align 4
	; CHECK-NEXT: br label %[[LOOP_LATCH]]
	; CHECK: [[LOOP_LATCH]]:
	; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1
	; CHECK-NEXT: br label %[[LOOP_HEADER]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret void
	;
	entry:
	br label %loop.header

	loop.header:
	%iv = phi i32 [ %start, %entry ], [ %iv.next, %loop.latch ]
	%ec = icmp ne i32 %iv, %n
	br i1 %ec, label %loop.body, label %exit

	loop.body:
	%sub = sub nsw i32 %iv, %start
	%idx = sext i32 %sub to i64
	%gep = getelementptr nusw i32, ptr %p, i64 %idx
	store i32 0, ptr %gep, align 4
	br label %loop.latch

	loop.latch:
	%iv.next = add nsw i32 %iv, 1
	br label %loop.header

	exit:
	ret void
	}

	; The stride 2^63 is negative when interpreted in the pointer index type, so a
	; non-negative index does not imply a non-negative offset and nuw must not be
	; added.
	define ptr @gep_no_nuw_stride_negative_in_index_type(ptr %p, i64 %i, i64 %j) {
	; CHECK-LABEL: define ptr @gep_no_nuw_stride_negative_in_index_type(
	; CHECK-SAME: ptr [[P:%.]], i64 [[I:%.]], i64 [[J:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
	; CHECK-NEXT: br i1 [[C_0]], label %[[BB_1:.]], label %[[EXIT:.]]
	; CHECK: [[BB_1]]:
	; CHECK-NEXT: [[C_1:%.*]] = icmp sgt i64 [[J]], 0
	; CHECK-NEXT: br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
	; CHECK: [[BB_2]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw [9223372036854775808 x i8], ptr [[P]], i64 [[I]]
	; CHECK-NEXT: ret ptr [[GEP]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c.0 = icmp sgt i64 %i, %j
	br i1 %c.0, label %bb.1, label %exit

	bb.1:
	%c.1 = icmp sgt i64 %j, 0
	br i1 %c.1, label %bb.2, label %exit

	bb.2:
	%gep = getelementptr nusw [9223372036854775808 x i8], ptr %p, i64 %i
	ret ptr %gep

	exit:
	ret ptr null
	}

	; The sign of a scalable stride in the pointer index type is not known.
	define ptr @gep_no_nuw_scalable_stride(ptr %p, i64 %i, i64 %j) {
	; CHECK-LABEL: define ptr @gep_no_nuw_scalable_stride(
	; CHECK-SAME: ptr [[P:%.]], i64 [[I:%.]], i64 [[J:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sgt i64 [[I]], [[J]]
	; CHECK-NEXT: br i1 [[C_0]], label %[[BB_1:.]], label %[[EXIT:.]]
	; CHECK: [[BB_1]]:
	; CHECK-NEXT: [[C_1:%.*]] = icmp sgt i64 [[J]], 0
	; CHECK-NEXT: br i1 [[C_1]], label %[[BB_2:.*]], label %[[EXIT]]
	; CHECK: [[BB_2]]:
	; CHECK-NEXT: [[GEP:%.*]] = getelementptr nusw <vscale x 2 x i8>, ptr [[P]], i64 [[I]]
	; CHECK-NEXT: ret ptr [[GEP]]
	; CHECK: [[EXIT]]:
	; CHECK-NEXT: ret ptr null
	;
	entry:
	%c.0 = icmp sgt i64 %i, %j
	br i1 %c.0, label %bb.1, label %exit

	bb.1:
	%c.1 = icmp sgt i64 %j, 0
	br i1 %c.1, label %bb.2, label %exit

	bb.2:
	%gep = getelementptr nusw <vscale x 2 x i8>, ptr %p, i64 %i
	ret ptr %gep

	exit:
	ret ptr null
	}

	; %x <u %n <u 1024, hence %x * 3 fits an i64 unsigned and signed.
	define i64 @mul_from_transitive_unsigned_bound(i64 %x, i64 %n) {
	; CHECK-LABEL: define i64 @mul_from_transitive_unsigned_bound(
	; CHECK-SAME: i64 [[X:%.]], i64 [[N:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp ult i64 [[N]], 1024
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[C_1:%.*]] = icmp ult i64 [[X]], [[N]]
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[MUL:%.*]] = mul nuw nsw i64 [[X]], 3
	; CHECK-NEXT: ret i64 [[MUL]]
	;
	entry:
	%c.0 = icmp ult i64 %n, 1024
	call void @llvm.assume(i1 %c.0)
	%c.1 = icmp ult i64 %x, %n
	call void @llvm.assume(i1 %c.1)
	%mul = mul i64 %x, 3
	ret i64 %mul
	}

	; Same as above, but there is no upper bound for %n.
	define i64 @mul_no_flags_unbounded_transitive_operand(i64 %x, i64 %n) {
	; CHECK-LABEL: define i64 @mul_no_flags_unbounded_transitive_operand(
	; CHECK-SAME: i64 [[X:%.]], i64 [[N:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_1:%.*]] = icmp ult i64 [[X]], [[N]]
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[MUL:%.*]] = mul i64 [[X]], 3
	; CHECK-NEXT: ret i64 [[MUL]]
	;
	entry:
	%c.1 = icmp ult i64 %x, %n
	call void @llvm.assume(i1 %c.1)
	%mul = mul i64 %x, 3
	ret i64 %mul
	}

	; %x <=u %x + %y <u 1024 due to the nuw add, hence %x << 3 fits an i64 unsigned.
	define i64 @shl_nuw_from_sum_bound(i64 %x, i64 %y) {
	; CHECK-LABEL: define i64 @shl_nuw_from_sum_bound(
	; CHECK-SAME: i64 [[X:%.]], i64 [[Y:%.]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[S:%.*]] = add nuw i64 [[X]], [[Y]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp ult i64 [[S]], 1024
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[SHL:%.*]] = shl nuw i64 [[X]], 3
	; CHECK-NEXT: ret i64 [[SHL]]
	;
	entry:
	%s = add nuw i64 %x, %y
	%c.0 = icmp ult i64 %s, 1024
	call void @llvm.assume(i1 %c.0)
	%shl = shl i64 %x, 3
	ret i64 %shl
	}

	; The bound on %x is one too weak for %x << 3 to fit an i64 unsigned.
	define i64 @shl_no_nuw_bound_too_weak(i64 %x) {
	; CHECK-LABEL: define i64 @shl_no_nuw_bound_too_weak(
	; CHECK-SAME: i64 [[X:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp ult i64 [[X]], 2305843009213693953
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[SHL:%.*]] = shl i64 [[X]], 3
	; CHECK-NEXT: ret i64 [[SHL]]
	;
	entry:
	%c.0 = icmp ult i64 %x, 2305843009213693953
	call void @llvm.assume(i1 %c.0)
	%shl = shl i64 %x, 3
	ret i64 %shl
	}

	; %x >=s %z >=s 0 and %y >=s 0, hence the nsw product also fits unsigned.
	define i64 @mul_nuw_from_nsw_and_non_negative(i64 %x, i64 %y, i64 %z) {
	; CHECK-LABEL: define i64 @mul_nuw_from_nsw_and_non_negative(
	; CHECK-SAME: i64 [[X:%.]], i64 [[Y:%.]], i64 [[Z:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[C_1:%.*]] = icmp sge i64 [[Z]], 0
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[C_2:%.*]] = icmp sge i64 [[Y]], 0
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_2]])
	; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[X]], [[Y]]
	; CHECK-NEXT: ret i64 [[MUL]]
	;
	entry:
	%c.0 = icmp sge i64 %x, %z
	call void @llvm.assume(i1 %c.0)
	%c.1 = icmp sge i64 %z, 0
	call void @llvm.assume(i1 %c.1)
	%c.2 = icmp sge i64 %y, 0
	call void @llvm.assume(i1 %c.2)
	%mul = mul nsw i64 %x, %y
	ret i64 %mul
	}

	; Same as above, but %y may be negative.
	define i64 @mul_no_nuw_from_nsw_second_operand_may_be_negative(i64 %x, i64 %y, i64 %z) {
	; CHECK-LABEL: define i64 @mul_no_nuw_from_nsw_second_operand_may_be_negative(
	; CHECK-SAME: i64 [[X:%.]], i64 [[Y:%.]], i64 [[Z:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[C_1:%.*]] = icmp sge i64 [[Z]], 0
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[X]], [[Y]]
	; CHECK-NEXT: ret i64 [[MUL]]
	;
	entry:
	%c.0 = icmp sge i64 %x, %z
	call void @llvm.assume(i1 %c.0)
	%c.1 = icmp sge i64 %z, 0
	call void @llvm.assume(i1 %c.1)
	%mul = mul nsw i64 %x, %y
	ret i64 %mul
	}

	; %x >=s %z >=s 0, hence the nsw shift also fits unsigned, for any shift amount.
	define i64 @shl_nuw_from_nsw_and_non_negative(i64 %x, i64 %s, i64 %z) {
	; CHECK-LABEL: define i64 @shl_nuw_from_nsw_and_non_negative(
	; CHECK-SAME: i64 [[X:%.]], i64 [[S:%.]], i64 [[Z:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[C_1:%.*]] = icmp sge i64 [[Z]], 0
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[SHL:%.*]] = shl nsw i64 [[X]], [[S]]
	; CHECK-NEXT: ret i64 [[SHL]]
	;
	entry:
	%c.0 = icmp sge i64 %x, %z
	call void @llvm.assume(i1 %c.0)
	%c.1 = icmp sge i64 %z, 0
	call void @llvm.assume(i1 %c.1)
	%shl = shl nsw i64 %x, %s
	ret i64 %shl
	}

	; Same as above, but the shift does not have nsw.
	define i64 @shl_no_nuw_non_negative_without_nsw(i64 %x, i64 %s, i64 %z) {
	; CHECK-LABEL: define i64 @shl_no_nuw_non_negative_without_nsw(
	; CHECK-SAME: i64 [[X:%.]], i64 [[S:%.]], i64 [[Z:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sge i64 [[X]], [[Z]]
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[C_1:%.*]] = icmp sge i64 [[Z]], 0
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[SHL:%.*]] = shl i64 [[X]], [[S]]
	; CHECK-NEXT: ret i64 [[SHL]]
	;
	entry:
	%c.0 = icmp sge i64 %x, %z
	call void @llvm.assume(i1 %c.0)
	%c.1 = icmp sge i64 %z, 0
	call void @llvm.assume(i1 %c.1)
	%shl = shl i64 %x, %s
	ret i64 %shl
	}

	; -8 <=s %x <=s 7 implies %x * 16 does not wrap signed, but it may wrap
	; unsigned.
	define i8 @mul_nsw_only_from_signed_bounds(i8 %x) {
	; CHECK-LABEL: define i8 @mul_nsw_only_from_signed_bounds(
	; CHECK-SAME: i8 [[X:%.*]]) {
	; CHECK-NEXT: [[ENTRY:.*:]]
	; CHECK-NEXT: [[C_0:%.*]] = icmp sle i8 [[X]], 7
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_0]])
	; CHECK-NEXT: [[C_1:%.*]] = icmp sge i8 [[X]], -8
	; CHECK-NEXT: call void @llvm.assume(i1 [[C_1]])
	; CHECK-NEXT: [[MUL:%.*]] = mul nsw i8 [[X]], 16
	; CHECK-NEXT: ret i8 [[MUL]]
	;
	entry:
	%c.0 = icmp sle i8 %x, 7
	call void @llvm.assume(i1 %c.0)
	%c.1 = icmp sge i8 %x, -8
	call void @llvm.assume(i1 %c.1)
	%mul = mul i8 %x, 16
	ret i8 %mul
	}