genrecog.c

GUN开源阻止下的编译器GCC

/* Generate code from machine description to recognize rtl as insns.
   Copyright (C) 1987, 88, 92, 93, 94, 1995 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC 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 2, or (at your option)
any later version.

GNU CC 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 GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */


/* 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 in a SEQUENCE.  */

#include <stdio.h>
#include "hconfig.h"
#include "rtl.h"
#include "obstack.h"

static struct obstack obstack;
struct obstack *rtl_obstack = &obstack;

#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free

extern void free ();
extern rtx read_rtx ();

/* Data structure for a listhead of decision trees.  The alternatives
   to a node are kept in a doublely-linked list so we can easily add nodes
   to the proper place when merging.  */

struct decision_head { struct decision *first, *last; };

/* Data structure for decision tree for recognizing
   legitimate instructions.  */

struct decision
{
  int number;			/* Node number, used for labels */
  char *position;		/* String denoting position in pattern */
  RTX_CODE code;		/* Code to test for or UNKNOWN to suppress */
  char ignore_code;		/* If non-zero, need not test code */
  char ignore_mode;		/* If non-zero, need not test mode */
  int veclen;			/* Length of vector, if nonzero */
  enum machine_mode mode;	/* Machine mode of node */
  char enforce_mode;		/* If non-zero, test `mode' */
  char retest_code, retest_mode; /* See write_tree_1 */
  int test_elt_zero_int;	/* Nonzero if should test XINT (rtl, 0) */
  int elt_zero_int;		/* Required value for XINT (rtl, 0) */
  int test_elt_one_int;		/* Nonzero if should test XINT (rtl, 1) */
  int elt_one_int;		/* Required value for XINT (rtl, 1) */
  int test_elt_zero_wide;	/* Nonzero if should test XWINT (rtl, 0) */
  HOST_WIDE_INT elt_zero_wide;	/* Required value for XWINT (rtl, 0) */
  char *tests;			/* If nonzero predicate to call */
  int pred;			/* `preds' index of predicate or -1 */
  char *c_test;			/* Additional test to perform */
  struct decision_head success;	/* Nodes to test on success */
  int insn_code_number;		/* Insn number matched, if success */
  int num_clobbers_to_add;	/* Number of CLOBBERs to be added to pattern */
  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 */
  int opno;			/* Operand number, if >= 0 */
  int dupno;			/* Number of operand to compare against */
  int label_needed;		/* Nonzero if label needed when writing tree */
  int subroutine_number;	/* Number of subroutine this node starts */
};

#define SUBROUTINE_THRESHOLD 50

static int next_subroutine_number;

/* We can write two types of subroutines: One for insn recognition and
   one to split insns.  This defines which type is being written.  */

enum routine_type {RECOG, SPLIT};

/* Next available node number for tree nodes.  */

static int next_number;

/* Next number to use as an insn_code.  */

static int next_insn_code;

/* Similar, but counts all expressions in the MD file; used for
   error messages. */

static int next_index;

/* Record the highest depth we ever have so we know how many variables to
   allocate in each subroutine we make.  */

static int max_depth;

/* This table contains a list of the rtl codes that can possibly match a
   predicate defined in recog.c.  The function `not_both_true' uses it to
   deduce that there are no expressions that can be matches by certain pairs
   of tree nodes.  Also, if a predicate can match only one code, we can
   hardwire that code into the node testing the predicate.  */

static struct pred_table
{
  char *name;
  RTX_CODE codes[NUM_RTX_CODE];
} preds[]
  = {{"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
			  LABEL_REF, SUBREG, REG, MEM}},
#ifdef PREDICATE_CODES
     PREDICATE_CODES
#endif
     {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
			  LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
     {"register_operand", {SUBREG, REG}},
     {"scratch_operand", {SCRATCH, REG}},
     {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
			    LABEL_REF}},
     {"const_int_operand", {CONST_INT}},
     {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
     {"nonimmediate_operand", {SUBREG, REG, MEM}},
     {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
			    LABEL_REF, SUBREG, REG}},
     {"push_operand", {MEM}},
     {"memory_operand", {SUBREG, MEM}},
     {"indirect_operand", {SUBREG, MEM}},
     {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}},
     {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
				   LABEL_REF, SUBREG, REG, MEM}}};

#define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])

static struct decision_head make_insn_sequence PROTO((rtx, enum routine_type));
static struct decision *add_to_sequence PROTO((rtx, struct decision_head *,
					       char *));
static int not_both_true	PROTO((struct decision *, struct decision *,
				       int));
static int position_merit	PROTO((struct decision *, enum machine_mode,
				       enum rtx_code));
static struct decision_head merge_trees PROTO((struct decision_head,
					       struct decision_head));
static int break_out_subroutines PROTO((struct decision_head,
					enum routine_type, int));
static void write_subroutine	PROTO((struct decision *, enum routine_type));
static void write_tree_1	PROTO((struct decision *, char *,
				       struct decision *, enum routine_type));
static void print_code		PROTO((enum rtx_code));
static int same_codes		PROTO((struct decision *, enum rtx_code));
static void clear_codes		PROTO((struct decision *));
static int same_modes		PROTO((struct decision *, enum machine_mode));
static void clear_modes		PROTO((struct decision *));
static void write_tree		PROTO((struct decision *, char *,
				       struct decision *, int,
				       enum routine_type));
static void change_state	PROTO((char *, char *, int));
static char *copystr		PROTO((char *));
static void mybzero		PROTO((char *, unsigned));
static void mybcopy		PROTO((char *, char *, unsigned));
static char *concat		PROTO((char *, char *));
static void fatal		PROTO((char *));
char *xrealloc			PROTO((char *, unsigned));
char *xmalloc			PROTO((unsigned));
void fancy_abort		PROTO((void));

/* 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 (insn, type)
     rtx insn;
     enum routine_type type;
{
  rtx x;
  char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
  struct decision *last;
  struct decision_head head;

  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);
    }

  last = add_to_sequence (x, &head, "");

  if (c_test[0])
    last->c_test = c_test;
  last->insn_code_number = next_insn_code;
  last->num_clobbers_to_add = 0;

  /* If this is not a DEFINE_SPLIT 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 (type == RECOG && GET_CODE (x) == PARALLEL)
    {
      int i;

      for (i = XVECLEN (x, 0); i > 0; i--)
	if (GET_CODE (XVECEXP (x, 0, i - 1)) != CLOBBER
	    || (GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != REG
		&& GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != MATCH_SCRATCH))
	  break;

      if (i != XVECLEN (x, 0))
	{
	  rtx new;
	  struct decision_head clobber_head;

	  if (i == 1)
	    new = XVECEXP (x, 0, 0);
	  else
	    {
	      int j;

	      new = rtx_alloc (PARALLEL);
	      XVEC (new, 0) = rtvec_alloc (i);
	      for (j = i - 1; j >= 0; j--)
		XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
	    }

	  last = add_to_sequence (new, &clobber_head, "");

	  if (c_test[0])
	    last->c_test = c_test;
	  last->insn_code_number = next_insn_code;
	  last->num_clobbers_to_add = XVECLEN (x, 0) - i;

	  head = merge_trees (head, clobber_head);
	}
    }

  next_insn_code++;

  if (type == SPLIT)
    /* Define the subroutine we will call below and emit in genemit.  */
    printf ("extern rtx gen_split_%d ();\n", last->insn_code_number);

  return head;
}

/* 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 string representing the current position in the insn.

   A pointer to the final node in the chain is returned.  */

static struct decision *
add_to_sequence (pattern, last, position)
     rtx pattern;
     struct decision_head *last;
     char *position;
{
  register RTX_CODE code;
  register struct decision *new
    = (struct decision *) xmalloc (sizeof (struct decision));
  struct decision *this;
  char *newpos;
  register char *fmt;
  register int i;
  int depth = strlen (position);
  int len;

  if (depth > max_depth)
    max_depth = depth;

  new->number = next_number++;
  new->position = copystr (position);
  new->ignore_code = 0;
  new->ignore_mode = 0;
  new->enforce_mode = 1;
  new->retest_code = new->retest_mode = 0;
  new->veclen = 0;
  new->test_elt_zero_int = 0;
  new->test_elt_one_int = 0;
  new->test_elt_zero_wide = 0;
  new->elt_zero_int = 0;
  new->elt_one_int = 0;
  new->elt_zero_wide = 0;
  new->tests = 0;
  new->pred = -1;
  new->c_test = 0;
  new->success.first = new->success.last = 0;
  new->insn_code_number = -1;
  new->num_clobbers_to_add = 0;
  new->next = 0;
  new->prev = 0;
  new->afterward = 0;
  new->opno = -1;
  new->dupno = -1;
  new->label_needed = 0;
  new->subroutine_number = 0;

  this = new;

  last->first = last->last = new;

  newpos = (char *) alloca (depth + 2);
  strcpy (newpos, position);
  newpos[depth + 1] = 0;

 restart:

  new->mode = GET_MODE (pattern);
  new->code = code = GET_CODE (pattern);

  switch (code)
    {
    case MATCH_OPERAND:
    case MATCH_SCRATCH:
    case MATCH_OPERATOR:
    case MATCH_PARALLEL:
      new->opno = XINT (pattern, 0);
      new->code = (code == MATCH_PARALLEL ? PARALLEL : UNKNOWN);
      new->enforce_mode = 0;

      if (code == MATCH_SCRATCH)
	new->tests = "scratch_operand";
      else
	new->tests = XSTR (pattern, 1);

      if (*new->tests == 0)
	new->tests = 0;

      /* See if we know about this predicate and save its number.  If we do,
	 and it only accepts one code, note that fact.  The predicate
	 `const_int_operand' only tests for a CONST_INT, so if we do so we
	 can avoid calling it at all.

	 Finally, if we know that the predicate does not allow CONST_INT, we
	 know that the only way the predicate can match is if the modes match
	 (here we use the kludge of relying on the fact that "address_operand"
	 accepts CONST_INT; otherwise, it would have to be a special case),
	 so we can test the mode (but we need not).  This fact should
	 considerably simplify the generated code.  */

      if (new->tests)
	{
	  for (i = 0; i < NUM_KNOWN_PREDS; i++)
	    if (! strcmp (preds[i].name, new->tests))
	      {
		int j;
		int allows_const_int = 0;

		new->pred = i;

		if (preds[i].codes[1] == 0 && new->code == UNKNOWN)
		  {
		    new->code = preds[i].codes[0];
		    if (! strcmp ("const_int_operand", new->tests))
		      new->tests = 0, new->pred = -1;
		  }

		for (j = 0; j < NUM_RTX_CODE && preds[i].codes[j] != 0; j++)
		  if (preds[i].codes[j] == CONST_INT)
		    allows_const_int = 1;

		if (! allows_const_int)
		  new->enforce_mode = new->ignore_mode= 1;

		break;
	      }

#ifdef PREDICATE_CODES
	  /* If the port has a list of the predicates it uses but omits
	     one, warn.  */
	  if (i == NUM_KNOWN_PREDS)
	    fprintf (stderr, "Warning: `%s' not in PREDICATE_CODES\n",
		     new->tests);
#endif
	}

      if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
	{
	  for (i = 0; i < XVECLEN (pattern, 2); i++)
	    {
	      newpos[depth] = i + (code == MATCH_OPERATOR ? '0': 'a');
	      new = add_to_sequence (XVECEXP (pattern, 2, i),
				     &new->success, newpos);
	    }
	}

      return new;

    case MATCH_OP_DUP:
      new->opno = XINT (pattern, 0);
      new->dupno = XINT (pattern, 0);
      new->code = UNKNOWN;
      new->tests = 0;
      for (i = 0; i < XVECLEN (pattern, 1); i++)
	{
	  newpos[depth] = i + '0';
	  new = add_to_sequence (XVECEXP (pattern, 1, i),
				 &new->success, newpos);
	}
      return new;

    case MATCH_DUP:
    case MATCH_PAR_DUP:
      new->dupno = XINT (pattern, 0);
      new->code = UNKNOWN;
      new->enforce_mode = 0;
      return new;

    case ADDRESS:
      pattern = XEXP (pattern, 0);
      goto restart;

    case SET:
      newpos[depth] = '0';