Initial checkin of GCC 4.9.0 from trunk (r208799).

Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba

1 files changed, 2694 insertions, 0 deletions

diff --git a/gcc-4.9/gcc/genrecog.c b/gcc-4.9/gcc/genrecog.c
new file mode 100644
index 000000000..a7949e815
--- /dev/null
+++ b/gcc-4.9/gcc/genrecog.c
@@ -0,0 +1,2694 @@
+/* Generate code from machine description to recognize rtl as insns.
+   Copyright (C) 1987-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/>.  */
+
+
+/* This program is used to produce insn-recog.c, which contains a
+   function called `recog' plus its subroutines.  These functions
+   contain a decision tree that recognizes whether an rtx, the
+   argument given to recog, is a valid instruction.
+
+   recog returns -1 if the rtx is not valid.  If the rtx is valid,
+   recog returns a nonnegative number which is the insn code number
+   for the pattern that matched.  This is the same as the order in the
+   machine description of the entry that matched.  This number can be
+   used as an index into various insn_* tables, such as insn_template,
+   insn_outfun, and insn_n_operands (found in insn-output.c).
+
+   The third argument to recog is an optional pointer to an int.  If
+   present, recog will accept a pattern if it matches except for
+   missing CLOBBER expressions at the end.  In that case, the value
+   pointed to by the optional pointer will be set to the number of
+   CLOBBERs that need to be added (it should be initialized to zero by
+   the caller).  If it is set nonzero, the caller should allocate a
+   PARALLEL of the appropriate size, copy the initial entries, and
+   call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
+
+   This program also generates the function `split_insns', which
+   returns 0 if the rtl could not be split, or it returns the split
+   rtl as an INSN list.
+
+   This program also generates the function `peephole2_insns', which
+   returns 0 if the rtl could not be matched.  If there was a match,
+   the new rtl is returned in an INSN list, and LAST_INSN will point
+   to the last recognized insn in the old sequence.  */
+
+#include "bconfig.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "errors.h"
+#include "read-md.h"
+#include "gensupport.h"
+
+#define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
+  printf ("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
+
+/* Ways of obtaining an rtx to be tested.  */
+enum position_type {
+  /* PATTERN (peep2_next_insn (ARG)).  */
+  POS_PEEP2_INSN,
+
+  /* XEXP (BASE, ARG).  */
+  POS_XEXP,
+
+  /* XVECEXP (BASE, 0, ARG).  */
+  POS_XVECEXP0
+};
+
+/* The position of an rtx relative to X0.  Each useful position is
+   represented by exactly one instance of this structure.  */
+struct position
+{
+  /* The parent rtx.  This is the root position for POS_PEEP2_INSNs.  */
+  struct position *base;
+
+  /* A position with the same BASE and TYPE, but with the next value
+     of ARG.  */
+  struct position *next;
+
+  /* A list of all POS_XEXP positions that use this one as their base,
+     chained by NEXT fields.  The first entry represents XEXP (this, 0),
+     the second represents XEXP (this, 1), and so on.  */
+  struct position *xexps;
+
+  /* A list of POS_XVECEXP0 positions that use this one as their base,
+     chained by NEXT fields.  The first entry represents XVECEXP (this, 0, 0),
+     the second represents XVECEXP (this, 0, 1), and so on.  */
+  struct position *xvecexp0s;
+
+  /* The type of position.  */
+  enum position_type type;
+
+  /* The argument to TYPE (shown as ARG in the position_type comments).  */
+  int arg;
+
+  /* The depth of this position, with 0 as the root.  */
+  int depth;
+};
+
+/* A listhead of decision trees.  The alternatives to a node are kept
+   in a doubly-linked list so we can easily add nodes to the proper
+   place when merging.  */
+
+struct decision_head
+{
+  struct decision *first;
+  struct decision *last;
+};
+
+/* These types are roughly in the order in which we'd like to test them.  */
+enum decision_type
+{
+  DT_num_insns,
+  DT_mode, DT_code, DT_veclen,
+  DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
+  DT_const_int,
+  DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
+  DT_accept_op, DT_accept_insn
+};
+
+/* A single test.  The two accept types aren't tests per-se, but
+   their equality (or lack thereof) does affect tree merging so
+   it is convenient to keep them here.  */
+
+struct decision_test
+{
+  /* A linked list through the tests attached to a node.  */
+  struct decision_test *next;
+
+  enum decision_type type;
+
+  union
+  {
+    int num_insns;		/* Number if insn in a define_peephole2.  */
+    enum machine_mode mode;	/* Machine mode of node.  */
+    RTX_CODE code;		/* Code to test.  */
+
+    struct
+    {
+      const char *name;		/* Predicate to call.  */
+      const struct pred_data *data;
+                                /* Optimization hints for this predicate.  */
+      enum machine_mode mode;	/* Machine mode for node.  */
+    } pred;
+
+    const char *c_test;		/* Additional test to perform.  */
+    int veclen;			/* Length of vector.  */
+    int dup;			/* Number of operand to compare against.  */
+    HOST_WIDE_INT intval;	/* Value for XINT for XWINT.  */
+    int opno;			/* Operand number matched.  */
+
+    struct {
+      int code_number;		/* Insn number matched.  */
+      int lineno;		/* Line number of the insn.  */
+      int num_clobbers_to_add;	/* Number of CLOBBERs to be added.  */
+    } insn;
+  } u;
+};
+
+/* Data structure for decision tree for recognizing legitimate insns.  */
+
+struct decision
+{
+  struct decision_head success;	/* Nodes to test on success.  */
+  struct decision *next;	/* Node to test on failure.  */
+  struct decision *prev;	/* Node whose failure tests us.  */
+  struct decision *afterward;	/* Node to test on success,
+				   but failure of successor nodes.  */
+
+  struct position *position;	/* Position in pattern.  */
+
+  struct decision_test *tests;	/* The tests for this node.  */
+
+  int number;			/* Node number, used for labels */
+  int subroutine_number;	/* Number of subroutine this node starts */
+  int need_label;		/* Label needs to be output.  */
+};
+
+#define SUBROUTINE_THRESHOLD	100
+
+static int next_subroutine_number;
+
+/* We can write three types of subroutines: One for insn recognition,
+   one to split insns, and one for peephole-type optimizations.  This
+   defines which type is being written.  */
+
+enum routine_type {
+  RECOG, SPLIT, PEEPHOLE2
+};
+
+#define IS_SPLIT(X) ((X) != RECOG)
+
+/* Next available node number for tree nodes.  */
+
+static int next_number;
+
+/* Next number to use as an insn_code.  */
+
+static int next_insn_code;
+
+/* Record the highest depth we ever have so we know how many variables to
+   allocate in each subroutine we make.  */
+
+static int max_depth;
+
+/* The line number of the start of the pattern currently being processed.  */
+static int pattern_lineno;
+
+/* The root position (x0).  */
+static struct position root_pos;
+
+/* A list of all POS_PEEP2_INSNs.  The entry for insn 0 is the root position,
+   since we are given that instruction's pattern as x0.  */
+static struct position *peep2_insn_pos_list = &root_pos;
+
+extern void debug_decision
+  (struct decision *);
+extern void debug_decision_list
+  (struct decision *);
+
+/* Return a position with the given BASE, TYPE and ARG.  NEXT_PTR
+   points to where the unique object that represents the position
+   should be stored.  Create the object if it doesn't already exist,
+   otherwise reuse the object that is already there.  */
+
+static struct position *
+next_position (struct position **next_ptr, struct position *base,
+	       enum position_type type, int arg)
+{
+  struct position *pos;
+
+  pos = *next_ptr;
+  if (!pos)
+    {
+      pos = XCNEW (struct position);
+      pos->base = base;
+      pos->type = type;
+      pos->arg = arg;
+      pos->depth = base->depth + 1;
+      *next_ptr = pos;
+    }
+  return pos;
+}
+
+/* Compare positions POS1 and POS2 lexicographically.  */
+
+static int
+compare_positions (struct position *pos1, struct position *pos2)
+{
+  int diff;
+
+  diff = pos1->depth - pos2->depth;
+  if (diff < 0)
+    do
+      pos2 = pos2->base;
+    while (pos1->depth != pos2->depth);
+  else if (diff > 0)
+    do
+      pos1 = pos1->base;
+    while (pos1->depth != pos2->depth);
+  while (pos1 != pos2)
+    {
+      diff = (int) pos1->type - (int) pos2->type;
+      if (diff == 0)
+	diff = pos1->arg - pos2->arg;
+      pos1 = pos1->base;
+      pos2 = pos2->base;
+    }
+  return diff;
+}
+
+/* Create a new node in sequence after LAST.  */
+
+static struct decision *
+new_decision (struct position *pos, struct decision_head *last)
+{
+  struct decision *new_decision = XCNEW (struct decision);
+
+  new_decision->success = *last;
+  new_decision->position = pos;
+  new_decision->number = next_number++;
+
+  last->first = last->last = new_decision;
+  return new_decision;
+}
+
+/* Create a new test and link it in at PLACE.  */
+
+static struct decision_test *
+new_decision_test (enum decision_type type, struct decision_test ***pplace)
+{
+  struct decision_test **place = *pplace;
+  struct decision_test *test;
+
+  test = XNEW (struct decision_test);
+  test->next = *place;
+  test->type = type;
+  *place = test;
+
+  place = &test->next;
+  *pplace = place;
+
+  return test;
+}
+
+/* Search for and return operand N, stop when reaching node STOP.  */
+
+static rtx
+find_operand (rtx pattern, int n, rtx stop)
+{
+  const char *fmt;
+  RTX_CODE code;
+  int i, j, len;
+  rtx r;
+
+  if (pattern == stop)
+    return stop;
+
+  code = GET_CODE (pattern);
+  if ((code == MATCH_SCRATCH
+       || code == MATCH_OPERAND
+       || code == MATCH_OPERATOR
+       || code == MATCH_PARALLEL)
+      && XINT (pattern, 0) == n)
+    return pattern;
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
+	    return r;
+	  break;
+
+	case 'V':
+	  if (! XVEC (pattern, i))
+	    break;
+	  /* Fall through.  */
+
+	case 'E':
+	  for (j = 0; j < XVECLEN (pattern, i); j++)
+	    if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
+		!= NULL_RTX)
+	      return r;
+	  break;
+
+	case 'i': case 'w': case '0': case 's':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return NULL;
+}
+
+/* Search for and return operand M, such that it has a matching
+   constraint for operand N.  */
+
+static rtx
+find_matching_operand (rtx pattern, int n)
+{
+  const char *fmt;
+  RTX_CODE code;
+  int i, j, len;
+  rtx r;
+
+  code = GET_CODE (pattern);
+  if (code == MATCH_OPERAND
+      && (XSTR (pattern, 2)[0] == '0' + n
+	  || (XSTR (pattern, 2)[0] == '%'
+	      && XSTR (pattern, 2)[1] == '0' + n)))
+    return pattern;
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if ((r = find_matching_operand (XEXP (pattern, i), n)))
+	    return r;
+	  break;
+
+	case 'V':
+	  if (! XVEC (pattern, i))
+	    break;
+	  /* Fall through.  */
+
+	case 'E':
+	  for (j = 0; j < XVECLEN (pattern, i); j++)
+	    if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
+	      return r;
+	  break;
+
+	case 'i': case 'w': case '0': case 's':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return NULL;
+}
+
+
+/* Check for various errors in patterns.  SET is nonnull for a destination,
+   and is the complete set pattern.  SET_CODE is '=' for normal sets, and
+   '+' within a context that requires in-out constraints.  */
+
+static void
+validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
+{
+  const char *fmt;
+  RTX_CODE code;
+  size_t i, len;
+  int j;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_SCRATCH:
+      return;
+    case MATCH_DUP:
+    case MATCH_OP_DUP:
+    case MATCH_PAR_DUP:
+      if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
+	error_with_line (pattern_lineno,
+			 "operand %i duplicated before defined",
+			 XINT (pattern, 0));
+      break;
+    case MATCH_OPERAND:
+    case MATCH_OPERATOR:
+      {
+	const char *pred_name = XSTR (pattern, 1);
+	const struct pred_data *pred;
+	const char *c_test;
+
+	if (GET_CODE (insn) == DEFINE_INSN)
+	  c_test = XSTR (insn, 2);
+	else
+	  c_test = XSTR (insn, 1);
+
+	if (pred_name[0] != 0)
+	  {
+	    pred = lookup_predicate (pred_name);
+	    if (!pred)
+	      error_with_line (pattern_lineno, "unknown predicate '%s'",
+			       pred_name);
+	  }
+	else
+	  pred = 0;
+
+	if (code == MATCH_OPERAND)
+	  {
+	    const char constraints0 = XSTR (pattern, 2)[0];
+
+	    /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
+	       don't use the MATCH_OPERAND constraint, only the predicate.
+	       This is confusing to folks doing new ports, so help them
+	       not make the mistake.  */
+	    if (GET_CODE (insn) == DEFINE_EXPAND
+		|| GET_CODE (insn) == DEFINE_SPLIT
+		|| GET_CODE (insn) == DEFINE_PEEPHOLE2)
+	      {
+		if (constraints0)
+		  error_with_line (pattern_lineno,
+				   "constraints not supported in %s",
+				   rtx_name[GET_CODE (insn)]);
+	      }
+
+	    /* A MATCH_OPERAND that is a SET should have an output reload.  */
+	    else if (set && constraints0)
+	      {
+		if (set_code == '+')
+		  {
+		    if (constraints0 == '+')
+		      ;
+		    /* If we've only got an output reload for this operand,
+		       we'd better have a matching input operand.  */
+		    else if (constraints0 == '='
+			     && find_matching_operand (insn, XINT (pattern, 0)))
+		      ;
+		    else
+		      error_with_line (pattern_lineno,
+				       "operand %d missing in-out reload",
+				       XINT (pattern, 0));
+		  }
+		else if (constraints0 != '=' && constraints0 != '+')
+		  error_with_line (pattern_lineno,
+				   "operand %d missing output reload",
+				   XINT (pattern, 0));
+	      }
+	  }
+
+	/* Allowing non-lvalues in destinations -- particularly CONST_INT --
+	   while not likely to occur at runtime, results in less efficient
+	   code from insn-recog.c.  */
+	if (set && pred && pred->allows_non_lvalue)
+	  error_with_line (pattern_lineno,
+			   "destination operand %d allows non-lvalue",
+			   XINT (pattern, 0));
+
+	/* A modeless MATCH_OPERAND can be handy when we can check for
+	   multiple modes in the c_test.  In most other cases, it is a
+	   mistake.  Only DEFINE_INSN is eligible, since SPLIT and
+	   PEEP2 can FAIL within the output pattern.  Exclude special
+	   predicates, which check the mode themselves.  Also exclude
+	   predicates that allow only constants.  Exclude the SET_DEST
+	   of a call instruction, as that is a common idiom.  */
+
+	if (GET_MODE (pattern) == VOIDmode
+	    && code == MATCH_OPERAND
+	    && GET_CODE (insn) == DEFINE_INSN
+	    && pred
+	    && !pred->special
+	    && pred->allows_non_const
+	    && strstr (c_test, "operands") == NULL
+	    && ! (set
+		  && GET_CODE (set) == SET
+		  && GET_CODE (SET_SRC (set)) == CALL))
+	  message_with_line (pattern_lineno,
+			     "warning: operand %d missing mode?",
+			     XINT (pattern, 0));
+	return;
+      }
+
+    case SET:
+      {
+	enum machine_mode dmode, smode;
+	rtx dest, src;
+
+	dest = SET_DEST (pattern);
+	src = SET_SRC (pattern);
+
+	/* STRICT_LOW_PART is a wrapper.  Its argument is the real
+	   destination, and it's mode should match the source.  */
+	if (GET_CODE (dest) == STRICT_LOW_PART)
+	  dest = XEXP (dest, 0);
+
+	/* Find the referent for a DUP.  */
+
+	if (GET_CODE (dest) == MATCH_DUP
+	    || GET_CODE (dest) == MATCH_OP_DUP
+	    || GET_CODE (dest) == MATCH_PAR_DUP)
+	  dest = find_operand (insn, XINT (dest, 0), NULL);
+
+	if (GET_CODE (src) == MATCH_DUP
+	    || GET_CODE (src) == MATCH_OP_DUP
+	    || GET_CODE (src) == MATCH_PAR_DUP)
+	  src = find_operand (insn, XINT (src, 0), NULL);
+
+	dmode = GET_MODE (dest);
+	smode = GET_MODE (src);
+
+	/* The mode of an ADDRESS_OPERAND is the mode of the memory
+	   reference, not the mode of the address.  */
+	if (GET_CODE (src) == MATCH_OPERAND
+	    && ! strcmp (XSTR (src, 1), "address_operand"))
+	  ;
+
+        /* The operands of a SET must have the same mode unless one
+	   is VOIDmode.  */
+        else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
+	  error_with_line (pattern_lineno,
+			   "mode mismatch in set: %smode vs %smode",
+			   GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
+
+	/* If only one of the operands is VOIDmode, and PC or CC0 is
+	   not involved, it's probably a mistake.  */
+	else if (dmode != smode
+		 && GET_CODE (dest) != PC
+		 && GET_CODE (dest) != CC0
+		 && GET_CODE (src) != PC
+		 && GET_CODE (src) != CC0
+		 && !CONST_INT_P (src)
+		 && GET_CODE (src) != CALL)
+	  {
+	    const char *which;
+	    which = (dmode == VOIDmode ? "destination" : "source");
+	    message_with_line (pattern_lineno,
+			       "warning: %s missing a mode?", which);
+	  }
+
+	if (dest != SET_DEST (pattern))
+	  validate_pattern (dest, insn, pattern, '=');
+	validate_pattern (SET_DEST (pattern), insn, pattern, '=');
+        validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
+        return;
+      }
+
+    case CLOBBER:
+      validate_pattern (SET_DEST (pattern), insn, pattern, '=');
+      return;
+
+    case ZERO_EXTRACT:
+      validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
+      validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
+      validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
+      return;
+
+    case STRICT_LOW_PART:
+      validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
+      return;
+
+    case LABEL_REF:
+      if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
+	error_with_line (pattern_lineno,
+			 "operand to label_ref %smode not VOIDmode",
+			 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
+	  break;
+
+	case 'E':
+	  for (j = 0; j < XVECLEN (pattern, i); j++)
+	    validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
+	  break;
+
+	case 'i': case 'w': case '0': case 's':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+}
+
+/* Create a chain of nodes to verify that an rtl expression matches
+   PATTERN.
+
+   LAST is a pointer to the listhead in the previous node in the chain (or
+   in the calling function, for the first node).
+
+   POSITION is the current position in the insn.
+
+   INSN_TYPE is the type of insn for which we are emitting code.
+
+   A pointer to the final node in the chain is returned.  */
+
+static struct decision *
+add_to_sequence (rtx pattern, struct decision_head *last,
+		 struct position *pos, enum routine_type insn_type, int top)
+{
+  RTX_CODE code;
+  struct decision *this_decision, *sub;
+  struct decision_test *test;
+  struct decision_test **place;
+  struct position *subpos, **subpos_ptr;
+  size_t i;
+  const char *fmt;
+  int len;
+  enum machine_mode mode;
+  enum position_type pos_type;
+
+  if (pos->depth > max_depth)
+    max_depth = pos->depth;
+
+  sub = this_decision = new_decision (pos, last);
+  place = &this_decision->tests;
+
+  mode = GET_MODE (pattern);
+  code = GET_CODE (pattern);
+
+  switch (code)
+    {
+    case PARALLEL:
+      /* Toplevel peephole pattern.  */
+      if (insn_type == PEEPHOLE2 && top)
+	{
+	  int num_insns;
+
+	  /* Check we have sufficient insns.  This avoids complications
+	     because we then know peep2_next_insn never fails.  */
+	  num_insns = XVECLEN (pattern, 0);
+	  if (num_insns > 1)
+	    {
+	      test = new_decision_test (DT_num_insns, &place);
+	      test->u.num_insns = num_insns;
+	      last = &sub->success;
+	    }
+	  else
+	    {
+	      /* We don't need the node we just created -- unlink it.  */
+	      last->first = last->last = NULL;
+	    }
+
+	  subpos_ptr = &peep2_insn_pos_list;
+	  for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
+	    {
+	      subpos = next_position (subpos_ptr, &root_pos,
+				      POS_PEEP2_INSN, i);
+	      sub = add_to_sequence (XVECEXP (pattern, 0, i),
+				     last, subpos, insn_type, 0);
+	      last = &sub->success;
+	      subpos_ptr = &subpos->next;
+	    }
+	  goto ret;
+	}
+
+      /* Else nothing special.  */
+      break;
+
+    case MATCH_PARALLEL:
+      /* The explicit patterns within a match_parallel enforce a minimum
+	 length on the vector.  The match_parallel predicate may allow
+	 for more elements.  We do need to check for this minimum here
+	 or the code generated to match the internals may reference data
+	 beyond the end of the vector.  */
+      test = new_decision_test (DT_veclen_ge, &place);
+      test->u.veclen = XVECLEN (pattern, 2);
+      /* Fall through.  */
+
+    case MATCH_OPERAND:
+    case MATCH_SCRATCH:
+    case MATCH_OPERATOR:
+      {
+	RTX_CODE was_code = code;
+	const char *pred_name;
+	bool allows_const_int = true;
+
+	if (code == MATCH_SCRATCH)
+	  {
+	    pred_name = "scratch_operand";
+	    code = UNKNOWN;
+	  }
+	else
+	  {
+	    pred_name = XSTR (pattern, 1);
+	    if (code == MATCH_PARALLEL)
+	      code = PARALLEL;
+	    else
+	      code = UNKNOWN;
+	  }
+
+	if (pred_name[0] != 0)
+	  {
+	    const struct pred_data *pred;
+
+	    test = new_decision_test (DT_pred, &place);
+	    test->u.pred.name = pred_name;
+	    test->u.pred.mode = mode;
+
+	    /* See if we know about this predicate.
+	       If we do, remember it for use below.
+
+	       We can optimize the generated code a little if either
+	       (a) the predicate only accepts one code, or (b) the
+	       predicate does not allow CONST_INT, in which case it
+	       can match only if the modes match.  */
+	    pred = lookup_predicate (pred_name);
+	    if (pred)
+	      {
+		test->u.pred.data = pred;
+		allows_const_int = pred->codes[CONST_INT];
+		if (was_code == MATCH_PARALLEL
+		    && pred->singleton != PARALLEL)
+		  error_with_line (pattern_lineno,
+				   "predicate '%s' used in match_parallel "
+				   "does not allow only PARALLEL", pred->name);
+		else
+		  code = pred->singleton;
+	      }
+	    else
+	      error_with_line (pattern_lineno,
+			       "unknown predicate '%s' in '%s' expression",
+			       pred_name, GET_RTX_NAME (was_code));
+	  }
+
+	/* Can't enforce a mode if we allow const_int.  */
+	if (allows_const_int)
+	  mode = VOIDmode;
+
+	/* Accept the operand, i.e. record it in `operands'.  */
+	test = new_decision_test (DT_accept_op, &place);
+	test->u.opno = XINT (pattern, 0);
+
+	if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
+	  {
+	    if (was_code == MATCH_OPERATOR)
+	      {
+		pos_type = POS_XEXP;
+		subpos_ptr = &pos->xexps;
+	      }
+	    else
+	      {
+		pos_type = POS_XVECEXP0;
+		subpos_ptr = &pos->xvecexp0s;
+	      }
+	    for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
+	      {
+		subpos = next_position (subpos_ptr, pos, pos_type, i);
+		sub = add_to_sequence (XVECEXP (pattern, 2, i),
+				       &sub->success, subpos, insn_type, 0);
+		subpos_ptr = &subpos->next;
+	      }
+	  }
+	goto fini;
+      }
+
+    case MATCH_OP_DUP:
+      code = UNKNOWN;
+
+      test = new_decision_test (DT_dup, &place);
+      test->u.dup = XINT (pattern, 0);
+
+      test = new_decision_test (DT_accept_op, &place);
+      test->u.opno = XINT (pattern, 0);
+
+      subpos_ptr = &pos->xexps;
+      for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
+	{
+	  subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
+	  sub = add_to_sequence (XVECEXP (pattern, 1, i),
+				 &sub->success, subpos, insn_type, 0);
+	  subpos_ptr = &subpos->next;
+	}
+      goto fini;
+
+    case MATCH_DUP:
+    case MATCH_PAR_DUP:
+      code = UNKNOWN;
+
+      test = new_decision_test (DT_dup, &place);
+      test->u.dup = XINT (pattern, 0);
+      goto fini;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+
+  /* Do tests against the current node first.  */
+  for (i = 0; i < (size_t) len; i++)
+    {
+      if (fmt[i] == 'i')
+	{
+	  gcc_assert (i < 2);
+
+	  if (!i)
+	    {
+	      test = new_decision_test (DT_elt_zero_int, &place);
+	      test->u.intval = XINT (pattern, i);
+	    }
+	  else
+	    {
+	      test = new_decision_test (DT_elt_one_int, &place);
+	      test->u.intval = XINT (pattern, i);
+	    }
+	}
+      else if (fmt[i] == 'w')
+	{
+	  /* If this value actually fits in an int, we can use a switch
+	     statement here, so indicate that.  */
+	  enum decision_type type
+	    = ((int) XWINT (pattern, i) == XWINT (pattern, i))
+	      ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
+
+	  gcc_assert (!i);
+
+	  test = new_decision_test (type, &place);
+	  test->u.intval = XWINT (pattern, i);
+	}
+      else if (fmt[i] == 'E')
+	{
+	  gcc_assert (!i);
+
+	  test = new_decision_test (DT_veclen, &place);
+	  test->u.veclen = XVECLEN (pattern, i);
+	}
+    }
+
+  /* Now test our sub-patterns.  */
+  subpos_ptr = &pos->xexps;
+  for (i = 0; i < (size_t) len; i++)
+    {
+      subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  sub = add_to_sequence (XEXP (pattern, i), &sub->success,
+				 subpos, insn_type, 0);
+	  break;
+
+	case 'E':
+	  {
+	    struct position *subpos2, **subpos2_ptr;
+	    int j;
+
+	    subpos2_ptr = &pos->xvecexp0s;
+	    for (j = 0; j < XVECLEN (pattern, i); j++)
+	      {
+		subpos2 = next_position (subpos2_ptr, pos, POS_XVECEXP0, j);
+		sub = add_to_sequence (XVECEXP (pattern, i, j),
+				       &sub->success, subpos2, insn_type, 0);
+		subpos2_ptr = &subpos2->next;
+	      }
+	    break;
+	  }
+
+	case 'i': case 'w':
+	  /* Handled above.  */
+	  break;
+	case '0':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+      subpos_ptr = &subpos->next;
+    }
+
+ fini:
+  /* Insert nodes testing mode and code, if they're still relevant,
+     before any of the nodes we may have added above.  */
+  if (code != UNKNOWN)
+    {
+      place = &this_decision->tests;
+      test = new_decision_test (DT_code, &place);
+      test->u.code = code;
+    }
+
+  if (mode != VOIDmode)
+    {
+      place = &this_decision->tests;
+      test = new_decision_test (DT_mode, &place);
+      test->u.mode = mode;
+    }
+
+  /* If we didn't insert any tests or accept nodes, hork.  */
+  gcc_assert (this_decision->tests);
+
+ ret:
+  return sub;
+}
+
+/* A subroutine of maybe_both_true; examines only one test.
+   Returns > 0 for "definitely both true" and < 0 for "maybe both true".  */
+
+static int
+maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
+{
+  if (d1->type == d2->type)
+    {
+      switch (d1->type)
+	{
+	case DT_num_insns:
+	  if (d1->u.num_insns == d2->u.num_insns)
+	    return 1;
+	  else
+	    return -1;
+
+	case DT_mode:
+	  return d1->u.mode == d2->u.mode;
+
+	case DT_code:
+	  return d1->u.code == d2->u.code;
+
+	case DT_veclen:
+	  return d1->u.veclen == d2->u.veclen;
+
+	case DT_elt_zero_int:
+	case DT_elt_one_int:
+	case DT_elt_zero_wide:
+	case DT_elt_zero_wide_safe:
+	  return d1->u.intval == d2->u.intval;
+
+	default:
+	  break;
+	}
+    }
+
+  /* If either has a predicate that we know something about, set
+     things up so that D1 is the one that always has a known
+     predicate.  Then see if they have any codes in common.  */
+
+  if (d1->type == DT_pred || d2->type == DT_pred)
+    {
+      if (d2->type == DT_pred)
+	{
+	  struct decision_test *tmp;
+	  tmp = d1, d1 = d2, d2 = tmp;
+	}
+
+      /* If D2 tests a mode, see if it matches D1.  */
+      if (d1->u.pred.mode != VOIDmode)
+	{
+	  if (d2->type == DT_mode)
+	    {
+	      if (d1->u.pred.mode != d2->u.mode
+		  /* The mode of an address_operand predicate is the
+		     mode of the memory, not the operand.  It can only
+		     be used for testing the predicate, so we must
+		     ignore it here.  */
+		  && strcmp (d1->u.pred.name, "address_operand") != 0)
+		return 0;
+	    }
+	  /* Don't check two predicate modes here, because if both predicates
+	     accept CONST_INT, then both can still be true even if the modes
+	     are different.  If they don't accept CONST_INT, there will be a
+	     separate DT_mode that will make maybe_both_true_1 return 0.  */
+	}
+
+      if (d1->u.pred.data)
+	{
+	  /* If D2 tests a code, see if it is in the list of valid
+	     codes for D1's predicate.  */
+	  if (d2->type == DT_code)
+	    {
+	      if (!d1->u.pred.data->codes[d2->u.code])
+		return 0;
+	    }
+
+	  /* Otherwise see if the predicates have any codes in common.  */
+	  else if (d2->type == DT_pred && d2->u.pred.data)
+	    {
+	      bool common = false;
+	      int c;
+
+	      for (c = 0; c < NUM_RTX_CODE; c++)
+		if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c])
+		  {
+		    common = true;
+		    break;
+		  }
+
+	      if (!common)
+		return 0;
+	    }
+	}
+    }
+
+  /* Tests vs veclen may be known when strict equality is involved.  */
+  if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
+    return d1->u.veclen >= d2->u.veclen;
+  if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
+    return d2->u.veclen >= d1->u.veclen;
+
+  return -1;
+}
+
+/* A subroutine of maybe_both_true; examines all the tests for a given node.
+   Returns > 0 for "definitely both true" and < 0 for "maybe both true".  */
+
+static int
+maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
+{
+  struct decision_test *t1, *t2;
+
+  /* A match_operand with no predicate can match anything.  Recognize
+     this by the existence of a lone DT_accept_op test.  */
+  if (d1->type == DT_accept_op || d2->type == DT_accept_op)
+    return 1;
+
+  /* Eliminate pairs of tests while they can exactly match.  */
+  while (d1 && d2 && d1->type == d2->type)
+    {
+      if (maybe_both_true_2 (d1, d2) == 0)
+	return 0;
+      d1 = d1->next, d2 = d2->next;
+    }
+
+  /* After that, consider all pairs.  */
+  for (t1 = d1; t1 ; t1 = t1->next)
+    for (t2 = d2; t2 ; t2 = t2->next)
+      if (maybe_both_true_2 (t1, t2) == 0)
+	return 0;
+
+  return -1;
+}
+
+/* Return 0 if we can prove that there is no RTL that can match both
+   D1 and D2.  Otherwise, return 1 (it may be that there is an RTL that
+   can match both or just that we couldn't prove there wasn't such an RTL).
+
+   TOPLEVEL is nonzero if we are to only look at the top level and not
+   recursively descend.  */
+
+static int
+maybe_both_true (struct decision *d1, struct decision *d2,
+		 int toplevel)
+{
+  struct decision *p1, *p2;
+  int cmp;
+
+  /* Don't compare strings on the different positions in insn.  Doing so
+     is incorrect and results in false matches from constructs like
+
+	[(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
+	      (subreg:HI (match_operand:SI "register_operand" "r") 0))]
+     vs
+	[(set (match_operand:HI "register_operand" "r")
+	      (match_operand:HI "register_operand" "r"))]
+
+     If we are presented with such, we are recursing through the remainder
+     of a node's success nodes (from the loop at the end of this function).
+     Skip forward until we come to a position that matches.
+
+     Due to the way positions are constructed, we know that iterating
+     forward from the lexically lower position will run into the lexically
+     higher position and not the other way around.  This saves a bit
+     of effort.  */
+
+  cmp = compare_positions (d1->position, d2->position);
+  if (cmp != 0)
+    {
+      gcc_assert (!toplevel);
+
+      /* If the d2->position was lexically lower, swap.  */
+      if (cmp > 0)
+	p1 = d1, d1 = d2, d2 = p1;
+
+      if (d1->success.first == 0)
+	return 1;
+      for (p1 = d1->success.first; p1; p1 = p1->next)
+	if (maybe_both_true (p1, d2, 0))
+	  return 1;
+
+      return 0;
+    }
+
+  /* Test the current level.  */
+  cmp = maybe_both_true_1 (d1->tests, d2->tests);
+  if (cmp >= 0)
+    return cmp;
+
+  /* We can't prove that D1 and D2 cannot both be true.  If we are only
+     to check the top level, return 1.  Otherwise, see if we can prove
+     that all choices in both successors are mutually exclusive.  If
+     either does not have any successors, we can't prove they can't both
+     be true.  */
+
+  if (toplevel || d1->success.first == 0 || d2->success.first == 0)
+    return 1;
+
+  for (p1 = d1->success.first; p1; p1 = p1->next)
+    for (p2 = d2->success.first; p2; p2 = p2->next)
+      if (maybe_both_true (p1, p2, 0))
+	return 1;
+
+  return 0;
+}
+
+/* A subroutine of nodes_identical.  Examine two tests for equivalence.  */
+
+static int
+nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
+{
+  switch (d1->type)
+    {
+    case DT_num_insns:
+      return d1->u.num_insns == d2->u.num_insns;
+
+    case DT_mode:
+      return d1->u.mode == d2->u.mode;
+
+    case DT_code:
+      return d1->u.code == d2->u.code;
+
+    case DT_pred:
+      return (d1->u.pred.mode == d2->u.pred.mode
+	      && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
+
+    case DT_c_test:
+      return strcmp (d1->u.c_test, d2->u.c_test) == 0;
+
+    case DT_veclen:
+    case DT_veclen_ge:
+      return d1->u.veclen == d2->u.veclen;
+
+    case DT_dup:
+      return d1->u.dup == d2->u.dup;
+
+    case DT_elt_zero_int:
+    case DT_elt_one_int:
+    case DT_elt_zero_wide:
+    case DT_elt_zero_wide_safe:
+      return d1->u.intval == d2->u.intval;
+
+    case DT_accept_op:
+      return d1->u.opno == d2->u.opno;
+
+    case DT_accept_insn:
+      /* Differences will be handled in merge_accept_insn.  */
+      return 1;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* True iff the two nodes are identical (on one level only).  Due
+   to the way these lists are constructed, we shouldn't have to
+   consider different orderings on the tests.  */
+
+static int
+nodes_identical (struct decision *d1, struct decision *d2)
+{
+  struct decision_test *t1, *t2;
+
+  for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
+    {
+      if (t1->type != t2->type)
+	return 0;
+      if (! nodes_identical_1 (t1, t2))
+	return 0;
+    }
+
+  /* For success, they should now both be null.  */
+  if (t1 != t2)
+    return 0;
+
+  /* Check that their subnodes are at the same position, as any one set
+     of sibling decisions must be at the same position.  Allowing this
+     requires complications to find_afterward and when change_state is
+     invoked.  */
+  if (d1->success.first
+      && d2->success.first
+      && d1->success.first->position != d2->success.first->position)
+    return 0;
+
+  return 1;
+}
+
+/* A subroutine of merge_trees; given two nodes that have been declared
+   identical, cope with two insn accept states.  If they differ in the
+   number of clobbers, then the conflict was created by make_insn_sequence
+   and we can drop the with-clobbers version on the floor.  If both
+   nodes have no additional clobbers, we have found an ambiguity in the
+   source machine description.  */
+
+static void
+merge_accept_insn (struct decision *oldd, struct decision *addd)
+{
+  struct decision_test *old, *add;
+
+  for (old = oldd->tests; old; old = old->next)
+    if (old->type == DT_accept_insn)
+      break;
+  if (old == NULL)
+    return;
+
+  for (add = addd->tests; add; add = add->next)
+    if (add->type == DT_accept_insn)
+      break;
+  if (add == NULL)
+    return;
+
+  /* If one node is for a normal insn and the second is for the base
+     insn with clobbers stripped off, the second node should be ignored.  */
+
+  if (old->u.insn.num_clobbers_to_add == 0
+      && add->u.insn.num_clobbers_to_add > 0)
+    {
+      /* Nothing to do here.  */
+    }
+  else if (old->u.insn.num_clobbers_to_add > 0
+	   && add->u.insn.num_clobbers_to_add == 0)
+    {
+      /* In this case, replace OLD with ADD.  */
+      old->u.insn = add->u.insn;
+    }
+  else
+    {
+      error_with_line (add->u.insn.lineno, "`%s' matches `%s'",
+		       get_insn_name (add->u.insn.code_number),
+		       get_insn_name (old->u.insn.code_number));
+      message_with_line (old->u.insn.lineno, "previous definition of `%s'",
+			 get_insn_name (old->u.insn.code_number));
+    }
+}
+
+/* Merge two decision trees OLDH and ADDH, modifying OLDH destructively.  */
+
+static void
+merge_trees (struct decision_head *oldh, struct decision_head *addh)
+{
+  struct decision *next, *add;
+
+  if (addh->first == 0)
+    return;
+  if (oldh->first == 0)
+    {
+      *oldh = *addh;
+      return;
+    }
+
+  /* Trying to merge bits at different positions isn't possible.  */
+  gcc_assert (oldh->first->position == addh->first->position);
+
+  for (add = addh->first; add ; add = next)
+    {
+      struct decision *old, *insert_before = NULL;
+
+      next = add->next;
+
+      /* The semantics of pattern matching state that the tests are
+	 done in the order given in the MD file so that if an insn
+	 matches two patterns, the first one will be used.  However,
+	 in practice, most, if not all, patterns are unambiguous so
+	 that their order is independent.  In that case, we can merge
+	 identical tests and group all similar modes and codes together.
+
+	 Scan starting from the end of OLDH until we reach a point
+	 where we reach the head of the list or where we pass a
+	 pattern that could also be true if NEW is true.  If we find
+	 an identical pattern, we can merge them.  Also, record the
+	 last node that tests the same code and mode and the last one
+	 that tests just the same mode.
+
+	 If we have no match, place NEW after the closest match we found.  */
+
+      for (old = oldh->last; old; old = old->prev)
+	{
+	  if (nodes_identical (old, add))
+	    {
+	      merge_accept_insn (old, add);
+	      merge_trees (&old->success, &add->success);
+	      goto merged_nodes;
+	    }
+
+	  if (maybe_both_true (old, add, 0))
+	    break;
+
+	  /* Insert the nodes in DT test type order, which is roughly
+	     how expensive/important the test is.  Given that the tests
+	     are also ordered within the list, examining the first is
+	     sufficient.  */
+	  if ((int) add->tests->type < (int) old->tests->type)
+	    insert_before = old;
+	}
+
+      if (insert_before == NULL)
+	{
+	  add->next = NULL;
+	  add->prev = oldh->last;
+	  oldh->last->next = add;
+	  oldh->last = add;
+	}
+      else
+	{
+	  if ((add->prev = insert_before->prev) != NULL)
+	    add->prev->next = add;
+	  else
+	    oldh->first = add;
+	  add->next = insert_before;
+	  insert_before->prev = add;
+	}
+
+    merged_nodes:;
+    }
+}
+
+/* Walk the tree looking for sub-nodes that perform common tests.
+   Factor out the common test into a new node.  This enables us
+   (depending on the test type) to emit switch statements later.  */
+
+static void
+factor_tests (struct decision_head *head)
+{
+  struct decision *first, *next;
+
+  for (first = head->first; first && first->next; first = next)
+    {
+      enum decision_type type;
+      struct decision *new_dec, *old_last;
+
+      type = first->tests->type;
+      next = first->next;
+
+      /* Want at least two compatible sequential nodes.  */
+      if (next->tests->type != type)
+	continue;
+
+      /* Don't want all node types, just those we can turn into
+	 switch statements.  */
+      if (type != DT_mode
+	  && type != DT_code
+	  && type != DT_veclen
+	  && type != DT_elt_zero_int
+	  && type != DT_elt_one_int
+	  && type != DT_elt_zero_wide_safe)
+	continue;
+
+      /* If we'd been performing more than one test, create a new node
+         below our first test.  */
+      if (first->tests->next != NULL)
+	{
+	  new_dec = new_decision (first->position, &first->success);
+	  new_dec->tests = first->tests->next;
+	  first->tests->next = NULL;
+	}
+
+      /* Crop the node tree off after our first test.  */
+      first->next = NULL;
+      old_last = head->last;
+      head->last = first;
+
+      /* For each compatible test, adjust to perform only one test in
+	 the top level node, then merge the node back into the tree.  */
+      do
+	{
+	  struct decision_head h;
+
+	  if (next->tests->next != NULL)
+	    {
+	      new_dec = new_decision (next->position, &next->success);
+	      new_dec->tests = next->tests->next;
+	      next->tests->next = NULL;
+	    }
+	  new_dec = next;
+	  next = next->next;
+	  new_dec->next = NULL;
+	  h.first = h.last = new_dec;
+
+	  merge_trees (head, &h);
+	}
+      while (next && next->tests->type == type);
+
+      /* After we run out of compatible tests, graft the remaining nodes
+	 back onto the tree.  */
+      if (next)
+	{
+	  next->prev = head->last;
+	  head->last->next = next;
+	  head->last = old_last;
+	}
+    }
+
+  /* Recurse.  */
+  for (first = head->first; first; first = first->next)
+    factor_tests (&first->success);
+}
+
+/* After factoring, try to simplify the tests on any one node.
+   Tests that are useful for switch statements are recognizable
+   by having only a single test on a node -- we'll be manipulating
+   nodes with multiple tests:
+
+   If we have mode tests or code tests that are redundant with
+   predicates, remove them.  */
+
+static void
+simplify_tests (struct decision_head *head)
+{
+  struct decision *tree;
+
+  for (tree = head->first; tree; tree = tree->next)
+    {
+      struct decision_test *a, *b;
+
+      a = tree->tests;
+      b = a->next;
+      if (b == NULL)
+	continue;
+
+      /* Find a predicate node.  */
+      while (b && b->type != DT_pred)
+	b = b->next;
+      if (b)
+	{
+	  /* Due to how these tests are constructed, we don't even need
+	     to check that the mode and code are compatible -- they were
+	     generated from the predicate in the first place.  */
+	  while (a->type == DT_mode || a->type == DT_code)
+	    a = a->next;
+	  tree->tests = a;
+	}
+    }
+
+  /* Recurse.  */
+  for (tree = head->first; tree; tree = tree->next)
+    simplify_tests (&tree->success);
+}
+
+/* Count the number of subnodes of HEAD.  If the number is high enough,
+   make the first node in HEAD start a separate subroutine in the C code
+   that is generated.  */
+
+static int
+break_out_subroutines (struct decision_head *head, int initial)
+{
+  int size = 0;
+  struct decision *sub;
+
+  for (sub = head->first; sub; sub = sub->next)
+    size += 1 + break_out_subroutines (&sub->success, 0);
+
+  if (size > SUBROUTINE_THRESHOLD && ! initial)
+    {
+      head->first->subroutine_number = ++next_subroutine_number;
+      size = 1;
+    }
+  return size;
+}
+
+/* For each node p, find the next alternative that might be true
+   when p is true.  */
+
+static void
+find_afterward (struct decision_head *head, struct decision *real_afterward)
+{
+  struct decision *p, *q, *afterward;
+
+  /* We can't propagate alternatives across subroutine boundaries.
+     This is not incorrect, merely a minor optimization loss.  */
+
+  p = head->first;
+  afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
+
+  for ( ; p ; p = p->next)
+    {
+      /* Find the next node that might be true if this one fails.  */
+      for (q = p->next; q ; q = q->next)
+	if (maybe_both_true (p, q, 1))
+	  break;
+
+      /* If we reached the end of the list without finding one,
+	 use the incoming afterward position.  */
+      if (!q)
+	q = afterward;
+      p->afterward = q;
+      if (q)
+	q->need_label = 1;
+    }
+
+  /* Recurse.  */
+  for (p = head->first; p ; p = p->next)
+    if (p->success.first)
+      find_afterward (&p->success, p->afterward);
+
+  /* When we are generating a subroutine, record the real afterward
+     position in the first node where write_tree can find it, and we
+     can do the right thing at the subroutine call site.  */
+  p = head->first;
+  if (p->subroutine_number > 0)
+    p->afterward = real_afterward;
+}
+
+/* Assuming that the state of argument is denoted by OLDPOS, take whatever
+   actions are necessary to move to NEWPOS.  If we fail to move to the
+   new state, branch to node AFTERWARD if nonzero, otherwise return.
+
+   Failure to move to the new state can only occur if we are trying to
+   match multiple insns and we try to step past the end of the stream.  */
+
+static void
+change_state (struct position *oldpos, struct position *newpos,
+	      const char *indent)
+{
+  while (oldpos->depth > newpos->depth)
+    oldpos = oldpos->base;
+
+  if (oldpos != newpos)
+    switch (newpos->type)
+      {
+      case POS_PEEP2_INSN:
+	printf ("%stem = peep2_next_insn (%d);\n", indent, newpos->arg);
+	printf ("%sx%d = PATTERN (tem);\n", indent, newpos->depth);
+	break;
+
+      case POS_XEXP:
+	change_state (oldpos, newpos->base, indent);
+	printf ("%sx%d = XEXP (x%d, %d);\n",
+		indent, newpos->depth, newpos->depth - 1, newpos->arg);
+	break;
+
+      case POS_XVECEXP0:
+	change_state (oldpos, newpos->base, indent);
+	printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
+		indent, newpos->depth, newpos->depth - 1, newpos->arg);
+	break;
+    }
+}
+
+/* Print the enumerator constant for CODE -- the upcase version of
+   the name.  */
+
+static void
+print_code (enum rtx_code code)
+{
+  const char *p;
+  for (p = GET_RTX_NAME (code); *p; p++)
+    putchar (TOUPPER (*p));
+}
+
+/* Emit code to cross an afterward link -- change state and branch.  */
+
+static void
+write_afterward (struct decision *start, struct decision *afterward,
+		 const char *indent)
+{
+  if (!afterward || start->subroutine_number > 0)
+    printf ("%sgoto ret0;\n", indent);
+  else
+    {
+      change_state (start->position, afterward->position, indent);
+      printf ("%sgoto L%d;\n", indent, afterward->number);
+    }
+}
+
+/* Emit a HOST_WIDE_INT as an integer constant expression.  We need to take
+   special care to avoid "decimal constant is so large that it is unsigned"
+   warnings in the resulting code.  */
+
+static void
+print_host_wide_int (HOST_WIDE_INT val)
+{
+  HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
+  if (val == min)
+    printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
+  else
+    printf (HOST_WIDE_INT_PRINT_DEC_C, val);
+}
+
+/* Emit a switch statement, if possible, for an initial sequence of
+   nodes at START.  Return the first node yet untested.  */
+
+static struct decision *
+write_switch (struct decision *start, int depth)
+{
+  struct decision *p = start;
+  enum decision_type type = p->tests->type;
+  struct decision *needs_label = NULL;
+
+  /* If we have two or more nodes in sequence that test the same one
+     thing, we may be able to use a switch statement.  */
+
+  if (!p->next
+      || p->tests->next
+      || p->next->tests->type != type
+      || p->next->tests->next
+      || nodes_identical_1 (p->tests, p->next->tests))
+    return p;
+
+  /* DT_code is special in that we can do interesting things with
+     known predicates at the same time.  */
+  if (type == DT_code)
+    {
+      char codemap[NUM_RTX_CODE];
+      struct decision *ret;
+      RTX_CODE code;
+
+      memset (codemap, 0, sizeof (codemap));
+
+      printf ("  switch (GET_CODE (x%d))\n    {\n", depth);
+      code = p->tests->u.code;
+      do
+	{
+	  if (p != start && p->need_label && needs_label == NULL)
+	    needs_label = p;
+
+	  printf ("    case ");
+	  print_code (code);
+	  printf (":\n      goto L%d;\n", p->success.first->number);
+	  p->success.first->need_label = 1;
+
+	  codemap[code] = 1;
+	  p = p->next;
+	}
+      while (p
+	     && ! p->tests->next
+	     && p->tests->type == DT_code
+	     && ! codemap[code = p->tests->u.code]);
+
+      /* If P is testing a predicate that we know about and we haven't
+	 seen any of the codes that are valid for the predicate, we can
+	 write a series of "case" statement, one for each possible code.
+	 Since we are already in a switch, these redundant tests are very
+	 cheap and will reduce the number of predicates called.  */
+
+      /* Note that while we write out cases for these predicates here,
+	 we don't actually write the test here, as it gets kinda messy.
+	 It is trivial to leave this to later by telling our caller that
+	 we only processed the CODE tests.  */
+      if (needs_label != NULL)
+	ret = needs_label;
+      else
+	ret = p;
+
+      while (p && p->tests->type == DT_pred && p->tests->u.pred.data)
+	{
+	  const struct pred_data *data = p->tests->u.pred.data;
+	  int c;
+
+	  for (c = 0; c < NUM_RTX_CODE; c++)
+	    if (codemap[c] && data->codes[c])
+	      goto pred_done;
+
+	  for (c = 0; c < NUM_RTX_CODE; c++)
+	    if (data->codes[c])
+	      {
+		fputs ("    case ", stdout);
+		print_code ((enum rtx_code) c);
+		fputs (":\n", stdout);
+		codemap[c] = 1;
+	      }
+
+	  printf ("      goto L%d;\n", p->number);
+	  p->need_label = 1;
+	  p = p->next;
+	}
+
+    pred_done:
+      /* Make the default case skip the predicates we managed to match.  */
+
+      printf ("    default:\n");
+      if (p != ret)
+	{
+	  if (p)
+	    {
+	      printf ("      goto L%d;\n", p->number);
+	      p->need_label = 1;
+	    }
+	  else
+	    write_afterward (start, start->afterward, "      ");
+	}
+      else
+	printf ("     break;\n");
+      printf ("   }\n");
+
+      return ret;
+    }
+  else if (type == DT_mode
+	   || type == DT_veclen
+	   || type == DT_elt_zero_int
+	   || type == DT_elt_one_int
+	   || type == DT_elt_zero_wide_safe)
+    {
+      const char *indent = "";
+
+      /* We cast switch parameter to integer, so we must ensure that the value
+	 fits.  */
+      if (type == DT_elt_zero_wide_safe)
+	{
+	  indent = "  ";
+	  printf ("  if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n",
+		  depth, depth);
+	}
+      printf ("%s  switch (", indent);
+      switch (type)
+	{
+	case DT_mode:
+	  printf ("GET_MODE (x%d)", depth);
+	  break;
+	case DT_veclen:
+	  printf ("XVECLEN (x%d, 0)", depth);
+	  break;
+	case DT_elt_zero_int:
+	  printf ("XINT (x%d, 0)", depth);
+	  break;
+	case DT_elt_one_int:
+	  printf ("XINT (x%d, 1)", depth);
+	  break;
+	case DT_elt_zero_wide_safe:
+	  /* Convert result of XWINT to int for portability since some C
+	     compilers won't do it and some will.  */
+	  printf ("(int) XWINT (x%d, 0)", depth);
+	  break;
+	default:
+	  gcc_unreachable ();
+	}
+      printf (")\n%s    {\n", indent);
+
+      do
+	{
+	  /* Merge trees will not unify identical nodes if their
+	     sub-nodes are at different levels.  Thus we must check
+	     for duplicate cases.  */
+	  struct decision *q;
+	  for (q = start; q != p; q = q->next)
+	    if (nodes_identical_1 (p->tests, q->tests))
+	      goto case_done;
+
+	  if (p != start && p->need_label && needs_label == NULL)
+	    needs_label = p;
+
+	  printf ("%s    case ", indent);
+	  switch (type)
+	    {
+	    case DT_mode:
+	      printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
+	      break;
+	    case DT_veclen:
+	      printf ("%d", p->tests->u.veclen);
+	      break;
+	    case DT_elt_zero_int:
+	    case DT_elt_one_int:
+	    case DT_elt_zero_wide:
+	    case DT_elt_zero_wide_safe:
+	      print_host_wide_int (p->tests->u.intval);
+	      break;
+	    default:
+	      gcc_unreachable ();
+	    }
+	  printf (":\n%s      goto L%d;\n", indent, p->success.first->number);
+	  p->success.first->need_label = 1;
+
+	  p = p->next;
+	}
+      while (p && p->tests->type == type && !p->tests->next);
+
+    case_done:
+      printf ("%s    default:\n%s      break;\n%s    }\n",
+	      indent, indent, indent);
+
+      return needs_label != NULL ? needs_label : p;
+    }
+  else
+    {
+      /* None of the other tests are amenable.  */
+      return p;
+    }
+}
+
+/* Emit code for one test.  */
+
+static void
+write_cond (struct decision_test *p, int depth,
+	    enum routine_type subroutine_type)
+{
+  switch (p->type)
+    {
+    case DT_num_insns:
+      printf ("peep2_current_count >= %d", p->u.num_insns);
+      break;
+
+    case DT_mode:
+      printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
+      break;
+
+    case DT_code:
+      printf ("GET_CODE (x%d) == ", depth);
+      print_code (p->u.code);
+      break;
+
+    case DT_veclen:
+      printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
+      break;
+
+    case DT_elt_zero_int:
+      printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
+      break;
+
+    case DT_elt_one_int:
+      printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
+      break;
+
+    case DT_elt_zero_wide:
+    case DT_elt_zero_wide_safe:
+      printf ("XWINT (x%d, 0) == ", depth);
+      print_host_wide_int (p->u.intval);
+      break;
+
+    case DT_const_int:
+      printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
+	      depth, (int) p->u.intval);
+      break;
+
+    case DT_veclen_ge:
+      printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
+      break;
+
+    case DT_dup:
+      printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
+      break;
+
+    case DT_pred:
+      printf ("%s (x%d, %smode)", p->u.pred.name, depth,
+	      GET_MODE_NAME (p->u.pred.mode));
+      break;
+
+    case DT_c_test:
+      print_c_condition (p->u.c_test);
+      break;
+
+    case DT_accept_insn:
+      gcc_assert (subroutine_type == RECOG);
+      gcc_assert (p->u.insn.num_clobbers_to_add);
+      printf ("pnum_clobbers != NULL");
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Emit code for one action.  The previous tests have succeeded;
+   TEST is the last of the chain.  In the normal case we simply
+   perform a state change.  For the `accept' tests we must do more work.  */
+
+static void
+write_action (struct decision *p, struct decision_test *test,
+	      int depth, int uncond, struct decision *success,
+	      enum routine_type subroutine_type)
+{
+  const char *indent;
+  int want_close = 0;
+
+  if (uncond)
+    indent = "  ";
+  else if (test->type == DT_accept_op || test->type == DT_accept_insn)
+    {
+      fputs ("    {\n", stdout);
+      indent = "      ";
+      want_close = 1;
+    }
+  else
+    indent = "    ";
+
+  if (test->type == DT_accept_op)
+    {
+      printf ("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
+
+      /* Only allow DT_accept_insn to follow.  */
+      if (test->next)
+	{
+	  test = test->next;
+	  gcc_assert (test->type == DT_accept_insn);
+	}
+    }
+
+  /* Sanity check that we're now at the end of the list of tests.  */
+  gcc_assert (!test->next);
+
+  if (test->type == DT_accept_insn)
+    {
+      switch (subroutine_type)
+	{
+	case RECOG:
+	  if (test->u.insn.num_clobbers_to_add != 0)
+	    printf ("%s*pnum_clobbers = %d;\n",
+		    indent, test->u.insn.num_clobbers_to_add);
+	  printf ("%sreturn %d;  /* %s */\n", indent,
+		  test->u.insn.code_number,
+		  get_insn_name (test->u.insn.code_number));
+	  break;
+
+	case SPLIT:
+	  printf ("%sreturn gen_split_%d (insn, operands);\n",
+		  indent, test->u.insn.code_number);
+	  break;
+
+	case PEEPHOLE2:
+	  {
+	    int match_len = 0;
+	    struct position *pos;
+
+	    for (pos = p->position; pos; pos = pos->base)
+	      if (pos->type == POS_PEEP2_INSN)
+		{
+		  match_len = pos->arg;
+		  break;
+		}
+	    printf ("%s*_pmatch_len = %d;\n", indent, match_len);
+	    printf ("%stem = gen_peephole2_%d (insn, operands);\n",
+		    indent, test->u.insn.code_number);
+	    printf ("%sif (tem != 0)\n%s  return tem;\n", indent, indent);
+	  }
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+  else
+    {
+      printf ("%sgoto L%d;\n", indent, success->number);
+      success->need_label = 1;
+    }
+
+  if (want_close)
+    fputs ("    }\n", stdout);
+}
+
+/* Return 1 if the test is always true and has no fallthru path.  Return -1
+   if the test does have a fallthru path, but requires that the condition be
+   terminated.  Otherwise return 0 for a normal test.  */
+/* ??? is_unconditional is a stupid name for a tri-state function.  */
+
+static int
+is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
+{
+  if (t->type == DT_accept_op)
+    return 1;
+
+  if (t->type == DT_accept_insn)
+    {
+      switch (subroutine_type)
+	{
+	case RECOG:
+	  return (t->u.insn.num_clobbers_to_add == 0);
+	case SPLIT:
+	  return 1;
+	case PEEPHOLE2:
+	  return -1;
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return 0;
+}
+
+/* Emit code for one node -- the conditional and the accompanying action.
+   Return true if there is no fallthru path.  */
+
+static int
+write_node (struct decision *p, int depth,
+	    enum routine_type subroutine_type)
+{
+  struct decision_test *test, *last_test;
+  int uncond;
+
+  /* Scan the tests and simplify comparisons against small
+     constants.  */
+  for (test = p->tests; test; test = test->next)
+    {
+      if (test->type == DT_code
+	  && test->u.code == CONST_INT
+	  && test->next
+	  && test->next->type == DT_elt_zero_wide_safe
+	  && -MAX_SAVED_CONST_INT <= test->next->u.intval
+	  && test->next->u.intval <= MAX_SAVED_CONST_INT)
+	{
+	  test->type = DT_const_int;
+	  test->u.intval = test->next->u.intval;
+	  test->next = test->next->next;
+	}
+    }
+
+  last_test = test = p->tests;
+  uncond = is_unconditional (test, subroutine_type);
+  if (uncond == 0)
+    {
+      printf ("  if (");
+      write_cond (test, depth, subroutine_type);
+
+      while ((test = test->next) != NULL)
+	{
+	  last_test = test;
+	  if (is_unconditional (test, subroutine_type))
+	    break;
+
+	  printf ("\n      && ");
+	  write_cond (test, depth, subroutine_type);
+	}
+
+      printf (")\n");
+    }
+
+  write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
+
+  return uncond > 0;
+}
+
+/* Emit code for all of the sibling nodes of HEAD.  */
+
+static void
+write_tree_1 (struct decision_head *head, int depth,
+	      enum routine_type subroutine_type)
+{
+  struct decision *p, *next;
+  int uncond = 0;
+
+  for (p = head->first; p ; p = next)
+    {
+      /* The label for the first element was printed in write_tree.  */
+      if (p != head->first && p->need_label)
+	OUTPUT_LABEL (" ", p->number);
+
+      /* Attempt to write a switch statement for a whole sequence.  */
+      next = write_switch (p, depth);
+      if (p != next)
+	uncond = 0;
+      else
+	{
+	  /* Failed -- fall back and write one node.  */
+	  uncond = write_node (p, depth, subroutine_type);
+	  next = p->next;
+	}
+    }
+
+  /* Finished with this chain.  Close a fallthru path by branching
+     to the afterward node.  */
+  if (! uncond)
+    write_afterward (head->last, head->last->afterward, "  ");
+}
+
+/* Write out the decision tree starting at HEAD.  PREVPOS is the
+   position at the node that branched to this node.  */
+
+static void
+write_tree (struct decision_head *head, struct position *prevpos,
+	    enum routine_type type, int initial)
+{
+  struct decision *p = head->first;
+
+  putchar ('\n');
+  if (p->need_label)
+    OUTPUT_LABEL (" ", p->number);
+
+  if (! initial && p->subroutine_number > 0)
+    {
+      static const char * const name_prefix[] = {
+	  "recog", "split", "peephole2"
+      };
+
+      static const char * const call_suffix[] = {
+	  ", pnum_clobbers", "", ", _pmatch_len"
+      };
+
+      /* This node has been broken out into a separate subroutine.
+	 Call it, test the result, and branch accordingly.  */
+
+      if (p->afterward)
+	{
+	  printf ("  tem = %s_%d (x0, insn%s);\n",
+		  name_prefix[type], p->subroutine_number, call_suffix[type]);
+	  if (IS_SPLIT (type))
+	    printf ("  if (tem != 0)\n    return tem;\n");
+	  else
+	    printf ("  if (tem >= 0)\n    return tem;\n");
+
+	  change_state (p->position, p->afterward->position, "  ");
+	  printf ("  goto L%d;\n", p->afterward->number);
+	}
+      else
+	{
+	  printf ("  return %s_%d (x0, insn%s);\n",
+		  name_prefix[type], p->subroutine_number, call_suffix[type]);
+	}
+    }
+  else
+    {
+      change_state (prevpos, p->position, "  ");
+      write_tree_1 (head, p->position->depth, type);
+
+      for (p = head->first; p; p = p->next)
+        if (p->success.first)
+          write_tree (&p->success, p->position, type, 0);
+    }
+}
+
+/* Write out a subroutine of type TYPE to do comparisons starting at
+   node TREE.  */
+
+static void
+write_subroutine (struct decision_head *head, enum routine_type type)
+{
+  int subfunction = head->first ? head->first->subroutine_number : 0;
+  const char *s_or_e;
+  char extension[32];
+  int i;
+
+  s_or_e = subfunction ? "static " : "";
+
+  if (subfunction)
+    sprintf (extension, "_%d", subfunction);
+  else if (type == RECOG)
+    extension[0] = '\0';
+  else
+    strcpy (extension, "_insns");
+
+  switch (type)
+    {
+    case RECOG:
+      printf ("%sint\n\
+recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
+      break;
+    case SPLIT:
+      printf ("%srtx\n\
+split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
+	      s_or_e, extension);
+      break;
+    case PEEPHOLE2:
+      printf ("%srtx\n\
+peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
+	      s_or_e, extension);
+      break;
+    }
+
+  printf ("{\n  rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
+  for (i = 1; i <= max_depth; i++)
+    printf ("  rtx x%d ATTRIBUTE_UNUSED;\n", i);
+
+  printf ("  %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
+
+  if (!subfunction)
+    printf ("  recog_data.insn = NULL_RTX;\n");
+
+  if (head->first)
+    write_tree (head, &root_pos, type, 1);
+  else
+    printf ("  goto ret0;\n");
+
+  printf (" ret0:\n  return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
+}
+
+/* In break_out_subroutines, we discovered the boundaries for the
+   subroutines, but did not write them out.  Do so now.  */
+
+static void
+write_subroutines (struct decision_head *head, enum routine_type type)
+{
+  struct decision *p;
+
+  for (p = head->first; p ; p = p->next)
+    if (p->success.first)
+      write_subroutines (&p->success, type);
+
+  if (head->first->subroutine_number > 0)
+    write_subroutine (head, type);
+}
+
+/* Begin the output file.  */
+
+static void
+write_header (void)
+{
+  puts ("\
+/* Generated automatically by the program `genrecog' from the target\n\
+   machine description file.  */\n\
+\n\
+#include \"config.h\"\n\
+#include \"system.h\"\n\
+#include \"coretypes.h\"\n\
+#include \"tm.h\"\n\
+#include \"rtl.h\"\n\
+#include \"tm_p.h\"\n\
+#include \"function.h\"\n\
+#include \"insn-config.h\"\n\
+#include \"recog.h\"\n\
+#include \"output.h\"\n\
+#include \"flags.h\"\n\
+#include \"hard-reg-set.h\"\n\
+#include \"resource.h\"\n\
+#include \"diagnostic-core.h\"\n\
+#include \"reload.h\"\n\
+#include \"regs.h\"\n\
+#include \"tm-constrs.h\"\n\
+\n");
+
+  puts ("\n\
+/* `recog' contains a decision tree that recognizes whether the rtx\n\
+   X0 is a valid instruction.\n\
+\n\
+   recog returns -1 if the rtx is not valid.  If the rtx is valid, recog\n\
+   returns a nonnegative number which is the insn code number for the\n\
+   pattern that matched.  This is the same as the order in the machine\n\
+   description of the entry that matched.  This number can be used as an\n\
+   index into `insn_data' and other tables.\n");
+  puts ("\
+   The third argument to recog is an optional pointer to an int.  If\n\
+   present, recog will accept a pattern if it matches except for missing\n\
+   CLOBBER expressions at the end.  In that case, the value pointed to by\n\
+   the optional pointer will be set to the number of CLOBBERs that need\n\
+   to be added (it should be initialized to zero by the caller).  If it");
+  puts ("\
+   is set nonzero, the caller should allocate a PARALLEL of the\n\
+   appropriate size, copy the initial entries, and call add_clobbers\n\
+   (found in insn-emit.c) to fill in the CLOBBERs.\n\
+");
+
+  puts ("\n\
+   The function split_insns returns 0 if the rtl could not\n\
+   be split or the split rtl as an INSN list if it can be.\n\
+\n\
+   The function peephole2_insns returns 0 if the rtl could not\n\
+   be matched. If there was a match, the new rtl is returned in an INSN list,\n\
+   and LAST_INSN will point to the last recognized insn in the old sequence.\n\
+*/\n\n");
+}
+
+
+/* Construct and return a sequence of decisions
+   that will recognize INSN.
+
+   TYPE says what type of routine we are recognizing (RECOG or SPLIT).  */
+
+static struct decision_head
+make_insn_sequence (rtx insn, enum routine_type type)
+{
+  rtx x;
+  const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
+  int truth = maybe_eval_c_test (c_test);
+  struct decision *last;
+  struct decision_test *test, **place;
+  struct decision_head head;
+  struct position *c_test_pos, **pos_ptr;
+
+  /* We should never see an insn whose C test is false at compile time.  */
+  gcc_assert (truth);
+
+  c_test_pos = &root_pos;
+  if (type == PEEPHOLE2)
+    {
+      int i, j;
+
+      /* peephole2 gets special treatment:
+	 - X always gets an outer parallel even if it's only one entry
+	 - we remove all traces of outer-level match_scratch and match_dup
+           expressions here.  */
+      x = rtx_alloc (PARALLEL);
+      PUT_MODE (x, VOIDmode);
+      XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
+      pos_ptr = &peep2_insn_pos_list;
+      for (i = j = 0; i < XVECLEN (insn, 0); i++)
+	{
+	  rtx tmp = XVECEXP (insn, 0, i);
+	  if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
+	    {
+	      c_test_pos = next_position (pos_ptr, &root_pos,
+					  POS_PEEP2_INSN, j);
+	      XVECEXP (x, 0, j) = tmp;
+	      j++;
+	      pos_ptr = &c_test_pos->next;
+	    }
+	}
+      XVECLEN (x, 0) = j;
+    }
+  else if (XVECLEN (insn, type == RECOG) == 1)
+    x = XVECEXP (insn, type == RECOG, 0);
+  else
+    {
+      x = rtx_alloc (PARALLEL);
+      XVEC (x, 0) = XVEC (insn, type == RECOG);
+      PUT_MODE (x, VOIDmode);
+    }
+
+  validate_pattern (x, insn, NULL_RTX, 0);
+
+  memset (&head, 0, sizeof (head));
+  last = add_to_sequence (x, &head, &root_pos, type, 1);
+
+  /* Find the end of the test chain on the last node.  */
+  for (test = last->tests; test->next; test = test->next)
+    continue;
+  place = &test->next;
+
+  /* Skip the C test if it's known to be true at compile time.  */
+  if (truth == -1)
+    {
+      /* Need a new node if we have another test to add.  */
+      if (test->type == DT_accept_op)
+	{
+	  last = new_decision (c_test_pos, &last->success);
+	  place = &last->tests;
+	}
+      test = new_decision_test (DT_c_test, &place);
+      test->u.c_test = c_test;
+    }
+
+  test = new_decision_test (DT_accept_insn, &place);
+  test->u.insn.code_number = next_insn_code;
+  test->u.insn.lineno = pattern_lineno;
+  test->u.insn.num_clobbers_to_add = 0;
+
+  switch (type)
+    {
+    case RECOG:
+      /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
+	 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
+	 If so, set up to recognize the pattern without these CLOBBERs.  */
+
+      if (GET_CODE (x) == PARALLEL)
+	{
+	  int i;
+
+	  /* Find the last non-clobber in the parallel.  */
+	  for (i = XVECLEN (x, 0); i > 0; i--)
+	    {
+	      rtx y = XVECEXP (x, 0, i - 1);
+	      if (GET_CODE (y) != CLOBBER
+		  || (!REG_P (XEXP (y, 0))
+		      && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
+		break;
+	    }
+
+	  if (i != XVECLEN (x, 0))
+	    {
+	      rtx new_rtx;
+	      struct decision_head clobber_head;
+
+	      /* Build a similar insn without the clobbers.  */
+	      if (i == 1)
+		new_rtx = XVECEXP (x, 0, 0);
+	      else
+		{
+		  int j;
+
+		  new_rtx = rtx_alloc (PARALLEL);
+		  XVEC (new_rtx, 0) = rtvec_alloc (i);
+		  for (j = i - 1; j >= 0; j--)
+		    XVECEXP (new_rtx, 0, j) = XVECEXP (x, 0, j);
+		}
+
+	      /* Recognize it.  */
+	      memset (&clobber_head, 0, sizeof (clobber_head));
+	      last = add_to_sequence (new_rtx, &clobber_head, &root_pos,
+				      type, 1);
+
+	      /* Find the end of the test chain on the last node.  */
+	      for (test = last->tests; test->next; test = test->next)
+		continue;
+
+	      /* We definitely have a new test to add -- create a new
+		 node if needed.  */
+	      place = &test->next;
+	      if (test->type == DT_accept_op)
+		{
+		  last = new_decision (&root_pos, &last->success);
+		  place = &last->tests;
+		}
+
+	      /* Skip the C test if it's known to be true at compile
+                 time.  */
+	      if (truth == -1)
+		{
+		  test = new_decision_test (DT_c_test, &place);
+		  test->u.c_test = c_test;
+		}
+
+	      test = new_decision_test (DT_accept_insn, &place);
+	      test->u.insn.code_number = next_insn_code;
+	      test->u.insn.lineno = pattern_lineno;
+	      test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
+
+	      merge_trees (&head, &clobber_head);
+	    }
+	}
+      break;
+
+    case SPLIT:
+      /* Define the subroutine we will call below and emit in genemit.  */
+      printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code);
+      break;
+
+    case PEEPHOLE2:
+      /* Define the subroutine we will call below and emit in genemit.  */
+      printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
+	      next_insn_code);
+      break;
+    }
+
+  return head;
+}
+
+static void
+process_tree (struct decision_head *head, enum routine_type subroutine_type)
+{
+  if (head->first == NULL)
+    {
+      /* We can elide peephole2_insns, but not recog or split_insns.  */
+      if (subroutine_type == PEEPHOLE2)
+	return;
+    }
+  else
+    {
+      factor_tests (head);
+
+      next_subroutine_number = 0;
+      break_out_subroutines (head, 1);
+      find_afterward (head, NULL);
+
+      /* We run this after find_afterward, because find_afterward needs
+	 the redundant DT_mode tests on predicates to determine whether
+	 two tests can both be true or not.  */
+      simplify_tests (head);
+
+      write_subroutines (head, subroutine_type);
+    }
+
+  write_subroutine (head, subroutine_type);
+}
+
+extern int main (int, char **);
+
+int
+main (int argc, char **argv)
+{
+  rtx desc;
+  struct decision_head recog_tree, split_tree, peephole2_tree, h;
+
+  progname = "genrecog";
+
+  memset (&recog_tree, 0, sizeof recog_tree);
+  memset (&split_tree, 0, sizeof split_tree);
+  memset (&peephole2_tree, 0, sizeof peephole2_tree);
+
+  if (!init_rtx_reader_args (argc, argv))
+    return (FATAL_EXIT_CODE);
+
+  next_insn_code = 0;
+
+  write_header ();
+
+  /* Read the machine description.  */
+
+  while (1)
+    {
+      desc = read_md_rtx (&pattern_lineno, &next_insn_code);
+      if (desc == NULL)
+	break;
+
+      switch (GET_CODE (desc))
+	{
+	case DEFINE_INSN:
+	  h = make_insn_sequence (desc, RECOG);
+	  merge_trees (&recog_tree, &h);
+	  break;
+
+	case DEFINE_SPLIT:
+	  h = make_insn_sequence (desc, SPLIT);
+	  merge_trees (&split_tree, &h);
+	  break;
+
+	case DEFINE_PEEPHOLE2:
+	  h = make_insn_sequence (desc, PEEPHOLE2);
+	  merge_trees (&peephole2_tree, &h);
+
+	default:
+	  /* do nothing */;
+	}
+    }
+
+  if (have_error)
+    return FATAL_EXIT_CODE;
+
+  puts ("\n\n");
+
+  process_tree (&recog_tree, RECOG);
+  process_tree (&split_tree, SPLIT);
+  process_tree (&peephole2_tree, PEEPHOLE2);
+
+  fflush (stdout);
+  return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
+}
+
+static void
+debug_decision_2 (struct decision_test *test)
+{
+  switch (test->type)
+    {
+    case DT_num_insns:
+      fprintf (stderr, "num_insns=%d", test->u.num_insns);
+      break;
+    case DT_mode:
+      fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
+      break;
+    case DT_code:
+      fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
+      break;
+    case DT_veclen:
+      fprintf (stderr, "veclen=%d", test->u.veclen);
+      break;
+    case DT_elt_zero_int:
+      fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
+      break;
+    case DT_elt_one_int:
+      fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
+      break;
+    case DT_elt_zero_wide:
+      fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
+      break;
+    case DT_elt_zero_wide_safe:
+      fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
+      break;
+    case DT_veclen_ge:
+      fprintf (stderr, "veclen>=%d", test->u.veclen);
+      break;
+    case DT_dup:
+      fprintf (stderr, "dup=%d", test->u.dup);
+      break;
+    case DT_pred:
+      fprintf (stderr, "pred=(%s,%s)",
+	       test->u.pred.name, GET_MODE_NAME (test->u.pred.mode));
+      break;
+    case DT_c_test:
+      {
+	char sub[16+4];
+	strncpy (sub, test->u.c_test, sizeof (sub));
+	memcpy (sub+16, "...", 4);
+	fprintf (stderr, "c_test=\"%s\"", sub);
+      }
+      break;
+    case DT_accept_op:
+      fprintf (stderr, "A_op=%d", test->u.opno);
+      break;
+    case DT_accept_insn:
+      fprintf (stderr, "A_insn=(%d,%d)",
+	       test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+static void
+debug_decision_1 (struct decision *d, int indent)
+{
+  int i;
+  struct decision_test *test;
+
+  if (d == NULL)
+    {
+      for (i = 0; i < indent; ++i)
+	putc (' ', stderr);
+      fputs ("(nil)\n", stderr);
+      return;
+    }
+
+  for (i = 0; i < indent; ++i)
+    putc (' ', stderr);
+
+  putc ('{', stderr);
+  test = d->tests;
+  if (test)
+    {
+      debug_decision_2 (test);
+      while ((test = test->next) != NULL)
+	{
+	  fputs (" + ", stderr);
+	  debug_decision_2 (test);
+	}
+    }
+  fprintf (stderr, "} %d n %d a %d\n", d->number,
+	   (d->next ? d->next->number : -1),
+	   (d->afterward ? d->afterward->number : -1));
+}
+
+static void
+debug_decision_0 (struct decision *d, int indent, int maxdepth)
+{
+  struct decision *n;
+  int i;
+
+  if (maxdepth < 0)
+    return;
+  if (d == NULL)
+    {
+      for (i = 0; i < indent; ++i)
+	putc (' ', stderr);
+      fputs ("(nil)\n", stderr);
+      return;
+    }
+
+  debug_decision_1 (d, indent);
+  for (n = d->success.first; n ; n = n->next)
+    debug_decision_0 (n, indent + 2, maxdepth - 1);
+}
+
+DEBUG_FUNCTION void
+debug_decision (struct decision *d)
+{
+  debug_decision_0 (d, 0, 1000000);
+}
+
+DEBUG_FUNCTION void
+debug_decision_list (struct decision *d)
+{
+  while (d)
+    {
+      debug_decision_0 (d, 0, 0);
+      d = d->next;
+    }
+}