Text file src/pkg/cmd/compile/internal/ssa/gen/generic.rules
1 // Copyright 2015 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 // Simplifications that apply to all backend architectures. As an example, this
6 // Go source code
7 //
8 // y := 0 * x
9 //
10 // can be translated into y := 0 without losing any information, which saves a
11 // pointless multiplication instruction. Other .rules files in this directory
12 // (for example AMD64.rules) contain rules specific to the architecture in the
13 // filename. The rules here apply to every architecture.
14 //
15 // The code for parsing this file lives in rulegen.go; this file generates
16 // ssa/rewritegeneric.go.
17
18 // values are specified using the following format:
19 // (op <type> [auxint] {aux} arg0 arg1 ...)
20 // the type, aux, and auxint fields are optional
21 // on the matching side
22 // - the type, aux, and auxint fields must match if they are specified.
23 // - the first occurrence of a variable defines that variable. Subsequent
24 // uses must match (be == to) the first use.
25 // - v is defined to be the value matched.
26 // - an additional conditional can be provided after the match pattern with "&&".
27 // on the generated side
28 // - the type of the top-level expression is the same as the one on the left-hand side.
29 // - the type of any subexpressions must be specified explicitly (or
30 // be specified in the op's type field).
31 // - auxint will be 0 if not specified.
32 // - aux will be nil if not specified.
33
34 // blocks are specified using the following format:
35 // (kind controlvalue succ0 succ1 ...)
36 // controlvalue must be "nil" or a value expression
37 // succ* fields must be variables
38 // For now, the generated successors must be a permutation of the matched successors.
39
40 // constant folding
41 (Trunc16to8 (Const16 [c])) -> (Const8 [int64(int8(c))])
42 (Trunc32to8 (Const32 [c])) -> (Const8 [int64(int8(c))])
43 (Trunc32to16 (Const32 [c])) -> (Const16 [int64(int16(c))])
44 (Trunc64to8 (Const64 [c])) -> (Const8 [int64(int8(c))])
45 (Trunc64to16 (Const64 [c])) -> (Const16 [int64(int16(c))])
46 (Trunc64to32 (Const64 [c])) -> (Const32 [int64(int32(c))])
47 (Cvt64Fto32F (Const64F [c])) -> (Const32F [auxFrom32F(float32(auxTo64F(c)))])
48 (Cvt32Fto64F (Const32F [c])) -> (Const64F [c]) // c is already a 64 bit float
49 (Cvt32to32F (Const32 [c])) -> (Const32F [auxFrom32F(float32(int32(c)))])
50 (Cvt32to64F (Const32 [c])) -> (Const64F [auxFrom64F(float64(int32(c)))])
51 (Cvt64to32F (Const64 [c])) -> (Const32F [auxFrom32F(float32(c))])
52 (Cvt64to64F (Const64 [c])) -> (Const64F [auxFrom64F(float64(c))])
53 (Cvt32Fto32 (Const32F [c])) -> (Const32 [int64(int32(auxTo32F(c)))])
54 (Cvt32Fto64 (Const32F [c])) -> (Const64 [int64(auxTo32F(c))])
55 (Cvt64Fto32 (Const64F [c])) -> (Const32 [int64(int32(auxTo64F(c)))])
56 (Cvt64Fto64 (Const64F [c])) -> (Const64 [int64(auxTo64F(c))])
57 (Round32F x:(Const32F)) -> x
58 (Round64F x:(Const64F)) -> x
59
60 (Trunc16to8 (ZeroExt8to16 x)) -> x
61 (Trunc32to8 (ZeroExt8to32 x)) -> x
62 (Trunc32to16 (ZeroExt8to32 x)) -> (ZeroExt8to16 x)
63 (Trunc32to16 (ZeroExt16to32 x)) -> x
64 (Trunc64to8 (ZeroExt8to64 x)) -> x
65 (Trunc64to16 (ZeroExt8to64 x)) -> (ZeroExt8to16 x)
66 (Trunc64to16 (ZeroExt16to64 x)) -> x
67 (Trunc64to32 (ZeroExt8to64 x)) -> (ZeroExt8to32 x)
68 (Trunc64to32 (ZeroExt16to64 x)) -> (ZeroExt16to32 x)
69 (Trunc64to32 (ZeroExt32to64 x)) -> x
70 (Trunc16to8 (SignExt8to16 x)) -> x
71 (Trunc32to8 (SignExt8to32 x)) -> x
72 (Trunc32to16 (SignExt8to32 x)) -> (SignExt8to16 x)
73 (Trunc32to16 (SignExt16to32 x)) -> x
74 (Trunc64to8 (SignExt8to64 x)) -> x
75 (Trunc64to16 (SignExt8to64 x)) -> (SignExt8to16 x)
76 (Trunc64to16 (SignExt16to64 x)) -> x
77 (Trunc64to32 (SignExt8to64 x)) -> (SignExt8to32 x)
78 (Trunc64to32 (SignExt16to64 x)) -> (SignExt16to32 x)
79 (Trunc64to32 (SignExt32to64 x)) -> x
80
81 (ZeroExt8to16 (Const8 [c])) -> (Const16 [int64( uint8(c))])
82 (ZeroExt8to32 (Const8 [c])) -> (Const32 [int64( uint8(c))])
83 (ZeroExt8to64 (Const8 [c])) -> (Const64 [int64( uint8(c))])
84 (ZeroExt16to32 (Const16 [c])) -> (Const32 [int64(uint16(c))])
85 (ZeroExt16to64 (Const16 [c])) -> (Const64 [int64(uint16(c))])
86 (ZeroExt32to64 (Const32 [c])) -> (Const64 [int64(uint32(c))])
87 (SignExt8to16 (Const8 [c])) -> (Const16 [int64( int8(c))])
88 (SignExt8to32 (Const8 [c])) -> (Const32 [int64( int8(c))])
89 (SignExt8to64 (Const8 [c])) -> (Const64 [int64( int8(c))])
90 (SignExt16to32 (Const16 [c])) -> (Const32 [int64( int16(c))])
91 (SignExt16to64 (Const16 [c])) -> (Const64 [int64( int16(c))])
92 (SignExt32to64 (Const32 [c])) -> (Const64 [int64( int32(c))])
93
94 (Neg8 (Const8 [c])) -> (Const8 [int64( -int8(c))])
95 (Neg16 (Const16 [c])) -> (Const16 [int64(-int16(c))])
96 (Neg32 (Const32 [c])) -> (Const32 [int64(-int32(c))])
97 (Neg64 (Const64 [c])) -> (Const64 [-c])
98 (Neg32F (Const32F [c])) && auxTo32F(c) != 0 -> (Const32F [auxFrom32F(-auxTo32F(c))])
99 (Neg64F (Const64F [c])) && auxTo64F(c) != 0 -> (Const64F [auxFrom64F(-auxTo64F(c))])
100
101 (Add8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c+d))])
102 (Add16 (Const16 [c]) (Const16 [d])) -> (Const16 [int64(int16(c+d))])
103 (Add32 (Const32 [c]) (Const32 [d])) -> (Const32 [int64(int32(c+d))])
104 (Add64 (Const64 [c]) (Const64 [d])) -> (Const64 [c+d])
105 (Add32F (Const32F [c]) (Const32F [d])) -> (Const32F [auxFrom32F(auxTo32F(c) + auxTo32F(d))])
106 (Add64F (Const64F [c]) (Const64F [d])) -> (Const64F [auxFrom64F(auxTo64F(c) + auxTo64F(d))])
107 (AddPtr <t> x (Const64 [c])) -> (OffPtr <t> x [c])
108 (AddPtr <t> x (Const32 [c])) -> (OffPtr <t> x [c])
109
110 (Sub8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c-d))])
111 (Sub16 (Const16 [c]) (Const16 [d])) -> (Const16 [int64(int16(c-d))])
112 (Sub32 (Const32 [c]) (Const32 [d])) -> (Const32 [int64(int32(c-d))])
113 (Sub64 (Const64 [c]) (Const64 [d])) -> (Const64 [c-d])
114 (Sub32F (Const32F [c]) (Const32F [d])) -> (Const32F [auxFrom32F(auxTo32F(c) - auxTo32F(d))])
115 (Sub64F (Const64F [c]) (Const64F [d])) -> (Const64F [auxFrom64F(auxTo64F(c) - auxTo64F(d))])
116
117 (Mul8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c*d))])
118 (Mul16 (Const16 [c]) (Const16 [d])) -> (Const16 [int64(int16(c*d))])
119 (Mul32 (Const32 [c]) (Const32 [d])) -> (Const32 [int64(int32(c*d))])
120 (Mul64 (Const64 [c]) (Const64 [d])) -> (Const64 [c*d])
121 (Mul32F (Const32F [c]) (Const32F [d])) -> (Const32F [auxFrom32F(auxTo32F(c) * auxTo32F(d))])
122 (Mul64F (Const64F [c]) (Const64F [d])) -> (Const64F [auxFrom64F(auxTo64F(c) * auxTo64F(d))])
123
124 (And8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c&d))])
125 (And16 (Const16 [c]) (Const16 [d])) -> (Const16 [int64(int16(c&d))])
126 (And32 (Const32 [c]) (Const32 [d])) -> (Const32 [int64(int32(c&d))])
127 (And64 (Const64 [c]) (Const64 [d])) -> (Const64 [c&d])
128
129 (Or8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c|d))])
130 (Or16 (Const16 [c]) (Const16 [d])) -> (Const16 [int64(int16(c|d))])
131 (Or32 (Const32 [c]) (Const32 [d])) -> (Const32 [int64(int32(c|d))])
132 (Or64 (Const64 [c]) (Const64 [d])) -> (Const64 [c|d])
133
134 (Xor8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c^d))])
135 (Xor16 (Const16 [c]) (Const16 [d])) -> (Const16 [int64(int16(c^d))])
136 (Xor32 (Const32 [c]) (Const32 [d])) -> (Const32 [int64(int32(c^d))])
137 (Xor64 (Const64 [c]) (Const64 [d])) -> (Const64 [c^d])
138
139 (Div8 (Const8 [c]) (Const8 [d])) && d != 0 -> (Const8 [int64(int8(c)/int8(d))])
140 (Div16 (Const16 [c]) (Const16 [d])) && d != 0 -> (Const16 [int64(int16(c)/int16(d))])
141 (Div32 (Const32 [c]) (Const32 [d])) && d != 0 -> (Const32 [int64(int32(c)/int32(d))])
142 (Div64 (Const64 [c]) (Const64 [d])) && d != 0 -> (Const64 [c/d])
143 (Div8u (Const8 [c]) (Const8 [d])) && d != 0 -> (Const8 [int64(int8(uint8(c)/uint8(d)))])
144 (Div16u (Const16 [c]) (Const16 [d])) && d != 0 -> (Const16 [int64(int16(uint16(c)/uint16(d)))])
145 (Div32u (Const32 [c]) (Const32 [d])) && d != 0 -> (Const32 [int64(int32(uint32(c)/uint32(d)))])
146 (Div64u (Const64 [c]) (Const64 [d])) && d != 0 -> (Const64 [int64(uint64(c)/uint64(d))])
147 (Div32F (Const32F [c]) (Const32F [d])) -> (Const32F [auxFrom32F(auxTo32F(c) / auxTo32F(d))])
148 (Div64F (Const64F [c]) (Const64F [d])) -> (Const64F [auxFrom64F(auxTo64F(c) / auxTo64F(d))])
149 (Select0 (Div128u (Const64 [0]) lo y)) -> (Div64u lo y)
150 (Select1 (Div128u (Const64 [0]) lo y)) -> (Mod64u lo y)
151
152 (Not (ConstBool [c])) -> (ConstBool [1-c])
153
154 // Convert x * 1 to x.
155 (Mul(8|16|32|64) (Const(8|16|32|64) [1]) x) -> x
156
157 // Convert x * -1 to -x.
158 (Mul(8|16|32|64) (Const(8|16|32|64) [-1]) x) -> (Neg(8|16|32|64) x)
159
160 // Convert multiplication by a power of two to a shift.
161 (Mul8 <t> n (Const8 [c])) && isPowerOfTwo(c) -> (Lsh8x64 <t> n (Const64 <typ.UInt64> [log2(c)]))
162 (Mul16 <t> n (Const16 [c])) && isPowerOfTwo(c) -> (Lsh16x64 <t> n (Const64 <typ.UInt64> [log2(c)]))
163 (Mul32 <t> n (Const32 [c])) && isPowerOfTwo(c) -> (Lsh32x64 <t> n (Const64 <typ.UInt64> [log2(c)]))
164 (Mul64 <t> n (Const64 [c])) && isPowerOfTwo(c) -> (Lsh64x64 <t> n (Const64 <typ.UInt64> [log2(c)]))
165 (Mul8 <t> n (Const8 [c])) && t.IsSigned() && isPowerOfTwo(-c) -> (Neg8 (Lsh8x64 <t> n (Const64 <typ.UInt64> [log2(-c)])))
166 (Mul16 <t> n (Const16 [c])) && t.IsSigned() && isPowerOfTwo(-c) -> (Neg16 (Lsh16x64 <t> n (Const64 <typ.UInt64> [log2(-c)])))
167 (Mul32 <t> n (Const32 [c])) && t.IsSigned() && isPowerOfTwo(-c) -> (Neg32 (Lsh32x64 <t> n (Const64 <typ.UInt64> [log2(-c)])))
168 (Mul64 <t> n (Const64 [c])) && t.IsSigned() && isPowerOfTwo(-c) -> (Neg64 (Lsh64x64 <t> n (Const64 <typ.UInt64> [log2(-c)])))
169
170 (Mod8 (Const8 [c]) (Const8 [d])) && d != 0 -> (Const8 [int64(int8(c % d))])
171 (Mod16 (Const16 [c]) (Const16 [d])) && d != 0 -> (Const16 [int64(int16(c % d))])
172 (Mod32 (Const32 [c]) (Const32 [d])) && d != 0 -> (Const32 [int64(int32(c % d))])
173 (Mod64 (Const64 [c]) (Const64 [d])) && d != 0 -> (Const64 [c % d])
174
175 (Mod8u (Const8 [c]) (Const8 [d])) && d != 0 -> (Const8 [int64(uint8(c) % uint8(d))])
176 (Mod16u (Const16 [c]) (Const16 [d])) && d != 0 -> (Const16 [int64(uint16(c) % uint16(d))])
177 (Mod32u (Const32 [c]) (Const32 [d])) && d != 0 -> (Const32 [int64(uint32(c) % uint32(d))])
178 (Mod64u (Const64 [c]) (Const64 [d])) && d != 0 -> (Const64 [int64(uint64(c) % uint64(d))])
179
180 (Lsh64x64 (Const64 [c]) (Const64 [d])) -> (Const64 [c << uint64(d)])
181 (Rsh64x64 (Const64 [c]) (Const64 [d])) -> (Const64 [c >> uint64(d)])
182 (Rsh64Ux64 (Const64 [c]) (Const64 [d])) -> (Const64 [int64(uint64(c) >> uint64(d))])
183 (Lsh32x64 (Const32 [c]) (Const64 [d])) -> (Const32 [int64(int32(c) << uint64(d))])
184 (Rsh32x64 (Const32 [c]) (Const64 [d])) -> (Const32 [int64(int32(c) >> uint64(d))])
185 (Rsh32Ux64 (Const32 [c]) (Const64 [d])) -> (Const32 [int64(int32(uint32(c) >> uint64(d)))])
186 (Lsh16x64 (Const16 [c]) (Const64 [d])) -> (Const16 [int64(int16(c) << uint64(d))])
187 (Rsh16x64 (Const16 [c]) (Const64 [d])) -> (Const16 [int64(int16(c) >> uint64(d))])
188 (Rsh16Ux64 (Const16 [c]) (Const64 [d])) -> (Const16 [int64(int16(uint16(c) >> uint64(d)))])
189 (Lsh8x64 (Const8 [c]) (Const64 [d])) -> (Const8 [int64(int8(c) << uint64(d))])
190 (Rsh8x64 (Const8 [c]) (Const64 [d])) -> (Const8 [int64(int8(c) >> uint64(d))])
191 (Rsh8Ux64 (Const8 [c]) (Const64 [d])) -> (Const8 [int64(int8(uint8(c) >> uint64(d)))])
192
193 // Fold IsInBounds when the range of the index cannot exceed the limit.
194 (IsInBounds (ZeroExt8to32 _) (Const32 [c])) && (1 << 8) <= c -> (ConstBool [1])
195 (IsInBounds (ZeroExt8to64 _) (Const64 [c])) && (1 << 8) <= c -> (ConstBool [1])
196 (IsInBounds (ZeroExt16to32 _) (Const32 [c])) && (1 << 16) <= c -> (ConstBool [1])
197 (IsInBounds (ZeroExt16to64 _) (Const64 [c])) && (1 << 16) <= c -> (ConstBool [1])
198 (IsInBounds x x) -> (ConstBool [0])
199 (IsInBounds (And8 (Const8 [c]) _) (Const8 [d])) && 0 <= c && c < d -> (ConstBool [1])
200 (IsInBounds (ZeroExt8to16 (And8 (Const8 [c]) _)) (Const16 [d])) && 0 <= c && c < d -> (ConstBool [1])
201 (IsInBounds (ZeroExt8to32 (And8 (Const8 [c]) _)) (Const32 [d])) && 0 <= c && c < d -> (ConstBool [1])
202 (IsInBounds (ZeroExt8to64 (And8 (Const8 [c]) _)) (Const64 [d])) && 0 <= c && c < d -> (ConstBool [1])
203 (IsInBounds (And16 (Const16 [c]) _) (Const16 [d])) && 0 <= c && c < d -> (ConstBool [1])
204 (IsInBounds (ZeroExt16to32 (And16 (Const16 [c]) _)) (Const32 [d])) && 0 <= c && c < d -> (ConstBool [1])
205 (IsInBounds (ZeroExt16to64 (And16 (Const16 [c]) _)) (Const64 [d])) && 0 <= c && c < d -> (ConstBool [1])
206 (IsInBounds (And32 (Const32 [c]) _) (Const32 [d])) && 0 <= c && c < d -> (ConstBool [1])
207 (IsInBounds (ZeroExt32to64 (And32 (Const32 [c]) _)) (Const64 [d])) && 0 <= c && c < d -> (ConstBool [1])
208 (IsInBounds (And64 (Const64 [c]) _) (Const64 [d])) && 0 <= c && c < d -> (ConstBool [1])
209 (IsInBounds (Const32 [c]) (Const32 [d])) -> (ConstBool [b2i(0 <= c && c < d)])
210 (IsInBounds (Const64 [c]) (Const64 [d])) -> (ConstBool [b2i(0 <= c && c < d)])
211 // (Mod64u x y) is always between 0 (inclusive) and y (exclusive).
212 (IsInBounds (Mod32u _ y) y) -> (ConstBool [1])
213 (IsInBounds (Mod64u _ y) y) -> (ConstBool [1])
214 // Right shifting an unsigned number limits its value.
215 (IsInBounds (ZeroExt8to64 (Rsh8Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 8 && 1<<uint( 8-c)-1 < d -> (ConstBool [1])
216 (IsInBounds (ZeroExt8to32 (Rsh8Ux64 _ (Const64 [c]))) (Const32 [d])) && 0 < c && c < 8 && 1<<uint( 8-c)-1 < d -> (ConstBool [1])
217 (IsInBounds (ZeroExt8to16 (Rsh8Ux64 _ (Const64 [c]))) (Const16 [d])) && 0 < c && c < 8 && 1<<uint( 8-c)-1 < d -> (ConstBool [1])
218 (IsInBounds (Rsh8Ux64 _ (Const64 [c])) (Const64 [d])) && 0 < c && c < 8 && 1<<uint( 8-c)-1 < d -> (ConstBool [1])
219 (IsInBounds (ZeroExt16to64 (Rsh16Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 16 && 1<<uint(16-c)-1 < d -> (ConstBool [1])
220 (IsInBounds (ZeroExt16to32 (Rsh16Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 16 && 1<<uint(16-c)-1 < d -> (ConstBool [1])
221 (IsInBounds (Rsh16Ux64 _ (Const64 [c])) (Const64 [d])) && 0 < c && c < 16 && 1<<uint(16-c)-1 < d -> (ConstBool [1])
222 (IsInBounds (ZeroExt32to64 (Rsh32Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 32 && 1<<uint(32-c)-1 < d -> (ConstBool [1])
223 (IsInBounds (Rsh32Ux64 _ (Const64 [c])) (Const64 [d])) && 0 < c && c < 32 && 1<<uint(32-c)-1 < d -> (ConstBool [1])
224 (IsInBounds (Rsh64Ux64 _ (Const64 [c])) (Const64 [d])) && 0 < c && c < 64 && 1<<uint(64-c)-1 < d -> (ConstBool [1])
225
226 (IsSliceInBounds x x) -> (ConstBool [1])
227 (IsSliceInBounds (And32 (Const32 [c]) _) (Const32 [d])) && 0 <= c && c <= d -> (ConstBool [1])
228 (IsSliceInBounds (And64 (Const64 [c]) _) (Const64 [d])) && 0 <= c && c <= d -> (ConstBool [1])
229 (IsSliceInBounds (Const32 [0]) _) -> (ConstBool [1])
230 (IsSliceInBounds (Const64 [0]) _) -> (ConstBool [1])
231 (IsSliceInBounds (Const32 [c]) (Const32 [d])) -> (ConstBool [b2i(0 <= c && c <= d)])
232 (IsSliceInBounds (Const64 [c]) (Const64 [d])) -> (ConstBool [b2i(0 <= c && c <= d)])
233 (IsSliceInBounds (SliceLen x) (SliceCap x)) -> (ConstBool [1])
234
235 (Eq(64|32|16|8) x x) -> (ConstBool [1])
236 (EqB (ConstBool [c]) (ConstBool [d])) -> (ConstBool [b2i(c == d)])
237 (EqB (ConstBool [0]) x) -> (Not x)
238 (EqB (ConstBool [1]) x) -> x
239
240 (Neq(64|32|16|8) x x) -> (ConstBool [0])
241 (NeqB (ConstBool [c]) (ConstBool [d])) -> (ConstBool [b2i(c != d)])
242 (NeqB (ConstBool [0]) x) -> x
243 (NeqB (ConstBool [1]) x) -> (Not x)
244 (NeqB (Not x) (Not y)) -> (NeqB x y)
245
246 (Eq64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) -> (Eq64 (Const64 <t> [c-d]) x)
247 (Eq32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) -> (Eq32 (Const32 <t> [int64(int32(c-d))]) x)
248 (Eq16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) -> (Eq16 (Const16 <t> [int64(int16(c-d))]) x)
249 (Eq8 (Const8 <t> [c]) (Add8 (Const8 <t> [d]) x)) -> (Eq8 (Const8 <t> [int64(int8(c-d))]) x)
250
251 (Neq64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) -> (Neq64 (Const64 <t> [c-d]) x)
252 (Neq32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) -> (Neq32 (Const32 <t> [int64(int32(c-d))]) x)
253 (Neq16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) -> (Neq16 (Const16 <t> [int64(int16(c-d))]) x)
254 (Neq8 (Const8 <t> [c]) (Add8 (Const8 <t> [d]) x)) -> (Neq8 (Const8 <t> [int64(int8(c-d))]) x)
255
256 // Canonicalize x-const to x+(-const)
257 (Sub64 x (Const64 <t> [c])) && x.Op != OpConst64 -> (Add64 (Const64 <t> [-c]) x)
258 (Sub32 x (Const32 <t> [c])) && x.Op != OpConst32 -> (Add32 (Const32 <t> [int64(int32(-c))]) x)
259 (Sub16 x (Const16 <t> [c])) && x.Op != OpConst16 -> (Add16 (Const16 <t> [int64(int16(-c))]) x)
260 (Sub8 x (Const8 <t> [c])) && x.Op != OpConst8 -> (Add8 (Const8 <t> [int64(int8(-c))]) x)
261
262 // fold negation into comparison operators
263 (Not (Eq(64|32|16|8|B) x y)) -> (Neq(64|32|16|8|B) x y)
264 (Not (Neq(64|32|16|8|B) x y)) -> (Eq(64|32|16|8|B) x y)
265
266 (Not (Greater(64|32|16|8) x y)) -> (Leq(64|32|16|8) x y)
267 (Not (Greater(64|32|16|8)U x y)) -> (Leq(64|32|16|8)U x y)
268 (Not (Geq(64|32|16|8) x y)) -> (Less(64|32|16|8) x y)
269 (Not (Geq(64|32|16|8)U x y)) -> (Less(64|32|16|8)U x y)
270
271 (Not (Less(64|32|16|8) x y)) -> (Geq(64|32|16|8) x y)
272 (Not (Less(64|32|16|8)U x y)) -> (Geq(64|32|16|8)U x y)
273 (Not (Leq(64|32|16|8) x y)) -> (Greater(64|32|16|8) x y)
274 (Not (Leq(64|32|16|8)U x y)) -> (Greater(64|32|16|8)U x y)
275
276
277 // Distribute multiplication c * (d+x) -> c*d + c*x. Useful for:
278 // a[i].b = ...; a[i+1].b = ...
279 (Mul64 (Const64 <t> [c]) (Add64 <t> (Const64 <t> [d]) x)) ->
280 (Add64 (Const64 <t> [c*d]) (Mul64 <t> (Const64 <t> [c]) x))
281 (Mul32 (Const32 <t> [c]) (Add32 <t> (Const32 <t> [d]) x)) ->
282 (Add32 (Const32 <t> [int64(int32(c*d))]) (Mul32 <t> (Const32 <t> [c]) x))
283
284 // Rewrite x*y ± x*z to x*(y±z)
285 (Add(64|32|16|8) <t> (Mul(64|32|16|8) x y) (Mul(64|32|16|8) x z))
286 -> (Mul(64|32|16|8) x (Add(64|32|16|8) <t> y z))
287 (Sub(64|32|16|8) <t> (Mul(64|32|16|8) x y) (Mul(64|32|16|8) x z))
288 -> (Mul(64|32|16|8) x (Sub(64|32|16|8) <t> y z))
289
290 // rewrite shifts of 8/16/32 bit consts into 64 bit consts to reduce
291 // the number of the other rewrite rules for const shifts
292 (Lsh64x32 <t> x (Const32 [c])) -> (Lsh64x64 x (Const64 <t> [int64(uint32(c))]))
293 (Lsh64x16 <t> x (Const16 [c])) -> (Lsh64x64 x (Const64 <t> [int64(uint16(c))]))
294 (Lsh64x8 <t> x (Const8 [c])) -> (Lsh64x64 x (Const64 <t> [int64(uint8(c))]))
295 (Rsh64x32 <t> x (Const32 [c])) -> (Rsh64x64 x (Const64 <t> [int64(uint32(c))]))
296 (Rsh64x16 <t> x (Const16 [c])) -> (Rsh64x64 x (Const64 <t> [int64(uint16(c))]))
297 (Rsh64x8 <t> x (Const8 [c])) -> (Rsh64x64 x (Const64 <t> [int64(uint8(c))]))
298 (Rsh64Ux32 <t> x (Const32 [c])) -> (Rsh64Ux64 x (Const64 <t> [int64(uint32(c))]))
299 (Rsh64Ux16 <t> x (Const16 [c])) -> (Rsh64Ux64 x (Const64 <t> [int64(uint16(c))]))
300 (Rsh64Ux8 <t> x (Const8 [c])) -> (Rsh64Ux64 x (Const64 <t> [int64(uint8(c))]))
301
302 (Lsh32x32 <t> x (Const32 [c])) -> (Lsh32x64 x (Const64 <t> [int64(uint32(c))]))
303 (Lsh32x16 <t> x (Const16 [c])) -> (Lsh32x64 x (Const64 <t> [int64(uint16(c))]))
304 (Lsh32x8 <t> x (Const8 [c])) -> (Lsh32x64 x (Const64 <t> [int64(uint8(c))]))
305 (Rsh32x32 <t> x (Const32 [c])) -> (Rsh32x64 x (Const64 <t> [int64(uint32(c))]))
306 (Rsh32x16 <t> x (Const16 [c])) -> (Rsh32x64 x (Const64 <t> [int64(uint16(c))]))
307 (Rsh32x8 <t> x (Const8 [c])) -> (Rsh32x64 x (Const64 <t> [int64(uint8(c))]))
308 (Rsh32Ux32 <t> x (Const32 [c])) -> (Rsh32Ux64 x (Const64 <t> [int64(uint32(c))]))
309 (Rsh32Ux16 <t> x (Const16 [c])) -> (Rsh32Ux64 x (Const64 <t> [int64(uint16(c))]))
310 (Rsh32Ux8 <t> x (Const8 [c])) -> (Rsh32Ux64 x (Const64 <t> [int64(uint8(c))]))
311
312 (Lsh16x32 <t> x (Const32 [c])) -> (Lsh16x64 x (Const64 <t> [int64(uint32(c))]))
313 (Lsh16x16 <t> x (Const16 [c])) -> (Lsh16x64 x (Const64 <t> [int64(uint16(c))]))
314 (Lsh16x8 <t> x (Const8 [c])) -> (Lsh16x64 x (Const64 <t> [int64(uint8(c))]))
315 (Rsh16x32 <t> x (Const32 [c])) -> (Rsh16x64 x (Const64 <t> [int64(uint32(c))]))
316 (Rsh16x16 <t> x (Const16 [c])) -> (Rsh16x64 x (Const64 <t> [int64(uint16(c))]))
317 (Rsh16x8 <t> x (Const8 [c])) -> (Rsh16x64 x (Const64 <t> [int64(uint8(c))]))
318 (Rsh16Ux32 <t> x (Const32 [c])) -> (Rsh16Ux64 x (Const64 <t> [int64(uint32(c))]))
319 (Rsh16Ux16 <t> x (Const16 [c])) -> (Rsh16Ux64 x (Const64 <t> [int64(uint16(c))]))
320 (Rsh16Ux8 <t> x (Const8 [c])) -> (Rsh16Ux64 x (Const64 <t> [int64(uint8(c))]))
321
322 (Lsh8x32 <t> x (Const32 [c])) -> (Lsh8x64 x (Const64 <t> [int64(uint32(c))]))
323 (Lsh8x16 <t> x (Const16 [c])) -> (Lsh8x64 x (Const64 <t> [int64(uint16(c))]))
324 (Lsh8x8 <t> x (Const8 [c])) -> (Lsh8x64 x (Const64 <t> [int64(uint8(c))]))
325 (Rsh8x32 <t> x (Const32 [c])) -> (Rsh8x64 x (Const64 <t> [int64(uint32(c))]))
326 (Rsh8x16 <t> x (Const16 [c])) -> (Rsh8x64 x (Const64 <t> [int64(uint16(c))]))
327 (Rsh8x8 <t> x (Const8 [c])) -> (Rsh8x64 x (Const64 <t> [int64(uint8(c))]))
328 (Rsh8Ux32 <t> x (Const32 [c])) -> (Rsh8Ux64 x (Const64 <t> [int64(uint32(c))]))
329 (Rsh8Ux16 <t> x (Const16 [c])) -> (Rsh8Ux64 x (Const64 <t> [int64(uint16(c))]))
330 (Rsh8Ux8 <t> x (Const8 [c])) -> (Rsh8Ux64 x (Const64 <t> [int64(uint8(c))]))
331
332 // shifts by zero
333 (Lsh(64|32|16|8)x64 x (Const64 [0])) -> x
334 (Rsh(64|32|16|8)x64 x (Const64 [0])) -> x
335 (Rsh(64|32|16|8)Ux64 x (Const64 [0])) -> x
336
337 // rotates by multiples of register width
338 (RotateLeft64 x (Const64 [c])) && c%64 == 0 -> x
339 (RotateLeft32 x (Const32 [c])) && c%32 == 0 -> x
340 (RotateLeft16 x (Const16 [c])) && c%16 == 0 -> x
341 (RotateLeft8 x (Const8 [c])) && c%8 == 0 -> x
342
343 // zero shifted
344 (Lsh64x(64|32|16|8) (Const64 [0]) _) -> (Const64 [0])
345 (Rsh64x(64|32|16|8) (Const64 [0]) _) -> (Const64 [0])
346 (Rsh64Ux(64|32|16|8) (Const64 [0]) _) -> (Const64 [0])
347 (Lsh32x(64|32|16|8) (Const32 [0]) _) -> (Const32 [0])
348 (Rsh32x(64|32|16|8) (Const32 [0]) _) -> (Const32 [0])
349 (Rsh32Ux(64|32|16|8) (Const32 [0]) _) -> (Const32 [0])
350 (Lsh16x(64|32|16|8) (Const16 [0]) _) -> (Const16 [0])
351 (Rsh16x(64|32|16|8) (Const16 [0]) _) -> (Const16 [0])
352 (Rsh16Ux(64|32|16|8) (Const16 [0]) _) -> (Const16 [0])
353 (Lsh8x(64|32|16|8) (Const8 [0]) _) -> (Const8 [0])
354 (Rsh8x(64|32|16|8) (Const8 [0]) _) -> (Const8 [0])
355 (Rsh8Ux(64|32|16|8) (Const8 [0]) _) -> (Const8 [0])
356
357 // large left shifts of all values, and right shifts of unsigned values
358 ((Lsh64|Rsh64U)x64 _ (Const64 [c])) && uint64(c) >= 64 -> (Const64 [0])
359 ((Lsh32|Rsh32U)x64 _ (Const64 [c])) && uint64(c) >= 32 -> (Const32 [0])
360 ((Lsh16|Rsh16U)x64 _ (Const64 [c])) && uint64(c) >= 16 -> (Const16 [0])
361 ((Lsh8|Rsh8U)x64 _ (Const64 [c])) && uint64(c) >= 8 -> (Const8 [0])
362
363 // combine const shifts
364 (Lsh64x64 <t> (Lsh64x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Lsh64x64 x (Const64 <t> [c+d]))
365 (Lsh32x64 <t> (Lsh32x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Lsh32x64 x (Const64 <t> [c+d]))
366 (Lsh16x64 <t> (Lsh16x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Lsh16x64 x (Const64 <t> [c+d]))
367 (Lsh8x64 <t> (Lsh8x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Lsh8x64 x (Const64 <t> [c+d]))
368
369 (Rsh64x64 <t> (Rsh64x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh64x64 x (Const64 <t> [c+d]))
370 (Rsh32x64 <t> (Rsh32x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh32x64 x (Const64 <t> [c+d]))
371 (Rsh16x64 <t> (Rsh16x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh16x64 x (Const64 <t> [c+d]))
372 (Rsh8x64 <t> (Rsh8x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh8x64 x (Const64 <t> [c+d]))
373
374 (Rsh64Ux64 <t> (Rsh64Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh64Ux64 x (Const64 <t> [c+d]))
375 (Rsh32Ux64 <t> (Rsh32Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh32Ux64 x (Const64 <t> [c+d]))
376 (Rsh16Ux64 <t> (Rsh16Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh16Ux64 x (Const64 <t> [c+d]))
377 (Rsh8Ux64 <t> (Rsh8Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) -> (Rsh8Ux64 x (Const64 <t> [c+d]))
378
379 // Remove signed right shift before an unsigned right shift that extracts the sign bit.
380 (Rsh8Ux64 (Rsh8x64 x _) (Const64 <t> [7] )) -> (Rsh8Ux64 x (Const64 <t> [7] ))
381 (Rsh16Ux64 (Rsh16x64 x _) (Const64 <t> [15])) -> (Rsh16Ux64 x (Const64 <t> [15]))
382 (Rsh32Ux64 (Rsh32x64 x _) (Const64 <t> [31])) -> (Rsh32Ux64 x (Const64 <t> [31]))
383 (Rsh64Ux64 (Rsh64x64 x _) (Const64 <t> [63])) -> (Rsh64Ux64 x (Const64 <t> [63]))
384
385 // ((x >> c1) << c2) >> c3
386 (Rsh(64|32|16|8)Ux64 (Lsh(64|32|16|8)x64 (Rsh(64|32|16|8)Ux64 x (Const64 [c1])) (Const64 [c2])) (Const64 [c3]))
387 && uint64(c1) >= uint64(c2) && uint64(c3) >= uint64(c2) && !uaddOvf(c1-c2, c3)
388 -> (Rsh(64|32|16|8)Ux64 x (Const64 <typ.UInt64> [c1-c2+c3]))
389
390 // ((x << c1) >> c2) << c3
391 (Lsh(64|32|16|8)x64 (Rsh(64|32|16|8)Ux64 (Lsh(64|32|16|8)x64 x (Const64 [c1])) (Const64 [c2])) (Const64 [c3]))
392 && uint64(c1) >= uint64(c2) && uint64(c3) >= uint64(c2) && !uaddOvf(c1-c2, c3)
393 -> (Lsh(64|32|16|8)x64 x (Const64 <typ.UInt64> [c1-c2+c3]))
394
395 // (x >> c) & uppermask = 0
396 (And64 (Const64 [m]) (Rsh64Ux64 _ (Const64 [c]))) && c >= 64-ntz(m) -> (Const64 [0])
397 (And32 (Const32 [m]) (Rsh32Ux64 _ (Const64 [c]))) && c >= 64-ntz(m) -> (Const32 [0])
398 (And16 (Const16 [m]) (Rsh16Ux64 _ (Const64 [c]))) && c >= 64-ntz(m) -> (Const16 [0])
399 (And8 (Const8 [m]) (Rsh8Ux64 _ (Const64 [c]))) && c >= 64-ntz(m) -> (Const8 [0])
400
401 // (x << c) & lowermask = 0
402 (And64 (Const64 [m]) (Lsh64x64 _ (Const64 [c]))) && c >= 64-nlz(m) -> (Const64 [0])
403 (And32 (Const32 [m]) (Lsh32x64 _ (Const64 [c]))) && c >= 64-nlz(m) -> (Const32 [0])
404 (And16 (Const16 [m]) (Lsh16x64 _ (Const64 [c]))) && c >= 64-nlz(m) -> (Const16 [0])
405 (And8 (Const8 [m]) (Lsh8x64 _ (Const64 [c]))) && c >= 64-nlz(m) -> (Const8 [0])
406
407 // replace shifts with zero extensions
408 (Rsh16Ux64 (Lsh16x64 x (Const64 [8])) (Const64 [8])) -> (ZeroExt8to16 (Trunc16to8 <typ.UInt8> x))
409 (Rsh32Ux64 (Lsh32x64 x (Const64 [24])) (Const64 [24])) -> (ZeroExt8to32 (Trunc32to8 <typ.UInt8> x))
410 (Rsh64Ux64 (Lsh64x64 x (Const64 [56])) (Const64 [56])) -> (ZeroExt8to64 (Trunc64to8 <typ.UInt8> x))
411 (Rsh32Ux64 (Lsh32x64 x (Const64 [16])) (Const64 [16])) -> (ZeroExt16to32 (Trunc32to16 <typ.UInt16> x))
412 (Rsh64Ux64 (Lsh64x64 x (Const64 [48])) (Const64 [48])) -> (ZeroExt16to64 (Trunc64to16 <typ.UInt16> x))
413 (Rsh64Ux64 (Lsh64x64 x (Const64 [32])) (Const64 [32])) -> (ZeroExt32to64 (Trunc64to32 <typ.UInt32> x))
414
415 // replace shifts with sign extensions
416 (Rsh16x64 (Lsh16x64 x (Const64 [8])) (Const64 [8])) -> (SignExt8to16 (Trunc16to8 <typ.Int8> x))
417 (Rsh32x64 (Lsh32x64 x (Const64 [24])) (Const64 [24])) -> (SignExt8to32 (Trunc32to8 <typ.Int8> x))
418 (Rsh64x64 (Lsh64x64 x (Const64 [56])) (Const64 [56])) -> (SignExt8to64 (Trunc64to8 <typ.Int8> x))
419 (Rsh32x64 (Lsh32x64 x (Const64 [16])) (Const64 [16])) -> (SignExt16to32 (Trunc32to16 <typ.Int16> x))
420 (Rsh64x64 (Lsh64x64 x (Const64 [48])) (Const64 [48])) -> (SignExt16to64 (Trunc64to16 <typ.Int16> x))
421 (Rsh64x64 (Lsh64x64 x (Const64 [32])) (Const64 [32])) -> (SignExt32to64 (Trunc64to32 <typ.Int32> x))
422
423 // constant comparisons
424 (Eq(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) -> (ConstBool [b2i(c == d)])
425 (Neq(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) -> (ConstBool [b2i(c != d)])
426 (Greater(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) -> (ConstBool [b2i(c > d)])
427 (Geq(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) -> (ConstBool [b2i(c >= d)])
428 (Less(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) -> (ConstBool [b2i(c < d)])
429 (Leq(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) -> (ConstBool [b2i(c <= d)])
430
431 (Geq8 (And8 _ (Const8 [c])) (Const8 [0])) && int8(c) >= 0 -> (ConstBool [1])
432 (Geq16 (And16 _ (Const16 [c])) (Const16 [0])) && int16(c) >= 0 -> (ConstBool [1])
433 (Geq32 (And32 _ (Const32 [c])) (Const32 [0])) && int32(c) >= 0 -> (ConstBool [1])
434 (Geq64 (And64 _ (Const64 [c])) (Const64 [0])) && int64(c) >= 0 -> (ConstBool [1])
435
436 (Geq64 (Rsh64Ux64 _ (Const64 [c])) (Const64 [0])) && c > 0 -> (ConstBool [1])
437
438 (Greater64U (Const64 [c]) (Const64 [d])) -> (ConstBool [b2i(uint64(c) > uint64(d))])
439 (Greater32U (Const32 [c]) (Const32 [d])) -> (ConstBool [b2i(uint32(c) > uint32(d))])
440 (Greater16U (Const16 [c]) (Const16 [d])) -> (ConstBool [b2i(uint16(c) > uint16(d))])
441 (Greater8U (Const8 [c]) (Const8 [d])) -> (ConstBool [b2i(uint8(c) > uint8(d))])
442
443 (Geq64U (Const64 [c]) (Const64 [d])) -> (ConstBool [b2i(uint64(c) >= uint64(d))])
444 (Geq32U (Const32 [c]) (Const32 [d])) -> (ConstBool [b2i(uint32(c) >= uint32(d))])
445 (Geq16U (Const16 [c]) (Const16 [d])) -> (ConstBool [b2i(uint16(c) >= uint16(d))])
446 (Geq8U (Const8 [c]) (Const8 [d])) -> (ConstBool [b2i(uint8(c) >= uint8(d))])
447
448 (Less64U (Const64 [c]) (Const64 [d])) -> (ConstBool [b2i(uint64(c) < uint64(d))])
449 (Less32U (Const32 [c]) (Const32 [d])) -> (ConstBool [b2i(uint32(c) < uint32(d))])
450 (Less16U (Const16 [c]) (Const16 [d])) -> (ConstBool [b2i(uint16(c) < uint16(d))])
451 (Less8U (Const8 [c]) (Const8 [d])) -> (ConstBool [b2i(uint8(c) < uint8(d))])
452
453 (Leq64U (Const64 [c]) (Const64 [d])) -> (ConstBool [b2i(uint64(c) <= uint64(d))])
454 (Leq32U (Const32 [c]) (Const32 [d])) -> (ConstBool [b2i(uint32(c) <= uint32(d))])
455 (Leq16U (Const16 [c]) (Const16 [d])) -> (ConstBool [b2i(uint16(c) <= uint16(d))])
456 (Leq8U (Const8 [c]) (Const8 [d])) -> (ConstBool [b2i(uint8(c) <= uint8(d))])
457
458 // constant floating point comparisons
459 (Eq32F (Const32F [c]) (Const32F [d])) -> (ConstBool [b2i(auxTo32F(c) == auxTo32F(d))])
460 (Eq64F (Const64F [c]) (Const64F [d])) -> (ConstBool [b2i(auxTo64F(c) == auxTo64F(d))])
461 (Neq32F (Const32F [c]) (Const32F [d])) -> (ConstBool [b2i(auxTo32F(c) != auxTo32F(d))])
462 (Neq64F (Const64F [c]) (Const64F [d])) -> (ConstBool [b2i(auxTo64F(c) != auxTo64F(d))])
463 (Greater32F (Const32F [c]) (Const32F [d])) -> (ConstBool [b2i(auxTo32F(c) > auxTo32F(d))])
464 (Greater64F (Const64F [c]) (Const64F [d])) -> (ConstBool [b2i(auxTo64F(c) > auxTo64F(d))])
465 (Geq32F (Const32F [c]) (Const32F [d])) -> (ConstBool [b2i(auxTo32F(c) >= auxTo32F(d))])
466 (Geq64F (Const64F [c]) (Const64F [d])) -> (ConstBool [b2i(auxTo64F(c) >= auxTo64F(d))])
467 (Less32F (Const32F [c]) (Const32F [d])) -> (ConstBool [b2i(auxTo32F(c) < auxTo32F(d))])
468 (Less64F (Const64F [c]) (Const64F [d])) -> (ConstBool [b2i(auxTo64F(c) < auxTo64F(d))])
469 (Leq32F (Const32F [c]) (Const32F [d])) -> (ConstBool [b2i(auxTo32F(c) <= auxTo32F(d))])
470 (Leq64F (Const64F [c]) (Const64F [d])) -> (ConstBool [b2i(auxTo64F(c) <= auxTo64F(d))])
471
472 // simplifications
473 (Or(64|32|16|8) x x) -> x
474 (Or(64|32|16|8) (Const(64|32|16|8) [0]) x) -> x
475 (Or(64|32|16|8) (Const(64|32|16|8) [-1]) _) -> (Const(64|32|16|8) [-1])
476
477 (And(64|32|16|8) x x) -> x
478 (And(64|32|16|8) (Const(64|32|16|8) [-1]) x) -> x
479 (And(64|32|16|8) (Const(64|32|16|8) [0]) _) -> (Const(64|32|16|8) [0])
480
481 (Xor(64|32|16|8) x x) -> (Const(64|32|16|8) [0])
482 (Xor(64|32|16|8) (Const(64|32|16|8) [0]) x) -> x
483
484 (Add(64|32|16|8) (Const(64|32|16|8) [0]) x) -> x
485 (Sub(64|32|16|8) x x) -> (Const(64|32|16|8) [0])
486 (Mul(64|32|16|8) (Const(64|32|16|8) [0]) _) -> (Const(64|32|16|8) [0])
487
488 (Com(64|32|16|8) (Com(64|32|16|8) x)) -> x
489 (Com(64|32|16|8) (Const(64|32|16|8) [c])) -> (Const(64|32|16|8) [^c])
490
491 (Neg(64|32|16|8) (Sub(64|32|16|8) x y)) -> (Sub(64|32|16|8) y x)
492
493 (Add(64|32|16|8) (Const(64|32|16|8) [1]) (Com(64|32|16|8) x)) -> (Neg(64|32|16|8) x)
494
495 (And(64|32|16|8) x (And(64|32|16|8) x y)) -> (And(64|32|16|8) x y)
496 (Or(64|32|16|8) x (Or(64|32|16|8) x y)) -> (Or(64|32|16|8) x y)
497 (Xor(64|32|16|8) x (Xor(64|32|16|8) x y)) -> y
498
499 // Ands clear bits. Ors set bits.
500 // If a subsequent Or will set all the bits
501 // that an And cleared, we can skip the And.
502 // This happens in bitmasking code like:
503 // x &^= 3 << shift // clear two old bits
504 // x |= v << shift // set two new bits
505 // when shift is a small constant and v ends up a constant 3.
506 (Or8 (And8 x (Const8 [c2])) (Const8 <t> [c1])) && ^(c1 | c2) == 0 -> (Or8 (Const8 <t> [c1]) x)
507 (Or16 (And16 x (Const16 [c2])) (Const16 <t> [c1])) && ^(c1 | c2) == 0 -> (Or16 (Const16 <t> [c1]) x)
508 (Or32 (And32 x (Const32 [c2])) (Const32 <t> [c1])) && ^(c1 | c2) == 0 -> (Or32 (Const32 <t> [c1]) x)
509 (Or64 (And64 x (Const64 [c2])) (Const64 <t> [c1])) && ^(c1 | c2) == 0 -> (Or64 (Const64 <t> [c1]) x)
510
511 (Trunc64to8 (And64 (Const64 [y]) x)) && y&0xFF == 0xFF -> (Trunc64to8 x)
512 (Trunc64to16 (And64 (Const64 [y]) x)) && y&0xFFFF == 0xFFFF -> (Trunc64to16 x)
513 (Trunc64to32 (And64 (Const64 [y]) x)) && y&0xFFFFFFFF == 0xFFFFFFFF -> (Trunc64to32 x)
514 (Trunc32to8 (And32 (Const32 [y]) x)) && y&0xFF == 0xFF -> (Trunc32to8 x)
515 (Trunc32to16 (And32 (Const32 [y]) x)) && y&0xFFFF == 0xFFFF -> (Trunc32to16 x)
516 (Trunc16to8 (And16 (Const16 [y]) x)) && y&0xFF == 0xFF -> (Trunc16to8 x)
517
518 (ZeroExt8to64 (Trunc64to8 x:(Rsh64Ux64 _ (Const64 [s])))) && s >= 56 -> x
519 (ZeroExt16to64 (Trunc64to16 x:(Rsh64Ux64 _ (Const64 [s])))) && s >= 48 -> x
520 (ZeroExt32to64 (Trunc64to32 x:(Rsh64Ux64 _ (Const64 [s])))) && s >= 32 -> x
521 (ZeroExt8to32 (Trunc32to8 x:(Rsh32Ux64 _ (Const64 [s])))) && s >= 24 -> x
522 (ZeroExt16to32 (Trunc32to16 x:(Rsh32Ux64 _ (Const64 [s])))) && s >= 16 -> x
523 (ZeroExt8to16 (Trunc16to8 x:(Rsh16Ux64 _ (Const64 [s])))) && s >= 8 -> x
524
525 (SignExt8to64 (Trunc64to8 x:(Rsh64x64 _ (Const64 [s])))) && s >= 56 -> x
526 (SignExt16to64 (Trunc64to16 x:(Rsh64x64 _ (Const64 [s])))) && s >= 48 -> x
527 (SignExt32to64 (Trunc64to32 x:(Rsh64x64 _ (Const64 [s])))) && s >= 32 -> x
528 (SignExt8to32 (Trunc32to8 x:(Rsh32x64 _ (Const64 [s])))) && s >= 24 -> x
529 (SignExt16to32 (Trunc32to16 x:(Rsh32x64 _ (Const64 [s])))) && s >= 16 -> x
530 (SignExt8to16 (Trunc16to8 x:(Rsh16x64 _ (Const64 [s])))) && s >= 8 -> x
531
532 (Slicemask (Const32 [x])) && x > 0 -> (Const32 [-1])
533 (Slicemask (Const32 [0])) -> (Const32 [0])
534 (Slicemask (Const64 [x])) && x > 0 -> (Const64 [-1])
535 (Slicemask (Const64 [0])) -> (Const64 [0])
536
537 // Rewrite AND of consts as shifts if possible, slightly faster for 64 bit operands
538 // leading zeros can be shifted left, then right
539 (And64 <t> (Const64 [y]) x) && nlz(y) + nto(y) == 64 && nto(y) >= 32
540 -> (Rsh64Ux64 (Lsh64x64 <t> x (Const64 <t> [nlz(y)])) (Const64 <t> [nlz(y)]))
541 // trailing zeros can be shifted right, then left
542 (And64 <t> (Const64 [y]) x) && nlo(y) + ntz(y) == 64 && ntz(y) >= 32
543 -> (Lsh64x64 (Rsh64Ux64 <t> x (Const64 <t> [ntz(y)])) (Const64 <t> [ntz(y)]))
544
545 // simplifications often used for lengths. e.g. len(s[i:i+5])==5
546 (Sub(64|32|16|8) (Add(64|32|16|8) x y) x) -> y
547 (Sub(64|32|16|8) (Add(64|32|16|8) x y) y) -> x
548
549 // basic phi simplifications
550 (Phi (Const8 [c]) (Const8 [c])) -> (Const8 [c])
551 (Phi (Const16 [c]) (Const16 [c])) -> (Const16 [c])
552 (Phi (Const32 [c]) (Const32 [c])) -> (Const32 [c])
553 (Phi (Const64 [c]) (Const64 [c])) -> (Const64 [c])
554
555 // slice and interface comparisons
556 // The frontend ensures that we can only compare against nil,
557 // so we need only compare the first word (interface type or slice ptr).
558 (EqInter x y) -> (EqPtr (ITab x) (ITab y))
559 (NeqInter x y) -> (NeqPtr (ITab x) (ITab y))
560 (EqSlice x y) -> (EqPtr (SlicePtr x) (SlicePtr y))
561 (NeqSlice x y) -> (NeqPtr (SlicePtr x) (SlicePtr y))
562
563 // Load of store of same address, with compatibly typed value and same size
564 (Load <t1> p1 (Store {t2} p2 x _))
565 && isSamePtr(p1, p2)
566 && t1.Compare(x.Type) == types.CMPeq
567 && t1.Size() == sizeof(t2)
568 -> x
569 (Load <t1> p1 (Store {t2} p2 _ (Store {t3} p3 x _)))
570 && isSamePtr(p1, p3)
571 && t1.Compare(x.Type) == types.CMPeq
572 && t1.Size() == sizeof(t2)
573 && disjoint(p3, sizeof(t3), p2, sizeof(t2))
574 -> x
575 (Load <t1> p1 (Store {t2} p2 _ (Store {t3} p3 _ (Store {t4} p4 x _))))
576 && isSamePtr(p1, p4)
577 && t1.Compare(x.Type) == types.CMPeq
578 && t1.Size() == sizeof(t2)
579 && disjoint(p4, sizeof(t4), p2, sizeof(t2))
580 && disjoint(p4, sizeof(t4), p3, sizeof(t3))
581 -> x
582 (Load <t1> p1 (Store {t2} p2 _ (Store {t3} p3 _ (Store {t4} p4 _ (Store {t5} p5 x _)))))
583 && isSamePtr(p1, p5)
584 && t1.Compare(x.Type) == types.CMPeq
585 && t1.Size() == sizeof(t2)
586 && disjoint(p5, sizeof(t5), p2, sizeof(t2))
587 && disjoint(p5, sizeof(t5), p3, sizeof(t3))
588 && disjoint(p5, sizeof(t5), p4, sizeof(t4))
589 -> x
590
591 // Pass constants through math.Float{32,64}bits and math.Float{32,64}frombits
592 (Load <t1> p1 (Store {t2} p2 (Const64 [x]) _)) && isSamePtr(p1,p2) && sizeof(t2) == 8 && is64BitFloat(t1) -> (Const64F [x])
593 (Load <t1> p1 (Store {t2} p2 (Const32 [x]) _)) && isSamePtr(p1,p2) && sizeof(t2) == 4 && is32BitFloat(t1) -> (Const32F [auxFrom32F(math.Float32frombits(uint32(x)))])
594 (Load <t1> p1 (Store {t2} p2 (Const64F [x]) _)) && isSamePtr(p1,p2) && sizeof(t2) == 8 && is64BitInt(t1) -> (Const64 [x])
595 (Load <t1> p1 (Store {t2} p2 (Const32F [x]) _)) && isSamePtr(p1,p2) && sizeof(t2) == 4 && is32BitInt(t1) -> (Const32 [int64(int32(math.Float32bits(auxTo32F(x))))])
596
597 // Float Loads up to Zeros so they can be constant folded.
598 (Load <t1> op:(OffPtr [o1] p1)
599 (Store {t2} p2 _
600 mem:(Zero [n] p3 _)))
601 && o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p3)
602 && fe.CanSSA(t1)
603 && disjoint(op, t1.Size(), p2, sizeof(t2))
604 -> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p3) mem)
605 (Load <t1> op:(OffPtr [o1] p1)
606 (Store {t2} p2 _
607 (Store {t3} p3 _
608 mem:(Zero [n] p4 _))))
609 && o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p4)
610 && fe.CanSSA(t1)
611 && disjoint(op, t1.Size(), p2, sizeof(t2))
612 && disjoint(op, t1.Size(), p3, sizeof(t3))
613 -> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p4) mem)
614 (Load <t1> op:(OffPtr [o1] p1)
615 (Store {t2} p2 _
616 (Store {t3} p3 _
617 (Store {t4} p4 _
618 mem:(Zero [n] p5 _)))))
619 && o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p5)
620 && fe.CanSSA(t1)
621 && disjoint(op, t1.Size(), p2, sizeof(t2))
622 && disjoint(op, t1.Size(), p3, sizeof(t3))
623 && disjoint(op, t1.Size(), p4, sizeof(t4))
624 -> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p5) mem)
625 (Load <t1> op:(OffPtr [o1] p1)
626 (Store {t2} p2 _
627 (Store {t3} p3 _
628 (Store {t4} p4 _
629 (Store {t5} p5 _
630 mem:(Zero [n] p6 _))))))
631 && o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p6)
632 && fe.CanSSA(t1)
633 && disjoint(op, t1.Size(), p2, sizeof(t2))
634 && disjoint(op, t1.Size(), p3, sizeof(t3))
635 && disjoint(op, t1.Size(), p4, sizeof(t4))
636 && disjoint(op, t1.Size(), p5, sizeof(t5))
637 -> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p6) mem)
638
639 // Zero to Load forwarding.
640 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
641 && t1.IsBoolean()
642 && isSamePtr(p1, p2)
643 && n >= o + 1
644 -> (ConstBool [0])
645 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
646 && is8BitInt(t1)
647 && isSamePtr(p1, p2)
648 && n >= o + 1
649 -> (Const8 [0])
650 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
651 && is16BitInt(t1)
652 && isSamePtr(p1, p2)
653 && n >= o + 2
654 -> (Const16 [0])
655 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
656 && is32BitInt(t1)
657 && isSamePtr(p1, p2)
658 && n >= o + 4
659 -> (Const32 [0])
660 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
661 && is64BitInt(t1)
662 && isSamePtr(p1, p2)
663 && n >= o + 8
664 -> (Const64 [0])
665 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
666 && is32BitFloat(t1)
667 && isSamePtr(p1, p2)
668 && n >= o + 4
669 -> (Const32F [0])
670 (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
671 && is64BitFloat(t1)
672 && isSamePtr(p1, p2)
673 && n >= o + 8
674 -> (Const64F [0])
675
676 // Eliminate stores of values that have just been loaded from the same location.
677 // We also handle the common case where there are some intermediate stores.
678 (Store {t1} p1 (Load <t2> p2 mem) mem)
679 && isSamePtr(p1, p2)
680 && t2.Size() == sizeof(t1)
681 -> mem
682 (Store {t1} p1 (Load <t2> p2 oldmem) mem:(Store {t3} p3 _ oldmem))
683 && isSamePtr(p1, p2)
684 && t2.Size() == sizeof(t1)
685 && disjoint(p1, sizeof(t1), p3, sizeof(t3))
686 -> mem
687 (Store {t1} p1 (Load <t2> p2 oldmem) mem:(Store {t3} p3 _ (Store {t4} p4 _ oldmem)))
688 && isSamePtr(p1, p2)
689 && t2.Size() == sizeof(t1)
690 && disjoint(p1, sizeof(t1), p3, sizeof(t3))
691 && disjoint(p1, sizeof(t1), p4, sizeof(t4))
692 -> mem
693 (Store {t1} p1 (Load <t2> p2 oldmem) mem:(Store {t3} p3 _ (Store {t4} p4 _ (Store {t5} p5 _ oldmem))))
694 && isSamePtr(p1, p2)
695 && t2.Size() == sizeof(t1)
696 && disjoint(p1, sizeof(t1), p3, sizeof(t3))
697 && disjoint(p1, sizeof(t1), p4, sizeof(t4))
698 && disjoint(p1, sizeof(t1), p5, sizeof(t5))
699 -> mem
700
701 // Don't Store zeros to cleared variables.
702 (Store {t} (OffPtr [o] p1) x mem:(Zero [n] p2 _))
703 && isConstZero(x)
704 && o >= 0 && sizeof(t) + o <= n && isSamePtr(p1, p2)
705 -> mem
706 (Store {t1} op:(OffPtr [o1] p1) x mem:(Store {t2} p2 _ (Zero [n] p3 _)))
707 && isConstZero(x)
708 && o1 >= 0 && sizeof(t1) + o1 <= n && isSamePtr(p1, p3)
709 && disjoint(op, sizeof(t1), p2, sizeof(t2))
710 -> mem
711 (Store {t1} op:(OffPtr [o1] p1) x mem:(Store {t2} p2 _ (Store {t3} p3 _ (Zero [n] p4 _))))
712 && isConstZero(x)
713 && o1 >= 0 && sizeof(t1) + o1 <= n && isSamePtr(p1, p4)
714 && disjoint(op, sizeof(t1), p2, sizeof(t2))
715 && disjoint(op, sizeof(t1), p3, sizeof(t3))
716 -> mem
717 (Store {t1} op:(OffPtr [o1] p1) x mem:(Store {t2} p2 _ (Store {t3} p3 _ (Store {t4} p4 _ (Zero [n] p5 _)))))
718 && isConstZero(x)
719 && o1 >= 0 && sizeof(t1) + o1 <= n && isSamePtr(p1, p5)
720 && disjoint(op, sizeof(t1), p2, sizeof(t2))
721 && disjoint(op, sizeof(t1), p3, sizeof(t3))
722 && disjoint(op, sizeof(t1), p4, sizeof(t4))
723 -> mem
724
725 // Collapse OffPtr
726 (OffPtr (OffPtr p [b]) [a]) -> (OffPtr p [a+b])
727 (OffPtr p [0]) && v.Type.Compare(p.Type) == types.CMPeq -> p
728
729 // indexing operations
730 // Note: bounds check has already been done
731 (PtrIndex <t> ptr idx) && config.PtrSize == 4 -> (AddPtr ptr (Mul32 <typ.Int> idx (Const32 <typ.Int> [t.Elem().Size()])))
732 (PtrIndex <t> ptr idx) && config.PtrSize == 8 -> (AddPtr ptr (Mul64 <typ.Int> idx (Const64 <typ.Int> [t.Elem().Size()])))
733
734 // struct operations
735 (StructSelect (StructMake1 x)) -> x
736 (StructSelect [0] (StructMake2 x _)) -> x
737 (StructSelect [1] (StructMake2 _ x)) -> x
738 (StructSelect [0] (StructMake3 x _ _)) -> x
739 (StructSelect [1] (StructMake3 _ x _)) -> x
740 (StructSelect [2] (StructMake3 _ _ x)) -> x
741 (StructSelect [0] (StructMake4 x _ _ _)) -> x
742 (StructSelect [1] (StructMake4 _ x _ _)) -> x
743 (StructSelect [2] (StructMake4 _ _ x _)) -> x
744 (StructSelect [3] (StructMake4 _ _ _ x)) -> x
745
746 (Load <t> _ _) && t.IsStruct() && t.NumFields() == 0 && fe.CanSSA(t) ->
747 (StructMake0)
748 (Load <t> ptr mem) && t.IsStruct() && t.NumFields() == 1 && fe.CanSSA(t) ->
749 (StructMake1
750 (Load <t.FieldType(0)> (OffPtr <t.FieldType(0).PtrTo()> [0] ptr) mem))
751 (Load <t> ptr mem) && t.IsStruct() && t.NumFields() == 2 && fe.CanSSA(t) ->
752 (StructMake2
753 (Load <t.FieldType(0)> (OffPtr <t.FieldType(0).PtrTo()> [0] ptr) mem)
754 (Load <t.FieldType(1)> (OffPtr <t.FieldType(1).PtrTo()> [t.FieldOff(1)] ptr) mem))
755 (Load <t> ptr mem) && t.IsStruct() && t.NumFields() == 3 && fe.CanSSA(t) ->
756 (StructMake3
757 (Load <t.FieldType(0)> (OffPtr <t.FieldType(0).PtrTo()> [0] ptr) mem)
758 (Load <t.FieldType(1)> (OffPtr <t.FieldType(1).PtrTo()> [t.FieldOff(1)] ptr) mem)
759 (Load <t.FieldType(2)> (OffPtr <t.FieldType(2).PtrTo()> [t.FieldOff(2)] ptr) mem))
760 (Load <t> ptr mem) && t.IsStruct() && t.NumFields() == 4 && fe.CanSSA(t) ->
761 (StructMake4
762 (Load <t.FieldType(0)> (OffPtr <t.FieldType(0).PtrTo()> [0] ptr) mem)
763 (Load <t.FieldType(1)> (OffPtr <t.FieldType(1).PtrTo()> [t.FieldOff(1)] ptr) mem)
764 (Load <t.FieldType(2)> (OffPtr <t.FieldType(2).PtrTo()> [t.FieldOff(2)] ptr) mem)
765 (Load <t.FieldType(3)> (OffPtr <t.FieldType(3).PtrTo()> [t.FieldOff(3)] ptr) mem))
766
767 (StructSelect [i] x:(Load <t> ptr mem)) && !fe.CanSSA(t) ->
768 @x.Block (Load <v.Type> (OffPtr <v.Type.PtrTo()> [t.FieldOff(int(i))] ptr) mem)
769
770 (Store _ (StructMake0) mem) -> mem
771 (Store dst (StructMake1 <t> f0) mem) ->
772 (Store {t.FieldType(0)} (OffPtr <t.FieldType(0).PtrTo()> [0] dst) f0 mem)
773 (Store dst (StructMake2 <t> f0 f1) mem) ->
774 (Store {t.FieldType(1)}
775 (OffPtr <t.FieldType(1).PtrTo()> [t.FieldOff(1)] dst)
776 f1
777 (Store {t.FieldType(0)}
778 (OffPtr <t.FieldType(0).PtrTo()> [0] dst)
779 f0 mem))
780 (Store dst (StructMake3 <t> f0 f1 f2) mem) ->
781 (Store {t.FieldType(2)}
782 (OffPtr <t.FieldType(2).PtrTo()> [t.FieldOff(2)] dst)
783 f2
784 (Store {t.FieldType(1)}
785 (OffPtr <t.FieldType(1).PtrTo()> [t.FieldOff(1)] dst)
786 f1
787 (Store {t.FieldType(0)}
788 (OffPtr <t.FieldType(0).PtrTo()> [0] dst)
789 f0 mem)))
790 (Store dst (StructMake4 <t> f0 f1 f2 f3) mem) ->
791 (Store {t.FieldType(3)}
792 (OffPtr <t.FieldType(3).PtrTo()> [t.FieldOff(3)] dst)
793 f3
794 (Store {t.FieldType(2)}
795 (OffPtr <t.FieldType(2).PtrTo()> [t.FieldOff(2)] dst)
796 f2
797 (Store {t.FieldType(1)}
798 (OffPtr <t.FieldType(1).PtrTo()> [t.FieldOff(1)] dst)
799 f1
800 (Store {t.FieldType(0)}
801 (OffPtr <t.FieldType(0).PtrTo()> [0] dst)
802 f0 mem))))
803
804 // Putting struct{*byte} and similar into direct interfaces.
805 (IMake typ (StructMake1 val)) -> (IMake typ val)
806 (StructSelect [0] x:(IData _)) -> x
807
808 // un-SSAable values use mem->mem copies
809 (Store {t} dst (Load src mem) mem) && !fe.CanSSA(t.(*types.Type)) ->
810 (Move {t} [sizeof(t)] dst src mem)
811 (Store {t} dst (Load src mem) (VarDef {x} mem)) && !fe.CanSSA(t.(*types.Type)) ->
812 (Move {t} [sizeof(t)] dst src (VarDef {x} mem))
813
814 // array ops
815 (ArraySelect (ArrayMake1 x)) -> x
816
817 (Load <t> _ _) && t.IsArray() && t.NumElem() == 0 ->
818 (ArrayMake0)
819
820 (Load <t> ptr mem) && t.IsArray() && t.NumElem() == 1 && fe.CanSSA(t) ->
821 (ArrayMake1 (Load <t.Elem()> ptr mem))
822
823 (Store _ (ArrayMake0) mem) -> mem
824 (Store dst (ArrayMake1 e) mem) -> (Store {e.Type} dst e mem)
825
826 // Putting [1]{*byte} and similar into direct interfaces.
827 (IMake typ (ArrayMake1 val)) -> (IMake typ val)
828 (ArraySelect [0] x:(IData _)) -> x
829
830 // string ops
831 // Decomposing StringMake and lowering of StringPtr and StringLen
832 // happens in a later pass, dec, so that these operations are available
833 // to other passes for optimizations.
834 (StringPtr (StringMake (Addr <t> {s} base) _)) -> (Addr <t> {s} base)
835 (StringLen (StringMake _ (Const64 <t> [c]))) -> (Const64 <t> [c])
836 (ConstString {s}) && config.PtrSize == 4 && s.(string) == "" ->
837 (StringMake (ConstNil) (Const32 <typ.Int> [0]))
838 (ConstString {s}) && config.PtrSize == 8 && s.(string) == "" ->
839 (StringMake (ConstNil) (Const64 <typ.Int> [0]))
840 (ConstString {s}) && config.PtrSize == 4 && s.(string) != "" ->
841 (StringMake
842 (Addr <typ.BytePtr> {fe.StringData(s.(string))}
843 (SB))
844 (Const32 <typ.Int> [int64(len(s.(string)))]))
845 (ConstString {s}) && config.PtrSize == 8 && s.(string) != "" ->
846 (StringMake
847 (Addr <typ.BytePtr> {fe.StringData(s.(string))}
848 (SB))
849 (Const64 <typ.Int> [int64(len(s.(string)))]))
850
851 // slice ops
852 // Only a few slice rules are provided here. See dec.rules for
853 // a more comprehensive set.
854 (SliceLen (SliceMake _ (Const64 <t> [c]) _)) -> (Const64 <t> [c])
855 (SliceCap (SliceMake _ _ (Const64 <t> [c]))) -> (Const64 <t> [c])
856 (SliceLen (SliceMake _ (Const32 <t> [c]) _)) -> (Const32 <t> [c])
857 (SliceCap (SliceMake _ _ (Const32 <t> [c]))) -> (Const32 <t> [c])
858 (SlicePtr (SliceMake (SlicePtr x) _ _)) -> (SlicePtr x)
859 (SliceLen (SliceMake _ (SliceLen x) _)) -> (SliceLen x)
860 (SliceCap (SliceMake _ _ (SliceCap x))) -> (SliceCap x)
861 (SliceCap (SliceMake _ _ (SliceLen x))) -> (SliceLen x)
862 (ConstSlice) && config.PtrSize == 4 ->
863 (SliceMake
864 (ConstNil <v.Type.Elem().PtrTo()>)
865 (Const32 <typ.Int> [0])
866 (Const32 <typ.Int> [0]))
867 (ConstSlice) && config.PtrSize == 8 ->
868 (SliceMake
869 (ConstNil <v.Type.Elem().PtrTo()>)
870 (Const64 <typ.Int> [0])
871 (Const64 <typ.Int> [0]))
872
873 // interface ops
874 (ConstInterface) ->
875 (IMake
876 (ConstNil <typ.Uintptr>)
877 (ConstNil <typ.BytePtr>))
878
879 (NilCheck (GetG mem) mem) -> mem
880
881 (If (Not cond) yes no) -> (If cond no yes)
882 (If (ConstBool [c]) yes no) && c == 1 -> (First nil yes no)
883 (If (ConstBool [c]) yes no) && c == 0 -> (First nil no yes)
884
885 // Get rid of Convert ops for pointer arithmetic on unsafe.Pointer.
886 (Convert (Add(64|32) (Convert ptr mem) off) mem) -> (Add(64|32) ptr off)
887 (Convert (Convert ptr mem) mem) -> ptr
888
889 // strength reduction of divide by a constant.
890 // See ../magic.go for a detailed description of these algorithms.
891
892 // Unsigned divide by power of 2. Strength reduce to a shift.
893 (Div8u n (Const8 [c])) && isPowerOfTwo(c&0xff) -> (Rsh8Ux64 n (Const64 <typ.UInt64> [log2(c&0xff)]))
894 (Div16u n (Const16 [c])) && isPowerOfTwo(c&0xffff) -> (Rsh16Ux64 n (Const64 <typ.UInt64> [log2(c&0xffff)]))
895 (Div32u n (Const32 [c])) && isPowerOfTwo(c&0xffffffff) -> (Rsh32Ux64 n (Const64 <typ.UInt64> [log2(c&0xffffffff)]))
896 (Div64u n (Const64 [c])) && isPowerOfTwo(c) -> (Rsh64Ux64 n (Const64 <typ.UInt64> [log2(c)]))
897 (Div64u n (Const64 [-1<<63])) -> (Rsh64Ux64 n (Const64 <typ.UInt64> [63]))
898
899 // Signed non-negative divide by power of 2.
900 (Div8 n (Const8 [c])) && isNonNegative(n) && isPowerOfTwo(c&0xff) -> (Rsh8Ux64 n (Const64 <typ.UInt64> [log2(c&0xff)]))
901 (Div16 n (Const16 [c])) && isNonNegative(n) && isPowerOfTwo(c&0xffff) -> (Rsh16Ux64 n (Const64 <typ.UInt64> [log2(c&0xffff)]))
902 (Div32 n (Const32 [c])) && isNonNegative(n) && isPowerOfTwo(c&0xffffffff) -> (Rsh32Ux64 n (Const64 <typ.UInt64> [log2(c&0xffffffff)]))
903 (Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c) -> (Rsh64Ux64 n (Const64 <typ.UInt64> [log2(c)]))
904 (Div64 n (Const64 [-1<<63])) && isNonNegative(n) -> (Const64 [0])
905
906 // Unsigned divide, not a power of 2. Strength reduce to a multiply.
907 // For 8-bit divides, we just do a direct 9-bit by 8-bit multiply.
908 (Div8u x (Const8 [c])) && umagicOK(8, c) ->
909 (Trunc32to8
910 (Rsh32Ux64 <typ.UInt32>
911 (Mul32 <typ.UInt32>
912 (Const32 <typ.UInt32> [int64(1<<8+umagic(8,c).m)])
913 (ZeroExt8to32 x))
914 (Const64 <typ.UInt64> [8+umagic(8,c).s])))
915
916 // For 16-bit divides on 64-bit machines, we do a direct 17-bit by 16-bit multiply.
917 (Div16u x (Const16 [c])) && umagicOK(16, c) && config.RegSize == 8 ->
918 (Trunc64to16
919 (Rsh64Ux64 <typ.UInt64>
920 (Mul64 <typ.UInt64>
921 (Const64 <typ.UInt64> [int64(1<<16+umagic(16,c).m)])
922 (ZeroExt16to64 x))
923 (Const64 <typ.UInt64> [16+umagic(16,c).s])))
924
925 // For 16-bit divides on 32-bit machines
926 (Div16u x (Const16 [c])) && umagicOK(16, c) && config.RegSize == 4 && umagic(16,c).m&1 == 0 ->
927 (Trunc32to16
928 (Rsh32Ux64 <typ.UInt32>
929 (Mul32 <typ.UInt32>
930 (Const32 <typ.UInt32> [int64(1<<15+umagic(16,c).m/2)])
931 (ZeroExt16to32 x))
932 (Const64 <typ.UInt64> [16+umagic(16,c).s-1])))
933 (Div16u x (Const16 [c])) && umagicOK(16, c) && config.RegSize == 4 && c&1 == 0 ->
934 (Trunc32to16
935 (Rsh32Ux64 <typ.UInt32>
936 (Mul32 <typ.UInt32>
937 (Const32 <typ.UInt32> [int64(1<<15+(umagic(16,c).m+1)/2)])
938 (Rsh32Ux64 <typ.UInt32> (ZeroExt16to32 x) (Const64 <typ.UInt64> [1])))
939 (Const64 <typ.UInt64> [16+umagic(16,c).s-2])))
940 (Div16u x (Const16 [c])) && umagicOK(16, c) && config.RegSize == 4 && config.useAvg ->
941 (Trunc32to16
942 (Rsh32Ux64 <typ.UInt32>
943 (Avg32u
944 (Lsh32x64 <typ.UInt32> (ZeroExt16to32 x) (Const64 <typ.UInt64> [16]))
945 (Mul32 <typ.UInt32>
946 (Const32 <typ.UInt32> [int64(umagic(16,c).m)])
947 (ZeroExt16to32 x)))
948 (Const64 <typ.UInt64> [16+umagic(16,c).s-1])))
949
950 // For 32-bit divides on 32-bit machines
951 (Div32u x (Const32 [c])) && umagicOK(32, c) && config.RegSize == 4 && umagic(32,c).m&1 == 0 && config.useHmul ->
952 (Rsh32Ux64 <typ.UInt32>
953 (Hmul32u <typ.UInt32>
954 (Const32 <typ.UInt32> [int64(int32(1<<31+umagic(32,c).m/2))])
955 x)
956 (Const64 <typ.UInt64> [umagic(32,c).s-1]))
957 (Div32u x (Const32 [c])) && umagicOK(32, c) && config.RegSize == 4 && c&1 == 0 && config.useHmul ->
958 (Rsh32Ux64 <typ.UInt32>
959 (Hmul32u <typ.UInt32>
960 (Const32 <typ.UInt32> [int64(int32(1<<31+(umagic(32,c).m+1)/2))])
961 (Rsh32Ux64 <typ.UInt32> x (Const64 <typ.UInt64> [1])))
962 (Const64 <typ.UInt64> [umagic(32,c).s-2]))
963 (Div32u x (Const32 [c])) && umagicOK(32, c) && config.RegSize == 4 && config.useAvg && config.useHmul ->
964 (Rsh32Ux64 <typ.UInt32>
965 (Avg32u
966 x
967 (Hmul32u <typ.UInt32>
968 (Const32 <typ.UInt32> [int64(int32(umagic(32,c).m))])
969 x))
970 (Const64 <typ.UInt64> [umagic(32,c).s-1]))
971
972 // For 32-bit divides on 64-bit machines
973 // We'll use a regular (non-hi) multiply for this case.
974 (Div32u x (Const32 [c])) && umagicOK(32, c) && config.RegSize == 8 && umagic(32,c).m&1 == 0 ->
975 (Trunc64to32
976 (Rsh64Ux64 <typ.UInt64>
977 (Mul64 <typ.UInt64>
978 (Const64 <typ.UInt64> [int64(1<<31+umagic(32,c).m/2)])
979 (ZeroExt32to64 x))
980 (Const64 <typ.UInt64> [32+umagic(32,c).s-1])))
981 (Div32u x (Const32 [c])) && umagicOK(32, c) && config.RegSize == 8 && c&1 == 0 ->
982 (Trunc64to32
983 (Rsh64Ux64 <typ.UInt64>
984 (Mul64 <typ.UInt64>
985 (Const64 <typ.UInt64> [int64(1<<31+(umagic(32,c).m+1)/2)])
986 (Rsh64Ux64 <typ.UInt64> (ZeroExt32to64 x) (Const64 <typ.UInt64> [1])))
987 (Const64 <typ.UInt64> [32+umagic(32,c).s-2])))
988 (Div32u x (Const32 [c])) && umagicOK(32, c) && config.RegSize == 8 && config.useAvg ->
989 (Trunc64to32
990 (Rsh64Ux64 <typ.UInt64>
991 (Avg64u
992 (Lsh64x64 <typ.UInt64> (ZeroExt32to64 x) (Const64 <typ.UInt64> [32]))
993 (Mul64 <typ.UInt64>
994 (Const64 <typ.UInt32> [int64(umagic(32,c).m)])
995 (ZeroExt32to64 x)))
996 (Const64 <typ.UInt64> [32+umagic(32,c).s-1])))
997
998 // For 64-bit divides on 64-bit machines
999 // (64-bit divides on 32-bit machines are lowered to a runtime call by the walk pass.)
1000 (Div64u x (Const64 [c])) && umagicOK(64, c) && config.RegSize == 8 && umagic(64,c).m&1 == 0 && config.useHmul ->
1001 (Rsh64Ux64 <typ.UInt64>
1002 (Hmul64u <typ.UInt64>
1003 (Const64 <typ.UInt64> [int64(1<<63+umagic(64,c).m/2)])
1004 x)
1005 (Const64 <typ.UInt64> [umagic(64,c).s-1]))
1006 (Div64u x (Const64 [c])) && umagicOK(64, c) && config.RegSize == 8 && c&1 == 0 && config.useHmul ->
1007 (Rsh64Ux64 <typ.UInt64>
1008 (Hmul64u <typ.UInt64>
1009 (Const64 <typ.UInt64> [int64(1<<63+(umagic(64,c).m+1)/2)])
1010 (Rsh64Ux64 <typ.UInt64> x (Const64 <typ.UInt64> [1])))
1011 (Const64 <typ.UInt64> [umagic(64,c).s-2]))
1012 (Div64u x (Const64 [c])) && umagicOK(64, c) && config.RegSize == 8 && config.useAvg && config.useHmul ->
1013 (Rsh64Ux64 <typ.UInt64>
1014 (Avg64u
1015 x
1016 (Hmul64u <typ.UInt64>
1017 (Const64 <typ.UInt64> [int64(umagic(64,c).m)])
1018 x))
1019 (Const64 <typ.UInt64> [umagic(64,c).s-1]))
1020
1021 // Signed divide by a negative constant. Rewrite to divide by a positive constant.
1022 (Div8 <t> n (Const8 [c])) && c < 0 && c != -1<<7 -> (Neg8 (Div8 <t> n (Const8 <t> [-c])))
1023 (Div16 <t> n (Const16 [c])) && c < 0 && c != -1<<15 -> (Neg16 (Div16 <t> n (Const16 <t> [-c])))
1024 (Div32 <t> n (Const32 [c])) && c < 0 && c != -1<<31 -> (Neg32 (Div32 <t> n (Const32 <t> [-c])))
1025 (Div64 <t> n (Const64 [c])) && c < 0 && c != -1<<63 -> (Neg64 (Div64 <t> n (Const64 <t> [-c])))
1026
1027 // Dividing by the most-negative number. Result is always 0 except
1028 // if the input is also the most-negative number.
1029 // We can detect that using the sign bit of x & -x.
1030 (Div8 <t> x (Const8 [-1<<7 ])) -> (Rsh8Ux64 (And8 <t> x (Neg8 <t> x)) (Const64 <typ.UInt64> [7 ]))
1031 (Div16 <t> x (Const16 [-1<<15])) -> (Rsh16Ux64 (And16 <t> x (Neg16 <t> x)) (Const64 <typ.UInt64> [15]))
1032 (Div32 <t> x (Const32 [-1<<31])) -> (Rsh32Ux64 (And32 <t> x (Neg32 <t> x)) (Const64 <typ.UInt64> [31]))
1033 (Div64 <t> x (Const64 [-1<<63])) -> (Rsh64Ux64 (And64 <t> x (Neg64 <t> x)) (Const64 <typ.UInt64> [63]))
1034
1035 // Signed divide by power of 2.
1036 // n / c = n >> log(c) if n >= 0
1037 // = (n+c-1) >> log(c) if n < 0
1038 // We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned).
1039 (Div8 <t> n (Const8 [c])) && isPowerOfTwo(c) ->
1040 (Rsh8x64
1041 (Add8 <t> n (Rsh8Ux64 <t> (Rsh8x64 <t> n (Const64 <typ.UInt64> [ 7])) (Const64 <typ.UInt64> [ 8-log2(c)])))
1042 (Const64 <typ.UInt64> [log2(c)]))
1043 (Div16 <t> n (Const16 [c])) && isPowerOfTwo(c) ->
1044 (Rsh16x64
1045 (Add16 <t> n (Rsh16Ux64 <t> (Rsh16x64 <t> n (Const64 <typ.UInt64> [15])) (Const64 <typ.UInt64> [16-log2(c)])))
1046 (Const64 <typ.UInt64> [log2(c)]))
1047 (Div32 <t> n (Const32 [c])) && isPowerOfTwo(c) ->
1048 (Rsh32x64
1049 (Add32 <t> n (Rsh32Ux64 <t> (Rsh32x64 <t> n (Const64 <typ.UInt64> [31])) (Const64 <typ.UInt64> [32-log2(c)])))
1050 (Const64 <typ.UInt64> [log2(c)]))
1051 (Div64 <t> n (Const64 [c])) && isPowerOfTwo(c) ->
1052 (Rsh64x64
1053 (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [64-log2(c)])))
1054 (Const64 <typ.UInt64> [log2(c)]))
1055
1056 // Signed divide, not a power of 2. Strength reduce to a multiply.
1057 (Div8 <t> x (Const8 [c])) && smagicOK(8,c) ->
1058 (Sub8 <t>
1059 (Rsh32x64 <t>
1060 (Mul32 <typ.UInt32>
1061 (Const32 <typ.UInt32> [int64(smagic(8,c).m)])
1062 (SignExt8to32 x))
1063 (Const64 <typ.UInt64> [8+smagic(8,c).s]))
1064 (Rsh32x64 <t>
1065 (SignExt8to32 x)
1066 (Const64 <typ.UInt64> [31])))
1067 (Div16 <t> x (Const16 [c])) && smagicOK(16,c) ->
1068 (Sub16 <t>
1069 (Rsh32x64 <t>
1070 (Mul32 <typ.UInt32>
1071 (Const32 <typ.UInt32> [int64(smagic(16,c).m)])
1072 (SignExt16to32 x))
1073 (Const64 <typ.UInt64> [16+smagic(16,c).s]))
1074 (Rsh32x64 <t>
1075 (SignExt16to32 x)
1076 (Const64 <typ.UInt64> [31])))
1077 (Div32 <t> x (Const32 [c])) && smagicOK(32,c) && config.RegSize == 8 ->
1078 (Sub32 <t>
1079 (Rsh64x64 <t>
1080 (Mul64 <typ.UInt64>
1081 (Const64 <typ.UInt64> [int64(smagic(32,c).m)])
1082 (SignExt32to64 x))
1083 (Const64 <typ.UInt64> [32+smagic(32,c).s]))
1084 (Rsh64x64 <t>
1085 (SignExt32to64 x)
1086 (Const64 <typ.UInt64> [63])))
1087 (Div32 <t> x (Const32 [c])) && smagicOK(32,c) && config.RegSize == 4 && smagic(32,c).m&1 == 0 && config.useHmul ->
1088 (Sub32 <t>
1089 (Rsh32x64 <t>
1090 (Hmul32 <t>
1091 (Const32 <typ.UInt32> [int64(int32(smagic(32,c).m/2))])
1092 x)
1093 (Const64 <typ.UInt64> [smagic(32,c).s-1]))
1094 (Rsh32x64 <t>
1095 x
1096 (Const64 <typ.UInt64> [31])))
1097 (Div32 <t> x (Const32 [c])) && smagicOK(32,c) && config.RegSize == 4 && smagic(32,c).m&1 != 0 && config.useHmul ->
1098 (Sub32 <t>
1099 (Rsh32x64 <t>
1100 (Add32 <t>
1101 (Hmul32 <t>
1102 (Const32 <typ.UInt32> [int64(int32(smagic(32,c).m))])
1103 x)
1104 x)
1105 (Const64 <typ.UInt64> [smagic(32,c).s]))
1106 (Rsh32x64 <t>
1107 x
1108 (Const64 <typ.UInt64> [31])))
1109 (Div64 <t> x (Const64 [c])) && smagicOK(64,c) && smagic(64,c).m&1 == 0 && config.useHmul ->
1110 (Sub64 <t>
1111 (Rsh64x64 <t>
1112 (Hmul64 <t>
1113 (Const64 <typ.UInt64> [int64(smagic(64,c).m/2)])
1114 x)
1115 (Const64 <typ.UInt64> [smagic(64,c).s-1]))
1116 (Rsh64x64 <t>
1117 x
1118 (Const64 <typ.UInt64> [63])))
1119 (Div64 <t> x (Const64 [c])) && smagicOK(64,c) && smagic(64,c).m&1 != 0 && config.useHmul ->
1120 (Sub64 <t>
1121 (Rsh64x64 <t>
1122 (Add64 <t>
1123 (Hmul64 <t>
1124 (Const64 <typ.UInt64> [int64(smagic(64,c).m)])
1125 x)
1126 x)
1127 (Const64 <typ.UInt64> [smagic(64,c).s]))
1128 (Rsh64x64 <t>
1129 x
1130 (Const64 <typ.UInt64> [63])))
1131
1132 // Unsigned mod by power of 2 constant.
1133 (Mod8u <t> n (Const8 [c])) && isPowerOfTwo(c&0xff) -> (And8 n (Const8 <t> [(c&0xff)-1]))
1134 (Mod16u <t> n (Const16 [c])) && isPowerOfTwo(c&0xffff) -> (And16 n (Const16 <t> [(c&0xffff)-1]))
1135 (Mod32u <t> n (Const32 [c])) && isPowerOfTwo(c&0xffffffff) -> (And32 n (Const32 <t> [(c&0xffffffff)-1]))
1136 (Mod64u <t> n (Const64 [c])) && isPowerOfTwo(c) -> (And64 n (Const64 <t> [c-1]))
1137 (Mod64u <t> n (Const64 [-1<<63])) -> (And64 n (Const64 <t> [1<<63-1]))
1138
1139 // Signed non-negative mod by power of 2 constant.
1140 (Mod8 <t> n (Const8 [c])) && isNonNegative(n) && isPowerOfTwo(c&0xff) -> (And8 n (Const8 <t> [(c&0xff)-1]))
1141 (Mod16 <t> n (Const16 [c])) && isNonNegative(n) && isPowerOfTwo(c&0xffff) -> (And16 n (Const16 <t> [(c&0xffff)-1]))
1142 (Mod32 <t> n (Const32 [c])) && isNonNegative(n) && isPowerOfTwo(c&0xffffffff) -> (And32 n (Const32 <t> [(c&0xffffffff)-1]))
1143 (Mod64 <t> n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c) -> (And64 n (Const64 <t> [c-1]))
1144 (Mod64 n (Const64 [-1<<63])) && isNonNegative(n) -> n
1145
1146 // Signed mod by negative constant.
1147 (Mod8 <t> n (Const8 [c])) && c < 0 && c != -1<<7 -> (Mod8 <t> n (Const8 <t> [-c]))
1148 (Mod16 <t> n (Const16 [c])) && c < 0 && c != -1<<15 -> (Mod16 <t> n (Const16 <t> [-c]))
1149 (Mod32 <t> n (Const32 [c])) && c < 0 && c != -1<<31 -> (Mod32 <t> n (Const32 <t> [-c]))
1150 (Mod64 <t> n (Const64 [c])) && c < 0 && c != -1<<63 -> (Mod64 <t> n (Const64 <t> [-c]))
1151
1152 // All other mods by constants, do A%B = A-(A/B*B).
1153 // This implements % with two * and a bunch of ancillary ops.
1154 // One of the * is free if the user's code also computes A/B.
1155 (Mod8 <t> x (Const8 [c])) && x.Op != OpConst8 && (c > 0 || c == -1<<7)
1156 -> (Sub8 x (Mul8 <t> (Div8 <t> x (Const8 <t> [c])) (Const8 <t> [c])))
1157 (Mod16 <t> x (Const16 [c])) && x.Op != OpConst16 && (c > 0 || c == -1<<15)
1158 -> (Sub16 x (Mul16 <t> (Div16 <t> x (Const16 <t> [c])) (Const16 <t> [c])))
1159 (Mod32 <t> x (Const32 [c])) && x.Op != OpConst32 && (c > 0 || c == -1<<31)
1160 -> (Sub32 x (Mul32 <t> (Div32 <t> x (Const32 <t> [c])) (Const32 <t> [c])))
1161 (Mod64 <t> x (Const64 [c])) && x.Op != OpConst64 && (c > 0 || c == -1<<63)
1162 -> (Sub64 x (Mul64 <t> (Div64 <t> x (Const64 <t> [c])) (Const64 <t> [c])))
1163 (Mod8u <t> x (Const8 [c])) && x.Op != OpConst8 && c > 0 && umagicOK(8, c)
1164 -> (Sub8 x (Mul8 <t> (Div8u <t> x (Const8 <t> [c])) (Const8 <t> [c])))
1165 (Mod16u <t> x (Const16 [c])) && x.Op != OpConst16 && c > 0 && umagicOK(16,c)
1166 -> (Sub16 x (Mul16 <t> (Div16u <t> x (Const16 <t> [c])) (Const16 <t> [c])))
1167 (Mod32u <t> x (Const32 [c])) && x.Op != OpConst32 && c > 0 && umagicOK(32,c)
1168 -> (Sub32 x (Mul32 <t> (Div32u <t> x (Const32 <t> [c])) (Const32 <t> [c])))
1169 (Mod64u <t> x (Const64 [c])) && x.Op != OpConst64 && c > 0 && umagicOK(64,c)
1170 -> (Sub64 x (Mul64 <t> (Div64u <t> x (Const64 <t> [c])) (Const64 <t> [c])))
1171
1172 // For architectures without rotates on less than 32-bits, promote these checks to 32-bit.
1173 (Eq8 (Mod8u x (Const8 [c])) (Const8 [0])) && x.Op != OpConst8 && udivisibleOK(8,c) && !hasSmallRotate(config) ->
1174 (Eq32 (Mod32u <typ.UInt32> (ZeroExt8to32 <typ.UInt32> x) (Const32 <typ.UInt32> [c&0xff])) (Const32 <typ.UInt32> [0]))
1175 (Eq16 (Mod16u x (Const16 [c])) (Const16 [0])) && x.Op != OpConst16 && udivisibleOK(16,c) && !hasSmallRotate(config) ->
1176 (Eq32 (Mod32u <typ.UInt32> (ZeroExt16to32 <typ.UInt32> x) (Const32 <typ.UInt32> [c&0xffff])) (Const32 <typ.UInt32> [0]))
1177 (Eq8 (Mod8 x (Const8 [c])) (Const8 [0])) && x.Op != OpConst8 && sdivisibleOK(8,c) && !hasSmallRotate(config) ->
1178 (Eq32 (Mod32 <typ.Int32> (SignExt8to32 <typ.Int32> x) (Const32 <typ.Int32> [c])) (Const32 <typ.Int32> [0]))
1179 (Eq16 (Mod16 x (Const16 [c])) (Const16 [0])) && x.Op != OpConst16 && sdivisibleOK(16,c) && !hasSmallRotate(config) ->
1180 (Eq32 (Mod32 <typ.Int32> (SignExt16to32 <typ.Int32> x) (Const32 <typ.Int32> [c])) (Const32 <typ.Int32> [0]))
1181
1182 // Divisibility checks x%c == 0 convert to multiply and rotate.
1183 // Note, x%c == 0 is rewritten as x == c*(x/c) during the opt pass
1184 // where (x/c) is peformed using multiplication with magic constants.
1185 // To rewrite x%c == 0 requires pattern matching the rewritten expression
1186 // and checking that the division by the same constant wasn't already calculated.
1187 // This check is made by counting uses of the magic constant multiplication.
1188 // Note that if there were an intermediate opt pass, this rule could be applied
1189 // directly on the Div op and magic division rewrites could be delayed to late opt.
1190
1191 // Unsigned divisibility checks convert to multiply and rotate.
1192 (Eq8 x (Mul8 (Const8 [c])
1193 (Trunc32to8
1194 (Rsh32Ux64
1195 mul:(Mul32
1196 (Const32 [m])
1197 (ZeroExt8to32 x))
1198 (Const64 [s])))
1199 )
1200 )
1201 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1202 && m == int64(1<<8+umagic(8,c).m) && s == 8+umagic(8,c).s
1203 && x.Op != OpConst8 && udivisibleOK(8,c)
1204 -> (Leq8U
1205 (RotateLeft8 <typ.UInt8>
1206 (Mul8 <typ.UInt8>
1207 (Const8 <typ.UInt8> [int64(int8(udivisible(8,c).m))])
1208 x)
1209 (Const8 <typ.UInt8> [int64(8-udivisible(8,c).k)])
1210 )
1211 (Const8 <typ.UInt8> [int64(int8(udivisible(8,c).max))])
1212 )
1213
1214 (Eq16 x (Mul16 (Const16 [c])
1215 (Trunc64to16
1216 (Rsh64Ux64
1217 mul:(Mul64
1218 (Const64 [m])
1219 (ZeroExt16to64 x))
1220 (Const64 [s])))
1221 )
1222 )
1223 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1224 && m == int64(1<<16+umagic(16,c).m) && s == 16+umagic(16,c).s
1225 && x.Op != OpConst16 && udivisibleOK(16,c)
1226 -> (Leq16U
1227 (RotateLeft16 <typ.UInt16>
1228 (Mul16 <typ.UInt16>
1229 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).m))])
1230 x)
1231 (Const16 <typ.UInt16> [int64(16-udivisible(16,c).k)])
1232 )
1233 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).max))])
1234 )
1235
1236 (Eq16 x (Mul16 (Const16 [c])
1237 (Trunc32to16
1238 (Rsh32Ux64
1239 mul:(Mul32
1240 (Const32 [m])
1241 (ZeroExt16to32 x))
1242 (Const64 [s])))
1243 )
1244 )
1245 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1246 && m == int64(1<<15+umagic(16,c).m/2) && s == 16+umagic(16,c).s-1
1247 && x.Op != OpConst16 && udivisibleOK(16,c)
1248 -> (Leq16U
1249 (RotateLeft16 <typ.UInt16>
1250 (Mul16 <typ.UInt16>
1251 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).m))])
1252 x)
1253 (Const16 <typ.UInt16> [int64(16-udivisible(16,c).k)])
1254 )
1255 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).max))])
1256 )
1257
1258 (Eq16 x (Mul16 (Const16 [c])
1259 (Trunc32to16
1260 (Rsh32Ux64
1261 mul:(Mul32
1262 (Const32 [m])
1263 (Rsh32Ux64 (ZeroExt16to32 x) (Const64 [1])))
1264 (Const64 [s])))
1265 )
1266 )
1267 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1268 && m == int64(1<<15+(umagic(16,c).m+1)/2) && s == 16+umagic(16,c).s-2
1269 && x.Op != OpConst16 && udivisibleOK(16,c)
1270 -> (Leq16U
1271 (RotateLeft16 <typ.UInt16>
1272 (Mul16 <typ.UInt16>
1273 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).m))])
1274 x)
1275 (Const16 <typ.UInt16> [int64(16-udivisible(16,c).k)])
1276 )
1277 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).max))])
1278 )
1279
1280 (Eq16 x (Mul16 (Const16 [c])
1281 (Trunc32to16
1282 (Rsh32Ux64
1283 (Avg32u
1284 (Lsh32x64 (ZeroExt16to32 x) (Const64 [16]))
1285 mul:(Mul32
1286 (Const32 [m])
1287 (ZeroExt16to32 x)))
1288 (Const64 [s])))
1289 )
1290 )
1291 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1292 && m == int64(umagic(16,c).m) && s == 16+umagic(16,c).s-1
1293 && x.Op != OpConst16 && udivisibleOK(16,c)
1294 -> (Leq16U
1295 (RotateLeft16 <typ.UInt16>
1296 (Mul16 <typ.UInt16>
1297 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).m))])
1298 x)
1299 (Const16 <typ.UInt16> [int64(16-udivisible(16,c).k)])
1300 )
1301 (Const16 <typ.UInt16> [int64(int16(udivisible(16,c).max))])
1302 )
1303
1304 (Eq32 x (Mul32 (Const32 [c])
1305 (Rsh32Ux64
1306 mul:(Hmul32u
1307 (Const32 [m])
1308 x)
1309 (Const64 [s]))
1310 )
1311 )
1312 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1313 && m == int64(int32(1<<31+umagic(32,c).m/2)) && s == umagic(32,c).s-1
1314 && x.Op != OpConst32 && udivisibleOK(32,c)
1315 -> (Leq32U
1316 (RotateLeft32 <typ.UInt32>
1317 (Mul32 <typ.UInt32>
1318 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).m))])
1319 x)
1320 (Const32 <typ.UInt32> [int64(32-udivisible(32,c).k)])
1321 )
1322 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).max))])
1323 )
1324
1325 (Eq32 x (Mul32 (Const32 [c])
1326 (Rsh32Ux64
1327 mul:(Hmul32u
1328 (Const32 <typ.UInt32> [m])
1329 (Rsh32Ux64 x (Const64 [1])))
1330 (Const64 [s]))
1331 )
1332 )
1333 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1334 && m == int64(int32(1<<31+(umagic(32,c).m+1)/2)) && s == umagic(32,c).s-2
1335 && x.Op != OpConst32 && udivisibleOK(32,c)
1336 -> (Leq32U
1337 (RotateLeft32 <typ.UInt32>
1338 (Mul32 <typ.UInt32>
1339 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).m))])
1340 x)
1341 (Const32 <typ.UInt32> [int64(32-udivisible(32,c).k)])
1342 )
1343 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).max))])
1344 )
1345
1346 (Eq32 x (Mul32 (Const32 [c])
1347 (Rsh32Ux64
1348 (Avg32u
1349 x
1350 mul:(Hmul32u
1351 (Const32 [m])
1352 x))
1353 (Const64 [s]))
1354 )
1355 )
1356 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1357 && m == int64(int32(umagic(32,c).m)) && s == umagic(32,c).s-1
1358 && x.Op != OpConst32 && udivisibleOK(32,c)
1359 -> (Leq32U
1360 (RotateLeft32 <typ.UInt32>
1361 (Mul32 <typ.UInt32>
1362 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).m))])
1363 x)
1364 (Const32 <typ.UInt32> [int64(32-udivisible(32,c).k)])
1365 )
1366 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).max))])
1367 )
1368
1369 (Eq32 x (Mul32 (Const32 [c])
1370 (Trunc64to32
1371 (Rsh64Ux64
1372 mul:(Mul64
1373 (Const64 [m])
1374 (ZeroExt32to64 x))
1375 (Const64 [s])))
1376 )
1377 )
1378 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1379 && m == int64(1<<31+umagic(32,c).m/2) && s == 32+umagic(32,c).s-1
1380 && x.Op != OpConst32 && udivisibleOK(32,c)
1381 -> (Leq32U
1382 (RotateLeft32 <typ.UInt32>
1383 (Mul32 <typ.UInt32>
1384 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).m))])
1385 x)
1386 (Const32 <typ.UInt32> [int64(32-udivisible(32,c).k)])
1387 )
1388 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).max))])
1389 )
1390
1391 (Eq32 x (Mul32 (Const32 [c])
1392 (Trunc64to32
1393 (Rsh64Ux64
1394 mul:(Mul64
1395 (Const64 [m])
1396 (Rsh64Ux64 (ZeroExt32to64 x) (Const64 [1])))
1397 (Const64 [s])))
1398 )
1399 )
1400 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1401 && m == int64(1<<31+(umagic(32,c).m+1)/2) && s == 32+umagic(32,c).s-2
1402 && x.Op != OpConst32 && udivisibleOK(32,c)
1403 -> (Leq32U
1404 (RotateLeft32 <typ.UInt32>
1405 (Mul32 <typ.UInt32>
1406 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).m))])
1407 x)
1408 (Const32 <typ.UInt32> [int64(32-udivisible(32,c).k)])
1409 )
1410 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).max))])
1411 )
1412
1413 (Eq32 x (Mul32 (Const32 [c])
1414 (Trunc64to32
1415 (Rsh64Ux64
1416 (Avg64u
1417 (Lsh64x64 (ZeroExt32to64 x) (Const64 [32]))
1418 mul:(Mul64
1419 (Const64 [m])
1420 (ZeroExt32to64 x)))
1421 (Const64 [s])))
1422 )
1423 )
1424 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1425 && m == int64(umagic(32,c).m) && s == 32+umagic(32,c).s-1
1426 && x.Op != OpConst32 && udivisibleOK(32,c)
1427 -> (Leq32U
1428 (RotateLeft32 <typ.UInt32>
1429 (Mul32 <typ.UInt32>
1430 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).m))])
1431 x)
1432 (Const32 <typ.UInt32> [int64(32-udivisible(32,c).k)])
1433 )
1434 (Const32 <typ.UInt32> [int64(int32(udivisible(32,c).max))])
1435 )
1436
1437 (Eq64 x (Mul64 (Const64 [c])
1438 (Rsh64Ux64
1439 mul:(Hmul64u
1440 (Const64 [m])
1441 x)
1442 (Const64 [s]))
1443 )
1444 ) && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1445 && m == int64(1<<63+umagic(64,c).m/2) && s == umagic(64,c).s-1
1446 && x.Op != OpConst64 && udivisibleOK(64,c)
1447 -> (Leq64U
1448 (RotateLeft64 <typ.UInt64>
1449 (Mul64 <typ.UInt64>
1450 (Const64 <typ.UInt64> [int64(udivisible(64,c).m)])
1451 x)
1452 (Const64 <typ.UInt64> [int64(64-udivisible(64,c).k)])
1453 )
1454 (Const64 <typ.UInt64> [int64(udivisible(64,c).max)])
1455 )
1456 (Eq64 x (Mul64 (Const64 [c])
1457 (Rsh64Ux64
1458 mul:(Hmul64u
1459 (Const64 [m])
1460 (Rsh64Ux64 x (Const64 [1])))
1461 (Const64 [s]))
1462 )
1463 ) && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1464 && m == int64(1<<63+(umagic(64,c).m+1)/2) && s == umagic(64,c).s-2
1465 && x.Op != OpConst64 && udivisibleOK(64,c)
1466 -> (Leq64U
1467 (RotateLeft64 <typ.UInt64>
1468 (Mul64 <typ.UInt64>
1469 (Const64 <typ.UInt64> [int64(udivisible(64,c).m)])
1470 x)
1471 (Const64 <typ.UInt64> [int64(64-udivisible(64,c).k)])
1472 )
1473 (Const64 <typ.UInt64> [int64(udivisible(64,c).max)])
1474 )
1475 (Eq64 x (Mul64 (Const64 [c])
1476 (Rsh64Ux64
1477 (Avg64u
1478 x
1479 mul:(Hmul64u
1480 (Const64 [m])
1481 x))
1482 (Const64 [s]))
1483 )
1484 ) && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1485 && m == int64(umagic(64,c).m) && s == umagic(64,c).s-1
1486 && x.Op != OpConst64 && udivisibleOK(64,c)
1487 -> (Leq64U
1488 (RotateLeft64 <typ.UInt64>
1489 (Mul64 <typ.UInt64>
1490 (Const64 <typ.UInt64> [int64(udivisible(64,c).m)])
1491 x)
1492 (Const64 <typ.UInt64> [int64(64-udivisible(64,c).k)])
1493 )
1494 (Const64 <typ.UInt64> [int64(udivisible(64,c).max)])
1495 )
1496
1497 // Signed divisibility checks convert to multiply, add and rotate.
1498 (Eq8 x (Mul8 (Const8 [c])
1499 (Sub8
1500 (Rsh32x64
1501 mul:(Mul32
1502 (Const32 [m])
1503 (SignExt8to32 x))
1504 (Const64 [s]))
1505 (Rsh32x64
1506 (SignExt8to32 x)
1507 (Const64 [31])))
1508 )
1509 )
1510 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1511 && m == int64(smagic(8,c).m) && s == 8+smagic(8,c).s
1512 && x.Op != OpConst8 && sdivisibleOK(8,c)
1513 -> (Leq8U
1514 (RotateLeft8 <typ.UInt8>
1515 (Add8 <typ.UInt8>
1516 (Mul8 <typ.UInt8>
1517 (Const8 <typ.UInt8> [int64(int8(sdivisible(8,c).m))])
1518 x)
1519 (Const8 <typ.UInt8> [int64(int8(sdivisible(8,c).a))])
1520 )
1521 (Const8 <typ.UInt8> [int64(8-sdivisible(8,c).k)])
1522 )
1523 (Const8 <typ.UInt8> [int64(int8(sdivisible(8,c).max))])
1524 )
1525
1526 (Eq16 x (Mul16 (Const16 [c])
1527 (Sub16
1528 (Rsh32x64
1529 mul:(Mul32
1530 (Const32 [m])
1531 (SignExt16to32 x))
1532 (Const64 [s]))
1533 (Rsh32x64
1534 (SignExt16to32 x)
1535 (Const64 [31])))
1536 )
1537 )
1538 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1539 && m == int64(smagic(16,c).m) && s == 16+smagic(16,c).s
1540 && x.Op != OpConst16 && sdivisibleOK(16,c)
1541 -> (Leq16U
1542 (RotateLeft16 <typ.UInt16>
1543 (Add16 <typ.UInt16>
1544 (Mul16 <typ.UInt16>
1545 (Const16 <typ.UInt16> [int64(int16(sdivisible(16,c).m))])
1546 x)
1547 (Const16 <typ.UInt16> [int64(int16(sdivisible(16,c).a))])
1548 )
1549 (Const16 <typ.UInt16> [int64(16-sdivisible(16,c).k)])
1550 )
1551 (Const16 <typ.UInt16> [int64(int16(sdivisible(16,c).max))])
1552 )
1553
1554 (Eq32 x (Mul32 (Const32 [c])
1555 (Sub32
1556 (Rsh64x64
1557 mul:(Mul64
1558 (Const64 [m])
1559 (SignExt32to64 x))
1560 (Const64 [s]))
1561 (Rsh64x64
1562 (SignExt32to64 x)
1563 (Const64 [63])))
1564 )
1565 )
1566 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1567 && m == int64(smagic(32,c).m) && s == 32+smagic(32,c).s
1568 && x.Op != OpConst32 && sdivisibleOK(32,c)
1569 -> (Leq32U
1570 (RotateLeft32 <typ.UInt32>
1571 (Add32 <typ.UInt32>
1572 (Mul32 <typ.UInt32>
1573 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).m))])
1574 x)
1575 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).a))])
1576 )
1577 (Const32 <typ.UInt32> [int64(32-sdivisible(32,c).k)])
1578 )
1579 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).max))])
1580 )
1581
1582 (Eq32 x (Mul32 (Const32 [c])
1583 (Sub32
1584 (Rsh32x64
1585 mul:(Hmul32
1586 (Const32 [m])
1587 x)
1588 (Const64 [s]))
1589 (Rsh32x64
1590 x
1591 (Const64 [31])))
1592 )
1593 )
1594 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1595 && m == int64(int32(smagic(32,c).m/2)) && s == smagic(32,c).s-1
1596 && x.Op != OpConst32 && sdivisibleOK(32,c)
1597 -> (Leq32U
1598 (RotateLeft32 <typ.UInt32>
1599 (Add32 <typ.UInt32>
1600 (Mul32 <typ.UInt32>
1601 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).m))])
1602 x)
1603 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).a))])
1604 )
1605 (Const32 <typ.UInt32> [int64(32-sdivisible(32,c).k)])
1606 )
1607 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).max))])
1608 )
1609
1610 (Eq32 x (Mul32 (Const32 [c])
1611 (Sub32
1612 (Rsh32x64
1613 (Add32
1614 mul:(Hmul32
1615 (Const32 [m])
1616 x)
1617 x)
1618 (Const64 [s]))
1619 (Rsh32x64
1620 x
1621 (Const64 [31])))
1622 )
1623 )
1624 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1625 && m == int64(int32(smagic(32,c).m)) && s == smagic(32,c).s
1626 && x.Op != OpConst32 && sdivisibleOK(32,c)
1627 -> (Leq32U
1628 (RotateLeft32 <typ.UInt32>
1629 (Add32 <typ.UInt32>
1630 (Mul32 <typ.UInt32>
1631 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).m))])
1632 x)
1633 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).a))])
1634 )
1635 (Const32 <typ.UInt32> [int64(32-sdivisible(32,c).k)])
1636 )
1637 (Const32 <typ.UInt32> [int64(int32(sdivisible(32,c).max))])
1638 )
1639
1640 (Eq64 x (Mul64 (Const64 [c])
1641 (Sub64
1642 (Rsh64x64
1643 mul:(Hmul64
1644 (Const64 [m])
1645 x)
1646 (Const64 [s]))
1647 (Rsh64x64
1648 x
1649 (Const64 [63])))
1650 )
1651 )
1652 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1653 && m == int64(smagic(64,c).m/2) && s == smagic(64,c).s-1
1654 && x.Op != OpConst64 && sdivisibleOK(64,c)
1655 -> (Leq64U
1656 (RotateLeft64 <typ.UInt64>
1657 (Add64 <typ.UInt64>
1658 (Mul64 <typ.UInt64>
1659 (Const64 <typ.UInt64> [int64(sdivisible(64,c).m)])
1660 x)
1661 (Const64 <typ.UInt64> [int64(sdivisible(64,c).a)])
1662 )
1663 (Const64 <typ.UInt64> [int64(64-sdivisible(64,c).k)])
1664 )
1665 (Const64 <typ.UInt64> [int64(sdivisible(64,c).max)])
1666 )
1667
1668 (Eq64 x (Mul64 (Const64 [c])
1669 (Sub64
1670 (Rsh64x64
1671 (Add64
1672 mul:(Hmul64
1673 (Const64 [m])
1674 x)
1675 x)
1676 (Const64 [s]))
1677 (Rsh64x64
1678 x
1679 (Const64 [63])))
1680 )
1681 )
1682 && v.Block.Func.pass.name != "opt" && mul.Uses == 1
1683 && m == int64(smagic(64,c).m) && s == smagic(64,c).s
1684 && x.Op != OpConst64 && sdivisibleOK(64,c)
1685 -> (Leq64U
1686 (RotateLeft64 <typ.UInt64>
1687 (Add64 <typ.UInt64>
1688 (Mul64 <typ.UInt64>
1689 (Const64 <typ.UInt64> [int64(sdivisible(64,c).m)])
1690 x)
1691 (Const64 <typ.UInt64> [int64(sdivisible(64,c).a)])
1692 )
1693 (Const64 <typ.UInt64> [int64(64-sdivisible(64,c).k)])
1694 )
1695 (Const64 <typ.UInt64> [int64(sdivisible(64,c).max)])
1696 )
1697
1698 // Divisibility check for signed integers for power of two constant are simple mask.
1699 // However, we must match against the rewritten n%c == 0 -> n - c*(n/c) == 0 -> n == c*(n/c)
1700 // where n/c contains fixup code to handle signed n.
1701 (Eq8 n (Lsh8x64
1702 (Rsh8x64
1703 (Add8 <t> n (Rsh8Ux64 <t> (Rsh8x64 <t> n (Const64 <typ.UInt64> [ 7])) (Const64 <typ.UInt64> [kbar])))
1704 (Const64 <typ.UInt64> [k]))
1705 (Const64 <typ.UInt64> [k]))
1706 ) && k > 0 && k < 7 && kbar == 8 - k
1707 -> (Eq8 (And8 <t> n (Const8 <t> [int64(1<<uint(k)-1)])) (Const8 <t> [0]))
1708
1709 (Eq16 n (Lsh16x64
1710 (Rsh16x64
1711 (Add16 <t> n (Rsh16Ux64 <t> (Rsh16x64 <t> n (Const64 <typ.UInt64> [15])) (Const64 <typ.UInt64> [kbar])))
1712 (Const64 <typ.UInt64> [k]))
1713 (Const64 <typ.UInt64> [k]))
1714 ) && k > 0 && k < 15 && kbar == 16 - k
1715 -> (Eq16 (And16 <t> n (Const16 <t> [int64(1<<uint(k)-1)])) (Const16 <t> [0]))
1716
1717 (Eq32 n (Lsh32x64
1718 (Rsh32x64
1719 (Add32 <t> n (Rsh32Ux64 <t> (Rsh32x64 <t> n (Const64 <typ.UInt64> [31])) (Const64 <typ.UInt64> [kbar])))
1720 (Const64 <typ.UInt64> [k]))
1721 (Const64 <typ.UInt64> [k]))
1722 ) && k > 0 && k < 31 && kbar == 32 - k
1723 -> (Eq32 (And32 <t> n (Const32 <t> [int64(1<<uint(k)-1)])) (Const32 <t> [0]))
1724
1725 (Eq64 n (Lsh64x64
1726 (Rsh64x64
1727 (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [kbar])))
1728 (Const64 <typ.UInt64> [k]))
1729 (Const64 <typ.UInt64> [k]))
1730 ) && k > 0 && k < 63 && kbar == 64 - k
1731 -> (Eq64 (And64 <t> n (Const64 <t> [int64(1<<uint(k)-1)])) (Const64 <t> [0]))
1732
1733 (Eq(8|16|32|64) s:(Sub(8|16|32|64) x y) (Const(8|16|32|64) [0])) && s.Uses == 1 -> (Eq(8|16|32|64) x y)
1734 (Neq(8|16|32|64) s:(Sub(8|16|32|64) x y) (Const(8|16|32|64) [0])) && s.Uses == 1 -> (Neq(8|16|32|64) x y)
1735
1736 // Reassociate expressions involving
1737 // constants such that constants come first,
1738 // exposing obvious constant-folding opportunities.
1739 // Reassociate (op (op y C) x) to (op C (op x y)) or similar, where C
1740 // is constant, which pushes constants to the outside
1741 // of the expression. At that point, any constant-folding
1742 // opportunities should be obvious.
1743
1744 // x + (C + z) -> C + (x + z)
1745 (Add64 (Add64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Add64 i (Add64 <t> z x))
1746 (Add32 (Add32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Add32 i (Add32 <t> z x))
1747 (Add16 (Add16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Add16 i (Add16 <t> z x))
1748 (Add8 (Add8 i:(Const8 <t>) z) x) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Add8 i (Add8 <t> z x))
1749
1750 // x + (C - z) -> C + (x - z)
1751 (Add64 (Sub64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Add64 i (Sub64 <t> x z))
1752 (Add32 (Sub32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Add32 i (Sub32 <t> x z))
1753 (Add16 (Sub16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Add16 i (Sub16 <t> x z))
1754 (Add8 (Sub8 i:(Const8 <t>) z) x) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Add8 i (Sub8 <t> x z))
1755 (Add64 x (Sub64 i:(Const64 <t>) z)) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Add64 i (Sub64 <t> x z))
1756 (Add32 x (Sub32 i:(Const32 <t>) z)) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Add32 i (Sub32 <t> x z))
1757 (Add16 x (Sub16 i:(Const16 <t>) z)) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Add16 i (Sub16 <t> x z))
1758 (Add8 x (Sub8 i:(Const8 <t>) z)) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Add8 i (Sub8 <t> x z))
1759
1760 // x + (z - C) -> (x + z) - C
1761 (Add64 (Sub64 z i:(Const64 <t>)) x) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Sub64 (Add64 <t> x z) i)
1762 (Add32 (Sub32 z i:(Const32 <t>)) x) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Sub32 (Add32 <t> x z) i)
1763 (Add16 (Sub16 z i:(Const16 <t>)) x) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Sub16 (Add16 <t> x z) i)
1764 (Add8 (Sub8 z i:(Const8 <t>)) x) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Sub8 (Add8 <t> x z) i)
1765 (Add64 x (Sub64 z i:(Const64 <t>))) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Sub64 (Add64 <t> x z) i)
1766 (Add32 x (Sub32 z i:(Const32 <t>))) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Sub32 (Add32 <t> x z) i)
1767 (Add16 x (Sub16 z i:(Const16 <t>))) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Sub16 (Add16 <t> x z) i)
1768 (Add8 x (Sub8 z i:(Const8 <t>))) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Sub8 (Add8 <t> x z) i)
1769
1770 // x - (C - z) -> x + (z - C) -> (x + z) - C
1771 (Sub64 x (Sub64 i:(Const64 <t>) z)) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Sub64 (Add64 <t> x z) i)
1772 (Sub32 x (Sub32 i:(Const32 <t>) z)) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Sub32 (Add32 <t> x z) i)
1773 (Sub16 x (Sub16 i:(Const16 <t>) z)) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Sub16 (Add16 <t> x z) i)
1774 (Sub8 x (Sub8 i:(Const8 <t>) z)) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Sub8 (Add8 <t> x z) i)
1775
1776 // x - (z - C) -> x + (C - z) -> (x - z) + C
1777 (Sub64 x (Sub64 z i:(Const64 <t>))) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Add64 i (Sub64 <t> x z))
1778 (Sub32 x (Sub32 z i:(Const32 <t>))) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Add32 i (Sub32 <t> x z))
1779 (Sub16 x (Sub16 z i:(Const16 <t>))) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Add16 i (Sub16 <t> x z))
1780 (Sub8 x (Sub8 z i:(Const8 <t>))) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Add8 i (Sub8 <t> x z))
1781
1782 // x & (C & z) -> C & (x & z)
1783 (And64 (And64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) -> (And64 i (And64 <t> z x))
1784 (And32 (And32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) -> (And32 i (And32 <t> z x))
1785 (And16 (And16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) -> (And16 i (And16 <t> z x))
1786 (And8 (And8 i:(Const8 <t>) z) x) && (z.Op != OpConst8 && x.Op != OpConst8) -> (And8 i (And8 <t> z x))
1787
1788 // x | (C | z) -> C | (x | z)
1789 (Or64 (Or64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Or64 i (Or64 <t> z x))
1790 (Or32 (Or32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Or32 i (Or32 <t> z x))
1791 (Or16 (Or16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Or16 i (Or16 <t> z x))
1792 (Or8 (Or8 i:(Const8 <t>) z) x) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Or8 i (Or8 <t> z x))
1793
1794 // x ^ (C ^ z) -> C ^ (x ^ z)
1795 (Xor64 (Xor64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) -> (Xor64 i (Xor64 <t> z x))
1796 (Xor32 (Xor32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) -> (Xor32 i (Xor32 <t> z x))
1797 (Xor16 (Xor16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) -> (Xor16 i (Xor16 <t> z x))
1798 (Xor8 (Xor8 i:(Const8 <t>) z) x) && (z.Op != OpConst8 && x.Op != OpConst8) -> (Xor8 i (Xor8 <t> z x))
1799
1800 // C + (D + x) -> (C + D) + x
1801 (Add64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) -> (Add64 (Const64 <t> [c+d]) x)
1802 (Add32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) -> (Add32 (Const32 <t> [int64(int32(c+d))]) x)
1803 (Add16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) -> (Add16 (Const16 <t> [int64(int16(c+d))]) x)
1804 (Add8 (Const8 <t> [c]) (Add8 (Const8 <t> [d]) x)) -> (Add8 (Const8 <t> [int64(int8(c+d))]) x)
1805
1806 // C + (D - x) -> (C + D) - x
1807 (Add64 (Const64 <t> [c]) (Sub64 (Const64 <t> [d]) x)) -> (Sub64 (Const64 <t> [c+d]) x)
1808 (Add32 (Const32 <t> [c]) (Sub32 (Const32 <t> [d]) x)) -> (Sub32 (Const32 <t> [int64(int32(c+d))]) x)
1809 (Add16 (Const16 <t> [c]) (Sub16 (Const16 <t> [d]) x)) -> (Sub16 (Const16 <t> [int64(int16(c+d))]) x)
1810 (Add8 (Const8 <t> [c]) (Sub8 (Const8 <t> [d]) x)) -> (Sub8 (Const8 <t> [int64(int8(c+d))]) x)
1811
1812 // C + (x - D) -> (C - D) + x
1813 (Add64 (Const64 <t> [c]) (Sub64 x (Const64 <t> [d]))) -> (Add64 (Const64 <t> [c-d]) x)
1814 (Add32 (Const32 <t> [c]) (Sub32 x (Const32 <t> [d]))) -> (Add32 (Const32 <t> [int64(int32(c-d))]) x)
1815 (Add16 (Const16 <t> [c]) (Sub16 x (Const16 <t> [d]))) -> (Add16 (Const16 <t> [int64(int16(c-d))]) x)
1816 (Add8 (Const8 <t> [c]) (Sub8 x (Const8 <t> [d]))) -> (Add8 (Const8 <t> [int64(int8(c-d))]) x)
1817
1818 // C - (x - D) -> (C + D) - x
1819 (Sub64 (Const64 <t> [c]) (Sub64 x (Const64 <t> [d]))) -> (Sub64 (Const64 <t> [c+d]) x)
1820 (Sub32 (Const32 <t> [c]) (Sub32 x (Const32 <t> [d]))) -> (Sub32 (Const32 <t> [int64(int32(c+d))]) x)
1821 (Sub16 (Const16 <t> [c]) (Sub16 x (Const16 <t> [d]))) -> (Sub16 (Const16 <t> [int64(int16(c+d))]) x)
1822 (Sub8 (Const8 <t> [c]) (Sub8 x (Const8 <t> [d]))) -> (Sub8 (Const8 <t> [int64(int8(c+d))]) x)
1823
1824 // C - (D - x) -> (C - D) + x
1825 (Sub64 (Const64 <t> [c]) (Sub64 (Const64 <t> [d]) x)) -> (Add64 (Const64 <t> [c-d]) x)
1826 (Sub32 (Const32 <t> [c]) (Sub32 (Const32 <t> [d]) x)) -> (Add32 (Const32 <t> [int64(int32(c-d))]) x)
1827 (Sub16 (Const16 <t> [c]) (Sub16 (Const16 <t> [d]) x)) -> (Add16 (Const16 <t> [int64(int16(c-d))]) x)
1828 (Sub8 (Const8 <t> [c]) (Sub8 (Const8 <t> [d]) x)) -> (Add8 (Const8 <t> [int64(int8(c-d))]) x)
1829
1830 // C & (D & x) -> (C & D) & x
1831 (And64 (Const64 <t> [c]) (And64 (Const64 <t> [d]) x)) -> (And64 (Const64 <t> [c&d]) x)
1832 (And32 (Const32 <t> [c]) (And32 (Const32 <t> [d]) x)) -> (And32 (Const32 <t> [int64(int32(c&d))]) x)
1833 (And16 (Const16 <t> [c]) (And16 (Const16 <t> [d]) x)) -> (And16 (Const16 <t> [int64(int16(c&d))]) x)
1834 (And8 (Const8 <t> [c]) (And8 (Const8 <t> [d]) x)) -> (And8 (Const8 <t> [int64(int8(c&d))]) x)
1835
1836 // C | (D | x) -> (C | D) | x
1837 (Or64 (Const64 <t> [c]) (Or64 (Const64 <t> [d]) x)) -> (Or64 (Const64 <t> [c|d]) x)
1838 (Or32 (Const32 <t> [c]) (Or32 (Const32 <t> [d]) x)) -> (Or32 (Const32 <t> [int64(int32(c|d))]) x)
1839 (Or16 (Const16 <t> [c]) (Or16 (Const16 <t> [d]) x)) -> (Or16 (Const16 <t> [int64(int16(c|d))]) x)
1840 (Or8 (Const8 <t> [c]) (Or8 (Const8 <t> [d]) x)) -> (Or8 (Const8 <t> [int64(int8(c|d))]) x)
1841
1842 // C ^ (D ^ x) -> (C ^ D) ^ x
1843 (Xor64 (Const64 <t> [c]) (Xor64 (Const64 <t> [d]) x)) -> (Xor64 (Const64 <t> [c^d]) x)
1844 (Xor32 (Const32 <t> [c]) (Xor32 (Const32 <t> [d]) x)) -> (Xor32 (Const32 <t> [int64(int32(c^d))]) x)
1845 (Xor16 (Const16 <t> [c]) (Xor16 (Const16 <t> [d]) x)) -> (Xor16 (Const16 <t> [int64(int16(c^d))]) x)
1846 (Xor8 (Const8 <t> [c]) (Xor8 (Const8 <t> [d]) x)) -> (Xor8 (Const8 <t> [int64(int8(c^d))]) x)
1847
1848 // C * (D * x) = (C * D) * x
1849 (Mul64 (Const64 <t> [c]) (Mul64 (Const64 <t> [d]) x)) -> (Mul64 (Const64 <t> [c*d]) x)
1850 (Mul32 (Const32 <t> [c]) (Mul32 (Const32 <t> [d]) x)) -> (Mul32 (Const32 <t> [int64(int32(c*d))]) x)
1851 (Mul16 (Const16 <t> [c]) (Mul16 (Const16 <t> [d]) x)) -> (Mul16 (Const16 <t> [int64(int16(c*d))]) x)
1852 (Mul8 (Const8 <t> [c]) (Mul8 (Const8 <t> [d]) x)) -> (Mul8 (Const8 <t> [int64(int8(c*d))]) x)
1853
1854 // floating point optimizations
1855 (Mul(32|64)F x (Const(32|64)F [auxFrom64F(1)])) -> x
1856 (Mul32F x (Const32F [auxFrom32F(-1)])) -> (Neg32F x)
1857 (Mul64F x (Const64F [auxFrom64F(-1)])) -> (Neg64F x)
1858 (Mul32F x (Const32F [auxFrom32F(2)])) -> (Add32F x x)
1859 (Mul64F x (Const64F [auxFrom64F(2)])) -> (Add64F x x)
1860
1861 (Div32F x (Const32F <t> [c])) && reciprocalExact32(auxTo32F(c)) -> (Mul32F x (Const32F <t> [auxFrom32F(1/auxTo32F(c))]))
1862 (Div64F x (Const64F <t> [c])) && reciprocalExact64(auxTo64F(c)) -> (Mul64F x (Const64F <t> [auxFrom64F(1/auxTo64F(c))]))
1863
1864 (Sqrt (Const64F [c])) -> (Const64F [auxFrom64F(math.Sqrt(auxTo64F(c)))])
1865
1866 // recognize runtime.newobject and don't Zero/Nilcheck it
1867 (Zero (Load (OffPtr [c] (SP)) mem) mem)
1868 && mem.Op == OpStaticCall
1869 && isSameSym(mem.Aux, "runtime.newobject")
1870 && c == config.ctxt.FixedFrameSize() + config.RegSize // offset of return value
1871 -> mem
1872 (Store (Load (OffPtr [c] (SP)) mem) x mem)
1873 && isConstZero(x)
1874 && mem.Op == OpStaticCall
1875 && isSameSym(mem.Aux, "runtime.newobject")
1876 && c == config.ctxt.FixedFrameSize() + config.RegSize // offset of return value
1877 -> mem
1878 (Store (OffPtr (Load (OffPtr [c] (SP)) mem)) x mem)
1879 && isConstZero(x)
1880 && mem.Op == OpStaticCall
1881 && isSameSym(mem.Aux, "runtime.newobject")
1882 && c == config.ctxt.FixedFrameSize() + config.RegSize // offset of return value
1883 -> mem
1884 // nil checks just need to rewrite to something useless.
1885 // they will be deadcode eliminated soon afterwards.
1886 (NilCheck (Load (OffPtr [c] (SP)) (StaticCall {sym} _)) _)
1887 && isSameSym(sym, "runtime.newobject")
1888 && c == config.ctxt.FixedFrameSize() + config.RegSize // offset of return value
1889 && warnRule(fe.Debug_checknil(), v, "removed nil check")
1890 -> (Invalid)
1891 (NilCheck (OffPtr (Load (OffPtr [c] (SP)) (StaticCall {sym} _))) _)
1892 && isSameSym(sym, "runtime.newobject")
1893 && c == config.ctxt.FixedFrameSize() + config.RegSize // offset of return value
1894 && warnRule(fe.Debug_checknil(), v, "removed nil check")
1895 -> (Invalid)
1896
1897 // Evaluate constant address comparisons.
1898 (EqPtr x x) -> (ConstBool [1])
1899 (NeqPtr x x) -> (ConstBool [0])
1900 (EqPtr (Addr {a} _) (Addr {b} _)) -> (ConstBool [b2i(a == b)])
1901 (NeqPtr (Addr {a} _) (Addr {b} _)) -> (ConstBool [b2i(a != b)])
1902 (EqPtr (LocalAddr {a} _ _) (LocalAddr {b} _ _)) -> (ConstBool [b2i(a == b)])
1903 (NeqPtr (LocalAddr {a} _ _) (LocalAddr {b} _ _)) -> (ConstBool [b2i(a != b)])
1904 (EqPtr (OffPtr [o1] p1) p2) && isSamePtr(p1, p2) -> (ConstBool [b2i(o1 == 0)])
1905 (NeqPtr (OffPtr [o1] p1) p2) && isSamePtr(p1, p2) -> (ConstBool [b2i(o1 != 0)])
1906 (EqPtr (OffPtr [o1] p1) (OffPtr [o2] p2)) && isSamePtr(p1, p2) -> (ConstBool [b2i(o1 == o2)])
1907 (NeqPtr (OffPtr [o1] p1) (OffPtr [o2] p2)) && isSamePtr(p1, p2) -> (ConstBool [b2i(o1 != o2)])
1908 (EqPtr (Const(32|64) [c]) (Const(32|64) [d])) -> (ConstBool [b2i(c == d)])
1909 (NeqPtr (Const(32|64) [c]) (Const(32|64) [d])) -> (ConstBool [b2i(c != d)])
1910
1911 (EqPtr (LocalAddr _ _) (Addr _)) -> (ConstBool [0])
1912 (NeqPtr (LocalAddr _ _) (Addr _)) -> (ConstBool [1])
1913 (EqPtr (Addr _) (LocalAddr _ _)) -> (ConstBool [0])
1914 (NeqPtr (Addr _) (LocalAddr _ _)) -> (ConstBool [1])
1915
1916 // Simplify address comparisons.
1917 (EqPtr (AddPtr p1 o1) p2) && isSamePtr(p1, p2) -> (Not (IsNonNil o1))
1918 (NeqPtr (AddPtr p1 o1) p2) && isSamePtr(p1, p2) -> (IsNonNil o1)
1919 (EqPtr (Const(32|64) [0]) p) -> (Not (IsNonNil p))
1920 (NeqPtr (Const(32|64) [0]) p) -> (IsNonNil p)
1921 (EqPtr (ConstNil) p) -> (Not (IsNonNil p))
1922 (NeqPtr (ConstNil) p) -> (IsNonNil p)
1923
1924 // Evaluate constant user nil checks.
1925 (IsNonNil (ConstNil)) -> (ConstBool [0])
1926 (IsNonNil (Const(32|64) [c])) -> (ConstBool [b2i(c != 0)])
1927 (IsNonNil (Addr _)) -> (ConstBool [1])
1928 (IsNonNil (LocalAddr _ _)) -> (ConstBool [1])
1929
1930 // Inline small or disjoint runtime.memmove calls with constant length.
1931 (StaticCall {sym} s1:(Store _ (Const(64|32) [sz]) s2:(Store _ src s3:(Store {t} _ dst mem))))
1932 && isSameSym(sym,"runtime.memmove")
1933 && t.(*types.Type).IsPtr() // avoids TUINTPTR, see issue 30061
1934 && s1.Uses == 1 && s2.Uses == 1 && s3.Uses == 1
1935 && isInlinableMemmove(dst,src,sz,config)
1936 && clobber(s1) && clobber(s2) && clobber(s3)
1937 -> (Move {t.(*types.Type).Elem()} [sz] dst src mem)
1938
1939 // De-virtualize interface calls into static calls.
1940 // Note that (ITab (IMake)) doesn't get
1941 // rewritten until after the first opt pass,
1942 // so this rule should trigger reliably.
1943 (InterCall [argsize] (Load (OffPtr [off] (ITab (IMake (Addr {itab} (SB)) _))) _) mem) && devirt(v, itab, off) != nil ->
1944 (StaticCall [argsize] {devirt(v, itab, off)} mem)
1945
1946 // Move and Zero optimizations.
1947 // Move source and destination may overlap.
1948
1949 // Convert Moves into Zeros when the source is known to be zeros.
1950 (Move {t} [n] dst1 src mem:(Zero {t} [n] dst2 _)) && isSamePtr(src, dst2)
1951 -> (Zero {t} [n] dst1 mem)
1952 (Move {t} [n] dst1 src mem:(VarDef (Zero {t} [n] dst0 _))) && isSamePtr(src, dst0)
1953 -> (Zero {t} [n] dst1 mem)
1954
1955 // Don't Store to variables that are about to be overwritten by Move/Zero.
1956 (Zero {t1} [n] p1 store:(Store {t2} (OffPtr [o2] p2) _ mem))
1957 && isSamePtr(p1, p2) && store.Uses == 1
1958 && n >= o2 + sizeof(t2)
1959 && clobber(store)
1960 -> (Zero {t1} [n] p1 mem)
1961 (Move {t1} [n] dst1 src1 store:(Store {t2} op:(OffPtr [o2] dst2) _ mem))
1962 && isSamePtr(dst1, dst2) && store.Uses == 1
1963 && n >= o2 + sizeof(t2)
1964 && disjoint(src1, n, op, sizeof(t2))
1965 && clobber(store)
1966 -> (Move {t1} [n] dst1 src1 mem)
1967
1968 // Don't Move to variables that are immediately completely overwritten.
1969 (Zero {t} [n] dst1 move:(Move {t} [n] dst2 _ mem))
1970 && move.Uses == 1
1971 && isSamePtr(dst1, dst2)
1972 && clobber(move)
1973 -> (Zero {t} [n] dst1 mem)
1974 (Move {t} [n] dst1 src1 move:(Move {t} [n] dst2 _ mem))
1975 && move.Uses == 1
1976 && isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
1977 && clobber(move)
1978 -> (Move {t} [n] dst1 src1 mem)
1979 (Zero {t} [n] dst1 vardef:(VarDef {x} move:(Move {t} [n] dst2 _ mem)))
1980 && move.Uses == 1 && vardef.Uses == 1
1981 && isSamePtr(dst1, dst2)
1982 && clobber(move) && clobber(vardef)
1983 -> (Zero {t} [n] dst1 (VarDef {x} mem))
1984 (Move {t} [n] dst1 src1 vardef:(VarDef {x} move:(Move {t} [n] dst2 _ mem)))
1985 && move.Uses == 1 && vardef.Uses == 1
1986 && isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
1987 && clobber(move) && clobber(vardef)
1988 -> (Move {t} [n] dst1 src1 (VarDef {x} mem))
1989 (Store {t1} op1:(OffPtr [o1] p1) d1
1990 m2:(Store {t2} op2:(OffPtr [0] p2) d2
1991 m3:(Move [n] p3 _ mem)))
1992 && m2.Uses == 1 && m3.Uses == 1
1993 && o1 == sizeof(t2)
1994 && n == sizeof(t2) + sizeof(t1)
1995 && isSamePtr(p1, p2) && isSamePtr(p2, p3)
1996 && clobber(m2) && clobber(m3)
1997 -> (Store {t1} op1 d1 (Store {t2} op2 d2 mem))
1998 (Store {t1} op1:(OffPtr [o1] p1) d1
1999 m2:(Store {t2} op2:(OffPtr [o2] p2) d2
2000 m3:(Store {t3} op3:(OffPtr [0] p3) d3
2001 m4:(Move [n] p4 _ mem))))
2002 && m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1
2003 && o2 == sizeof(t3)
2004 && o1-o2 == sizeof(t2)
2005 && n == sizeof(t3) + sizeof(t2) + sizeof(t1)
2006 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
2007 && clobber(m2) && clobber(m3) && clobber(m4)
2008 -> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 mem)))
2009 (Store {t1} op1:(OffPtr [o1] p1) d1
2010 m2:(Store {t2} op2:(OffPtr [o2] p2) d2
2011 m3:(Store {t3} op3:(OffPtr [o3] p3) d3
2012 m4:(Store {t4} op4:(OffPtr [0] p4) d4
2013 m5:(Move [n] p5 _ mem)))))
2014 && m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1 && m5.Uses == 1
2015 && o3 == sizeof(t4)
2016 && o2-o3 == sizeof(t3)
2017 && o1-o2 == sizeof(t2)
2018 && n == sizeof(t4) + sizeof(t3) + sizeof(t2) + sizeof(t1)
2019 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
2020 && clobber(m2) && clobber(m3) && clobber(m4) && clobber(m5)
2021 -> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 (Store {t4} op4 d4 mem))))
2022
2023 // Don't Zero variables that are immediately completely overwritten
2024 // before being accessed.
2025 (Move {t} [n] dst1 src1 zero:(Zero {t} [n] dst2 mem))
2026 && zero.Uses == 1
2027 && isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
2028 && clobber(zero)
2029 -> (Move {t} [n] dst1 src1 mem)
2030 (Move {t} [n] dst1 src1 vardef:(VarDef {x} zero:(Zero {t} [n] dst2 mem)))
2031 && zero.Uses == 1 && vardef.Uses == 1
2032 && isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
2033 && clobber(zero) && clobber(vardef)
2034 -> (Move {t} [n] dst1 src1 (VarDef {x} mem))
2035 (Store {t1} op1:(OffPtr [o1] p1) d1
2036 m2:(Store {t2} op2:(OffPtr [0] p2) d2
2037 m3:(Zero [n] p3 mem)))
2038 && m2.Uses == 1 && m3.Uses == 1
2039 && o1 == sizeof(t2)
2040 && n == sizeof(t2) + sizeof(t1)
2041 && isSamePtr(p1, p2) && isSamePtr(p2, p3)
2042 && clobber(m2) && clobber(m3)
2043 -> (Store {t1} op1 d1 (Store {t2} op2 d2 mem))
2044 (Store {t1} op1:(OffPtr [o1] p1) d1
2045 m2:(Store {t2} op2:(OffPtr [o2] p2) d2
2046 m3:(Store {t3} op3:(OffPtr [0] p3) d3
2047 m4:(Zero [n] p4 mem))))
2048 && m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1
2049 && o2 == sizeof(t3)
2050 && o1-o2 == sizeof(t2)
2051 && n == sizeof(t3) + sizeof(t2) + sizeof(t1)
2052 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
2053 && clobber(m2) && clobber(m3) && clobber(m4)
2054 -> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 mem)))
2055 (Store {t1} op1:(OffPtr [o1] p1) d1
2056 m2:(Store {t2} op2:(OffPtr [o2] p2) d2
2057 m3:(Store {t3} op3:(OffPtr [o3] p3) d3
2058 m4:(Store {t4} op4:(OffPtr [0] p4) d4
2059 m5:(Zero [n] p5 mem)))))
2060 && m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1 && m5.Uses == 1
2061 && o3 == sizeof(t4)
2062 && o2-o3 == sizeof(t3)
2063 && o1-o2 == sizeof(t2)
2064 && n == sizeof(t4) + sizeof(t3) + sizeof(t2) + sizeof(t1)
2065 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
2066 && clobber(m2) && clobber(m3) && clobber(m4) && clobber(m5)
2067 -> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 (Store {t4} op4 d4 mem))))
2068
2069 // Don't Move from memory if the values are likely to already be
2070 // in registers.
2071 (Move {t1} [n] dst p1
2072 mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2073 (Store {t3} op3:(OffPtr <tt3> [0] p3) d2 _)))
2074 && isSamePtr(p1, p2) && isSamePtr(p2, p3)
2075 && alignof(t2) <= alignof(t1)
2076 && alignof(t3) <= alignof(t1)
2077 && registerizable(b, t2)
2078 && registerizable(b, t3)
2079 && o2 == sizeof(t3)
2080 && n == sizeof(t2) + sizeof(t3)
2081 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2082 (Store {t3} (OffPtr <tt3> [0] dst) d2 mem))
2083 (Move {t1} [n] dst p1
2084 mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2085 (Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
2086 (Store {t4} op4:(OffPtr <tt4> [0] p4) d3 _))))
2087 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
2088 && alignof(t2) <= alignof(t1)
2089 && alignof(t3) <= alignof(t1)
2090 && alignof(t4) <= alignof(t1)
2091 && registerizable(b, t2)
2092 && registerizable(b, t3)
2093 && registerizable(b, t4)
2094 && o3 == sizeof(t4)
2095 && o2-o3 == sizeof(t3)
2096 && n == sizeof(t2) + sizeof(t3) + sizeof(t4)
2097 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2098 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2099 (Store {t4} (OffPtr <tt4> [0] dst) d3 mem)))
2100 (Move {t1} [n] dst p1
2101 mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2102 (Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
2103 (Store {t4} op4:(OffPtr <tt4> [o4] p4) d3
2104 (Store {t5} op5:(OffPtr <tt5> [0] p5) d4 _)))))
2105 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
2106 && alignof(t2) <= alignof(t1)
2107 && alignof(t3) <= alignof(t1)
2108 && alignof(t4) <= alignof(t1)
2109 && alignof(t5) <= alignof(t1)
2110 && registerizable(b, t2)
2111 && registerizable(b, t3)
2112 && registerizable(b, t4)
2113 && registerizable(b, t5)
2114 && o4 == sizeof(t5)
2115 && o3-o4 == sizeof(t4)
2116 && o2-o3 == sizeof(t3)
2117 && n == sizeof(t2) + sizeof(t3) + sizeof(t4) + sizeof(t5)
2118 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2119 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2120 (Store {t4} (OffPtr <tt4> [o4] dst) d3
2121 (Store {t5} (OffPtr <tt5> [0] dst) d4 mem))))
2122
2123 // Same thing but with VarDef in the middle.
2124 (Move {t1} [n] dst p1
2125 mem:(VarDef
2126 (Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2127 (Store {t3} op3:(OffPtr <tt3> [0] p3) d2 _))))
2128 && isSamePtr(p1, p2) && isSamePtr(p2, p3)
2129 && alignof(t2) <= alignof(t1)
2130 && alignof(t3) <= alignof(t1)
2131 && registerizable(b, t2)
2132 && registerizable(b, t3)
2133 && o2 == sizeof(t3)
2134 && n == sizeof(t2) + sizeof(t3)
2135 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2136 (Store {t3} (OffPtr <tt3> [0] dst) d2 mem))
2137 (Move {t1} [n] dst p1
2138 mem:(VarDef
2139 (Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2140 (Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
2141 (Store {t4} op4:(OffPtr <tt4> [0] p4) d3 _)))))
2142 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
2143 && alignof(t2) <= alignof(t1)
2144 && alignof(t3) <= alignof(t1)
2145 && alignof(t4) <= alignof(t1)
2146 && registerizable(b, t2)
2147 && registerizable(b, t3)
2148 && registerizable(b, t4)
2149 && o3 == sizeof(t4)
2150 && o2-o3 == sizeof(t3)
2151 && n == sizeof(t2) + sizeof(t3) + sizeof(t4)
2152 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2153 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2154 (Store {t4} (OffPtr <tt4> [0] dst) d3 mem)))
2155 (Move {t1} [n] dst p1
2156 mem:(VarDef
2157 (Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2158 (Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
2159 (Store {t4} op4:(OffPtr <tt4> [o4] p4) d3
2160 (Store {t5} op5:(OffPtr <tt5> [0] p5) d4 _))))))
2161 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
2162 && alignof(t2) <= alignof(t1)
2163 && alignof(t3) <= alignof(t1)
2164 && alignof(t4) <= alignof(t1)
2165 && alignof(t5) <= alignof(t1)
2166 && registerizable(b, t2)
2167 && registerizable(b, t3)
2168 && registerizable(b, t4)
2169 && registerizable(b, t5)
2170 && o4 == sizeof(t5)
2171 && o3-o4 == sizeof(t4)
2172 && o2-o3 == sizeof(t3)
2173 && n == sizeof(t2) + sizeof(t3) + sizeof(t4) + sizeof(t5)
2174 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2175 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2176 (Store {t4} (OffPtr <tt4> [o4] dst) d3
2177 (Store {t5} (OffPtr <tt5> [0] dst) d4 mem))))
2178
2179 // Prefer to Zero and Store than to Move.
2180 (Move {t1} [n] dst p1
2181 mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2182 (Zero {t3} [n] p3 _)))
2183 && isSamePtr(p1, p2) && isSamePtr(p2, p3)
2184 && alignof(t2) <= alignof(t1)
2185 && alignof(t3) <= alignof(t1)
2186 && registerizable(b, t2)
2187 && n >= o2 + sizeof(t2)
2188 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2189 (Zero {t1} [n] dst mem))
2190 (Move {t1} [n] dst p1
2191 mem:(Store {t2} (OffPtr <tt2> [o2] p2) d1
2192 (Store {t3} (OffPtr <tt3> [o3] p3) d2
2193 (Zero {t4} [n] p4 _))))
2194 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
2195 && alignof(t2) <= alignof(t1)
2196 && alignof(t3) <= alignof(t1)
2197 && alignof(t4) <= alignof(t1)
2198 && registerizable(b, t2)
2199 && registerizable(b, t3)
2200 && n >= o2 + sizeof(t2)
2201 && n >= o3 + sizeof(t3)
2202 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2203 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2204 (Zero {t1} [n] dst mem)))
2205 (Move {t1} [n] dst p1
2206 mem:(Store {t2} (OffPtr <tt2> [o2] p2) d1
2207 (Store {t3} (OffPtr <tt3> [o3] p3) d2
2208 (Store {t4} (OffPtr <tt4> [o4] p4) d3
2209 (Zero {t5} [n] p5 _)))))
2210 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
2211 && alignof(t2) <= alignof(t1)
2212 && alignof(t3) <= alignof(t1)
2213 && alignof(t4) <= alignof(t1)
2214 && alignof(t5) <= alignof(t1)
2215 && registerizable(b, t2)
2216 && registerizable(b, t3)
2217 && registerizable(b, t4)
2218 && n >= o2 + sizeof(t2)
2219 && n >= o3 + sizeof(t3)
2220 && n >= o4 + sizeof(t4)
2221 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2222 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2223 (Store {t4} (OffPtr <tt4> [o4] dst) d3
2224 (Zero {t1} [n] dst mem))))
2225 (Move {t1} [n] dst p1
2226 mem:(Store {t2} (OffPtr <tt2> [o2] p2) d1
2227 (Store {t3} (OffPtr <tt3> [o3] p3) d2
2228 (Store {t4} (OffPtr <tt4> [o4] p4) d3
2229 (Store {t5} (OffPtr <tt5> [o5] p5) d4
2230 (Zero {t6} [n] p6 _))))))
2231 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5) && isSamePtr(p5, p6)
2232 && alignof(t2) <= alignof(t1)
2233 && alignof(t3) <= alignof(t1)
2234 && alignof(t4) <= alignof(t1)
2235 && alignof(t5) <= alignof(t1)
2236 && alignof(t6) <= alignof(t1)
2237 && registerizable(b, t2)
2238 && registerizable(b, t3)
2239 && registerizable(b, t4)
2240 && registerizable(b, t5)
2241 && n >= o2 + sizeof(t2)
2242 && n >= o3 + sizeof(t3)
2243 && n >= o4 + sizeof(t4)
2244 && n >= o5 + sizeof(t5)
2245 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2246 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2247 (Store {t4} (OffPtr <tt4> [o4] dst) d3
2248 (Store {t5} (OffPtr <tt5> [o5] dst) d4
2249 (Zero {t1} [n] dst mem)))))
2250 (Move {t1} [n] dst p1
2251 mem:(VarDef
2252 (Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
2253 (Zero {t3} [n] p3 _))))
2254 && isSamePtr(p1, p2) && isSamePtr(p2, p3)
2255 && alignof(t2) <= alignof(t1)
2256 && alignof(t3) <= alignof(t1)
2257 && registerizable(b, t2)
2258 && n >= o2 + sizeof(t2)
2259 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2260 (Zero {t1} [n] dst mem))
2261 (Move {t1} [n] dst p1
2262 mem:(VarDef
2263 (Store {t2} (OffPtr <tt2> [o2] p2) d1
2264 (Store {t3} (OffPtr <tt3> [o3] p3) d2
2265 (Zero {t4} [n] p4 _)))))
2266 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
2267 && alignof(t2) <= alignof(t1)
2268 && alignof(t3) <= alignof(t1)
2269 && alignof(t4) <= alignof(t1)
2270 && registerizable(b, t2)
2271 && registerizable(b, t3)
2272 && n >= o2 + sizeof(t2)
2273 && n >= o3 + sizeof(t3)
2274 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2275 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2276 (Zero {t1} [n] dst mem)))
2277 (Move {t1} [n] dst p1
2278 mem:(VarDef
2279 (Store {t2} (OffPtr <tt2> [o2] p2) d1
2280 (Store {t3} (OffPtr <tt3> [o3] p3) d2
2281 (Store {t4} (OffPtr <tt4> [o4] p4) d3
2282 (Zero {t5} [n] p5 _))))))
2283 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
2284 && alignof(t2) <= alignof(t1)
2285 && alignof(t3) <= alignof(t1)
2286 && alignof(t4) <= alignof(t1)
2287 && alignof(t5) <= alignof(t1)
2288 && registerizable(b, t2)
2289 && registerizable(b, t3)
2290 && registerizable(b, t4)
2291 && n >= o2 + sizeof(t2)
2292 && n >= o3 + sizeof(t3)
2293 && n >= o4 + sizeof(t4)
2294 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2295 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2296 (Store {t4} (OffPtr <tt4> [o4] dst) d3
2297 (Zero {t1} [n] dst mem))))
2298 (Move {t1} [n] dst p1
2299 mem:(VarDef
2300 (Store {t2} (OffPtr <tt2> [o2] p2) d1
2301 (Store {t3} (OffPtr <tt3> [o3] p3) d2
2302 (Store {t4} (OffPtr <tt4> [o4] p4) d3
2303 (Store {t5} (OffPtr <tt5> [o5] p5) d4
2304 (Zero {t6} [n] p6 _)))))))
2305 && isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5) && isSamePtr(p5, p6)
2306 && alignof(t2) <= alignof(t1)
2307 && alignof(t3) <= alignof(t1)
2308 && alignof(t4) <= alignof(t1)
2309 && alignof(t5) <= alignof(t1)
2310 && alignof(t6) <= alignof(t1)
2311 && registerizable(b, t2)
2312 && registerizable(b, t3)
2313 && registerizable(b, t4)
2314 && registerizable(b, t5)
2315 && n >= o2 + sizeof(t2)
2316 && n >= o3 + sizeof(t3)
2317 && n >= o4 + sizeof(t4)
2318 && n >= o5 + sizeof(t5)
2319 -> (Store {t2} (OffPtr <tt2> [o2] dst) d1
2320 (Store {t3} (OffPtr <tt3> [o3] dst) d2
2321 (Store {t4} (OffPtr <tt4> [o4] dst) d3
2322 (Store {t5} (OffPtr <tt5> [o5] dst) d4
2323 (Zero {t1} [n] dst mem)))))
2324
2325 (StaticCall {sym} x) && needRaceCleanup(sym,v) -> x
2326
2327 // Collapse moving A -> B -> C into just A -> C.
2328 // Later passes (deadstore, elim unread auto) will remove the A -> B move, if possible.
2329 // This happens most commonly when B is an autotmp inserted earlier
2330 // during compilation to ensure correctness.
2331 // Take care that overlapping moves are preserved.
2332 // Restrict this optimization to the stack, to avoid duplicating loads from the heap;
2333 // see CL 145208 for discussion.
2334 (Move {t1} [s] dst tmp1 midmem:(Move {t2} [s] tmp2 src _))
2335 && t1.(*types.Type).Compare(t2.(*types.Type)) == types.CMPeq
2336 && isSamePtr(tmp1, tmp2)
2337 && isStackPtr(src)
2338 && disjoint(src, s, tmp2, s)
2339 && (disjoint(src, s, dst, s) || isInlinableMemmove(dst, src, s, config))
2340 -> (Move {t1} [s] dst src midmem)
2341
2342 // Same, but for large types that require VarDefs.
2343 (Move {t1} [s] dst tmp1 midmem:(VarDef (Move {t2} [s] tmp2 src _)))
2344 && t1.(*types.Type).Compare(t2.(*types.Type)) == types.CMPeq
2345 && isSamePtr(tmp1, tmp2)
2346 && isStackPtr(src)
2347 && disjoint(src, s, tmp2, s)
2348 && (disjoint(src, s, dst, s) || isInlinableMemmove(dst, src, s, config))
2349 -> (Move {t1} [s] dst src midmem)
2350
2351 // Elide self-moves. This only happens rarely (e.g test/fixedbugs/bug277.go).
2352 // However, this rule is needed to prevent the previous rule from looping forever in such cases.
2353 (Move dst src mem) && isSamePtr(dst, src) -> mem
View as plain text