1@c Copyright (C) 2014-2016 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. This example also introduces 114operands written in C code. These can be used in the expression 115replacements and are supposed to evaluate to a tree node which has to 116be a valid GIMPLE operand (so you cannot generate expressions in C code). 117 118@smallexample 119(simplify 120 (trunc_mod integer_zerop@@0 @@1) 121 (if (!integer_zerop (@@1)) 122 @@0)) 123@end smallexample 124 125Here @code{@@0} captures the first operand of the trunc_mod expression 126which is also predicated with @code{integer_zerop}. Expression operands 127may be either expressions, predicates or captures. Captures 128can be unconstrained or capture expresions or predicates. 129 130This example introduces an optional operand of simplify, 131the if-expression. This condition is evaluated after the 132expression matched in the IL and is required to evaluate to true 133to enable the replacement expression in the second operand 134position. The expression operand of the @code{if} is a standard C 135expression which may contain references to captures. The @code{if} 136has an optional third operand which may contain the replacement 137expression that is enabled when the condition evaluates to false. 138 139A @code{if} expression can be used to specify a common condition 140for multiple simplify patterns, avoiding the need 141to repeat that multiple times: 142 143@smallexample 144(if (!TYPE_SATURATING (type) 145 && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type)) 146 (simplify 147 (minus (plus @@0 @@1) @@0) 148 @@1) 149 (simplify 150 (minus (minus @@0 @@1) @@0) 151 (negate @@1))) 152@end smallexample 153 154Note that @code{if}s in outer position do not have the optional 155else clause but instead have multiple then clauses. 156 157Ifs can be nested. 158 159There exists a @code{switch} expression which can be used to 160chain conditions avoiding nesting @code{if}s too much: 161 162@smallexample 163(simplify 164 (simple_comparison @@0 REAL_CST@@1) 165 (switch 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); @}))) 173@end smallexample 174 175Is equal to 176 177@smallexample 178(simplify 179 (simple_comparison @@0 REAL_CST@@1) 180 (switch 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); @})))) 188@end smallexample 189 190which has the second @code{if} in the else operand of the first. 191The @code{switch} expression takes @code{if} expressions as 192operands (which may not have else clauses) and as a last operand 193a replacement expression which should be enabled by default if 194no other condition evaluated to true. 195 196Captures can also be used for capturing results of sub-expressions. 197 198@smallexample 199#if GIMPLE 200(simplify 201 (pointer_plus (addr@@2 @@0) INTEGER_CST_P@@1) 202 (if (is_gimple_min_invariant (@@2))) 203 @{ 204 HOST_WIDE_INT off; 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))); 213 @}) 214#endif 215@end smallexample 216 217In the above example, @code{@@2} captures the result of the expression 218@code{(addr @@0)}. For outermost expression only its type can be captured, 219and the keyword @code{type} is reserved for this purpose. The above 220example also gives a way to conditionalize patterns to only apply 221to @code{GIMPLE} or @code{GENERIC} by means of using the pre-defined 222preprocessor macros @code{GIMPLE} and @code{GENERIC} and using 223preprocessor directives. 224 225@smallexample 226(simplify 227 (bit_and:c integral_op_p@@0 (bit_ior:c (bit_not @@0) @@1)) 228 (bit_and @@1 @@0)) 229@end smallexample 230 231Here we introduce flags on match expressions. The flag used 232above, @code{c}, denotes that the expression should 233be also matched commutated. Thus the above match expression 234is really the following four match expressions: 235 236@smallexample 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) 241@end smallexample 242 243Usual canonicalizations you know from GENERIC expressions are 244applied before matching, so for example constant operands always 245come second in commutative expressions. 246 247The second supported flag is @code{s} which tells the code 248generator to fail the pattern if the expression marked with 249@code{s} does have more than one use. For example in 250 251@smallexample 252(simplify 253 (pointer_plus (pointer_plus:s @@0 @@1) @@3) 254 (pointer_plus @@0 (plus @@1 @@3))) 255@end smallexample 256 257this avoids the association if @code{(pointer_plus @@0 @@1)} is 258used outside of the matched expression and thus it would stay 259live and not trivially removed by dead code elimination. 260 261More features exist to avoid too much repetition. 262 263@smallexample 264(for op (plus pointer_plus minus bit_ior bit_xor) 265 (simplify 266 (op @@0 integer_zerop) 267 @@0)) 268@end smallexample 269 270A @code{for} expression can be used to repeat a pattern for each 271operator specified, substituting @code{op}. @code{for} can be 272nested and a @code{for} can have multiple operators to iterate. 273 274@smallexample 275(for opa (plus minus) 276 opb (minus plus) 277 (for opc (plus minus) 278 (simplify... 279@end smallexample 280 281In 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}. 285 286To avoid repeating operator lists in @code{for} you can name 287them via 288 289@smallexample 290(define_operator_list pmm plus minus mult) 291@end smallexample 292 293and use them in @code{for} operator lists where they get expanded. 294 295@smallexample 296(for opa (pmm trunc_div) 297 (simplify... 298@end smallexample 299 300So this example iterates over @code{plus}, @code{minus}, @code{mult} 301and @code{trunc_div}. 302 303Using operator lists can also remove the need to explicitely write 304a @code{for}. All operator list uses that appear in a @code{simplify} 305or @code{match} pattern in operator positions will implicitely 306be added to a new @code{for}. For example 307 308@smallexample 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) 311(simplify 312 (SQRT (POW @@0 @@1)) 313 (POW (abs @@0) (mult @@1 @{ built_real (TREE_TYPE (@@1), dconsthalf); @}))) 314@end smallexample 315 316is the same as 317 318@smallexample 319(for SQRT (BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL) 320 POW (BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL) 321 (simplify 322 (SQRT (POW @@0 @@1)) 323 (POW (abs @@0) (mult @@1 @{ built_real (TREE_TYPE (@@1), dconsthalf); @})))) 324@end smallexample 325 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 328be used to pad an operator list so that it has a standard form, 329even if there isn't a suitable operator for every form. 330 331Another building block are @code{with} expressions in the 332result expression which nest the generated code in a new C block 333followed by its argument: 334 335@smallexample 336(simplify 337 (convert (mult @@0 @@1)) 338 (with @{ tree utype = unsigned_type_for (type); @} 339 (convert (mult (convert:utype @@0) (convert:utype @@1))))) 340@end smallexample 341 342This allows code nested in the @code{with} to refer to the declared 343variables. In the above case we use the feature to specify the 344type of a generated expression with the @code{:type} syntax where 345@code{type} needs to be an identifier that refers to the desired type. 346Usually the types of the generated result expressions are 347determined from the context, but sometimes like in the above case 348it is required that you specify them explicitely. 349 350As intermediate conversions are often optional there is a way to 351avoid the need to repeat patterns both with and without such 352conversions. Namely you can mark a conversion as being optional 353with a @code{?}: 354 355@smallexample 356(simplify 357 (eq (convert@@0 @@1) (convert@? @@2)) 358 (eq @@1 (convert @@2))) 359@end smallexample 360 361which will match both @code{(eq (convert @@1) (convert @@2))} and 362@code{(eq (convert @@1) @@2)}. The optional converts are supposed 363to be all either present or not, thus 364@code{(eq (convert@? @@1) (convert@? @@2))} will result in two 365patterns only. If you want to match all four combinations you 366have access to two additional conditional converts as in 367@code{(eq (convert1@? @@1) (convert2@? @@2))}. 368 369Predicates available from the GCC middle-end need to be made 370available explicitely via @code{define_predicates}: 371 372@smallexample 373(define_predicates 374 integer_onep integer_zerop integer_all_onesp) 375@end smallexample 376 377You can also define predicates using the pattern matching language 378and the @code{match} form: 379 380@smallexample 381(match negate_expr_p 382 INTEGER_CST 383 (if (TYPE_OVERFLOW_WRAPS (type) 384 || may_negate_without_overflow_p (t)))) 385(match negate_expr_p 386 (negate @@0)) 387@end smallexample 388 389This shows that for @code{match} expressions there is @code{t} 390available which captures the outermost expression (something 391not possible in the @code{simplify} context). As you can see 392@code{match} has an identifier as first operand which is how 393you refer to the predicate in patterns. Multiple @code{match} 394for the same identifier add additional cases where the predicate 395matches. 396 397Predicates can also match an expression in which case you need 398to provide a template specifying the identifier and where to 399get its operands from: 400 401@smallexample 402(match (logical_inverted_value @@0) 403 (eq @@0 integer_zerop)) 404(match (logical_inverted_value @@0) 405 (bit_not truth_valued_p@@0)) 406@end smallexample 407 408You can use the above predicate like 409 410@smallexample 411(simplify 412 (bit_and @@0 (logical_inverted_value @@0)) 413 @{ build_zero_cst (type); @}) 414@end smallexample 415 416Which will match a bitwise and of an operand with its logical 417inverted value. 418 419