; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
; RUN: llc -mtriple=i686-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=CHECK,X86
; RUN: llc -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=CHECK,X64

; This tests the BuildREMEqFold optimization with UREM, i32, odd divisor, SETEQ.
; The corresponding pseudocode is:
; Q <- [N * multInv(5, 2^32)] <=> [N * 0xCCCCCCCD] <=> [N * (-858993459)]
; res <- [Q <= (2^32 - 1) / 5] <=> [Q <= 858993459] <=> [Q < 858993460]
define i32 @test_urem_odd(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_odd:
; X86:       # %bb.0:
; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
; X86-NEXT:    movl $-858993459, %edx # imm = 0xCCCCCCCD
; X86-NEXT:    movl %ecx, %eax
; X86-NEXT:    mull %edx
; X86-NEXT:    shrl $2, %edx
; X86-NEXT:    leal (%edx,%edx,4), %edx
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpl %edx, %ecx
; X86-NEXT:    sete %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_odd:
; X64:       # %bb.0:
; X64-NEXT:    movl %edi, %eax
; X64-NEXT:    movl $3435973837, %ecx # imm = 0xCCCCCCCD
; X64-NEXT:    imulq %rax, %rcx
; X64-NEXT:    shrq $34, %rcx
; X64-NEXT:    leal (%rcx,%rcx,4), %ecx
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpl %ecx, %edi
; X64-NEXT:    sete %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 5
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

; This is like test_urem_odd, except the divisor has bit 30 set.
define i32 @test_urem_odd_bit30(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_odd_bit30:
; X86:       # %bb.0:
; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
; X86-NEXT:    movl $-11, %edx
; X86-NEXT:    movl %ecx, %eax
; X86-NEXT:    mull %edx
; X86-NEXT:    shrl $30, %edx
; X86-NEXT:    imull $1073741827, %edx, %edx # imm = 0x40000003
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpl %edx, %ecx
; X86-NEXT:    sete %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_odd_bit30:
; X64:       # %bb.0:
; X64-NEXT:    movl %edi, %eax
; X64-NEXT:    movl $4294967285, %ecx # imm = 0xFFFFFFF5
; X64-NEXT:    imulq %rax, %rcx
; X64-NEXT:    shrq $62, %rcx
; X64-NEXT:    imull $1073741827, %ecx, %ecx # imm = 0x40000003
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpl %ecx, %edi
; X64-NEXT:    sete %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 1073741827
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

; This is like test_urem_odd, except the divisor has bit 31 set.
define i32 @test_urem_odd_bit31(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_odd_bit31:
; X86:       # %bb.0:
; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
; X86-NEXT:    movl $1073741823, %edx # imm = 0x3FFFFFFF
; X86-NEXT:    movl %ecx, %eax
; X86-NEXT:    mull %edx
; X86-NEXT:    shrl $29, %edx
; X86-NEXT:    imull $-2147483645, %edx, %edx # imm = 0x80000003
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpl %edx, %ecx
; X86-NEXT:    sete %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_odd_bit31:
; X64:       # %bb.0:
; X64-NEXT:    movl %edi, %eax
; X64-NEXT:    movq %rax, %rcx
; X64-NEXT:    shlq $30, %rcx
; X64-NEXT:    subq %rax, %rcx
; X64-NEXT:    shrq $61, %rcx
; X64-NEXT:    imull $-2147483645, %ecx, %ecx # imm = 0x80000003
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpl %ecx, %edi
; X64-NEXT:    sete %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 2147483651
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

; This tests the BuildREMEqFold optimization with UREM, i16, even divisor, SETNE.
; In this case, D <=> 14 <=> 7 * 2^1, so D0 = 7 and K = 1.
; The corresponding pseudocode is:
; Q <- [N * multInv(D0, 2^16)] <=> [N * multInv(7, 2^16)] <=> [N * 28087]
; Q <- [Q >>rot K] <=> [Q >>rot 1]
; res <- ![Q <= (2^16 - 1) / 7] <=> ![Q <= 9362] <=> [Q > 9362]
define i16 @test_urem_even(i16 %X) nounwind readnone {
; X86-LABEL: test_urem_even:
; X86:       # %bb.0:
; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %ecx
; X86-NEXT:    movl %ecx, %eax
; X86-NEXT:    shrl %eax
; X86-NEXT:    imull $18725, %eax, %eax # imm = 0x4925
; X86-NEXT:    shrl $17, %eax
; X86-NEXT:    movl %eax, %edx
; X86-NEXT:    shll $4, %edx
; X86-NEXT:    subl %eax, %edx
; X86-NEXT:    subl %eax, %edx
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpw %dx, %cx
; X86-NEXT:    setne %al
; X86-NEXT:    # kill: def $ax killed $ax killed $eax
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_even:
; X64:       # %bb.0:
; X64-NEXT:    movzwl %di, %ecx
; X64-NEXT:    movl %ecx, %eax
; X64-NEXT:    shrl %eax
; X64-NEXT:    imull $18725, %eax, %eax # imm = 0x4925
; X64-NEXT:    shrl $17, %eax
; X64-NEXT:    movl %eax, %edx
; X64-NEXT:    shll $4, %edx
; X64-NEXT:    subl %eax, %edx
; X64-NEXT:    subl %eax, %edx
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpw %dx, %cx
; X64-NEXT:    setne %al
; X64-NEXT:    # kill: def $ax killed $ax killed $eax
; X64-NEXT:    retq
  %urem = urem i16 %X, 14
  %cmp = icmp ne i16 %urem, 0
  %ret = zext i1 %cmp to i16
  ret i16 %ret
}

; This is like test_urem_even, except the divisor has bit 30 set.
define i32 @test_urem_even_bit30(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_even_bit30:
; X86:       # %bb.0:
; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
; X86-NEXT:    movl $-415, %edx # imm = 0xFE61
; X86-NEXT:    movl %ecx, %eax
; X86-NEXT:    mull %edx
; X86-NEXT:    shrl $30, %edx
; X86-NEXT:    imull $1073741928, %edx, %edx # imm = 0x40000068
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpl %edx, %ecx
; X86-NEXT:    sete %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_even_bit30:
; X64:       # %bb.0:
; X64-NEXT:    movl %edi, %eax
; X64-NEXT:    movl $4294966881, %ecx # imm = 0xFFFFFE61
; X64-NEXT:    imulq %rax, %rcx
; X64-NEXT:    shrq $62, %rcx
; X64-NEXT:    imull $1073741928, %ecx, %ecx # imm = 0x40000068
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpl %ecx, %edi
; X64-NEXT:    sete %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 1073741928
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

; This is like test_urem_odd, except the divisor has bit 31 set.
define i32 @test_urem_even_bit31(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_even_bit31:
; X86:       # %bb.0:
; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
; X86-NEXT:    movl $2147483547, %edx # imm = 0x7FFFFF9B
; X86-NEXT:    movl %ecx, %eax
; X86-NEXT:    mull %edx
; X86-NEXT:    shrl $30, %edx
; X86-NEXT:    imull $-2147483546, %edx, %edx # imm = 0x80000066
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpl %edx, %ecx
; X86-NEXT:    sete %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_even_bit31:
; X64:       # %bb.0:
; X64-NEXT:    movl %edi, %eax
; X64-NEXT:    imulq $2147483547, %rax, %rax # imm = 0x7FFFFF9B
; X64-NEXT:    shrq $62, %rax
; X64-NEXT:    imull $-2147483546, %eax, %ecx # imm = 0x80000066
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpl %ecx, %edi
; X64-NEXT:    sete %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 2147483750
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

; We should not proceed with this fold if the divisor is 1 or -1
define i32 @test_urem_one(i32 %X) nounwind readnone {
; CHECK-LABEL: test_urem_one:
; CHECK:       # %bb.0:
; CHECK-NEXT:    movl $1, %eax
; CHECK-NEXT:    ret{{[l|q]}}
  %urem = urem i32 %X, 1
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

; We can lower remainder of division by powers of two much better elsewhere;
; also, BuildREMEqFold does not work when the only odd factor of the divisor is 1.
; This ensures we don't touch powers of two.
define i32 @test_urem_pow2(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_pow2:
; X86:       # %bb.0:
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    testb $15, {{[0-9]+}}(%esp)
; X86-NEXT:    sete %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_pow2:
; X64:       # %bb.0:
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    testb $15, %dil
; X64-NEXT:    sete %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 16
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}