diff options
Diffstat (limited to 'share/doc/gccint/The-Language.html')
| -rw-r--r-- | share/doc/gccint/The-Language.html | 464 |
1 files changed, 464 insertions, 0 deletions
diff --git a/share/doc/gccint/The-Language.html b/share/doc/gccint/The-Language.html new file mode 100644 index 0000000..c1497fc --- /dev/null +++ b/share/doc/gccint/The-Language.html @@ -0,0 +1,464 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> +<html> +<!-- Copyright (C) 1988-2023 Free Software Foundation, Inc. + +Permission is granted to copy, distribute and/or modify this document +under the terms of the GNU Free Documentation License, Version 1.3 or +any later version published by the Free Software Foundation; with the +Invariant Sections being "Funding Free Software", the Front-Cover +Texts being (a) (see below), and with the Back-Cover Texts being (b) +(see below). A copy of the license is included in the section entitled +"GNU Free Documentation License". + +(a) The FSF's Front-Cover Text is: + +A GNU Manual + +(b) The FSF's Back-Cover Text is: + +You have freedom to copy and modify this GNU Manual, like GNU + software. Copies published by the Free Software Foundation raise + funds for GNU development. --> +<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ --> +<head> +<title>GNU Compiler Collection (GCC) Internals: The Language</title> + +<meta name="description" content="GNU Compiler Collection (GCC) Internals: The Language"> +<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: The Language"> +<meta name="resource-type" content="document"> +<meta name="distribution" content="global"> +<meta name="Generator" content="makeinfo"> +<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> +<link href="index.html#Top" rel="start" title="Top"> +<link href="Option-Index.html#Option-Index" rel="index" title="Option Index"> +<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents"> +<link href="Match-and-Simplify.html#Match-and-Simplify" rel="up" title="Match and Simplify"> +<link href="Static-Analyzer.html#Static-Analyzer" rel="next" title="Static Analyzer"> +<link href="GIMPLE-API.html#GIMPLE-API" rel="previous" title="GIMPLE API"> +<style type="text/css"> +<!-- +a.summary-letter {text-decoration: none} +blockquote.smallquotation {font-size: smaller} +div.display {margin-left: 3.2em} +div.example {margin-left: 3.2em} +div.indentedblock {margin-left: 3.2em} +div.lisp {margin-left: 3.2em} +div.smalldisplay {margin-left: 3.2em} +div.smallexample {margin-left: 3.2em} +div.smallindentedblock {margin-left: 3.2em; font-size: smaller} +div.smalllisp {margin-left: 3.2em} +kbd {font-style:oblique} +pre.display {font-family: inherit} +pre.format {font-family: inherit} +pre.menu-comment {font-family: serif} +pre.menu-preformatted {font-family: serif} +pre.smalldisplay {font-family: inherit; font-size: smaller} +pre.smallexample {font-size: smaller} +pre.smallformat {font-family: inherit; font-size: smaller} +pre.smalllisp {font-size: smaller} +span.nocodebreak {white-space:nowrap} +span.nolinebreak {white-space:nowrap} +span.roman {font-family:serif; font-weight:normal} +span.sansserif {font-family:sans-serif; font-weight:normal} +ul.no-bullet {list-style: none} +--> +</style> + + +</head> + +<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000"> +<a name="The-Language"></a> +<div class="header"> +<p> +Previous: <a href="GIMPLE-API.html#GIMPLE-API" accesskey="p" rel="previous">GIMPLE API</a>, Up: <a href="Match-and-Simplify.html#Match-and-Simplify" accesskey="u" rel="up">Match and Simplify</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p> +</div> +<hr> +<a name="The-Language-1"></a> +<h3 class="section">26.2 The Language</h3> +<a name="index-The-Language"></a> + +<p>The language in which to write expression simplifications resembles +other domain-specific languages GCC uses. Thus it is lispy. Let’s +start with an example from the match.pd file: +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (bit_and @0 integer_all_onesp) + @0) +</pre></div> + +<p>This example contains all required parts of an expression simplification. +A simplification is wrapped inside a <code>(simplify ...)</code> expression. +That contains at least two operands - an expression that is matched +with the GIMPLE or GENERIC IL and a replacement expression that is +returned if the match was successful. +</p> +<p>Expressions have an operator ID, <code>bit_and</code> in this case. Expressions can +be lower-case tree codes with <code>_expr</code> stripped off or builtin +function code names in all-caps, like <code>BUILT_IN_SQRT</code>. +</p> +<p><code>@n</code> denotes a so-called capture. It captures the operand and lets +you refer to it in other places of the match-and-simplify. In the +above example it is referred to in the replacement expression. Captures +are <code>@</code> followed by a number or an identifier. +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (bit_xor @0 @0) + { build_zero_cst (type); }) +</pre></div> + +<p>In this example <code>@0</code> is mentioned twice which constrains the matched +expression to have two equal operands. Usually matches are constrained +to equal types. If operands may be constants and conversions are involved, +matching by value might be preferred in which case use <code>@@0</code> to +denote a by-value match and the specific operand you want to refer to +in the result part. This example also introduces +operands written in C code. These can be used in the expression +replacements and are supposed to evaluate to a tree node which has to +be a valid GIMPLE operand (so you cannot generate expressions in C code). +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (trunc_mod integer_zerop@0 @1) + (if (!integer_zerop (@1)) + @0)) +</pre></div> + +<p>Here <code>@0</code> captures the first operand of the trunc_mod expression +which is also predicated with <code>integer_zerop</code>. Expression operands +may be either expressions, predicates or captures. Captures +can be unconstrained or capture expressions or predicates. +</p> +<p>This example introduces an optional operand of simplify, +the if-expression. This condition is evaluated after the +expression matched in the IL and is required to evaluate to true +to enable the replacement expression in the second operand +position. The expression operand of the <code>if</code> is a standard C +expression which may contain references to captures. The <code>if</code> +has an optional third operand which may contain the replacement +expression that is enabled when the condition evaluates to false. +</p> +<p>A <code>if</code> expression can be used to specify a common condition +for multiple simplify patterns, avoiding the need +to repeat that multiple times: +</p> +<div class="smallexample"> +<pre class="smallexample">(if (!TYPE_SATURATING (type) + && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type)) + (simplify + (minus (plus @0 @1) @0) + @1) + (simplify + (minus (minus @0 @1) @0) + (negate @1))) +</pre></div> + +<p>Note that <code>if</code>s in outer position do not have the optional +else clause but instead have multiple then clauses. +</p> +<p>Ifs can be nested. +</p> +<p>There exists a <code>switch</code> expression which can be used to +chain conditions avoiding nesting <code>if</code>s too much: +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (simple_comparison @0 REAL_CST@1) + (switch + /* a CMP (-0) -> a CMP 0 */ + (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1))) + (cmp @0 { build_real (TREE_TYPE (@1), dconst0); })) + /* x != NaN is always true, other ops are always false. */ + (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1)) + && ! HONOR_SNANS (@1)) + { constant_boolean_node (cmp == NE_EXPR, type); }))) +</pre></div> + +<p>Is equal to +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (simple_comparison @0 REAL_CST@1) + (switch + /* a CMP (-0) -> a CMP 0 */ + (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1))) + (cmp @0 { build_real (TREE_TYPE (@1), dconst0); }) + /* x != NaN is always true, other ops are always false. */ + (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1)) + && ! HONOR_SNANS (@1)) + { constant_boolean_node (cmp == NE_EXPR, type); })))) +</pre></div> + +<p>which has the second <code>if</code> in the else operand of the first. +The <code>switch</code> expression takes <code>if</code> expressions as +operands (which may not have else clauses) and as a last operand +a replacement expression which should be enabled by default if +no other condition evaluated to true. +</p> +<p>Captures can also be used for capturing results of sub-expressions. +</p> +<div class="smallexample"> +<pre class="smallexample">#if GIMPLE +(simplify + (pointer_plus (addr@2 @0) INTEGER_CST_P@1) + (if (is_gimple_min_invariant (@2))) + { + poly_int64 off; + tree base = get_addr_base_and_unit_offset (@0, &off); + off += tree_to_uhwi (@1); + /* Now with that we should be able to simply write + (addr (mem_ref (addr @base) (plus @off @1))) */ + build1 (ADDR_EXPR, type, + build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)), + build_fold_addr_expr (base), + build_int_cst (ptr_type_node, off))); + }) +#endif +</pre></div> + +<p>In the above example, <code>@2</code> captures the result of the expression +<code>(addr @0)</code>. For the outermost expression only its type can be +captured, and the keyword <code>type</code> is reserved for this purpose. The +above example also gives a way to conditionalize patterns to only apply +to <code>GIMPLE</code> or <code>GENERIC</code> by means of using the pre-defined +preprocessor macros <code>GIMPLE</code> and <code>GENERIC</code> and using +preprocessor directives. +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (bit_and:c integral_op_p@0 (bit_ior:c (bit_not @0) @1)) + (bit_and @1 @0)) +</pre></div> + +<p>Here we introduce flags on match expressions. The flag used +above, <code>c</code>, denotes that the expression should +be also matched commutated. Thus the above match expression +is really the following four match expressions: +</p> +<div class="smallexample"> +<pre class="smallexample"> (bit_and integral_op_p@0 (bit_ior (bit_not @0) @1)) + (bit_and (bit_ior (bit_not @0) @1) integral_op_p@0) + (bit_and integral_op_p@0 (bit_ior @1 (bit_not @0))) + (bit_and (bit_ior @1 (bit_not @0)) integral_op_p@0) +</pre></div> + +<p>Usual canonicalizations you know from GENERIC expressions are +applied before matching, so for example constant operands always +come second in commutative expressions. +</p> +<p>The second supported flag is <code>s</code> which tells the code +generator to fail the pattern if the expression marked with +<code>s</code> does have more than one use and the simplification +results in an expression with more than one operator. +For example in +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (pointer_plus (pointer_plus:s @0 @1) @3) + (pointer_plus @0 (plus @1 @3))) +</pre></div> + +<p>this avoids the association if <code>(pointer_plus @0 @1)</code> is +used outside of the matched expression and thus it would stay +live and not trivially removed by dead code elimination. +Now consider <code>((x + 3) + -3)</code> with the temporary +holding <code>(x + 3)</code> used elsewhere. This simplifies down +to <code>x</code> which is desirable and thus flagging with <code>s</code> +does not prevent the transform. Now consider <code>((x + 3) + 1)</code> +which simplifies to <code>(x + 4)</code>. Despite being flagged with +<code>s</code> the simplification will be performed. The +simplification of <code>((x + a) + 1)</code> to <code>(x + (a + 1))</code> will +not performed in this case though. +</p> +<p>More features exist to avoid too much repetition. +</p> +<div class="smallexample"> +<pre class="smallexample">(for op (plus pointer_plus minus bit_ior bit_xor) + (simplify + (op @0 integer_zerop) + @0)) +</pre></div> + +<p>A <code>for</code> expression can be used to repeat a pattern for each +operator specified, substituting <code>op</code>. <code>for</code> can be +nested and a <code>for</code> can have multiple operators to iterate. +</p> +<div class="smallexample"> +<pre class="smallexample">(for opa (plus minus) + opb (minus plus) + (for opc (plus minus) + (simplify... +</pre></div> + +<p>In this example the pattern will be repeated four times with +<code>opa, opb, opc</code> being <code>plus, minus, plus</code>; +<code>plus, minus, minus</code>; <code>minus, plus, plus</code>; +<code>minus, plus, minus</code>. +</p> +<p>To avoid repeating operator lists in <code>for</code> you can name +them via +</p> +<div class="smallexample"> +<pre class="smallexample">(define_operator_list pmm plus minus mult) +</pre></div> + +<p>and use them in <code>for</code> operator lists where they get expanded. +</p> +<div class="smallexample"> +<pre class="smallexample">(for opa (pmm trunc_div) + (simplify... +</pre></div> + +<p>So this example iterates over <code>plus</code>, <code>minus</code>, <code>mult</code> +and <code>trunc_div</code>. +</p> +<p>Using operator lists can also remove the need to explicitly write +a <code>for</code>. All operator list uses that appear in a <code>simplify</code> +or <code>match</code> pattern in operator positions will implicitly +be added to a new <code>for</code>. For example +</p> +<div class="smallexample"> +<pre class="smallexample">(define_operator_list SQRT BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL) +(define_operator_list POW BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL) +(simplify + (SQRT (POW @0 @1)) + (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); }))) +</pre></div> + +<p>is the same as +</p> +<div class="smallexample"> +<pre class="smallexample">(for SQRT (BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL) + POW (BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL) + (simplify + (SQRT (POW @0 @1)) + (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); })))) +</pre></div> + +<p><code>for</code>s and operator lists can include the special identifier +<code>null</code> that matches nothing and can never be generated. This can +be used to pad an operator list so that it has a standard form, +even if there isn’t a suitable operator for every form. +</p> +<p>Another building block are <code>with</code> expressions in the +result expression which nest the generated code in a new C block +followed by its argument: +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (convert (mult @0 @1)) + (with { tree utype = unsigned_type_for (type); } + (convert (mult (convert:utype @0) (convert:utype @1))))) +</pre></div> + +<p>This allows code nested in the <code>with</code> to refer to the declared +variables. In the above case we use the feature to specify the +type of a generated expression with the <code>:type</code> syntax where +<code>type</code> needs to be an identifier that refers to the desired type. +Usually the types of the generated result expressions are +determined from the context, but sometimes like in the above case +it is required that you specify them explicitly. +</p> +<p>Another modifier for generated expressions is <code>!</code> which +tells the machinery to only consider the simplification in case +the marked expression simplified to a simple operand. Consider +for example +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (plus (vec_cond:s @0 @1 @2) @3) + (vec_cond @0 (plus! @1 @3) (plus! @2 @3))) +</pre></div> + +<p>which moves the outer <code>plus</code> operation to the inner arms +of the <code>vec_cond</code> expression but only if the actual plus +operations both simplify. Note that on <code>GENERIC</code> a simple +operand means that the result satisfies <code>!EXPR_P</code> which +can be limiting if the operation itself simplifies but the +remaining operand is an (unrelated) expression. +</p> +<p>As intermediate conversions are often optional there is a way to +avoid the need to repeat patterns both with and without such +conversions. Namely you can mark a conversion as being optional +with a <code>?</code>: +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (eq (convert@0 @1) (convert? @2)) + (eq @1 (convert @2))) +</pre></div> + +<p>which will match both <code>(eq (convert @1) (convert @2))</code> and +<code>(eq (convert @1) @2)</code>. The optional converts are supposed +to be all either present or not, thus +<code>(eq (convert? @1) (convert? @2))</code> will result in two +patterns only. If you want to match all four combinations you +have access to two additional conditional converts as in +<code>(eq (convert1? @1) (convert2? @2))</code>. +</p> +<p>The support for <code>?</code> marking extends to all unary operations +including predicates you declare yourself with <code>match</code>. +</p> +<p>Predicates available from the GCC middle-end need to be made +available explicitly via <code>define_predicates</code>: +</p> +<div class="smallexample"> +<pre class="smallexample">(define_predicates + integer_onep integer_zerop integer_all_onesp) +</pre></div> + +<p>You can also define predicates using the pattern matching language +and the <code>match</code> form: +</p> +<div class="smallexample"> +<pre class="smallexample">(match negate_expr_p + INTEGER_CST + (if (TYPE_OVERFLOW_WRAPS (type) + || may_negate_without_overflow_p (t)))) +(match negate_expr_p + (negate @0)) +</pre></div> + +<p>This shows that for <code>match</code> expressions there is <code>t</code> +available which captures the outermost expression (something +not possible in the <code>simplify</code> context). As you can see +<code>match</code> has an identifier as first operand which is how +you refer to the predicate in patterns. Multiple <code>match</code> +for the same identifier add additional cases where the predicate +matches. +</p> +<p>Predicates can also match an expression in which case you need +to provide a template specifying the identifier and where to +get its operands from: +</p> +<div class="smallexample"> +<pre class="smallexample">(match (logical_inverted_value @0) + (eq @0 integer_zerop)) +(match (logical_inverted_value @0) + (bit_not truth_valued_p@0)) +</pre></div> + +<p>You can use the above predicate like +</p> +<div class="smallexample"> +<pre class="smallexample">(simplify + (bit_and @0 (logical_inverted_value @0)) + { build_zero_cst (type); }) +</pre></div> + +<p>Which will match a bitwise and of an operand with its logical +inverted value. +</p> + +<hr> +<div class="header"> +<p> +Previous: <a href="GIMPLE-API.html#GIMPLE-API" accesskey="p" rel="previous">GIMPLE API</a>, Up: <a href="Match-and-Simplify.html#Match-and-Simplify" accesskey="u" rel="up">Match and Simplify</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p> +</div> + + + +</body> +</html> |