tree.c

gcc-2.95.3 Linux下最常用的C编译器

      return type;
    }
  return build_qualified_type (type, type_quals);
}

/* Returns the canonical version of TYPE.  In other words, if TYPE is
   a typedef, returns the underlying type.  The cv-qualification of
   the type returned matches the type input; they will always be
   compatible types.  */

tree
canonical_type_variant (t)
     tree t;
{
  return cp_build_qualified_type (TYPE_MAIN_VARIANT (t), CP_TYPE_QUALS (t));
}

/* Add OFFSET to all base types of T.

   OFFSET, which is a type offset, is number of bytes.

   Note that we don't have to worry about having two paths to the
   same base type, since this type owns its association list.  */

static void
propagate_binfo_offsets (binfo, offset)
     tree binfo;
     tree offset;
{
  tree binfos = BINFO_BASETYPES (binfo);
  int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;

  for (i = 0; i < n_baselinks; /* note increment is done in the loop.  */)
    {
      tree base_binfo = TREE_VEC_ELT (binfos, i);

      if (TREE_VIA_VIRTUAL (base_binfo))
	i += 1;
      else
	{
	  int j;
	  tree delta = NULL_TREE;

	  for (j = i+1; j < n_baselinks; j++)
	    if (! TREE_VIA_VIRTUAL (TREE_VEC_ELT (binfos, j)))
	      {
		/* The next basetype offset must take into account the space
		   between the classes, not just the size of each class.  */
		delta = size_binop (MINUS_EXPR,
				    BINFO_OFFSET (TREE_VEC_ELT (binfos, j)),
				    BINFO_OFFSET (base_binfo));
		break;
	      }

#if 0
	  if (BINFO_OFFSET_ZEROP (base_binfo))
	    BINFO_OFFSET (base_binfo) = offset;
	  else
	    BINFO_OFFSET (base_binfo)
	      = size_binop (PLUS_EXPR, BINFO_OFFSET (base_binfo), offset);
#else
	  BINFO_OFFSET (base_binfo) = offset;
#endif

	  propagate_binfo_offsets (base_binfo, offset);

	  /* Go to our next class that counts for offset propagation.  */
	  i = j;
	  if (i < n_baselinks)
	    offset = size_binop (PLUS_EXPR, offset, delta);
	}
    }
}

/* Makes new binfos for the indirect bases under BINFO, and updates
   BINFO_OFFSET for them and their bases.  */

void
unshare_base_binfos (binfo)
     tree binfo;
{
  tree binfos = BINFO_BASETYPES (binfo);
  tree new_binfo;
  int j;

  if (binfos == NULL_TREE)
    return;

  /* Now unshare the structure beneath BINFO.  */
  for (j = TREE_VEC_LENGTH (binfos)-1;
       j >= 0; j--)
    {
      tree base_binfo = TREE_VEC_ELT (binfos, j);
      new_binfo = TREE_VEC_ELT (binfos, j)
	= make_binfo (BINFO_OFFSET (base_binfo),
		      base_binfo,
		      BINFO_VTABLE (base_binfo),
		      BINFO_VIRTUALS (base_binfo));
      TREE_VIA_PUBLIC (new_binfo) = TREE_VIA_PUBLIC (base_binfo);
      TREE_VIA_PROTECTED (new_binfo) = TREE_VIA_PROTECTED (base_binfo);
      TREE_VIA_VIRTUAL (new_binfo) = TREE_VIA_VIRTUAL (base_binfo);
      BINFO_INHERITANCE_CHAIN (new_binfo) = binfo;
      unshare_base_binfos (new_binfo);
    }
}

/* Finish the work of layout_record, now taking virtual bases into account.
   Also compute the actual offsets that our base classes will have.
   This must be performed after the fields are laid out, since virtual
   baseclasses must lay down at the end of the record.

   Returns the maximum number of virtual functions any of the
   baseclasses provide.  */

int
layout_basetypes (rec, max)
     tree rec;
     int max;
{
  tree binfos = TYPE_BINFO_BASETYPES (rec);
  int i, n_baseclasses = binfos ? TREE_VEC_LENGTH (binfos) : 0;

  tree vbase_types;

  unsigned int record_align = MAX (BITS_PER_UNIT, TYPE_ALIGN (rec));
  unsigned int desired_align;

  /* Record size so far is CONST_SIZE bits, where CONST_SIZE is an integer.  */
  register unsigned int const_size = 0;
  unsigned int nonvirtual_const_size;

#ifdef STRUCTURE_SIZE_BOUNDARY
  /* Packed structures don't need to have minimum size.  */
  if (! TYPE_PACKED (rec))
    record_align = MAX (record_align, STRUCTURE_SIZE_BOUNDARY);
#endif

  /* Get all the virtual base types that this type uses.  The
     TREE_VALUE slot holds the virtual baseclass type.  Note that
     get_vbase_types makes copies of the virtual base BINFOs, so that
     the vbase_types are unshared.  */
  vbase_types = CLASSTYPE_VBASECLASSES (rec);

  my_friendly_assert (TREE_CODE (TYPE_SIZE (rec)) == INTEGER_CST, 19970302);
  const_size = TREE_INT_CST_LOW (TYPE_SIZE (rec));

  nonvirtual_const_size = const_size;

  while (vbase_types)
    {
      tree basetype = BINFO_TYPE (vbase_types);
      tree offset;

      desired_align = TYPE_ALIGN (basetype);
      record_align = MAX (record_align, desired_align);

      if (const_size == 0)
	offset = integer_zero_node;
      else
	{
	  /* Give each virtual base type the alignment it wants.  */
	  const_size = CEIL (const_size, desired_align) * desired_align;
	  offset = size_int (CEIL (const_size, BITS_PER_UNIT));
	}

      if (CLASSTYPE_VSIZE (basetype) > max)
	max = CLASSTYPE_VSIZE (basetype);
      BINFO_OFFSET (vbase_types) = offset;

      /* Every virtual baseclass takes a least a UNIT, so that we can
	 take it's address and get something different for each base.  */
      const_size += MAX (BITS_PER_UNIT,
			 TREE_INT_CST_LOW (CLASSTYPE_SIZE (basetype)));

      vbase_types = TREE_CHAIN (vbase_types);
    }

  if (const_size)
    {
      /* Because a virtual base might take a single byte above,
	 we have to re-adjust the total size to make sure it is
	 a multiple of the alignment.  */
      /* Give the whole object the alignment it wants.  */
      const_size = CEIL (const_size, record_align) * record_align;
    }

  /* Set the alignment in the complete type.  We don't set CLASSTYPE_ALIGN
   here, as that is for this class, without any virtual base classes.  */
  TYPE_ALIGN (rec) = record_align;
  if (const_size != nonvirtual_const_size)
    {
      TYPE_SIZE (rec) = size_int (const_size);
      TYPE_SIZE_UNIT (rec) = size_binop (FLOOR_DIV_EXPR, TYPE_SIZE (rec),
                                         size_int (BITS_PER_UNIT));
    }

  /* Now propagate offset information throughout the lattice.  */
  for (i = 0; i < n_baseclasses; i++)
    {
      register tree base_binfo = TREE_VEC_ELT (binfos, i);
      register tree basetype = BINFO_TYPE (base_binfo);
      tree field = TYPE_FIELDS (rec);

      if (TREE_VIA_VIRTUAL (base_binfo))
	continue;

      my_friendly_assert (TREE_TYPE (field) == basetype, 23897);

      if (get_base_distance (basetype, rec, 0, (tree*)0) == -2)
	cp_warning ("direct base `%T' inaccessible in `%T' due to ambiguity",
		    basetype, rec);

      BINFO_OFFSET (base_binfo)
	= size_int (CEIL (TREE_INT_CST_LOW (DECL_FIELD_BITPOS (field)),
			  BITS_PER_UNIT));
      propagate_binfo_offsets (base_binfo, BINFO_OFFSET (base_binfo));
      TYPE_FIELDS (rec) = TREE_CHAIN (field);
    }

  for (vbase_types = CLASSTYPE_VBASECLASSES (rec); vbase_types;
       vbase_types = TREE_CHAIN (vbase_types))
    {
      BINFO_INHERITANCE_CHAIN (vbase_types) = TYPE_BINFO (rec);
      unshare_base_binfos (vbase_types);
      propagate_binfo_offsets (vbase_types, BINFO_OFFSET (vbase_types));

      if (extra_warnings)
	{
	  tree basetype = BINFO_TYPE (vbase_types);
	  if (get_base_distance (basetype, rec, 0, (tree*)0) == -2)
	    cp_warning ("virtual base `%T' inaccessible in `%T' due to ambiguity",
			basetype, rec);
	}
    }

  return max;
}

/* If the empty base field in DECL overlaps with a base of the same type in
   NEWDECL, which is either another base field or the first data field of
   the class, pad the base just before NEWDECL and return 1.  Otherwise,
   return 0.  */

static int
avoid_overlap (decl, newdecl)
     tree decl, newdecl;
{
  tree field;

  if (newdecl == NULL_TREE
      || ! types_overlap_p (TREE_TYPE (decl), TREE_TYPE (newdecl)))
    return 0;

  for (field = decl; TREE_CHAIN (field) && TREE_CHAIN (field) != newdecl;
       field = TREE_CHAIN (field))
    ;

  DECL_SIZE (field) = integer_one_node;

  return 1;
}

/* Returns a list of fields to stand in for the base class subobjects
   of REC.  These fields are later removed by layout_basetypes.  */

tree
build_base_fields (rec)
     tree rec;
{
  /* Chain to hold all the new FIELD_DECLs which stand in for base class
     subobjects.  */
  tree base_decls = NULL_TREE;
  tree binfos = TYPE_BINFO_BASETYPES (rec);
  int n_baseclasses = binfos ? TREE_VEC_LENGTH (binfos) : 0;
  tree decl, nextdecl;
  int i, saw_empty = 0;
  unsigned int base_align = 0;

  for (i = 0; i < n_baseclasses; ++i)
    {
      register tree base_binfo = TREE_VEC_ELT (binfos, i);
      register tree basetype = BINFO_TYPE (base_binfo);

      if (TYPE_SIZE (basetype) == 0)
	/* This error is now reported in xref_tag, thus giving better
	   location information.  */
	continue;

      if (TREE_VIA_VIRTUAL (base_binfo))
	continue;

      decl = build_lang_field_decl (FIELD_DECL, NULL_TREE, basetype);
      DECL_ARTIFICIAL (decl) = 1;
      DECL_FIELD_CONTEXT (decl) = DECL_CLASS_CONTEXT (decl) = rec;
      DECL_SIZE (decl) = CLASSTYPE_SIZE (basetype);
      DECL_ALIGN (decl) = CLASSTYPE_ALIGN (basetype);
      TREE_CHAIN (decl) = base_decls;
      base_decls = decl;

      if (! flag_new_abi)
	{
	  /* Brain damage for backwards compatibility.  For no good reason,
	     the old layout_basetypes made every base at least as large as
	     the alignment for the bases up to that point, gratuitously
	     wasting space.  So we do the same thing here.  */
	  base_align = MAX (base_align, DECL_ALIGN (decl));
	  DECL_SIZE (decl)
	    = size_int (MAX (TREE_INT_CST_LOW (DECL_SIZE (decl)),
			     (int) base_align));
	}
      else if (DECL_SIZE (decl) == integer_zero_node)
	saw_empty = 1;
    }

  /* Reverse the list of fields so we allocate the bases in the proper
     order.  */
  base_decls = nreverse (base_decls);

  /* In the presence of empty base classes, we run the risk of allocating
     two objects of the same class on top of one another.  Avoid that.  */
  if (flag_new_abi && saw_empty)
    for (decl = base_decls; decl; decl = TREE_CHAIN (decl))
      {
	if (DECL_SIZE (decl) == integer_zero_node)
	  {
	    /* First step through the following bases until we find
	       an overlap or a non-empty base.  */
	    for (nextdecl = TREE_CHAIN (decl); nextdecl;
		 nextdecl = TREE_CHAIN (nextdecl))
	      {
		if (avoid_overlap (decl, nextdecl)
		    || DECL_SIZE (nextdecl) != integer_zero_node)
		  goto nextbase;
	      }

	    /* If we're still looking, also check against the first
	       field.  */
	    for (nextdecl = TYPE_FIELDS (rec);
		 nextdecl && TREE_CODE (nextdecl) != FIELD_DECL;
		 nextdecl = TREE_CHAIN (nextdecl))
	      /* keep looking */;
	    avoid_overlap (decl, nextdecl);
	  }
      nextbase:;
      }

  return base_decls;
}

/* Returns list of virtual base class pointers in a FIELD_DECL chain.  */

tree
build_vbase_pointer_fields (rec)
     tree rec;
{
  /* Chain to hold all the new FIELD_DECLs which point at virtual
     base classes.  */
  tree vbase_decls = NULL_TREE;
  tree binfos = TYPE_BINFO_BASETYPES (rec);
  int n_baseclasses = binfos ? TREE_VEC_LENGTH (binfos) : 0;
  tree decl;
  int i;

  /* Handle basetypes almost like fields, but record their
     offsets differently.  */

  for (i = 0; i < n_baseclasses; i++)
    {
      register tree base_binfo = TREE_VEC_ELT (binfos, i);
      register tree basetype = BINFO_TYPE (base_binfo);

      if (TYPE_SIZE (basetype) == 0)
	/* This error is now reported in xref_tag, thus giving better
	   location information.  */
	continue;

      /* All basetypes are recorded in the association list of the
	 derived type.  */

      if (TREE_VIA_VIRTUAL (base_binfo))
	{
	  int j;
	  const char *name;

	  /* The offset for a virtual base class is only used in computing
	     virtual function tables and for initializing virtual base
	     pointers.  It is built once `get_vbase_types' is called.  */

	  /* If this basetype can come from another vbase pointer
	     without an additional indirection, we will share
	     that pointer.  If an indirection is involved, we
	     make our own pointer.  */
	  for (j = 0; j < n_baseclasses; j++)
	    {
	      tree other_base_binfo = TREE_VEC_ELT (binfos, j);
	      if (! TREE_VIA_VIRTUAL (other_base_binfo)
		  && binfo_member (basetype,
				   CLASSTYPE_VBASECLASSES (BINFO_TYPE
							   (other_base_binfo))
				   ))
		goto got_it;
	    }
	  FORMAT_VBASE_NAME (name, basetype);
	  decl = build_lang_field_decl (FIELD_DECL, get_identifier (name),
					build_pointer_type (basetype));
	  /* If you change any of the below, take a look at all the
	     other VFIELD_BASEs and VTABLE_BASEs in the code, and change
	     them too.  */
	  DECL_ASSEMBLER_NAME (decl) = get_identifier (VTABLE_BASE);
	  DECL_VIRTUAL_P (decl) = 1;
	  DECL_ARTIFICIAL (decl) = 1;
	  DECL_FIELD_CONTEXT (decl) = rec;
	  DECL_CLASS_CONTEXT (decl) = rec;
	  DECL_FCONTEXT (decl) = basetype;
	  DECL_SAVED_INSNS (decl) = NULL_RTX;
	  DECL_FIELD_SIZE (decl) = 0;
	  DECL_ALIGN (decl) = TYPE_ALIGN (ptr_type_node);
	  TREE_CHAIN (decl) = vbase_decls;
	  BINFO_VPTR_FIELD (base_binfo) = decl;
	  vbase_decls = decl;

	got_it:
	  /* The space this decl occupies has already been accounted for.  */
	  ;
	}
    }

  return vbase_decls;
}

/* Hashing of lists so that we don't make duplicates.
   The entry point is `list_hash_canon'.  */

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

struct list_hash
{
  struct list_hash *next;	/* Next structure in the bucket.  */
  int hashcode;			/* Hash code of this list.  */
  tree list;			/* The list recorded here.  */
};

/* Now here is the hash table.  When recording a list, 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 lists.
   While all these live in the same table, they are completely independent,
   and the hash code is computed differently for each of these.  */

#define TYPE_HASH_SIZE 59
static struct list_hash *list_hash_table[TYPE_HASH_SIZE];

/* Compute a hash code for a list (chain of TREE_LIST nodes
   with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
   TREE_COMMON slots), by adding the hash codes of the individual entries.  */

static int
list_hash (purpose, value, chain)
     tree purpose, value, chain;
{
  register int hashcode = 0;

  if (chain)
    hashcode += TYPE_HASH (chain);

  if (value)
    hashcode += TYPE_HASH (value);
  else
    hashcode += 1007;
  if (purpose)
    hashcode += TYPE_HASH (purpose);
  else
    hashcode += 1009;
  return hashcode;
}

/* Look in the type hash table for a type isomorphic to TYPE.
   If one is found, return it.  Otherwise return 0.  */

static tree
list_hash_lookup (hashcode, purpose, value, chain)
     int hashcode;
     tree purpose, value, chain;
{
  register struct list_hash *h;

  for (h = list_hash_table[hashcode % TYPE_HASH_SIZE]; h; h = h->next)
    if (h->hashcode == hashcode
	&& TREE_PURPOSE (h->list) == purpose
	&& TREE_VALUE (h->list) == value
	&& TREE_CHAIN (h->list) == chain)
      return h->list;
  return 0;
}

/* Add an entry to the list-hash-table
   for a list TYPE whose hash code is HASHCODE.  */

static void
list_hash_add (hashcode, list)