|
131
|
1 @c Copyright (C) 2014-2018 Free Software Foundation, Inc.
|
|
111
|
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))
|
|
|
42 @deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, tree, tree, gimple_seq *, tree (*)(tree))
|
|
|
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);
|
|
|
67 @deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum built_in_function, tree, tree, tree, tree, tree (*valueize) (tree) = NULL);
|
|
|
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
|
|
|
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
|
|
|
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)
|
|
|
125 (if (!integer_zerop (@@1))
|
|
|
126 @@0))
|
|
|
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
|
|
|
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.
|
|
|
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
|
|
|
158 Note that @code{if}s in outer position do not have the optional
|
|
|
159 else clause but instead have multiple then clauses.
|
|
|
160
|
|
|
161 Ifs can be nested.
|
|
|
162
|
|
|
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
|
|
|
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 @{
|
|
131
|
208 poly_int64 off;
|
|
111
|
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
|
|
|
235 Here we introduce flags on match expressions. The flag used
|
|
|
236 above, @code{c}, denotes that the expression should
|
|
|
237 be also matched commutated. Thus the above match expression
|
|
|
238 is really the following four match expressions:
|
|
|
239
|
|
|
240 @smallexample
|
|
|
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)
|
|
|
245 @end smallexample
|
|
|
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
|
|
|
251 The second supported flag is @code{s} which tells the code
|
|
|
252 generator to fail the pattern if the expression marked with
|
|
131
|
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
|
|
111
|
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.
|
|
131
|
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.
|
|
111
|
274
|
|
|
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
|
|
|
296 @code{opa, opb, opc} being @code{plus, minus, plus},
|
|
|
297 @code{plus, minus, minus}, @code{minus, plus, plus},
|
|
|
298 @code{minus, plus, minus}.
|
|
|
299
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
364 As intermediate conversions are often optional there is a way to
|
|
|
365 avoid the need to repeat patterns both with and without such
|
|
|
366 conversions. Namely you can mark a conversion as being optional
|
|
|
367 with a @code{?}:
|
|
|
368
|
|
|
369 @smallexample
|
|
|
370 (simplify
|
|
|
371 (eq (convert@@0 @@1) (convert@? @@2))
|
|
|
372 (eq @@1 (convert @@2)))
|
|
|
373 @end smallexample
|
|
|
374
|
|
|
375 which will match both @code{(eq (convert @@1) (convert @@2))} and
|
|
|
376 @code{(eq (convert @@1) @@2)}. The optional converts are supposed
|
|
|
377 to be all either present or not, thus
|
|
|
378 @code{(eq (convert@? @@1) (convert@? @@2))} will result in two
|
|
|
379 patterns only. If you want to match all four combinations you
|
|
|
380 have access to two additional conditional converts as in
|
|
|
381 @code{(eq (convert1@? @@1) (convert2@? @@2))}.
|
|
|
382
|
|
|
383 Predicates available from the GCC middle-end need to be made
|
|
|
384 available explicitely via @code{define_predicates}:
|
|
|
385
|
|
|
386 @smallexample
|
|
|
387 (define_predicates
|
|
|
388 integer_onep integer_zerop integer_all_onesp)
|
|
|
389 @end smallexample
|
|
|
390
|
|
|
391 You can also define predicates using the pattern matching language
|
|
|
392 and the @code{match} form:
|
|
|
393
|
|
|
394 @smallexample
|
|
|
395 (match negate_expr_p
|
|
|
396 INTEGER_CST
|
|
|
397 (if (TYPE_OVERFLOW_WRAPS (type)
|
|
|
398 || may_negate_without_overflow_p (t))))
|
|
|
399 (match negate_expr_p
|
|
|
400 (negate @@0))
|
|
|
401 @end smallexample
|
|
|
402
|
|
|
403 This shows that for @code{match} expressions there is @code{t}
|
|
|
404 available which captures the outermost expression (something
|
|
|
405 not possible in the @code{simplify} context). As you can see
|
|
|
406 @code{match} has an identifier as first operand which is how
|
|
|
407 you refer to the predicate in patterns. Multiple @code{match}
|
|
|
408 for the same identifier add additional cases where the predicate
|
|
|
409 matches.
|
|
|
410
|
|
|
411 Predicates can also match an expression in which case you need
|
|
|
412 to provide a template specifying the identifier and where to
|
|
|
413 get its operands from:
|
|
|
414
|
|
|
415 @smallexample
|
|
|
416 (match (logical_inverted_value @@0)
|
|
|
417 (eq @@0 integer_zerop))
|
|
|
418 (match (logical_inverted_value @@0)
|
|
|
419 (bit_not truth_valued_p@@0))
|
|
|
420 @end smallexample
|
|
|
421
|
|
|
422 You can use the above predicate like
|
|
|
423
|
|
|
424 @smallexample
|
|
|
425 (simplify
|
|
|
426 (bit_and @@0 (logical_inverted_value @@0))
|
|
|
427 @{ build_zero_cst (type); @})
|
|
|
428 @end smallexample
|
|
|
429
|
|
|
430 Which will match a bitwise and of an operand with its logical
|
|
|
431 inverted value.
|
|
|
432
|
