1// Copyright 2025 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Divisibility checks (x%c == 0 or x%c != 0) convert to multiply, rotate, compare.
6// The opt pass rewrote x%c to x-(x/c)*c
7// and then also rewrote x-(x/c)*c == 0 to x == (x/c)*c.
8// If x/c is being used for a division already (div.Uses != 1)
9// then we leave the expression alone.
10//
11// See ../magic.go for a detailed description of these algorithms.
12// See test/codegen/divmod.go for tests.
13// See divmod.rules for other division rules that run after these.
14
15// Divisiblity by unsigned or signed power of two.
16(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])))
17 && x.Op != OpConst64 && isPowerOfTwo(c) =>
18 (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]))
19(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])))
20 && x.Op != OpConst64 && isPowerOfTwo(c) =>
21 (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]))
22(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])))
23 && x.Op != OpConst64 && isPowerOfTwo(c) =>
24 (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]))
25(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])))
26 && x.Op != OpConst64 && isPowerOfTwo(c) =>
27 (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]))
28
29// Divisiblity by unsigned.
30(Eq8 x (Mul8 <t> div:(Div8u x (Const8 [c])) (Const8 [c])))
31 && div.Uses == 1
32 && x.Op != OpConst8 && udivisibleOK8(c) =>
33 (Leq8U
34 (RotateLeft8 <t>
35 (Mul8 <t> x (Const8 <t> [int8(udivisible8(c).m)]))
36 (Const8 <t> [int8(8 - udivisible8(c).k)]))
37 (Const8 <t> [int8(udivisible8(c).max)]))
38(Neq8 x (Mul8 <t> div:(Div8u x (Const8 [c])) (Const8 [c])))
39 && div.Uses == 1
40 && x.Op != OpConst8 && udivisibleOK8(c) =>
41 (Less8U
42 (Const8 <t> [int8(udivisible8(c).max)])
43 (RotateLeft8 <t>
44 (Mul8 <t> x (Const8 <t> [int8(udivisible8(c).m)]))
45 (Const8 <t> [int8(8 - udivisible8(c).k)])))
46(Eq16 x (Mul16 <t> div:(Div16u x (Const16 [c])) (Const16 [c])))
47 && div.Uses == 1
48 && x.Op != OpConst16 && udivisibleOK16(c) =>
49 (Leq16U
50 (RotateLeft16 <t>
51 (Mul16 <t> x (Const16 <t> [int16(udivisible16(c).m)]))
52 (Const16 <t> [int16(16 - udivisible16(c).k)]))
53 (Const16 <t> [int16(udivisible16(c).max)]))
54(Neq16 x (Mul16 <t> div:(Div16u x (Const16 [c])) (Const16 [c])))
55 && div.Uses == 1
56 && x.Op != OpConst16 && udivisibleOK16(c) =>
57 (Less16U
58 (Const16 <t> [int16(udivisible16(c).max)])
59 (RotateLeft16 <t>
60 (Mul16 <t> x (Const16 <t> [int16(udivisible16(c).m)]))
61 (Const16 <t> [int16(16 - udivisible16(c).k)])))
62(Eq32 x (Mul32 <t> div:(Div32u x (Const32 [c])) (Const32 [c])))
63 && div.Uses == 1
64 && x.Op != OpConst32 && udivisibleOK32(c) =>
65 (Leq32U
66 (RotateLeft32 <t>
67 (Mul32 <t> x (Const32 <t> [int32(udivisible32(c).m)]))
68 (Const32 <t> [int32(32 - udivisible32(c).k)]))
69 (Const32 <t> [int32(udivisible32(c).max)]))
70(Neq32 x (Mul32 <t> div:(Div32u x (Const32 [c])) (Const32 [c])))
71 && div.Uses == 1
72 && x.Op != OpConst32 && udivisibleOK32(c) =>
73 (Less32U
74 (Const32 <t> [int32(udivisible32(c).max)])
75 (RotateLeft32 <t>
76 (Mul32 <t> x (Const32 <t> [int32(udivisible32(c).m)]))
77 (Const32 <t> [int32(32 - udivisible32(c).k)])))
78(Eq64 x (Mul64 <t> div:(Div64u x (Const64 [c])) (Const64 [c])))
79 && div.Uses == 1
80 && x.Op != OpConst64 && udivisibleOK64(c) =>
81 (Leq64U
82 (RotateLeft64 <t>
83 (Mul64 <t> x (Const64 <t> [int64(udivisible64(c).m)]))
84 (Const64 <t> [int64(64 - udivisible64(c).k)]))
85 (Const64 <t> [int64(udivisible64(c).max)]))
86(Neq64 x (Mul64 <t> div:(Div64u x (Const64 [c])) (Const64 [c])))
87 && div.Uses == 1
88 && x.Op != OpConst64 && udivisibleOK64(c) =>
89 (Less64U
90 (Const64 <t> [int64(udivisible64(c).max)])
91 (RotateLeft64 <t>
92 (Mul64 <t> x (Const64 <t> [int64(udivisible64(c).m)]))
93 (Const64 <t> [int64(64 - udivisible64(c).k)])))
94
95// Divisiblity by signed.
96(Eq8 x (Mul8 <t> div:(Div8 x (Const8 [c])) (Const8 [c])))
97 && div.Uses == 1
98 && x.Op != OpConst8 && sdivisibleOK8(c) =>
99 (Leq8U
100 (RotateLeft8 <t>
101 (Add8 <t> (Mul8 <t> x (Const8 <t> [int8(sdivisible8(c).m)]))
102 (Const8 <t> [int8(sdivisible8(c).a)]))
103 (Const8 <t> [int8(8 - sdivisible8(c).k)]))
104 (Const8 <t> [int8(sdivisible8(c).max)]))
105(Neq8 x (Mul8 <t> div:(Div8 x (Const8 [c])) (Const8 [c])))
106 && div.Uses == 1
107 && x.Op != OpConst8 && sdivisibleOK8(c) =>
108 (Less8U
109 (Const8 <t> [int8(sdivisible8(c).max)])
110 (RotateLeft8 <t>
111 (Add8 <t> (Mul8 <t> x (Const8 <t> [int8(sdivisible8(c).m)]))
112 (Const8 <t> [int8(sdivisible8(c).a)]))
113 (Const8 <t> [int8(8 - sdivisible8(c).k)])))
114(Eq16 x (Mul16 <t> div:(Div16 x (Const16 [c])) (Const16 [c])))
115 && div.Uses == 1
116 && x.Op != OpConst16 && sdivisibleOK16(c) =>
117 (Leq16U
118 (RotateLeft16 <t>
119 (Add16 <t> (Mul16 <t> x (Const16 <t> [int16(sdivisible16(c).m)]))
120 (Const16 <t> [int16(sdivisible16(c).a)]))
121 (Const16 <t> [int16(16 - sdivisible16(c).k)]))
122 (Const16 <t> [int16(sdivisible16(c).max)]))
123(Neq16 x (Mul16 <t> div:(Div16 x (Const16 [c])) (Const16 [c])))
124 && div.Uses == 1
125 && x.Op != OpConst16 && sdivisibleOK16(c) =>
126 (Less16U
127 (Const16 <t> [int16(sdivisible16(c).max)])
128 (RotateLeft16 <t>
129 (Add16 <t> (Mul16 <t> x (Const16 <t> [int16(sdivisible16(c).m)]))
130 (Const16 <t> [int16(sdivisible16(c).a)]))
131 (Const16 <t> [int16(16 - sdivisible16(c).k)])))
132(Eq32 x (Mul32 <t> div:(Div32 x (Const32 [c])) (Const32 [c])))
133 && div.Uses == 1
134 && x.Op != OpConst32 && sdivisibleOK32(c) =>
135 (Leq32U
136 (RotateLeft32 <t>
137 (Add32 <t> (Mul32 <t> x (Const32 <t> [int32(sdivisible32(c).m)]))
138 (Const32 <t> [int32(sdivisible32(c).a)]))
139 (Const32 <t> [int32(32 - sdivisible32(c).k)]))
140 (Const32 <t> [int32(sdivisible32(c).max)]))
141(Neq32 x (Mul32 <t> div:(Div32 x (Const32 [c])) (Const32 [c])))
142 && div.Uses == 1
143 && x.Op != OpConst32 && sdivisibleOK32(c) =>
144 (Less32U
145 (Const32 <t> [int32(sdivisible32(c).max)])
146 (RotateLeft32 <t>
147 (Add32 <t> (Mul32 <t> x (Const32 <t> [int32(sdivisible32(c).m)]))
148 (Const32 <t> [int32(sdivisible32(c).a)]))
149 (Const32 <t> [int32(32 - sdivisible32(c).k)])))
150(Eq64 x (Mul64 <t> div:(Div64 x (Const64 [c])) (Const64 [c])))
151 && div.Uses == 1
152 && x.Op != OpConst64 && sdivisibleOK64(c) =>
153 (Leq64U
154 (RotateLeft64 <t>
155 (Add64 <t> (Mul64 <t> x (Const64 <t> [int64(sdivisible64(c).m)]))
156 (Const64 <t> [int64(sdivisible64(c).a)]))
157 (Const64 <t> [int64(64 - sdivisible64(c).k)]))
158 (Const64 <t> [int64(sdivisible64(c).max)]))
159(Neq64 x (Mul64 <t> div:(Div64 x (Const64 [c])) (Const64 [c])))
160 && div.Uses == 1
161 && x.Op != OpConst64 && sdivisibleOK64(c) =>
162 (Less64U
163 (Const64 <t> [int64(sdivisible64(c).max)])
164 (RotateLeft64 <t>
165 (Add64 <t> (Mul64 <t> x (Const64 <t> [int64(sdivisible64(c).m)]))
166 (Const64 <t> [int64(sdivisible64(c).a)]))
167 (Const64 <t> [int64(64 - sdivisible64(c).k)])))
View as plain text