genrecog.c

早期freebsd实现

/* Generate code from machine description to recognize rtl as insns.
   Copyright (C) 1987, 1988, 1992 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, 675 Mass Ave, Cambridge, MA 02139, 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_operation", {EQ, NE, LE, LT, GE, LT, 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 int try_merge_1 ();
static int no_same_mode ();
static int same_codes ();
static int same_modes ();
char *xmalloc ();
static struct decision *add_to_sequence ();
static struct decision_head merge_trees ();
static struct decision *try_merge_2 ();
static void write_subroutine ();
static void print_code ();
static void clear_codes ();
static void clear_modes ();
static void change_state ();
static void write_tree ();
static char *copystr ();
static char *concat ();
static void fatal ();
void fancy_abort ();
static void mybzero ();
static void mybcopy ();

/* 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 kluge 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;
	    }

      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';
      new = add_to_sequence (SET_DEST (pattern), &new->success, newpos);
      this->success.first->enforce_mode = 1;
      newpos[depth] = '1';
      new = add_to_sequence (SET_SRC (pattern), &new->success, newpos);

      /* If set are setting CC0 from anything other than a COMPARE, we
	 must enforce the mode so that we do not produce ambiguous insns.  */
      if (GET_CODE (SET_DEST (pattern)) == CC0
	  && GET_CODE (SET_SRC (pattern)) != COMPARE)
	this->success.first->enforce_mode = 1;
      return new;

    case SIGN_EXTEND:
    case ZERO_EXTEND: