Subversion Repositories scarts

/* Generate code from machine description to compute values of attributes.

   Copyright (C) 1991, 1993, 1994, 1995, 1996, 1997, 1998,

   1999, 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

   Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu)

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 2, 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 COPYING.  If not, write to the Free

Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301, USA.  */

/* This program handles insn attributes and the DEFINE_DELAY and

   DEFINE_INSN_RESERVATION definitions.

   It produces a series of functions named `get_attr_...', one for each insn

   attribute.  Each of these is given the rtx for an insn and returns a member

   of the enum for the attribute.

   These subroutines have the form of a `switch' on the INSN_CODE (via

   `recog_memoized').  Each case either returns a constant attribute value

   or a value that depends on tests on other attributes, the form of

   operands, or some random C expression (encoded with a SYMBOL_REF

   expression).

   If the attribute `alternative', or a random C expression is present,

   `constrain_operands' is called.  If either of these cases of a reference to

   an operand is found, `extract_insn' is called.

   The special attribute `length' is also recognized.  For this operand,

   expressions involving the address of an operand or the current insn,

   (address (pc)), are valid.  In this case, an initial pass is made to

   set all lengths that do not depend on address.  Those that do are set to

   the maximum length.  Then each insn that depends on an address is checked

   and possibly has its length changed.  The process repeats until no further

   changed are made.  The resulting lengths are saved for use by

   `get_attr_length'.

   A special form of DEFINE_ATTR, where the expression for default value is a

   CONST expression, indicates an attribute that is constant for a given run

   of the compiler.  The subroutine generated for these attributes has no

   parameters as it does not depend on any particular insn.  Constant

   attributes are typically used to specify which variety of processor is

   used.

   Internal attributes are defined to handle DEFINE_DELAY and

   DEFINE_INSN_RESERVATION.  Special routines are output for these cases.

   This program works by keeping a list of possible values for each attribute.

   These include the basic attribute choices, default values for attribute, and

   all derived quantities.

   As the description file is read, the definition for each insn is saved in a

   `struct insn_def'.   When the file reading is complete, a `struct insn_ent'

   is created for each insn and chained to the corresponding attribute value,

   either that specified, or the default.

   An optimization phase is then run.  This simplifies expressions for each

   insn.  EQ_ATTR tests are resolved, whenever possible, to a test that

   indicates when the attribute has the specified value for the insn.  This

   avoids recursive calls during compilation.

   The strategy used when processing DEFINE_DELAY definitions is to create

   arbitrarily complex expressions and have the optimization simplify them.

   Once optimization is complete, any required routines and definitions

   will be written.

   An optimization that is not yet implemented is to hoist the constant

   expressions entirely out of the routines and definitions that are written.

   A way to do this is to iterate over all possible combinations of values

   for constant attributes and generate a set of functions for that given

   combination.  An initialization function would be written that evaluates

   the attributes and installs the corresponding set of routines and

   definitions (each would be accessed through a pointer).

   We use the flags in an RTX as follows:

   `unchanging' (ATTR_IND_SIMPLIFIED_P): This rtx is fully simplified

      independent of the insn code.

   `in_struct' (ATTR_CURR_SIMPLIFIED_P): This rtx is fully simplified

      for the insn code currently being processed (see optimize_attrs).

   `return_val' (ATTR_PERMANENT_P): This rtx is permanent and unique

      (see attr_rtx).  */

#define ATTR_IND_SIMPLIFIED_P(RTX) (RTX_FLAG((RTX), unchanging))

#define ATTR_CURR_SIMPLIFIED_P(RTX) (RTX_FLAG((RTX), in_struct))

#define ATTR_PERMANENT_P(RTX) (RTX_FLAG((RTX), return_val))

#if 0

#define strcmp_check(S1, S2) ((S1) == (S2)              \

                              ? 0                        \

                              : (gcc_assert (strcmp ((S1), (S2))), 1))

#else

#define strcmp_check(S1, S2) ((S1) != (S2))

#endif

#include "bconfig.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "ggc.h"

#include "gensupport.h"

#ifdef HAVE_SYS_RESOURCE_H

# include <sys/resource.h>

#endif

/* We must include obstack.h after <sys/time.h>, to avoid lossage with

   /usr/include/sys/stdtypes.h on Sun OS 4.x.  */

#include "obstack.h"

#include "errors.h"

#include "genattrtab.h"

static struct obstack obstack1, obstack2;

struct obstack *hash_obstack = &obstack1;

struct obstack *temp_obstack = &obstack2;

/* enough space to reserve for printing out ints */

#define MAX_DIGITS (HOST_BITS_PER_INT * 3 / 10 + 3)

/* Define structures used to record attributes and values.  */

/* As each DEFINE_INSN, DEFINE_PEEPHOLE, or DEFINE_ASM_ATTRIBUTES is

   encountered, we store all the relevant information into a

   `struct insn_def'.  This is done to allow attribute definitions to occur

   anywhere in the file.  */

struct insn_def

{

  struct insn_def *next;        /* Next insn in chain.  */

  rtx def;                      /* The DEFINE_...  */

  int insn_code;                /* Instruction number.  */

  int insn_index;               /* Expression numer in file, for errors.  */

  int lineno;                   /* Line number.  */

  int num_alternatives;         /* Number of alternatives.  */

  int vec_idx;                  /* Index of attribute vector in `def'.  */

};

/* Once everything has been read in, we store in each attribute value a list

   of insn codes that have that value.  Here is the structure used for the

   list.  */

struct insn_ent

{

  struct insn_ent *next;        /* Next in chain.  */

  struct insn_def *def;         /* Instruction definition.  */

};

/* Each value of an attribute (either constant or computed) is assigned a

   structure which is used as the listhead of the insns that have that

   value.  */

struct attr_value

{

  rtx value;                    /* Value of attribute.  */

  struct attr_value *next;      /* Next attribute value in chain.  */

  struct insn_ent *first_insn;  /* First insn with this value.  */

  int num_insns;                /* Number of insns with this value.  */

  int has_asm_insn;             /* True if this value used for `asm' insns */

};

/* Structure for each attribute.  */

struct attr_desc

{

  char *name;                   /* Name of attribute.  */

  struct attr_desc *next;       /* Next attribute.  */

  struct attr_value *first_value; /* First value of this attribute.  */

  struct attr_value *default_val; /* Default value for this attribute.  */

  int lineno : 24;              /* Line number.  */

  unsigned is_numeric   : 1;    /* Values of this attribute are numeric.  */

  unsigned is_const     : 1;    /* Attribute value constant for each run.  */

  unsigned is_special   : 1;    /* Don't call `write_attr_set'.  */

  unsigned static_p     : 1;    /* Make the output function static.  */

};

/* Structure for each DEFINE_DELAY.  */

struct delay_desc

{

  rtx def;                      /* DEFINE_DELAY expression.  */

  struct delay_desc *next;      /* Next DEFINE_DELAY.  */

  int num;                      /* Number of DEFINE_DELAY, starting at 1.  */

  int lineno;                   /* Line number.  */

};

/* Listheads of above structures.  */

/* This one is indexed by the first character of the attribute name.  */

#define MAX_ATTRS_INDEX 256

static struct attr_desc *attrs[MAX_ATTRS_INDEX];

static struct insn_def *defs;

static struct delay_desc *delays;

/* Other variables.  */

static int insn_code_number;

static int insn_index_number;

static int got_define_asm_attributes;

static int must_extract;

static int must_constrain;

static int address_used;

static int length_used;

static int num_delays;

static int have_annul_true, have_annul_false;

static int num_insn_ents;

int num_dfa_decls;

/* Stores, for each insn code, the number of constraint alternatives.  */

static int *insn_n_alternatives;

/* Stores, for each insn code, a bitmap that has bits on for each possible

   alternative.  */

static int *insn_alternatives;

/* Used to simplify expressions.  */

static rtx true_rtx, false_rtx;

/* Used to reduce calls to `strcmp' */

static const char *alternative_name;

static const char *length_str;

static const char *delay_type_str;

static const char *delay_1_0_str;

static const char *num_delay_slots_str;

/* Indicate that REG_DEAD notes are valid if dead_or_set_p is ever

   called.  */

int reload_completed = 0;

/* Some machines test `optimize' in macros called from rtlanal.c, so we need

   to define it here.  */

int optimize = 0;

/* Simplify an expression.  Only call the routine if there is something to

   simplify.  */

#define SIMPLIFY_TEST_EXP(EXP,INSN_CODE,INSN_INDEX)     \

  (ATTR_IND_SIMPLIFIED_P (EXP) || ATTR_CURR_SIMPLIFIED_P (EXP) ? (EXP)  \

   : simplify_test_exp (EXP, INSN_CODE, INSN_INDEX))

#define DEF_ATTR_STRING(S) (attr_string ((S), strlen (S)))

/* These are referenced by rtlanal.c and hence need to be defined somewhere.

   They won't actually be used.  */

rtx global_rtl[GR_MAX];

rtx pic_offset_table_rtx;

static void attr_hash_add_rtx   (int, rtx);

static void attr_hash_add_string (int, char *);

static rtx attr_rtx             (enum rtx_code, ...);

static rtx attr_rtx_1           (enum rtx_code, va_list);

static char *attr_string        (const char *, int);

static rtx check_attr_value     (rtx, struct attr_desc *);

static rtx convert_set_attr_alternative (rtx, struct insn_def *);

static rtx convert_set_attr     (rtx, struct insn_def *);

static void check_defs          (void);

static rtx make_canonical       (struct attr_desc *, rtx);

static struct attr_value *get_attr_value (rtx, struct attr_desc *, int);

static rtx copy_rtx_unchanging  (rtx);

static rtx copy_boolean         (rtx);

static void expand_delays       (void);

static void fill_attr           (struct attr_desc *);

static rtx substitute_address   (rtx, rtx (*) (rtx), rtx (*) (rtx));

static void make_length_attrs   (void);

static rtx identity_fn          (rtx);

static rtx zero_fn              (rtx);

static rtx one_fn               (rtx);

static rtx max_fn               (rtx);

static rtx min_fn               (rtx);

static void write_length_unit_log (void);

static rtx simplify_cond        (rtx, int, int);

static void clear_struct_flag (rtx);

static void remove_insn_ent  (struct attr_value *, struct insn_ent *);

static void insert_insn_ent  (struct attr_value *, struct insn_ent *);

static rtx insert_right_side    (enum rtx_code, rtx, rtx, int, int);

static rtx make_alternative_compare (int);

static int compute_alternative_mask (rtx, enum rtx_code);

static rtx evaluate_eq_attr     (rtx, rtx, int, int);

static rtx simplify_and_tree    (rtx, rtx *, int, int);

static rtx simplify_or_tree     (rtx, rtx *, int, int);

static rtx simplify_test_exp    (rtx, int, int);

static rtx simplify_test_exp_in_temp (rtx, int, int);

static void optimize_attrs      (void);

static void gen_attr            (rtx, int);

static int count_alternatives   (rtx);

static int compares_alternatives_p (rtx);

static int contained_in_p       (rtx, rtx);

static void gen_insn            (rtx, int);

static void gen_delay           (rtx, int);

static void write_test_expr     (rtx, int);

static int max_attr_value       (rtx, int*);

static int min_attr_value       (rtx, int*);

static int or_attr_value        (rtx, int*);

static void walk_attr_value     (rtx);

static void write_attr_get      (struct attr_desc *);

static rtx eliminate_known_true (rtx, rtx, int, int);

static void write_attr_set      (struct attr_desc *, int, rtx,

                                 const char *, const char *, rtx,

                                 int, int);

static void write_insn_cases    (struct insn_ent *, int);

static void write_attr_case     (struct attr_desc *, struct attr_value *,

                                 int, const char *, const char *, int, rtx);

static void write_attr_valueq   (struct attr_desc *, const char *);

static void write_attr_value    (struct attr_desc *, rtx);

static void write_upcase        (const char *);

static void write_indent        (int);

static void write_eligible_delay (const char *);

static int write_expr_attr_cache (rtx, struct attr_desc *);

static void write_const_num_delay_slots (void);

static char *next_comma_elt     (const char **);

static struct attr_desc *find_attr (const char **, int);

static struct attr_value *find_most_used  (struct attr_desc *);

static rtx attr_eq              (const char *, const char *);

static const char *attr_numeral (int);

static int attr_equal_p         (rtx, rtx);

static rtx attr_copy_rtx        (rtx);

static int attr_rtx_cost        (rtx);

static bool attr_alt_subset_p (rtx, rtx);

static bool attr_alt_subset_of_compl_p (rtx, rtx);

static rtx attr_alt_intersection (rtx, rtx);

static rtx attr_alt_union (rtx, rtx);

static rtx attr_alt_complement (rtx);

static rtx mk_attr_alt (int);

#define oballoc(size) obstack_alloc (hash_obstack, size)

/* Hash table for sharing RTL and strings.  */

/* Each hash table slot is a bucket containing a chain of these structures.

   Strings are given negative hash codes; RTL expressions are given positive

   hash codes.  */

struct attr_hash

{

  struct attr_hash *next;       /* Next structure in the bucket.  */

  int hashcode;                 /* Hash code of this rtx or string.  */

  union

    {

      char *str;                /* The string (negative hash codes) */

      rtx rtl;                  /* or the RTL recorded here.  */

    } u;

};

/* Now here is the hash table.  When recording an RTL, it is added to

   the slot whose index is the hash code mod the table size.  Note

   that the hash table is used for several kinds of RTL (see attr_rtx)

   and for strings.  While all these live in the same table, they are

   completely independent, and the hash code is computed differently

   for each.  */

#define RTL_HASH_SIZE 4093

struct attr_hash *attr_hash_table[RTL_HASH_SIZE];

/* Here is how primitive or already-shared RTL's hash

   codes are made.  */

#define RTL_HASH(RTL) ((long) (RTL) & 0777777)

/* Add an entry to the hash table for RTL with hash code HASHCODE.  */

static void

attr_hash_add_rtx (int hashcode, rtx rtl)

{

  struct attr_hash *h;

  h = obstack_alloc (hash_obstack, sizeof (struct attr_hash));

  h->hashcode = hashcode;

  h->u.rtl = rtl;

  h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];

  attr_hash_table[hashcode % RTL_HASH_SIZE] = h;

}

/* Add an entry to the hash table for STRING with hash code HASHCODE.  */

static void

attr_hash_add_string (int hashcode, char *str)

{

  struct attr_hash *h;

  h = obstack_alloc (hash_obstack, sizeof (struct attr_hash));

  h->hashcode = -hashcode;

  h->u.str = str;

  h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];

  attr_hash_table[hashcode % RTL_HASH_SIZE] = h;

}

/* Generate an RTL expression, but avoid duplicates.

   Set the ATTR_PERMANENT_P flag for these permanent objects.

   In some cases we cannot uniquify; then we return an ordinary

   impermanent rtx with ATTR_PERMANENT_P clear.

   Args are as follows:

   rtx attr_rtx (code, [element1, ..., elementn])  */

static rtx

attr_rtx_1 (enum rtx_code code, va_list p)

{

  rtx rt_val = NULL_RTX;/* RTX to return to caller...           */

  int hashcode;

  struct attr_hash *h;

  struct obstack *old_obstack = rtl_obstack;

  /* For each of several cases, search the hash table for an existing entry.

     Use that entry if one is found; otherwise create a new RTL and add it

     to the table.  */

  if (GET_RTX_CLASS (code) == RTX_UNARY)

    {

      rtx arg0 = va_arg (p, rtx);

      /* A permanent object cannot point to impermanent ones.  */

      if (! ATTR_PERMANENT_P (arg0))

        {

          rt_val = rtx_alloc (code);

          XEXP (rt_val, 0) = arg0;

          return rt_val;

        }

      hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));

      for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)

        if (h->hashcode == hashcode

            && GET_CODE (h->u.rtl) == code

            && XEXP (h->u.rtl, 0) == arg0)

          return h->u.rtl;

      if (h == 0)

        {

          rtl_obstack = hash_obstack;

          rt_val = rtx_alloc (code);

          XEXP (rt_val, 0) = arg0;

        }

    }

  else if (GET_RTX_CLASS (code) == RTX_BIN_ARITH

           || GET_RTX_CLASS (code) == RTX_COMM_ARITH

           || GET_RTX_CLASS (code) == RTX_COMPARE

           || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)

    {

      rtx arg0 = va_arg (p, rtx);

      rtx arg1 = va_arg (p, rtx);

      /* A permanent object cannot point to impermanent ones.  */

      if (! ATTR_PERMANENT_P (arg0) || ! ATTR_PERMANENT_P (arg1))

        {

          rt_val = rtx_alloc (code);

          XEXP (rt_val, 0) = arg0;

          XEXP (rt_val, 1) = arg1;

          return rt_val;

        }

      hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));

      for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)

        if (h->hashcode == hashcode

            && GET_CODE (h->u.rtl) == code

            && XEXP (h->u.rtl, 0) == arg0

            && XEXP (h->u.rtl, 1) == arg1)

          return h->u.rtl;

      if (h == 0)

        {

          rtl_obstack = hash_obstack;

          rt_val = rtx_alloc (code);

          XEXP (rt_val, 0) = arg0;

          XEXP (rt_val, 1) = arg1;

        }

    }

  else if (GET_RTX_LENGTH (code) == 1

           && GET_RTX_FORMAT (code)[0] == 's')

    {

      char *arg0 = va_arg (p, char *);

      arg0 = DEF_ATTR_STRING (arg0);

      hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));

      for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)

        if (h->hashcode == hashcode

            && GET_CODE (h->u.rtl) == code

            && XSTR (h->u.rtl, 0) == arg0)

          return h->u.rtl;

      if (h == 0)

        {

          rtl_obstack = hash_obstack;

          rt_val = rtx_alloc (code);

          XSTR (rt_val, 0) = arg0;

        }

    }

  else if (GET_RTX_LENGTH (code) == 2

           && GET_RTX_FORMAT (code)[0] == 's'

           && GET_RTX_FORMAT (code)[1] == 's')

    {

      char *arg0 = va_arg (p, char *);

      char *arg1 = va_arg (p, char *);

      hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));

      for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)

        if (h->hashcode == hashcode

            && GET_CODE (h->u.rtl) == code

            && XSTR (h->u.rtl, 0) == arg0

            && XSTR (h->u.rtl, 1) == arg1)

          return h->u.rtl;

      if (h == 0)

        {

          rtl_obstack = hash_obstack;

          rt_val = rtx_alloc (code);

          XSTR (rt_val, 0) = arg0;

          XSTR (rt_val, 1) = arg1;

        }

    }

  else if (code == CONST_INT)

    {

      HOST_WIDE_INT arg0 = va_arg (p, HOST_WIDE_INT);

      if (arg0 == 0)

        return false_rtx;

      else if (arg0 == 1)

        return true_rtx;

      else

        goto nohash;

    }

  else

    {

      int i;            /* Array indices...                     */

      const char *fmt;  /* Current rtx's format...              */

    nohash:

      rt_val = rtx_alloc (code);        /* Allocate the storage space.  */

      fmt = GET_RTX_FORMAT (code);      /* Find the right format...  */

      for (i = 0; i < GET_RTX_LENGTH (code); i++)

        {

          switch (*fmt++)

            {

            case '0':           /* Unused field.  */

              break;

            case 'i':           /* An integer?  */

              XINT (rt_val, i) = va_arg (p, int);

              break;

            case 'w':           /* A wide integer? */

              XWINT (rt_val, i) = va_arg (p, HOST_WIDE_INT);

              break;

            case 's':           /* A string?  */

              XSTR (rt_val, i) = va_arg (p, char *);

              break;

            case 'e':           /* An expression?  */

            case 'u':           /* An insn?  Same except when printing.  */

              XEXP (rt_val, i) = va_arg (p, rtx);

              break;

            case 'E':           /* An RTX vector?  */

              XVEC (rt_val, i) = va_arg (p, rtvec);

              break;

            default:

              gcc_unreachable ();

            }

        }

      return rt_val;

    }

  rtl_obstack = old_obstack;

  attr_hash_add_rtx (hashcode, rt_val);

  ATTR_PERMANENT_P (rt_val) = 1;

  return rt_val;

}

static rtx

attr_rtx (enum rtx_code code, ...)

{

  rtx result;

  va_list p;

  va_start (p, code);

  result = attr_rtx_1 (code, p);

  va_end (p);

  return result;

}

/* Create a new string printed with the printf line arguments into a space

   of at most LEN bytes:

   rtx attr_printf (len, format, [arg1, ..., argn])  */

char *

attr_printf (unsigned int len, const char *fmt, ...)

{

  char str[256];

  va_list p;

  va_start (p, fmt);

  gcc_assert (len < sizeof str); /* Leave room for \0.  */

  vsprintf (str, fmt, p);

  va_end (p);

  return DEF_ATTR_STRING (str);

}

static rtx

attr_eq (const char *name, const char *value)

{

  return attr_rtx (EQ_ATTR, DEF_ATTR_STRING (name), DEF_ATTR_STRING (value));

}

static const char *

attr_numeral (int n)

{

  return XSTR (make_numeric_value (n), 0);

}

/* Return a permanent (possibly shared) copy of a string STR (not assumed

   to be null terminated) with LEN bytes.  */

static char *

attr_string (const char *str, int len)

{

  struct attr_hash *h;

  int hashcode;

  int i;

  char *new_str;

  /* Compute the hash code.  */

  hashcode = (len + 1) * 613 + (unsigned) str[0];

  for (i = 1; i <= len; i += 2)

    hashcode = ((hashcode * 613) + (unsigned) str[i]);

  if (hashcode < 0)

    hashcode = -hashcode;

  /* Search the table for the string.  */

  for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)

    if (h->hashcode == -hashcode && h->u.str[0] == str[0]

        && !strncmp (h->u.str, str, len))

      return h->u.str;                  /* <-- return if found.  */

  /* Not found; create a permanent copy and add it to the hash table.  */

  new_str = obstack_alloc (hash_obstack, len + 1);

  memcpy (new_str, str, len);

  new_str[len] = '\0';

  attr_hash_add_string (hashcode, new_str);

  return new_str;                       /* Return the new string.  */

}

/* Check two rtx's for equality of contents,

   taking advantage of the fact that if both are hashed

   then they can't be equal unless they are the same object.  */

static int

attr_equal_p (rtx x, rtx y)

{

  return (x == y || (! (ATTR_PERMANENT_P (x) && ATTR_PERMANENT_P (y))