; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; Test that the memchr library call simplifier works correctly.
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"

@hello = constant [14 x i8] c"hello world\5Cn\00"
@hellonull = constant [14 x i8] c"hello\00world\5Cn\00"
@null = constant [1 x i8] zeroinitializer
@newlines = constant [3 x i8] c"\0D\0A\00"
@single = constant [2 x i8] c"\1F\00"
@spaces = constant [4 x i8] c" \0D\0A\00"
@negative = constant [3 x i8] c"\FF\FE\00"
@chp = global ptr zeroinitializer

declare ptr @memchr(ptr, i32, i32)

define void @test1() {
; CHECK-LABEL: @test1(
; CHECK-NEXT:    store ptr getelementptr inbounds nuw (i8, ptr @hello, i32 6), ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @hello, i32 119, i32 14)
  store ptr %dst, ptr @chp
  ret void
}

define void @test2() {
; CHECK-LABEL: @test2(
; CHECK-NEXT:    store ptr null, ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @null, i32 119, i32 1)
  store ptr %dst, ptr @chp
  ret void
}

define void @test3() {
; CHECK-LABEL: @test3(
; CHECK-NEXT:    store ptr getelementptr inbounds nuw (i8, ptr @hello, i32 13), ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @hello, i32 0, i32 14)
  store ptr %dst, ptr @chp
  ret void
}

define void @test4(i32 %chr) {
; CHECK-LABEL: @test4(
; CHECK-NEXT:    [[DST:%.*]] = call ptr @memchr(ptr noundef nonnull dereferenceable(1) @hello, i32 [[CHR:%.*]], i32 14)
; CHECK-NEXT:    store ptr [[DST]], ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @hello, i32 %chr, i32 14)
  store ptr %dst, ptr @chp
  ret void
}

define void @test5() {
; CHECK-LABEL: @test5(
; CHECK-NEXT:    store ptr getelementptr inbounds nuw (i8, ptr @hello, i32 13), ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @hello, i32 65280, i32 14)
  store ptr %dst, ptr @chp
  ret void
}

define void @test6() {
; CHECK-LABEL: @test6(
; CHECK-NEXT:    store ptr getelementptr inbounds nuw (i8, ptr @hello, i32 6), ptr @chp, align 4
; CHECK-NEXT:    ret void
;
; Overflow, but we still find the right thing.
  %dst = call ptr @memchr(ptr @hello, i32 119, i32 100)
  store ptr %dst, ptr @chp
  ret void
}

define void @test7() {
; CHECK-LABEL: @test7(
; CHECK-NEXT:    store ptr null, ptr @chp, align 4
; CHECK-NEXT:    ret void
;
; Overflow
  %dst = call ptr @memchr(ptr @hello, i32 120, i32 100)
  store ptr %dst, ptr @chp
  ret void
}

define void @test8() {
; CHECK-LABEL: @test8(
; CHECK-NEXT:    store ptr getelementptr inbounds nuw (i8, ptr @hellonull, i32 6), ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @hellonull, i32 119, i32 14)
  store ptr %dst, ptr @chp
  ret void
}

define void @test9() {
; CHECK-LABEL: @test9(
; CHECK-NEXT:    store ptr getelementptr inbounds nuw (i8, ptr @hellonull, i32 6), ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %str = getelementptr [14 x i8], ptr @hellonull, i32 0, i32 2
  %dst = call ptr @memchr(ptr %str, i32 119, i32 12)
  store ptr %dst, ptr @chp
  ret void
}

define void @test10() {
; CHECK-LABEL: @test10(
; CHECK-NEXT:    store ptr null, ptr @chp, align 4
; CHECK-NEXT:    ret void
;
  %dst = call ptr @memchr(ptr @hello, i32 119, i32 6)
  store ptr %dst, ptr @chp
  ret void
}

; Check transformation memchr("\r\n", C, 3) != nullptr -> (C & 9217) != 0
define i1 @test11(i32 %C) {
; CHECK-LABEL: @test11(
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i16
; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], 255
; CHECK-NEXT:    [[MEMCHR_BOUNDS:%.*]] = icmp samesign ult i16 [[TMP2]], 16
; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i16 1, [[TMP2]]
; CHECK-NEXT:    [[TMP4:%.*]] = and i16 [[TMP3]], 9217
; CHECK-NEXT:    [[MEMCHR_BITS:%.*]] = icmp ne i16 [[TMP4]], 0
; CHECK-NEXT:    [[MEMCHR:%.*]] = select i1 [[MEMCHR_BOUNDS]], i1 [[MEMCHR_BITS]], i1 false
; CHECK-NEXT:    ret i1 [[MEMCHR]]
;
  %dst = call ptr @memchr(ptr @newlines, i32 %C, i32 3)
  %cmp = icmp ne ptr %dst, null
  ret i1 %cmp
}

; No 64 bits here
define i1 @test12(i32 %C) {
; CHECK-LABEL: @test12(
; CHECK-NEXT:    [[DST:%.*]] = call ptr @memchr(ptr noundef nonnull dereferenceable(1) @spaces, i32 [[C:%.*]], i32 3)
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne ptr [[DST]], null
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %dst = call ptr @memchr(ptr @spaces, i32 %C, i32 3)
  %cmp = icmp ne ptr %dst, null
  ret i1 %cmp
}

define i1 @test13(i32 %C) {
; CHECK-LABEL: @test13(
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 31
; CHECK-NEXT:    [[CMP:%.*]] = or i1 [[TMP3]], [[TMP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %dst = call ptr @memchr(ptr @single, i32 %C, i32 2)
  %cmp = icmp ne ptr %dst, null
  ret i1 %cmp
}

define i1 @test14(i32 %C) {
; CHECK-LABEL: @test14(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], 255
; CHECK-NEXT:    [[MEMCHR_CHAR0CMP:%.*]] = icmp eq i32 [[TMP1]], 31
; CHECK-NEXT:    ret i1 [[MEMCHR_CHAR0CMP]]
;
  %dst = call ptr @memchr(ptr @single, i32 %C, i32 1)
  %cmp = icmp ne ptr %dst, null
  ret i1 %cmp
}

define i1 @test15(i32 %C, i32 %n) {
; CHECK-LABEL: @test15(
; CHECK-NEXT:    [[DST:%.*]] = call ptr @memchr(ptr nonnull @negative, i32 [[C:%.*]], i32 [[N:%.*]])
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne ptr [[DST]], null
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %dst = call ptr @memchr(ptr @negative, i32 %C, i32 %n)
  %cmp = icmp ne ptr %dst, null
  ret i1 %cmp
}

@s = internal constant [1 x i8] [i8 0], align 1
define ptr @pr32124() {
; CHECK-LABEL: @pr32124(
; CHECK-NEXT:    ret ptr @s
;
  %res = tail call ptr @memchr(ptr @s, i32 0, i32 1)
  ret ptr %res
}

define ptr @test16(ptr %str, i32 %c, i32 %n) {
; CHECK-LABEL: @test16(
; CHECK-NEXT:    [[RET:%.*]] = call ptr @memchr(ptr [[STR:%.*]], i32 [[C:%.*]], i32 [[N:%.*]])
; CHECK-NEXT:    ret ptr [[RET]]
;

  %ret = call ptr @memchr(ptr %str, i32 %c, i32 %n)
  ret ptr %ret
}

define ptr @test17(ptr %str, i32 %c, i32 %n) {
; CHECK-LABEL: @test17(
; CHECK-NEXT:    [[RET:%.*]] = call ptr @memchr(ptr nonnull [[STR:%.*]], i32 [[C:%.*]], i32 [[N:%.*]])
; CHECK-NEXT:    ret ptr [[RET]]
;

  %ret = call ptr @memchr(ptr nonnull %str, i32 %c, i32 %n)
  ret ptr %ret
}

define ptr @test18(ptr %str, i32 %c) {
; CHECK-LABEL: @test18(
; CHECK-NEXT:    [[RET:%.*]] = call ptr @memchr(ptr noundef nonnull dereferenceable(1) [[STR:%.*]], i32 [[C:%.*]], i32 5)
; CHECK-NEXT:    ret ptr [[RET]]
;

  %ret = call ptr @memchr(ptr %str, i32 %c, i32 5)
  ret ptr %ret
}

define ptr @test19(ptr %str, i32 %c) null_pointer_is_valid {
; CHECK-LABEL: @test19(
; CHECK-NEXT:    [[RET:%.*]] = call ptr @memchr(ptr noundef [[STR:%.*]], i32 [[C:%.*]], i32 5)
; CHECK-NEXT:    ret ptr [[RET]]
;

  %ret = call ptr @memchr(ptr %str, i32 %c, i32 5)
  ret ptr %ret
}