1@c Copyright (C) 2014-2020 Free Software Foundation, Inc.
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
10The GIMPLE and GENERIC pattern matching project match-and-simplify
11tries 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
22To address these the project introduces a simple domain specific language
23to write expression simplifications from which code targeting GIMPLE
24and GENERIC is auto-generated.  The GENERIC variant follows the
25fold_buildN API while for the GIMPLE variant and to address 2) new
26APIs 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))
43The main GIMPLE API entry to the expression simplifications mimicing
44that of the GENERIC fold_@{unary,binary,ternary@} functions.
45@end deftypefn
46
47thus providing n-ary overloads for operation or function.  The
48additional arguments are a gimple_seq where built statements are
49inserted on (if @code{NULL} then simplifications requiring new statements
50are not performed) and a valueization hook that can be used to
51tie simplifications to a SSA lattice.
52
53In addition to those APIs @code{fold_stmt} is overloaded with
54a valueization hook:
55
56@deftypefn bool fold_stmt (gimple_stmt_iterator *, tree (*)(tree));
57@end deftypefn
58
59
60Ontop 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
71which is supposed to replace @code{force_gimple_operand (fold_buildN (...), ...)}
72and calls to @code{fold_convert}.  Overloads without the @code{location_t}
73argument exist.  Built statements are inserted on the provided sequence
74and simplification is performed using the optional valueization hook.
75
76
77@node The Language
78@section The Language
79@cindex The Language
80
81The language to write expression simplifications in resembles other
82domain-specific languages GCC uses.  Thus it is lispy.  Lets start
83with 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
91This example contains all required parts of an expression simplification.
92A simplification is wrapped inside a @code{(simplify ...)} expression.
93That contains at least two operands - an expression that is matched
94with the GIMPLE or GENERIC IL and a replacement expression that is
95returned if the match was successful.
96
97Expressions have an operator ID, @code{bit_and} in this case.  Expressions can
98be lower-case tree codes with @code{_expr} stripped off or builtin
99function 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
102you refer to it in other places of the match-and-simplify.  In the
103above example it is refered to in the replacement expression.  Captures
104are @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
112In this example @code{@@0} is mentioned twice which constrains the matched
113expression to have two equal operands.  Usually matches are constraint
114to equal types.  If operands may be constants and conversions are involved
115matching by value might be preferred in which case use @code{@@@@0} to
116denote a by value match and the specific operand you want to refer to
117in the result part.  This example also introduces
118operands written in C code.  These can be used in the expression
119replacements and are supposed to evaluate to a tree node which has to
120be 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
129Here @code{@@0} captures the first operand of the trunc_mod expression
130which is also predicated with @code{integer_zerop}.  Expression operands
131may be either expressions, predicates or captures.  Captures
132can be unconstrained or capture expresions or predicates.
133
134This example introduces an optional operand of simplify,
135the if-expression.  This condition is evaluated after the
136expression matched in the IL and is required to evaluate to true
137to enable the replacement expression in the second operand
138position.  The expression operand of the @code{if} is a standard C
139expression which may contain references to captures.  The @code{if}
140has an optional third operand which may contain the replacement
141expression that is enabled when the condition evaluates to false.
142
143A @code{if} expression can be used to specify a common condition
144for multiple simplify patterns, avoiding the need
145to 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
158Note that @code{if}s in outer position do not have the optional
159else clause but instead have multiple then clauses.
160
161Ifs can be nested.
162
163There exists a @code{switch} expression which can be used to
164chain 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
179Is 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
194which has the second @code{if} in the else operand of the first.
195The @code{switch} expression takes @code{if} expressions as
196operands (which may not have else clauses) and as a last operand
197a replacement expression which should be enabled by default if
198no other condition evaluated to true.
199
200Captures 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  @{
208    poly_int64 off;
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
221In the above example, @code{@@2} captures the result of the expression
222@code{(addr @@0)}.  For outermost expression only its type can be captured,
223and the keyword @code{type} is reserved for this purpose.  The above
224example also gives a way to conditionalize patterns to only apply
225to @code{GIMPLE} or @code{GENERIC} by means of using the pre-defined
226preprocessor macros @code{GIMPLE} and @code{GENERIC} and using
227preprocessor 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
235Here we introduce flags on match expressions.  The flag used
236above, @code{c}, denotes that the expression should
237be also matched commutated.  Thus the above match expression
238is 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
247Usual canonicalizations you know from GENERIC expressions are
248applied before matching, so for example constant operands always
249come second in commutative expressions.
250
251The second supported flag is @code{s} which tells the code
252generator to fail the pattern if the expression marked with
253@code{s} does have more than one use and the simplification
254results in an expression with more than one operator.
255For example in
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
263this avoids the association if @code{(pointer_plus @@0 @@1)} is
264used outside of the matched expression and thus it would stay
265live and not trivially removed by dead code elimination.
266Now consider @code{((x + 3) + -3)} with the temporary
267holding @code{(x + 3)} used elsewhere.  This simplifies down
268to @code{x} which is desirable and thus flagging with @code{s}
269does not prevent the transform.  Now consider @code{((x + 3) + 1)}
270which simplifies to @code{(x + 4)}.  Despite being flagged with
271@code{s} the simplification will be performed.  The
272simplification of @code{((x + a) + 1)} to @code{(x + (a + 1))} will
273not performed in this case though.
274
275More 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
284A @code{for} expression can be used to repeat a pattern for each
285operator specified, substituting @code{op}.  @code{for} can be
286nested 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
295In 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
300To avoid repeating operator lists in @code{for} you can name
301them via
302
303@smallexample
304(define_operator_list pmm plus minus mult)
305@end smallexample
306
307and 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
314So this example iterates over @code{plus}, @code{minus}, @code{mult}
315and @code{trunc_div}.
316
317Using operator lists can also remove the need to explicitely write
318a @code{for}.  All operator list uses that appear in a @code{simplify}
319or @code{match} pattern in operator positions will implicitely
320be 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
330is 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
342be used to pad an operator list so that it has a standard form,
343even if there isn't a suitable operator for every form.
344
345Another building block are @code{with} expressions in the
346result expression which nest the generated code in a new C block
347followed 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
356This allows code nested in the @code{with} to refer to the declared
357variables.  In the above case we use the feature to specify the
358type of a generated expression with the @code{:type} syntax where
359@code{type} needs to be an identifier that refers to the desired type.
360Usually the types of the generated result expressions are
361determined from the context, but sometimes like in the above case
362it is required that you specify them explicitely.
363
364As intermediate conversions are often optional there is a way to
365avoid the need to repeat patterns both with and without such
366conversions.  Namely you can mark a conversion as being optional
367with a @code{?}:
368
369@smallexample
370(simplify
371 (eq (convert@@0 @@1) (convert@? @@2))
372 (eq @@1 (convert @@2)))
373@end smallexample
374
375which will match both @code{(eq (convert @@1) (convert @@2))} and
376@code{(eq (convert @@1) @@2)}.  The optional converts are supposed
377to be all either present or not, thus
378@code{(eq (convert@? @@1) (convert@? @@2))} will result in two
379patterns only.  If you want to match all four combinations you
380have access to two additional conditional converts as in
381@code{(eq (convert1@? @@1) (convert2@? @@2))}.
382
383The support for @code{?} marking extends to all unary operations
384including predicates you declare yourself with @code{match}.
385
386Predicates available from the GCC middle-end need to be made
387available explicitely via @code{define_predicates}:
388
389@smallexample
390(define_predicates
391 integer_onep integer_zerop integer_all_onesp)
392@end smallexample
393
394You can also define predicates using the pattern matching language
395and the @code{match} form:
396
397@smallexample
398(match negate_expr_p
399 INTEGER_CST
400 (if (TYPE_OVERFLOW_WRAPS (type)
401      || may_negate_without_overflow_p (t))))
402(match negate_expr_p
403 (negate @@0))
404@end smallexample
405
406This shows that for @code{match} expressions there is @code{t}
407available which captures the outermost expression (something
408not possible in the @code{simplify} context).  As you can see
409@code{match} has an identifier as first operand which is how
410you refer to the predicate in patterns.  Multiple @code{match}
411for the same identifier add additional cases where the predicate
412matches.
413
414Predicates can also match an expression in which case you need
415to provide a template specifying the identifier and where to
416get its operands from:
417
418@smallexample
419(match (logical_inverted_value @@0)
420 (eq @@0 integer_zerop))
421(match (logical_inverted_value @@0)
422 (bit_not truth_valued_p@@0))
423@end smallexample
424
425You can use the above predicate like
426
427@smallexample
428(simplify
429 (bit_and @@0 (logical_inverted_value @@0))
430 @{ build_zero_cst (type); @})
431@end smallexample
432
433Which will match a bitwise and of an operand with its logical
434inverted value.
435
436