This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH][1-2/n] Merge from match-and-simplify


This is a merge of both initial patches, with feedback I got
incorporated.  I am currently bootstrapping and testing this
on x86_64-unknown-linux-gnu and plan to install it after
that finished.

I'll re-send 3/n and up, possibly a bit re-structured.

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Richard.

2014-10-21  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.

Index: gcc/Makefile.in
===================================================================
*** gcc/Makefile.in.orig	2014-10-21 13:47:34.450220139 +0200
--- gcc/Makefile.in	2014-10-21 14:29:59.296044929 +0200
*************** gengtype-lex.o-warn = -Wno-error
*** 204,209 ****
--- 204,211 ----
  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
*************** OBJS = \
*** 1226,1231 ****
--- 1228,1235 ----
  	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 \
*************** MOSTLYCLEANFILES = insn-flags.h insn-con
*** 1503,1509 ****
   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 \
   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) \
--- 1507,1513 ----
   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 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) \
*************** $(common_out_object_file): $(common_out_
*** 2020,2026 ****
  .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
  
  # 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
--- 2024,2030 ----
  .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 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
*************** s-tm-texi: build/genhooks$(build_exeext)
*** 2229,2234 ****
--- 2233,2252 ----
  	  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 \
*************** build/rtl.o: rtl.c $(BCONFIG_H) coretype
*** 2377,2382 ****
--- 2395,2402 ----
    $(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) \
*************** build/genhooks.o : genhooks.c $(TARGET_D
*** 2472,2477 ****
--- 2492,2499 ----
    $(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,
*************** genprogerr = $(genprogmd) genrtl modes g
*** 2492,2502 ****
  $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS)
  
  # Remaining build programs.
! genprog = $(genprogerr) check checksum condmd
  
  # These programs need libs over and above what they get from the above list.
  build/genautomata$(build_exeext) : BUILD_LIBS += -lm
  
  # 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
--- 2514,2527 ----
  $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS)
  
  # Remaining build programs.
! 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
*************** TEXI_GCCINT_FILES = gccint.texi gcc-comm
*** 2831,2837 ****
  	 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
  
  TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi		\
  	 gcc-common.texi gcc-vers.texi
--- 2856,2863 ----
  	 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   \
! 	 match-and-simplify.texi
  
  TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi		\
  	 gcc-common.texi gcc-vers.texi
Index: gcc/generic-match-head.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/generic-match-head.c	2014-10-21 13:47:53.432218832 +0200
***************
*** 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"
+ 
+ 
Index: gcc/gimple-match-head.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/gimple-match-head.c	2014-10-21 14:29:13.899048055 +0200
***************
*** 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;
+ }
+ 
Index: gcc/gimple-match.h
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/gimple-match.h	2014-10-21 13:47:53.433218832 +0200
***************
*** 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 */
Index: gcc/genmatch.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/genmatch.c	2014-10-21 13:51:12.077205156 +0200
***************
*** 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;
+ }
Index: gcc/match.pd
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/match.pd	2014-10-21 13:51:46.565202781 +0200
***************
*** 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)
Index: gcc/builtins.h
===================================================================
*** gcc/builtins.h.orig	2014-10-21 10:47:53.137962419 +0200
--- gcc/builtins.h	2014-10-21 13:47:53.435218832 +0200
*************** extern tree fold_fma (location_t, tree,
*** 75,80 ****
--- 75,81 ----
  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);
Index: gcc/builtins.c
===================================================================
*** gcc/builtins.c.orig	2014-10-21 13:47:28.053220579 +0200
--- gcc/builtins.c	2014-10-21 13:47:53.438218832 +0200
*************** static tree fold_builtin_fabs (location_
*** 180,186 ****
  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);
--- 180,185 ----
*************** fold_builtin_4 (location_t loc, tree fnd
*** 10395,10401 ****
  
  #define MAX_ARGS_TO_FOLD_BUILTIN 4
  
! static tree
  fold_builtin_n (location_t loc, tree fndecl, tree *args, int nargs, bool ignore)
  {
    tree ret = NULL_TREE;
--- 10394,10400 ----
  
  #define MAX_ARGS_TO_FOLD_BUILTIN 4
  
! tree
  fold_builtin_n (location_t loc, tree fndecl, tree *args, int nargs, bool ignore)
  {
    tree ret = NULL_TREE;
Index: gcc/doc/match-and-simplify.texi
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/doc/match-and-simplify.texi	2014-10-21 13:47:53.438218832 +0200
***************
*** 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.
+ 
Index: gcc/doc/gccint.texi
===================================================================
*** gcc/doc/gccint.texi.orig	2014-10-21 10:47:53.137962419 +0200
--- gcc/doc/gccint.texi	2014-10-21 13:47:53.775218808 +0200
*************** Additional tutorial information is linke
*** 123,128 ****
--- 123,129 ----
  * 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.
  
*************** Additional tutorial information is linke
*** 158,163 ****
--- 159,165 ----
  @include gty.texi
  @include plugins.texi
  @include lto.texi
+ @include match-and-simplify.texi
  
  @include funding.texi
  @include gnu.texi
Index: gcc/gimple-fold.h
===================================================================
*** gcc/gimple-fold.h.orig	2014-10-21 10:47:52.676962451 +0200
--- gcc/gimple-fold.h	2014-10-21 13:47:53.817218806 +0200
*************** extern tree gimple_fold_indirect_ref (tr
*** 45,50 ****
--- 45,109 ----
  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)
*************** gimple_convert (gimple_seq *seq, tree ty
*** 52,55 ****
--- 111,128 ----
    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 */
Index: gcc/gimple-fold.c
===================================================================
*** gcc/gimple-fold.c.orig	2014-10-21 13:47:33.962220173 +0200
--- gcc/gimple-fold.c	2014-10-21 13:47:53.818218805 +0200
*************** rewrite_to_defined_overflow (gimple stmt
*** 5364,5382 ****
    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.  */
  
  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;
  }
--- 5364,5565 ----
    return stmts;
  }
  
! 
! /* 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;
!   return gimple_build (seq, loc, NOP_EXPR, type, op);
  }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]