1 @c Copyright (C) 2014-2015 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.
6 @node Match and Simplify
7 @chapter Match and Simplify
8 @cindex Match and Simplify
10 The GIMPLE and GENERIC pattern matching project match-and-simplify
11 tries to address several issues.
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
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
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.
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.
53 In addition to those APIs @code{fold_stmt} is overloaded with
56 @deftypefn bool fold_stmt (gimple_stmt_iterator *, tree (*)(tree));
60 Ontop of these a @code{fold_buildN}-like API for GIMPLE is introduced:
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);
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.
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:
87 (bit_and @@0 integer_all_onesp)
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.
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}.
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.
109 @{ build_zero_cst (type); @})
112 In this example @code{@@0} is mentioned twice which constrains the matched
113 expression to have two equal operands. This example also introduces
114 operands written in C code. These can be used in the expression
115 replacements and are supposed to evaluate to a tree node which has to
116 be a valid GIMPLE operand (so you cannot generate expressions in C code).
120 (trunc_mod integer_zerop@@0 @@1)
121 (if (!integer_zerop (@@1))
125 Here @code{@@0} captures the first operand of the trunc_mod expression
126 which is also predicated with @code{integer_zerop}. Expression operands
127 may be either expressions, predicates or captures. Captures
128 can be unconstrained or capture expresions or predicates.
130 This example introduces an optional operand of simplify,
131 the if-expression. This condition is evaluated after the
132 expression matched in the IL and is required to evaluate to true
133 to enable the replacement expression in the second operand
134 position. The expression operand of the @code{if} is a standard C
135 expression which may contain references to captures. The @code{if}
136 has an optional third operand which may contain the replacement
137 expression that is enabled when the condition evaluates to false.
139 A @code{if} expression can be used to specify a common condition
140 for multiple simplify patterns, avoiding the need
141 to repeat that multiple times:
144 (if (!TYPE_SATURATING (type)
145 && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type))
147 (minus (plus @@0 @@1) @@0)
150 (minus (minus @@0 @@1) @@0)
154 Note that @code{if}s in outer position do not have the optional
155 else clause but instead have multiple then clauses.
159 There exists a @code{switch} expression which can be used to
160 chain conditions avoiding nesting @code{if}s too much:
164 (simple_comparison @@0 REAL_CST@@1)
166 /* a CMP (-0) -> a CMP 0 */
167 (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@@1)))
168 (cmp @@0 @{ build_real (TREE_TYPE (@@1), dconst0); @}))
169 /* x != NaN is always true, other ops are always false. */
170 (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@@1))
171 && ! HONOR_SNANS (@@1))
172 @{ constant_boolean_node (cmp == NE_EXPR, type); @})))
179 (simple_comparison @@0 REAL_CST@@1)
181 /* a CMP (-0) -> a CMP 0 */
182 (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@@1)))
183 (cmp @@0 @{ build_real (TREE_TYPE (@@1), dconst0); @})
184 /* x != NaN is always true, other ops are always false. */
185 (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@@1))
186 && ! HONOR_SNANS (@@1))
187 @{ constant_boolean_node (cmp == NE_EXPR, type); @}))))
190 which has the second @code{if} in the else operand of the first.
191 The @code{switch} expression takes @code{if} expressions as
192 operands (which may not have else clauses) and as a last operand
193 a replacement expression which should be enabled by default if
194 no other condition evaluated to true.
196 Captures can also be used for capturing results of sub-expressions.
201 (pointer_plus (addr@@2 @@0) INTEGER_CST_P@@1)
202 (if (is_gimple_min_invariant (@@2)))
205 tree base = get_addr_base_and_unit_offset (@@0, &off);
206 off += tree_to_uhwi (@@1);
207 /* Now with that we should be able to simply write
208 (addr (mem_ref (addr @@base) (plus @@off @@1))) */
209 build1 (ADDR_EXPR, type,
210 build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@@2)),
211 build_fold_addr_expr (base),
212 build_int_cst (ptr_type_node, off)));
217 In the above example, @code{@@2} captures the result of the expression
218 @code{(addr @@0)}. For outermost expression only its type can be captured,
219 and the keyword @code{type} is reserved for this purpose. The above
220 example also gives a way to conditionalize patterns to only apply
221 to @code{GIMPLE} or @code{GENERIC} by means of using the pre-defined
222 preprocessor macros @code{GIMPLE} and @code{GENERIC} and using
223 preprocessor directives.
227 (bit_and:c integral_op_p@@0 (bit_ior:c (bit_not @@0) @@1))
231 Here we introduce flags on match expressions. The flag used
232 above, @code{c}, denotes that the expression should
233 be also matched commutated. Thus the above match expression
234 is really the following four match expressions:
237 (bit_and integral_op_p@@0 (bit_ior (bit_not @@0) @@1))
238 (bit_and (bit_ior (bit_not @@0) @@1) integral_op_p@@0)
239 (bit_and integral_op_p@@0 (bit_ior @@1 (bit_not @@0)))
240 (bit_and (bit_ior @@1 (bit_not @@0)) integral_op_p@@0)
243 Usual canonicalizations you know from GENERIC expressions are
244 applied before matching, so for example constant operands always
245 come second in commutative expressions.
247 The second supported flag is @code{s} which tells the code
248 generator to fail the pattern if the expression marked with
249 @code{s} does have more than one use. For example in
253 (pointer_plus (pointer_plus:s @@0 @@1) @@3)
254 (pointer_plus @@0 (plus @@1 @@3)))
257 this avoids the association if @code{(pointer_plus @@0 @@1)} is
258 used outside of the matched expression and thus it would stay
259 live and not trivially removed by dead code elimination.
261 More features exist to avoid too much repetition.
264 (for op (plus pointer_plus minus bit_ior bit_xor)
266 (op @@0 integer_zerop)
270 A @code{for} expression can be used to repeat a pattern for each
271 operator specified, substituting @code{op}. @code{for} can be
272 nested and a @code{for} can have multiple operators to iterate.
275 (for opa (plus minus)
277 (for opc (plus minus)
281 In this example the pattern will be repeated four times with
282 @code{opa, opb, opc} being @code{plus, minus, plus},
283 @code{plus, minus, minus}, @code{minus, plus, plus},
284 @code{minus, plus, minus}.
286 To avoid repeating operator lists in @code{for} you can name
290 (define_operator_list pmm plus minus mult)
293 and use them in @code{for} operator lists where they get expanded.
296 (for opa (pmm trunc_div)
300 So this example iterates over @code{plus}, @code{minus}, @code{mult}
301 and @code{trunc_div}.
303 Using operator lists can also remove the need to explicitely write
304 a @code{for}. All operator list uses that appear in a @code{simplify}
305 or @code{match} pattern in operator positions will implicitely
306 be added to a new @code{for}. For example
309 (define_operator_list SQRT BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL)
310 (define_operator_list POW BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL)
313 (POW (abs @@0) (mult @@1 @{ built_real (TREE_TYPE (@@1), dconsthalf); @})))
319 (for SQRT (BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL)
320 POW (BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL)
323 (POW (abs @@0) (mult @@1 @{ built_real (TREE_TYPE (@@1), dconsthalf); @}))))
326 @code{for}s and operator lists can include the special identifier
327 @code{null} that matches nothing and can never be generated. This can
328 be used to pad an operator list so that it has a standard form,
329 even if there isn't a suitable operator for every form.
331 Another building block are @code{with} expressions in the
332 result expression which nest the generated code in a new C block
333 followed by its argument:
337 (convert (mult @@0 @@1))
338 (with @{ tree utype = unsigned_type_for (type); @}
339 (convert (mult (convert:utype @@0) (convert:utype @@1)))))
342 This allows code nested in the @code{with} to refer to the declared
343 variables. In the above case we use the feature to specify the
344 type of a generated expression with the @code{:type} syntax where
345 @code{type} needs to be an identifier that refers to the desired type.
346 Usually the types of the generated result expressions are
347 determined from the context, but sometimes like in the above case
348 it is required that you specify them explicitely.
350 As intermediate conversions are often optional there is a way to
351 avoid the need to repeat patterns both with and without such
352 conversions. Namely you can mark a conversion as being optional
357 (eq (convert@@0 @@1) (convert@? @@2))
358 (eq @@1 (convert @@2)))
361 which will match both @code{(eq (convert @@1) (convert @@2))} and
362 @code{(eq (convert @@1) @@2)}. The optional converts are supposed
363 to be all either present or not, thus
364 @code{(eq (convert@? @@1) (convert@? @@2))} will result in two
365 patterns only. If you want to match all four combinations you
366 have access to two additional conditional converts as in
367 @code{(eq (convert1@? @@1) (convert2@? @@2))}.
369 Predicates available from the GCC middle-end need to be made
370 available explicitely via @code{define_predicates}:
374 integer_onep integer_zerop integer_all_onesp)
377 You can also define predicates using the pattern matching language
378 and the @code{match} form:
383 (if (TYPE_OVERFLOW_WRAPS (type)
384 || may_negate_without_overflow_p (t))))
389 This shows that for @code{match} expressions there is @code{t}
390 available which captures the outermost expression (something
391 not possible in the @code{simplify} context). As you can see
392 @code{match} has an identifier as first operand which is how
393 you refer to the predicate in patterns. Multiple @code{match}
394 for the same identifier add additional cases where the predicate
397 Predicates can also match an expression in which case you need
398 to provide a template specifying the identifier and where to
399 get its operands from:
402 (match (logical_inverted_value @@0)
403 (eq @@0 integer_zerop))
404 (match (logical_inverted_value @@0)
405 (bit_not truth_valued_p@@0))
408 You can use the above predicate like
412 (bit_and @@0 (logical_inverted_value @@0))
413 @{ build_zero_cst (type); @})
416 Which will match a bitwise and of an operand with its logical