; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
; RUN: llc < %s -mtriple=aarch64 | FileCheck %s
; RUN: llc < %s -mtriple=aarch64 -global-isel -global-isel-abort=1 | FileCheck %s --check-prefix=GISEL

; Convert mul x, pow2 to shift.
; Convert mul x, pow2 +/- 1 to shift + add/sub.
; Convert mul x, (pow2 + 1) * pow2 to shift + add + shift.
; Lowering other positive constants are not supported yet.

define i32 @test2(i32 %x) {
; CHECK-LABEL: test2:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w0, w0, #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test2:
; GISEL:       // %bb.0:
; GISEL-NEXT:    lsl w0, w0, #1
; GISEL-NEXT:    ret

  %mul = shl nsw i32 %x, 1
  ret i32 %mul
}

define i32 @test3(i32 %x) {
; CHECK-LABEL: test3:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w0, w0, w0, lsl #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test3:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w0, w0, w0, lsl #1
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 3
  ret i32 %mul
}

define i32 @test4(i32 %x) {
; CHECK-LABEL: test4:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w0, w0, #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test4:
; GISEL:       // %bb.0:
; GISEL-NEXT:    lsl w0, w0, #2
; GISEL-NEXT:    ret

  %mul = shl nsw i32 %x, 2
  ret i32 %mul
}

define i32 @test5(i32 %x) {
; CHECK-LABEL: test5:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w0, w0, w0, lsl #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test5:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w0, w0, w0, lsl #2
; GISEL-NEXT:    ret


  %mul = mul nsw i32 %x, 5
  ret i32 %mul
}

define i32 @test6_32b(i32 %x) {
; CHECK-LABEL: test6_32b:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #1
; CHECK-NEXT:    lsl w0, w8, #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_32b:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w8, w0, w0, lsl #1
; GISEL-NEXT:    lsl w0, w8, #1
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 6
  ret i32 %mul
}

define i64 @test6_64b(i64 %x) {
; CHECK-LABEL: test6_64b:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add x8, x0, x0, lsl #1
; CHECK-NEXT:    lsl x0, x8, #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_64b:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add x8, x0, x0, lsl #1
; GISEL-NEXT:    lsl x0, x8, #1
; GISEL-NEXT:    ret

  %mul = mul nsw i64 %x, 6
  ret i64 %mul
}

; mul that appears together with add, sub, s(z)ext is not supported to be
; converted to the combination of lsl, add/sub yet.
define i64 @test6_umull(i32 %x) {
; CHECK-LABEL: test6_umull:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    umull x0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_umull:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    umull x0, w0, w8
; GISEL-NEXT:    ret

  %ext = zext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  ret i64 %mul
}

define i64 @test6_smull(i32 %x) {
; CHECK-LABEL: test6_smull:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    smull x0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_smull:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    smull x0, w0, w8
; GISEL-NEXT:    ret

  %ext = sext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  ret i64 %mul
}

define i32 @test6_madd(i32 %x, i32 %y) {
; CHECK-LABEL: test6_madd:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    madd w0, w0, w8, w1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_madd:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    madd w0, w0, w8, w1
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 6
  %add = add i32 %mul, %y
  ret i32 %add
}

define i32 @test6_msub(i32 %x, i32 %y) {
; CHECK-LABEL: test6_msub:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    msub w0, w0, w8, w1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_msub:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    msub w0, w0, w8, w1
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 6
  %sub = sub i32 %y, %mul
  ret i32 %sub
}

define i64 @test6_umaddl(i32 %x, i64 %y) {
; CHECK-LABEL: test6_umaddl:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    umaddl x0, w0, w8, x1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_umaddl:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    umaddl x0, w0, w8, x1
; GISEL-NEXT:    ret

  %ext = zext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  %add = add i64 %mul, %y
  ret i64 %add
}

define i64 @test6_smaddl(i32 %x, i64 %y) {
; CHECK-LABEL: test6_smaddl:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    smaddl x0, w0, w8, x1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_smaddl:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    smaddl x0, w0, w8, x1
; GISEL-NEXT:    ret

  %ext = sext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  %add = add i64 %mul, %y
  ret i64 %add
}

define i64 @test6_umsubl(i32 %x, i64 %y) {
; CHECK-LABEL: test6_umsubl:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    umsubl x0, w0, w8, x1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_umsubl:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    umsubl x0, w0, w8, x1
; GISEL-NEXT:    ret

  %ext = zext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  %sub = sub i64 %y, %mul
  ret i64 %sub
}

define i64 @test6_smsubl(i32 %x, i64 %y) {
; CHECK-LABEL: test6_smsubl:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    smsubl x0, w0, w8, x1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_smsubl:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    smsubl x0, w0, w8, x1
; GISEL-NEXT:    ret

  %ext = sext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  %sub = sub i64 %y, %mul
  ret i64 %sub
}

define i64 @test6_umnegl(i32 %x) {
; CHECK-LABEL: test6_umnegl:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    umnegl x0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_umnegl:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    umnegl x0, w0, w8
; GISEL-NEXT:    ret

  %ext = zext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  %sub = sub i64 0, %mul
  ret i64 %sub
}

define i64 @test6_smnegl(i32 %x) {
; CHECK-LABEL: test6_smnegl:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    smnegl x0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test6_smnegl:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    smnegl x0, w0, w8
; GISEL-NEXT:    ret

  %ext = sext i32 %x to i64
  %mul = mul nsw i64 %ext, 6
  %sub = sub i64 0, %mul
  ret i64 %sub
}

; We may hoist the "mov" instructions out of a loop
define i32 @mull6_sub(i32 %x) {
; CHECK-LABEL: mull6_sub:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    mov w9, #-1 // =0xffffffff
; CHECK-NEXT:    madd w0, w0, w8, w9
; CHECK-NEXT:    ret
;
; GISEL-LABEL: mull6_sub:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    mov w9, #-1 // =0xffffffff
; GISEL-NEXT:    madd w0, w0, w8, w9
; GISEL-NEXT:    ret
  %mul = mul nsw i32 %x, 6
  %sub = add nsw i32 %mul, -1
  ret i32 %sub
}

define i64 @mull6_sub_orr(i64 %x) {
; CHECK-LABEL: mull6_sub_orr:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #6 // =0x6
; CHECK-NEXT:    mov x9, #16773120 // =0xfff000
; CHECK-NEXT:    madd x0, x0, x8, x9
; CHECK-NEXT:    ret
;
; GISEL-LABEL: mull6_sub_orr:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #6 // =0x6
; GISEL-NEXT:    mov x9, #16773120 // =0xfff000
; GISEL-NEXT:    madd x0, x0, x8, x9
; GISEL-NEXT:    ret
  %mul = mul nsw i64 %x, 6
  %sub = add nsw i64 %mul, 16773120
  ret i64 %sub
}

define i32 @test7(i32 %x) {
; CHECK-LABEL: test7:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #3
; CHECK-NEXT:    sub w0, w8, w0
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test7:
; GISEL:       // %bb.0:
; GISEL-NEXT:    lsl w8, w0, #3
; GISEL-NEXT:    sub w0, w8, w0
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 7
  ret i32 %mul
}

define i32 @test8(i32 %x) {
; CHECK-LABEL: test8:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w0, w0, #3
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test8:
; GISEL:       // %bb.0:
; GISEL-NEXT:    lsl w0, w0, #3
; GISEL-NEXT:    ret

  %mul = shl nsw i32 %x, 3
  ret i32 %mul
}

define i32 @test9(i32 %x) {
; CHECK-LABEL: test9:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w0, w0, w0, lsl #3
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test9:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w0, w0, w0, lsl #3
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 9
  ret i32 %mul
}

define i32 @test10(i32 %x) {
; CHECK-LABEL: test10:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #2
; CHECK-NEXT:    lsl w0, w8, #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test10:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w8, w0, w0, lsl #2
; GISEL-NEXT:    lsl w0, w8, #1
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 10
  ret i32 %mul
}

define i32 @test11(i32 %x) {
; CHECK-LABEL: test11:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #11 // =0xb
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test11:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #11 // =0xb
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 11
  ret i32 %mul
}

define i32 @test11_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test11_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #2
; CHECK-NEXT:    add w0, w0, w8, lsl #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test11_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #11 // =0xb
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 11 ; 11 = (((1<<2) + 1) << 1) + 1
  ret i32 %mul
}

define i32 @test12(i32 %x) {
; CHECK-LABEL: test12:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #1
; CHECK-NEXT:    lsl w0, w8, #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test12:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w8, w0, w0, lsl #1
; GISEL-NEXT:    lsl w0, w8, #2
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 12
  ret i32 %mul
}

define i32 @test13(i32 %x) {
; CHECK-LABEL: test13:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #13 // =0xd
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test13:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #13 // =0xd
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 13
  ret i32 %mul
}

define i32 @test14(i32 %x) {
; CHECK-LABEL: test14:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #4
; CHECK-NEXT:    sub w0, w8, w0, lsl #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test14:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #14 // =0xe
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 14
  ret i32 %mul
}

define i32 @test15(i32 %x) {
; CHECK-LABEL: test15:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #4
; CHECK-NEXT:    sub w0, w8, w0
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test15:
; GISEL:       // %bb.0:
; GISEL-NEXT:    lsl w8, w0, #4
; GISEL-NEXT:    sub w0, w8, w0
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 15
  ret i32 %mul
}

define i32 @test16(i32 %x) {
; CHECK-LABEL: test16:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w0, w0, #4
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test16:
; GISEL:       // %bb.0:
; GISEL-NEXT:    lsl w0, w0, #4
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 16
  ret i32 %mul
}

define i32 @test25_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test25_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #2
; CHECK-NEXT:    add w0, w8, w8, lsl #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test25_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #25 // =0x19
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 25 ; 25 = (1+4)*(1+4)
  ret i32 %mul
}

define i32 @test29_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test29_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    sub w8, w0, w0, lsl #3
; CHECK-NEXT:    sub w0, w0, w8, lsl #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test29_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #29 // =0x1d
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 29 ; 29 = 1 - (1-8) * 4
  ret i32 %mul
}

define i32 @test45_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test45_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #2
; CHECK-NEXT:    add w0, w8, w8, lsl #3
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test45_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #45 // =0x2d
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 45 ; 45 = (1+4)*(1+8)
  ret i32 %mul
}

; Negative test: Keep MUL as don't have the feature LSLFast
define i32 @test45(i32 %x) {
; CHECK-LABEL: test45:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #45 // =0x2d
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test45:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #45 // =0x2d
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 45 ; 45 = (1+4)*(1+8)
  ret i32 %mul
}

; Negative test: The shift number 5 is out of bound
define i32 @test67_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test67_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #67 // =0x43
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test67_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #67 // =0x43
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 67 ; 67 = (((1<<5) + 1) << 1) + 1
  ret i32 %mul
}

define i32 @test85_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test85_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #2
; CHECK-NEXT:    add w0, w8, w8, lsl #4
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test85_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #85 // =0x55
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 85 ; 85 = (1+4)*(1+16)
  ret i32 %mul
}

; Negative test: The shift number 5 is out of bound
define i32 @test97_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test97_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #97 // =0x61
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test97_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #97 // =0x61
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 97 ; 97 = ((2 + 1) << 5) + 1
  ret i32 %mul
}

; Negative test: The shift number 5 is out of bound
define i32 @test125_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test125_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #125 // =0x7d
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test125_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #125 // =0x7d
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 125 ; 125 = 1 - ((1-32) << 2)
  ret i32 %mul
}

; TODO: (1 - 2^M) * (1 - 2^N)
define i32 @test225_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test225_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #225 // =0xe1
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test225_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #225 // =0xe1
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 225 ; 225 = (1-16)*(1-16)
  ret i32 %mul
}

; Negative test: The shift amount 5 larger than 4
define i32 @test297_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test297_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #297 // =0x129
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test297_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #297 // =0x129
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 297 ; 297 = (1+8)*(1+32)
  ret i32 %mul
}

; Negative test: The shift number 5 is out of bound
define i32 @test481_fast_shift(i32 %x) "target-features"="+alu-lsl-fast" {
; CHECK-LABEL: test481_fast_shift:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #481 // =0x1e1
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: test481_fast_shift:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #481 // =0x1e1
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, 481 ; 481 = 1 - ((1-16) << 5)
  ret i32 %mul
}

; Convert mul x, -pow2 to shift.
; Convert mul x, -(pow2 +/- 1) to shift + add/sub.
; Lowering other negative constants are not supported yet.

define i32 @ntest2(i32 %x) {
; CHECK-LABEL: ntest2:
; CHECK:       // %bb.0:
; CHECK-NEXT:    neg w0, w0, lsl #1
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest2:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-2 // =0xfffffffe
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -2
  ret i32 %mul
}

define i32 @ntest3(i32 %x) {
; CHECK-LABEL: ntest3:
; CHECK:       // %bb.0:
; CHECK-NEXT:    sub w0, w0, w0, lsl #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest3:
; GISEL:       // %bb.0:
; GISEL-NEXT:    sub w0, w0, w0, lsl #2
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -3
  ret i32 %mul
}

define i32 @ntest4(i32 %x) {
; CHECK-LABEL: ntest4:
; CHECK:       // %bb.0:
; CHECK-NEXT:    neg w0, w0, lsl #2
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest4:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-4 // =0xfffffffc
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -4
  ret i32 %mul
}

define i32 @ntest5(i32 %x) {
; CHECK-LABEL: ntest5:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #2
; CHECK-NEXT:    neg w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest5:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w8, w0, w0, lsl #2
; GISEL-NEXT:    neg w0, w8
; GISEL-NEXT:    ret
  %mul = mul nsw i32 %x, -5
  ret i32 %mul
}

define i32 @ntest6(i32 %x) {
; CHECK-LABEL: ntest6:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #1
; CHECK-NEXT:    sub w0, w8, w0, lsl #3
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest6:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-6 // =0xfffffffa
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -6
  ret i32 %mul
}

define i32 @ntest7(i32 %x) {
; CHECK-LABEL: ntest7:
; CHECK:       // %bb.0:
; CHECK-NEXT:    sub w0, w0, w0, lsl #3
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest7:
; GISEL:       // %bb.0:
; GISEL-NEXT:    sub w0, w0, w0, lsl #3
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -7
  ret i32 %mul
}

define i32 @ntest8(i32 %x) {
; CHECK-LABEL: ntest8:
; CHECK:       // %bb.0:
; CHECK-NEXT:    neg w0, w0, lsl #3
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest8:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-8 // =0xfffffff8
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -8
  ret i32 %mul
}

define i32 @ntest9(i32 %x) {
; CHECK-LABEL: ntest9:
; CHECK:       // %bb.0:
; CHECK-NEXT:    add w8, w0, w0, lsl #3
; CHECK-NEXT:    neg w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest9:
; GISEL:       // %bb.0:
; GISEL-NEXT:    add w8, w0, w0, lsl #3
; GISEL-NEXT:    neg w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -9
  ret i32 %mul
}

define i32 @ntest10(i32 %x) {
; CHECK-LABEL: ntest10:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #-10 // =0xfffffff6
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest10:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-10 // =0xfffffff6
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -10
  ret i32 %mul
}

define i32 @ntest11(i32 %x) {
; CHECK-LABEL: ntest11:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #-11 // =0xfffffff5
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest11:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-11 // =0xfffffff5
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -11
  ret i32 %mul
}

define i32 @ntest12(i32 %x) {
; CHECK-LABEL: ntest12:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #2
; CHECK-NEXT:    sub w0, w8, w0, lsl #4
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest12:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-12 // =0xfffffff4
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -12
  ret i32 %mul
}

define i32 @ntest13(i32 %x) {
; CHECK-LABEL: ntest13:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #-13 // =0xfffffff3
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest13:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-13 // =0xfffffff3
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret
  %mul = mul nsw i32 %x, -13
  ret i32 %mul
}

define i32 @ntest14(i32 %x) {
; CHECK-LABEL: ntest14:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #1
; CHECK-NEXT:    sub w0, w8, w0, lsl #4
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest14:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-14 // =0xfffffff2
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -14
  ret i32 %mul
}

define i32 @ntest15(i32 %x) {
; CHECK-LABEL: ntest15:
; CHECK:       // %bb.0:
; CHECK-NEXT:    sub w0, w0, w0, lsl #4
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest15:
; GISEL:       // %bb.0:
; GISEL-NEXT:    sub w0, w0, w0, lsl #4
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -15
  ret i32 %mul
}

define i32 @ntest16(i32 %x) {
; CHECK-LABEL: ntest16:
; CHECK:       // %bb.0:
; CHECK-NEXT:    neg w0, w0, lsl #4
; CHECK-NEXT:    ret
;
; GISEL-LABEL: ntest16:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-16 // =0xfffffff0
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret

  %mul = mul nsw i32 %x, -16
  ret i32 %mul
}

define i32 @muladd_demand(i32 %x, i32 %y) {
; CHECK-LABEL: muladd_demand:
; CHECK:       // %bb.0:
; CHECK-NEXT:    sub w8, w1, w0, lsl #6
; CHECK-NEXT:    and w0, w8, #0x1ffc0
; CHECK-NEXT:    ret
;
; GISEL-LABEL: muladd_demand:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #131008 // =0x1ffc0
; GISEL-NEXT:    madd w8, w0, w8, w1
; GISEL-NEXT:    and w0, w8, #0x1ffc0
; GISEL-NEXT:    ret
  %m = mul i32 %x, 131008 ; 0x0001ffc0
  %a = add i32 %y, %m
  %r = and i32 %a, 131008
  ret i32 %r
}

define <4 x i32> @muladd_demand_commute(<4 x i32> %x, <4 x i32> %y) {
; CHECK-LABEL: muladd_demand_commute:
; CHECK:       // %bb.0:
; CHECK-NEXT:    shl v0.4s, v0.4s, #6
; CHECK-NEXT:    movi v2.4s, #1, msl #16
; CHECK-NEXT:    sub v0.4s, v1.4s, v0.4s
; CHECK-NEXT:    and v0.16b, v0.16b, v2.16b
; CHECK-NEXT:    ret
;
; GISEL-LABEL: muladd_demand_commute:
; GISEL:       // %bb.0:
; GISEL-NEXT:    adrp x8, .LCPI56_0
; GISEL-NEXT:    movi v3.4s, #1, msl #16
; GISEL-NEXT:    ldr q2, [x8, :lo12:.LCPI56_0]
; GISEL-NEXT:    mla v1.4s, v0.4s, v2.4s
; GISEL-NEXT:    and v0.16b, v1.16b, v3.16b
; GISEL-NEXT:    ret
  %m = mul <4 x i32> %x, <i32 131008, i32 131008, i32 131008, i32 131008>
  %a = add <4 x i32> %m, %y
  %r = and <4 x i32> %a, <i32 131071, i32 131071, i32 131071, i32 131071>
  ret <4 x i32> %r
}

; Transforming `(mul x, -(2^(N-M) - 1) * 2^M)` to `(sub (shl x, M), (shl x, N))`
; will cause overflow when N is 32 and M is 31.
define i32 @shift_overflow(i32 %x) {
; CHECK-LABEL: shift_overflow:
; CHECK:       // %bb.0:
; CHECK-NEXT:    mov w8, #-2147483648 // =0x80000000
; CHECK-NEXT:    mul w0, w0, w8
; CHECK-NEXT:    ret
;
; GISEL-LABEL: shift_overflow:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #-2147483648 // =0x80000000
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret
  %const = bitcast i32 2147483648 to i32
  %r = mul i32 %x, %const
  ret i32 %r
}

; Transforming `(mul x, -(2^(N-M) - 1) * 2^M)` to `(sub (shl x, M), (shl x, N))`
; will not cause overflow when N is 31 and M is 30.
define i32 @shift_no_overflow(i32 %x) {
; CHECK-LABEL: shift_no_overflow:
; CHECK:       // %bb.0:
; CHECK-NEXT:    lsl w8, w0, #31
; CHECK-NEXT:    sub w0, w8, w0, lsl #30
; CHECK-NEXT:    ret
;
; GISEL-LABEL: shift_no_overflow:
; GISEL:       // %bb.0:
; GISEL-NEXT:    mov w8, #1073741824 // =0x40000000
; GISEL-NEXT:    mul w0, w0, w8
; GISEL-NEXT:    ret
  %const = bitcast i32 1073741824 to i32
  %r = mul i32 %x, %const
  ret i32 %r
}