]>
Commit | Line | Data |
---|---|---|
c63539ff ML |
1 | .. |
2 | Copyright 1988-2022 Free Software Foundation, Inc. | |
3 | This is part of the GCC manual. | |
4 | For copying conditions, see the copyright.rst file. | |
5 | ||
6 | .. index:: The Language | |
7 | ||
8 | .. _the-language: | |
9 | ||
10 | The Language | |
11 | ************ | |
12 | ||
13 | The language in which to write expression simplifications resembles | |
14 | other domain-specific languages GCC uses. Thus it is lispy. Let's | |
15 | start with an example from the match.pd file: | |
16 | ||
17 | .. code-block:: | |
18 | ||
19 | (simplify | |
20 | (bit_and @0 integer_all_onesp) | |
21 | @0) | |
22 | ||
23 | This example contains all required parts of an expression simplification. | |
24 | A simplification is wrapped inside a ``(simplify ...)`` expression. | |
25 | That contains at least two operands - an expression that is matched | |
26 | with the GIMPLE or GENERIC IL and a replacement expression that is | |
27 | returned if the match was successful. | |
28 | ||
29 | Expressions have an operator ID, ``bit_and`` in this case. Expressions can | |
30 | be lower-case tree codes with ``_expr`` stripped off or builtin | |
31 | function code names in all-caps, like ``BUILT_IN_SQRT``. | |
32 | ||
33 | ``@n`` denotes a so-called capture. It captures the operand and lets | |
34 | you refer to it in other places of the match-and-simplify. In the | |
35 | above example it is referred to in the replacement expression. Captures | |
36 | are ``@`` followed by a number or an identifier. | |
37 | ||
38 | .. code-block:: | |
39 | ||
40 | (simplify | |
41 | (bit_xor @0 @0) | |
42 | { build_zero_cst (type); }) | |
43 | ||
44 | In this example ``@0`` is mentioned twice which constrains the matched | |
45 | expression to have two equal operands. Usually matches are constrained | |
46 | to equal types. If operands may be constants and conversions are involved, | |
47 | matching by value might be preferred in which case use ``@@0`` to | |
48 | denote a by-value match and the specific operand you want to refer to | |
49 | in the result part. This example also introduces | |
50 | operands written in C code. These can be used in the expression | |
51 | replacements and are supposed to evaluate to a tree node which has to | |
52 | be a valid GIMPLE operand (so you cannot generate expressions in C code). | |
53 | ||
54 | .. code-block:: | |
55 | ||
56 | (simplify | |
57 | (trunc_mod integer_zerop@0 @1) | |
58 | (if (!integer_zerop (@1)) | |
59 | @0)) | |
60 | ||
61 | Here ``@0`` captures the first operand of the trunc_mod expression | |
62 | which is also predicated with ``integer_zerop``. Expression operands | |
63 | may be either expressions, predicates or captures. Captures | |
64 | can be unconstrained or capture expressions or predicates. | |
65 | ||
66 | This example introduces an optional operand of simplify, | |
67 | the if-expression. This condition is evaluated after the | |
68 | expression matched in the IL and is required to evaluate to true | |
69 | to enable the replacement expression in the second operand | |
70 | position. The expression operand of the ``if`` is a standard C | |
71 | expression which may contain references to captures. The ``if`` | |
72 | has an optional third operand which may contain the replacement | |
73 | expression that is enabled when the condition evaluates to false. | |
74 | ||
75 | A ``if`` expression can be used to specify a common condition | |
76 | for multiple simplify patterns, avoiding the need | |
77 | to repeat that multiple times: | |
78 | ||
79 | .. code-block:: | |
80 | ||
81 | (if (!TYPE_SATURATING (type) | |
82 | && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type)) | |
83 | (simplify | |
84 | (minus (plus @0 @1) @0) | |
85 | @1) | |
86 | (simplify | |
87 | (minus (minus @0 @1) @0) | |
88 | (negate @1))) | |
89 | ||
90 | Note that ``if`` s in outer position do not have the optional | |
91 | else clause but instead have multiple then clauses. | |
92 | ||
93 | Ifs can be nested. | |
94 | ||
95 | There exists a ``switch`` expression which can be used to | |
96 | chain conditions avoiding nesting ``if`` s too much: | |
97 | ||
98 | .. code-block:: | |
99 | ||
100 | (simplify | |
101 | (simple_comparison @0 REAL_CST@1) | |
102 | (switch | |
103 | /* a CMP (-0) -> a CMP 0 */ | |
104 | (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1))) | |
105 | (cmp @0 { build_real (TREE_TYPE (@1), dconst0); })) | |
106 | /* x != NaN is always true, other ops are always false. */ | |
107 | (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1)) | |
108 | && ! HONOR_SNANS (@1)) | |
109 | { constant_boolean_node (cmp == NE_EXPR, type); }))) | |
110 | ||
111 | Is equal to | |
112 | ||
113 | .. code-block:: | |
114 | ||
115 | (simplify | |
116 | (simple_comparison @0 REAL_CST@1) | |
117 | (switch | |
118 | /* a CMP (-0) -> a CMP 0 */ | |
119 | (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1))) | |
120 | (cmp @0 { build_real (TREE_TYPE (@1), dconst0); }) | |
121 | /* x != NaN is always true, other ops are always false. */ | |
122 | (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1)) | |
123 | && ! HONOR_SNANS (@1)) | |
124 | { constant_boolean_node (cmp == NE_EXPR, type); })))) | |
125 | ||
126 | which has the second ``if`` in the else operand of the first. | |
127 | The ``switch`` expression takes ``if`` expressions as | |
128 | operands (which may not have else clauses) and as a last operand | |
129 | a replacement expression which should be enabled by default if | |
130 | no other condition evaluated to true. | |
131 | ||
132 | Captures can also be used for capturing results of sub-expressions. | |
133 | ||
134 | .. code-block:: | |
135 | ||
136 | #if GIMPLE | |
137 | (simplify | |
138 | (pointer_plus (addr@2 @0) INTEGER_CST_P@1) | |
139 | (if (is_gimple_min_invariant (@2))) | |
140 | { | |
141 | poly_int64 off; | |
142 | tree base = get_addr_base_and_unit_offset (@0, &off); | |
143 | off += tree_to_uhwi (@1); | |
144 | /* Now with that we should be able to simply write | |
145 | (addr (mem_ref (addr @base) (plus @off @1))) */ | |
146 | build1 (ADDR_EXPR, type, | |
147 | build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)), | |
148 | build_fold_addr_expr (base), | |
149 | build_int_cst (ptr_type_node, off))); | |
150 | }) | |
151 | #endif | |
152 | ||
153 | In the above example, ``@2`` captures the result of the expression | |
154 | ``(addr @0)``. For the outermost expression only its type can be | |
155 | captured, and the keyword ``type`` is reserved for this purpose. The | |
156 | above example also gives a way to conditionalize patterns to only apply | |
157 | to ``GIMPLE`` or ``GENERIC`` by means of using the pre-defined | |
158 | preprocessor macros ``GIMPLE`` and ``GENERIC`` and using | |
159 | preprocessor directives. | |
160 | ||
161 | .. code-block:: | |
162 | ||
163 | (simplify | |
164 | (bit_and:c integral_op_p@0 (bit_ior:c (bit_not @0) @1)) | |
165 | (bit_and @1 @0)) | |
166 | ||
167 | Here we introduce flags on match expressions. The flag used | |
168 | above, ``c``, denotes that the expression should | |
169 | be also matched commutated. Thus the above match expression | |
170 | is really the following four match expressions: | |
171 | ||
172 | .. code-block:: | |
173 | ||
174 | (bit_and integral_op_p@0 (bit_ior (bit_not @0) @1)) | |
175 | (bit_and (bit_ior (bit_not @0) @1) integral_op_p@0) | |
176 | (bit_and integral_op_p@0 (bit_ior @1 (bit_not @0))) | |
177 | (bit_and (bit_ior @1 (bit_not @0)) integral_op_p@0) | |
178 | ||
179 | Usual canonicalizations you know from GENERIC expressions are | |
180 | applied before matching, so for example constant operands always | |
181 | come second in commutative expressions. | |
182 | ||
183 | The second supported flag is ``s`` which tells the code | |
184 | generator to fail the pattern if the expression marked with | |
185 | ``s`` does have more than one use and the simplification | |
186 | results in an expression with more than one operator. | |
187 | For example in | |
188 | ||
189 | .. code-block:: | |
190 | ||
191 | (simplify | |
192 | (pointer_plus (pointer_plus:s @0 @1) @3) | |
193 | (pointer_plus @0 (plus @1 @3))) | |
194 | ||
195 | this avoids the association if ``(pointer_plus @0 @1)`` is | |
196 | used outside of the matched expression and thus it would stay | |
197 | live and not trivially removed by dead code elimination. | |
198 | Now consider ``((x + 3) + -3)`` with the temporary | |
199 | holding ``(x + 3)`` used elsewhere. This simplifies down | |
200 | to ``x`` which is desirable and thus flagging with ``s`` | |
201 | does not prevent the transform. Now consider ``((x + 3) + 1)`` | |
202 | which simplifies to ``(x + 4)``. Despite being flagged with | |
203 | ``s`` the simplification will be performed. The | |
204 | simplification of ``((x + a) + 1)`` to ``(x + (a + 1))`` will | |
205 | not performed in this case though. | |
206 | ||
207 | More features exist to avoid too much repetition. | |
208 | ||
209 | .. code-block:: | |
210 | ||
211 | (for op (plus pointer_plus minus bit_ior bit_xor) | |
212 | (simplify | |
213 | (op @0 integer_zerop) | |
214 | @0)) | |
215 | ||
216 | A ``for`` expression can be used to repeat a pattern for each | |
217 | operator specified, substituting ``op``. ``for`` can be | |
218 | nested and a ``for`` can have multiple operators to iterate. | |
219 | ||
220 | .. code-block:: | |
221 | ||
222 | (for opa (plus minus) | |
223 | opb (minus plus) | |
224 | (for opc (plus minus) | |
225 | (simplify... | |
226 | ||
227 | In this example the pattern will be repeated four times with | |
228 | ``opa, opb, opc`` being ``plus, minus, plus`` ; | |
229 | ``plus, minus, minus`` ; ``minus, plus, plus`` ; | |
230 | ``minus, plus, minus``. | |
231 | ||
232 | To avoid repeating operator lists in ``for`` you can name | |
233 | them via | |
234 | ||
235 | .. code-block:: c++ | |
236 | ||
237 | (define_operator_list pmm plus minus mult) | |
238 | ||
239 | and use them in ``for`` operator lists where they get expanded. | |
240 | ||
241 | .. code-block:: c++ | |
242 | ||
243 | (for opa (pmm trunc_div) | |
244 | (simplify... | |
245 | ||
246 | So this example iterates over ``plus``, ``minus``, ``mult`` | |
247 | and ``trunc_div``. | |
248 | ||
249 | Using operator lists can also remove the need to explicitly write | |
250 | a ``for``. All operator list uses that appear in a ``simplify`` | |
251 | or ``match`` pattern in operator positions will implicitly | |
252 | be added to a new ``for``. For example | |
253 | ||
254 | .. code-block:: | |
255 | ||
256 | (define_operator_list SQRT BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL) | |
257 | (define_operator_list POW BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL) | |
258 | (simplify | |
259 | (SQRT (POW @0 @1)) | |
260 | (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); }))) | |
261 | ||
262 | is the same as | |
263 | ||
264 | .. code-block:: | |
265 | ||
266 | (for SQRT (BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL) | |
267 | POW (BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL) | |
268 | (simplify | |
269 | (SQRT (POW @0 @1)) | |
270 | (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); })))) | |
271 | ||
272 | ``for`` s and operator lists can include the special identifier | |
273 | ``null`` that matches nothing and can never be generated. This can | |
274 | be used to pad an operator list so that it has a standard form, | |
275 | even if there isn't a suitable operator for every form. | |
276 | ||
277 | Another building block are ``with`` expressions in the | |
278 | result expression which nest the generated code in a new C block | |
279 | followed by its argument: | |
280 | ||
281 | .. code-block:: | |
282 | ||
283 | (simplify | |
284 | (convert (mult @0 @1)) | |
285 | (with { tree utype = unsigned_type_for (type); } | |
286 | (convert (mult (convert:utype @0) (convert:utype @1))))) | |
287 | ||
288 | This allows code nested in the ``with`` to refer to the declared | |
289 | variables. In the above case we use the feature to specify the | |
290 | type of a generated expression with the ``:type`` syntax where | |
291 | ``type`` needs to be an identifier that refers to the desired type. | |
292 | Usually the types of the generated result expressions are | |
293 | determined from the context, but sometimes like in the above case | |
294 | it is required that you specify them explicitly. | |
295 | ||
296 | Another modifier for generated expressions is ``!`` which | |
297 | tells the machinery to only consider the simplification in case | |
298 | the marked expression simplified to a simple operand. Consider | |
299 | for example | |
300 | ||
301 | .. code-block:: | |
302 | ||
303 | (simplify | |
304 | (plus (vec_cond:s @0 @1 @2) @3) | |
305 | (vec_cond @0 (plus! @1 @3) (plus! @2 @3))) | |
306 | ||
307 | which moves the outer ``plus`` operation to the inner arms | |
308 | of the ``vec_cond`` expression but only if the actual plus | |
309 | operations both simplify. Note that on ``GENERIC`` a simple | |
310 | operand means that the result satisfies ``!EXPR_P`` which | |
311 | can be limiting if the operation itself simplifies but the | |
312 | remaining operand is an (unrelated) expression. | |
313 | ||
314 | As intermediate conversions are often optional there is a way to | |
315 | avoid the need to repeat patterns both with and without such | |
316 | conversions. Namely you can mark a conversion as being optional | |
317 | with a ``?`` : | |
318 | ||
319 | .. code-block:: | |
320 | ||
321 | (simplify | |
322 | (eq (convert@0 @1) (convert? @2)) | |
323 | (eq @1 (convert @2))) | |
324 | ||
325 | which will match both ``(eq (convert @1) (convert @2))`` and | |
326 | ``(eq (convert @1) @2)``. The optional converts are supposed | |
327 | to be all either present or not, thus | |
328 | ``(eq (convert? @1) (convert? @2))`` will result in two | |
329 | patterns only. If you want to match all four combinations you | |
330 | have access to two additional conditional converts as in | |
331 | ``(eq (convert1? @1) (convert2? @2))``. | |
332 | ||
333 | The support for ``?`` marking extends to all unary operations | |
334 | including predicates you declare yourself with ``match``. | |
335 | ||
336 | Predicates available from the GCC middle-end need to be made | |
337 | available explicitly via ``define_predicates`` : | |
338 | ||
339 | .. code-block:: | |
340 | ||
341 | (define_predicates | |
342 | integer_onep integer_zerop integer_all_onesp) | |
343 | ||
344 | You can also define predicates using the pattern matching language | |
345 | and the ``match`` form: | |
346 | ||
347 | .. code-block:: | |
348 | ||
349 | (match negate_expr_p | |
350 | INTEGER_CST | |
351 | (if (TYPE_OVERFLOW_WRAPS (type) | |
352 | || may_negate_without_overflow_p (t)))) | |
353 | (match negate_expr_p | |
354 | (negate @0)) | |
355 | ||
356 | This shows that for ``match`` expressions there is ``t`` | |
357 | available which captures the outermost expression (something | |
358 | not possible in the ``simplify`` context). As you can see | |
359 | ``match`` has an identifier as first operand which is how | |
360 | you refer to the predicate in patterns. Multiple ``match`` | |
361 | for the same identifier add additional cases where the predicate | |
362 | matches. | |
363 | ||
364 | Predicates can also match an expression in which case you need | |
365 | to provide a template specifying the identifier and where to | |
366 | get its operands from: | |
367 | ||
368 | .. code-block:: | |
369 | ||
370 | (match (logical_inverted_value @0) | |
371 | (eq @0 integer_zerop)) | |
372 | (match (logical_inverted_value @0) | |
373 | (bit_not truth_valued_p@0)) | |
374 | ||
375 | You can use the above predicate like | |
376 | ||
377 | .. code-block:: | |
378 | ||
379 | (simplify | |
380 | (bit_and @0 (logical_inverted_value @0)) | |
381 | { build_zero_cst (type); }) | |
382 | ||
383 | Which will match a bitwise and of an operand with its logical | |
3ed1b4ce | 384 | inverted value. |