Makefile.in (OBJS): Add gimple-match.o and generic-match.o.

2014-10-22  Richard Biener  <rguenther@suse.de>
	Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>

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

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

Co-Authored-By: Prathamesh Kulkarni <bilbotheelffriend@gmail.com>

From-SVN: r216542

1 files changed, 3039 insertions, 0 deletions

diff --git a/gcc/genmatch.c b/gcc/genmatch.c
new file mode 100644
index 0000000..2def7fa
--- /dev/null
+++ b/gcc/genmatch.c
@@ -0,0 +1,3039 @@
+/* Generate pattern matching and transform code shared between
+   GENERIC and GIMPLE folding code from match-and-simplify description.
+
+   Copyright (C) 2014 Free Software Foundation, Inc.
+   Contributed by Richard Biener <rguenther@suse.de>
+   and Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "bconfig.h"
+#include <new>
+#include <map>
+#include <utility>
+#include <string>
+#include "system.h"
+#include "coretypes.h"
+#include <cpplib.h>
+#include "errors.h"
+#include "hashtab.h"
+#include "hash-table.h"
+#include "vec.h"
+#include "is-a.h"
+
+
+/* libccp helpers.  */
+
+static struct line_maps *line_table;
+
+static bool
+#if GCC_VERSION >= 4001
+__attribute__((format (printf, 6, 0)))
+#endif
+error_cb (cpp_reader *, int, int, source_location location,
+	  unsigned int, const char *msg, va_list *ap)
+{
+  const line_map *map;
+  linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
+  expanded_location loc = linemap_expand_location (line_table, map, location);
+  fprintf (stderr, "%s:%d:%d error: ", loc.file, loc.line, loc.column);
+  vfprintf (stderr, msg, *ap);
+  fprintf (stderr, "\n");
+  FILE *f = fopen (loc.file, "r");
+  if (f)
+    {
+      char buf[128];
+      while (loc.line > 0)
+	{
+	  if (!fgets (buf, 128, f))
+	    goto notfound;
+	  if (buf[strlen (buf) - 1] != '\n')
+	    {
+	      if (loc.line > 1)
+		loc.line++;
+	    }
+	  loc.line--;
+	}
+      fprintf (stderr, "%s", buf);
+      for (int i = 0; i < loc.column - 1; ++i)
+	fputc (' ', stderr);
+      fputc ('^', stderr);
+      fputc ('\n', stderr);
+notfound:
+      fclose (f);
+    }
+  exit (1);
+}
+
+static void
+#if GCC_VERSION >= 4001
+__attribute__((format (printf, 2, 3)))
+#endif
+fatal_at (const cpp_token *tk, const char *msg, ...)
+{
+  va_list ap;
+  va_start (ap, msg);
+  error_cb (NULL, CPP_DL_FATAL, 0, tk->src_loc, 0, msg, &ap);
+  va_end (ap);
+}
+
+static void
+output_line_directive (FILE *f, source_location location,
+		       bool dumpfile = false)
+{
+  const line_map *map;
+  linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
+  expanded_location loc = linemap_expand_location (line_table, map, location);
+  if (dumpfile)
+    {
+      /* When writing to a dumpfile only dump the filename.  */
+      const char *file = strrchr (loc.file, DIR_SEPARATOR);
+      if (!file)
+	file = loc.file;
+      else
+	++file;
+      fprintf (f, "%s:%d", file, loc.line);
+    }
+  else
+    /* Other gen programs really output line directives here, at least for
+       development it's right now more convenient to have line information
+       from the generated file.  Still keep the directives as comment for now
+       to easily back-point to the meta-description.  */
+    fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
+}
+
+
+/* Pull in tree codes and builtin function codes from their
+   definition files.  */
+
+#define DEFTREECODE(SYM, STRING, TYPE, NARGS)   SYM,
+enum tree_code {
+#include "tree.def"
+CONVERT0,
+CONVERT1,
+CONVERT2,
+MAX_TREE_CODES
+};
+#undef DEFTREECODE
+
+#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
+enum built_in_function {
+#include "builtins.def"
+END_BUILTINS
+};
+#undef DEF_BUILTIN
+
+
+/* Base class for all identifiers the parser knows.  */
+
+struct id_base : typed_noop_remove<id_base>
+{
+  enum id_kind { CODE, FN, PREDICATE, USER } kind;
+
+  id_base (id_kind, const char *, int = -1);
+
+  hashval_t hashval;
+  int nargs;
+  const char *id;
+
+  /* hash_table support.  */
+  typedef id_base value_type;
+  typedef id_base compare_type;
+  static inline hashval_t hash (const value_type *);
+  static inline int equal (const value_type *, const compare_type *);
+};
+
+inline hashval_t
+id_base::hash (const value_type *op)
+{
+  return op->hashval;
+}
+
+inline int
+id_base::equal (const value_type *op1,
+			const compare_type *op2)
+{
+  return (op1->hashval == op2->hashval
+	  && strcmp (op1->id, op2->id) == 0);
+}
+
+/* Hashtable of known pattern operators.  This is pre-seeded from
+   all known tree codes and all known builtin function ids.  */
+static hash_table<id_base> *operators;
+
+id_base::id_base (id_kind kind_, const char *id_, int nargs_)
+{
+  kind = kind_;
+  id = id_;
+  nargs = nargs_;
+  hashval = htab_hash_string (id);
+}
+
+/* Identifier that maps to a tree code.  */
+
+struct operator_id : public id_base
+{
+  operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
+	       const char *tcc_)
+      : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
+  enum tree_code code;
+  const char *tcc;
+};
+
+/* Identifier that maps to a builtin function code.  */
+
+struct fn_id : public id_base
+{
+  fn_id (enum built_in_function fn_, const char *id_)
+      : id_base (id_base::FN, id_), fn (fn_) {}
+  enum built_in_function fn;
+};
+
+struct simplify;
+
+/* Identifier that maps to a user-defined predicate.  */
+
+struct predicate_id : public id_base
+{
+  predicate_id (const char *id_)
+    : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
+  vec<simplify *> matchers;
+};
+
+/* Identifier that maps to a operator defined by a 'for' directive.  */
+
+struct user_id : public id_base
+{
+  user_id (const char *id_)
+    : id_base (id_base::USER, id_), substitutes (vNULL) {}
+  vec<id_base *> substitutes;
+};
+
+template<>
+template<>
+inline bool
+is_a_helper <fn_id *>::test (id_base *id)
+{
+  return id->kind == id_base::FN;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <operator_id *>::test (id_base *id)
+{
+  return id->kind == id_base::CODE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <predicate_id *>::test (id_base *id)
+{
+  return id->kind == id_base::PREDICATE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <user_id *>::test (id_base *id)
+{
+  return id->kind == id_base::USER;
+}
+
+/* Add a predicate identifier to the hash.  */
+
+static predicate_id *
+add_predicate (const char *id)
+{
+  predicate_id *p = new predicate_id (id);
+  id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
+  if (*slot)
+    fatal ("duplicate id definition");
+  *slot = p;
+  return p;
+}
+
+/* Add a tree code identifier to the hash.  */
+
+static void
+add_operator (enum tree_code code, const char *id,
+	      const char *tcc, unsigned nargs)
+{
+  if (strcmp (tcc, "tcc_unary") != 0
+      && strcmp (tcc, "tcc_binary") != 0
+      && strcmp (tcc, "tcc_comparison") != 0
+      && strcmp (tcc, "tcc_expression") != 0
+      /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR.  */
+      && strcmp (tcc, "tcc_reference") != 0
+      /* To have INTEGER_CST and friends as "predicate operators".  */
+      && strcmp (tcc, "tcc_constant") != 0)
+    return;
+  operator_id *op = new operator_id (code, id, nargs, tcc);
+  id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
+  if (*slot)
+    fatal ("duplicate id definition");
+  *slot = op;
+}
+
+/* Add a builtin identifier to the hash.  */
+
+static void
+add_builtin (enum built_in_function code, const char *id)
+{
+  fn_id *fn = new fn_id (code, id);
+  id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
+  if (*slot)
+    fatal ("duplicate id definition");
+  *slot = fn;
+}
+
+/* Helper for easy comparing ID with tree code CODE.  */
+
+static bool
+operator==(id_base &id, enum tree_code code)
+{
+  if (operator_id *oid = dyn_cast <operator_id *> (&id))
+    return oid->code == code;
+  return false;
+}
+
+/* Lookup the identifier ID.  */
+
+id_base *
+get_operator (const char *id)
+{
+  id_base tem (id_base::CODE, id);
+
+  id_base *op = operators->find_with_hash (&tem, tem.hashval);
+  if (op)
+    return op;
+
+  /* Try all-uppercase.  */
+  char *id2 = xstrdup (id);
+  for (unsigned i = 0; i < strlen (id2); ++i)
+    id2[i] = TOUPPER (id2[i]);
+  new (&tem) id_base (id_base::CODE, id2);
+  op = operators->find_with_hash (&tem, tem.hashval);
+  if (op)
+    {
+      free (id2);
+      return op;
+    }
+
+  /* Try _EXPR appended.  */
+  id2 = (char *)xrealloc (id2, strlen (id2) + sizeof ("_EXPR") + 1);
+  strcat (id2, "_EXPR");
+  new (&tem) id_base (id_base::CODE, id2);
+  op = operators->find_with_hash (&tem, tem.hashval);
+  if (op)
+    {
+      free (id2);
+      return op;
+    }
+
+  return 0;
+}
+
+
+
+/* The AST produced by parsing of the pattern definitions.  */
+
+struct dt_operand;
+
+/* The base class for operands.  */
+
+struct operand {
+  enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR };
+  operand (enum op_type type_) : type (type_) {}
+  enum op_type type;
+  virtual void gen_transform (FILE *, const char *, bool, int,
+			      const char *, dt_operand ** = 0)
+    { gcc_unreachable  (); }
+};
+
+/* A predicate operand.  Predicates are leafs in the AST.  */
+
+struct predicate : public operand
+{
+  predicate (predicate_id *p_) : operand (OP_PREDICATE), p (p_) {}
+  predicate_id *p;
+};
+
+/* An operand that constitutes an expression.  Expressions include
+   function calls and user-defined predicate invocations.  */
+
+struct expr : public operand
+{
+  expr (id_base *operation_, bool is_commutative_ = false)
+    : operand (OP_EXPR), operation (operation_),
+      ops (vNULL), expr_type (NULL), is_commutative (is_commutative_) {}
+  void append_op (operand *op) { ops.safe_push (op); }
+  /* The operator and its operands.  */
+  id_base *operation;
+  vec<operand *> ops;
+  /* An explicitely specified type - used exclusively for conversions.  */
+  const char *expr_type;
+  /* Whether the operation is to be applied commutatively.  This is
+     later lowered to two separate patterns.  */
+  bool is_commutative;
+  virtual void gen_transform (FILE *f, const char *, bool, int,
+			      const char *, dt_operand ** = 0);
+};
+
+/* An operator that is represented by native C code.  This is always
+   a leaf operand in the AST.  This class is also used to represent
+   the code to be generated for 'if' and 'with' expressions.  */
+
+struct c_expr : public operand
+{
+  /* A mapping of an identifier and its replacement.  Used to apply
+     'for' lowering.  */
+  struct id_tab {
+    const char *id;
+    const char *oper;
+    id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
+  };
+
+  c_expr (cpp_reader *r_, vec<cpp_token> code_, unsigned nr_stmts_,
+	  vec<id_tab> ids_, std::map<std::string, unsigned> *capture_ids_)
+    : operand (OP_C_EXPR), r (r_), code (code_), capture_ids (capture_ids_),
+      nr_stmts (nr_stmts_), ids (ids_) {}
+  /* cpplib tokens and state to transform this back to source.  */
+  cpp_reader *r;
+  vec<cpp_token> code;
+  std::map<std::string, unsigned> *capture_ids;
+  /* The number of statements parsed (well, the number of ';'s).  */
+  unsigned nr_stmts;
+  /* The identifier replacement vector.  */
+  vec<id_tab> ids;
+  virtual void gen_transform (FILE *f, const char *, bool, int,
+			      const char *, dt_operand **);
+};
+
+/* A wrapper around another operand that captures its value.  */
+
+struct capture : public operand
+{
+  capture (unsigned where_, operand *what_)
+      : operand (OP_CAPTURE), where (where_), what (what_) {}
+  /* Identifier index for the value.  */
+  unsigned where;
+  /* The captured value.  */
+  operand *what;
+  virtual void gen_transform (FILE *f, const char *, bool, int,
+			      const char *, dt_operand ** = 0);
+};
+
+template<>
+template<>
+inline bool
+is_a_helper <capture *>::test (operand *op)
+{
+  return op->type == operand::OP_CAPTURE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <predicate *>::test (operand *op)
+{
+  return op->type == operand::OP_PREDICATE;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <c_expr *>::test (operand *op)
+{
+  return op->type == operand::OP_C_EXPR;
+}
+
+template<>
+template<>
+inline bool
+is_a_helper <expr *>::test (operand *op)
+{
+  return op->type == operand::OP_EXPR;
+}
+
+/* Helper to distinguish 'if' from 'with' expressions.  */
+
+struct if_or_with
+{
+  if_or_with (operand *cexpr_, source_location location_, bool is_with_)
+      : location (location_), cexpr (cexpr_), is_with (is_with_) {}
+  source_location location;
+  operand *cexpr;
+  bool is_with;
+};
+
+/* The main class of a pattern and its transform.  This is used to
+   represent both (simplify ...) and (match ...) kinds.  The AST
+   duplicates all outer 'if' and 'for' expressions here so each
+   simplify can exist in isolation.  */
+
+struct simplify
+{
+  simplify (operand *match_, source_location match_location_,
+	    struct operand *result_, source_location result_location_,
+	    vec<if_or_with> ifexpr_vec_, vec<vec<user_id *> > for_vec_,
+	    std::map<std::string, unsigned> *capture_ids_)
+      : match (match_), match_location (match_location_),
+      result (result_), result_location (result_location_),
+      ifexpr_vec (ifexpr_vec_), for_vec (for_vec_),
+      capture_ids (capture_ids_), capture_max (capture_ids_->size () - 1) {}
+
+  /* The expression that is matched against the GENERIC or GIMPLE IL.  */
+  operand *match;
+  source_location match_location;
+  /* For a (simplify ...) the expression produced when the pattern applies.
+     For a (match ...) either NULL if it is a simple predicate or the
+     single expression specifying the matched operands.  */
+  struct operand *result;
+  source_location result_location;
+  /* Collected 'if' expressions that need to evaluate to true to make
+     the pattern apply.  */
+  vec<if_or_with> ifexpr_vec;
+  /* Collected 'for' expression operators that have to be replaced
+     in the lowering phase.  */
+  vec<vec<user_id *> > for_vec;
+  /* A map of capture identifiers to indexes.  */
+  std::map<std::string, unsigned> *capture_ids;
+  int capture_max;
+};
+
+/* Debugging routines for dumping the AST.  */
+
+DEBUG_FUNCTION void
+print_operand (operand *o, FILE *f = stderr, bool flattened = false)
+{
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      fprintf (f, "@%u", c->where);
+      if (c->what && flattened == false)
+	{
+	  putc (':', f);
+	  print_operand (c->what, f, flattened);
+	  putc (' ', f);
+	}
+    }
+
+  else if (predicate *p = dyn_cast<predicate *> (o))
+    fprintf (f, "%s", p->p->id);
+
+  else if (is_a<c_expr *> (o))
+    fprintf (f, "c_expr");
+
+  else if (expr *e = dyn_cast<expr *> (o))
+    {
+      fprintf (f, "(%s", e->operation->id);
+
+      if (flattened == false)
+	{
+	  putc (' ', f);
+	  for (unsigned i = 0; i < e->ops.length (); ++i)
+	    {
+	      print_operand (e->ops[i], f, flattened);
+	      putc (' ', f);
+	    }
+	}
+      putc (')', f);
+    }
+
+  else
+    gcc_unreachable ();
+}
+
+DEBUG_FUNCTION void
+print_matches (struct simplify *s, FILE *f = stderr)
+{
+  fprintf (f, "for expression: ");
+  print_operand (s->match, f);
+  putc ('\n', f);
+}
+
+
+/* AST lowering.  */
+
+/* Lowering of commutative operators.  */
+
+static void
+cartesian_product (const vec< vec<operand *> >& ops_vector,
+		   vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
+{
+  if (n == ops_vector.length ())
+    {
+      vec<operand *> xv = v.copy ();
+      result.safe_push (xv);
+      return;
+    }
+
+  for (unsigned i = 0; i < ops_vector[n].length (); ++i)
+    {
+      v[n] = ops_vector[n][i];
+      cartesian_product (ops_vector, result, v, n + 1);
+    }
+}
+
+/* Lower OP to two operands in case it is marked as commutative.  */
+
+static vec<operand *>
+commutate (operand *op)
+{
+  vec<operand *> ret = vNULL;
+
+  if (capture *c = dyn_cast <capture *> (op))
+    {
+      if (!c->what)
+	{
+	  ret.safe_push (op);
+	  return ret;
+	}
+      vec<operand *> v = commutate (c->what);
+      for (unsigned i = 0; i < v.length (); ++i)
+	{
+	  capture *nc = new capture (c->where, v[i]);
+	  ret.safe_push (nc);
+	}
+      return ret;
+    }
+
+  expr *e = dyn_cast <expr *> (op);
+  if (!e || e->ops.length () == 0)
+    {
+      ret.safe_push (op);
+      return ret;
+    }
+
+  vec< vec<operand *> > ops_vector = vNULL;
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ops_vector.safe_push (commutate (e->ops[i]));
+
+  auto_vec< vec<operand *> > result;
+  auto_vec<operand *> v (e->ops.length ());
+  v.quick_grow_cleared (e->ops.length ());
+  cartesian_product (ops_vector, result, v, 0);
+
+
+  for (unsigned i = 0; i < result.length (); ++i)
+    {
+      expr *ne = new expr (e->operation);
+      for (unsigned j = 0; j < result[i].length (); ++j)
+	ne->append_op (result[i][j]);
+      ret.safe_push (ne);
+    }
+
+  if (!e->is_commutative)
+    return ret;
+
+  for (unsigned i = 0; i < result.length (); ++i)
+    {
+      expr *ne = new expr (e->operation);
+      // result[i].length () is 2 since e->operation is binary
+      for (unsigned j = result[i].length (); j; --j)
+	ne->append_op (result[i][j-1]);
+      ret.safe_push (ne);
+    }
+
+  return ret;
+}
+
+/* Lower operations marked as commutative in the AST of S and push
+   the resulting patterns to SIMPLIFIERS.  */
+
+static void
+lower_commutative (simplify *s, vec<simplify *>& simplifiers)
+{
+  vec<operand *> matchers = commutate (s->match);
+  for (unsigned i = 0; i < matchers.length (); ++i)
+    {
+      simplify *ns = new simplify (matchers[i], s->match_location,
+				   s->result, s->result_location, s->ifexpr_vec,
+				   s->for_vec, s->capture_ids);
+      simplifiers.safe_push (ns);
+    }
+}
+
+/* Strip conditional conversios using operator OPER from O and its
+   children if STRIP, else replace them with an unconditional convert.  */
+
+operand *
+lower_opt_convert (operand *o, enum tree_code oper, bool strip)
+{
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      if (c->what)
+	return new capture (c->where, lower_opt_convert (c->what, oper, strip));
+      else
+	return c;
+    }
+
+  expr *e = dyn_cast<expr *> (o);
+  if (!e)
+    return o;
+
+  if (*e->operation == oper)
+    {
+      if (strip)
+	return lower_opt_convert (e->ops[0], oper, strip);
+
+      expr *ne = new expr (get_operator ("CONVERT_EXPR"));
+      ne->append_op (lower_opt_convert (e->ops[0], oper, strip));
+      return ne;
+    }
+
+  expr *ne = new expr (e->operation, e->is_commutative);
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ne->append_op (lower_opt_convert (e->ops[i], oper, strip));
+
+  return ne;
+}
+
+/* Determine whether O or its children uses the conditional conversion
+   operator OPER.  */
+
+static bool
+has_opt_convert (operand *o, enum tree_code oper)
+{
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      if (c->what)
+	return has_opt_convert (c->what, oper);
+      else
+	return false;
+    }
+
+  expr *e = dyn_cast<expr *> (o);
+  if (!e)
+    return false;
+
+  if (*e->operation == oper)
+    return true;
+
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    if (has_opt_convert (e->ops[i], oper))
+      return true;
+
+  return false;
+}
+
+/* Lower conditional convert operators in O, expanding it to a vector
+   if required.  */
+
+static vec<operand *>
+lower_opt_convert (operand *o)
+{
+  vec<operand *> v1 = vNULL, v2;
+
+  v1.safe_push (o);
+
+  enum tree_code opers[] = { CONVERT0, CONVERT1, CONVERT2 };
+
+  /* Conditional converts are lowered to a pattern with the
+     conversion and one without.  The three different conditional
+     convert codes are lowered separately.  */
+
+  for (unsigned i = 0; i < 3; ++i)
+    {
+      v2 = vNULL;
+      for (unsigned j = 0; j < v1.length (); ++j)
+	if (has_opt_convert (v1[j], opers[i]))
+	  {
+	    v2.safe_push (lower_opt_convert (v1[j], opers[i], false));
+	    v2.safe_push (lower_opt_convert (v1[j], opers[i], true));
+	  }
+
+      if (v2 != vNULL)
+	{
+	  v1 = vNULL;
+	  for (unsigned j = 0; j < v2.length (); ++j)
+	    v1.safe_push (v2[j]);
+	}
+    }
+
+  return v1;
+}
+
+/* Lower conditional convert operators in the AST of S and push
+   the resulting multiple patterns to SIMPLIFIERS.  */
+
+static void
+lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
+{
+  vec<operand *> matchers = lower_opt_convert (s->match);
+  for (unsigned i = 0; i < matchers.length (); ++i)
+    {
+      simplify *ns = new simplify (matchers[i], s->match_location,
+				   s->result, s->result_location, s->ifexpr_vec,
+				   s->for_vec, s->capture_ids);
+      simplifiers.safe_push (ns);
+    }
+}
+
+/* In AST operand O replace operator ID with operator WITH.  */
+
+operand *
+replace_id (operand *o, user_id *id, id_base *with)
+{
+  /* Deep-copy captures and expressions, replacing operations as
+     needed.  */
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      if (!c->what)
+	return c;
+      return new capture (c->where, replace_id (c->what, id, with));
+    }
+  else if (expr *e = dyn_cast<expr *> (o))
+    {
+      expr *ne = new expr (e->operation == id ? with : e->operation,
+			   e->is_commutative);
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	ne->append_op (replace_id (e->ops[i], id, with));
+      return ne;
+    }
+
+  /* For c_expr we simply record a string replacement table which is
+     applied at code-generation time.  */
+  if (c_expr *ce = dyn_cast<c_expr *> (o))
+    {
+      vec<c_expr::id_tab> ids = ce->ids.copy ();
+      ids.safe_push (c_expr::id_tab (id->id, with->id));
+      return new c_expr (ce->r, ce->code, ce->nr_stmts, ids, ce->capture_ids);
+    }
+
+  return o;
+}
+
+/* Lower recorded fors for SIN and output to SIMPLIFIERS.  */
+
+static void
+lower_for (simplify *sin, vec<simplify *>& simplifiers)
+{
+  vec<vec<user_id *> >& for_vec = sin->for_vec;
+  unsigned worklist_start = 0;
+  auto_vec<simplify *> worklist;
+  worklist.safe_push (sin);
+
+  /* Lower each recorded for separately, operating on the
+     set of simplifiers created by the previous one.
+     Lower inner-to-outer so inner for substitutes can refer
+     to operators replaced by outer fors.  */
+  for (int fi = for_vec.length () - 1; fi >= 0; --fi)
+    {
+      vec<user_id *>& ids = for_vec[fi];
+      unsigned n_ids = ids.length ();
+      unsigned max_n_opers = 0;
+      for (unsigned i = 0; i < n_ids; ++i)
+	if (ids[i]->substitutes.length () > max_n_opers)
+	  max_n_opers = ids[i]->substitutes.length ();
+
+      unsigned worklist_end = worklist.length ();
+      for (unsigned si = worklist_start; si < worklist_end; ++si)
+	{
+	  simplify *s = worklist[si];
+	  for (unsigned j = 0; j < max_n_opers; ++j)
+	    {
+	      operand *match_op = s->match;
+	      operand *result_op = s->result;
+	      vec<if_or_with> ifexpr_vec = s->ifexpr_vec.copy ();
+
+	      for (unsigned i = 0; i < n_ids; ++i)
+		{
+		  user_id *id = ids[i];
+		  id_base *oper = id->substitutes[j % id->substitutes.length ()];
+		  match_op = replace_id (match_op, id, oper);
+		  if (result_op)
+		    result_op = replace_id (result_op, id, oper);
+		  for (unsigned k = 0; k < s->ifexpr_vec.length (); ++k)
+		    ifexpr_vec[k].cexpr = replace_id (ifexpr_vec[k].cexpr,
+						      id, oper);
+		}
+	      simplify *ns = new simplify (match_op, s->match_location,
+					   result_op, s->result_location,
+					   ifexpr_vec, vNULL, s->capture_ids);
+	      worklist.safe_push (ns);
+	    }
+	}
+      worklist_start = worklist_end;
+    }
+
+  /* Copy out the result from the last for lowering.  */
+  for (unsigned i = worklist_start; i < worklist.length (); ++i)
+    simplifiers.safe_push (worklist[i]);
+}
+
+/* Lower the AST for everything in SIMPLIFIERS.  */
+
+static void
+lower (vec<simplify *>& simplifiers)
+{
+  auto_vec<simplify *> out_simplifiers0;
+  for (unsigned i = 0; i < simplifiers.length (); ++i)
+    lower_opt_convert (simplifiers[i], out_simplifiers0);
+
+  auto_vec<simplify *> out_simplifiers1;
+  for (unsigned i = 0; i < out_simplifiers0.length (); ++i)
+    lower_commutative (out_simplifiers0[i], out_simplifiers1);
+
+  simplifiers.truncate (0);
+  for (unsigned i = 0; i < out_simplifiers1.length (); ++i)
+    lower_for (out_simplifiers1[i], simplifiers);
+}
+
+
+
+
+/* The decision tree built for generating GIMPLE and GENERIC pattern
+   matching code.  It represents the 'match' expression of all
+   simplifies and has those as its leafs.  */
+
+/* Decision tree base class, used for DT_TRUE and DT_NODE.  */
+
+struct dt_node
+{
+  enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
+
+  enum dt_type type;
+  unsigned level;
+  vec<dt_node *> kids;
+
+  dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
+
+  dt_node *append_node (dt_node *);
+  dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_simplify (simplify *, unsigned, dt_operand **);
+
+  virtual void gen (FILE *, bool) {}
+
+  void gen_kids (FILE *, bool);
+};
+
+/* Generic decision tree node used for DT_OPERAND and DT_MATCH.  */
+
+struct dt_operand : public dt_node
+{
+  operand *op;
+  dt_operand *match_dop;
+  dt_operand *parent;
+  unsigned pos;
+
+  dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
+	      dt_operand *parent_ = 0, unsigned pos_ = 0)
+      : dt_node (type), op (op_), match_dop (match_dop_),
+      parent (parent_), pos (pos_) {}
+
+  void gen (FILE *, bool);
+  unsigned gen_predicate (FILE *, const char *, bool);
+  unsigned gen_match_op (FILE *, const char *);
+
+  unsigned gen_gimple_expr (FILE *);
+  unsigned gen_generic_expr (FILE *, const char *);
+
+  char *get_name (char *);
+  void gen_opname (char *, unsigned);
+};
+
+/* Leaf node of the decision tree, used for DT_SIMPLIFY.  */
+
+struct dt_simplify : public dt_node
+{
+  simplify *s;
+  unsigned pattern_no;
+  dt_operand **indexes;
+
+  dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
+	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
+	  indexes (indexes_)  {}
+
+  void gen (FILE *f, bool);
+};
+
+template<>
+template<>
+inline bool
+is_a_helper <dt_operand *>::test (dt_node *n)
+{
+  return (n->type == dt_node::DT_OPERAND
+	  || n->type == dt_node::DT_MATCH);
+}
+
+/* A container for the actual decision tree.  */
+
+struct decision_tree
+{
+  dt_node *root;
+
+  void insert (struct simplify *, unsigned);
+  void gen_gimple (FILE *f = stderr);
+  void gen_generic (FILE *f = stderr);
+  void print (FILE *f = stderr);
+
+  decision_tree () { root = new dt_node (dt_node::DT_NODE); }
+
+  static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
+				  unsigned pos = 0, dt_node *parent = 0);
+  static dt_node *find_node (vec<dt_node *>&, dt_node *);
+  static bool cmp_node (dt_node *, dt_node *);
+  static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
+};
+
+/* Compare two AST operands O1 and O2 and return true if they are equal.  */
+
+bool
+cmp_operand (operand *o1, operand *o2)
+{
+  if (!o1 || !o2 || o1->type != o2->type)
+    return false;
+
+  if (o1->type == operand::OP_PREDICATE)
+    {
+      predicate *p1 = as_a<predicate *>(o1);
+      predicate *p2 = as_a<predicate *>(o2);
+      return p1->p == p2->p;
+    }
+  else if (o1->type == operand::OP_EXPR)
+    {
+      expr *e1 = static_cast<expr *>(o1);
+      expr *e2 = static_cast<expr *>(o2);
+      return e1->operation == e2->operation;
+    }
+  else
+    return false;
+}
+
+/* Compare two decision tree nodes N1 and N2 and return true if they
+   are equal.  */
+
+bool
+decision_tree::cmp_node (dt_node *n1, dt_node *n2)
+{
+  if (!n1 || !n2 || n1->type != n2->type)
+    return false;
+
+  if (n1 == n2 || n1->type == dt_node::DT_TRUE)
+    return true;
+
+  if (n1->type == dt_node::DT_OPERAND)
+    return cmp_operand ((as_a<dt_operand *> (n1))->op,
+			(as_a<dt_operand *> (n2))->op);
+  else if (n1->type == dt_node::DT_MATCH)
+    return ((as_a<dt_operand *> (n1))->match_dop
+	    == (as_a<dt_operand *> (n2))->match_dop);
+  return false;
+}
+
+/* Search OPS for a decision tree node like P and return it if found.  */
+
+dt_node *
+decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
+{
+  for (unsigned i = 0; i < ops.length (); ++i)
+    if (decision_tree::cmp_node (ops[i], p))
+      return ops[i];
+
+  return NULL;
+}
+
+/* Append N to the decision tree if it there is not already an existing
+   identical child.  */
+
+dt_node *
+dt_node::append_node (dt_node *n)
+{
+  dt_node *kid;
+
+  kid = decision_tree::find_node (kids, n);
+  if (kid)
+    return kid;
+
+  kids.safe_push (n);
+  n->level = this->level + 1;
+
+  unsigned len = kids.length ();
+
+  if (len > 1 && kids[len - 2]->type == dt_node::DT_TRUE)
+    {
+      dt_node *p = kids[len - 2];
+      kids[len - 2] = kids[len - 1];
+      kids[len - 1] = p;
+    }
+
+  return n;
+}
+
+/* Append OP to the decision tree.  */
+
+dt_node *
+dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
+  dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
+  return append_node (n);
+}
+
+/* Append a DT_TRUE decision tree node.  */
+
+dt_node *
+dt_node::append_true_op (dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = as_a<dt_operand *> (parent);
+  dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
+  return append_node (n);
+}
+
+/* Append a DT_MATCH decision tree node.  */
+
+dt_node *
+dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = as_a<dt_operand *> (parent);
+  dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
+  return append_node (n);
+}
+
+/* Append S to the decision tree.  */
+
+dt_node *
+dt_node::append_simplify (simplify *s, unsigned pattern_no,
+			  dt_operand **indexes)
+{
+  dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
+  return append_node (n);
+}
+
+/* Insert O into the decision tree and return the decision tree node found
+   or created.  */
+
+dt_node *
+decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
+			       unsigned pos, dt_node *parent)
+{
+  dt_node *q, *elm = 0;
+
+  if (capture *c = dyn_cast<capture *> (o))
+    {
+      unsigned capt_index = c->where;
+
+      if (indexes[capt_index] == 0)
+	{
+	  if (c->what)
+	    q = insert_operand (p, c->what, indexes, pos, parent);
+	  else
+	    {
+	      q = elm = p->append_true_op (parent, pos);
+	      goto at_assert_elm;
+	    }
+	  // get to the last capture
+	  for (operand *what = c->what;
+	       what && is_a<capture *> (what);
+	       c = as_a<capture *> (what), what = c->what)
+	    ;
+
+	  if (!c->what)
+	    {
+	      unsigned cc_index = c->where;
+	      dt_operand *match_op = indexes[cc_index];
+
+	      dt_operand temp (dt_node::DT_TRUE, 0, 0);
+	      elm = decision_tree::find_node (p->kids, &temp);
+
+	      if (elm == 0)
+		{
+		  dt_operand temp (dt_node::DT_MATCH, 0, match_op);
+		  elm = decision_tree::find_node (p->kids, &temp);
+		}
+	    }
+	  else
+	    {
+	      dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
+	      elm = decision_tree::find_node (p->kids, &temp);
+	    }
+
+at_assert_elm:
+	  gcc_assert (elm->type == dt_node::DT_TRUE
+		      || elm->type == dt_node::DT_OPERAND
+		      || elm->type == dt_node::DT_MATCH);
+	  indexes[capt_index] = static_cast<dt_operand *> (elm);
+	  return q;
+	}
+      else
+	{
+	  p = p->append_match_op (indexes[capt_index], parent, pos);
+	  if (c->what)
+	    return insert_operand (p, c->what, indexes, 0, p);
+	  else
+	    return p;
+	}
+    }
+  p = p->append_op (o, parent, pos);
+  q = p;
+
+  if (expr *e = dyn_cast <expr *>(o))
+    {
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
+    }
+
+  return q;
+}
+
+/* Insert S into the decision tree.  */
+
+void
+decision_tree::insert (struct simplify *s, unsigned pattern_no)
+{
+  if (s->match->type != operand::OP_EXPR)
+    return;
+
+  dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
+  dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
+  p->append_simplify (s, pattern_no, indexes);
+}
+
+/* Debug functions to dump the decision tree.  */
+
+DEBUG_FUNCTION void
+decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
+{
+  if (p->type == dt_node::DT_NODE)
+    fprintf (f, "root");
+  else
+    {
+      fprintf (f, "|");
+      for (unsigned i = 0; i < indent; i++)
+	fprintf (f, "-");
+
+      if (p->type == dt_node::DT_OPERAND)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(p);
+	  print_operand (dop->op, f, true);
+	}
+      else if (p->type == dt_node::DT_TRUE)
+	fprintf (f, "true");
+      else if (p->type == dt_node::DT_MATCH)
+	fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
+      else if (p->type == dt_node::DT_SIMPLIFY)
+	{
+	  dt_simplify *s = static_cast<dt_simplify *> (p);
+	  fprintf (f, "simplify_%u { ", s->pattern_no);
+	  for (int i = 0; i <= s->s->capture_max; ++i)
+	    fprintf (f, "%p, ", (void *) s->indexes[i]);
+	  fprintf (f, " } ");
+	}
+    }
+
+  fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
+
+  for (unsigned i = 0; i < p->kids.length (); ++i)
+    decision_tree::print_node (p->kids[i], f, indent + 2);
+}
+
+DEBUG_FUNCTION void
+decision_tree::print (FILE *f)
+{
+  return decision_tree::print_node (root, f);
+}
+
+
+
+/* Code generation off the decision tree and the refered AST nodes.  */
+
+bool
+is_conversion (id_base *op)
+{
+  return (*op == CONVERT_EXPR
+	  || *op == NOP_EXPR
+	  || *op == FLOAT_EXPR
+	  || *op == FIX_TRUNC_EXPR
+	  || *op == VIEW_CONVERT_EXPR);
+}
+
+/* Get the type to be used for generating operands of OP from the
+   various sources.  */
+
+static const char *
+get_operand_type (id_base *op, const char *in_type,
+		  const char *expr_type,
+		  const char *other_oprnd_type)
+{
+  /* Generally operands whose type does not match the type of the
+     expression generated need to know their types but match and
+     thus can fall back to 'other_oprnd_type'.  */
+  if (is_conversion (op))
+    return other_oprnd_type;
+  else if (*op == REALPART_EXPR
+	   || *op == IMAGPART_EXPR)
+    return other_oprnd_type;
+  else if (is_a <operator_id *> (op)
+	   && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
+    return other_oprnd_type;
+  else
+    {
+      /* Otherwise all types should match - choose one in order of
+         preference.  */
+      if (expr_type)
+	return expr_type;
+      else if (in_type)
+	return in_type;
+      else
+	return other_oprnd_type;
+    }
+}
+
+/* Generate transform code for an expression.  */
+
+void
+expr::gen_transform (FILE *f, const char *dest, bool gimple, int depth,
+		     const char *in_type, dt_operand **indexes)
+{
+  bool conversion_p = is_conversion (operation);
+  const char *type = expr_type;
+  char optype[64];
+  if (type)
+    /* If there was a type specification in the pattern use it.  */
+    ;
+  else if (conversion_p)
+    /* For conversions we need to build the expression using the
+       outer type passed in.  */
+    type = in_type;
+  else if (*operation == REALPART_EXPR
+	   || *operation == IMAGPART_EXPR)
+    {
+      /* __real and __imag use the component type of its operand.  */
+      sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
+      type = optype;
+    }
+  else if (is_a <operator_id *> (operation)
+	   && !strcmp (as_a <operator_id *> (operation)->tcc, "tcc_comparison"))
+    {
+      /* comparisons use boolean_type_node (or what gets in), but
+         their operands need to figure out the types themselves.  */
+      sprintf (optype, "boolean_type_node");
+      type = optype;
+    }
+  else
+    {
+      /* Other operations are of the same type as their first operand.  */
+      sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
+      type = optype;
+    }
+  if (!type)
+    fatal ("two conversions in a row");
+
+  fprintf (f, "{\n");
+  fprintf (f, "  tree ops%d[%u], res;\n", depth, ops.length ());
+  char op0type[64];
+  snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
+  for (unsigned i = 0; i < ops.length (); ++i)
+    {
+      char dest[32];
+      snprintf (dest, 32, "  ops%d[%u]", depth, i);
+      const char *optype
+	= get_operand_type (operation, in_type, expr_type,
+			    i == 0 ? NULL : op0type);
+      ops[i]->gen_transform (f, dest, gimple, depth + 1, optype, indexes);
+    }
+
+  if (gimple)
+    {
+      /* ???  Have another helper that is like gimple_build but may
+	 fail if seq == NULL.  */
+      fprintf (f, "  if (!seq)\n"
+	       "    {\n"
+	       "      res = gimple_simplify (%s, %s",
+	       operation->id, type);
+      for (unsigned i = 0; i < ops.length (); ++i)
+	fprintf (f, ", ops%d[%u]", depth, i);
+      fprintf (f, ", seq, valueize);\n");
+      fprintf (f, "      if (!res) return false;\n");
+      fprintf (f, "    }\n");
+      fprintf (f, "  else\n");
+      fprintf (f, "    res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
+	       operation->id, type);
+      for (unsigned i = 0; i < ops.length (); ++i)
+	fprintf (f, ", ops%d[%u]", depth, i);
+      fprintf (f, ", valueize);\n");
+    }
+  else
+    {
+      if (operation->kind == id_base::CODE)
+	fprintf (f, "  res = fold_build%d (%s, %s",
+		 ops.length(), operation->id, type);
+      else
+	fprintf (f, "  res = build_call_expr (builtin_decl_implicit (%s), %d",
+		 operation->id, ops.length());
+      for (unsigned i = 0; i < ops.length (); ++i)
+	fprintf (f, ", ops%d[%u]", depth, i);
+      fprintf (f, ");\n");
+    }
+  fprintf (f, "  %s = res;\n", dest);
+  fprintf (f, "}\n");
+}
+
+/* Generate code for a c_expr which is either the expression inside
+   an if statement or a sequence of statements which computes a
+   result to be stored to DEST.  */
+
+void
+c_expr::gen_transform (FILE *f, const char *dest,
+		       bool, int, const char *, dt_operand **)
+{
+  if (dest && nr_stmts == 1)
+    fprintf (f, "%s = ", dest);
+
+  unsigned stmt_nr = 1;
+  for (unsigned i = 0; i < code.length (); ++i)
+    {
+      const cpp_token *token = &code[i];
+
+      /* Replace captures for code-gen.  */
+      if (token->type == CPP_ATSIGN)
+	{
+	  const cpp_token *n = &code[i+1];
+	  if ((n->type == CPP_NUMBER
+	       || n->type == CPP_NAME)
+	      && !(n->flags & PREV_WHITE))
+	    {
+	      if (token->flags & PREV_WHITE)
+		fputc (' ', f);
+	      const char *id;
+	      if (n->type == CPP_NUMBER)
+		id = (const char *)n->val.str.text;
+	      else
+		id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
+	      fprintf (f, "captures[%u]", (*capture_ids)[id]);
+	      ++i;
+	      continue;
+	    }
+	}
+
+      if (token->flags & PREV_WHITE)
+	fputc (' ', f);
+
+      if (token->type == CPP_NAME)
+	{
+	  const char *id = (const char *) NODE_NAME (token->val.node.node);
+	  unsigned j;
+	  for (j = 0; j < ids.length (); ++j)
+	    {
+	    if (strcmp (id, ids[j].id) == 0)
+	      {
+		fprintf (f, "%s", ids[j].oper);
+		break;
+	      }
+	    }
+	  if (j < ids.length ())
+	    continue;
+	}
+
+      /* Output the token as string.  */
+      char *tk = (char *)cpp_token_as_text (r, token);
+      fputs (tk, f);
+
+      if (token->type == CPP_SEMICOLON)
+	{
+	  stmt_nr++;
+	  if (dest && stmt_nr == nr_stmts)
+	    fprintf (f, "\n %s = ", dest);
+	  else
+	    fputc ('\n', f);
+	}
+    }
+}
+
+/* Generate transform code for a capture.  */
+
+void
+capture::gen_transform (FILE *f, const char *dest, bool gimple, int depth,
+			const char *in_type, dt_operand **indexes)
+{
+  if (what && is_a<expr *> (what))
+    {
+      if (indexes[where] == 0)
+	{
+	  char buf[20];
+	  sprintf (buf, "captures[%u]", where);
+	  what->gen_transform (f, buf, gimple, depth, in_type, NULL);
+	}
+    }
+
+  fprintf (f, "%s = captures[%u];\n", dest, where);
+}
+
+/* Return the name of the operand representing the decision tree node.
+   Use NAME as space to generate it.  */
+
+char *
+dt_operand::get_name (char *name)
+{
+  if (!parent)
+    sprintf (name, "t");
+  else if (parent->level == 1)
+    sprintf (name, "op%u", pos);
+  else if (parent->type == dt_node::DT_MATCH)
+    return parent->get_name (name);
+  else
+    sprintf (name, "o%u%u", parent->level, pos);
+  return name;
+}
+
+/* Fill NAME with the operand name at position POS.  */
+
+void
+dt_operand::gen_opname (char *name, unsigned pos)
+{
+  if (!parent)
+    sprintf (name, "op%u", pos);
+  else
+    sprintf (name, "o%u%u", level, pos);
+}
+
+/* Generate matching code for the decision tree operand which is
+   a predicate.  */
+
+unsigned
+dt_operand::gen_predicate (FILE *f, const char *opname, bool gimple)
+{
+  predicate *p = as_a <predicate *> (op);
+
+  if (p->p->matchers.exists ())
+    {
+      /* If this is a predicate generated from a pattern mangle its
+	 name and pass on the valueize hook.  */
+      if (gimple)
+	fprintf (f, "if (gimple_%s (%s, valueize))\n", p->p->id, opname);
+      else
+	fprintf (f, "if (tree_%s (%s))\n", p->p->id, opname);
+    }
+  else
+    fprintf (f, "if (%s (%s))\n", p->p->id, opname);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+/* Generate matching code for the decision tree operand which is
+   a capture-match.  */
+
+unsigned
+dt_operand::gen_match_op (FILE *f, const char *opname)
+{
+  char match_opname[20];
+  match_dop->get_name (match_opname);
+  fprintf (f, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
+	   opname, match_opname, opname, match_opname);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+/* Generate GIMPLE matching code for the decision tree operand.  */
+
+unsigned
+dt_operand::gen_gimple_expr (FILE *f)
+{
+  expr *e = static_cast<expr *> (op);
+  id_base *id = e->operation;
+  unsigned n_ops = e->ops.length ();
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      gen_opname (child_opname, i);
+
+      if (id->kind == id_base::CODE)
+	{
+	  if (*id == REALPART_EXPR || *id == IMAGPART_EXPR
+	      || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
+	    {
+	      /* ???  If this is a memory operation we can't (and should not)
+		 match this.  The only sensible operand types are
+		 SSA names and invariants.  */
+	      fprintf (f, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
+		       child_opname, i);
+	      fprintf (f, "if ((TREE_CODE (%s) == SSA_NAME\n"
+		       "|| is_gimple_min_invariant (%s))\n"
+		       "&& (%s = do_valueize (valueize, %s)))\n"
+		       "{\n", child_opname, child_opname, child_opname,
+		       child_opname);
+	      continue;
+	    }
+	  else
+	    fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
+		     child_opname, i + 1);
+	}
+      else
+	fprintf (f, "tree %s = gimple_call_arg (def_stmt, %u);\n",
+		 child_opname, i);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
+	       child_opname, child_opname);
+      fprintf (f, "{\n");
+    }
+
+  return n_ops;
+}
+
+/* Generate GENERIC matching code for the decision tree operand.  */
+
+unsigned
+dt_operand::gen_generic_expr (FILE *f, const char *opname)
+{
+  expr *e = static_cast<expr *> (op);
+  unsigned n_ops = e->ops.length ();
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      gen_opname (child_opname, i);
+
+      if (e->operation->kind == id_base::CODE)
+	fprintf (f, "tree %s = TREE_OPERAND (%s, %u);\n",
+		 child_opname, opname, i);
+      else
+	fprintf (f, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
+		 child_opname, opname, i);
+    }
+
+  return 0;
+}
+
+/* Generate matching code for the children of the decision tree node.  */
+
+void
+dt_node::gen_kids (FILE *f, bool gimple)
+{
+  auto_vec<dt_operand *> gimple_exprs;
+  auto_vec<dt_operand *> generic_exprs;
+  auto_vec<dt_operand *> fns;
+  auto_vec<dt_operand *> generic_fns;
+  auto_vec<dt_operand *> preds;
+  auto_vec<dt_node *> others;
+  dt_node *true_operand = NULL;
+
+  for (unsigned i = 0; i < kids.length (); ++i)
+    {
+      if (kids[i]->type == dt_node::DT_OPERAND)
+	{
+	  dt_operand *op = as_a<dt_operand *> (kids[i]);
+	  if (expr *e = dyn_cast <expr *> (op->op))
+	    {
+	      if (e->ops.length () == 0)
+		generic_exprs.safe_push (op);
+	      else if (e->operation->kind == id_base::FN)
+		{
+		  if (gimple)
+		    fns.safe_push (op);
+		  else
+		    generic_fns.safe_push (op);
+		}
+	      else if (e->operation->kind == id_base::PREDICATE)
+		preds.safe_push (op);
+	      else
+		{
+		  if (gimple)
+		    gimple_exprs.safe_push (op);
+		  else
+		    generic_exprs.safe_push (op);
+		}
+	    }
+	  else if (op->op->type == operand::OP_PREDICATE)
+	    others.safe_push (kids[i]);
+	  else
+	    gcc_unreachable ();
+	}
+      else if (kids[i]->type == dt_node::DT_MATCH
+	       || kids[i]->type == dt_node::DT_SIMPLIFY)
+	others.safe_push (kids[i]);
+      else if (kids[i]->type == dt_node::DT_TRUE)
+	true_operand = kids[i];
+      else
+	gcc_unreachable ();
+    }
+
+  char buf[128];
+  char *kid_opname = buf;
+
+  unsigned exprs_len = gimple_exprs.length ();
+  unsigned gexprs_len = generic_exprs.length ();
+  unsigned fns_len = fns.length ();
+  unsigned gfns_len = generic_fns.length ();
+
+  if (exprs_len || fns_len || gexprs_len || gfns_len)
+    {
+      if (exprs_len)
+	gimple_exprs[0]->get_name (kid_opname);
+      else if (fns_len)
+	fns[0]->get_name (kid_opname);
+      else if (gfns_len)
+	generic_fns[0]->get_name (kid_opname);
+      else
+	generic_exprs[0]->get_name (kid_opname);
+
+      fprintf (f, "switch (TREE_CODE (%s))\n"
+	       "{\n", kid_opname);
+    }
+
+  if (exprs_len || fns_len)
+    {
+      fprintf (f, "case SSA_NAME:\n");
+      fprintf (f, "{\n");
+      fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname);
+
+      if (exprs_len)
+	{
+	  fprintf (f, "if (is_gimple_assign (def_stmt))\n");
+	  fprintf (f, "switch (gimple_assign_rhs_code (def_stmt))\n"
+		   "{\n");
+	  for (unsigned i = 0; i < exprs_len; ++i)
+	    {
+	      expr *e = as_a <expr *> (gimple_exprs[i]->op);
+	      id_base *op = e->operation;
+	      if (*op == CONVERT_EXPR || *op == NOP_EXPR)
+		fprintf (f, "CASE_CONVERT:\n");
+	      else
+		fprintf (f, "case %s:\n", op->id);
+	      fprintf (f, "{\n");
+	      gimple_exprs[i]->gen (f, true);
+	      fprintf (f, "break;\n"
+		       "}\n");
+	    }
+	  fprintf (f, "default:;\n"
+		   "}\n");
+	}
+
+      if (fns_len)
+	{
+	  if (exprs_len)
+	    fprintf (f, "else ");
+
+	  fprintf (f, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
+		   "{\n"
+		   "tree fndecl = gimple_call_fndecl (def_stmt);\n"
+		   "switch (DECL_FUNCTION_CODE (fndecl))\n"
+		   "{\n");
+
+	  for (unsigned i = 0; i < fns_len; ++i)
+	    {
+	      expr *e = as_a <expr *>(fns[i]->op);
+	      fprintf (f, "case %s:\n"
+		       "{\n", e->operation->id);
+	      fns[i]->gen (f, true);
+	      fprintf (f, "break;\n"
+		       "}\n");
+	    }
+
+	  fprintf (f, "default:;\n"
+		   "}\n"
+		   "}\n");
+	}
+
+      fprintf (f, "break;\n"
+	       "}\n");
+    }
+
+  for (unsigned i = 0; i < generic_exprs.length (); ++i)
+    {
+      expr *e = as_a <expr *>(generic_exprs[i]->op);
+      id_base *op = e->operation;
+      if (*op == CONVERT_EXPR || *op == NOP_EXPR)
+	fprintf (f, "CASE_CONVERT:\n");
+      else
+	fprintf (f, "case %s:\n", op->id);
+      fprintf (f, "{\n");
+      generic_exprs[i]->gen (f, gimple);
+      fprintf (f, "break;\n"
+	       "}\n");
+    }
+
+  if (gfns_len)
+    {
+      fprintf (f, "case CALL_EXPR:\n"
+	       "{\n"
+	       "tree fndecl = get_callee_fndecl (%s);\n"
+	       "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
+	       "switch (DECL_FUNCTION_CODE (fndecl))\n"
+	       "{\n", kid_opname);
+
+      for (unsigned j = 0; j < generic_fns.length (); ++j)
+	{
+	  expr *e = as_a <expr *>(generic_fns[j]->op);
+	  gcc_assert (e->operation->kind == id_base::FN);
+
+	  fprintf (f, "case %s:\n"
+		   "{\n", e->operation->id);
+	  generic_fns[j]->gen (f, false);
+	  fprintf (f, "break;\n"
+		   "}\n");
+	}
+
+      fprintf (f, "default:;\n"
+	       "}\n"
+	       "break;\n"
+	       "}\n");
+    }
+
+  /* Close switch (TREE_CODE ()).  */
+  if (exprs_len || fns_len || gexprs_len || gfns_len)
+    fprintf (f, "default:;\n"
+	     "}\n");
+
+  for (unsigned i = 0; i < preds.length (); ++i)
+    {
+      expr *e = as_a <expr *> (preds[i]->op);
+      predicate_id *p = as_a <predicate_id *> (e->operation);
+      preds[i]->get_name (kid_opname);
+      fprintf (f, "tree %s_pops[%d];\n", kid_opname, p->nargs);
+      fprintf (f, "if (%s_%s (%s, %s_pops%s))\n",
+	       gimple ? "gimple" : "tree",
+	       p->id, kid_opname, kid_opname,
+	       gimple ? ", valueize" : "");
+      fprintf (f, "{\n");
+      for (int j = 0; j < p->nargs; ++j)
+	{
+	  char child_opname[20];
+	  preds[i]->gen_opname (child_opname, j);
+	  fprintf (f, "tree %s = %s_pops[%d];\n", child_opname, kid_opname, j);
+	}
+      preds[i]->gen_kids (f, gimple);
+      fprintf (f, "}\n");
+    }
+
+  for (unsigned i = 0; i < others.length (); ++i)
+    others[i]->gen (f, gimple);
+
+  if (true_operand)
+    true_operand->gen (f, gimple);
+}
+
+/* Generate matching code for the decision tree operand.  */
+
+void
+dt_operand::gen (FILE *f, bool gimple)
+{
+  char opname[20];
+  get_name (opname);
+
+  unsigned n_braces = 0;
+
+  if (type == DT_OPERAND)
+    switch (op->type)
+      {
+	case operand::OP_PREDICATE:
+	  n_braces = gen_predicate (f, opname, gimple);
+	  break;
+
+	case operand::OP_EXPR:
+	  if (gimple)
+	    n_braces = gen_gimple_expr (f);
+	  else
+	    n_braces = gen_generic_expr (f, opname);
+	  break;
+
+	default:
+	  gcc_unreachable ();
+      }
+  else if (type == DT_TRUE)
+    ;
+  else if (type == DT_MATCH)
+    n_braces = gen_match_op (f, opname);
+  else
+    gcc_unreachable ();
+
+  gen_kids (f, gimple);
+
+  for (unsigned i = 0; i < n_braces; ++i)
+    fprintf (f, "}\n");
+}
+
+/* Generate code for the '(if ...)', '(with ..)' and actual transform
+   step of a '(simplify ...)' or '(match ...)'.  This handles everything
+   that is not part of the decision tree (simplify->match).  */
+
+void
+dt_simplify::gen (FILE *f, bool gimple)
+{
+  fprintf (f, "{\n");
+  output_line_directive (f, s->result_location);
+  if (s->capture_max >= 0)
+    fprintf (f, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
+	     s->capture_max + 1);
+
+  for (int i = 0; i <= s->capture_max; ++i)
+    if (indexes[i])
+      {
+	char opname[20];
+	fprintf (f, "captures[%u] = %s;\n", i, indexes[i]->get_name (opname));
+      }
+
+  unsigned n_braces = 0;
+  if (s->ifexpr_vec != vNULL)
+    {
+      for (unsigned i = 0; i < s->ifexpr_vec.length (); ++i)
+	{
+	  if_or_with &w = s->ifexpr_vec[i];
+	  if (w.is_with)
+	    {
+	      fprintf (f, "{\n");
+	      output_line_directive (f, w.location);
+	      w.cexpr->gen_transform (f, NULL, true, 1, "type");
+	      n_braces++;
+	    }
+	  else
+	    {
+	      output_line_directive (f, w.location);
+	      fprintf (f, "if (");
+	      if (i == s->ifexpr_vec.length () - 1
+		  || s->ifexpr_vec[i+1].is_with)
+		w.cexpr->gen_transform (f, NULL, true, 1, "type");
+	      else
+		{
+		  unsigned j = i;
+		  do
+		    {
+		      if (j != i)
+			{
+			  fprintf (f, "\n");
+			  output_line_directive (f, s->ifexpr_vec[j].location);
+			  fprintf (f, "&& ");
+			}
+		      fprintf (f, "(");
+		      s->ifexpr_vec[j].cexpr->gen_transform (f, NULL,
+							     true, 1, "type");
+		      fprintf (f, ")");
+		      ++j;
+		    }
+		  while (j < s->ifexpr_vec.length ()
+			 && !s->ifexpr_vec[j].is_with);
+		  i = j - 1;
+		}
+	      fprintf (f, ")\n");
+	    }
+	}
+      fprintf (f, "{\n");
+      n_braces++;
+    }
+
+  fprintf (f, "if (dump_file && (dump_flags & TDF_DETAILS)) "
+	   "fprintf (dump_file, \"Applying pattern ");
+  output_line_directive (f, s->result_location, true);
+  fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
+
+  if (!s->result)
+    {
+      /* If there is no result then this is a predicate implementation.  */
+      fprintf (f, "return true;\n");
+    }
+  else if (gimple)
+    {
+      if (s->result->type == operand::OP_EXPR)
+	{
+	  expr *e = as_a <expr *> (s->result);
+	  bool is_predicate = is_a <predicate_id *> (e->operation);
+	  if (!is_predicate)
+	    fprintf (f, "*res_code = %s;\n", e->operation->id);
+	  for (unsigned j = 0; j < e->ops.length (); ++j)
+	    {
+	      char dest[32];
+	      snprintf (dest, 32, "  res_ops[%d]", j);
+	      const char *optype
+		= get_operand_type (e->operation,
+				    "type", e->expr_type,
+				    j == 0
+				    ? NULL : "TREE_TYPE (res_ops[0])");
+	      e->ops[j]->gen_transform (f, dest, true, 1, optype, indexes);
+	    }
+
+	  /* Re-fold the toplevel result.  It's basically an embedded
+	     gimple_build w/o actually building the stmt.  */
+	  if (!is_predicate)
+	    fprintf (f, "gimple_resimplify%d (seq, res_code, type, "
+		     "res_ops, valueize);\n", e->ops.length ());
+	}
+      else if (s->result->type == operand::OP_CAPTURE
+	       || s->result->type == operand::OP_C_EXPR)
+	{
+	  s->result->gen_transform (f, "res_ops[0]", true, 1, "type", indexes);
+	  fprintf (f, "*res_code = TREE_CODE (res_ops[0]);\n");
+	}
+      else
+	gcc_unreachable ();
+      fprintf (f, "return true;\n");
+    }
+  else /* GENERIC */
+    {
+      if (s->result->type == operand::OP_EXPR)
+	{
+	  expr *e = as_a <expr *> (s->result);
+	  bool is_predicate = is_a <predicate_id *> (e->operation);
+	  for (unsigned j = 0; j < e->ops.length (); ++j)
+	    {
+	      char dest[32];
+	      if (is_predicate)
+		snprintf (dest, 32, "res_ops[%d]", j);
+	      else
+		{
+		  fprintf (f, "   tree res_op%d;\n", j);
+		  snprintf (dest, 32, "  res_op%d", j);
+		}
+	      const char *optype
+	        = get_operand_type (e->operation,
+				    "type", e->expr_type,
+				    j == 0
+				    ? NULL : "TREE_TYPE (res_op0)");
+	      e->ops[j]->gen_transform (f, dest, false, 1, optype, indexes);
+	    }
+	  if (is_a <predicate_id *> (e->operation))
+	    fprintf (f, "return true;\n");
+	  else
+	    {
+	      /* Re-fold the toplevel result.  */
+	      if (e->operation->kind == id_base::CODE)
+		fprintf (f, "  return fold_build%d (%s, type",
+			 e->ops.length (), e->operation->id);
+	      else
+		fprintf (f, "  return build_call_expr "
+			 "(builtin_decl_implicit (%s), %d",
+			 e->operation->id, e->ops.length());
+	      for (unsigned j = 0; j < e->ops.length (); ++j)
+		fprintf (f, ", res_op%d", j);
+	      fprintf (f, ");\n");
+	    }
+	}
+      else if (s->result->type == operand::OP_CAPTURE
+	       || s->result->type == operand::OP_C_EXPR)
+	{
+	  fprintf (f, "  tree res;\n");
+	  s->result->gen_transform (f, " res", false, 1, "type", indexes);
+	  fprintf (f, "  return res;\n");
+	}
+      else
+	gcc_unreachable ();
+    }
+
+  for (unsigned i = 0; i < n_braces; ++i)
+    fprintf (f, "}\n");
+
+  fprintf (f, "}\n");
+}
+
+/* Main entry to generate code for matching GIMPLE IL off the decision
+   tree.  */
+
+void
+decision_tree::gen_gimple (FILE *f)
+{
+  for (unsigned n = 1; n <= 3; ++n)
+    {
+      fprintf (f, "\nstatic bool\n"
+	       "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
+	       "                 gimple_seq *seq, tree (*valueize)(tree),\n"
+	       "                 code_helper code, tree type");
+      for (unsigned i = 0; i < n; ++i)
+	fprintf (f, ", tree op%d", i);
+      fprintf (f, ")\n");
+      fprintf (f, "{\n");
+
+      fprintf (f, "switch (code.get_rep())\n"
+	       "{\n");
+      for (unsigned i = 0; i < root->kids.length (); i++)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
+	  expr *e = static_cast<expr *>(dop->op);
+	  if (e->ops.length () != n)
+	    continue;
+
+	  if (*e->operation == CONVERT_EXPR
+	      || *e->operation == NOP_EXPR)
+	    fprintf (f, "CASE_CONVERT:\n");
+	  else
+	    fprintf (f, "case %s%s:\n",
+		     is_a <fn_id *> (e->operation) ? "-" : "",
+		     e->operation->id);
+	  fprintf (f, "{\n");
+	  dop->gen_kids (f, true);
+	  fprintf (f, "break;\n");
+	  fprintf (f, "}\n");
+	}
+      fprintf (f, "default:;\n"
+	       "}\n");
+
+      fprintf (f, "return false;\n");
+      fprintf (f, "}\n");
+    }
+}
+
+/* Main entry to generate code for matching GENERIC IL off the decision
+   tree.  */
+
+void
+decision_tree::gen_generic (FILE *f)
+{
+  for (unsigned n = 1; n <= 3; ++n)
+    {
+      fprintf (f, "\ntree\n"
+	       "generic_simplify (enum tree_code code, "
+	       "tree type ATTRIBUTE_UNUSED");
+      for (unsigned i = 0; i < n; ++i)
+	fprintf (f, ", tree op%d", i);
+      fprintf (f, ")\n");
+      fprintf (f, "{\n");
+
+      /* ???  For now reject all simplifications on operands with
+         side-effects as we are not prepared to properly wrap
+	 omitted parts with omit_one_operand and friends.  In
+	 principle we can do that automagically for a subset of
+	 transforms (and only reject the remaining cases).
+	 This fixes for example gcc.c-torture/execute/20050131-1.c.  */
+      fprintf (f, "if ((op0 && TREE_SIDE_EFFECTS (op0))");
+      for (unsigned i = 1; i < n; ++i)
+	fprintf (f, "|| (op%d && TREE_SIDE_EFFECTS (op%d))", i, i);
+      fprintf (f, ")\n"
+	       "  return NULL_TREE;\n");
+
+      fprintf (f, "switch (code)\n"
+	       "{\n");
+      for (unsigned i = 0; i < root->kids.length (); i++)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
+	  expr *e = static_cast<expr *>(dop->op);
+	  if (e->ops.length () != n
+	      /* Builtin simplifications are somewhat premature on
+	         GENERIC.  The following drops patterns with outermost
+		 calls.  It's easy to emit overloads for function code
+		 though if necessary.  */
+	      || e->operation->kind != id_base::CODE)
+	    continue;
+
+	  operator_id *op_id = static_cast <operator_id *> (e->operation);
+	  if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
+	    fprintf (f, "CASE_CONVERT:\n");
+	  else
+	    fprintf (f, "case %s:\n", e->operation->id);
+	  fprintf (f, "{\n");
+	  dop->gen_kids (f, false);
+	  fprintf (f, "break;\n"
+		   "}\n");
+	}
+      fprintf (f, "default:;\n"
+	       "}\n");
+
+      fprintf (f, "return NULL_TREE;\n");
+      fprintf (f, "}\n");
+    }
+}
+
+/* Output code to implement the predicate P from the decision tree DT.  */
+
+void
+write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
+{
+  fprintf (f, "\nbool\n"
+	   "%s%s (tree t%s%s)\n"
+	   "{\n", gimple ? "gimple_" : "tree_", p->id,
+	   p->nargs > 0 ? ", tree *res_ops" : "",
+	   gimple ? ", tree (*valueize)(tree)" : "");
+  /* Conveniently make 'type' available.  */
+  fprintf (f, "tree type = TREE_TYPE (t);\n");
+
+  if (!gimple)
+    fprintf (f, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
+  dt.root->gen_kids (f, gimple);
+
+  fprintf (f, "return false;\n"
+	   "}\n");
+}
+
+/* Write the common header for the GIMPLE/GENERIC IL matching routines.  */
+
+static void
+write_header (FILE *f, const char *head)
+{
+  fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
+  fprintf (f, "   a IL pattern matching and simplification description.  */\n");
+
+  /* Include the header instead of writing it awkwardly quoted here.  */
+  fprintf (f, "\n#include \"%s\"\n", head);
+}
+
+
+
+/* AST parsing.  */
+
+class parser
+{
+public:
+  parser (cpp_reader *);
+
+private:
+  const cpp_token *next ();
+  const cpp_token *peek ();
+  const cpp_token *peek_ident (const char * = NULL);
+  const cpp_token *expect (enum cpp_ttype);
+  void eat_token (enum cpp_ttype);
+  const char *get_string ();
+  const char *get_ident ();
+  void eat_ident (const char *);
+  const char *get_number ();
+
+  id_base *parse_operation ();
+  operand *parse_capture (operand *);
+  operand *parse_expr ();
+  c_expr *parse_c_expr (cpp_ttype);
+  operand *parse_op ();
+
+  void parse_pattern ();
+  void parse_simplify (source_location, vec<simplify *>&, predicate_id *,
+		       expr *);
+  void parse_for (source_location);
+  void parse_if (source_location);
+  void parse_predicates (source_location);
+
+  cpp_reader *r;
+  vec<if_or_with> active_ifs;
+  vec<vec<user_id *> > active_fors;
+
+  std::map<std::string, unsigned> *capture_ids;
+
+public:
+  vec<simplify *> simplifiers;
+  vec<predicate_id *> user_predicates;
+};
+
+/* Lexing helpers.  */
+
+/* Read the next non-whitespace token from R.  */
+
+const cpp_token *
+parser::next ()
+{
+  const cpp_token *token;
+  do
+    {
+      token = cpp_get_token (r);
+    }
+  while (token->type == CPP_PADDING
+	 && token->type != CPP_EOF);
+  return token;
+}
+
+/* Peek at the next non-whitespace token from R.  */
+
+const cpp_token *
+parser::peek ()
+{
+  const cpp_token *token;
+  unsigned i = 0;
+  do
+    {
+      token = cpp_peek_token (r, i++);
+    }
+  while (token->type == CPP_PADDING
+	 && token->type != CPP_EOF);
+  /* If we peek at EOF this is a fatal error as it leaves the
+     cpp_reader in unusable state.  Assume we really wanted a
+     token and thus this EOF is unexpected.  */
+  if (token->type == CPP_EOF)
+    fatal_at (token, "unexpected end of file");
+  return token;
+}
+
+/* Peek at the next identifier token (or return NULL if the next
+   token is not an identifier or equal to ID if supplied).  */
+
+const cpp_token *
+parser::peek_ident (const char *id)
+{
+  const cpp_token *token = peek ();
+  if (token->type != CPP_NAME)
+    return 0;
+
+  if (id == 0)
+    return token;
+
+  const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
+  if (strcmp (id, t) == 0)
+    return token;
+
+  return 0;
+}
+
+/* Read the next token from R and assert it is of type TK.  */
+
+const cpp_token *
+parser::expect (enum cpp_ttype tk)
+{
+  const cpp_token *token = next ();
+  if (token->type != tk)
+    fatal_at (token, "expected %s, got %s",
+	      cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
+
+  return token;
+}
+
+/* Consume the next token from R and assert it is of type TK.  */
+
+void
+parser::eat_token (enum cpp_ttype tk)
+{
+  expect (tk);
+}
+
+/* Read the next token from R and assert it is of type CPP_STRING and
+   return its value.  */
+
+const char *
+parser::get_string ()
+{
+  const cpp_token *token = expect (CPP_STRING);
+  return (const char *)token->val.str.text;
+}
+
+/* Read the next token from R and assert it is of type CPP_NAME and
+   return its value.  */
+
+const char *
+parser::get_ident ()
+{
+  const cpp_token *token = expect (CPP_NAME);
+  return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
+}
+
+/* Eat an identifier token with value S from R.  */
+
+void
+parser::eat_ident (const char *s)
+{
+  const cpp_token *token = peek ();
+  const char *t = get_ident ();
+  if (strcmp (s, t) != 0)
+    fatal_at (token, "expected '%s' got '%s'\n", s, t);
+}
+
+/* Read the next token from R and assert it is of type CPP_NUMBER and
+   return its value.  */
+
+const char *
+parser::get_number ()
+{
+  const cpp_token *token = expect (CPP_NUMBER);
+  return (const char *)token->val.str.text;
+}
+
+
+/* Parse the operator ID, special-casing convert?, convert1? and
+   convert2?  */
+
+id_base *
+parser::parse_operation ()
+{
+  const cpp_token *id_tok = peek ();
+  const char *id = get_ident ();
+  const cpp_token *token = peek ();
+  if (strcmp (id, "convert0") == 0)
+    fatal_at (id_tok, "use 'convert?' here");
+  if (token->type == CPP_QUERY
+      && !(token->flags & PREV_WHITE))
+    {
+      if (strcmp (id, "convert") == 0)
+	id = "convert0";
+      else if (strcmp  (id, "convert1") == 0)
+	;
+      else if (strcmp  (id, "convert2") == 0)
+	;
+      else
+	fatal_at (id_tok, "non-convert operator conditionalized");
+      eat_token (CPP_QUERY);
+    }
+  else if (strcmp  (id, "convert1") == 0
+	   || strcmp  (id, "convert2") == 0)
+    fatal_at (id_tok, "expected '?' after conditional operator");
+  id_base *op = get_operator (id);
+  if (!op)
+    fatal_at (id_tok, "unknown operator %s", id);
+  return op;
+}
+
+/* Parse a capture.
+     capture = '@'<number>  */
+
+struct operand *
+parser::parse_capture (operand *op)
+{
+  eat_token (CPP_ATSIGN);
+  const cpp_token *token = peek ();
+  const char *id;
+  if (token->type == CPP_NUMBER)
+    id = get_number ();
+  else if (token->type == CPP_NAME)
+    id = get_ident ();
+  else
+    fatal_at (token, "expected number or identifier");
+  unsigned next_id = capture_ids->size ();
+  std::pair<std::map<std::string, unsigned>::iterator, bool> res
+    = capture_ids->insert (std::pair<std::string, unsigned>(id, next_id));
+  return new capture ((*res.first).second, op);
+}
+
+/* Parse an expression
+     expr = '(' <operation>[capture][flag][type] <operand>... ')'  */
+
+struct operand *
+parser::parse_expr ()
+{
+  expr *e = new expr (parse_operation ());
+  const cpp_token *token = peek ();
+  operand *op;
+  bool is_commutative = false;
+  const char *expr_type = NULL;
+
+  if (token->type == CPP_COLON
+      && !(token->flags & PREV_WHITE))
+    {
+      eat_token (CPP_COLON);
+      token = peek ();
+      if (token->type == CPP_NAME
+	  && !(token->flags & PREV_WHITE))
+	{
+	  const char *s = get_ident ();
+	  if (s[0] == 'c' && !s[1])
+	    is_commutative = true;
+	  else if (s[1] != '\0')
+	    expr_type = s;
+	  else
+	    fatal_at (token, "flag %s not recognized", s);
+	  token = peek ();
+	}
+      else
+	fatal_at (token, "expected flag or type specifying identifier");
+    }
+
+  if (token->type == CPP_ATSIGN
+      && !(token->flags & PREV_WHITE))
+    op = parse_capture (e);
+  else
+    op = e;
+  do
+    {
+      const cpp_token *token = peek ();
+      if (token->type == CPP_CLOSE_PAREN)
+	{
+	  if (e->operation->nargs != -1
+	      && e->operation->nargs != (int) e->ops.length ())
+	    fatal_at (token, "'%s' expects %u operands, not %u",
+		      e->operation->id, e->operation->nargs, e->ops.length ());
+	  if (is_commutative)
+	    {
+	      if (e->ops.length () == 2)
+		e->is_commutative = true;
+	      else
+		fatal_at (token, "only binary operators or function with "
+			  "two arguments can be marked commutative");
+	    }
+	  e->expr_type = expr_type;
+	  return op;
+	}
+      e->append_op (parse_op ());
+    }
+  while (1);
+}
+
+/* Lex native C code delimited by START recording the preprocessing tokens
+   for later processing.
+     c_expr = ('{'|'(') <pp token>... ('}'|')')  */
+
+c_expr *
+parser::parse_c_expr (cpp_ttype start)
+{
+  const cpp_token *token;
+  cpp_ttype end;
+  unsigned opencnt;
+  vec<cpp_token> code = vNULL;
+  unsigned nr_stmts = 0;
+  eat_token (start);
+  if (start == CPP_OPEN_PAREN)
+    end = CPP_CLOSE_PAREN;
+  else if (start == CPP_OPEN_BRACE)
+    end = CPP_CLOSE_BRACE;
+  else
+    gcc_unreachable ();
+  opencnt = 1;
+  do
+    {
+      token = next ();
+
+      /* Count brace pairs to find the end of the expr to match.  */
+      if (token->type == start)
+	opencnt++;
+      else if (token->type == end
+	       && --opencnt == 0)
+	break;
+
+      /* This is a lame way of counting the number of statements.  */
+      if (token->type == CPP_SEMICOLON)
+	nr_stmts++;
+
+      /* Record the token.  */
+      code.safe_push (*token);
+    }
+  while (1);
+  return new c_expr (r, code, nr_stmts, vNULL, capture_ids);
+}
+
+/* Parse an operand which is either an expression, a predicate or
+   a standalone capture.
+     op = predicate | expr | c_expr | capture  */
+
+struct operand *
+parser::parse_op ()
+{
+  const cpp_token *token = peek ();
+  struct operand *op = NULL;
+  if (token->type == CPP_OPEN_PAREN)
+    {
+      eat_token (CPP_OPEN_PAREN);
+      op = parse_expr ();
+      eat_token (CPP_CLOSE_PAREN);
+    }
+  else if (token->type == CPP_OPEN_BRACE)
+    {
+      op = parse_c_expr (CPP_OPEN_BRACE);
+    }
+  else
+    {
+      /* Remaining ops are either empty or predicates  */
+      if (token->type == CPP_NAME)
+	{
+	  const char *id = get_ident ();
+	  id_base *opr = get_operator (id);
+	  if (!opr)
+	    fatal_at (token, "expected predicate name");
+	  if (operator_id *code = dyn_cast <operator_id *> (opr))
+	    {
+	      if (code->nargs != 0)
+		fatal_at (token, "using an operator with operands as predicate");
+	      /* Parse the zero-operand operator "predicates" as
+		 expression.  */
+	      op = new expr (opr);
+	    }
+	  else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
+	    op = new predicate (p);
+	  else
+	    fatal_at (token, "using an unsupported operator as predicate");
+	  token = peek ();
+	  if (token->flags & PREV_WHITE)
+	    return op;
+	}
+      else if (token->type != CPP_COLON
+	       && token->type != CPP_ATSIGN)
+	fatal_at (token, "expected expression or predicate");
+      /* optionally followed by a capture and a predicate.  */
+      if (token->type == CPP_COLON)
+	fatal_at (token, "not implemented: predicate on leaf operand");
+      if (token->type == CPP_ATSIGN)
+	op = parse_capture (op);
+    }
+
+  return op;
+}
+
+/* Parse
+     simplify = 'simplify' <expr> <result-op>
+   or
+     match = 'match' <ident> <expr> [<result-op>]
+   with
+     <result-op> = <op> | <if> | <with>
+     <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
+     <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
+   and fill SIMPLIFIERS with the results.  */
+
+void
+parser::parse_simplify (source_location match_location,
+			vec<simplify *>& simplifiers, predicate_id *matcher,
+			expr *result)
+{
+  /* Reset the capture map.  */
+  capture_ids = new std::map<std::string, unsigned>;
+
+  const cpp_token *loc = peek ();
+  struct operand *match = parse_op ();
+  if (match->type == operand::OP_CAPTURE && !matcher)
+    fatal_at (loc, "outermost expression cannot be captured");
+  if (match->type == operand::OP_EXPR
+      && is_a <predicate_id *> (as_a <expr *> (match)->operation))
+    fatal_at (loc, "outermost expression cannot be a predicate");
+
+  const cpp_token *token = peek ();
+
+  /* If this if is immediately closed then it is part of a predicate
+     definition.  Push it.  */
+  if (token->type == CPP_CLOSE_PAREN)
+    {
+      if (!matcher)
+	fatal_at (token, "expected transform expression");
+      simplifiers.safe_push
+	(new simplify (match, match_location, result, token->src_loc,
+		       active_ifs.copy (), active_fors.copy (),
+		       capture_ids));
+      return;
+    }
+
+  unsigned active_ifs_len = active_ifs.length ();
+  while (1)
+    {
+      if (token->type == CPP_OPEN_PAREN)
+	{
+	  source_location paren_loc = token->src_loc;
+	  eat_token (CPP_OPEN_PAREN);
+	  if (peek_ident ("if"))
+	    {
+	      eat_ident ("if");
+	      active_ifs.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN),
+						token->src_loc, false));
+	      /* If this if is immediately closed then it contains a
+	         manual matcher or is part of a predicate definition.
+		 Push it.  */
+	      if (peek ()->type == CPP_CLOSE_PAREN)
+		{
+		  if (!matcher)
+		    fatal_at (token, "manual transform not implemented");
+		  simplifiers.safe_push
+		      (new simplify (match, match_location, result,
+				     paren_loc, active_ifs.copy (),
+				     active_fors.copy (), capture_ids));
+		}
+	    }
+	  else if (peek_ident ("with"))
+	    {
+	      eat_ident ("with");
+	      /* Parse (with c-expr expr) as (if-with (true) expr).  */
+	      c_expr *e = parse_c_expr (CPP_OPEN_BRACE);
+	      e->nr_stmts = 0;
+	      active_ifs.safe_push (if_or_with (e, token->src_loc, true));
+	    }
+	  else
+	    {
+	      operand *op = result;
+	      if (!matcher)
+		op = parse_expr ();
+	      simplifiers.safe_push
+		  (new simplify (match, match_location, op,
+				 token->src_loc, active_ifs.copy (),
+				 active_fors.copy (), capture_ids));
+	      eat_token (CPP_CLOSE_PAREN);
+	      /* A "default" result closes the enclosing scope.  */
+	      if (active_ifs.length () > active_ifs_len)
+		{
+		  eat_token (CPP_CLOSE_PAREN);
+		  active_ifs.pop ();
+		}
+	      else
+		return;
+	    }
+	}
+      else if (token->type == CPP_CLOSE_PAREN)
+	{
+	  /* Close a scope if requested.  */
+	  if (active_ifs.length () > active_ifs_len)
+	    {
+	      eat_token (CPP_CLOSE_PAREN);
+	      active_ifs.pop ();
+	      token = peek ();
+	    }
+	  else
+	    return;
+	}
+      else
+	{
+	  if (matcher)
+	    fatal_at (token, "expected match operand expression");
+	  simplifiers.safe_push
+	      (new simplify (match, match_location,
+			     matcher ? result : parse_op (),
+			     token->src_loc, active_ifs.copy (),
+			     active_fors.copy (), capture_ids));
+	  /* A "default" result closes the enclosing scope.  */
+	  if (active_ifs.length () > active_ifs_len)
+	    {
+	      eat_token (CPP_CLOSE_PAREN);
+	      active_ifs.pop ();
+	    }
+	  else
+	    return;
+	}
+      token = peek ();
+    }
+}
+
+/* Parsing of the outer control structures.  */
+
+/* Parse a for expression
+     for = '(' 'for' <subst>... <pattern> ')'
+     subst = <ident> '(' <ident>... ')'  */
+
+void
+parser::parse_for (source_location)
+{
+  vec<user_id *> user_ids = vNULL;
+  const cpp_token *token;
+  unsigned min_n_opers = 0, max_n_opers = 0;
+
+  while (1)
+    {
+      token = peek_ident ();
+      if (token == 0)
+	break;
+
+      /* Insert the user defined operators into the operator hash.  */
+      const char *id = get_ident ();
+      user_id *op = new user_id (id);
+      id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
+      if (*slot)
+	fatal_at (token, "operator already defined");
+      *slot = op;
+      user_ids.safe_push (op);
+
+      eat_token (CPP_OPEN_PAREN);
+
+      int arity = -1;
+      while ((token = peek_ident ()) != 0)
+	{
+	  const char *oper = get_ident ();
+	  id_base *idb = get_operator (oper);
+	  if (idb == NULL)
+	    fatal_at (token, "no such operator '%s'", oper);
+	  if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2)
+	    fatal_at (token, "conditional operators cannot be used inside for");
+
+	  if (arity == -1)
+	    arity = idb->nargs;
+	  else if (idb->nargs == -1)
+	    ;
+	  else if (idb->nargs != arity)
+	    fatal_at (token, "operator '%s' with arity %d does not match "
+		      "others with arity %d", oper, idb->nargs, arity);
+
+	  op->substitutes.safe_push (idb);
+	}
+      op->nargs = arity;
+      token = expect (CPP_CLOSE_PAREN);
+
+      unsigned nsubstitutes = op->substitutes.length ();
+      if (nsubstitutes == 0)
+	fatal_at (token, "A user-defined operator must have at least "
+		  "one substitution");
+      if (max_n_opers == 0)
+	{
+	  min_n_opers = nsubstitutes;
+	  max_n_opers = nsubstitutes;
+	}
+      else
+	{
+	  if (nsubstitutes % min_n_opers != 0
+	      && min_n_opers % nsubstitutes != 0)
+	    fatal_at (token, "All user-defined identifiers must have a "
+		      "multiple number of operator substitutions of the "
+		      "smallest number of substitutions");
+	  if (nsubstitutes < min_n_opers)
+	    min_n_opers = nsubstitutes;
+	  else if (nsubstitutes > max_n_opers)
+	    max_n_opers = nsubstitutes;
+	}
+    }
+
+  unsigned n_ids = user_ids.length ();
+  if (n_ids == 0)
+    fatal_at (token, "for requires at least one user-defined identifier");
+
+  token = peek ();
+  if (token->type == CPP_CLOSE_PAREN)
+    fatal_at (token, "no pattern defined in for");
+
+  active_fors.safe_push (user_ids);
+  while (1)
+    {
+      token = peek ();
+      if (token->type == CPP_CLOSE_PAREN)
+ 	break;
+      parse_pattern ();
+    }
+  active_fors.pop ();
+
+  /* Remove user-defined operators from the hash again.  */
+  for (unsigned i = 0; i < user_ids.length (); ++i)
+    operators->remove_elt (user_ids[i]);
+}
+
+/* Parse an outer if expression.
+     if = '(' 'if' '(' <c-expr> ')' <pattern> ')'  */
+
+void
+parser::parse_if (source_location loc)
+{
+  operand *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
+
+  const cpp_token *token = peek ();
+  if (token->type == CPP_CLOSE_PAREN)
+    fatal_at (token, "no pattern defined in if");
+
+  active_ifs.safe_push (if_or_with (ifexpr, loc, false));
+  while (1)
+    {
+      const cpp_token *token = peek ();
+      if (token->type == CPP_CLOSE_PAREN)
+	break;
+
+      parse_pattern ();
+    }
+  active_ifs.pop ();
+}
+
+/* Parse a list of predefined predicate identifiers.
+     preds = '(' 'define_predicates' <ident>... ')'  */
+
+void
+parser::parse_predicates (source_location)
+{
+  do
+    {
+      const cpp_token *token = peek ();
+      if (token->type != CPP_NAME)
+	break;
+
+      add_predicate (get_ident ());
+    }
+  while (1);
+}
+
+/* Parse outer control structures.
+     pattern = <preds>|<for>|<if>|<simplify>|<match>  */
+
+void
+parser::parse_pattern ()
+{
+  /* All clauses start with '('.  */
+  eat_token (CPP_OPEN_PAREN);
+  const cpp_token *token = peek ();
+  const char *id = get_ident ();
+  if (strcmp (id, "simplify") == 0)
+    parse_simplify (token->src_loc, simplifiers, NULL, NULL);
+  else if (strcmp (id, "match") == 0)
+    {
+      bool with_args = false;
+      if (peek ()->type == CPP_OPEN_PAREN)
+	{
+	  eat_token (CPP_OPEN_PAREN);
+	  with_args = true;
+	}
+      const char *name = get_ident ();
+      id_base *id = get_operator (name);
+      predicate_id *p;
+      if (!id)
+	{
+	  p = add_predicate (name);
+	  user_predicates.safe_push (p);
+	}
+      else if ((p = dyn_cast <predicate_id *> (id)))
+	;
+      else
+	fatal_at (token, "cannot add a match to a non-predicate ID");
+      /* Parse (match <id> <arg>... (match-expr)) here.  */
+      expr *e = NULL;
+      if (with_args)
+	{
+	  e = new expr (p);
+	  while (peek ()->type == CPP_ATSIGN)
+	    e->append_op (parse_capture (NULL));
+	  eat_token (CPP_CLOSE_PAREN);
+	}
+      if (p->nargs != -1
+	  && ((e && e->ops.length () != (unsigned)p->nargs)
+	      || (!e && p->nargs != 0)))
+	fatal_at (token, "non-matching number of match operands");
+      p->nargs = e ? e->ops.length () : 0;
+      parse_simplify (token->src_loc, p->matchers, p, e);
+    }
+  else if (strcmp (id, "for") == 0)
+    parse_for (token->src_loc);
+  else if (strcmp (id, "if") == 0)
+    parse_if (token->src_loc);
+  else if (strcmp (id, "define_predicates") == 0)
+    {
+      if (active_ifs.length () > 0
+	  || active_fors.length () > 0)
+	fatal_at (token, "define_predicates inside if or for is not supported");
+      parse_predicates (token->src_loc);
+    }
+  else
+    fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
+	      active_ifs.length () == 0 && active_fors.length () == 0
+	      ? "'define_predicates', " : "");
+
+  eat_token (CPP_CLOSE_PAREN);
+}
+
+/* Main entry of the parser.  Repeatedly parse outer control structures.  */
+
+parser::parser (cpp_reader *r_)
+{
+  r = r_;
+  active_ifs = vNULL;
+  active_fors = vNULL;
+  simplifiers = vNULL;
+  user_predicates = vNULL;
+
+  const cpp_token *token = next ();
+  while (token->type != CPP_EOF)
+    {
+      _cpp_backup_tokens (r, 1);
+      parse_pattern ();
+      token = next ();
+    }
+}
+
+
+/* Helper for the linemap code.  */
+
+static size_t
+round_alloc_size (size_t s)
+{
+  return s;
+}
+
+
+/* The genmatch generator progam.  It reads from a pattern description
+   and outputs GIMPLE or GENERIC IL matching and simplification routines.  */
+
+int
+main (int argc, char **argv)
+{
+  cpp_reader *r;
+
+  progname = "genmatch";
+
+  if (argc < 2)
+    return 1;
+
+  bool gimple = true;
+  bool verbose = false;
+  char *input = argv[argc-1];
+  for (int i = 1; i < argc - 1; ++i)
+    {
+      if (strcmp (argv[i], "--gimple") == 0)
+	gimple = true;
+      else if (strcmp (argv[i], "--generic") == 0)
+	gimple = false;
+      else if (strcmp (argv[i], "-v") == 0)
+	verbose = true;
+      else
+	{
+	  fprintf (stderr, "Usage: genmatch "
+		   "[--gimple] [--generic] [-v] input\n");
+	  return 1;
+	}
+    }
+
+  line_table = XCNEW (struct line_maps);
+  linemap_init (line_table, 0);
+  line_table->reallocator = xrealloc;
+  line_table->round_alloc_size = round_alloc_size;
+
+  r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
+  cpp_callbacks *cb = cpp_get_callbacks (r);
+  cb->error = error_cb;
+
+  if (!cpp_read_main_file (r, input))
+    return 1;
+  cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
+  cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
+
+  /* Pre-seed operators.  */
+  operators = new hash_table<id_base> (1024);
+#define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
+  add_operator (SYM, # SYM, # TYPE, NARGS);
+#define END_OF_BASE_TREE_CODES
+#include "tree.def"
+add_operator (CONVERT0, "CONVERT0", "tcc_unary", 1);
+add_operator (CONVERT1, "CONVERT1", "tcc_unary", 1);
+add_operator (CONVERT2, "CONVERT2", "tcc_unary", 1);
+#undef END_OF_BASE_TREE_CODES
+#undef DEFTREECODE
+
+  /* Pre-seed builtin functions.
+     ???  Cannot use N (name) as that is targetm.emultls.get_address
+     for BUILT_IN_EMUTLS_GET_ADDRESS ... */
+#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
+  add_builtin (ENUM, # ENUM);
+#include "builtins.def"
+#undef DEF_BUILTIN
+
+  /* Parse ahead!  */
+  parser p (r);
+
+  if (gimple)
+    write_header (stdout, "gimple-match-head.c");
+  else
+    write_header (stdout, "generic-match-head.c");
+
+  /* Go over all predicates defined with patterns and perform
+     lowering and code generation.  */
+  for (unsigned i = 0; i < p.user_predicates.length (); ++i)
+    {
+      predicate_id *pred = p.user_predicates[i];
+      lower (pred->matchers);
+
+      if (verbose)
+	for (unsigned i = 0; i < pred->matchers.length (); ++i)
+	  print_matches (pred->matchers[i]);
+
+      decision_tree dt;
+      for (unsigned i = 0; i < pred->matchers.length (); ++i)
+	dt.insert (pred->matchers[i], i);
+
+      if (verbose)
+	dt.print (stderr);
+
+      write_predicate (stdout, pred, dt, gimple);
+    }
+
+  /* Lower the main simplifiers and generate code for them.  */
+  lower (p.simplifiers);
+
+  if (verbose)
+    for (unsigned i = 0; i < p.simplifiers.length (); ++i)
+      print_matches (p.simplifiers[i]);
+
+  decision_tree dt;
+  for (unsigned i = 0; i < p.simplifiers.length (); ++i)
+    dt.insert (p.simplifiers[i], i);
+
+  if (verbose)
+    dt.print (stderr);
+
+  if (gimple)
+    dt.gen_gimple (stdout);
+  else
+    dt.gen_generic (stdout);
+
+  /* Finalize.  */
+  cpp_finish (r, NULL);
+  cpp_destroy (r);
+
+  delete operators;
+
+  return 0;
+}