===================================================================
@@ -0,0 +1,202 @@
+@c Copyright (C) 2014 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.c, gimple-fold.c and builtins.c
+@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 addres 2) new
+APIs are introduced.
+
+@menu
+* GIMPLE API::
+* The Language::
+@end menu
+
+@node GIMPLE API
+@section GIMPLE API
+@cindex GIMPLE API
+
+The main GIMPLE API entry to the expression simplifications mimics
+that of the GENERIC fold_@{unary,binary,ternary@} API:
+
+@deftypefn
+tree gimple_match_and_simplify (enum tree_code, tree, tree,
+ gimple_seq *, tree (*)(tree));
+@end deftypefn
+@deftypefn
+tree gimple_match_and_simplify (enum tree_code, tree, tree, tree,
+ gimple_seq *, tree (*)(tree));
+@end deftypefn
+@deftypefn
+tree gimple_match_and_simplify (enum tree_code, tree, tree, tree, tree,
+ gimple_seq *, tree (*)(tree));
+@end deftypefn
+@deftypefn
+tree gimple_match_and_simplify (enum built_in_function, tree, tree,
+ gimple_seq *, tree (*)(tree));
+@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 a fold_stmt-like interface is provided with
+
+@deftypefn
+bool gimple_match_and_simplify (gimple_stmt_iterator *, tree (*)(tree));
+@end deftypefn
+
+which also has the additional valueization hook.
+
+Ontop of these a @code{fold_buildN}-like API for GIMPLE is introduced:
+
+@deftypefn
+tree gimple_build (gimple_seq *, location_t,
+ enum tree_code, tree, tree,
+ tree (*valueize) (tree) = NULL);
+@end deftypefn
+@deftypefn
+tree gimple_build (gimple_seq *, location_t,
+ enum tree_code, tree, tree, tree,
+ tree (*valueize) (tree) = NULL);
+@end deftypefn
+@deftypefn
+tree gimple_build (gimple_seq *, location_t,
+ enum tree_code, tree, tree, tree, tree,
+ tree (*valueize) (tree) = NULL);
+@end deftypefn
+@deftypefn
+tree gimple_build (gimple_seq *, location_t,
+ enum built_in_function, tree, tree,
+ tree (*valueize) (tree) = NULL);
+@end deftypefn
+
+which is supposed to replace @code{force_gimple_operand (fold_buildN (...), ...)}.
+
+
+@node The Language
+@section The Language
+@cindex The Language
+
+The language to write expression simplifications in resembles other
+domain-specific languages GCC uses. Thus it is lispy. Lets start
+with an example from the match.pd file on the branch:
+
+@smallexample
+(match_and_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{(match_and_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 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 refered to in the replacement expression.
+
+@smallexample
+(match_and_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. 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.
+
+@smallexample
+(match_and_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 expresions or predicates.
+
+This example introduces an optional operand of match_and_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. The expression operand
+of the @code{if} is a standard C expression which may contain references
+to captures.
+
+@smallexample
+(match_and_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. There is currently
+a single flag, @code{c}, which denotes that the expression should
+be also matched commutated. Thus the above match expression
+is really the following four match expressions:
+
+ (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)
+
+Usual canonicalizations you know from GENERIC expressions are
+applied before matching, so for example constant operands always
+come second in commutative expressions.
+
+Two more features exist to avoid too much repetition.
+
+@smallexample
+(for op in plus pointer_plus minus bit_ior bit_xor
+ (match_and_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}.
+
+@smallexample
+(if (!TYPE_SATURATING (type)
+ && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type))
+ (match_and_simplify
+ (minus (plus @@0 @@1) @@0)
+ @@1)
+ (match_and_simplify
+ (minus (minus @@0 @@1) @@0)
+ (negate @@1)))
+@end smallexample
+
+A @code{if} expression can be used to specify a common condition
+for multiple match-and-simplify patterns, avoiding the need
+to repeat that multiple times.
+
+
===================================================================
@@ -123,6 +123,7 @@ Additional tutorial information is linke
* Plugins:: Extending the compiler with plugins.
* LTO:: Using Link-Time Optimization.
+* Match and Simplify:: How to write expression simplification patterns for GIMPLE and GENERIC
* Funding:: How to help assure funding for free software.
* GNU Project:: The GNU Project and GNU/Linux.
@@ -158,6 +159,7 @@ Additional tutorial information is linke
@include gty.texi
@include plugins.texi
@include lto.texi
+@include match-and-simplify.texi
@include funding.texi
@include gnu.texi
===================================================================
@@ -2865,7 +2865,8 @@ TEXI_GCCINT_FILES = gccint.texi gcc-comm
configfiles.texi collect2.texi headerdirs.texi funding.texi \
gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi \
sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi \
- loop.texi generic.texi gimple.texi plugins.texi optinfo.texi
+ loop.texi generic.texi gimple.texi plugins.texi optinfo.texi \
+ match-and-simplify.texi
TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \
gcc-common.texi gcc-vers.texi