// Copyright 2025 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Divisibility checks (x%c == 0 or x%c != 0) convert to multiply, rotate, compare.
// The opt pass rewrote x%c to x-(x/c)*c
// and then also rewrote x-(x/c)*c == 0 to x == (x/c)*c.
// If x/c is being used for a division already (div.Uses != 1)
// then we leave the expression alone.
//
// See ../magic.go for a detailed description of these algorithms.
// See test/codegen/divmod.go for tests.
// See divmod.rules for other division rules that run after these.

// Divisiblity by unsigned or signed power of two.
(Eq(8|16|32|64)  x (Mul(8|16|32|64) <t> (Div(8|16|32|64)u x (Const(8|16|32|64) [c])) (Const(8|16|32|64) [c])))
  && x.Op != ssaop.OpConst64 && ssa.IsPowerOfTwo(c) =>
  (Eq(8|16|32|64)  (And(8|16|32|64) <t> x (Const(8|16|32|64) <t> [c-1])) (Const(8|16|32|64) <t> [0]))
(Eq(8|16|32|64)  x (Mul(8|16|32|64) <t> (Div(8|16|32|64)  x (Const(8|16|32|64) [c])) (Const(8|16|32|64) [c])))
  && x.Op != ssaop.OpConst64 && ssa.IsPowerOfTwo(c) =>
  (Eq(8|16|32|64)  (And(8|16|32|64) <t> x (Const(8|16|32|64) <t> [c-1])) (Const(8|16|32|64) <t> [0]))
(Neq(8|16|32|64) x (Mul(8|16|32|64) <t> (Div(8|16|32|64)u x (Const(8|16|32|64) [c])) (Const(8|16|32|64) [c])))
  && x.Op != ssaop.OpConst64 && ssa.IsPowerOfTwo(c) =>
  (Neq(8|16|32|64) (And(8|16|32|64) <t> x (Const(8|16|32|64) <t> [c-1])) (Const(8|16|32|64) <t> [0]))
(Neq(8|16|32|64) x (Mul(8|16|32|64) <t> (Div(8|16|32|64)  x (Const(8|16|32|64) [c])) (Const(8|16|32|64) [c])))
  && x.Op != ssaop.OpConst64 && ssa.IsPowerOfTwo(c) =>
  (Neq(8|16|32|64) (And(8|16|32|64) <t> x (Const(8|16|32|64) <t> [c-1])) (Const(8|16|32|64) <t> [0]))

// Divisiblity by unsigned.
(Eq8 x (Mul8 <t> div:(Div8u x (Const8 [c])) (Const8 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst8 && ssa.UdivisibleOK8(c) =>
  (Leq8U
    (RotateLeft8 <t>
      (Mul8 <t> x (Const8 <t> [int8(udivisible8(c).M)]))
      (Const8 <t> [int8(8 - udivisible8(c).K)]))
    (Const8 <t> [int8(udivisible8(c).Max)]))
(Neq8 x (Mul8 <t> div:(Div8u x (Const8 [c])) (Const8 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst8 && ssa.UdivisibleOK8(c) =>
  (Less8U
    (Const8 <t> [int8(udivisible8(c).Max)])
    (RotateLeft8 <t>
      (Mul8 <t> x (Const8 <t> [int8(udivisible8(c).M)]))
      (Const8 <t> [int8(8 - udivisible8(c).K)])))
(Eq16 x (Mul16 <t> div:(Div16u x (Const16 [c])) (Const16 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst16 && ssa.UdivisibleOK16(c) =>
  (Leq16U
    (RotateLeft16 <t>
      (Mul16 <t> x (Const16 <t> [int16(udivisible16(c).M)]))
      (Const16 <t> [int16(16 - udivisible16(c).K)]))
    (Const16 <t> [int16(udivisible16(c).Max)]))
(Neq16 x (Mul16 <t> div:(Div16u x (Const16 [c])) (Const16 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst16 && ssa.UdivisibleOK16(c) =>
  (Less16U
    (Const16 <t> [int16(udivisible16(c).Max)])
    (RotateLeft16 <t>
      (Mul16 <t> x (Const16 <t> [int16(udivisible16(c).M)]))
      (Const16 <t> [int16(16 - udivisible16(c).K)])))
(Eq32 x (Mul32 <t> div:(Div32u x (Const32 [c])) (Const32 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst32 && udivisibleOK32(c) =>
  (Leq32U
    (RotateLeft32 <t>
      (Mul32 <t> x (Const32 <t> [int32(udivisible32(c).M)]))
      (Const32 <t> [int32(32 - udivisible32(c).K)]))
    (Const32 <t> [int32(udivisible32(c).Max)]))
(Neq32 x (Mul32 <t> div:(Div32u x (Const32 [c])) (Const32 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst32 && udivisibleOK32(c) =>
  (Less32U
    (Const32 <t> [int32(udivisible32(c).Max)])
    (RotateLeft32 <t>
      (Mul32 <t> x (Const32 <t> [int32(udivisible32(c).M)]))
      (Const32 <t> [int32(32 - udivisible32(c).K)])))
(Eq64 x (Mul64 <t> div:(Div64u x (Const64 [c])) (Const64 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst64 && udivisibleOK64(c) =>
  (Leq64U
    (RotateLeft64 <t>
      (Mul64 <t> x (Const64 <t> [int64(udivisible64(c).M)]))
      (Const64 <t> [int64(64 - udivisible64(c).K)]))
    (Const64 <t> [int64(udivisible64(c).Max)]))
(Neq64 x (Mul64 <t> div:(Div64u x (Const64 [c])) (Const64 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst64 && udivisibleOK64(c) =>
  (Less64U
    (Const64 <t> [int64(udivisible64(c).Max)])
    (RotateLeft64 <t>
      (Mul64 <t> x (Const64 <t> [int64(udivisible64(c).M)]))
      (Const64 <t> [int64(64 - udivisible64(c).K)])))

// Divisiblity by signed.
(Eq8 x (Mul8 <t> div:(Div8  x (Const8 [c])) (Const8 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst8 && ssa.SdivisibleOK8(c) =>
  (Leq8U
    (RotateLeft8 <t>
      (Add8 <t> (Mul8 <t> x (Const8 <t> [int8(sdivisible8(c).M)]))
        (Const8 <t> [int8(sdivisible8(c).A)]))
      (Const8 <t> [int8(8 - sdivisible8(c).K)]))
    (Const8 <t> [int8(sdivisible8(c).Max)]))
(Neq8 x (Mul8 <t> div:(Div8  x (Const8 [c])) (Const8 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst8 && ssa.SdivisibleOK8(c) =>
  (Less8U
    (Const8 <t> [int8(sdivisible8(c).Max)])
    (RotateLeft8 <t>
      (Add8 <t> (Mul8 <t> x (Const8 <t> [int8(sdivisible8(c).M)]))
        (Const8 <t> [int8(sdivisible8(c).A)]))
      (Const8 <t> [int8(8 - sdivisible8(c).K)])))
(Eq16 x (Mul16 <t> div:(Div16 x (Const16 [c])) (Const16 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst16 && ssa.SdivisibleOK16(c) =>
  (Leq16U
    (RotateLeft16 <t>
      (Add16 <t> (Mul16 <t> x (Const16 <t> [int16(sdivisible16(c).M)]))
        (Const16 <t> [int16(sdivisible16(c).A)]))
      (Const16 <t> [int16(16 - sdivisible16(c).K)]))
    (Const16 <t> [int16(sdivisible16(c).Max)]))
(Neq16 x (Mul16 <t> div:(Div16 x (Const16 [c])) (Const16 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst16 && ssa.SdivisibleOK16(c) =>
  (Less16U
    (Const16 <t> [int16(sdivisible16(c).Max)])
    (RotateLeft16 <t>
      (Add16 <t> (Mul16 <t> x (Const16 <t> [int16(sdivisible16(c).M)]))
        (Const16 <t> [int16(sdivisible16(c).A)]))
      (Const16 <t> [int16(16 - sdivisible16(c).K)])))
(Eq32 x (Mul32 <t> div:(Div32 x (Const32 [c])) (Const32 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst32 && sdivisibleOK32(c) =>
  (Leq32U
    (RotateLeft32 <t>
      (Add32 <t> (Mul32 <t> x (Const32 <t> [int32(sdivisible32(c).M)]))
        (Const32 <t> [int32(sdivisible32(c).A)]))
      (Const32 <t> [int32(32 - sdivisible32(c).K)]))
    (Const32 <t> [int32(sdivisible32(c).Max)]))
(Neq32 x (Mul32 <t> div:(Div32 x (Const32 [c])) (Const32 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst32 && sdivisibleOK32(c) =>
  (Less32U
    (Const32 <t> [int32(sdivisible32(c).Max)])
    (RotateLeft32 <t>
      (Add32 <t> (Mul32 <t> x (Const32 <t> [int32(sdivisible32(c).M)]))
        (Const32 <t> [int32(sdivisible32(c).A)]))
      (Const32 <t> [int32(32 - sdivisible32(c).K)])))
(Eq64 x (Mul64 <t> div:(Div64 x (Const64 [c])) (Const64 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst64 && sdivisibleOK64(c) =>
  (Leq64U
    (RotateLeft64 <t>
      (Add64 <t> (Mul64 <t> x (Const64 <t> [int64(sdivisible64(c).M)]))
        (Const64 <t> [int64(sdivisible64(c).A)]))
      (Const64 <t> [int64(64 - sdivisible64(c).K)]))
    (Const64 <t> [int64(sdivisible64(c).Max)]))
(Neq64 x (Mul64 <t> div:(Div64 x (Const64 [c])) (Const64 [c])))
  && div.Uses == 1
  && x.Op != ssaop.OpConst64 && sdivisibleOK64(c) =>
  (Less64U
    (Const64 <t> [int64(sdivisible64(c).Max)])
    (RotateLeft64 <t>
      (Add64 <t> (Mul64 <t> x (Const64 <t> [int64(sdivisible64(c).M)]))
        (Const64 <t> [int64(sdivisible64(c).A)]))
      (Const64 <t> [int64(64 - sdivisible64(c).K)])))