; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 4
; RUN: llc < %s -mtriple=bpf -mcpu=v1 | FileCheck %s

; test that we can expand CTTZ & CTLZ

declare i32 @llvm.cttz.i32(i32, i1)

define i32 @cttz_i32_zdef(i32 %a) {
; CHECK-LABEL: cttz_i32_zdef:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 = -r2
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r1 *= 125613361
; CHECK-NEXT:    r2 = 4160749568 ll
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r1 >>= 27
; CHECK-NEXT:    r2 = {{\.?LCPI[0-9]+_[0-9]+}} ll
; CHECK-NEXT:    r2 += r1
; CHECK-NEXT:    r0 = *(u8 *)(r2 + 0)
; CHECK-NEXT:    exit
    %ret = call i32 @llvm.cttz.i32(i32 %a, i1 1)
    ret i32 %ret
}


define i32 @cttz_i32(i32 %a) {
; CHECK-LABEL: cttz_i32:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r0 = 32
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 <<= 32
; CHECK-NEXT:    r2 >>= 32
; CHECK-NEXT:    if r2 == 0 goto LBB1_2
; CHECK-NEXT:  # %bb.1: # %cond.false
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 = -r2
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r1 *= 125613361
; CHECK-NEXT:    r2 = 4160749568 ll
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r1 >>= 27
; CHECK-NEXT:    r2 = {{\.?LCPI[0-9]+_[0-9]+}} ll
; CHECK-NEXT:    r2 += r1
; CHECK-NEXT:    r0 = *(u8 *)(r2 + 0)
; CHECK-NEXT:  LBB1_2: # %cond.end
; CHECK-NEXT:    exit
    %ret = call i32 @llvm.cttz.i32(i32 %a, i1 0)
    ret i32 %ret
}

declare i64 @llvm.cttz.i64(i64, i1)

define i64 @cttz_i64_zdef(i64 %a) {
; CHECK-LABEL: cttz_i64_zdef:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 = -r2
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r2 = 151050438420815295 ll
; CHECK-NEXT:    r1 *= r2
; CHECK-NEXT:    r1 >>= 58
; CHECK-NEXT:    r2 = {{\.?LCPI[0-9]+_[0-9]+}} ll
; CHECK-NEXT:    r2 += r1
; CHECK-NEXT:    r0 = *(u8 *)(r2 + 0)
; CHECK-NEXT:    exit
    %ret = call i64 @llvm.cttz.i64(i64 %a, i1 1)
    ret i64 %ret
}


define i64 @cttz_i64(i64 %a) {
; CHECK-LABEL: cttz_i64:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r0 = 64
; CHECK-NEXT:    if r1 == 0 goto LBB3_2
; CHECK-NEXT:  # %bb.1: # %cond.false
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 = -r2
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r2 = 151050438420815295 ll
; CHECK-NEXT:    r1 *= r2
; CHECK-NEXT:    r1 >>= 58
; CHECK-NEXT:    r2 = {{\.?LCPI[0-9]+_[0-9]+}} ll
; CHECK-NEXT:    r2 += r1
; CHECK-NEXT:    r0 = *(u8 *)(r2 + 0)
; CHECK-NEXT:  LBB3_2: # %cond.end
; CHECK-NEXT:    exit
    %ret = call i64 @llvm.cttz.i64(i64 %a, i1 0)
    ret i64 %ret
}


declare i32 @llvm.ctlz.i32(i32, i1)

define i32 @ctlz_i32_zdef(i32 %a) {
; CHECK-LABEL: ctlz_i32_zdef:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r2 = 4294967294 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 1
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294967292 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 2
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294967280 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 4
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294967040 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 8
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294901760 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 16
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r1 ^= -1
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 1
; CHECK-NEXT:    r2 &= 1431655765
; CHECK-NEXT:    r1 -= r2
; CHECK-NEXT:    r0 = r1
; CHECK-NEXT:    r0 &= 858993459
; CHECK-NEXT:    r1 >>= 2
; CHECK-NEXT:    r1 &= 858993459
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r1 = r0
; CHECK-NEXT:    r1 >>= 4
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r0 &= 252645135
; CHECK-NEXT:    r0 *= 16843009
; CHECK-NEXT:    r1 = 4278190080 ll
; CHECK-NEXT:    r0 &= r1
; CHECK-NEXT:    r0 >>= 24
; CHECK-NEXT:    exit
    %ret = call i32 @llvm.ctlz.i32(i32 %a, i1 1)
    ret i32 %ret
}


define i32 @ctlz_i32(i32 %a) {
; CHECK-LABEL: ctlz_i32:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r0 = 32
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 <<= 32
; CHECK-NEXT:    r2 >>= 32
; CHECK-NEXT:    if r2 == 0 goto LBB5_2
; CHECK-NEXT:  # %bb.1: # %cond.false
; CHECK-NEXT:    r2 = 4294967294 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 1
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294967292 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 2
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294967280 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 4
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294967040 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 8
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r2 = 4294901760 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r3 >>= 16
; CHECK-NEXT:    r1 |= r3
; CHECK-NEXT:    r1 ^= -1
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 1
; CHECK-NEXT:    r2 &= 1431655765
; CHECK-NEXT:    r1 -= r2
; CHECK-NEXT:    r0 = r1
; CHECK-NEXT:    r0 &= 858993459
; CHECK-NEXT:    r1 >>= 2
; CHECK-NEXT:    r1 &= 858993459
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r1 = r0
; CHECK-NEXT:    r1 >>= 4
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r0 &= 252645135
; CHECK-NEXT:    r0 *= 16843009
; CHECK-NEXT:    r1 = 4278190080 ll
; CHECK-NEXT:    r0 &= r1
; CHECK-NEXT:    r0 >>= 24
; CHECK-NEXT:  LBB5_2: # %cond.end
; CHECK-NEXT:    exit
    %ret = call i32 @llvm.ctlz.i32(i32 %a, i1 0)
    ret i32 %ret
}

declare i64 @llvm.ctlz.i64(i64, i1)

define i64 @ctlz_i64_zdef(i64 %a) {
; CHECK-LABEL: ctlz_i64_zdef:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 1
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 2
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 4
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 8
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 16
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 32
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r1 ^= -1
; CHECK-NEXT:    r2 = 6148914691236517205 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 >>= 1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r1 -= r3
; CHECK-NEXT:    r2 = 3689348814741910323 ll
; CHECK-NEXT:    r0 = r1
; CHECK-NEXT:    r0 &= r2
; CHECK-NEXT:    r1 >>= 2
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r1 = r0
; CHECK-NEXT:    r1 >>= 4
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r1 = 1085102592571150095 ll
; CHECK-NEXT:    r0 &= r1
; CHECK-NEXT:    r1 = 72340172838076673 ll
; CHECK-NEXT:    r0 *= r1
; CHECK-NEXT:    r0 >>= 56
; CHECK-NEXT:    exit
    %ret = call i64 @llvm.ctlz.i64(i64 %a, i1 1)
    ret i64 %ret
}


define i64 @ctlz_i64(i64 %a) {
; CHECK-LABEL: ctlz_i64:
; CHECK:       # %bb.0:
; CHECK-NEXT:    r0 = 64
; CHECK-NEXT:    if r1 == 0 goto LBB7_2
; CHECK-NEXT:  # %bb.1: # %cond.false
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 1
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 2
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 4
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 8
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 16
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r2 = r1
; CHECK-NEXT:    r2 >>= 32
; CHECK-NEXT:    r1 |= r2
; CHECK-NEXT:    r1 ^= -1
; CHECK-NEXT:    r2 = 6148914691236517205 ll
; CHECK-NEXT:    r3 = r1
; CHECK-NEXT:    r3 >>= 1
; CHECK-NEXT:    r3 &= r2
; CHECK-NEXT:    r1 -= r3
; CHECK-NEXT:    r2 = 3689348814741910323 ll
; CHECK-NEXT:    r0 = r1
; CHECK-NEXT:    r0 &= r2
; CHECK-NEXT:    r1 >>= 2
; CHECK-NEXT:    r1 &= r2
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r1 = r0
; CHECK-NEXT:    r1 >>= 4
; CHECK-NEXT:    r0 += r1
; CHECK-NEXT:    r1 = 1085102592571150095 ll
; CHECK-NEXT:    r0 &= r1
; CHECK-NEXT:    r1 = 72340172838076673 ll
; CHECK-NEXT:    r0 *= r1
; CHECK-NEXT:    r0 >>= 56
; CHECK-NEXT:  LBB7_2: # %cond.end
; CHECK-NEXT:    exit
    %ret = call i64 @llvm.ctlz.i64(i64 %a, i1 0)
    ret i64 %ret
}