| 1 |
@c Copyright (C) 2014-2023 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 |
|
| 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.cc, gimple-fold.cc and builtins.cc |
| 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 mimicking |
| 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 |
On top 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 in which to write expression simplifications resembles |
| 82 |
other domain-specific languages GCC uses. Thus it is lispy. Let's |
| 83 |
start 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 referred 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 constrained |
| 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 expressions 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 |
@{ |
| 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 |
|
| 221 |
In the above example, @code{@@2} captures the result of the expression |
| 222 |
@code{(addr @@0)}. For the outermost expression only its type can be |
| 223 |
captured, and the keyword @code{type} is reserved for this purpose. The |
| 224 |
above 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 |
| 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 |
| 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. |
| 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. |
| 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 explicitly write |
| 318 |
a @code{for}. All operator list uses that appear in a @code{simplify} |
| 319 |
or @code{match} pattern in operator positions will implicitly |
| 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 explicitly. |
| 363 |
|
| 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 |
| 377 |
operations both simplify. Note that on @code{GENERIC} a simple |
| 378 |
operand means that the result satisfies @code{!EXPR_P} which |
| 379 |
can be limiting if the operation itself simplifies but the |
| 380 |
remaining operand is an (unrelated) expression. |
| 381 |
|
| 382 |
As intermediate conversions are often optional there is a way to |
| 383 |
avoid the need to repeat patterns both with and without such |
| 384 |
conversions. Namely you can mark a conversion as being optional |
| 385 |
with a @code{?}: |
| 386 |
|
| 387 |
@smallexample |
| 388 |
(simplify |
| 389 |
(eq (convert@@0 @@1) (convert@? @@2)) |
| 390 |
(eq @@1 (convert @@2))) |
| 391 |
@end smallexample |
| 392 |
|
| 393 |
which will match both @code{(eq (convert @@1) (convert @@2))} and |
| 394 |
@code{(eq (convert @@1) @@2)}. The optional converts are supposed |
| 395 |
to be all either present or not, thus |
| 396 |
@code{(eq (convert@? @@1) (convert@? @@2))} will result in two |
| 397 |
patterns only. If you want to match all four combinations you |
| 398 |
have access to two additional conditional converts as in |
| 399 |
@code{(eq (convert1@? @@1) (convert2@? @@2))}. |
| 400 |
|
| 401 |
The support for @code{?} marking extends to all unary operations |
| 402 |
including predicates you declare yourself with @code{match}. |
| 403 |
|
| 404 |
Predicates available from the GCC middle-end need to be made |
| 405 |
available explicitly via @code{define_predicates}: |
| 406 |
|
| 407 |
@smallexample |
| 408 |
(define_predicates |
| 409 |
integer_onep integer_zerop integer_all_onesp) |
| 410 |
@end smallexample |
| 411 |
|
| 412 |
You can also define predicates using the pattern matching language |
| 413 |
and the @code{match} form: |
| 414 |
|
| 415 |
@smallexample |
| 416 |
(match negate_expr_p |
| 417 |
INTEGER_CST |
| 418 |
(if (TYPE_OVERFLOW_WRAPS (type) |
| 419 |
|| may_negate_without_overflow_p (t)))) |
| 420 |
(match negate_expr_p |
| 421 |
(negate @@0)) |
| 422 |
@end smallexample |
| 423 |
|
| 424 |
This shows that for @code{match} expressions there is @code{t} |
| 425 |
available which captures the outermost expression (something |
| 426 |
not possible in the @code{simplify} context). As you can see |
| 427 |
@code{match} has an identifier as first operand which is how |
| 428 |
you refer to the predicate in patterns. Multiple @code{match} |
| 429 |
for the same identifier add additional cases where the predicate |
| 430 |
matches. |
| 431 |
|
| 432 |
Predicates can also match an expression in which case you need |
| 433 |
to provide a template specifying the identifier and where to |
| 434 |
get its operands from: |
| 435 |
|
| 436 |
@smallexample |
| 437 |
(match (logical_inverted_value @@0) |
| 438 |
(eq @@0 integer_zerop)) |
| 439 |
(match (logical_inverted_value @@0) |
| 440 |
(bit_not truth_valued_p@@0)) |
| 441 |
@end smallexample |
| 442 |
|
| 443 |
You can use the above predicate like |
| 444 |
|
| 445 |
@smallexample |
| 446 |
(simplify |
| 447 |
(bit_and @@0 (logical_inverted_value @@0)) |
| 448 |
@{ build_zero_cst (type); @}) |
| 449 |
@end smallexample |
| 450 |
|
| 451 |
Which will match a bitwise and of an operand with its logical |
| 452 |
inverted value. |
| 453 |
|