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