2014-10-22 Richard Biener <rguenther@suse.de>

	Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>

	* Makefile.in (OBJS): Add gimple-match.o and generic-match.o.
	(MOSTLYCLEANFILES): Add gimple-match.c and generic-match.c.
	(gimple-match.c): Generate by triggering s-match.
	(generic-match.c): Likewise.
	(s-match): Rule to build gimple-match.c and generic-match.c
	by running the genmatch generator program.
	(build/hash-table.o): Dependencies to build hash-table.c for the host.
	(build/genmatch.o): Dependencies to build genmatch.
	(genprog): Add match.
	(build/genmatch): Likewise.
	(TEXI_GCCINT_FILES): Add match-and-simplify.texi.
	* generic-match-head.c: New file.
	* gimple-match-head.c: Likewise.
	* gimple-match.h: Likewise.
	* genmatch.c: Likewise.
	* match.pd: Likewise.
	* builtins.h (fold_builtin_n): Export.
	* builtins.c (fold_builtin_n): Likewise.
	* gimple-fold.h (gimple_build): Declare various overloads.
	(gimple_simplify): Likewise.
	(gimple_convert): Re-implement in terms of gimple_build.
	* gimple-fold.c (gimple_convert): Remove.
	(gimple_build): New functions.

	* doc/match-and-simplify.texi: New file.
	* doc/gccint.texi: Add menu item Match and Simplify and include
	match-and-simplify.texi.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@216542 138bc75d-0d04-0410-961f-82ee72b054a4

13 files changed, 4648 insertions, 15 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 5ff077fbb22..b596a3857d4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,33 @@
+2014-10-22  Richard Biener  <rguenther@suse.de>
+	Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>
+
+	* Makefile.in (OBJS): Add gimple-match.o and generic-match.o.
+	(MOSTLYCLEANFILES): Add gimple-match.c and generic-match.c.
+	(gimple-match.c): Generate by triggering s-match.
+	(generic-match.c): Likewise.
+	(s-match): Rule to build gimple-match.c and generic-match.c
+	by running the genmatch generator program.
+	(build/hash-table.o): Dependencies to build hash-table.c for the host.
+	(build/genmatch.o): Dependencies to build genmatch.
+	(genprog): Add match.
+	(build/genmatch): Likewise.
+	(TEXI_GCCINT_FILES): Add match-and-simplify.texi.
+	* generic-match-head.c: New file.
+	* gimple-match-head.c: Likewise.
+	* gimple-match.h: Likewise.
+	* genmatch.c: Likewise.
+	* match.pd: Likewise.
+	* builtins.h (fold_builtin_n): Export.
+	* builtins.c (fold_builtin_n): Likewise.
+	* gimple-fold.h (gimple_build): Declare various overloads.
+	(gimple_simplify): Likewise.
+	(gimple_convert): Re-implement in terms of gimple_build.
+	* gimple-fold.c (gimple_convert): Remove.
+	(gimple_build): New functions.
+	* doc/match-and-simplify.texi: New file.
+	* doc/gccint.texi: Add menu item Match and Simplify and include
+	match-and-simplify.texi.
+
 2014-10-22  Jakub Jelinek  <jakub@redhat.com>
 
 	PR target/63594
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 1fd7915814c..6aa59ed3ee7 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -204,6 +204,8 @@ gengtype-lex.o-warn = -Wno-error
 libgcov-util.o-warn = -Wno-error
 libgcov-driver-tool.o-warn = -Wno-error
 libgcov-merge-tool.o-warn = -Wno-error
+gimple-match.o-warn = -Wno-unused-variable -Wno-unused-parameter
+generic-match.o-warn = -Wno-unused-variable -Wno-unused-parameter
 
 # All warnings have to be shut off in stage1 if the compiler used then
 # isn't gcc; configure determines that.  WARN_CFLAGS will be either
@@ -1227,6 +1229,8 @@ OBJS = \
 	gimple-iterator.o \
 	gimple-fold.o \
 	gimple-low.o \
+	gimple-match.o \
+	generic-match.o \
 	gimple-pretty-print.o \
 	gimple-ssa-isolate-paths.o \
 	gimple-ssa-strength-reduction.o \
@@ -1504,7 +1508,7 @@ MOSTLYCLEANFILES = insn-flags.h insn-config.h insn-codes.h \
  insn-output.c insn-recog.c insn-emit.c insn-extract.c insn-peep.c \
  insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \
  insn-latencytab.c insn-opinit.c insn-opinit.h insn-preds.c insn-constants.h \
- tm-preds.h tm-constrs.h checksum-options \
+ tm-preds.h tm-constrs.h checksum-options gimple-match.c generic-match.c \
  tree-check.h min-insn-modes.c insn-modes.c insn-modes.h \
  genrtl.h gt-*.h gtype-*.h gtype-desc.c gtyp-input.list \
  xgcc$(exeext) cpp$(exeext) \
@@ -2021,7 +2025,7 @@ $(common_out_object_file): $(common_out_file)
 .PRECIOUS: insn-config.h insn-flags.h insn-codes.h insn-constants.h \
   insn-emit.c insn-recog.c insn-extract.c insn-output.c insn-peep.c \
   insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \
-  insn-latencytab.c insn-preds.c
+  insn-latencytab.c insn-preds.c gimple-match.c generic-match.c
 
 # Dependencies for the md file.  The first time through, we just assume
 # the md file itself and the generated dependency file (in order to get
@@ -2230,6 +2234,20 @@ s-tm-texi: build/genhooks$(build_exeext) $(srcdir)/doc/tm.texi.in
 	  false; \
 	fi
 
+gimple-match.c: s-match gimple-match-head.c ; @true
+generic-match.c: s-match generic-match-head.c ; @true
+
+s-match: build/genmatch$(build_exeext) $(srcdir)/match*.pd
+	$(RUN_GEN) build/genmatch$(build_exeext) --gimple $(srcdir)/match.pd \
+	    > tmp-gimple-match.c
+	$(RUN_GEN) build/genmatch$(build_exeext) --generic $(srcdir)/match.pd \
+	    > tmp-generic-match.c
+	$(SHELL) $(srcdir)/../move-if-change tmp-gimple-match.c \
+	    					gimple-match.c
+	$(SHELL) $(srcdir)/../move-if-change tmp-generic-match.c \
+	    					generic-match.c
+	$(STAMP) s-match
+
 GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \
   $(host_xm_file_list) \
   $(tm_file_list) $(HASHTAB_H) $(SPLAY_TREE_H) $(srcdir)/bitmap.h \
@@ -2378,6 +2396,8 @@ build/rtl.o: rtl.c $(BCONFIG_H) coretypes.h $(GTM_H) $(SYSTEM_H)	\
   $(RTL_H) $(GGC_H) errors.h
 build/vec.o : vec.c $(BCONFIG_H) $(SYSTEM_H) coretypes.h $(VEC_H)	\
    $(GGC_H) toplev.h $(DIAGNOSTIC_CORE_H)
+build/hash-table.o : hash-table.c $(BCONFIG_H) $(SYSTEM_H) coretypes.h  \
+   $(HASH_TABLE_H) $(GGC_H) toplev.h $(DIAGNOSTIC_CORE_H)
 build/gencondmd.o : build/gencondmd.c $(BCONFIG_H) $(SYSTEM_H)		\
   coretypes.h $(GTM_H) insn-constants.h					\
   $(filter-out insn-flags.h, $(RTL_H) $(TM_P_H) $(FUNCTION_H) $(REGS_H) \
@@ -2473,6 +2493,8 @@ build/genhooks.o : genhooks.c $(TARGET_DEF) $(C_TARGET_DEF)		\
   $(COMMON_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h
 build/genmddump.o : genmddump.c $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H)	\
   coretypes.h $(GTM_H) errors.h $(READ_MD_H) gensupport.h
+build/genmatch.o : genmatch.c $(BCONFIG_H) $(SYSTEM_H) \
+  coretypes.h errors.h
 
 # Compile the programs that generate insn-* from the machine description.
 # They are compiled with $(COMPILER_FOR_BUILD), and associated libraries,
@@ -2493,11 +2515,14 @@ genprogerr = $(genprogmd) genrtl modes gtype hooks
 $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS)
 
 # Remaining build programs.
-genprog = $(genprogerr) check checksum condmd
+genprog = $(genprogerr) check checksum condmd match
 
 # These programs need libs over and above what they get from the above list.
 build/genautomata$(build_exeext) : BUILD_LIBS += -lm
 
+build/genmatch$(build_exeext) : $(CPPLIB) $(LIBIBERTY) \
+  $(BUILD_ERRORS) build/vec.o build/hash-table.o
+
 # These programs are not linked with the MD reader.
 build/gengtype$(build_exeext) : build/gengtype-lex.o build/gengtype-parse.o \
               build/gengtype-state.o build/version.o build/errors.o
@@ -2832,7 +2857,8 @@ TEXI_GCCINT_FILES = gccint.texi gcc-common.texi gcc-vers.texi		\
 	 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
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 7d07b4d6823..e47b936df55 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -180,7 +180,6 @@ static tree fold_builtin_fabs (location_t, tree, tree);
 static tree fold_builtin_abs (location_t, tree, tree);
 static tree fold_builtin_unordered_cmp (location_t, tree, tree, tree, enum tree_code,
 					enum tree_code);
-static tree fold_builtin_n (location_t, tree, tree *, int, bool);
 static tree fold_builtin_0 (location_t, tree, bool);
 static tree fold_builtin_1 (location_t, tree, tree, bool);
 static tree fold_builtin_2 (location_t, tree, tree, tree, bool);
@@ -10395,7 +10394,7 @@ fold_builtin_4 (location_t loc, tree fndecl,
 
 #define MAX_ARGS_TO_FOLD_BUILTIN 4
 
-static tree
+tree
 fold_builtin_n (location_t loc, tree fndecl, tree *args, int nargs, bool ignore)
 {
   tree ret = NULL_TREE;
diff --git a/gcc/builtins.h b/gcc/builtins.h
index dd1cdbcec7e..7261bf80458 100644
--- a/gcc/builtins.h
+++ b/gcc/builtins.h
@@ -75,6 +75,7 @@ extern tree fold_fma (location_t, tree, tree, tree, tree);
 extern bool avoid_folding_inline_builtin (tree);
 extern tree fold_call_expr (location_t, tree, bool);
 extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *);
+extern tree fold_builtin_n (location_t, tree, tree *, int, bool);
 extern bool validate_gimple_arglist (const_gimple, ...);
 extern rtx default_expand_builtin (tree, rtx, rtx, enum machine_mode, int);
 extern bool fold_builtin_next_arg (tree, bool);
diff --git a/gcc/doc/gccint.texi b/gcc/doc/gccint.texi
index 889f410c563..e5563c58de0 100644
--- a/gcc/doc/gccint.texi
+++ b/gcc/doc/gccint.texi
@@ -123,6 +123,7 @@ Additional tutorial information is linked to from
 * 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 linked to from
 @include gty.texi
 @include plugins.texi
 @include lto.texi
+@include match-and-simplify.texi
 
 @include funding.texi
 @include gnu.texi
diff --git a/gcc/doc/match-and-simplify.texi b/gcc/doc/match-and-simplify.texi
new file mode 100644
index 00000000000..d63d8b81ead
--- /dev/null
+++ b/gcc/doc/match-and-simplify.texi
@@ -0,0 +1,314 @@
+@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 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, gimple_seq *, tree (*)(tree))
+The main GIMPLE API entry to the expression simplifications mimicing
+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
+
+
+Ontop 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_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 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:
+
+@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 refered 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.  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 expresions 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.  The expression operand
+of the @code{if} is a standard C expression which may contain references
+to captures.
+
+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
+
+Ifs can be nested.
+
+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)))
+  @{
+    HOST_WIDE_INT 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 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.  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.
+
+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}.
+
+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 explicitely.
+
+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))}.
+
+Predicates available from the GCC middle-end need to be made
+available explicitely 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.
+
diff --git a/gcc/generic-match-head.c b/gcc/generic-match-head.c
new file mode 100644
index 00000000000..245f3ede456
--- /dev/null
+++ b/gcc/generic-match-head.c
@@ -0,0 +1,48 @@
+/* Preamble and helpers for the autogenerated generic-match.c file.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "stringpool.h"
+#include "stor-layout.h"
+#include "flags.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-ssa.h"
+#include "tree-ssanames.h"
+#include "gimple-fold.h"
+#include "gimple-iterator.h"
+#include "expr.h"
+#include "tree-dfa.h"
+#include "builtins.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "dumpfile.h"
+#include "gimple-match.h"
+
+
diff --git a/gcc/genmatch.c b/gcc/genmatch.c
new file mode 100644
index 00000000000..2def7fa58cd
--- /dev/null
+++ b/gcc/genmatch.c
@@ -0,0 +1,3039 @@
+/* Generate pattern matching and transform code shared between
+   GENERIC and GIMPLE folding code from match-and-simplify description.
+
+   Copyright (C) 2014 Free Software Foundation, Inc.
+   Contributed by Richard Biener <rguenther@suse.de>
+   and Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "bconfig.h"
+#include <new>
+#include <map>
+#include <utility>
+#include <string>
+#include "system.h"
+#include "coretypes.h"
+#include <cpplib.h>
+#include "errors.h"
+#include "hashtab.h"
+#include "hash-table.h"
+#include "vec.h"
+#include "is-a.h"
+
+
+/* libccp helpers.  */
+
+static struct line_maps *line_table;
+
+static bool
+#if GCC_VERSION >= 4001
+__attribute__((format (printf, 6, 0)))
+#endif
+error_cb (cpp_reader *, int, int, source_location location,
+	  unsigned int, const char *msg, va_list *ap)
+{
+  const line_map *map;
+  linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
+  expanded_location loc = linemap_expand_location (line_table, map, location);
+  fprintf (stderr, "%s:%d:%d error: ", loc.file, loc.line, loc.column);
+  vfprintf (stderr, msg, *ap);
+  fprintf (stderr, "\n");
+  FILE *f = fopen (loc.file, "r");
+  if (f)
+    {
+      char buf[128];
+      while (loc.line > 0)
+	{
+	  if (!fgets (buf, 128, f))
+	    goto notfound;
+	  if (buf[strlen (buf) - 1] != '\n')
+	    {
+	      if (loc.line > 1)
+		loc.line++;
+	    }
+	  loc.line--;
+	}
+      fprintf (stderr, "%s", buf);
+      for (int i = 0; i < loc.column - 1; ++i)
+	fputc (' ', stderr);
+      fputc ('^', stderr);
+      fputc ('\n', stderr);
+notfound:
+      fclose (f);
+    }
+  exit (1);
+}
+
+static void
+#if GCC_VERSION >= 4001
+__attribute__((format (printf, 2, 3)))
+#endif
+fatal_at (const cpp_token *tk, const char *msg, ...)
+{
+  va_list ap;
+  va_start (ap, msg);
+  error_cb (NULL, CPP_DL_FATAL, 0, tk->src_loc, 0, msg, &ap);
+  va_end (ap);
+}
+
+static void
+output_line_directive (FILE *f, source_location location,
+		       bool dumpfile = false)
+{
+  const line_map *map;
+  linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
+  expanded_location loc = linemap_expand_location (line_table, map, location);
+  if (dumpfile)
+    {
+      /* When writing to a dumpfile only dump the filename.  */
+      const char *file = strrchr (loc.file, DIR_SEPARATOR);
+      if (!file)
+	file = loc.file;
+      else
+	++file;
+      fprintf (f, "%s:%d", file, loc.line);
+    }
+  else
+    /* Other gen programs really output line directives here, at least for
+       development it's right now more convenient to have line information
+       from the generated file.  Still keep the directives as comment for now
+       to easily back-point to the meta-description.  */
+    fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
+}
+
+
+/* Pull in tree codes and builtin function codes from their
+   definition files.  */
+
+#define DEFTREECODE(SYM, STRING, TYPE, NARGS)   SYM,
+enum tree_code {
+#include "tree.def"
+CONVERT0,
+CONVERT1,
+CONVERT2,
+MAX_TREE_CODES
+};
+#undef DEFTREECODE
+
+#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
+enum built_in_function {
+#include "builtins.def"
+END_BUILTINS
+};
+#undef DEF_BUILTIN
+
+
+/* Base class for all identifiers the parser knows.  */
+
+struct id_base : typed_noop_remove<id_base>
+{
+  enum id_kind { CODE, FN, PREDICATE, USER } kind;
+
+  id_base (id_kind, const char *, int = -1);
+
+  hashval_t hashval;
+  int nargs;
+  const char *id;
+
+  /* hash_table support.  */
+  typedef id_base value_type;
+  typedef id_base compare_type;
+  static inline hashval_t hash (const value_type *);
+  static inline int equal (const value_type *, const compare_type *);
+};
+
+inline hashval_t
+id_base::hash (const value_type *op)
+{
+  return op->hashval;
+}
+
+inline int
+id_base::equal (const value_type *op1,
+			const compare_type *op2)
+{
+  return (op1->hashval == op2->hashval
+	  && strcmp (op1->id, op2->id) == 0);
+}
+
+/* Hashtable of known pattern operators.  This is pre-seeded from
+   all known tree codes and all known builtin function ids.  */
+static hash_table<id_base> *operators;
+
+id_base::id_base (id_kind kind_, const char *id_, int nargs_)
+{
+  kind = kind_;
+  id = id_;
+  nargs = nargs_;
+  hashval = htab_hash_string (id);
+}
+
+/* Identifier that maps to a tree code.  */
+
+struct operator_id : public id_base
+{
+  operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
+	       const char *tcc_)
+      : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
+  enum tree_code code;
+  const char *tcc;
+};
+
+/* Identifier that maps to a builtin function code.  */
+
+struct fn_id : public id_base
+{
+  fn_id (enum built_in_function fn_, const char *id_)
+      : id_base (id_base::FN, id_), fn (fn_) {}
+  enum built_in_function fn;
+};
+
+struct simplify;
+
+/* Identifier that maps to a user-defined predicate.  */
+
+struct predicate_id : public id_base
+{
+  predicate_id (const char *id_)
+    : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
+  vec<simplify *> matchers;
+};
+
+/* Identifier that maps to a operator defined by a 'for' directive.  */
+
+struct user_id : public id_base
+{
+  user_id (const char *id_)
+    : id_base (id_base::USER, id_), substitutes (vNULL) {}
+  vec<id_base *> substitutes;
+};
+
+template<>
+template<>
+inline bool
+is_a_helper <fn_id *>::test (id_base *id)
+{
+  return id->kind == id_base::FN;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <operator_id *>::test (id_base *id)
+{
+  return id->kind == id_base::CODE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <predicate_id *>::test (id_base *id)
+{
+  return id->kind == id_base::PREDICATE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <user_id *>::test (id_base *id)
+{
+  return id->kind == id_base::USER;
+}
+
+/* Add a predicate identifier to the hash.  */
+
+static predicate_id *
+add_predicate (const char *id)
+{
+  predicate_id *p = new predicate_id (id);
+  id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
+  if (*slot)
+    fatal ("duplicate id definition");
+  *slot = p;
+  return p;
+}
+
+/* Add a tree code identifier to the hash.  */
+
+static void
+add_operator (enum tree_code code, const char *id,
+	      const char *tcc, unsigned nargs)
+{
+  if (strcmp (tcc, "tcc_unary") != 0
+      && strcmp (tcc, "tcc_binary") != 0
+      && strcmp (tcc, "tcc_comparison") != 0
+      && strcmp (tcc, "tcc_expression") != 0
+      /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR.  */
+      && strcmp (tcc, "tcc_reference") != 0
+      /* To have INTEGER_CST and friends as "predicate operators".  */
+      && strcmp (tcc, "tcc_constant") != 0)
+    return;
+  operator_id *op = new operator_id (code, id, nargs, tcc);
+  id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
+  if (*slot)
+    fatal ("duplicate id definition");
+  *slot = op;
+}
+
+/* Add a builtin identifier to the hash.  */
+
+static void
+add_builtin (enum built_in_function code, const char *id)
+{
+  fn_id *fn = new fn_id (code, id);
+  id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
+  if (*slot)
+    fatal ("duplicate id definition");
+  *slot = fn;
+}
+
+/* Helper for easy comparing ID with tree code CODE.  */
+
+static bool
+operator==(id_base &id, enum tree_code code)
+{
+  if (operator_id *oid = dyn_cast <operator_id *> (&id))
+    return oid->code == code;
+  return false;
+}
+
+/* Lookup the identifier ID.  */
+
+id_base *
+get_operator (const char *id)
+{
+  id_base tem (id_base::CODE, id);
+
+  id_base *op = operators->find_with_hash (&tem, tem.hashval);
+  if (op)
+    return op;
+
+  /* Try all-uppercase.  */
+  char *id2 = xstrdup (id);
+  for (unsigned i = 0; i < strlen (id2); ++i)
+    id2[i] = TOUPPER (id2[i]);
+  new (&tem) id_base (id_base::CODE, id2);
+  op = operators->find_with_hash (&tem, tem.hashval);
+  if (op)
+    {
+      free (id2);
+      return op;
+    }
+
+  /* Try _EXPR appended.  */
+  id2 = (char *)xrealloc (id2, strlen (id2) + sizeof ("_EXPR") + 1);
+  strcat (id2, "_EXPR");
+  new (&tem) id_base (id_base::CODE, id2);
+  op = operators->find_with_hash (&tem, tem.hashval);
+  if (op)
+    {
+      free (id2);
+      return op;
+    }
+
+  return 0;
+}
+
+
+
+/* The AST produced by parsing of the pattern definitions.  */
+
+struct dt_operand;
+
+/* The base class for operands.  */
+
+struct operand {
+  enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR };
+  operand (enum op_type type_) : type (type_) {}
+  enum op_type type;
+  virtual void gen_transform (FILE *, const char *, bool, int,
+			      const char *, dt_operand ** = 0)
+    { gcc_unreachable  (); }
+};
+
+/* A predicate operand.  Predicates are leafs in the AST.  */
+
+struct predicate : public operand
+{
+  predicate (predicate_id *p_) : operand (OP_PREDICATE), p (p_) {}
+  predicate_id *p;
+};
+
+/* An operand that constitutes an expression.  Expressions include
+   function calls and user-defined predicate invocations.  */
+
+struct expr : public operand
+{
+  expr (id_base *operation_, bool is_commutative_ = false)
+    : operand (OP_EXPR), operation (operation_),
+      ops (vNULL), expr_type (NULL), is_commutative (is_commutative_) {}
+  void append_op (operand *op) { ops.safe_push (op); }
+  /* The operator and its operands.  */
+  id_base *operation;
+  vec<operand *> ops;
+  /* An explicitely specified type - used exclusively for conversions.  */
+  const char *expr_type;
+  /* Whether the operation is to be applied commutatively.  This is
+     later lowered to two separate patterns.  */
+  bool is_commutative;
+  virtual void gen_transform (FILE *f, const char *, bool, int,
+			      const char *, dt_operand ** = 0);
+};
+
+/* An operator that is represented by native C code.  This is always
+   a leaf operand in the AST.  This class is also used to represent
+   the code to be generated for 'if' and 'with' expressions.  */
+
+struct c_expr : public operand
+{
+  /* A mapping of an identifier and its replacement.  Used to apply
+     'for' lowering.  */
+  struct id_tab {
+    const char *id;
+    const char *oper;
+    id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
+  };
+
+  c_expr (cpp_reader *r_, vec<cpp_token> code_, unsigned nr_stmts_,
+	  vec<id_tab> ids_, std::map<std::string, unsigned> *capture_ids_)
+    : operand (OP_C_EXPR), r (r_), code (code_), capture_ids (capture_ids_),
+      nr_stmts (nr_stmts_), ids (ids_) {}
+  /* cpplib tokens and state to transform this back to source.  */
+  cpp_reader *r;
+  vec<cpp_token> code;
+  std::map<std::string, unsigned> *capture_ids;
+  /* The number of statements parsed (well, the number of ';'s).  */
+  unsigned nr_stmts;
+  /* The identifier replacement vector.  */
+  vec<id_tab> ids;
+  virtual void gen_transform (FILE *f, const char *, bool, int,
+			      const char *, dt_operand **);
+};
+
+/* A wrapper around another operand that captures its value.  */
+
+struct capture : public operand
+{
+  capture (unsigned where_, operand *what_)
+      : operand (OP_CAPTURE), where (where_), what (what_) {}
+  /* Identifier index for the value.  */
+  unsigned where;
+  /* The captured value.  */
+  operand *what;
+  virtual void gen_transform (FILE *f, const char *, bool, int,
+			      const char *, dt_operand ** = 0);
+};
+
+template<>
+template<>
+inline bool
+is_a_helper <capture *>::test (operand *op)
+{
+  return op->type == operand::OP_CAPTURE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <predicate *>::test (operand *op)
+{
+  return op->type == operand::OP_PREDICATE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <c_expr *>::test (operand *op)
+{
+  return op->type == operand::OP_C_EXPR;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <expr *>::test (operand *op)
+{
+  return op->type == operand::OP_EXPR;
+}
+
+/* Helper to distinguish 'if' from 'with' expressions.  */
+
+struct if_or_with
+{
+  if_or_with (operand *cexpr_, source_location location_, bool is_with_)
+      : location (location_), cexpr (cexpr_), is_with (is_with_) {}
+  source_location location;
+  operand *cexpr;
+  bool is_with;
+};
+
+/* The main class of a pattern and its transform.  This is used to
+   represent both (simplify ...) and (match ...) kinds.  The AST
+   duplicates all outer 'if' and 'for' expressions here so each
+   simplify can exist in isolation.  */
+
+struct simplify
+{
+  simplify (operand *match_, source_location match_location_,
+	    struct operand *result_, source_location result_location_,
+	    vec<if_or_with> ifexpr_vec_, vec<vec<user_id *> > for_vec_,
+	    std::map<std::string, unsigned> *capture_ids_)
+      : match (match_), match_location (match_location_),
+      result (result_), result_location (result_location_),
+      ifexpr_vec (ifexpr_vec_), for_vec (for_vec_),
+      capture_ids (capture_ids_), capture_max (capture_ids_->size () - 1) {}
+
+  /* The expression that is matched against the GENERIC or GIMPLE IL.  */
+  operand *match;
+  source_location match_location;
+  /* For a (simplify ...) the expression produced when the pattern applies.
+     For a (match ...) either NULL if it is a simple predicate or the
+     single expression specifying the matched operands.  */
+  struct operand *result;
+  source_location result_location;
+  /* Collected 'if' expressions that need to evaluate to true to make
+     the pattern apply.  */
+  vec<if_or_with> ifexpr_vec;
+  /* Collected 'for' expression operators that have to be replaced
+     in the lowering phase.  */
+  vec<vec<user_id *> > for_vec;
+  /* A map of capture identifiers to indexes.  */
+  std::map<std::string, unsigned> *capture_ids;
+  int capture_max;
+};
+
+/* Debugging routines for dumping the AST.  */
+
+DEBUG_FUNCTION void
+print_operand (operand *o, FILE *f = stderr, bool flattened = false)
+{
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      fprintf (f, "@%u", c->where);
+      if (c->what && flattened == false)
+	{
+	  putc (':', f);
+	  print_operand (c->what, f, flattened);
+	  putc (' ', f);
+	}
+    }
+
+  else if (predicate *p = dyn_cast<predicate *> (o))
+    fprintf (f, "%s", p->p->id);
+
+  else if (is_a<c_expr *> (o))
+    fprintf (f, "c_expr");
+
+  else if (expr *e = dyn_cast<expr *> (o))
+    {
+      fprintf (f, "(%s", e->operation->id);
+
+      if (flattened == false)
+	{
+	  putc (' ', f);
+	  for (unsigned i = 0; i < e->ops.length (); ++i)
+	    {
+	      print_operand (e->ops[i], f, flattened);
+	      putc (' ', f);
+	    }
+	}
+      putc (')', f);
+    }
+
+  else
+    gcc_unreachable ();
+}
+
+DEBUG_FUNCTION void
+print_matches (struct simplify *s, FILE *f = stderr)
+{
+  fprintf (f, "for expression: ");
+  print_operand (s->match, f);
+  putc ('\n', f);
+}
+
+
+/* AST lowering.  */
+
+/* Lowering of commutative operators.  */
+
+static void
+cartesian_product (const vec< vec<operand *> >& ops_vector,
+		   vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
+{
+  if (n == ops_vector.length ())
+    {
+      vec<operand *> xv = v.copy ();
+      result.safe_push (xv);
+      return;
+    }
+
+  for (unsigned i = 0; i < ops_vector[n].length (); ++i)
+    {
+      v[n] = ops_vector[n][i];
+      cartesian_product (ops_vector, result, v, n + 1);
+    }
+}
+
+/* Lower OP to two operands in case it is marked as commutative.  */
+
+static vec<operand *>
+commutate (operand *op)
+{
+  vec<operand *> ret = vNULL;
+
+  if (capture *c = dyn_cast <capture *> (op))
+    {
+      if (!c->what)
+	{
+	  ret.safe_push (op);
+	  return ret;
+	}
+      vec<operand *> v = commutate (c->what);
+      for (unsigned i = 0; i < v.length (); ++i)
+	{
+	  capture *nc = new capture (c->where, v[i]);
+	  ret.safe_push (nc);
+	}
+      return ret;
+    }
+
+  expr *e = dyn_cast <expr *> (op);
+  if (!e || e->ops.length () == 0)
+    {
+      ret.safe_push (op);
+      return ret;
+    }
+
+  vec< vec<operand *> > ops_vector = vNULL;
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ops_vector.safe_push (commutate (e->ops[i]));
+
+  auto_vec< vec<operand *> > result;
+  auto_vec<operand *> v (e->ops.length ());
+  v.quick_grow_cleared (e->ops.length ());
+  cartesian_product (ops_vector, result, v, 0);
+
+
+  for (unsigned i = 0; i < result.length (); ++i)
+    {
+      expr *ne = new expr (e->operation);
+      for (unsigned j = 0; j < result[i].length (); ++j)
+	ne->append_op (result[i][j]);
+      ret.safe_push (ne);
+    }
+
+  if (!e->is_commutative)
+    return ret;
+
+  for (unsigned i = 0; i < result.length (); ++i)
+    {
+      expr *ne = new expr (e->operation);
+      // result[i].length () is 2 since e->operation is binary
+      for (unsigned j = result[i].length (); j; --j)
+	ne->append_op (result[i][j-1]);
+      ret.safe_push (ne);
+    }
+
+  return ret;
+}
+
+/* Lower operations marked as commutative in the AST of S and push
+   the resulting patterns to SIMPLIFIERS.  */
+
+static void
+lower_commutative (simplify *s, vec<simplify *>& simplifiers)
+{
+  vec<operand *> matchers = commutate (s->match);
+  for (unsigned i = 0; i < matchers.length (); ++i)
+    {
+      simplify *ns = new simplify (matchers[i], s->match_location,
+				   s->result, s->result_location, s->ifexpr_vec,
+				   s->for_vec, s->capture_ids);
+      simplifiers.safe_push (ns);
+    }
+}
+
+/* Strip conditional conversios using operator OPER from O and its
+   children if STRIP, else replace them with an unconditional convert.  */
+
+operand *
+lower_opt_convert (operand *o, enum tree_code oper, bool strip)
+{
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      if (c->what)
+	return new capture (c->where, lower_opt_convert (c->what, oper, strip));
+      else
+	return c;
+    }
+
+  expr *e = dyn_cast<expr *> (o);
+  if (!e)
+    return o;
+
+  if (*e->operation == oper)
+    {
+      if (strip)
+	return lower_opt_convert (e->ops[0], oper, strip);
+
+      expr *ne = new expr (get_operator ("CONVERT_EXPR"));
+      ne->append_op (lower_opt_convert (e->ops[0], oper, strip));
+      return ne;
+    }
+
+  expr *ne = new expr (e->operation, e->is_commutative);
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ne->append_op (lower_opt_convert (e->ops[i], oper, strip));
+
+  return ne;
+}
+
+/* Determine whether O or its children uses the conditional conversion
+   operator OPER.  */
+
+static bool
+has_opt_convert (operand *o, enum tree_code oper)
+{
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      if (c->what)
+	return has_opt_convert (c->what, oper);
+      else
+	return false;
+    }
+
+  expr *e = dyn_cast<expr *> (o);
+  if (!e)
+    return false;
+
+  if (*e->operation == oper)
+    return true;
+
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    if (has_opt_convert (e->ops[i], oper))
+      return true;
+
+  return false;
+}
+
+/* Lower conditional convert operators in O, expanding it to a vector
+   if required.  */
+
+static vec<operand *>
+lower_opt_convert (operand *o)
+{
+  vec<operand *> v1 = vNULL, v2;
+
+  v1.safe_push (o);
+
+  enum tree_code opers[] = { CONVERT0, CONVERT1, CONVERT2 };
+
+  /* Conditional converts are lowered to a pattern with the
+     conversion and one without.  The three different conditional
+     convert codes are lowered separately.  */
+
+  for (unsigned i = 0; i < 3; ++i)
+    {
+      v2 = vNULL;
+      for (unsigned j = 0; j < v1.length (); ++j)
+	if (has_opt_convert (v1[j], opers[i]))
+	  {
+	    v2.safe_push (lower_opt_convert (v1[j], opers[i], false));
+	    v2.safe_push (lower_opt_convert (v1[j], opers[i], true));
+	  }
+
+      if (v2 != vNULL)
+	{
+	  v1 = vNULL;
+	  for (unsigned j = 0; j < v2.length (); ++j)
+	    v1.safe_push (v2[j]);
+	}
+    }
+
+  return v1;
+}
+
+/* Lower conditional convert operators in the AST of S and push
+   the resulting multiple patterns to SIMPLIFIERS.  */
+
+static void
+lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
+{
+  vec<operand *> matchers = lower_opt_convert (s->match);
+  for (unsigned i = 0; i < matchers.length (); ++i)
+    {
+      simplify *ns = new simplify (matchers[i], s->match_location,
+				   s->result, s->result_location, s->ifexpr_vec,
+				   s->for_vec, s->capture_ids);
+      simplifiers.safe_push (ns);
+    }
+}
+
+/* In AST operand O replace operator ID with operator WITH.  */
+
+operand *
+replace_id (operand *o, user_id *id, id_base *with)
+{
+  /* Deep-copy captures and expressions, replacing operations as
+     needed.  */
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      if (!c->what)
+	return c;
+      return new capture (c->where, replace_id (c->what, id, with));
+    }
+  else if (expr *e = dyn_cast<expr *> (o))
+    {
+      expr *ne = new expr (e->operation == id ? with : e->operation,
+			   e->is_commutative);
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	ne->append_op (replace_id (e->ops[i], id, with));
+      return ne;
+    }
+
+  /* For c_expr we simply record a string replacement table which is
+     applied at code-generation time.  */
+  if (c_expr *ce = dyn_cast<c_expr *> (o))
+    {
+      vec<c_expr::id_tab> ids = ce->ids.copy ();
+      ids.safe_push (c_expr::id_tab (id->id, with->id));
+      return new c_expr (ce->r, ce->code, ce->nr_stmts, ids, ce->capture_ids);
+    }
+
+  return o;
+}
+
+/* Lower recorded fors for SIN and output to SIMPLIFIERS.  */
+
+static void
+lower_for (simplify *sin, vec<simplify *>& simplifiers)
+{
+  vec<vec<user_id *> >& for_vec = sin->for_vec;
+  unsigned worklist_start = 0;
+  auto_vec<simplify *> worklist;
+  worklist.safe_push (sin);
+
+  /* Lower each recorded for separately, operating on the
+     set of simplifiers created by the previous one.
+     Lower inner-to-outer so inner for substitutes can refer
+     to operators replaced by outer fors.  */
+  for (int fi = for_vec.length () - 1; fi >= 0; --fi)
+    {
+      vec<user_id *>& ids = for_vec[fi];
+      unsigned n_ids = ids.length ();
+      unsigned max_n_opers = 0;
+      for (unsigned i = 0; i < n_ids; ++i)
+	if (ids[i]->substitutes.length () > max_n_opers)
+	  max_n_opers = ids[i]->substitutes.length ();
+
+      unsigned worklist_end = worklist.length ();
+      for (unsigned si = worklist_start; si < worklist_end; ++si)
+	{
+	  simplify *s = worklist[si];
+	  for (unsigned j = 0; j < max_n_opers; ++j)
+	    {
+	      operand *match_op = s->match;
+	      operand *result_op = s->result;
+	      vec<if_or_with> ifexpr_vec = s->ifexpr_vec.copy ();
+
+	      for (unsigned i = 0; i < n_ids; ++i)
+		{
+		  user_id *id = ids[i];
+		  id_base *oper = id->substitutes[j % id->substitutes.length ()];
+		  match_op = replace_id (match_op, id, oper);
+		  if (result_op)
+		    result_op = replace_id (result_op, id, oper);
+		  for (unsigned k = 0; k < s->ifexpr_vec.length (); ++k)
+		    ifexpr_vec[k].cexpr = replace_id (ifexpr_vec[k].cexpr,
+						      id, oper);
+		}
+	      simplify *ns = new simplify (match_op, s->match_location,
+					   result_op, s->result_location,
+					   ifexpr_vec, vNULL, s->capture_ids);
+	      worklist.safe_push (ns);
+	    }
+	}
+      worklist_start = worklist_end;
+    }
+
+  /* Copy out the result from the last for lowering.  */
+  for (unsigned i = worklist_start; i < worklist.length (); ++i)
+    simplifiers.safe_push (worklist[i]);
+}
+
+/* Lower the AST for everything in SIMPLIFIERS.  */
+
+static void
+lower (vec<simplify *>& simplifiers)
+{
+  auto_vec<simplify *> out_simplifiers0;
+  for (unsigned i = 0; i < simplifiers.length (); ++i)
+    lower_opt_convert (simplifiers[i], out_simplifiers0);
+
+  auto_vec<simplify *> out_simplifiers1;
+  for (unsigned i = 0; i < out_simplifiers0.length (); ++i)
+    lower_commutative (out_simplifiers0[i], out_simplifiers1);
+
+  simplifiers.truncate (0);
+  for (unsigned i = 0; i < out_simplifiers1.length (); ++i)
+    lower_for (out_simplifiers1[i], simplifiers);
+}
+
+
+
+
+/* The decision tree built for generating GIMPLE and GENERIC pattern
+   matching code.  It represents the 'match' expression of all
+   simplifies and has those as its leafs.  */
+
+/* Decision tree base class, used for DT_TRUE and DT_NODE.  */
+
+struct dt_node
+{
+  enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
+
+  enum dt_type type;
+  unsigned level;
+  vec<dt_node *> kids;
+
+  dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
+
+  dt_node *append_node (dt_node *);
+  dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_simplify (simplify *, unsigned, dt_operand **);
+
+  virtual void gen (FILE *, bool) {}
+
+  void gen_kids (FILE *, bool);
+};
+
+/* Generic decision tree node used for DT_OPERAND and DT_MATCH.  */
+
+struct dt_operand : public dt_node
+{
+  operand *op;
+  dt_operand *match_dop;
+  dt_operand *parent;
+  unsigned pos;
+
+  dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
+	      dt_operand *parent_ = 0, unsigned pos_ = 0)
+      : dt_node (type), op (op_), match_dop (match_dop_),
+      parent (parent_), pos (pos_) {}
+
+  void gen (FILE *, bool);
+  unsigned gen_predicate (FILE *, const char *, bool);
+  unsigned gen_match_op (FILE *, const char *);
+
+  unsigned gen_gimple_expr (FILE *);
+  unsigned gen_generic_expr (FILE *, const char *);
+
+  char *get_name (char *);
+  void gen_opname (char *, unsigned);
+};
+
+/* Leaf node of the decision tree, used for DT_SIMPLIFY.  */
+
+struct dt_simplify : public dt_node
+{
+  simplify *s;
+  unsigned pattern_no;
+  dt_operand **indexes;
+
+  dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
+	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
+	  indexes (indexes_)  {}
+
+  void gen (FILE *f, bool);
+};
+
+template<>
+template<>
+inline bool
+is_a_helper <dt_operand *>::test (dt_node *n)
+{
+  return (n->type == dt_node::DT_OPERAND
+	  || n->type == dt_node::DT_MATCH);
+}
+
+/* A container for the actual decision tree.  */
+
+struct decision_tree
+{
+  dt_node *root;
+
+  void insert (struct simplify *, unsigned);
+  void gen_gimple (FILE *f = stderr);
+  void gen_generic (FILE *f = stderr);
+  void print (FILE *f = stderr);
+
+  decision_tree () { root = new dt_node (dt_node::DT_NODE); }
+
+  static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
+				  unsigned pos = 0, dt_node *parent = 0);
+  static dt_node *find_node (vec<dt_node *>&, dt_node *);
+  static bool cmp_node (dt_node *, dt_node *);
+  static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
+};
+
+/* Compare two AST operands O1 and O2 and return true if they are equal.  */
+
+bool
+cmp_operand (operand *o1, operand *o2)
+{
+  if (!o1 || !o2 || o1->type != o2->type)
+    return false;
+
+  if (o1->type == operand::OP_PREDICATE)
+    {
+      predicate *p1 = as_a<predicate *>(o1);
+      predicate *p2 = as_a<predicate *>(o2);
+      return p1->p == p2->p;
+    }
+  else if (o1->type == operand::OP_EXPR)
+    {
+      expr *e1 = static_cast<expr *>(o1);
+      expr *e2 = static_cast<expr *>(o2);
+      return e1->operation == e2->operation;
+    }
+  else
+    return false;
+}
+
+/* Compare two decision tree nodes N1 and N2 and return true if they
+   are equal.  */
+
+bool
+decision_tree::cmp_node (dt_node *n1, dt_node *n2)
+{
+  if (!n1 || !n2 || n1->type != n2->type)
+    return false;
+
+  if (n1 == n2 || n1->type == dt_node::DT_TRUE)
+    return true;
+
+  if (n1->type == dt_node::DT_OPERAND)
+    return cmp_operand ((as_a<dt_operand *> (n1))->op,
+			(as_a<dt_operand *> (n2))->op);
+  else if (n1->type == dt_node::DT_MATCH)
+    return ((as_a<dt_operand *> (n1))->match_dop
+	    == (as_a<dt_operand *> (n2))->match_dop);
+  return false;
+}
+
+/* Search OPS for a decision tree node like P and return it if found.  */
+
+dt_node *
+decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
+{
+  for (unsigned i = 0; i < ops.length (); ++i)
+    if (decision_tree::cmp_node (ops[i], p))
+      return ops[i];
+
+  return NULL;
+}
+
+/* Append N to the decision tree if it there is not already an existing
+   identical child.  */
+
+dt_node *
+dt_node::append_node (dt_node *n)
+{
+  dt_node *kid;
+
+  kid = decision_tree::find_node (kids, n);
+  if (kid)
+    return kid;
+
+  kids.safe_push (n);
+  n->level = this->level + 1;
+
+  unsigned len = kids.length ();
+
+  if (len > 1 && kids[len - 2]->type == dt_node::DT_TRUE)
+    {
+      dt_node *p = kids[len - 2];
+      kids[len - 2] = kids[len - 1];
+      kids[len - 1] = p;
+    }
+
+  return n;
+}
+
+/* Append OP to the decision tree.  */
+
+dt_node *
+dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
+  dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
+  return append_node (n);
+}
+
+/* Append a DT_TRUE decision tree node.  */
+
+dt_node *
+dt_node::append_true_op (dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = as_a<dt_operand *> (parent);
+  dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
+  return append_node (n);
+}
+
+/* Append a DT_MATCH decision tree node.  */
+
+dt_node *
+dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = as_a<dt_operand *> (parent);
+  dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
+  return append_node (n);
+}
+
+/* Append S to the decision tree.  */
+
+dt_node *
+dt_node::append_simplify (simplify *s, unsigned pattern_no,
+			  dt_operand **indexes)
+{
+  dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
+  return append_node (n);
+}
+
+/* Insert O into the decision tree and return the decision tree node found
+   or created.  */
+
+dt_node *
+decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
+			       unsigned pos, dt_node *parent)
+{
+  dt_node *q, *elm = 0;
+
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      unsigned capt_index = c->where;
+
+      if (indexes[capt_index] == 0)
+	{
+	  if (c->what)
+	    q = insert_operand (p, c->what, indexes, pos, parent);
+	  else
+	    {
+	      q = elm = p->append_true_op (parent, pos);
+	      goto at_assert_elm;
+	    }
+	  // get to the last capture
+	  for (operand *what = c->what;
+	       what && is_a<capture *> (what);
+	       c = as_a<capture *> (what), what = c->what)
+	    ;
+
+	  if (!c->what)
+	    {
+	      unsigned cc_index = c->where;
+	      dt_operand *match_op = indexes[cc_index];
+
+	      dt_operand temp (dt_node::DT_TRUE, 0, 0);
+	      elm = decision_tree::find_node (p->kids, &temp);
+
+	      if (elm == 0)
+		{
+		  dt_operand temp (dt_node::DT_MATCH, 0, match_op);
+		  elm = decision_tree::find_node (p->kids, &temp);
+		}
+	    }
+	  else
+	    {
+	      dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
+	      elm = decision_tree::find_node (p->kids, &temp);
+	    }
+
+at_assert_elm:
+	  gcc_assert (elm->type == dt_node::DT_TRUE
+		      || elm->type == dt_node::DT_OPERAND
+		      || elm->type == dt_node::DT_MATCH);
+	  indexes[capt_index] = static_cast<dt_operand *> (elm);
+	  return q;
+	}
+      else
+	{
+	  p = p->append_match_op (indexes[capt_index], parent, pos);
+	  if (c->what)
+	    return insert_operand (p, c->what, indexes, 0, p);
+	  else
+	    return p;
+	}
+    }
+  p = p->append_op (o, parent, pos);
+  q = p;
+
+  if (expr *e = dyn_cast <expr *>(o))
+    {
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
+    }
+
+  return q;
+}
+
+/* Insert S into the decision tree.  */
+
+void
+decision_tree::insert (struct simplify *s, unsigned pattern_no)
+{
+  if (s->match->type != operand::OP_EXPR)
+    return;
+
+  dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
+  dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
+  p->append_simplify (s, pattern_no, indexes);
+}
+
+/* Debug functions to dump the decision tree.  */
+
+DEBUG_FUNCTION void
+decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
+{
+  if (p->type == dt_node::DT_NODE)
+    fprintf (f, "root");
+  else
+    {
+      fprintf (f, "|");
+      for (unsigned i = 0; i < indent; i++)
+	fprintf (f, "-");
+
+      if (p->type == dt_node::DT_OPERAND)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(p);
+	  print_operand (dop->op, f, true);
+	}
+      else if (p->type == dt_node::DT_TRUE)
+	fprintf (f, "true");
+      else if (p->type == dt_node::DT_MATCH)
+	fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
+      else if (p->type == dt_node::DT_SIMPLIFY)
+	{
+	  dt_simplify *s = static_cast<dt_simplify *> (p);
+	  fprintf (f, "simplify_%u { ", s->pattern_no);
+	  for (int i = 0; i <= s->s->capture_max; ++i)
+	    fprintf (f, "%p, ", (void *) s->indexes[i]);
+	  fprintf (f, " } ");
+	}
+    }
+
+  fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
+
+  for (unsigned i = 0; i < p->kids.length (); ++i)
+    decision_tree::print_node (p->kids[i], f, indent + 2);
+}
+
+DEBUG_FUNCTION void
+decision_tree::print (FILE *f)
+{
+  return decision_tree::print_node (root, f);
+}
+
+
+
+/* Code generation off the decision tree and the refered AST nodes.  */
+
+bool
+is_conversion (id_base *op)
+{
+  return (*op == CONVERT_EXPR
+	  || *op == NOP_EXPR
+	  || *op == FLOAT_EXPR
+	  || *op == FIX_TRUNC_EXPR
+	  || *op == VIEW_CONVERT_EXPR);
+}
+
+/* Get the type to be used for generating operands of OP from the
+   various sources.  */
+
+static const char *
+get_operand_type (id_base *op, const char *in_type,
+		  const char *expr_type,
+		  const char *other_oprnd_type)
+{
+  /* Generally operands whose type does not match the type of the
+     expression generated need to know their types but match and
+     thus can fall back to 'other_oprnd_type'.  */
+  if (is_conversion (op))
+    return other_oprnd_type;
+  else if (*op == REALPART_EXPR
+	   || *op == IMAGPART_EXPR)
+    return other_oprnd_type;
+  else if (is_a <operator_id *> (op)
+	   && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
+    return other_oprnd_type;
+  else
+    {
+      /* Otherwise all types should match - choose one in order of
+         preference.  */
+      if (expr_type)
+	return expr_type;
+      else if (in_type)
+	return in_type;
+      else
+	return other_oprnd_type;
+    }
+}
+
+/* Generate transform code for an expression.  */
+
+void
+expr::gen_transform (FILE *f, const char *dest, bool gimple, int depth,
+		     const char *in_type, dt_operand **indexes)
+{
+  bool conversion_p = is_conversion (operation);
+  const char *type = expr_type;
+  char optype[64];
+  if (type)
+    /* If there was a type specification in the pattern use it.  */
+    ;
+  else if (conversion_p)
+    /* For conversions we need to build the expression using the
+       outer type passed in.  */
+    type = in_type;
+  else if (*operation == REALPART_EXPR
+	   || *operation == IMAGPART_EXPR)
+    {
+      /* __real and __imag use the component type of its operand.  */
+      sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
+      type = optype;
+    }
+  else if (is_a <operator_id *> (operation)
+	   && !strcmp (as_a <operator_id *> (operation)->tcc, "tcc_comparison"))
+    {
+      /* comparisons use boolean_type_node (or what gets in), but
+         their operands need to figure out the types themselves.  */
+      sprintf (optype, "boolean_type_node");
+      type = optype;
+    }
+  else
+    {
+      /* Other operations are of the same type as their first operand.  */
+      sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
+      type = optype;
+    }
+  if (!type)
+    fatal ("two conversions in a row");
+
+  fprintf (f, "{\n");
+  fprintf (f, "  tree ops%d[%u], res;\n", depth, ops.length ());
+  char op0type[64];
+  snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
+  for (unsigned i = 0; i < ops.length (); ++i)
+    {
+      char dest[32];
+      snprintf (dest, 32, "  ops%d[%u]", depth, i);
+      const char *optype
+	= get_operand_type (operation, in_type, expr_type,
+			    i == 0 ? NULL : op0type);
+      ops[i]->gen_transform (f, dest, gimple, depth + 1, optype, indexes);
+    }
+
+  if (gimple)
+    {
+      /* ???  Have another helper that is like gimple_build but may
+	 fail if seq == NULL.  */
+      fprintf (f, "  if (!seq)\n"
+	       "    {\n"
+	       "      res = gimple_simplify (%s, %s",
+	       operation->id, type);
+      for (unsigned i = 0; i < ops.length (); ++i)
+	fprintf (f, ", ops%d[%u]", depth, i);
+      fprintf (f, ", seq, valueize);\n");
+      fprintf (f, "      if (!res) return false;\n");
+      fprintf (f, "    }\n");
+      fprintf (f, "  else\n");
+      fprintf (f, "    res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
+	       operation->id, type);
+      for (unsigned i = 0; i < ops.length (); ++i)
+	fprintf (f, ", ops%d[%u]", depth, i);
+      fprintf (f, ", valueize);\n");
+    }
+  else
+    {
+      if (operation->kind == id_base::CODE)
+	fprintf (f, "  res = fold_build%d (%s, %s",
+		 ops.length(), operation->id, type);
+      else
+	fprintf (f, "  res = build_call_expr (builtin_decl_implicit (%s), %d",
+		 operation->id, ops.length());
+      for (unsigned i = 0; i < ops.length (); ++i)
+	fprintf (f, ", ops%d[%u]", depth, i);
+      fprintf (f, ");\n");
+    }
+  fprintf (f, "  %s = res;\n", dest);
+  fprintf (f, "}\n");
+}
+
+/* Generate code for a c_expr which is either the expression inside
+   an if statement or a sequence of statements which computes a
+   result to be stored to DEST.  */
+
+void
+c_expr::gen_transform (FILE *f, const char *dest,
+		       bool, int, const char *, dt_operand **)
+{
+  if (dest && nr_stmts == 1)
+    fprintf (f, "%s = ", dest);
+
+  unsigned stmt_nr = 1;
+  for (unsigned i = 0; i < code.length (); ++i)
+    {
+      const cpp_token *token = &code[i];
+
+      /* Replace captures for code-gen.  */
+      if (token->type == CPP_ATSIGN)
+	{
+	  const cpp_token *n = &code[i+1];
+	  if ((n->type == CPP_NUMBER
+	       || n->type == CPP_NAME)
+	      && !(n->flags & PREV_WHITE))
+	    {
+	      if (token->flags & PREV_WHITE)
+		fputc (' ', f);
+	      const char *id;
+	      if (n->type == CPP_NUMBER)
+		id = (const char *)n->val.str.text;
+	      else
+		id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
+	      fprintf (f, "captures[%u]", (*capture_ids)[id]);
+	      ++i;
+	      continue;
+	    }
+	}
+
+      if (token->flags & PREV_WHITE)
+	fputc (' ', f);
+
+      if (token->type == CPP_NAME)
+	{
+	  const char *id = (const char *) NODE_NAME (token->val.node.node);
+	  unsigned j;
+	  for (j = 0; j < ids.length (); ++j)
+	    {
+	    if (strcmp (id, ids[j].id) == 0)
+	      {
+		fprintf (f, "%s", ids[j].oper);
+		break;
+	      }
+	    }
+	  if (j < ids.length ())
+	    continue;
+	}
+
+      /* Output the token as string.  */
+      char *tk = (char *)cpp_token_as_text (r, token);
+      fputs (tk, f);
+
+      if (token->type == CPP_SEMICOLON)
+	{
+	  stmt_nr++;
+	  if (dest && stmt_nr == nr_stmts)
+	    fprintf (f, "\n %s = ", dest);
+	  else
+	    fputc ('\n', f);
+	}
+    }
+}
+
+/* Generate transform code for a capture.  */
+
+void
+capture::gen_transform (FILE *f, const char *dest, bool gimple, int depth,
+			const char *in_type, dt_operand **indexes)
+{
+  if (what && is_a<expr *> (what))
+    {
+      if (indexes[where] == 0)
+	{
+	  char buf[20];
+	  sprintf (buf, "captures[%u]", where);
+	  what->gen_transform (f, buf, gimple, depth, in_type, NULL);
+	}
+    }
+
+  fprintf (f, "%s = captures[%u];\n", dest, where);
+}
+
+/* Return the name of the operand representing the decision tree node.
+   Use NAME as space to generate it.  */
+
+char *
+dt_operand::get_name (char *name)
+{
+  if (!parent)
+    sprintf (name, "t");
+  else if (parent->level == 1)
+    sprintf (name, "op%u", pos);
+  else if (parent->type == dt_node::DT_MATCH)
+    return parent->get_name (name);
+  else
+    sprintf (name, "o%u%u", parent->level, pos);
+  return name;
+}
+
+/* Fill NAME with the operand name at position POS.  */
+
+void
+dt_operand::gen_opname (char *name, unsigned pos)
+{
+  if (!parent)
+    sprintf (name, "op%u", pos);
+  else
+    sprintf (name, "o%u%u", level, pos);
+}
+
+/* Generate matching code for the decision tree operand which is
+   a predicate.  */
+
+unsigned
+dt_operand::gen_predicate (FILE *f, const char *opname, bool gimple)
+{
+  predicate *p = as_a <predicate *> (op);
+
+  if (p->p->matchers.exists ())
+    {
+      /* If this is a predicate generated from a pattern mangle its
+	 name and pass on the valueize hook.  */
+      if (gimple)
+	fprintf (f, "if (gimple_%s (%s, valueize))\n", p->p->id, opname);
+      else
+	fprintf (f, "if (tree_%s (%s))\n", p->p->id, opname);
+    }
+  else
+    fprintf (f, "if (%s (%s))\n", p->p->id, opname);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+/* Generate matching code for the decision tree operand which is
+   a capture-match.  */
+
+unsigned
+dt_operand::gen_match_op (FILE *f, const char *opname)
+{
+  char match_opname[20];
+  match_dop->get_name (match_opname);
+  fprintf (f, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
+	   opname, match_opname, opname, match_opname);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+/* Generate GIMPLE matching code for the decision tree operand.  */
+
+unsigned
+dt_operand::gen_gimple_expr (FILE *f)
+{
+  expr *e = static_cast<expr *> (op);
+  id_base *id = e->operation;
+  unsigned n_ops = e->ops.length ();
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      gen_opname (child_opname, i);
+
+      if (id->kind == id_base::CODE)
+	{
+	  if (*id == REALPART_EXPR || *id == IMAGPART_EXPR
+	      || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
+	    {
+	      /* ???  If this is a memory operation we can't (and should not)
+		 match this.  The only sensible operand types are
+		 SSA names and invariants.  */
+	      fprintf (f, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
+		       child_opname, i);
+	      fprintf (f, "if ((TREE_CODE (%s) == SSA_NAME\n"
+		       "|| is_gimple_min_invariant (%s))\n"
+		       "&& (%s = do_valueize (valueize, %s)))\n"
+		       "{\n", child_opname, child_opname, child_opname,
+		       child_opname);
+	      continue;
+	    }
+	  else
+	    fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
+		     child_opname, i + 1);
+	}
+      else
+	fprintf (f, "tree %s = gimple_call_arg (def_stmt, %u);\n",
+		 child_opname, i);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
+	       child_opname, child_opname);
+      fprintf (f, "{\n");
+    }
+
+  return n_ops;
+}
+
+/* Generate GENERIC matching code for the decision tree operand.  */
+
+unsigned
+dt_operand::gen_generic_expr (FILE *f, const char *opname)
+{
+  expr *e = static_cast<expr *> (op);
+  unsigned n_ops = e->ops.length ();
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      gen_opname (child_opname, i);
+
+      if (e->operation->kind == id_base::CODE)
+	fprintf (f, "tree %s = TREE_OPERAND (%s, %u);\n",
+		 child_opname, opname, i);
+      else
+	fprintf (f, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
+		 child_opname, opname, i);
+    }
+
+  return 0;
+}
+
+/* Generate matching code for the children of the decision tree node.  */
+
+void
+dt_node::gen_kids (FILE *f, bool gimple)
+{
+  auto_vec<dt_operand *> gimple_exprs;
+  auto_vec<dt_operand *> generic_exprs;
+  auto_vec<dt_operand *> fns;
+  auto_vec<dt_operand *> generic_fns;
+  auto_vec<dt_operand *> preds;
+  auto_vec<dt_node *> others;
+  dt_node *true_operand = NULL;
+
+  for (unsigned i = 0; i < kids.length (); ++i)
+    {
+      if (kids[i]->type == dt_node::DT_OPERAND)
+	{
+	  dt_operand *op = as_a<dt_operand *> (kids[i]);
+	  if (expr *e = dyn_cast <expr *> (op->op))
+	    {
+	      if (e->ops.length () == 0)
+		generic_exprs.safe_push (op);
+	      else if (e->operation->kind == id_base::FN)
+		{
+		  if (gimple)
+		    fns.safe_push (op);
+		  else
+		    generic_fns.safe_push (op);
+		}
+	      else if (e->operation->kind == id_base::PREDICATE)
+		preds.safe_push (op);
+	      else
+		{
+		  if (gimple)
+		    gimple_exprs.safe_push (op);
+		  else
+		    generic_exprs.safe_push (op);
+		}
+	    }
+	  else if (op->op->type == operand::OP_PREDICATE)
+	    others.safe_push (kids[i]);
+	  else
+	    gcc_unreachable ();
+	}
+      else if (kids[i]->type == dt_node::DT_MATCH
+	       || kids[i]->type == dt_node::DT_SIMPLIFY)
+	others.safe_push (kids[i]);
+      else if (kids[i]->type == dt_node::DT_TRUE)
+	true_operand = kids[i];
+      else
+	gcc_unreachable ();
+    }
+
+  char buf[128];
+  char *kid_opname = buf;
+
+  unsigned exprs_len = gimple_exprs.length ();
+  unsigned gexprs_len = generic_exprs.length ();
+  unsigned fns_len = fns.length ();
+  unsigned gfns_len = generic_fns.length ();
+
+  if (exprs_len || fns_len || gexprs_len || gfns_len)
+    {
+      if (exprs_len)
+	gimple_exprs[0]->get_name (kid_opname);
+      else if (fns_len)
+	fns[0]->get_name (kid_opname);
+      else if (gfns_len)
+	generic_fns[0]->get_name (kid_opname);
+      else
+	generic_exprs[0]->get_name (kid_opname);
+
+      fprintf (f, "switch (TREE_CODE (%s))\n"
+	       "{\n", kid_opname);
+    }
+
+  if (exprs_len || fns_len)
+    {
+      fprintf (f, "case SSA_NAME:\n");
+      fprintf (f, "{\n");
+      fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname);
+
+      if (exprs_len)
+	{
+	  fprintf (f, "if (is_gimple_assign (def_stmt))\n");
+	  fprintf (f, "switch (gimple_assign_rhs_code (def_stmt))\n"
+		   "{\n");
+	  for (unsigned i = 0; i < exprs_len; ++i)
+	    {
+	      expr *e = as_a <expr *> (gimple_exprs[i]->op);
+	      id_base *op = e->operation;
+	      if (*op == CONVERT_EXPR || *op == NOP_EXPR)
+		fprintf (f, "CASE_CONVERT:\n");
+	      else
+		fprintf (f, "case %s:\n", op->id);
+	      fprintf (f, "{\n");
+	      gimple_exprs[i]->gen (f, true);
+	      fprintf (f, "break;\n"
+		       "}\n");
+	    }
+	  fprintf (f, "default:;\n"
+		   "}\n");
+	}
+
+      if (fns_len)
+	{
+	  if (exprs_len)
+	    fprintf (f, "else ");
+
+	  fprintf (f, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
+		   "{\n"
+		   "tree fndecl = gimple_call_fndecl (def_stmt);\n"
+		   "switch (DECL_FUNCTION_CODE (fndecl))\n"
+		   "{\n");
+
+	  for (unsigned i = 0; i < fns_len; ++i)
+	    {
+	      expr *e = as_a <expr *>(fns[i]->op);
+	      fprintf (f, "case %s:\n"
+		       "{\n", e->operation->id);
+	      fns[i]->gen (f, true);
+	      fprintf (f, "break;\n"
+		       "}\n");
+	    }
+
+	  fprintf (f, "default:;\n"
+		   "}\n"
+		   "}\n");
+	}
+
+      fprintf (f, "break;\n"
+	       "}\n");
+    }
+
+  for (unsigned i = 0; i < generic_exprs.length (); ++i)
+    {
+      expr *e = as_a <expr *>(generic_exprs[i]->op);
+      id_base *op = e->operation;
+      if (*op == CONVERT_EXPR || *op == NOP_EXPR)
+	fprintf (f, "CASE_CONVERT:\n");
+      else
+	fprintf (f, "case %s:\n", op->id);
+      fprintf (f, "{\n");
+      generic_exprs[i]->gen (f, gimple);
+      fprintf (f, "break;\n"
+	       "}\n");
+    }
+
+  if (gfns_len)
+    {
+      fprintf (f, "case CALL_EXPR:\n"
+	       "{\n"
+	       "tree fndecl = get_callee_fndecl (%s);\n"
+	       "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
+	       "switch (DECL_FUNCTION_CODE (fndecl))\n"
+	       "{\n", kid_opname);
+
+      for (unsigned j = 0; j < generic_fns.length (); ++j)
+	{
+	  expr *e = as_a <expr *>(generic_fns[j]->op);
+	  gcc_assert (e->operation->kind == id_base::FN);
+
+	  fprintf (f, "case %s:\n"
+		   "{\n", e->operation->id);
+	  generic_fns[j]->gen (f, false);
+	  fprintf (f, "break;\n"
+		   "}\n");
+	}
+
+      fprintf (f, "default:;\n"
+	       "}\n"
+	       "break;\n"
+	       "}\n");
+    }
+
+  /* Close switch (TREE_CODE ()).  */
+  if (exprs_len || fns_len || gexprs_len || gfns_len)
+    fprintf (f, "default:;\n"
+	     "}\n");
+
+  for (unsigned i = 0; i < preds.length (); ++i)
+    {
+      expr *e = as_a <expr *> (preds[i]->op);
+      predicate_id *p = as_a <predicate_id *> (e->operation);
+      preds[i]->get_name (kid_opname);
+      fprintf (f, "tree %s_pops[%d];\n", kid_opname, p->nargs);
+      fprintf (f, "if (%s_%s (%s, %s_pops%s))\n",
+	       gimple ? "gimple" : "tree",
+	       p->id, kid_opname, kid_opname,
+	       gimple ? ", valueize" : "");
+      fprintf (f, "{\n");
+      for (int j = 0; j < p->nargs; ++j)
+	{
+	  char child_opname[20];
+	  preds[i]->gen_opname (child_opname, j);
+	  fprintf (f, "tree %s = %s_pops[%d];\n", child_opname, kid_opname, j);
+	}
+      preds[i]->gen_kids (f, gimple);
+      fprintf (f, "}\n");
+    }
+
+  for (unsigned i = 0; i < others.length (); ++i)
+    others[i]->gen (f, gimple);
+
+  if (true_operand)
+    true_operand->gen (f, gimple);
+}
+
+/* Generate matching code for the decision tree operand.  */
+
+void
+dt_operand::gen (FILE *f, bool gimple)
+{
+  char opname[20];
+  get_name (opname);
+
+  unsigned n_braces = 0;
+
+  if (type == DT_OPERAND)
+    switch (op->type)
+      {
+	case operand::OP_PREDICATE:
+	  n_braces = gen_predicate (f, opname, gimple);
+	  break;
+
+	case operand::OP_EXPR:
+	  if (gimple)
+	    n_braces = gen_gimple_expr (f);
+	  else
+	    n_braces = gen_generic_expr (f, opname);
+	  break;
+
+	default:
+	  gcc_unreachable ();
+      }
+  else if (type == DT_TRUE)
+    ;
+  else if (type == DT_MATCH)
+    n_braces = gen_match_op (f, opname);
+  else
+    gcc_unreachable ();
+
+  gen_kids (f, gimple);
+
+  for (unsigned i = 0; i < n_braces; ++i)
+    fprintf (f, "}\n");
+}
+
+/* Generate code for the '(if ...)', '(with ..)' and actual transform
+   step of a '(simplify ...)' or '(match ...)'.  This handles everything
+   that is not part of the decision tree (simplify->match).  */
+
+void
+dt_simplify::gen (FILE *f, bool gimple)
+{
+  fprintf (f, "{\n");
+  output_line_directive (f, s->result_location);
+  if (s->capture_max >= 0)
+    fprintf (f, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
+	     s->capture_max + 1);
+
+  for (int i = 0; i <= s->capture_max; ++i)
+    if (indexes[i])
+      {
+	char opname[20];
+	fprintf (f, "captures[%u] = %s;\n", i, indexes[i]->get_name (opname));
+      }
+
+  unsigned n_braces = 0;
+  if (s->ifexpr_vec != vNULL)
+    {
+      for (unsigned i = 0; i < s->ifexpr_vec.length (); ++i)
+	{
+	  if_or_with &w = s->ifexpr_vec[i];
+	  if (w.is_with)
+	    {
+	      fprintf (f, "{\n");
+	      output_line_directive (f, w.location);
+	      w.cexpr->gen_transform (f, NULL, true, 1, "type");
+	      n_braces++;
+	    }
+	  else
+	    {
+	      output_line_directive (f, w.location);
+	      fprintf (f, "if (");
+	      if (i == s->ifexpr_vec.length () - 1
+		  || s->ifexpr_vec[i+1].is_with)
+		w.cexpr->gen_transform (f, NULL, true, 1, "type");
+	      else
+		{
+		  unsigned j = i;
+		  do
+		    {
+		      if (j != i)
+			{
+			  fprintf (f, "\n");
+			  output_line_directive (f, s->ifexpr_vec[j].location);
+			  fprintf (f, "&& ");
+			}
+		      fprintf (f, "(");
+		      s->ifexpr_vec[j].cexpr->gen_transform (f, NULL,
+							     true, 1, "type");
+		      fprintf (f, ")");
+		      ++j;
+		    }
+		  while (j < s->ifexpr_vec.length ()
+			 && !s->ifexpr_vec[j].is_with);
+		  i = j - 1;
+		}
+	      fprintf (f, ")\n");
+	    }
+	}
+      fprintf (f, "{\n");
+      n_braces++;
+    }
+
+  fprintf (f, "if (dump_file && (dump_flags & TDF_DETAILS)) "
+	   "fprintf (dump_file, \"Applying pattern ");
+  output_line_directive (f, s->result_location, true);
+  fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
+
+  if (!s->result)
+    {
+      /* If there is no result then this is a predicate implementation.  */
+      fprintf (f, "return true;\n");
+    }
+  else if (gimple)
+    {
+      if (s->result->type == operand::OP_EXPR)
+	{
+	  expr *e = as_a <expr *> (s->result);
+	  bool is_predicate = is_a <predicate_id *> (e->operation);
+	  if (!is_predicate)
+	    fprintf (f, "*res_code = %s;\n", e->operation->id);
+	  for (unsigned j = 0; j < e->ops.length (); ++j)
+	    {
+	      char dest[32];
+	      snprintf (dest, 32, "  res_ops[%d]", j);
+	      const char *optype
+		= get_operand_type (e->operation,
+				    "type", e->expr_type,
+				    j == 0
+				    ? NULL : "TREE_TYPE (res_ops[0])");
+	      e->ops[j]->gen_transform (f, dest, true, 1, optype, indexes);
+	    }
+
+	  /* Re-fold the toplevel result.  It's basically an embedded
+	     gimple_build w/o actually building the stmt.  */
+	  if (!is_predicate)
+	    fprintf (f, "gimple_resimplify%d (seq, res_code, type, "
+		     "res_ops, valueize);\n", e->ops.length ());
+	}
+      else if (s->result->type == operand::OP_CAPTURE
+	       || s->result->type == operand::OP_C_EXPR)
+	{
+	  s->result->gen_transform (f, "res_ops[0]", true, 1, "type", indexes);
+	  fprintf (f, "*res_code = TREE_CODE (res_ops[0]);\n");
+	}
+      else
+	gcc_unreachable ();
+      fprintf (f, "return true;\n");
+    }
+  else /* GENERIC */
+    {
+      if (s->result->type == operand::OP_EXPR)
+	{
+	  expr *e = as_a <expr *> (s->result);
+	  bool is_predicate = is_a <predicate_id *> (e->operation);
+	  for (unsigned j = 0; j < e->ops.length (); ++j)
+	    {
+	      char dest[32];
+	      if (is_predicate)
+		snprintf (dest, 32, "res_ops[%d]", j);
+	      else
+		{
+		  fprintf (f, "   tree res_op%d;\n", j);
+		  snprintf (dest, 32, "  res_op%d", j);
+		}
+	      const char *optype
+	        = get_operand_type (e->operation,
+				    "type", e->expr_type,
+				    j == 0
+				    ? NULL : "TREE_TYPE (res_op0)");
+	      e->ops[j]->gen_transform (f, dest, false, 1, optype, indexes);
+	    }
+	  if (is_a <predicate_id *> (e->operation))
+	    fprintf (f, "return true;\n");
+	  else
+	    {
+	      /* Re-fold the toplevel result.  */
+	      if (e->operation->kind == id_base::CODE)
+		fprintf (f, "  return fold_build%d (%s, type",
+			 e->ops.length (), e->operation->id);
+	      else
+		fprintf (f, "  return build_call_expr "
+			 "(builtin_decl_implicit (%s), %d",
+			 e->operation->id, e->ops.length());
+	      for (unsigned j = 0; j < e->ops.length (); ++j)
+		fprintf (f, ", res_op%d", j);
+	      fprintf (f, ");\n");
+	    }
+	}
+      else if (s->result->type == operand::OP_CAPTURE
+	       || s->result->type == operand::OP_C_EXPR)
+	{
+	  fprintf (f, "  tree res;\n");
+	  s->result->gen_transform (f, " res", false, 1, "type", indexes);
+	  fprintf (f, "  return res;\n");
+	}
+      else
+	gcc_unreachable ();
+    }
+
+  for (unsigned i = 0; i < n_braces; ++i)
+    fprintf (f, "}\n");
+
+  fprintf (f, "}\n");
+}
+
+/* Main entry to generate code for matching GIMPLE IL off the decision
+   tree.  */
+
+void
+decision_tree::gen_gimple (FILE *f)
+{
+  for (unsigned n = 1; n <= 3; ++n)
+    {
+      fprintf (f, "\nstatic bool\n"
+	       "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
+	       "                 gimple_seq *seq, tree (*valueize)(tree),\n"
+	       "                 code_helper code, tree type");
+      for (unsigned i = 0; i < n; ++i)
+	fprintf (f, ", tree op%d", i);
+      fprintf (f, ")\n");
+      fprintf (f, "{\n");
+
+      fprintf (f, "switch (code.get_rep())\n"
+	       "{\n");
+      for (unsigned i = 0; i < root->kids.length (); i++)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
+	  expr *e = static_cast<expr *>(dop->op);
+	  if (e->ops.length () != n)
+	    continue;
+
+	  if (*e->operation == CONVERT_EXPR
+	      || *e->operation == NOP_EXPR)
+	    fprintf (f, "CASE_CONVERT:\n");
+	  else
+	    fprintf (f, "case %s%s:\n",
+		     is_a <fn_id *> (e->operation) ? "-" : "",
+		     e->operation->id);
+	  fprintf (f, "{\n");
+	  dop->gen_kids (f, true);
+	  fprintf (f, "break;\n");
+	  fprintf (f, "}\n");
+	}
+      fprintf (f, "default:;\n"
+	       "}\n");
+
+      fprintf (f, "return false;\n");
+      fprintf (f, "}\n");
+    }
+}
+
+/* Main entry to generate code for matching GENERIC IL off the decision
+   tree.  */
+
+void
+decision_tree::gen_generic (FILE *f)
+{
+  for (unsigned n = 1; n <= 3; ++n)
+    {
+      fprintf (f, "\ntree\n"
+	       "generic_simplify (enum tree_code code, "
+	       "tree type ATTRIBUTE_UNUSED");
+      for (unsigned i = 0; i < n; ++i)
+	fprintf (f, ", tree op%d", i);
+      fprintf (f, ")\n");
+      fprintf (f, "{\n");
+
+      /* ???  For now reject all simplifications on operands with
+         side-effects as we are not prepared to properly wrap
+	 omitted parts with omit_one_operand and friends.  In
+	 principle we can do that automagically for a subset of
+	 transforms (and only reject the remaining cases).
+	 This fixes for example gcc.c-torture/execute/20050131-1.c.  */
+      fprintf (f, "if ((op0 && TREE_SIDE_EFFECTS (op0))");
+      for (unsigned i = 1; i < n; ++i)
+	fprintf (f, "|| (op%d && TREE_SIDE_EFFECTS (op%d))", i, i);
+      fprintf (f, ")\n"
+	       "  return NULL_TREE;\n");
+
+      fprintf (f, "switch (code)\n"
+	       "{\n");
+      for (unsigned i = 0; i < root->kids.length (); i++)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
+	  expr *e = static_cast<expr *>(dop->op);
+	  if (e->ops.length () != n
+	      /* Builtin simplifications are somewhat premature on
+	         GENERIC.  The following drops patterns with outermost
+		 calls.  It's easy to emit overloads for function code
+		 though if necessary.  */
+	      || e->operation->kind != id_base::CODE)
+	    continue;
+
+	  operator_id *op_id = static_cast <operator_id *> (e->operation);
+	  if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
+	    fprintf (f, "CASE_CONVERT:\n");
+	  else
+	    fprintf (f, "case %s:\n", e->operation->id);
+	  fprintf (f, "{\n");
+	  dop->gen_kids (f, false);
+	  fprintf (f, "break;\n"
+		   "}\n");
+	}
+      fprintf (f, "default:;\n"
+	       "}\n");
+
+      fprintf (f, "return NULL_TREE;\n");
+      fprintf (f, "}\n");
+    }
+}
+
+/* Output code to implement the predicate P from the decision tree DT.  */
+
+void
+write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
+{
+  fprintf (f, "\nbool\n"
+	   "%s%s (tree t%s%s)\n"
+	   "{\n", gimple ? "gimple_" : "tree_", p->id,
+	   p->nargs > 0 ? ", tree *res_ops" : "",
+	   gimple ? ", tree (*valueize)(tree)" : "");
+  /* Conveniently make 'type' available.  */
+  fprintf (f, "tree type = TREE_TYPE (t);\n");
+
+  if (!gimple)
+    fprintf (f, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
+  dt.root->gen_kids (f, gimple);
+
+  fprintf (f, "return false;\n"
+	   "}\n");
+}
+
+/* Write the common header for the GIMPLE/GENERIC IL matching routines.  */
+
+static void
+write_header (FILE *f, const char *head)
+{
+  fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
+  fprintf (f, "   a IL pattern matching and simplification description.  */\n");
+
+  /* Include the header instead of writing it awkwardly quoted here.  */
+  fprintf (f, "\n#include \"%s\"\n", head);
+}
+
+
+
+/* AST parsing.  */
+
+class parser
+{
+public:
+  parser (cpp_reader *);
+
+private:
+  const cpp_token *next ();
+  const cpp_token *peek ();
+  const cpp_token *peek_ident (const char * = NULL);
+  const cpp_token *expect (enum cpp_ttype);
+  void eat_token (enum cpp_ttype);
+  const char *get_string ();
+  const char *get_ident ();
+  void eat_ident (const char *);
+  const char *get_number ();
+
+  id_base *parse_operation ();
+  operand *parse_capture (operand *);
+  operand *parse_expr ();
+  c_expr *parse_c_expr (cpp_ttype);
+  operand *parse_op ();
+
+  void parse_pattern ();
+  void parse_simplify (source_location, vec<simplify *>&, predicate_id *,
+		       expr *);
+  void parse_for (source_location);
+  void parse_if (source_location);
+  void parse_predicates (source_location);
+
+  cpp_reader *r;
+  vec<if_or_with> active_ifs;
+  vec<vec<user_id *> > active_fors;
+
+  std::map<std::string, unsigned> *capture_ids;
+
+public:
+  vec<simplify *> simplifiers;
+  vec<predicate_id *> user_predicates;
+};
+
+/* Lexing helpers.  */
+
+/* Read the next non-whitespace token from R.  */
+
+const cpp_token *
+parser::next ()
+{
+  const cpp_token *token;
+  do
+    {
+      token = cpp_get_token (r);
+    }
+  while (token->type == CPP_PADDING
+	 && token->type != CPP_EOF);
+  return token;
+}
+
+/* Peek at the next non-whitespace token from R.  */
+
+const cpp_token *
+parser::peek ()
+{
+  const cpp_token *token;
+  unsigned i = 0;
+  do
+    {
+      token = cpp_peek_token (r, i++);
+    }
+  while (token->type == CPP_PADDING
+	 && token->type != CPP_EOF);
+  /* If we peek at EOF this is a fatal error as it leaves the
+     cpp_reader in unusable state.  Assume we really wanted a
+     token and thus this EOF is unexpected.  */
+  if (token->type == CPP_EOF)
+    fatal_at (token, "unexpected end of file");
+  return token;
+}
+
+/* Peek at the next identifier token (or return NULL if the next
+   token is not an identifier or equal to ID if supplied).  */
+
+const cpp_token *
+parser::peek_ident (const char *id)
+{
+  const cpp_token *token = peek ();
+  if (token->type != CPP_NAME)
+    return 0;
+
+  if (id == 0)
+    return token;
+
+  const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
+  if (strcmp (id, t) == 0)
+    return token;
+
+  return 0;
+}
+
+/* Read the next token from R and assert it is of type TK.  */
+
+const cpp_token *
+parser::expect (enum cpp_ttype tk)
+{
+  const cpp_token *token = next ();
+  if (token->type != tk)
+    fatal_at (token, "expected %s, got %s",
+	      cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
+
+  return token;
+}
+
+/* Consume the next token from R and assert it is of type TK.  */
+
+void
+parser::eat_token (enum cpp_ttype tk)
+{
+  expect (tk);
+}
+
+/* Read the next token from R and assert it is of type CPP_STRING and
+   return its value.  */
+
+const char *
+parser::get_string ()
+{
+  const cpp_token *token = expect (CPP_STRING);
+  return (const char *)token->val.str.text;
+}
+
+/* Read the next token from R and assert it is of type CPP_NAME and
+   return its value.  */
+
+const char *
+parser::get_ident ()
+{
+  const cpp_token *token = expect (CPP_NAME);
+  return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
+}
+
+/* Eat an identifier token with value S from R.  */
+
+void
+parser::eat_ident (const char *s)
+{
+  const cpp_token *token = peek ();
+  const char *t = get_ident ();
+  if (strcmp (s, t) != 0)
+    fatal_at (token, "expected '%s' got '%s'\n", s, t);
+}
+
+/* Read the next token from R and assert it is of type CPP_NUMBER and
+   return its value.  */
+
+const char *
+parser::get_number ()
+{
+  const cpp_token *token = expect (CPP_NUMBER);
+  return (const char *)token->val.str.text;
+}
+
+
+/* Parse the operator ID, special-casing convert?, convert1? and
+   convert2?  */
+
+id_base *
+parser::parse_operation ()
+{
+  const cpp_token *id_tok = peek ();
+  const char *id = get_ident ();
+  const cpp_token *token = peek ();
+  if (strcmp (id, "convert0") == 0)
+    fatal_at (id_tok, "use 'convert?' here");
+  if (token->type == CPP_QUERY
+      && !(token->flags & PREV_WHITE))
+    {
+      if (strcmp (id, "convert") == 0)
+	id = "convert0";
+      else if (strcmp  (id, "convert1") == 0)
+	;
+      else if (strcmp  (id, "convert2") == 0)
+	;
+      else
+	fatal_at (id_tok, "non-convert operator conditionalized");
+      eat_token (CPP_QUERY);
+    }
+  else if (strcmp  (id, "convert1") == 0
+	   || strcmp  (id, "convert2") == 0)
+    fatal_at (id_tok, "expected '?' after conditional operator");
+  id_base *op = get_operator (id);
+  if (!op)
+    fatal_at (id_tok, "unknown operator %s", id);
+  return op;
+}
+
+/* Parse a capture.
+     capture = '@'<number>  */
+
+struct operand *
+parser::parse_capture (operand *op)
+{
+  eat_token (CPP_ATSIGN);
+  const cpp_token *token = peek ();
+  const char *id;
+  if (token->type == CPP_NUMBER)
+    id = get_number ();
+  else if (token->type == CPP_NAME)
+    id = get_ident ();
+  else
+    fatal_at (token, "expected number or identifier");
+  unsigned next_id = capture_ids->size ();
+  std::pair<std::map<std::string, unsigned>::iterator, bool> res
+    = capture_ids->insert (std::pair<std::string, unsigned>(id, next_id));
+  return new capture ((*res.first).second, op);
+}
+
+/* Parse an expression
+     expr = '(' <operation>[capture][flag][type] <operand>... ')'  */
+
+struct operand *
+parser::parse_expr ()
+{
+  expr *e = new expr (parse_operation ());
+  const cpp_token *token = peek ();
+  operand *op;
+  bool is_commutative = false;
+  const char *expr_type = NULL;
+
+  if (token->type == CPP_COLON
+      && !(token->flags & PREV_WHITE))
+    {
+      eat_token (CPP_COLON);
+      token = peek ();
+      if (token->type == CPP_NAME
+	  && !(token->flags & PREV_WHITE))
+	{
+	  const char *s = get_ident ();
+	  if (s[0] == 'c' && !s[1])
+	    is_commutative = true;
+	  else if (s[1] != '\0')
+	    expr_type = s;
+	  else
+	    fatal_at (token, "flag %s not recognized", s);
+	  token = peek ();
+	}
+      else
+	fatal_at (token, "expected flag or type specifying identifier");
+    }
+
+  if (token->type == CPP_ATSIGN
+      && !(token->flags & PREV_WHITE))
+    op = parse_capture (e);
+  else
+    op = e;
+  do
+    {
+      const cpp_token *token = peek ();
+      if (token->type == CPP_CLOSE_PAREN)
+	{
+	  if (e->operation->nargs != -1
+	      && e->operation->nargs != (int) e->ops.length ())
+	    fatal_at (token, "'%s' expects %u operands, not %u",
+		      e->operation->id, e->operation->nargs, e->ops.length ());
+	  if (is_commutative)
+	    {
+	      if (e->ops.length () == 2)
+		e->is_commutative = true;
+	      else
+		fatal_at (token, "only binary operators or function with "
+			  "two arguments can be marked commutative");
+	    }
+	  e->expr_type = expr_type;
+	  return op;
+	}
+      e->append_op (parse_op ());
+    }
+  while (1);
+}
+
+/* Lex native C code delimited by START recording the preprocessing tokens
+   for later processing.
+     c_expr = ('{'|'(') <pp token>... ('}'|')')  */
+
+c_expr *
+parser::parse_c_expr (cpp_ttype start)
+{
+  const cpp_token *token;
+  cpp_ttype end;
+  unsigned opencnt;
+  vec<cpp_token> code = vNULL;
+  unsigned nr_stmts = 0;
+  eat_token (start);
+  if (start == CPP_OPEN_PAREN)
+    end = CPP_CLOSE_PAREN;
+  else if (start == CPP_OPEN_BRACE)
+    end = CPP_CLOSE_BRACE;
+  else
+    gcc_unreachable ();
+  opencnt = 1;
+  do
+    {
+      token = next ();
+
+      /* Count brace pairs to find the end of the expr to match.  */
+      if (token->type == start)
+	opencnt++;
+      else if (token->type == end
+	       && --opencnt == 0)
+	break;
+
+      /* This is a lame way of counting the number of statements.  */
+      if (token->type == CPP_SEMICOLON)
+	nr_stmts++;
+
+      /* Record the token.  */
+      code.safe_push (*token);
+    }
+  while (1);
+  return new c_expr (r, code, nr_stmts, vNULL, capture_ids);
+}
+
+/* Parse an operand which is either an expression, a predicate or
+   a standalone capture.
+     op = predicate | expr | c_expr | capture  */
+
+struct operand *
+parser::parse_op ()
+{
+  const cpp_token *token = peek ();
+  struct operand *op = NULL;
+  if (token->type == CPP_OPEN_PAREN)
+    {
+      eat_token (CPP_OPEN_PAREN);
+      op = parse_expr ();
+      eat_token (CPP_CLOSE_PAREN);
+    }
+  else if (token->type == CPP_OPEN_BRACE)
+    {
+      op = parse_c_expr (CPP_OPEN_BRACE);
+    }
+  else
+    {
+      /* Remaining ops are either empty or predicates  */
+      if (token->type == CPP_NAME)
+	{
+	  const char *id = get_ident ();
+	  id_base *opr = get_operator (id);
+	  if (!opr)
+	    fatal_at (token, "expected predicate name");
+	  if (operator_id *code = dyn_cast <operator_id *> (opr))
+	    {
+	      if (code->nargs != 0)
+		fatal_at (token, "using an operator with operands as predicate");
+	      /* Parse the zero-operand operator "predicates" as
+		 expression.  */
+	      op = new expr (opr);
+	    }
+	  else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
+	    op = new predicate (p);
+	  else
+	    fatal_at (token, "using an unsupported operator as predicate");
+	  token = peek ();
+	  if (token->flags & PREV_WHITE)
+	    return op;
+	}
+      else if (token->type != CPP_COLON
+	       && token->type != CPP_ATSIGN)
+	fatal_at (token, "expected expression or predicate");
+      /* optionally followed by a capture and a predicate.  */
+      if (token->type == CPP_COLON)
+	fatal_at (token, "not implemented: predicate on leaf operand");
+      if (token->type == CPP_ATSIGN)
+	op = parse_capture (op);
+    }
+
+  return op;
+}
+
+/* Parse
+     simplify = 'simplify' <expr> <result-op>
+   or
+     match = 'match' <ident> <expr> [<result-op>]
+   with
+     <result-op> = <op> | <if> | <with>
+     <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
+     <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
+   and fill SIMPLIFIERS with the results.  */
+
+void
+parser::parse_simplify (source_location match_location,
+			vec<simplify *>& simplifiers, predicate_id *matcher,
+			expr *result)
+{
+  /* Reset the capture map.  */
+  capture_ids = new std::map<std::string, unsigned>;
+
+  const cpp_token *loc = peek ();
+  struct operand *match = parse_op ();
+  if (match->type == operand::OP_CAPTURE && !matcher)
+    fatal_at (loc, "outermost expression cannot be captured");
+  if (match->type == operand::OP_EXPR
+      && is_a <predicate_id *> (as_a <expr *> (match)->operation))
+    fatal_at (loc, "outermost expression cannot be a predicate");
+
+  const cpp_token *token = peek ();
+
+  /* If this if is immediately closed then it is part of a predicate
+     definition.  Push it.  */
+  if (token->type == CPP_CLOSE_PAREN)
+    {
+      if (!matcher)
+	fatal_at (token, "expected transform expression");
+      simplifiers.safe_push
+	(new simplify (match, match_location, result, token->src_loc,
+		       active_ifs.copy (), active_fors.copy (),
+		       capture_ids));
+      return;
+    }
+
+  unsigned active_ifs_len = active_ifs.length ();
+  while (1)
+    {
+      if (token->type == CPP_OPEN_PAREN)
+	{
+	  source_location paren_loc = token->src_loc;
+	  eat_token (CPP_OPEN_PAREN);
+	  if (peek_ident ("if"))
+	    {
+	      eat_ident ("if");
+	      active_ifs.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN),
+						token->src_loc, false));
+	      /* If this if is immediately closed then it contains a
+	         manual matcher or is part of a predicate definition.
+		 Push it.  */
+	      if (peek ()->type == CPP_CLOSE_PAREN)
+		{
+		  if (!matcher)
+		    fatal_at (token, "manual transform not implemented");
+		  simplifiers.safe_push
+		      (new simplify (match, match_location, result,
+				     paren_loc, active_ifs.copy (),
+				     active_fors.copy (), capture_ids));
+		}
+	    }
+	  else if (peek_ident ("with"))
+	    {
+	      eat_ident ("with");
+	      /* Parse (with c-expr expr) as (if-with (true) expr).  */
+	      c_expr *e = parse_c_expr (CPP_OPEN_BRACE);
+	      e->nr_stmts = 0;
+	      active_ifs.safe_push (if_or_with (e, token->src_loc, true));
+	    }
+	  else
+	    {
+	      operand *op = result;
+	      if (!matcher)
+		op = parse_expr ();
+	      simplifiers.safe_push
+		  (new simplify (match, match_location, op,
+				 token->src_loc, active_ifs.copy (),
+				 active_fors.copy (), capture_ids));
+	      eat_token (CPP_CLOSE_PAREN);
+	      /* A "default" result closes the enclosing scope.  */
+	      if (active_ifs.length () > active_ifs_len)
+		{
+		  eat_token (CPP_CLOSE_PAREN);
+		  active_ifs.pop ();
+		}
+	      else
+		return;
+	    }
+	}
+      else if (token->type == CPP_CLOSE_PAREN)
+	{
+	  /* Close a scope if requested.  */
+	  if (active_ifs.length () > active_ifs_len)
+	    {
+	      eat_token (CPP_CLOSE_PAREN);
+	      active_ifs.pop ();
+	      token = peek ();
+	    }
+	  else
+	    return;
+	}
+      else
+	{
+	  if (matcher)
+	    fatal_at (token, "expected match operand expression");
+	  simplifiers.safe_push
+	      (new simplify (match, match_location,
+			     matcher ? result : parse_op (),
+			     token->src_loc, active_ifs.copy (),
+			     active_fors.copy (), capture_ids));
+	  /* A "default" result closes the enclosing scope.  */
+	  if (active_ifs.length () > active_ifs_len)
+	    {
+	      eat_token (CPP_CLOSE_PAREN);
+	      active_ifs.pop ();
+	    }
+	  else
+	    return;
+	}
+      token = peek ();
+    }
+}
+
+/* Parsing of the outer control structures.  */
+
+/* Parse a for expression
+     for = '(' 'for' <subst>... <pattern> ')'
+     subst = <ident> '(' <ident>... ')'  */
+
+void
+parser::parse_for (source_location)
+{
+  vec<user_id *> user_ids = vNULL;
+  const cpp_token *token;
+  unsigned min_n_opers = 0, max_n_opers = 0;
+
+  while (1)
+    {
+      token = peek_ident ();
+      if (token == 0)
+	break;
+
+      /* Insert the user defined operators into the operator hash.  */
+      const char *id = get_ident ();
+      user_id *op = new user_id (id);
+      id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
+      if (*slot)
+	fatal_at (token, "operator already defined");
+      *slot = op;
+      user_ids.safe_push (op);
+
+      eat_token (CPP_OPEN_PAREN);
+
+      int arity = -1;
+      while ((token = peek_ident ()) != 0)
+	{
+	  const char *oper = get_ident ();
+	  id_base *idb = get_operator (oper);
+	  if (idb == NULL)
+	    fatal_at (token, "no such operator '%s'", oper);
+	  if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2)
+	    fatal_at (token, "conditional operators cannot be used inside for");
+
+	  if (arity == -1)
+	    arity = idb->nargs;
+	  else if (idb->nargs == -1)
+	    ;
+	  else if (idb->nargs != arity)
+	    fatal_at (token, "operator '%s' with arity %d does not match "
+		      "others with arity %d", oper, idb->nargs, arity);
+
+	  op->substitutes.safe_push (idb);
+	}
+      op->nargs = arity;
+      token = expect (CPP_CLOSE_PAREN);
+
+      unsigned nsubstitutes = op->substitutes.length ();
+      if (nsubstitutes == 0)
+	fatal_at (token, "A user-defined operator must have at least "
+		  "one substitution");
+      if (max_n_opers == 0)
+	{
+	  min_n_opers = nsubstitutes;
+	  max_n_opers = nsubstitutes;
+	}
+      else
+	{
+	  if (nsubstitutes % min_n_opers != 0
+	      && min_n_opers % nsubstitutes != 0)
+	    fatal_at (token, "All user-defined identifiers must have a "
+		      "multiple number of operator substitutions of the "
+		      "smallest number of substitutions");
+	  if (nsubstitutes < min_n_opers)
+	    min_n_opers = nsubstitutes;
+	  else if (nsubstitutes > max_n_opers)
+	    max_n_opers = nsubstitutes;
+	}
+    }
+
+  unsigned n_ids = user_ids.length ();
+  if (n_ids == 0)
+    fatal_at (token, "for requires at least one user-defined identifier");
+
+  token = peek ();
+  if (token->type == CPP_CLOSE_PAREN)
+    fatal_at (token, "no pattern defined in for");
+
+  active_fors.safe_push (user_ids);
+  while (1)
+    {
+      token = peek ();
+      if (token->type == CPP_CLOSE_PAREN)
+ 	break;
+      parse_pattern ();
+    }
+  active_fors.pop ();
+
+  /* Remove user-defined operators from the hash again.  */
+  for (unsigned i = 0; i < user_ids.length (); ++i)
+    operators->remove_elt (user_ids[i]);
+}
+
+/* Parse an outer if expression.
+     if = '(' 'if' '(' <c-expr> ')' <pattern> ')'  */
+
+void
+parser::parse_if (source_location loc)
+{
+  operand *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
+
+  const cpp_token *token = peek ();
+  if (token->type == CPP_CLOSE_PAREN)
+    fatal_at (token, "no pattern defined in if");
+
+  active_ifs.safe_push (if_or_with (ifexpr, loc, false));
+  while (1)
+    {
+      const cpp_token *token = peek ();
+      if (token->type == CPP_CLOSE_PAREN)
+	break;
+
+      parse_pattern ();
+    }
+  active_ifs.pop ();
+}
+
+/* Parse a list of predefined predicate identifiers.
+     preds = '(' 'define_predicates' <ident>... ')'  */
+
+void
+parser::parse_predicates (source_location)
+{
+  do
+    {
+      const cpp_token *token = peek ();
+      if (token->type != CPP_NAME)
+	break;
+
+      add_predicate (get_ident ());
+    }
+  while (1);
+}
+
+/* Parse outer control structures.
+     pattern = <preds>|<for>|<if>|<simplify>|<match>  */
+
+void
+parser::parse_pattern ()
+{
+  /* All clauses start with '('.  */
+  eat_token (CPP_OPEN_PAREN);
+  const cpp_token *token = peek ();
+  const char *id = get_ident ();
+  if (strcmp (id, "simplify") == 0)
+    parse_simplify (token->src_loc, simplifiers, NULL, NULL);
+  else if (strcmp (id, "match") == 0)
+    {
+      bool with_args = false;
+      if (peek ()->type == CPP_OPEN_PAREN)
+	{
+	  eat_token (CPP_OPEN_PAREN);
+	  with_args = true;
+	}
+      const char *name = get_ident ();
+      id_base *id = get_operator (name);
+      predicate_id *p;
+      if (!id)
+	{
+	  p = add_predicate (name);
+	  user_predicates.safe_push (p);
+	}
+      else if ((p = dyn_cast <predicate_id *> (id)))
+	;
+      else
+	fatal_at (token, "cannot add a match to a non-predicate ID");
+      /* Parse (match <id> <arg>... (match-expr)) here.  */
+      expr *e = NULL;
+      if (with_args)
+	{
+	  e = new expr (p);
+	  while (peek ()->type == CPP_ATSIGN)
+	    e->append_op (parse_capture (NULL));
+	  eat_token (CPP_CLOSE_PAREN);
+	}
+      if (p->nargs != -1
+	  && ((e && e->ops.length () != (unsigned)p->nargs)
+	      || (!e && p->nargs != 0)))
+	fatal_at (token, "non-matching number of match operands");
+      p->nargs = e ? e->ops.length () : 0;
+      parse_simplify (token->src_loc, p->matchers, p, e);
+    }
+  else if (strcmp (id, "for") == 0)
+    parse_for (token->src_loc);
+  else if (strcmp (id, "if") == 0)
+    parse_if (token->src_loc);
+  else if (strcmp (id, "define_predicates") == 0)
+    {
+      if (active_ifs.length () > 0
+	  || active_fors.length () > 0)
+	fatal_at (token, "define_predicates inside if or for is not supported");
+      parse_predicates (token->src_loc);
+    }
+  else
+    fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
+	      active_ifs.length () == 0 && active_fors.length () == 0
+	      ? "'define_predicates', " : "");
+
+  eat_token (CPP_CLOSE_PAREN);
+}
+
+/* Main entry of the parser.  Repeatedly parse outer control structures.  */
+
+parser::parser (cpp_reader *r_)
+{
+  r = r_;
+  active_ifs = vNULL;
+  active_fors = vNULL;
+  simplifiers = vNULL;
+  user_predicates = vNULL;
+
+  const cpp_token *token = next ();
+  while (token->type != CPP_EOF)
+    {
+      _cpp_backup_tokens (r, 1);
+      parse_pattern ();
+      token = next ();
+    }
+}
+
+
+/* Helper for the linemap code.  */
+
+static size_t
+round_alloc_size (size_t s)
+{
+  return s;
+}
+
+
+/* The genmatch generator progam.  It reads from a pattern description
+   and outputs GIMPLE or GENERIC IL matching and simplification routines.  */
+
+int
+main (int argc, char **argv)
+{
+  cpp_reader *r;
+
+  progname = "genmatch";
+
+  if (argc < 2)
+    return 1;
+
+  bool gimple = true;
+  bool verbose = false;
+  char *input = argv[argc-1];
+  for (int i = 1; i < argc - 1; ++i)
+    {
+      if (strcmp (argv[i], "--gimple") == 0)
+	gimple = true;
+      else if (strcmp (argv[i], "--generic") == 0)
+	gimple = false;
+      else if (strcmp (argv[i], "-v") == 0)
+	verbose = true;
+      else
+	{
+	  fprintf (stderr, "Usage: genmatch "
+		   "[--gimple] [--generic] [-v] input\n");
+	  return 1;
+	}
+    }
+
+  line_table = XCNEW (struct line_maps);
+  linemap_init (line_table, 0);
+  line_table->reallocator = xrealloc;
+  line_table->round_alloc_size = round_alloc_size;
+
+  r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
+  cpp_callbacks *cb = cpp_get_callbacks (r);
+  cb->error = error_cb;
+
+  if (!cpp_read_main_file (r, input))
+    return 1;
+  cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
+  cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
+
+  /* Pre-seed operators.  */
+  operators = new hash_table<id_base> (1024);
+#define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
+  add_operator (SYM, # SYM, # TYPE, NARGS);
+#define END_OF_BASE_TREE_CODES
+#include "tree.def"
+add_operator (CONVERT0, "CONVERT0", "tcc_unary", 1);
+add_operator (CONVERT1, "CONVERT1", "tcc_unary", 1);
+add_operator (CONVERT2, "CONVERT2", "tcc_unary", 1);
+#undef END_OF_BASE_TREE_CODES
+#undef DEFTREECODE
+
+  /* Pre-seed builtin functions.
+     ???  Cannot use N (name) as that is targetm.emultls.get_address
+     for BUILT_IN_EMUTLS_GET_ADDRESS ... */
+#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
+  add_builtin (ENUM, # ENUM);
+#include "builtins.def"
+#undef DEF_BUILTIN
+
+  /* Parse ahead!  */
+  parser p (r);
+
+  if (gimple)
+    write_header (stdout, "gimple-match-head.c");
+  else
+    write_header (stdout, "generic-match-head.c");
+
+  /* Go over all predicates defined with patterns and perform
+     lowering and code generation.  */
+  for (unsigned i = 0; i < p.user_predicates.length (); ++i)
+    {
+      predicate_id *pred = p.user_predicates[i];
+      lower (pred->matchers);
+
+      if (verbose)
+	for (unsigned i = 0; i < pred->matchers.length (); ++i)
+	  print_matches (pred->matchers[i]);
+
+      decision_tree dt;
+      for (unsigned i = 0; i < pred->matchers.length (); ++i)
+	dt.insert (pred->matchers[i], i);
+
+      if (verbose)
+	dt.print (stderr);
+
+      write_predicate (stdout, pred, dt, gimple);
+    }
+
+  /* Lower the main simplifiers and generate code for them.  */
+  lower (p.simplifiers);
+
+  if (verbose)
+    for (unsigned i = 0; i < p.simplifiers.length (); ++i)
+      print_matches (p.simplifiers[i]);
+
+  decision_tree dt;
+  for (unsigned i = 0; i < p.simplifiers.length (); ++i)
+    dt.insert (p.simplifiers[i], i);
+
+  if (verbose)
+    dt.print (stderr);
+
+  if (gimple)
+    dt.gen_gimple (stdout);
+  else
+    dt.gen_generic (stdout);
+
+  /* Finalize.  */
+  cpp_finish (r, NULL);
+  cpp_destroy (r);
+
+  delete operators;
+
+  return 0;
+}
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index 9344e0b9dea..5b47cbc37bb 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -5364,19 +5364,202 @@ rewrite_to_defined_overflow (gimple stmt)
   return stmts;
 }
 
-/* Return OP converted to TYPE by emitting a conversion statement on SEQ
-   if required using location LOC.  Note that OP will be returned
-   unmodified if GIMPLE does not require an explicit conversion between
-   its type and TYPE.  */
+
+/* Build the expression CODE OP0 of type TYPE with location LOC,
+   simplifying it first if possible using VALUEIZE if not NULL.
+   OP0 is expected to be valueized already.  Returns the built
+   expression value and appends statements possibly defining it
+   to SEQ.  */
+
+tree
+gimple_build (gimple_seq *seq, location_t loc,
+	      enum tree_code code, tree type, tree op0,
+	      tree (*valueize)(tree))
+{
+  tree res = gimple_simplify (code, type, op0, seq, valueize);
+  if (!res)
+    {
+      if (gimple_in_ssa_p (cfun))
+	res = make_ssa_name (type, NULL);
+      else
+	res = create_tmp_reg (type, NULL);
+      gimple stmt;
+      if (code == REALPART_EXPR
+	  || code == IMAGPART_EXPR
+	  || code == VIEW_CONVERT_EXPR)
+	stmt = gimple_build_assign_with_ops (code, res,
+					     build1 (code, type,
+						     op0), NULL_TREE);
+      else
+	stmt = gimple_build_assign_with_ops (code, res, op0, NULL_TREE);
+      gimple_set_location (stmt, loc);
+      gimple_seq_add_stmt_without_update (seq, stmt);
+    }
+  return res;
+}
+
+/* Build the expression OP0 CODE OP1 of type TYPE with location LOC,
+   simplifying it first if possible using VALUEIZE if not NULL.
+   OP0 and OP1 are expected to be valueized already.  Returns the built
+   expression value and appends statements possibly defining it
+   to SEQ.  */
+
+tree
+gimple_build (gimple_seq *seq, location_t loc,
+	      enum tree_code code, tree type, tree op0, tree op1,
+	      tree (*valueize)(tree))
+{
+  tree res = gimple_simplify (code, type, op0, op1, seq, valueize);
+  if (!res)
+    {
+      if (gimple_in_ssa_p (cfun))
+	res = make_ssa_name (type, NULL);
+      else
+	res = create_tmp_reg (type, NULL);
+      gimple stmt = gimple_build_assign_with_ops (code, res, op0, op1);
+      gimple_set_location (stmt, loc);
+      gimple_seq_add_stmt_without_update (seq, stmt);
+    }
+  return res;
+}
+
+/* Build the expression (CODE OP0 OP1 OP2) of type TYPE with location LOC,
+   simplifying it first if possible using VALUEIZE if not NULL.
+   OP0, OP1 and OP2 are expected to be valueized already.  Returns the built
+   expression value and appends statements possibly defining it
+   to SEQ.  */
+
+tree
+gimple_build (gimple_seq *seq, location_t loc,
+	      enum tree_code code, tree type, tree op0, tree op1, tree op2,
+	      tree (*valueize)(tree))
+{
+  tree res = gimple_simplify (code, type, op0, op1, op2,
+			      seq, valueize);
+  if (!res)
+    {
+      if (gimple_in_ssa_p (cfun))
+	res = make_ssa_name (type, NULL);
+      else
+	res = create_tmp_reg (type, NULL);
+      gimple stmt;
+      if (code == BIT_FIELD_REF)
+	stmt = gimple_build_assign_with_ops (code, res,
+					     build3 (BIT_FIELD_REF, type,
+						     op0, op1, op2),
+					     NULL_TREE);
+      else
+	stmt = gimple_build_assign_with_ops (code, res, op0, op1, op2);
+      gimple_set_location (stmt, loc);
+      gimple_seq_add_stmt_without_update (seq, stmt);
+    }
+  return res;
+}
+
+/* Build the call FN (ARG0) with a result of type TYPE
+   (or no result if TYPE is void) with location LOC,
+   simplifying it first if possible using VALUEIZE if not NULL.
+   ARG0 is expected to be valueized already.  Returns the built
+   expression value (or NULL_TREE if TYPE is void) and appends
+   statements possibly defining it to SEQ.  */
+
+tree
+gimple_build (gimple_seq *seq, location_t loc,
+	      enum built_in_function fn, tree type, tree arg0,
+	      tree (*valueize)(tree))
+{
+  tree res = gimple_simplify (fn, type, arg0, seq, valueize);
+  if (!res)
+    {
+      tree decl = builtin_decl_implicit (fn);
+      gimple stmt = gimple_build_call (decl, 1, arg0);
+      if (!VOID_TYPE_P (type))
+	{
+	  if (gimple_in_ssa_p (cfun))
+	    res = make_ssa_name (type, NULL);
+	  else
+	    res = create_tmp_reg (type, NULL);
+	  gimple_call_set_lhs (stmt, res);
+	}
+      gimple_set_location (stmt, loc);
+      gimple_seq_add_stmt_without_update (seq, stmt);
+    }
+  return res;
+}
+
+/* Build the call FN (ARG0, ARG1) with a result of type TYPE
+   (or no result if TYPE is void) with location LOC,
+   simplifying it first if possible using VALUEIZE if not NULL.
+   ARG0 is expected to be valueized already.  Returns the built
+   expression value (or NULL_TREE if TYPE is void) and appends
+   statements possibly defining it to SEQ.  */
+
+tree
+gimple_build (gimple_seq *seq, location_t loc,
+	      enum built_in_function fn, tree type, tree arg0, tree arg1,
+	      tree (*valueize)(tree))
+{
+  tree res = gimple_simplify (fn, type, arg0, arg1, seq, valueize);
+  if (!res)
+    {
+      tree decl = builtin_decl_implicit (fn);
+      gimple stmt = gimple_build_call (decl, 2, arg0, arg1);
+      if (!VOID_TYPE_P (type))
+	{
+	  if (gimple_in_ssa_p (cfun))
+	    res = make_ssa_name (type, NULL);
+	  else
+	    res = create_tmp_reg (type, NULL);
+	  gimple_call_set_lhs (stmt, res);
+	}
+      gimple_set_location (stmt, loc);
+      gimple_seq_add_stmt_without_update (seq, stmt);
+    }
+  return res;
+}
+
+/* Build the call FN (ARG0, ARG1, ARG2) with a result of type TYPE
+   (or no result if TYPE is void) with location LOC,
+   simplifying it first if possible using VALUEIZE if not NULL.
+   ARG0 is expected to be valueized already.  Returns the built
+   expression value (or NULL_TREE if TYPE is void) and appends
+   statements possibly defining it to SEQ.  */
+
+tree
+gimple_build (gimple_seq *seq, location_t loc,
+	      enum built_in_function fn, tree type,
+	      tree arg0, tree arg1, tree arg2,
+	      tree (*valueize)(tree))
+{
+  tree res = gimple_simplify (fn, type, arg0, arg1, arg2, seq, valueize);
+  if (!res)
+    {
+      tree decl = builtin_decl_implicit (fn);
+      gimple stmt = gimple_build_call (decl, 3, arg0, arg1, arg2);
+      if (!VOID_TYPE_P (type))
+	{
+	  if (gimple_in_ssa_p (cfun))
+	    res = make_ssa_name (type, NULL);
+	  else
+	    res = create_tmp_reg (type, NULL);
+	  gimple_call_set_lhs (stmt, res);
+	}
+      gimple_set_location (stmt, loc);
+      gimple_seq_add_stmt_without_update (seq, stmt);
+    }
+  return res;
+}
+
+/* Build the conversion (TYPE) OP with a result of type TYPE
+   with location LOC if such conversion is neccesary in GIMPLE,
+   simplifying it first.
+   Returns the built expression value and appends
+   statements possibly defining it to SEQ.  */
 
 tree
 gimple_convert (gimple_seq *seq, location_t loc, tree type, tree op)
 {
   if (useless_type_conversion_p (type, TREE_TYPE (op)))
     return op;
-  op = fold_convert_loc (loc, type, op);
-  gimple_seq stmts = NULL;
-  op = force_gimple_operand (op, &stmts, true, NULL_TREE);
-  gimple_seq_add_seq_without_update (seq, stmts);
-  return op;
+  return gimple_build (seq, loc, NOP_EXPR, type, op);
 }
diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
index b55a3ef8b3e..93814cad0f1 100644
--- a/gcc/gimple-fold.h
+++ b/gcc/gimple-fold.h
@@ -45,6 +45,65 @@ extern tree gimple_fold_indirect_ref (tree);
 extern bool arith_code_with_undefined_signed_overflow (tree_code);
 extern gimple_seq rewrite_to_defined_overflow (gimple);
 
+/* gimple_build, functionally matching fold_buildN, outputs stmts
+   int the provided sequence, matching and simplifying them on-the-fly.
+   Supposed to replace force_gimple_operand (fold_buildN (...), ...).  */
+extern tree gimple_build (gimple_seq *, location_t,
+			  enum tree_code, tree, tree,
+			  tree (*valueize) (tree) = NULL);
+inline tree
+gimple_build (gimple_seq *seq,
+	      enum tree_code code, tree type, tree op0)
+{
+  return gimple_build (seq, UNKNOWN_LOCATION, code, type, op0);
+}
+extern tree gimple_build (gimple_seq *, location_t,
+			  enum tree_code, tree, tree, tree,
+			  tree (*valueize) (tree) = NULL);
+inline tree
+gimple_build (gimple_seq *seq,
+	      enum tree_code code, tree type, tree op0, tree op1)
+{
+  return gimple_build (seq, UNKNOWN_LOCATION, code, type, op0, op1);
+}
+extern tree gimple_build (gimple_seq *, location_t,
+			  enum tree_code, tree, tree, tree, tree,
+			  tree (*valueize) (tree) = NULL);
+inline tree
+gimple_build (gimple_seq *seq,
+	      enum tree_code code, tree type, tree op0, tree op1, tree op2)
+{
+  return gimple_build (seq, UNKNOWN_LOCATION, code, type, op0, op1, op2);
+}
+extern tree gimple_build (gimple_seq *, location_t,
+			  enum built_in_function, tree, tree,
+			  tree (*valueize) (tree) = NULL);
+inline tree
+gimple_build (gimple_seq *seq,
+	      enum built_in_function fn, tree type, tree arg0)
+{
+  return gimple_build (seq, UNKNOWN_LOCATION, fn, type, arg0);
+}
+extern tree gimple_build (gimple_seq *, location_t,
+			  enum built_in_function, tree, tree, tree,
+			  tree (*valueize) (tree) = NULL);
+inline tree
+gimple_build (gimple_seq *seq,
+	      enum built_in_function fn, tree type, tree arg0, tree arg1)
+{
+  return gimple_build (seq, UNKNOWN_LOCATION, fn, type, arg0, arg1);
+}
+extern tree gimple_build (gimple_seq *, location_t,
+			  enum built_in_function, tree, tree, tree, tree,
+			  tree (*valueize) (tree) = NULL);
+inline tree
+gimple_build (gimple_seq *seq,
+	      enum built_in_function fn, tree type,
+	      tree arg0, tree arg1, tree arg2)
+{
+  return gimple_build (seq, UNKNOWN_LOCATION, fn, type, arg0, arg1, arg2);
+}
+
 extern tree gimple_convert (gimple_seq *, location_t, tree, tree);
 inline tree
 gimple_convert (gimple_seq *seq, tree type, tree op)
@@ -52,4 +111,18 @@ gimple_convert (gimple_seq *seq, tree type, tree op)
   return gimple_convert (seq, UNKNOWN_LOCATION, type, op);
 }
 
+/* In gimple-match.c.  */
+extern tree gimple_simplify (enum tree_code, tree, tree,
+			     gimple_seq *, tree (*)(tree));
+extern tree gimple_simplify (enum tree_code, tree, tree, tree,
+			     gimple_seq *, tree (*)(tree));
+extern tree gimple_simplify (enum tree_code, tree, tree, tree, tree,
+			     gimple_seq *, tree (*)(tree));
+extern tree gimple_simplify (enum built_in_function, tree, tree,
+			     gimple_seq *, tree (*)(tree));
+extern tree gimple_simplify (enum built_in_function, tree, tree, tree,
+			     gimple_seq *, tree (*)(tree));
+extern tree gimple_simplify (enum built_in_function, tree, tree, tree, tree,
+			     gimple_seq *, tree (*)(tree));
+
 #endif  /* GCC_GIMPLE_FOLD_H */
diff --git a/gcc/gimple-match-head.c b/gcc/gimple-match-head.c
new file mode 100644
index 00000000000..0558e9a892e
--- /dev/null
+++ b/gcc/gimple-match-head.c
@@ -0,0 +1,838 @@
+/* Preamble and helpers for the autogenerated gimple-match.c file.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "stringpool.h"
+#include "stor-layout.h"
+#include "flags.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-ssa.h"
+#include "tree-ssanames.h"
+#include "gimple-fold.h"
+#include "gimple-iterator.h"
+#include "expr.h"
+#include "tree-dfa.h"
+#include "builtins.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "dumpfile.h"
+#include "gimple-match.h"
+
+
+/* Forward declarations of the private auto-generated matchers.
+   They expect valueized operands in canonical order and do not
+   perform simplification of all-constant operands.  */
+static bool gimple_simplify (code_helper *, tree *,
+			     gimple_seq *, tree (*)(tree),
+			     code_helper, tree, tree);
+static bool gimple_simplify (code_helper *, tree *,
+			     gimple_seq *, tree (*)(tree),
+			     code_helper, tree, tree, tree);
+static bool gimple_simplify (code_helper *, tree *,
+			     gimple_seq *, tree (*)(tree),
+			     code_helper, tree, tree, tree, tree);
+
+
+/* Return whether T is a constant that we'll dispatch to fold to
+   evaluate fully constant expressions.  */
+
+static inline bool
+constant_for_folding (tree t)
+{
+  return (CONSTANT_CLASS_P (t)
+	  /* The following is only interesting to string builtins.  */
+	  || (TREE_CODE (t) == ADDR_EXPR
+	      && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST));
+}
+
+
+/* Helper that matches and simplifies the toplevel result from
+   a gimple_simplify run (where we don't want to build
+   a stmt in case it's used in in-place folding).  Replaces
+   *RES_CODE and *RES_OPS with a simplified and/or canonicalized
+   result and returns whether any change was made.  */
+
+static bool
+gimple_resimplify1 (gimple_seq *seq,
+		    code_helper *res_code, tree type, tree *res_ops,
+		    tree (*valueize)(tree))
+{
+  if (constant_for_folding (res_ops[0]))
+    {
+      tree tem = NULL_TREE;
+      if (res_code->is_tree_code ())
+	tem = fold_unary_to_constant (*res_code, type, res_ops[0]);
+      else
+	{
+	  tree decl = builtin_decl_implicit (*res_code);
+	  if (decl)
+	    {
+	      tem = fold_builtin_n (UNKNOWN_LOCATION, decl, res_ops, 1, false);
+	      if (tem)
+		{
+		  /* fold_builtin_n wraps the result inside a NOP_EXPR.  */
+		  STRIP_NOPS (tem);
+		  tem = fold_convert (type, tem);
+		}
+	    }
+	}
+      if (tem != NULL_TREE
+	  && CONSTANT_CLASS_P (tem))
+	{
+	  res_ops[0] = tem;
+	  res_ops[1] = NULL_TREE;
+	  res_ops[2] = NULL_TREE;
+	  *res_code = TREE_CODE (res_ops[0]);
+	  return true;
+	}
+    }
+
+  code_helper res_code2;
+  tree res_ops2[3] = {};
+  if (gimple_simplify (&res_code2, res_ops2, seq, valueize,
+		       *res_code, type, res_ops[0]))
+    {
+      *res_code = res_code2;
+      res_ops[0] = res_ops2[0];
+      res_ops[1] = res_ops2[1];
+      res_ops[2] = res_ops2[2];
+      return true;
+    }
+
+  return false;
+}
+
+/* Helper that matches and simplifies the toplevel result from
+   a gimple_simplify run (where we don't want to build
+   a stmt in case it's used in in-place folding).  Replaces
+   *RES_CODE and *RES_OPS with a simplified and/or canonicalized
+   result and returns whether any change was made.  */
+
+static bool
+gimple_resimplify2 (gimple_seq *seq,
+		    code_helper *res_code, tree type, tree *res_ops,
+		    tree (*valueize)(tree))
+{
+  if (constant_for_folding (res_ops[0]) && constant_for_folding (res_ops[1]))
+    {
+      tree tem = NULL_TREE;
+      if (res_code->is_tree_code ())
+	tem = fold_binary_to_constant (*res_code, type,
+				       res_ops[0], res_ops[1]);
+      else
+	{
+	  tree decl = builtin_decl_implicit (*res_code);
+	  if (decl)
+	    {
+	      tem = fold_builtin_n (UNKNOWN_LOCATION, decl, res_ops, 2, false);
+	      if (tem)
+		{
+		  /* fold_builtin_n wraps the result inside a NOP_EXPR.  */
+		  STRIP_NOPS (tem);
+		  tem = fold_convert (type, tem);
+		}
+	    }
+	}
+      if (tem != NULL_TREE
+	  && CONSTANT_CLASS_P (tem))
+	{
+	  res_ops[0] = tem;
+	  res_ops[1] = NULL_TREE;
+	  res_ops[2] = NULL_TREE;
+	  *res_code = TREE_CODE (res_ops[0]);
+	  return true;
+	}
+    }
+
+  /* Canonicalize operand order.  */
+  bool canonicalized = false;
+  if (res_code->is_tree_code ()
+      && (TREE_CODE_CLASS ((enum tree_code) *res_code) == tcc_comparison
+	  || commutative_tree_code (*res_code))
+      && tree_swap_operands_p (res_ops[0], res_ops[1], false))
+    {
+      tree tem = res_ops[0];
+      res_ops[0] = res_ops[1];
+      res_ops[1] = tem;
+      if (TREE_CODE_CLASS ((enum tree_code) *res_code) == tcc_comparison)
+	*res_code = swap_tree_comparison (*res_code);
+      canonicalized = true;
+    }
+
+  code_helper res_code2;
+  tree res_ops2[3] = {};
+  if (gimple_simplify (&res_code2, res_ops2, seq, valueize,
+		       *res_code, type, res_ops[0], res_ops[1]))
+    {
+      *res_code = res_code2;
+      res_ops[0] = res_ops2[0];
+      res_ops[1] = res_ops2[1];
+      res_ops[2] = res_ops2[2];
+      return true;
+    }
+
+  return canonicalized;
+}
+
+/* Helper that matches and simplifies the toplevel result from
+   a gimple_simplify run (where we don't want to build
+   a stmt in case it's used in in-place folding).  Replaces
+   *RES_CODE and *RES_OPS with a simplified and/or canonicalized
+   result and returns whether any change was made.  */
+
+static bool
+gimple_resimplify3 (gimple_seq *seq,
+		    code_helper *res_code, tree type, tree *res_ops,
+		    tree (*valueize)(tree))
+{
+  if (constant_for_folding (res_ops[0]) && constant_for_folding (res_ops[1])
+      && constant_for_folding (res_ops[2]))
+    {
+      tree tem = NULL_TREE;
+      if (res_code->is_tree_code ())
+	tem = fold_ternary/*_to_constant*/ (*res_code, type, res_ops[0],
+					    res_ops[1], res_ops[2]);
+      else
+	{
+	  tree decl = builtin_decl_implicit (*res_code);
+	  if (decl)
+	    {
+	      tem = fold_builtin_n (UNKNOWN_LOCATION, decl, res_ops, 3, false);
+	      if (tem)
+		{
+		  /* fold_builtin_n wraps the result inside a NOP_EXPR.  */
+		  STRIP_NOPS (tem);
+		  tem = fold_convert (type, tem);
+		}
+	    }
+	}
+      if (tem != NULL_TREE
+	  && CONSTANT_CLASS_P (tem))
+	{
+	  res_ops[0] = tem;
+	  res_ops[1] = NULL_TREE;
+	  res_ops[2] = NULL_TREE;
+	  *res_code = TREE_CODE (res_ops[0]);
+	  return true;
+	}
+    }
+
+  /* Canonicalize operand order.  */
+  bool canonicalized = false;
+  if (res_code->is_tree_code ()
+      && commutative_ternary_tree_code (*res_code)
+      && tree_swap_operands_p (res_ops[0], res_ops[1], false))
+    {
+      tree tem = res_ops[0];
+      res_ops[0] = res_ops[1];
+      res_ops[1] = tem;
+      canonicalized = true;
+    }
+
+  code_helper res_code2;
+  tree res_ops2[3] = {};
+  if (gimple_simplify (&res_code2, res_ops2, seq, valueize,
+		       *res_code, type,
+		       res_ops[0], res_ops[1], res_ops[2]))
+    {
+      *res_code = res_code2;
+      res_ops[0] = res_ops2[0];
+      res_ops[1] = res_ops2[1];
+      res_ops[2] = res_ops2[2];
+      return true;
+    }
+
+  return canonicalized;
+}
+
+
+/* If in GIMPLE expressions with CODE go as single-rhs build
+   a GENERIC tree for that expression into *OP0.  */
+
+void
+maybe_build_generic_op (enum tree_code code, tree type,
+			tree *op0, tree op1, tree op2)
+{
+  switch (code)
+    {
+    case REALPART_EXPR:
+    case IMAGPART_EXPR:
+    case VIEW_CONVERT_EXPR:
+      *op0 = build1 (code, type, *op0);
+      break;
+    case BIT_FIELD_REF:
+      *op0 = build3 (code, type, *op0, op1, op2);
+      break;
+    default:;
+    }
+}
+
+/* Push the exploded expression described by RCODE, TYPE and OPS
+   as a statement to SEQ if necessary and return a gimple value
+   denoting the value of the expression.  If RES is not NULL
+   then the result will be always RES and even gimple values are
+   pushed to SEQ.  */
+
+tree
+maybe_push_res_to_seq (code_helper rcode, tree type, tree *ops,
+		       gimple_seq *seq, tree res)
+{
+  if (rcode.is_tree_code ())
+    {
+      if (!res
+	  && (TREE_CODE_LENGTH ((tree_code) rcode) == 0
+	      || ((tree_code) rcode) == ADDR_EXPR)
+	  && is_gimple_val (ops[0]))
+	return ops[0];
+      if (!seq)
+	return NULL_TREE;
+      /* Play safe and do not allow abnormals to be mentioned in
+         newly created statements.  */
+      if ((TREE_CODE (ops[0]) == SSA_NAME
+	   && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0]))
+	  || (ops[1]
+	      && TREE_CODE (ops[1]) == SSA_NAME
+	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1]))
+	  || (ops[2]
+	      && TREE_CODE (ops[2]) == SSA_NAME
+	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2])))
+	return NULL_TREE;
+      if (!res)
+	res = make_ssa_name (type, NULL);
+      maybe_build_generic_op (rcode, type, &ops[0], ops[1], ops[2]);
+      gimple new_stmt = gimple_build_assign_with_ops (rcode, res,
+						      ops[0], ops[1], ops[2]);
+      gimple_seq_add_stmt_without_update (seq, new_stmt);
+      return res;
+    }
+  else
+    {
+      if (!seq)
+	return NULL_TREE;
+      tree decl = builtin_decl_implicit (rcode);
+      if (!decl)
+	return NULL_TREE;
+      unsigned nargs = type_num_arguments (TREE_TYPE (decl));
+      gcc_assert (nargs <= 3);
+      /* Play safe and do not allow abnormals to be mentioned in
+         newly created statements.  */
+      if ((TREE_CODE (ops[0]) == SSA_NAME
+	   && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0]))
+	  || (nargs >= 2
+	      && TREE_CODE (ops[1]) == SSA_NAME
+	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1]))
+	  || (nargs == 3
+	      && TREE_CODE (ops[2]) == SSA_NAME
+	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2])))
+	return NULL_TREE;
+      if (!res)
+	res = make_ssa_name (type, NULL);
+      gimple new_stmt = gimple_build_call (decl, nargs, ops[0], ops[1], ops[2]);
+      gimple_call_set_lhs (new_stmt, res);
+      gimple_seq_add_stmt_without_update (seq, new_stmt);
+      return res;
+    }
+}
+
+
+/* Public API overloads follow for operation being tree_code or
+   built_in_function and for one to three operands or arguments.
+   They return NULL_TREE if nothing could be simplified or
+   the resulting simplified value with parts pushed to SEQ.
+   If SEQ is NULL then if the simplification needs to create
+   new stmts it will fail.  If VALUEIZE is non-NULL then all
+   SSA names will be valueized using that hook prior to
+   applying simplifications.  */
+
+/* Unary ops.  */
+
+tree
+gimple_simplify (enum tree_code code, tree type,
+		 tree op0,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  if (constant_for_folding (op0))
+    {
+      tree res = fold_unary_to_constant (code, type, op0);
+      if (res != NULL_TREE
+	  && CONSTANT_CLASS_P (res))
+	return res;
+    }
+
+  code_helper rcode;
+  tree ops[3] = {};
+  if (!gimple_simplify (&rcode, ops, seq, valueize,
+			code, type, op0))
+    return NULL_TREE;
+  return maybe_push_res_to_seq (rcode, type, ops, seq);
+}
+
+/* Binary ops.  */
+
+tree
+gimple_simplify (enum tree_code code, tree type,
+		 tree op0, tree op1,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  if (constant_for_folding (op0) && constant_for_folding (op1))
+    {
+      tree res = fold_binary_to_constant (code, type, op0, op1);
+      if (res != NULL_TREE
+	  && CONSTANT_CLASS_P (res))
+	return res;
+    }
+
+  /* Canonicalize operand order both for matching and fallback stmt
+     generation.  */
+  if ((commutative_tree_code (code)
+       || TREE_CODE_CLASS (code) == tcc_comparison)
+      && tree_swap_operands_p (op0, op1, false))
+    {
+      tree tem = op0;
+      op0 = op1;
+      op1 = tem;
+      if (TREE_CODE_CLASS (code) == tcc_comparison)
+	code = swap_tree_comparison (code);
+    }
+
+  code_helper rcode;
+  tree ops[3] = {};
+  if (!gimple_simplify (&rcode, ops, seq, valueize,
+			code, type, op0, op1))
+    return NULL_TREE;
+  return maybe_push_res_to_seq (rcode, type, ops, seq);
+}
+
+/* Ternary ops.  */
+
+tree
+gimple_simplify (enum tree_code code, tree type,
+		 tree op0, tree op1, tree op2,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  if (constant_for_folding (op0) && constant_for_folding (op1)
+      && constant_for_folding (op2))
+    {
+      tree res = fold_ternary/*_to_constant */ (code, type, op0, op1, op2);
+      if (res != NULL_TREE
+	  && CONSTANT_CLASS_P (res))
+	return res;
+    }
+
+  /* Canonicalize operand order both for matching and fallback stmt
+     generation.  */
+  if (commutative_ternary_tree_code (code)
+      && tree_swap_operands_p (op0, op1, false))
+    {
+      tree tem = op0;
+      op0 = op1;
+      op1 = tem;
+    }
+
+  code_helper rcode;
+  tree ops[3] = {};
+  if (!gimple_simplify (&rcode, ops, seq, valueize,
+			code, type, op0, op1, op2))
+    return NULL_TREE;
+  return maybe_push_res_to_seq (rcode, type, ops, seq);
+}
+
+/* Builtin function with one argument.  */
+
+tree
+gimple_simplify (enum built_in_function fn, tree type,
+		 tree arg0,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  if (constant_for_folding (arg0))
+    {
+      tree decl = builtin_decl_implicit (fn);
+      if (decl)
+	{
+	  tree res = fold_builtin_n (UNKNOWN_LOCATION, decl, &arg0, 1, false);
+	  if (res)
+	    {
+	      /* fold_builtin_n wraps the result inside a NOP_EXPR.  */
+	      STRIP_NOPS (res);
+	      res = fold_convert (type, res);
+	      if (CONSTANT_CLASS_P (res))
+		return res;
+	    }
+	}
+    }
+
+  code_helper rcode;
+  tree ops[3] = {};
+  if (!gimple_simplify (&rcode, ops, seq, valueize,
+			fn, type, arg0))
+    return NULL_TREE;
+  return maybe_push_res_to_seq (rcode, type, ops, seq);
+}
+
+/* Builtin function with two arguments.  */
+
+tree
+gimple_simplify (enum built_in_function fn, tree type,
+		 tree arg0, tree arg1,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  if (constant_for_folding (arg0)
+      && constant_for_folding (arg1))
+    {
+      tree decl = builtin_decl_implicit (fn);
+      if (decl)
+	{
+	  tree args[2];
+	  args[0] = arg0;
+	  args[1] = arg1;
+	  tree res = fold_builtin_n (UNKNOWN_LOCATION, decl, args, 2, false);
+	  if (res)
+	    {
+	      /* fold_builtin_n wraps the result inside a NOP_EXPR.  */
+	      STRIP_NOPS (res);
+	      res = fold_convert (type, res);
+	      if (CONSTANT_CLASS_P (res))
+		return res;
+	    }
+	}
+    }
+
+  code_helper rcode;
+  tree ops[3] = {};
+  if (!gimple_simplify (&rcode, ops, seq, valueize,
+			fn, type, arg0, arg1))
+    return NULL_TREE;
+  return maybe_push_res_to_seq (rcode, type, ops, seq);
+}
+
+/* Builtin function with three arguments.  */
+
+tree
+gimple_simplify (enum built_in_function fn, tree type,
+		 tree arg0, tree arg1, tree arg2,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  if (constant_for_folding (arg0)
+      && constant_for_folding (arg1)
+      && constant_for_folding (arg2))
+    {
+      tree decl = builtin_decl_implicit (fn);
+      if (decl)
+	{
+	  tree args[3];
+	  args[0] = arg0;
+	  args[1] = arg1;
+	  args[2] = arg2;
+	  tree res = fold_builtin_n (UNKNOWN_LOCATION, decl, args, 3, false);
+	  if (res)
+	    {
+	      /* fold_builtin_n wraps the result inside a NOP_EXPR.  */
+	      STRIP_NOPS (res);
+	      res = fold_convert (type, res);
+	      if (CONSTANT_CLASS_P (res))
+		return res;
+	    }
+	}
+    }
+
+  code_helper rcode;
+  tree ops[3] = {};
+  if (!gimple_simplify (&rcode, ops, seq, valueize,
+			fn, type, arg0, arg1, arg2))
+    return NULL_TREE;
+  return maybe_push_res_to_seq (rcode, type, ops, seq);
+}
+
+
+/* The main STMT based simplification entry.  It is used by the fold_stmt
+   and the fold_stmt_to_constant APIs.  */
+
+bool
+gimple_simplify (gimple stmt,
+		 code_helper *rcode, tree *ops,
+		 gimple_seq *seq, tree (*valueize)(tree))
+{
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_ASSIGN:
+      {
+	enum tree_code code = gimple_assign_rhs_code (stmt);
+	tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+	switch (gimple_assign_rhs_class (stmt))
+	  {
+	  case GIMPLE_SINGLE_RHS:
+	    if (code == REALPART_EXPR
+		|| code == IMAGPART_EXPR
+		|| code == VIEW_CONVERT_EXPR)
+	      {
+		tree op0 = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
+		if (valueize && TREE_CODE (op0) == SSA_NAME)
+		  {
+		    tree tem = valueize (op0);
+		    if (tem)
+		      op0 = tem;
+		  }
+		*rcode = code;
+		ops[0] = op0;
+		return gimple_resimplify1 (seq, rcode, type, ops, valueize);
+	      }
+	    else if (code == BIT_FIELD_REF)
+	      {
+		tree rhs1 = gimple_assign_rhs1 (stmt);
+		tree op0 = TREE_OPERAND (rhs1, 0);
+		if (valueize && TREE_CODE (op0) == SSA_NAME)
+		  {
+		    tree tem = valueize (op0);
+		    if (tem)
+		      op0 = tem;
+		  }
+		*rcode = code;
+		ops[0] = op0;
+		ops[1] = TREE_OPERAND (rhs1, 1);
+		ops[2] = TREE_OPERAND (rhs1, 2);
+		return gimple_resimplify3 (seq, rcode, type, ops, valueize);
+	      }
+	    else if (code == SSA_NAME
+		     && valueize)
+	      {
+		tree op0 = gimple_assign_rhs1 (stmt);
+		tree valueized = valueize (op0);
+		if (!valueized || op0 == valueized)
+		  return false;
+		ops[0] = valueized;
+		*rcode = TREE_CODE (op0);
+		return true;
+	      }
+	    break;
+	  case GIMPLE_UNARY_RHS:
+	    {
+	      tree rhs1 = gimple_assign_rhs1 (stmt);
+	      if (valueize && TREE_CODE (rhs1) == SSA_NAME)
+		{
+		  tree tem = valueize (rhs1);
+		  if (tem)
+		    rhs1 = tem;
+		}
+	      *rcode = code;
+	      ops[0] = rhs1;
+	      return gimple_resimplify1 (seq, rcode, type, ops, valueize);
+	    }
+	  case GIMPLE_BINARY_RHS:
+	    {
+	      tree rhs1 = gimple_assign_rhs1 (stmt);
+	      if (valueize && TREE_CODE (rhs1) == SSA_NAME)
+		{
+		  tree tem = valueize (rhs1);
+		  if (tem)
+		    rhs1 = tem;
+		}
+	      tree rhs2 = gimple_assign_rhs2 (stmt);
+	      if (valueize && TREE_CODE (rhs2) == SSA_NAME)
+		{
+		  tree tem = valueize (rhs2);
+		  if (tem)
+		    rhs2 = tem;
+		}
+	      *rcode = code;
+	      ops[0] = rhs1;
+	      ops[1] = rhs2;
+	      return gimple_resimplify2 (seq, rcode, type, ops, valueize);
+	    }
+	  case GIMPLE_TERNARY_RHS:
+	    {
+	      tree rhs1 = gimple_assign_rhs1 (stmt);
+	      if (valueize && TREE_CODE (rhs1) == SSA_NAME)
+		{
+		  tree tem = valueize (rhs1);
+		  if (tem)
+		    rhs1 = tem;
+		}
+	      tree rhs2 = gimple_assign_rhs2 (stmt);
+	      if (valueize && TREE_CODE (rhs2) == SSA_NAME)
+		{
+		  tree tem = valueize (rhs2);
+		  if (tem)
+		    rhs2 = tem;
+		}
+	      tree rhs3 = gimple_assign_rhs3 (stmt);
+	      if (valueize && TREE_CODE (rhs3) == SSA_NAME)
+		{
+		  tree tem = valueize (rhs3);
+		  if (tem)
+		    rhs3 = tem;
+		}
+	      *rcode = code;
+	      ops[0] = rhs1;
+	      ops[1] = rhs2;
+	      ops[2] = rhs3;
+	      return gimple_resimplify3 (seq, rcode, type, ops, valueize);
+	    }
+	  default:
+	    gcc_unreachable ();
+	  }
+	break;
+      }
+
+    case GIMPLE_CALL:
+      /* ???  This way we can't simplify calls with side-effects.  */
+      if (gimple_call_lhs (stmt) != NULL_TREE)
+	{
+	  tree fn = gimple_call_fn (stmt);
+	  /* ???  Internal function support missing.  */
+	  if (!fn)
+	    return false;
+	  if (valueize && TREE_CODE (fn) == SSA_NAME)
+	    {
+	      tree tem = valueize (fn);
+	      if (tem)
+		fn = tem;
+	    }
+	  if (!fn
+	      || TREE_CODE (fn) != ADDR_EXPR
+	      || TREE_CODE (TREE_OPERAND (fn, 0)) != FUNCTION_DECL
+	      || DECL_BUILT_IN_CLASS (TREE_OPERAND (fn, 0)) != BUILT_IN_NORMAL
+	      || !builtin_decl_implicit (DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0)))
+	      || !gimple_builtin_call_types_compatible_p (stmt,
+							  TREE_OPERAND (fn, 0)))
+	    return false;
+
+	  tree decl = TREE_OPERAND (fn, 0);
+	  tree type = TREE_TYPE (gimple_call_lhs (stmt));
+	  switch (gimple_call_num_args (stmt))
+	    {
+	    case 1:
+	      {
+		tree arg1 = gimple_call_arg (stmt, 0);
+		if (valueize && TREE_CODE (arg1) == SSA_NAME)
+		  {
+		    tree tem = valueize (arg1);
+		    if (tem)
+		      arg1 = tem;
+		  }
+		*rcode = DECL_FUNCTION_CODE (decl);
+		ops[0] = arg1;
+		return gimple_resimplify1 (seq, rcode, type, ops, valueize);
+	      }
+	    case 2:
+	      {
+		tree arg1 = gimple_call_arg (stmt, 0);
+		if (valueize && TREE_CODE (arg1) == SSA_NAME)
+		  {
+		    tree tem = valueize (arg1);
+		    if (tem)
+		      arg1 = tem;
+		  }
+		tree arg2 = gimple_call_arg (stmt, 1);
+		if (valueize && TREE_CODE (arg2) == SSA_NAME)
+		  {
+		    tree tem = valueize (arg2);
+		    if (tem)
+		      arg2 = tem;
+		  }
+		*rcode = DECL_FUNCTION_CODE (decl);
+		ops[0] = arg1;
+		ops[1] = arg2;
+		return gimple_resimplify2 (seq, rcode, type, ops, valueize);
+	      }
+	    case 3:
+	      {
+		tree arg1 = gimple_call_arg (stmt, 0);
+		if (valueize && TREE_CODE (arg1) == SSA_NAME)
+		  {
+		    tree tem = valueize (arg1);
+		    if (tem)
+		      arg1 = tem;
+		  }
+		tree arg2 = gimple_call_arg (stmt, 1);
+		if (valueize && TREE_CODE (arg2) == SSA_NAME)
+		  {
+		    tree tem = valueize (arg2);
+		    if (tem)
+		      arg2 = tem;
+		  }
+		tree arg3 = gimple_call_arg (stmt, 2);
+		if (valueize && TREE_CODE (arg3) == SSA_NAME)
+		  {
+		    tree tem = valueize (arg3);
+		    if (tem)
+		      arg3 = tem;
+		  }
+		*rcode = DECL_FUNCTION_CODE (decl);
+		ops[0] = arg1;
+		ops[1] = arg2;
+		ops[2] = arg3;
+		return gimple_resimplify3 (seq, rcode, type, ops, valueize);
+	      }
+	    default:
+	      return false;
+	    }
+	}
+      break;
+
+    case GIMPLE_COND:
+      {
+	tree lhs = gimple_cond_lhs (stmt);
+	if (valueize && TREE_CODE (lhs) == SSA_NAME)
+	  {
+	    tree tem = valueize (lhs);
+	    if (tem)
+	      lhs = tem;
+	  }
+	tree rhs = gimple_cond_rhs (stmt);
+	if (valueize && TREE_CODE (rhs) == SSA_NAME)
+	  {
+	    tree tem = valueize (rhs);
+	    if (tem)
+	      rhs = tem;
+	  }
+	*rcode = gimple_cond_code (stmt);
+	ops[0] = lhs;
+	ops[1] = rhs;
+        return gimple_resimplify2 (seq, rcode, boolean_type_node, ops, valueize);
+      }
+
+    default:
+      break;
+    }
+
+  return false;
+}
+
+
+/* Helper for the autogenerated code, valueize OP.  */
+
+inline tree
+do_valueize (tree (*valueize)(tree), tree op)
+{
+  if (valueize && TREE_CODE (op) == SSA_NAME)
+    return valueize (op);
+  return op;
+}
+
diff --git a/gcc/gimple-match.h b/gcc/gimple-match.h
new file mode 100644
index 00000000000..571d5fd311e
--- /dev/null
+++ b/gcc/gimple-match.h
@@ -0,0 +1,50 @@
+/* Gimple simplify definitions.
+
+   Copyright (C) 2011-2014 Free Software Foundation, Inc.
+   Contributed by Richard Guenther <rguenther@suse.de>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_GIMPLE_MATCH_H
+#define GCC_GIMPLE_MATCH_H
+
+
+/* Helper to transparently allow tree codes and builtin function codes
+   exist in one storage entity.  */
+class code_helper
+{
+public:
+  code_helper () {}
+  code_helper (tree_code code) : rep ((int) code) {}
+  code_helper (built_in_function fn) : rep (-(int) fn) {}
+  operator tree_code () const { return (tree_code) rep; }
+  operator built_in_function () const { return (built_in_function) -rep; }
+  bool is_tree_code () const { return rep > 0; }
+  bool is_fn_code () const { return rep < 0; }
+  int get_rep () const { return rep; }
+private:
+  int rep;
+};
+
+bool gimple_simplify (gimple, code_helper *, tree *, gimple_seq *,
+		      tree (*)(tree));
+tree maybe_push_res_to_seq (code_helper, tree, tree *,
+			    gimple_seq *, tree res = NULL_TREE);
+void maybe_build_generic_op (enum tree_code, tree, tree *, tree, tree);
+
+
+#endif  /* GCC_GIMPLE_MATCH_H */
diff --git a/gcc/match.pd b/gcc/match.pd
new file mode 100644
index 00000000000..097dfcd2dfa
--- /dev/null
+++ b/gcc/match.pd
@@ -0,0 +1,30 @@
+/* Match-and-simplify patterns for shared GENERIC and GIMPLE folding.
+   This file is consumed by genmatch which produces gimple-match.c
+   and generic-match.c from it.
+
+   Copyright (C) 2014 Free Software Foundation, Inc.
+   Contributed by Richard Biener <rguenther@suse.de>
+   and Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* Generic tree predicates we inherit.  */
+(define_predicates
+   integer_onep integer_zerop integer_all_onesp
+   real_zerop real_onep
+   CONSTANT_CLASS_P)