aboutsummaryrefslogtreecommitdiff
path: root/gcc/doc/match-and-simplify.texi
diff options
context:
space:
mode:
authorMartin Liska <mliska@suse.cz>2022-11-07 13:23:41 +0100
committerMartin Liska <mliska@suse.cz>2022-11-09 09:00:35 +0100
commit54ca4eef58661a7d7a511e2bbbe309bde1732abf (patch)
tree4f9067b036a4e7c08d0d483246cb5ab5a0d60d41 /gcc/doc/match-and-simplify.texi
parent564a805f9f08b4346a854ab8dca2e5b561a7a28e (diff)
downloadgcc-54ca4eef58661a7d7a511e2bbbe309bde1732abf.zip
gcc-54ca4eef58661a7d7a511e2bbbe309bde1732abf.tar.gz
gcc-54ca4eef58661a7d7a511e2bbbe309bde1732abf.tar.bz2
sphinx: remove texinfo files
gcc/d/ChangeLog: * gdc.texi: Removed. gcc/ChangeLog: * doc/analyzer.texi: Removed. * doc/avr-mmcu.texi: Removed. * doc/bugreport.texi: Removed. * doc/cfg.texi: Removed. * doc/collect2.texi: Removed. * doc/compat.texi: Removed. * doc/configfiles.texi: Removed. * doc/configterms.texi: Removed. * doc/contrib.texi: Removed. * doc/contribute.texi: Removed. * doc/cpp.texi: Removed. * doc/cppdiropts.texi: Removed. * doc/cppenv.texi: Removed. * doc/cppinternals.texi: Removed. * doc/cppopts.texi: Removed. * doc/cppwarnopts.texi: Removed. * doc/extend.texi: Removed. * doc/fragments.texi: Removed. * doc/frontends.texi: Removed. * doc/gcc.texi: Removed. * doc/gccint.texi: Removed. * doc/gcov-dump.texi: Removed. * doc/gcov-tool.texi: Removed. * doc/gcov.texi: Removed. * doc/generic.texi: Removed. * doc/gimple.texi: Removed. * doc/gnu.texi: Removed. * doc/gty.texi: Removed. * doc/headerdirs.texi: Removed. * doc/hostconfig.texi: Removed. * doc/implement-c.texi: Removed. * doc/implement-cxx.texi: Removed. * doc/include/fdl.texi: Removed. * doc/include/funding.texi: Removed. * doc/include/gcc-common.texi: Removed. * doc/include/gpl_v3.texi: Removed. * doc/install.texi: Removed. * doc/interface.texi: Removed. * doc/invoke.texi: Removed. * doc/languages.texi: Removed. * doc/libgcc.texi: Removed. * doc/loop.texi: Removed. * doc/lto-dump.texi: Removed. * doc/lto.texi: Removed. * doc/makefile.texi: Removed. * doc/match-and-simplify.texi: Removed. * doc/md.texi: Removed. * doc/objc.texi: Removed. * doc/optinfo.texi: Removed. * doc/options.texi: Removed. * doc/passes.texi: Removed. * doc/plugins.texi: Removed. * doc/poly-int.texi: Removed. * doc/portability.texi: Removed. * doc/rtl.texi: Removed. * doc/service.texi: Removed. * doc/sourcebuild.texi: Removed. * doc/standards.texi: Removed. * doc/tm.texi: Removed. * doc/tree-ssa.texi: Removed. * doc/trouble.texi: Removed. * doc/ux.texi: Removed. * doc/tm.texi.in: Removed. gcc/fortran/ChangeLog: * gfc-internals.texi: Removed. * gfortran.texi: Removed. * intrinsic.texi: Removed. * invoke.texi: Removed. gcc/go/ChangeLog: * gccgo.texi: Removed. libgomp/ChangeLog: * libgomp.texi: Removed. libiberty/ChangeLog: * at-file.texi: Removed. * copying-lib.texi: Removed. * functions.texi: Removed. * libiberty.texi: Removed. * obstacks.texi: Removed. libitm/ChangeLog: * libitm.texi: Removed. libquadmath/ChangeLog: * libquadmath.texi: Removed.
Diffstat (limited to 'gcc/doc/match-and-simplify.texi')
-rw-r--r--gcc/doc/match-and-simplify.texi453
1 files changed, 0 insertions, 453 deletions
diff --git a/gcc/doc/match-and-simplify.texi b/gcc/doc/match-and-simplify.texi
deleted file mode 100644
index b33d835..0000000
--- a/gcc/doc/match-and-simplify.texi
+++ /dev/null
@@ -1,453 +0,0 @@
-@c Copyright (C) 2014-2022 Free Software Foundation, Inc.
-@c Free Software Foundation, Inc.
-@c This is part of the GCC manual.
-@c For copying conditions, see the file gcc.texi.
-
-@node Match and Simplify
-@chapter Match and Simplify
-@cindex Match and Simplify
-
-The GIMPLE and GENERIC pattern matching project match-and-simplify
-tries to address several issues.
-
-@enumerate
-@item unify expression simplifications currently spread and duplicated
- over separate files like fold-const.cc, gimple-fold.cc and builtins.cc
-@item allow for a cheap way to implement building and simplifying
- non-trivial GIMPLE expressions, avoiding the need to go through
- building and simplifying GENERIC via fold_buildN and then
- gimplifying via force_gimple_operand
-@end enumerate
-
-To address these the project introduces a simple domain-specific language
-to write expression simplifications from which code targeting GIMPLE
-and GENERIC is auto-generated. The GENERIC variant follows the
-fold_buildN API while for the GIMPLE variant and to address 2) new
-APIs are introduced.
-
-@menu
-* GIMPLE API::
-* The Language::
-@end menu
-
-@node GIMPLE API
-@section GIMPLE API
-@cindex GIMPLE API
-
-@deftypefn {GIMPLE function} tree gimple_simplify (enum tree_code, tree, tree, gimple_seq *, tree (*)(tree))
-@deftypefnx {GIMPLE function} tree gimple_simplify (enum tree_code, tree, tree, tree, gimple_seq *, tree (*)(tree))
-@deftypefnx {GIMPLE function} tree gimple_simplify (enum tree_code, tree, tree, tree, tree, gimple_seq *, tree (*)(tree))
-@deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, gimple_seq *, tree (*)(tree))
-@deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, tree, gimple_seq *, tree (*)(tree))
-@deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, tree, tree, gimple_seq *, tree (*)(tree))
-The main GIMPLE API entry to the expression simplifications mimicking
-that of the GENERIC fold_@{unary,binary,ternary@} functions.
-@end deftypefn
-
-thus providing n-ary overloads for operation or function. The
-additional arguments are a gimple_seq where built statements are
-inserted on (if @code{NULL} then simplifications requiring new statements
-are not performed) and a valueization hook that can be used to
-tie simplifications to a SSA lattice.
-
-In addition to those APIs @code{fold_stmt} is overloaded with
-a valueization hook:
-
-@deftypefn bool fold_stmt (gimple_stmt_iterator *, tree (*)(tree));
-@end deftypefn
-
-
-On top of these a @code{fold_buildN}-like API for GIMPLE is introduced:
-
-@deftypefn {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum tree_code, tree, tree, tree (*valueize) (tree) = NULL);
-@deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum tree_code, tree, tree, tree, tree (*valueize) (tree) = NULL);
-@deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum tree_code, tree, tree, tree, tree, tree (*valueize) (tree) = NULL);
-@deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum built_in_function, tree, tree, tree (*valueize) (tree) = NULL);
-@deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum built_in_function, tree, tree, tree, tree (*valueize) (tree) = NULL);
-@deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum built_in_function, tree, tree, tree, tree, tree (*valueize) (tree) = NULL);
-@deftypefnx {GIMPLE function} tree gimple_convert (gimple_seq *, location_t, tree, tree);
-@end deftypefn
-
-which is supposed to replace @code{force_gimple_operand (fold_buildN (...), ...)}
-and calls to @code{fold_convert}. Overloads without the @code{location_t}
-argument exist. Built statements are inserted on the provided sequence
-and simplification is performed using the optional valueization hook.
-
-
-@node The Language
-@section The Language
-@cindex The Language
-
-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:
-
-@smallexample
-(simplify
- (bit_and @@0 integer_all_onesp)
- @@0)
-@end smallexample
-
-This example contains all required parts of an expression simplification.
-A simplification is wrapped inside a @code{(simplify ...)} 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.
-
-Expressions have an operator ID, @code{bit_and} in this case. Expressions can
-be lower-case tree codes with @code{_expr} stripped off or builtin
-function code names in all-caps, like @code{BUILT_IN_SQRT}.
-
-@code{@@n} 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{@@} followed by a number or an identifier.
-
-@smallexample
-(simplify
- (bit_xor @@0 @@0)
- @{ build_zero_cst (type); @})
-@end smallexample
-
-In this example @code{@@0} 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} 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).
-
-@smallexample
-(simplify
- (trunc_mod integer_zerop@@0 @@1)
- (if (!integer_zerop (@@1))
- @@0))
-@end smallexample
-
-Here @code{@@0} captures the first operand of the trunc_mod expression
-which is also predicated with @code{integer_zerop}. Expression operands
-may be either expressions, predicates or captures. Captures
-can be unconstrained or capture expressions or predicates.
-
-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} is a standard C
-expression which may contain references to captures. The @code{if}
-has an optional third operand which may contain the replacement
-expression that is enabled when the condition evaluates to false.
-
-A @code{if} expression can be used to specify a common condition
-for multiple simplify patterns, avoiding the need
-to repeat that multiple times:
-
-@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)))
-@end smallexample
-
-Note that @code{if}s in outer position do not have the optional
-else clause but instead have multiple then clauses.
-
-Ifs can be nested.
-
-There exists a @code{switch} expression which can be used to
-chain conditions avoiding nesting @code{if}s too much:
-
-@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); @})))
-@end smallexample
-
-Is equal to
-
-@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); @}))))
-@end smallexample
-
-which has the second @code{if} in the else operand of the first.
-The @code{switch} expression takes @code{if} 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.
-
-Captures can also be used for capturing results of sub-expressions.
-
-@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
-@end smallexample
-
-In the above example, @code{@@2} captures the result of the expression
-@code{(addr @@0)}. For the outermost expression only its type can be
-captured, and the keyword @code{type} is reserved for this purpose. The
-above example also gives a way to conditionalize patterns to only apply
-to @code{GIMPLE} or @code{GENERIC} by means of using the pre-defined
-preprocessor macros @code{GIMPLE} and @code{GENERIC} and using
-preprocessor directives.
-
-@smallexample
-(simplify
- (bit_and:c integral_op_p@@0 (bit_ior:c (bit_not @@0) @@1))
- (bit_and @@1 @@0))
-@end smallexample
-
-Here we introduce flags on match expressions. The flag used
-above, @code{c}, denotes that the expression should
-be also matched commutated. Thus the above match expression
-is really the following four match expressions:
-
-@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)
-@end smallexample
-
-Usual canonicalizations you know from GENERIC expressions are
-applied before matching, so for example constant operands always
-come second in commutative expressions.
-
-The second supported flag is @code{s} which tells the code
-generator to fail the pattern if the expression marked with
-@code{s} does have more than one use and the simplification
-results in an expression with more than one operator.
-For example in
-
-@smallexample
-(simplify
- (pointer_plus (pointer_plus:s @@0 @@1) @@3)
- (pointer_plus @@0 (plus @@1 @@3)))
-@end smallexample
-
-this avoids the association if @code{(pointer_plus @@0 @@1)} 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)} with the temporary
-holding @code{(x + 3)} used elsewhere. This simplifies down
-to @code{x} which is desirable and thus flagging with @code{s}
-does not prevent the transform. Now consider @code{((x + 3) + 1)}
-which simplifies to @code{(x + 4)}. Despite being flagged with
-@code{s} the simplification will be performed. The
-simplification of @code{((x + a) + 1)} to @code{(x + (a + 1))} will
-not performed in this case though.
-
-More features exist to avoid too much repetition.
-
-@smallexample
-(for op (plus pointer_plus minus bit_ior bit_xor)
- (simplify
- (op @@0 integer_zerop)
- @@0))
-@end smallexample
-
-A @code{for} expression can be used to repeat a pattern for each
-operator specified, substituting @code{op}. @code{for} can be
-nested and a @code{for} can have multiple operators to iterate.
-
-@smallexample
-(for opa (plus minus)
- opb (minus plus)
- (for opc (plus minus)
- (simplify...
-@end smallexample
-
-In this example the pattern will be repeated four times with
-@code{opa, opb, opc} being @code{plus, minus, plus};
-@code{plus, minus, minus}; @code{minus, plus, plus};
-@code{minus, plus, minus}.
-
-To avoid repeating operator lists in @code{for} you can name
-them via
-
-@smallexample
-(define_operator_list pmm plus minus mult)
-@end smallexample
-
-and use them in @code{for} operator lists where they get expanded.
-
-@smallexample
-(for opa (pmm trunc_div)
- (simplify...
-@end smallexample
-
-So this example iterates over @code{plus}, @code{minus}, @code{mult}
-and @code{trunc_div}.
-
-Using operator lists can also remove the need to explicitly write
-a @code{for}. All operator list uses that appear in a @code{simplify}
-or @code{match} pattern in operator positions will implicitly
-be added to a new @code{for}. For example
-
-@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); @})))
-@end smallexample
-
-is the same as
-
-@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); @}))))
-@end smallexample
-
-@code{for}s and operator lists can include the special identifier
-@code{null} 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.
-
-Another building block are @code{with} expressions in the
-result expression which nest the generated code in a new C block
-followed by its argument:
-
-@smallexample
-(simplify
- (convert (mult @@0 @@1))
- (with @{ tree utype = unsigned_type_for (type); @}
- (convert (mult (convert:utype @@0) (convert:utype @@1)))))
-@end smallexample
-
-This allows code nested in the @code{with} 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} syntax where
-@code{type} 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.
-
-Another modifier for generated expressions is @code{!} which
-tells the machinery to only consider the simplification in case
-the marked expression simplified to a simple operand. Consider
-for example
-
-@smallexample
-(simplify
- (plus (vec_cond:s @@0 @@1 @@2) @@3)
- (vec_cond @@0 (plus! @@1 @@3) (plus! @@2 @@3)))
-@end smallexample
-
-which moves the outer @code{plus} operation to the inner arms
-of the @code{vec_cond} expression but only if the actual plus
-operations both simplify. Note that on @code{GENERIC} a simple
-operand means that the result satisfies @code{!EXPR_P} which
-can be limiting if the operation itself simplifies but the
-remaining operand is an (unrelated) expression.
-
-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{?}:
-
-@smallexample
-(simplify
- (eq (convert@@0 @@1) (convert@? @@2))
- (eq @@1 (convert @@2)))
-@end smallexample
-
-which will match both @code{(eq (convert @@1) (convert @@2))} and
-@code{(eq (convert @@1) @@2)}. The optional converts are supposed
-to be all either present or not, thus
-@code{(eq (convert@? @@1) (convert@? @@2))} 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))}.
-
-The support for @code{?} marking extends to all unary operations
-including predicates you declare yourself with @code{match}.
-
-Predicates available from the GCC middle-end need to be made
-available explicitly via @code{define_predicates}:
-
-@smallexample
-(define_predicates
- integer_onep integer_zerop integer_all_onesp)
-@end smallexample
-
-You can also define predicates using the pattern matching language
-and the @code{match} form:
-
-@smallexample
-(match negate_expr_p
- INTEGER_CST
- (if (TYPE_OVERFLOW_WRAPS (type)
- || may_negate_without_overflow_p (t))))
-(match negate_expr_p
- (negate @@0))
-@end smallexample
-
-This shows that for @code{match} expressions there is @code{t}
-available which captures the outermost expression (something
-not possible in the @code{simplify} context). As you can see
-@code{match} has an identifier as first operand which is how
-you refer to the predicate in patterns. Multiple @code{match}
-for the same identifier add additional cases where the predicate
-matches.
-
-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:
-
-@smallexample
-(match (logical_inverted_value @@0)
- (eq @@0 integer_zerop))
-(match (logical_inverted_value @@0)
- (bit_not truth_valued_p@@0))
-@end smallexample
-
-You can use the above predicate like
-
-@smallexample
-(simplify
- (bit_and @@0 (logical_inverted_value @@0))
- @{ build_zero_cst (type); @})
-@end smallexample
-
-Which will match a bitwise and of an operand with its logical
-inverted value.
-