[pf3gnuchains/gcc-fork.git] / gcc / cp / class.c

/* Functions related to building classes and their related objects.
   Copyright (C) 1987, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
   Free Software Foundation, Inc.
   Contributed by Michael Tiemann (tiemann@cygnus.com)

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/>.  */


/* High-level class interface.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "cp-tree.h"
#include "flags.h"
#include "rtl.h"
#include "output.h"
#include "toplev.h"
#include "target.h"
#include "convert.h"
#include "cgraph.h"
#include "tree-dump.h"

/* The number of nested classes being processed.  If we are not in the
   scope of any class, this is zero.  */

int current_class_depth;

/* In order to deal with nested classes, we keep a stack of classes.
   The topmost entry is the innermost class, and is the entry at index
   CURRENT_CLASS_DEPTH  */

typedef struct class_stack_node {
  /* The name of the class.  */
  tree name;

  /* The _TYPE node for the class.  */
  tree type;

  /* The access specifier pending for new declarations in the scope of
     this class.  */
  tree access;

  /* If were defining TYPE, the names used in this class.  */
  splay_tree names_used;

  /* Nonzero if this class is no longer open, because of a call to
     push_to_top_level.  */
  size_t hidden;
}* class_stack_node_t;

typedef struct vtbl_init_data_s
{
  /* The base for which we're building initializers.  */
  tree binfo;
  /* The type of the most-derived type.  */
  tree derived;
  /* The binfo for the dynamic type. This will be TYPE_BINFO (derived),
     unless ctor_vtbl_p is true.  */
  tree rtti_binfo;
  /* The negative-index vtable initializers built up so far.  These
     are in order from least negative index to most negative index.  */
  tree inits;
  /* The last (i.e., most negative) entry in INITS.  */
  tree* last_init;
  /* The binfo for the virtual base for which we're building
     vcall offset initializers.  */
  tree vbase;
  /* The functions in vbase for which we have already provided vcall
     offsets.  */
  VEC(tree,gc) *fns;
  /* The vtable index of the next vcall or vbase offset.  */
  tree index;
  /* Nonzero if we are building the initializer for the primary
     vtable.  */
  int primary_vtbl_p;
  /* Nonzero if we are building the initializer for a construction
     vtable.  */
  int ctor_vtbl_p;
  /* True when adding vcall offset entries to the vtable.  False when
     merely computing the indices.  */
  bool generate_vcall_entries;
} vtbl_init_data;

/* The type of a function passed to walk_subobject_offsets.  */
typedef int (*subobject_offset_fn) (tree, tree, splay_tree);

/* The stack itself.  This is a dynamically resized array.  The
   number of elements allocated is CURRENT_CLASS_STACK_SIZE.  */
static int current_class_stack_size;
static class_stack_node_t current_class_stack;

/* The size of the largest empty class seen in this translation unit.  */
static GTY (()) tree sizeof_biggest_empty_class;

/* An array of all local classes present in this translation unit, in
   declaration order.  */
VEC(tree,gc) *local_classes;

static tree get_vfield_name (tree);
static void finish_struct_anon (tree);
static tree get_vtable_name (tree);
static tree get_basefndecls (tree, tree);
static int build_primary_vtable (tree, tree);
static int build_secondary_vtable (tree);
static void finish_vtbls (tree);
static void modify_vtable_entry (tree, tree, tree, tree, tree *);
static void finish_struct_bits (tree);
static int alter_access (tree, tree, tree);
static void handle_using_decl (tree, tree);
static tree dfs_modify_vtables (tree, void *);
static tree modify_all_vtables (tree, tree);
static void determine_primary_bases (tree);
static void finish_struct_methods (tree);
static void maybe_warn_about_overly_private_class (tree);
static int method_name_cmp (const void *, const void *);
static int resort_method_name_cmp (const void *, const void *);
static void add_implicitly_declared_members (tree, int, int);
static tree fixed_type_or_null (tree, int *, int *);
static tree build_simple_base_path (tree expr, tree binfo);
static tree build_vtbl_ref_1 (tree, tree);
static tree build_vtbl_initializer (tree, tree, tree, tree, int *);
static int count_fields (tree);
static int add_fields_to_record_type (tree, struct sorted_fields_type*, int);
static bool check_bitfield_decl (tree);
static void check_field_decl (tree, tree, int *, int *, int *);
static void check_field_decls (tree, tree *, int *, int *);
static tree *build_base_field (record_layout_info, tree, splay_tree, tree *);
static void build_base_fields (record_layout_info, splay_tree, tree *);
static void check_methods (tree);
static void remove_zero_width_bit_fields (tree);
static void check_bases (tree, int *, int *);
static void check_bases_and_members (tree);
static tree create_vtable_ptr (tree, tree *);
static void include_empty_classes (record_layout_info);
static void layout_class_type (tree, tree *);
static void propagate_binfo_offsets (tree, tree);
static void layout_virtual_bases (record_layout_info, splay_tree);
static void build_vbase_offset_vtbl_entries (tree, vtbl_init_data *);
static void add_vcall_offset_vtbl_entries_r (tree, vtbl_init_data *);
static void add_vcall_offset_vtbl_entries_1 (tree, vtbl_init_data *);
static void build_vcall_offset_vtbl_entries (tree, vtbl_init_data *);
static void add_vcall_offset (tree, tree, vtbl_init_data *);
static void layout_vtable_decl (tree, int);
static tree dfs_find_final_overrider_pre (tree, void *);
static tree dfs_find_final_overrider_post (tree, void *);
static tree find_final_overrider (tree, tree, tree);
static int make_new_vtable (tree, tree);
static tree get_primary_binfo (tree);
static int maybe_indent_hierarchy (FILE *, int, int);
static tree dump_class_hierarchy_r (FILE *, int, tree, tree, int);
static void dump_class_hierarchy (tree);
static void dump_class_hierarchy_1 (FILE *, int, tree);
static void dump_array (FILE *, tree);
static void dump_vtable (tree, tree, tree);
static void dump_vtt (tree, tree);
static void dump_thunk (FILE *, int, tree);
static tree build_vtable (tree, tree, tree);
static void initialize_vtable (tree, tree);
static void layout_nonempty_base_or_field (record_layout_info,
                                           tree, tree, splay_tree);
static tree end_of_class (tree, int);
static bool layout_empty_base (record_layout_info, tree, tree, splay_tree);
static void accumulate_vtbl_inits (tree, tree, tree, tree, tree);
static tree dfs_accumulate_vtbl_inits (tree, tree, tree, tree,
                                               tree);
static void build_rtti_vtbl_entries (tree, vtbl_init_data *);
static void build_vcall_and_vbase_vtbl_entries (tree, vtbl_init_data *);
static void clone_constructors_and_destructors (tree);
static tree build_clone (tree, tree);
static void update_vtable_entry_for_fn (tree, tree, tree, tree *, unsigned);
static void build_ctor_vtbl_group (tree, tree);
static void build_vtt (tree);
static tree binfo_ctor_vtable (tree);
static tree *build_vtt_inits (tree, tree, tree *, tree *);
static tree dfs_build_secondary_vptr_vtt_inits (tree, void *);
static tree dfs_fixup_binfo_vtbls (tree, void *);
static int record_subobject_offset (tree, tree, splay_tree);
static int check_subobject_offset (tree, tree, splay_tree);
static int walk_subobject_offsets (tree, subobject_offset_fn,
                                   tree, splay_tree, tree, int);
static void record_subobject_offsets (tree, tree, splay_tree, bool);
static int layout_conflict_p (tree, tree, splay_tree, int);
static int splay_tree_compare_integer_csts (splay_tree_key k1,
                                            splay_tree_key k2);
static void warn_about_ambiguous_bases (tree);
static bool type_requires_array_cookie (tree);
static bool contains_empty_class_p (tree);
static bool base_derived_from (tree, tree);
static int empty_base_at_nonzero_offset_p (tree, tree, splay_tree);
static tree end_of_base (tree);
static tree get_vcall_index (tree, tree);

/* Variables shared between class.c and call.c.  */

#ifdef GATHER_STATISTICS
int n_vtables = 0;
int n_vtable_entries = 0;
int n_vtable_searches = 0;
int n_vtable_elems = 0;
int n_convert_harshness = 0;
int n_compute_conversion_costs = 0;
int n_inner_fields_searched = 0;
#endif

/* Convert to or from a base subobject.  EXPR is an expression of type
   `A' or `A*', an expression of type `B' or `B*' is returned.  To
   convert A to a base B, CODE is PLUS_EXPR and BINFO is the binfo for
   the B base instance within A.  To convert base A to derived B, CODE
   is MINUS_EXPR and BINFO is the binfo for the A instance within B.
   In this latter case, A must not be a morally virtual base of B.
   NONNULL is true if EXPR is known to be non-NULL (this is only
   needed when EXPR is of pointer type).  CV qualifiers are preserved
   from EXPR.  */

tree
build_base_path (enum tree_code code,
                 tree expr,
                 tree binfo,
                 int nonnull)
{
  tree v_binfo = NULL_TREE;
  tree d_binfo = NULL_TREE;
  tree probe;
  tree offset;
  tree target_type;
  tree null_test = NULL;
  tree ptr_target_type;
  int fixed_type_p;
  int want_pointer = TREE_CODE (TREE_TYPE (expr)) == POINTER_TYPE;
  bool has_empty = false;
  bool virtual_access;

  if (expr == error_mark_node || binfo == error_mark_node || !binfo)
    return error_mark_node;

  for (probe = binfo; probe; probe = BINFO_INHERITANCE_CHAIN (probe))
    {
      d_binfo = probe;
      if (is_empty_class (BINFO_TYPE (probe)))
        has_empty = true;
      if (!v_binfo && BINFO_VIRTUAL_P (probe))
        v_binfo = probe;
    }

  probe = TYPE_MAIN_VARIANT (TREE_TYPE (expr));
  if (want_pointer)
    probe = TYPE_MAIN_VARIANT (TREE_TYPE (probe));

  gcc_assert ((code == MINUS_EXPR
               && SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), probe))
              || (code == PLUS_EXPR
                  && SAME_BINFO_TYPE_P (BINFO_TYPE (d_binfo), probe)));

  if (binfo == d_binfo)
    /* Nothing to do.  */
    return expr;

  if (code == MINUS_EXPR && v_binfo)
    {
      error ("cannot convert from base %qT to derived type %qT via virtual base %qT",
             BINFO_TYPE (binfo), BINFO_TYPE (d_binfo), BINFO_TYPE (v_binfo));
      return error_mark_node;
    }

  if (!want_pointer)
    /* This must happen before the call to save_expr.  */
    expr = cp_build_unary_op (ADDR_EXPR, expr, 0, tf_warning_or_error);

  offset = BINFO_OFFSET (binfo);
  fixed_type_p = resolves_to_fixed_type_p (expr, &nonnull);
  target_type = code == PLUS_EXPR ? BINFO_TYPE (binfo) : BINFO_TYPE (d_binfo);

  /* Do we need to look in the vtable for the real offset?  */
  virtual_access = (v_binfo && fixed_type_p <= 0);

  /* Don't bother with the calculations inside sizeof; they'll ICE if the
     source type is incomplete and the pointer value doesn't matter.  */
  if (cp_unevaluated_operand != 0)
    {
      expr = build_nop (build_pointer_type (target_type), expr);
      if (!want_pointer)
        expr = build_indirect_ref (EXPR_LOCATION (expr), expr, RO_NULL);
      return expr;
    }

  /* Do we need to check for a null pointer?  */
  if (want_pointer && !nonnull)
    {
      /* If we know the conversion will not actually change the value
         of EXPR, then we can avoid testing the expression for NULL.
         We have to avoid generating a COMPONENT_REF for a base class
         field, because other parts of the compiler know that such
         expressions are always non-NULL.  */
      if (!virtual_access && integer_zerop (offset))
        {
          tree class_type;
          /* TARGET_TYPE has been extracted from BINFO, and, is
             therefore always cv-unqualified.  Extract the
             cv-qualifiers from EXPR so that the expression returned
             matches the input.  */
          class_type = TREE_TYPE (TREE_TYPE (expr));
          target_type
            = cp_build_qualified_type (target_type,
                                       cp_type_quals (class_type));
          return build_nop (build_pointer_type (target_type), expr);
        }
      null_test = error_mark_node;
    }

  /* Protect against multiple evaluation if necessary.  */
  if (TREE_SIDE_EFFECTS (expr) && (null_test || virtual_access))
    expr = save_expr (expr);

  /* Now that we've saved expr, build the real null test.  */
  if (null_test)
    {
      tree zero = cp_convert (TREE_TYPE (expr), integer_zero_node);
      null_test = fold_build2_loc (input_location, NE_EXPR, boolean_type_node,
                               expr, zero);
    }

  /* If this is a simple base reference, express it as a COMPONENT_REF.  */
  if (code == PLUS_EXPR && !virtual_access
      /* We don't build base fields for empty bases, and they aren't very
         interesting to the optimizers anyway.  */
      && !has_empty)
    {
      expr = cp_build_indirect_ref (expr, RO_NULL, tf_warning_or_error);
      expr = build_simple_base_path (expr, binfo);
      if (want_pointer)
        expr = build_address (expr);
      target_type = TREE_TYPE (expr);
      goto out;
    }

  if (virtual_access)
    {
      /* Going via virtual base V_BINFO.  We need the static offset
         from V_BINFO to BINFO, and the dynamic offset from D_BINFO to
         V_BINFO.  That offset is an entry in D_BINFO's vtable.  */
      tree v_offset;

      if (fixed_type_p < 0 && in_base_initializer)
        {
          /* In a base member initializer, we cannot rely on the
             vtable being set up.  We have to indirect via the
             vtt_parm.  */
          tree t;

          t = TREE_TYPE (TYPE_VFIELD (current_class_type));
          t = build_pointer_type (t);
          v_offset = convert (t, current_vtt_parm);
          v_offset = cp_build_indirect_ref (v_offset, RO_NULL, 
                                            tf_warning_or_error);
        }
      else
        v_offset = build_vfield_ref (cp_build_indirect_ref (expr, RO_NULL,
                                                            tf_warning_or_error),
                                     TREE_TYPE (TREE_TYPE (expr)));

      v_offset = build2 (POINTER_PLUS_EXPR, TREE_TYPE (v_offset),
                         v_offset, fold_convert (sizetype, BINFO_VPTR_FIELD (v_binfo)));
      v_offset = build1 (NOP_EXPR,
                         build_pointer_type (ptrdiff_type_node),
                         v_offset);
      v_offset = cp_build_indirect_ref (v_offset, RO_NULL, tf_warning_or_error);
      TREE_CONSTANT (v_offset) = 1;

      offset = convert_to_integer (ptrdiff_type_node,
                                   size_diffop_loc (input_location, offset,
                                                BINFO_OFFSET (v_binfo)));

      if (!integer_zerop (offset))
        v_offset = build2 (code, ptrdiff_type_node, v_offset, offset);

      if (fixed_type_p < 0)
        /* Negative fixed_type_p means this is a constructor or destructor;
           virtual base layout is fixed in in-charge [cd]tors, but not in
           base [cd]tors.  */
        offset = build3 (COND_EXPR, ptrdiff_type_node,
                         build2 (EQ_EXPR, boolean_type_node,
                                 current_in_charge_parm, integer_zero_node),
                         v_offset,
                         convert_to_integer (ptrdiff_type_node,
                                             BINFO_OFFSET (binfo)));
      else
        offset = v_offset;
    }

  target_type = cp_build_qualified_type
    (target_type, cp_type_quals (TREE_TYPE (TREE_TYPE (expr))));
  ptr_target_type = build_pointer_type (target_type);
  if (want_pointer)
    target_type = ptr_target_type;

  expr = build1 (NOP_EXPR, ptr_target_type, expr);

  if (!integer_zerop (offset))
    {
      offset = fold_convert (sizetype, offset);
      if (code == MINUS_EXPR)
        offset = fold_build1_loc (input_location, NEGATE_EXPR, sizetype, offset);
      expr = build2 (POINTER_PLUS_EXPR, ptr_target_type, expr, offset);
    }
  else
    null_test = NULL;

  if (!want_pointer)
    expr = cp_build_indirect_ref (expr, RO_NULL, tf_warning_or_error);

 out:
  if (null_test)
    expr = fold_build3_loc (input_location, COND_EXPR, target_type, null_test, expr,
                        fold_build1_loc (input_location, NOP_EXPR, target_type,
                                     integer_zero_node));

  return expr;
}

/* Subroutine of build_base_path; EXPR and BINFO are as in that function.
   Perform a derived-to-base conversion by recursively building up a
   sequence of COMPONENT_REFs to the appropriate base fields.  */

static tree
build_simple_base_path (tree expr, tree binfo)
{
  tree type = BINFO_TYPE (binfo);
  tree d_binfo = BINFO_INHERITANCE_CHAIN (binfo);
  tree field;

  if (d_binfo == NULL_TREE)
    {
      tree temp;

      gcc_assert (TYPE_MAIN_VARIANT (TREE_TYPE (expr)) == type);

      /* Transform `(a, b).x' into `(*(a, &b)).x', `(a ? b : c).x'
         into `(*(a ?  &b : &c)).x', and so on.  A COND_EXPR is only
         an lvalue in the front end; only _DECLs and _REFs are lvalues
         in the back end.  */
      temp = unary_complex_lvalue (ADDR_EXPR, expr);
      if (temp)
        expr = cp_build_indirect_ref (temp, RO_NULL, tf_warning_or_error);

      return expr;
    }

  /* Recurse.  */
  expr = build_simple_base_path (expr, d_binfo);

  for (field = TYPE_FIELDS (BINFO_TYPE (d_binfo));
       field; field = TREE_CHAIN (field))
    /* Is this the base field created by build_base_field?  */
    if (TREE_CODE (field) == FIELD_DECL
        && DECL_FIELD_IS_BASE (field)
        && TREE_TYPE (field) == type)
      {
        /* We don't use build_class_member_access_expr here, as that
           has unnecessary checks, and more importantly results in
           recursive calls to dfs_walk_once.  */
        int type_quals = cp_type_quals (TREE_TYPE (expr));

        expr = build3 (COMPONENT_REF,
                       cp_build_qualified_type (type, type_quals),
                       expr, field, NULL_TREE);
        expr = fold_if_not_in_template (expr);

        /* Mark the expression const or volatile, as appropriate.
           Even though we've dealt with the type above, we still have
           to mark the expression itself.  */
        if (type_quals & TYPE_QUAL_CONST)
          TREE_READONLY (expr) = 1;
        if (type_quals & TYPE_QUAL_VOLATILE)
          TREE_THIS_VOLATILE (expr) = 1;

        return expr;
      }

  /* Didn't find the base field?!?  */
  gcc_unreachable ();
}

/* Convert OBJECT to the base TYPE.  OBJECT is an expression whose
   type is a class type or a pointer to a class type.  In the former
   case, TYPE is also a class type; in the latter it is another
   pointer type.  If CHECK_ACCESS is true, an error message is emitted
   if TYPE is inaccessible.  If OBJECT has pointer type, the value is
   assumed to be non-NULL.  */

tree
convert_to_base (tree object, tree type, bool check_access, bool nonnull,
                 tsubst_flags_t complain)
{
  tree binfo;
  tree object_type;
  base_access access;

  if (TYPE_PTR_P (TREE_TYPE (object)))
    {
      object_type = TREE_TYPE (TREE_TYPE (object));
      type = TREE_TYPE (type);
    }
  else
    object_type = TREE_TYPE (object);

  access = check_access ? ba_check : ba_unique;
  if (!(complain & tf_error))
    access |= ba_quiet;
  binfo = lookup_base (object_type, type,
                       access,
                       NULL);
  if (!binfo || binfo == error_mark_node)
    return error_mark_node;

  return build_base_path (PLUS_EXPR, object, binfo, nonnull);
}

/* EXPR is an expression with unqualified class type.  BASE is a base
   binfo of that class type.  Returns EXPR, converted to the BASE
   type.  This function assumes that EXPR is the most derived class;
   therefore virtual bases can be found at their static offsets.  */

tree
convert_to_base_statically (tree expr, tree base)
{
  tree expr_type;

  expr_type = TREE_TYPE (expr);
  if (!SAME_BINFO_TYPE_P (BINFO_TYPE (base), expr_type))
    {
      tree pointer_type;

      pointer_type = build_pointer_type (expr_type);

      /* We use fold_build2 and fold_convert below to simplify the trees
         provided to the optimizers.  It is not safe to call these functions
         when processing a template because they do not handle C++-specific
         trees.  */
      gcc_assert (!processing_template_decl);
      expr = cp_build_unary_op (ADDR_EXPR, expr, /*noconvert=*/1, 
                             tf_warning_or_error);
      if (!integer_zerop (BINFO_OFFSET (base)))
        expr = fold_build2_loc (input_location,
                            POINTER_PLUS_EXPR, pointer_type, expr,
                            fold_convert (sizetype, BINFO_OFFSET (base)));
      expr = fold_convert (build_pointer_type (BINFO_TYPE (base)), expr);
      expr = build_fold_indirect_ref_loc (input_location, expr);
    }

  return expr;
}

\f
tree
build_vfield_ref (tree datum, tree type)
{
  tree vfield, vcontext;

  if (datum == error_mark_node)
    return error_mark_node;

  /* First, convert to the requested type.  */
  if (!same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (datum), type))
    datum = convert_to_base (datum, type, /*check_access=*/false,
                             /*nonnull=*/true, tf_warning_or_error);

  /* Second, the requested type may not be the owner of its own vptr.
     If not, convert to the base class that owns it.  We cannot use
     convert_to_base here, because VCONTEXT may appear more than once
     in the inheritance hierarchy of TYPE, and thus direct conversion
     between the types may be ambiguous.  Following the path back up
     one step at a time via primary bases avoids the problem.  */
  vfield = TYPE_VFIELD (type);
  vcontext = DECL_CONTEXT (vfield);
  while (!same_type_ignoring_top_level_qualifiers_p (vcontext, type))
    {
      datum = build_simple_base_path (datum, CLASSTYPE_PRIMARY_BINFO (type));
      type = TREE_TYPE (datum);
    }

  return build3 (COMPONENT_REF, TREE_TYPE (vfield), datum, vfield, NULL_TREE);
}

/* Given an object INSTANCE, return an expression which yields the
   vtable element corresponding to INDEX.  There are many special
   cases for INSTANCE which we take care of here, mainly to avoid
   creating extra tree nodes when we don't have to.  */

static tree
build_vtbl_ref_1 (tree instance, tree idx)
{
  tree aref;
  tree vtbl = NULL_TREE;

  /* Try to figure out what a reference refers to, and
     access its virtual function table directly.  */

  int cdtorp = 0;
  tree fixed_type = fixed_type_or_null (instance, NULL, &cdtorp);

  tree basetype = non_reference (TREE_TYPE (instance));

  if (fixed_type && !cdtorp)
    {
      tree binfo = lookup_base (fixed_type, basetype,
                                ba_unique | ba_quiet, NULL);
      if (binfo)
        vtbl = unshare_expr (BINFO_VTABLE (binfo));
    }

  if (!vtbl)
    vtbl = build_vfield_ref (instance, basetype);

  aref = build_array_ref (input_location, vtbl, idx);
  TREE_CONSTANT (aref) |= TREE_CONSTANT (vtbl) && TREE_CONSTANT (idx);

  return aref;
}

tree
build_vtbl_ref (tree instance, tree idx)
{
  tree aref = build_vtbl_ref_1 (instance, idx);

  return aref;
}

/* Given a stable object pointer INSTANCE_PTR, return an expression which
   yields a function pointer corresponding to vtable element INDEX.  */

tree
build_vfn_ref (tree instance_ptr, tree idx)
{
  tree aref;

  aref = build_vtbl_ref_1 (cp_build_indirect_ref (instance_ptr, RO_NULL,
                                                  tf_warning_or_error), 
                           idx);

  /* When using function descriptors, the address of the
     vtable entry is treated as a function pointer.  */
  if (TARGET_VTABLE_USES_DESCRIPTORS)
    aref = build1 (NOP_EXPR, TREE_TYPE (aref),
                   cp_build_unary_op (ADDR_EXPR, aref, /*noconvert=*/1,
                                   tf_warning_or_error));

  /* Remember this as a method reference, for later devirtualization.  */
  aref = build3 (OBJ_TYPE_REF, TREE_TYPE (aref), aref, instance_ptr, idx);

  return aref;
}

/* Return the name of the virtual function table (as an IDENTIFIER_NODE)
   for the given TYPE.  */

static tree
get_vtable_name (tree type)
{
  return mangle_vtbl_for_type (type);
}

/* DECL is an entity associated with TYPE, like a virtual table or an
   implicitly generated constructor.  Determine whether or not DECL
   should have external or internal linkage at the object file
   level.  This routine does not deal with COMDAT linkage and other
   similar complexities; it simply sets TREE_PUBLIC if it possible for
   entities in other translation units to contain copies of DECL, in
   the abstract.  */

void
set_linkage_according_to_type (tree type, tree decl)
{
  /* If TYPE involves a local class in a function with internal
     linkage, then DECL should have internal linkage too.  Other local
     classes have no linkage -- but if their containing functions
     have external linkage, it makes sense for DECL to have external
     linkage too.  That will allow template definitions to be merged,
     for example.  */
  if (no_linkage_check (type, /*relaxed_p=*/true))
    {
      TREE_PUBLIC (decl) = 0;
      DECL_INTERFACE_KNOWN (decl) = 1;
    }
  else
    TREE_PUBLIC (decl) = 1;
}

/* Create a VAR_DECL for a primary or secondary vtable for CLASS_TYPE.
   (For a secondary vtable for B-in-D, CLASS_TYPE should be D, not B.)
   Use NAME for the name of the vtable, and VTABLE_TYPE for its type.  */

static tree
build_vtable (tree class_type, tree name, tree vtable_type)
{
  tree decl;

  decl = build_lang_decl (VAR_DECL, name, vtable_type);
  /* vtable names are already mangled; give them their DECL_ASSEMBLER_NAME
     now to avoid confusion in mangle_decl.  */
  SET_DECL_ASSEMBLER_NAME (decl, name);
  DECL_CONTEXT (decl) = class_type;
  DECL_ARTIFICIAL (decl) = 1;
  TREE_STATIC (decl) = 1;
  TREE_READONLY (decl) = 1;
  DECL_VIRTUAL_P (decl) = 1;
  DECL_ALIGN (decl) = TARGET_VTABLE_ENTRY_ALIGN;
  DECL_VTABLE_OR_VTT_P (decl) = 1;
  /* At one time the vtable info was grabbed 2 words at a time.  This
     fails on sparc unless you have 8-byte alignment.  (tiemann) */
  DECL_ALIGN (decl) = MAX (TYPE_ALIGN (double_type_node),
                           DECL_ALIGN (decl));
  set_linkage_according_to_type (class_type, decl);
  /* The vtable has not been defined -- yet.  */
  DECL_EXTERNAL (decl) = 1;
  DECL_NOT_REALLY_EXTERN (decl) = 1;

  /* Mark the VAR_DECL node representing the vtable itself as a
     "gratuitous" one, thereby forcing dwarfout.c to ignore it.  It
     is rather important that such things be ignored because any
     effort to actually generate DWARF for them will run into
     trouble when/if we encounter code like:

     #pragma interface
     struct S { virtual void member (); };

     because the artificial declaration of the vtable itself (as
     manufactured by the g++ front end) will say that the vtable is
     a static member of `S' but only *after* the debug output for
     the definition of `S' has already been output.  This causes
     grief because the DWARF entry for the definition of the vtable
     will try to refer back to an earlier *declaration* of the
     vtable as a static member of `S' and there won't be one.  We
     might be able to arrange to have the "vtable static member"
     attached to the member list for `S' before the debug info for
     `S' get written (which would solve the problem) but that would
     require more intrusive changes to the g++ front end.  */
  DECL_IGNORED_P (decl) = 1;

  return decl;
}

/* Get the VAR_DECL of the vtable for TYPE. TYPE need not be polymorphic,
   or even complete.  If this does not exist, create it.  If COMPLETE is
   nonzero, then complete the definition of it -- that will render it
   impossible to actually build the vtable, but is useful to get at those
   which are known to exist in the runtime.  */

tree
get_vtable_decl (tree type, int complete)
{
  tree decl;

  if (CLASSTYPE_VTABLES (type))
    return CLASSTYPE_VTABLES (type);

  decl = build_vtable (type, get_vtable_name (type), vtbl_type_node);
  CLASSTYPE_VTABLES (type) = decl;

  if (complete)
    {
      DECL_EXTERNAL (decl) = 1;
      cp_finish_decl (decl, NULL_TREE, false, NULL_TREE, 0);
    }

  return decl;
}

/* Build the primary virtual function table for TYPE.  If BINFO is
   non-NULL, build the vtable starting with the initial approximation
   that it is the same as the one which is the head of the association
   list.  Returns a nonzero value if a new vtable is actually
   created.  */

static int
build_primary_vtable (tree binfo, tree type)
{
  tree decl;
  tree virtuals;

  decl = get_vtable_decl (type, /*complete=*/0);

  if (binfo)
    {
      if (BINFO_NEW_VTABLE_MARKED (binfo))
        /* We have already created a vtable for this base, so there's
           no need to do it again.  */
        return 0;

      virtuals = copy_list (BINFO_VIRTUALS (binfo));
      TREE_TYPE (decl) = TREE_TYPE (get_vtbl_decl_for_binfo (binfo));
      DECL_SIZE (decl) = TYPE_SIZE (TREE_TYPE (decl));
      DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (TREE_TYPE (decl));
    }
  else
    {
      gcc_assert (TREE_TYPE (decl) == vtbl_type_node);
      virtuals = NULL_TREE;
    }

#ifdef GATHER_STATISTICS
  n_vtables += 1;
  n_vtable_elems += list_length (virtuals);
#endif

  /* Initialize the association list for this type, based
     on our first approximation.  */
  BINFO_VTABLE (TYPE_BINFO (type)) = decl;
  BINFO_VIRTUALS (TYPE_BINFO (type)) = virtuals;
  SET_BINFO_NEW_VTABLE_MARKED (TYPE_BINFO (type));
  return 1;
}

/* Give BINFO a new virtual function table which is initialized
   with a skeleton-copy of its original initialization.  The only
   entry that changes is the `delta' entry, so we can really
   share a lot of structure.

   FOR_TYPE is the most derived type which caused this table to
   be needed.

   Returns nonzero if we haven't met BINFO before.

   The order in which vtables are built (by calling this function) for
   an object must remain the same, otherwise a binary incompatibility
   can result.  */

static int
build_secondary_vtable (tree binfo)
{
  if (BINFO_NEW_VTABLE_MARKED (binfo))
    /* We already created a vtable for this base.  There's no need to
       do it again.  */
    return 0;

  /* Remember that we've created a vtable for this BINFO, so that we
     don't try to do so again.  */
  SET_BINFO_NEW_VTABLE_MARKED (binfo);

  /* Make fresh virtual list, so we can smash it later.  */
  BINFO_VIRTUALS (binfo) = copy_list (BINFO_VIRTUALS (binfo));

  /* Secondary vtables are laid out as part of the same structure as
     the primary vtable.  */
  BINFO_VTABLE (binfo) = NULL_TREE;
  return 1;
}

/* Create a new vtable for BINFO which is the hierarchy dominated by
   T. Return nonzero if we actually created a new vtable.  */

static int
make_new_vtable (tree t, tree binfo)
{
  if (binfo == TYPE_BINFO (t))
    /* In this case, it is *type*'s vtable we are modifying.  We start
       with the approximation that its vtable is that of the
       immediate base class.  */
    return build_primary_vtable (binfo, t);
  else
    /* This is our very own copy of `basetype' to play with.  Later,
       we will fill in all the virtual functions that override the
       virtual functions in these base classes which are not defined
       by the current type.  */
    return build_secondary_vtable (binfo);
}

/* Make *VIRTUALS, an entry on the BINFO_VIRTUALS list for BINFO
   (which is in the hierarchy dominated by T) list FNDECL as its
   BV_FN.  DELTA is the required constant adjustment from the `this'
   pointer where the vtable entry appears to the `this' required when
   the function is actually called.  */

static void
modify_vtable_entry (tree t,
                     tree binfo,
                     tree fndecl,
                     tree delta,
                     tree *virtuals)
{
  tree v;

  v = *virtuals;

  if (fndecl != BV_FN (v)
      || !tree_int_cst_equal (delta, BV_DELTA (v)))
    {
      /* We need a new vtable for BINFO.  */
      if (make_new_vtable (t, binfo))
        {
          /* If we really did make a new vtable, we also made a copy
             of the BINFO_VIRTUALS list.  Now, we have to find the
             corresponding entry in that list.  */
          *virtuals = BINFO_VIRTUALS (binfo);
          while (BV_FN (*virtuals) != BV_FN (v))
            *virtuals = TREE_CHAIN (*virtuals);
          v = *virtuals;
        }

      BV_DELTA (v) = delta;
      BV_VCALL_INDEX (v) = NULL_TREE;
      BV_FN (v) = fndecl;
    }
}

\f
/* Add method METHOD to class TYPE.  If USING_DECL is non-null, it is
   the USING_DECL naming METHOD.  Returns true if the method could be
   added to the method vec.  */

bool
add_method (tree type, tree method, tree using_decl)
{
  unsigned slot;
  tree overload;
  bool template_conv_p = false;
  bool conv_p;
  VEC(tree,gc) *method_vec;
  bool complete_p;
  bool insert_p = false;
  tree current_fns;
  tree fns;

  if (method == error_mark_node)
    return false;

  complete_p = COMPLETE_TYPE_P (type);
  conv_p = DECL_CONV_FN_P (method);
  if (conv_p)
    template_conv_p = (TREE_CODE (method) == TEMPLATE_DECL
                       && DECL_TEMPLATE_CONV_FN_P (method));

  method_vec = CLASSTYPE_METHOD_VEC (type);
  if (!method_vec)
    {
      /* Make a new method vector.  We start with 8 entries.  We must
         allocate at least two (for constructors and destructors), and
         we're going to end up with an assignment operator at some
         point as well.  */
      method_vec = VEC_alloc (tree, gc, 8);
      /* Create slots for constructors and destructors.  */
      VEC_quick_push (tree, method_vec, NULL_TREE);
      VEC_quick_push (tree, method_vec, NULL_TREE);
      CLASSTYPE_METHOD_VEC (type) = method_vec;
    }

  /* Maintain TYPE_HAS_USER_CONSTRUCTOR, etc.  */
  grok_special_member_properties (method);

  /* Constructors and destructors go in special slots.  */
  if (DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (method))
    slot = CLASSTYPE_CONSTRUCTOR_SLOT;
  else if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (method))
    {
      slot = CLASSTYPE_DESTRUCTOR_SLOT;

      if (TYPE_FOR_JAVA (type))
        {
          if (!DECL_ARTIFICIAL (method))
            error ("Java class %qT cannot have a destructor", type);
          else if (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (type))
            error ("Java class %qT cannot have an implicit non-trivial "
                   "destructor",
                   type);
        }
    }
  else
    {
      tree m;

      insert_p = true;
      /* See if we already have an entry with this name.  */
      for (slot = CLASSTYPE_FIRST_CONVERSION_SLOT;
           VEC_iterate (tree, method_vec, slot, m);
           ++slot)
        {
          m = OVL_CURRENT (m);
          if (template_conv_p)
            {
              if (TREE_CODE (m) == TEMPLATE_DECL
                  && DECL_TEMPLATE_CONV_FN_P (m))
                insert_p = false;
              break;
            }
          if (conv_p && !DECL_CONV_FN_P (m))
            break;
          if (DECL_NAME (m) == DECL_NAME (method))
            {
              insert_p = false;
              break;
            }
          if (complete_p
              && !DECL_CONV_FN_P (m)
              && DECL_NAME (m) > DECL_NAME (method))
            break;
        }
    }
  current_fns = insert_p ? NULL_TREE : VEC_index (tree, method_vec, slot);

  /* Check to see if we've already got this method.  */
  for (fns = current_fns; fns; fns = OVL_NEXT (fns))
    {
      tree fn = OVL_CURRENT (fns);
      tree fn_type;
      tree method_type;
      tree parms1;
      tree parms2;

      if (TREE_CODE (fn) != TREE_CODE (method))
        continue;

      /* [over.load] Member function declarations with the
         same name and the same parameter types cannot be
         overloaded if any of them is a static member
         function declaration.

         [namespace.udecl] When a using-declaration brings names
         from a base class into a derived class scope, member
         functions in the derived class override and/or hide member
         functions with the same name and parameter types in a base
         class (rather than conflicting).  */
      fn_type = TREE_TYPE (fn);
      method_type = TREE_TYPE (method);
      parms1 = TYPE_ARG_TYPES (fn_type);
      parms2 = TYPE_ARG_TYPES (method_type);

      /* Compare the quals on the 'this' parm.  Don't compare
         the whole types, as used functions are treated as
         coming from the using class in overload resolution.  */
      if (! DECL_STATIC_FUNCTION_P (fn)
          && ! DECL_STATIC_FUNCTION_P (method)
          && TREE_TYPE (TREE_VALUE (parms1)) != error_mark_node
          && TREE_TYPE (TREE_VALUE (parms2)) != error_mark_node
          && (TYPE_QUALS (TREE_TYPE (TREE_VALUE (parms1)))
              != TYPE_QUALS (TREE_TYPE (TREE_VALUE (parms2)))))
        continue;

      /* For templates, the return type and template parameters
         must be identical.  */
      if (TREE_CODE (fn) == TEMPLATE_DECL
          && (!same_type_p (TREE_TYPE (fn_type),
                            TREE_TYPE (method_type))
              || !comp_template_parms (DECL_TEMPLATE_PARMS (fn),
                                       DECL_TEMPLATE_PARMS (method))))
        continue;

      if (! DECL_STATIC_FUNCTION_P (fn))
        parms1 = TREE_CHAIN (parms1);
      if (! DECL_STATIC_FUNCTION_P (method))
        parms2 = TREE_CHAIN (parms2);

      if (compparms (parms1, parms2)
          && (!DECL_CONV_FN_P (fn)
              || same_type_p (TREE_TYPE (fn_type),
                              TREE_TYPE (method_type))))
        {
          if (using_decl)
            {
              if (DECL_CONTEXT (fn) == type)
                /* Defer to the local function.  */
                return false;
              if (DECL_CONTEXT (fn) == DECL_CONTEXT (method))
                error ("repeated using declaration %q+D", using_decl);
              else
                error ("using declaration %q+D conflicts with a previous using declaration",
                       using_decl);
            }
          else
            {
              error ("%q+#D cannot be overloaded", method);
              error ("with %q+#D", fn);
            }

          /* We don't call duplicate_decls here to merge the
             declarations because that will confuse things if the
             methods have inline definitions.  In particular, we
             will crash while processing the definitions.  */
          return false;
        }
    }

  /* A class should never have more than one destructor.  */
  if (current_fns && DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (method))
    return false;

  /* Add the new binding.  */
  overload = build_overload (method, current_fns);

  if (conv_p)
    TYPE_HAS_CONVERSION (type) = 1;
  else if (slot >= CLASSTYPE_FIRST_CONVERSION_SLOT && !complete_p)
    push_class_level_binding (DECL_NAME (method), overload);

  if (insert_p)
    {
      bool reallocated;

      /* We only expect to add few methods in the COMPLETE_P case, so
         just make room for one more method in that case.  */
      if (complete_p)
        reallocated = VEC_reserve_exact (tree, gc, method_vec, 1);
      else
        reallocated = VEC_reserve (tree, gc, method_vec, 1);
      if (reallocated)
        CLASSTYPE_METHOD_VEC (type) = method_vec;
      if (slot == VEC_length (tree, method_vec))
        VEC_quick_push (tree, method_vec, overload);
      else
        VEC_quick_insert (tree, method_vec, slot, overload);
    }
  else
    /* Replace the current slot.  */
    VEC_replace (tree, method_vec, slot, overload);
  return true;
}

/* Subroutines of finish_struct.  */

/* Change the access of FDECL to ACCESS in T.  Return 1 if change was
   legit, otherwise return 0.  */

static int
alter_access (tree t, tree fdecl, tree access)
{
  tree elem;

  if (!DECL_LANG_SPECIFIC (fdecl))
    retrofit_lang_decl (fdecl);

  gcc_assert (!DECL_DISCRIMINATOR_P (fdecl));

  elem = purpose_member (t, DECL_ACCESS (fdecl));
  if (elem)
    {
      if (TREE_VALUE (elem) != access)
        {
          if (TREE_CODE (TREE_TYPE (fdecl)) == FUNCTION_DECL)
            error ("conflicting access specifications for method"
                   " %q+D, ignored", TREE_TYPE (fdecl));
          else
            error ("conflicting access specifications for field %qE, ignored",
                   DECL_NAME (fdecl));
        }
      else
        {
          /* They're changing the access to the same thing they changed
             it to before.  That's OK.  */
          ;
        }
    }
  else
    {
      perform_or_defer_access_check (TYPE_BINFO (t), fdecl, fdecl);
      DECL_ACCESS (fdecl) = tree_cons (t, access, DECL_ACCESS (fdecl));
      return 1;
    }
  return 0;
}

/* Process the USING_DECL, which is a member of T.  */

static void
handle_using_decl (tree using_decl, tree t)
{
  tree decl = USING_DECL_DECLS (using_decl);
  tree name = DECL_NAME (using_decl);
  tree access
    = TREE_PRIVATE (using_decl) ? access_private_node
    : TREE_PROTECTED (using_decl) ? access_protected_node
    : access_public_node;
  tree flist = NULL_TREE;
  tree old_value;

  gcc_assert (!processing_template_decl && decl);

  old_value = lookup_member (t, name, /*protect=*/0, /*want_type=*/false);
  if (old_value)
    {
      if (is_overloaded_fn (old_value))
        old_value = OVL_CURRENT (old_value);

      if (DECL_P (old_value) && DECL_CONTEXT (old_value) == t)
        /* OK */;
      else
        old_value = NULL_TREE;
    }

  cp_emit_debug_info_for_using (decl, USING_DECL_SCOPE (using_decl));

  if (is_overloaded_fn (decl))
    flist = decl;

  if (! old_value)
    ;
  else if (is_overloaded_fn (old_value))
    {
      if (flist)
        /* It's OK to use functions from a base when there are functions with
           the same name already present in the current class.  */;
      else
        {
          error ("%q+D invalid in %q#T", using_decl, t);
          error ("  because of local method %q+#D with same name",
                 OVL_CURRENT (old_value));
          return;
        }
    }
  else if (!DECL_ARTIFICIAL (old_value))
    {
      error ("%q+D invalid in %q#T", using_decl, t);
      error ("  because of local member %q+#D with same name", old_value);
      return;
    }

  /* Make type T see field decl FDECL with access ACCESS.  */
  if (flist)
    for (; flist; flist = OVL_NEXT (flist))
      {
        add_method (t, OVL_CURRENT (flist), using_decl);
        alter_access (t, OVL_CURRENT (flist), access);
      }
  else
    alter_access (t, decl, access);
}
\f
/* Run through the base classes of T, updating CANT_HAVE_CONST_CTOR_P,
   and NO_CONST_ASN_REF_P.  Also set flag bits in T based on
   properties of the bases.  */

static void
check_bases (tree t,
             int* cant_have_const_ctor_p,
             int* no_const_asn_ref_p)
{
  int i;
  int seen_non_virtual_nearly_empty_base_p;
  tree base_binfo;
  tree binfo;
  tree field = NULL_TREE;

  seen_non_virtual_nearly_empty_base_p = 0;

  if (!CLASSTYPE_NON_STD_LAYOUT (t))
    for (field = TYPE_FIELDS (t); field; field = TREE_CHAIN (field))
      if (TREE_CODE (field) == FIELD_DECL)
        break;

  for (binfo = TYPE_BINFO (t), i = 0;
       BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
    {
      tree basetype = TREE_TYPE (base_binfo);

      gcc_assert (COMPLETE_TYPE_P (basetype));

      /* Effective C++ rule 14.  We only need to check TYPE_POLYMORPHIC_P
         here because the case of virtual functions but non-virtual
         dtor is handled in finish_struct_1.  */
      if (!TYPE_POLYMORPHIC_P (basetype))
        warning (OPT_Weffc__,
                 "base class %q#T has a non-virtual destructor", basetype);

      /* If the base class doesn't have copy constructors or
         assignment operators that take const references, then the
         derived class cannot have such a member automatically
         generated.  */
      if (! TYPE_HAS_CONST_INIT_REF (basetype))
        *cant_have_const_ctor_p = 1;
      if (TYPE_HAS_ASSIGN_REF (basetype)
          && !TYPE_HAS_CONST_ASSIGN_REF (basetype))
        *no_const_asn_ref_p = 1;

      if (BINFO_VIRTUAL_P (base_binfo))
        /* A virtual base does not effect nearly emptiness.  */
        ;
      else if (CLASSTYPE_NEARLY_EMPTY_P (basetype))
        {
          if (seen_non_virtual_nearly_empty_base_p)
            /* And if there is more than one nearly empty base, then the
               derived class is not nearly empty either.  */
            CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
          else
            /* Remember we've seen one.  */
            seen_non_virtual_nearly_empty_base_p = 1;
        }
      else if (!is_empty_class (basetype))
        /* If the base class is not empty or nearly empty, then this
           class cannot be nearly empty.  */
        CLASSTYPE_NEARLY_EMPTY_P (t) = 0;

      /* A lot of properties from the bases also apply to the derived
         class.  */
      TYPE_NEEDS_CONSTRUCTING (t) |= TYPE_NEEDS_CONSTRUCTING (basetype);
      TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
        |= TYPE_HAS_NONTRIVIAL_DESTRUCTOR (basetype);
      TYPE_HAS_COMPLEX_ASSIGN_REF (t)
        |= TYPE_HAS_COMPLEX_ASSIGN_REF (basetype);
      TYPE_HAS_COMPLEX_INIT_REF (t) |= TYPE_HAS_COMPLEX_INIT_REF (basetype);
      TYPE_POLYMORPHIC_P (t) |= TYPE_POLYMORPHIC_P (basetype);
      CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t)
        |= CLASSTYPE_CONTAINS_EMPTY_CLASS_P (basetype);
      TYPE_HAS_COMPLEX_DFLT (t) |= TYPE_HAS_COMPLEX_DFLT (basetype);      

      /*  A standard-layout class is a class that:
          ...
          * has no non-standard-layout base classes,  */
      CLASSTYPE_NON_STD_LAYOUT (t) |= CLASSTYPE_NON_STD_LAYOUT (basetype);
      if (!CLASSTYPE_NON_STD_LAYOUT (t))
        {
          tree basefield;
          /* ...has no base classes of the same type as the first non-static
             data member...  */
          if (field && DECL_CONTEXT (field) == t
              && (same_type_ignoring_top_level_qualifiers_p
                  (TREE_TYPE (field), basetype)))
            CLASSTYPE_NON_STD_LAYOUT (t) = 1;
          else
            /* ...either has no non-static data members in the most-derived
               class and at most one base class with non-static data
               members, or has no base classes with non-static data
               members */
            for (basefield = TYPE_FIELDS (basetype); basefield;
                 basefield = TREE_CHAIN (basefield))
              if (TREE_CODE (basefield) == FIELD_DECL)
                {
                  if (field)
                    CLASSTYPE_NON_STD_LAYOUT (t) = 1;
                  else
                    field = basefield;
                  break;
                }
        }
    }
}

/* Determine all the primary bases within T.  Sets BINFO_PRIMARY_BASE_P for
   those that are primaries.  Sets BINFO_LOST_PRIMARY_P for those
   that have had a nearly-empty virtual primary base stolen by some
   other base in the hierarchy.  Determines CLASSTYPE_PRIMARY_BASE for
   T.  */

static void
determine_primary_bases (tree t)
{
  unsigned i;
  tree primary = NULL_TREE;
  tree type_binfo = TYPE_BINFO (t);
  tree base_binfo;

  /* Determine the primary bases of our bases.  */
  for (base_binfo = TREE_CHAIN (type_binfo); base_binfo;
       base_binfo = TREE_CHAIN (base_binfo))
    {
      tree primary = CLASSTYPE_PRIMARY_BINFO (BINFO_TYPE (base_binfo));

      /* See if we're the non-virtual primary of our inheritance
         chain.  */
      if (!BINFO_VIRTUAL_P (base_binfo))
        {
          tree parent = BINFO_INHERITANCE_CHAIN (base_binfo);
          tree parent_primary = CLASSTYPE_PRIMARY_BINFO (BINFO_TYPE (parent));

          if (parent_primary
              && SAME_BINFO_TYPE_P (BINFO_TYPE (base_binfo),
                                    BINFO_TYPE (parent_primary)))
            /* We are the primary binfo.  */
            BINFO_PRIMARY_P (base_binfo) = 1;
        }
      /* Determine if we have a virtual primary base, and mark it so.
       */
      if (primary && BINFO_VIRTUAL_P (primary))
        {
          tree this_primary = copied_binfo (primary, base_binfo);

          if (BINFO_PRIMARY_P (this_primary))
            /* Someone already claimed this base.  */
            BINFO_LOST_PRIMARY_P (base_binfo) = 1;
          else
            {
              tree delta;

              BINFO_PRIMARY_P (this_primary) = 1;
              BINFO_INHERITANCE_CHAIN (this_primary) = base_binfo;

              /* A virtual binfo might have been copied from within
                 another hierarchy. As we're about to use it as a
                 primary base, make sure the offsets match.  */
              delta = size_diffop_loc (input_location,
                                   convert (ssizetype,
                                            BINFO_OFFSET (base_binfo)),
                                   convert (ssizetype,
                                            BINFO_OFFSET (this_primary)));

              propagate_binfo_offsets (this_primary, delta);
            }
        }
    }

  /* First look for a dynamic direct non-virtual base.  */
  for (i = 0; BINFO_BASE_ITERATE (type_binfo, i, base_binfo); i++)
    {
      tree basetype = BINFO_TYPE (base_binfo);

      if (TYPE_CONTAINS_VPTR_P (basetype) && !BINFO_VIRTUAL_P (base_binfo))
        {
          primary = base_binfo;
          goto found;
        }
    }

  /* A "nearly-empty" virtual base class can be the primary base
     class, if no non-virtual polymorphic base can be found.  Look for
     a nearly-empty virtual dynamic base that is not already a primary
     base of something in the hierarchy.  If there is no such base,
     just pick the first nearly-empty virtual base.  */

  for (base_binfo = TREE_CHAIN (type_binfo); base_binfo;
       base_binfo = TREE_CHAIN (base_binfo))
    if (BINFO_VIRTUAL_P (base_binfo)
        && CLASSTYPE_NEARLY_EMPTY_P (BINFO_TYPE (base_binfo)))
      {
        if (!BINFO_PRIMARY_P (base_binfo))
          {
            /* Found one that is not primary.  */
            primary = base_binfo;
            goto found;
          }
        else if (!primary)
          /* Remember the first candidate.  */
          primary = base_binfo;
      }

 found:
  /* If we've got a primary base, use it.  */
  if (primary)
    {
      tree basetype = BINFO_TYPE (primary);

      CLASSTYPE_PRIMARY_BINFO (t) = primary;
      if (BINFO_PRIMARY_P (primary))
        /* We are stealing a primary base.  */
        BINFO_LOST_PRIMARY_P (BINFO_INHERITANCE_CHAIN (primary)) = 1;
      BINFO_PRIMARY_P (primary) = 1;
      if (BINFO_VIRTUAL_P (primary))
        {
          tree delta;

          BINFO_INHERITANCE_CHAIN (primary) = type_binfo;
          /* A virtual binfo might have been copied from within
             another hierarchy. As we're about to use it as a primary
             base, make sure the offsets match.  */
          delta = size_diffop_loc (input_location, ssize_int (0),
                               convert (ssizetype, BINFO_OFFSET (primary)));

          propagate_binfo_offsets (primary, delta);
        }

      primary = TYPE_BINFO (basetype);

      TYPE_VFIELD (t) = TYPE_VFIELD (basetype);
      BINFO_VTABLE (type_binfo) = BINFO_VTABLE (primary);
      BINFO_VIRTUALS (type_binfo) = BINFO_VIRTUALS (primary);
    }
}

/* Update the variant types of T.  */

void
fixup_type_variants (tree t)
{
  tree variants;

  if (!t)
    return;

  for (variants = TYPE_NEXT_VARIANT (t);
       variants;
       variants = TYPE_NEXT_VARIANT (variants))
    {
      /* These fields are in the _TYPE part of the node, not in
         the TYPE_LANG_SPECIFIC component, so they are not shared.  */
      TYPE_HAS_USER_CONSTRUCTOR (variants) = TYPE_HAS_USER_CONSTRUCTOR (t);
      TYPE_NEEDS_CONSTRUCTING (variants) = TYPE_NEEDS_CONSTRUCTING (t);
      TYPE_HAS_NONTRIVIAL_DESTRUCTOR (variants)
        = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t);

      TYPE_POLYMORPHIC_P (variants) = TYPE_POLYMORPHIC_P (t);

      TYPE_BINFO (variants) = TYPE_BINFO (t);

      /* Copy whatever these are holding today.  */
      TYPE_VFIELD (variants) = TYPE_VFIELD (t);
      TYPE_METHODS (variants) = TYPE_METHODS (t);
      TYPE_FIELDS (variants) = TYPE_FIELDS (t);

      /* All variants of a class have the same attributes.  */
      TYPE_ATTRIBUTES (variants) = TYPE_ATTRIBUTES (t);
    }
}

\f
/* Set memoizing fields and bits of T (and its variants) for later
   use.  */

static void
finish_struct_bits (tree t)
{
  /* Fix up variants (if any).  */
  fixup_type_variants (t);

  if (BINFO_N_BASE_BINFOS (TYPE_BINFO (t)) && TYPE_POLYMORPHIC_P (t))
    /* For a class w/o baseclasses, 'finish_struct' has set
       CLASSTYPE_PURE_VIRTUALS correctly (by definition).
       Similarly for a class whose base classes do not have vtables.
       When neither of these is true, we might have removed abstract
       virtuals (by providing a definition), added some (by declaring
       new ones), or redeclared ones from a base class.  We need to
       recalculate what's really an abstract virtual at this point (by
       looking in the vtables).  */
    get_pure_virtuals (t);

  /* If this type has a copy constructor or a destructor, force its
     mode to be BLKmode, and force its TREE_ADDRESSABLE bit to be
     nonzero.  This will cause it to be passed by invisible reference
     and prevent it from being returned in a register.  */
  if (! TYPE_HAS_TRIVIAL_INIT_REF (t) || TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t))
    {
      tree variants;
      DECL_MODE (TYPE_MAIN_DECL (t)) = BLKmode;
      for (variants = t; variants; variants = TYPE_NEXT_VARIANT (variants))
        {
          SET_TYPE_MODE (variants, BLKmode);
          TREE_ADDRESSABLE (variants) = 1;
        }
    }
}

/* Issue warnings about T having private constructors, but no friends,
   and so forth.

   HAS_NONPRIVATE_METHOD is nonzero if T has any non-private methods or
   static members.  HAS_NONPRIVATE_STATIC_FN is nonzero if T has any
   non-private static member functions.  */

static void
maybe_warn_about_overly_private_class (tree t)
{
  int has_member_fn = 0;
  int has_nonprivate_method = 0;
  tree fn;

  if (!warn_ctor_dtor_privacy
      /* If the class has friends, those entities might create and
         access instances, so we should not warn.  */
      || (CLASSTYPE_FRIEND_CLASSES (t)
          || DECL_FRIENDLIST (TYPE_MAIN_DECL (t)))
      /* We will have warned when the template was declared; there's
         no need to warn on every instantiation.  */
      || CLASSTYPE_TEMPLATE_INSTANTIATION (t))
    /* There's no reason to even consider warning about this
       class.  */
    return;

  /* We only issue one warning, if more than one applies, because
     otherwise, on code like:

     class A {
       // Oops - forgot `public:'
       A();
       A(const A&);
       ~A();
     };

     we warn several times about essentially the same problem.  */

  /* Check to see if all (non-constructor, non-destructor) member
     functions are private.  (Since there are no friends or
     non-private statics, we can't ever call any of the private member
     functions.)  */
  for (fn = TYPE_METHODS (t); fn; fn = TREE_CHAIN (fn))
    /* We're not interested in compiler-generated methods; they don't
       provide any way to call private members.  */
    if (!DECL_ARTIFICIAL (fn))
      {
        if (!TREE_PRIVATE (fn))
          {
            if (DECL_STATIC_FUNCTION_P (fn))
              /* A non-private static member function is just like a
                 friend; it can create and invoke private member
                 functions, and be accessed without a class
                 instance.  */
              return;

            has_nonprivate_method = 1;
            /* Keep searching for a static member function.  */
          }
        else if (!DECL_CONSTRUCTOR_P (fn) && !DECL_DESTRUCTOR_P (fn))
          has_member_fn = 1;
      }

  if (!has_nonprivate_method && has_member_fn)
    {
      /* There are no non-private methods, and there's at least one
         private member function that isn't a constructor or
         destructor.  (If all the private members are
         constructors/destructors we want to use the code below that
         issues error messages specifically referring to
         constructors/destructors.)  */
      unsigned i;
      tree binfo = TYPE_BINFO (t);

      for (i = 0; i != BINFO_N_BASE_BINFOS (binfo); i++)
        if (BINFO_BASE_ACCESS (binfo, i) != access_private_node)
          {
            has_nonprivate_method = 1;
            break;
          }
      if (!has_nonprivate_method)
        {
          warning (OPT_Wctor_dtor_privacy,
                   "all member functions in class %qT are private", t);
          return;
        }
    }

  /* Even if some of the member functions are non-private, the class
     won't be useful for much if all the constructors or destructors
     are private: such an object can never be created or destroyed.  */
  fn = CLASSTYPE_DESTRUCTORS (t);
  if (fn && TREE_PRIVATE (fn))
    {
      warning (OPT_Wctor_dtor_privacy,
               "%q#T only defines a private destructor and has no friends",
               t);
      return;
    }

  /* Warn about classes that have private constructors and no friends.  */
  if (TYPE_HAS_USER_CONSTRUCTOR (t)
      /* Implicitly generated constructors are always public.  */
      && (!CLASSTYPE_LAZY_DEFAULT_CTOR (t)
          || !CLASSTYPE_LAZY_COPY_CTOR (t)))
    {
      int nonprivate_ctor = 0;

      /* If a non-template class does not define a copy
         constructor, one is defined for it, enabling it to avoid
         this warning.  For a template class, this does not
         happen, and so we would normally get a warning on:

           template <class T> class C { private: C(); };

         To avoid this asymmetry, we check TYPE_HAS_INIT_REF.  All
         complete non-template or fully instantiated classes have this
         flag set.  */
      if (!TYPE_HAS_INIT_REF (t))
        nonprivate_ctor = 1;
      else
        for (fn = CLASSTYPE_CONSTRUCTORS (t); fn; fn = OVL_NEXT (fn))
          {
            tree ctor = OVL_CURRENT (fn);
            /* Ideally, we wouldn't count copy constructors (or, in
               fact, any constructor that takes an argument of the
               class type as a parameter) because such things cannot
               be used to construct an instance of the class unless
               you already have one.  But, for now at least, we're
               more generous.  */
            if (! TREE_PRIVATE (ctor))
              {
                nonprivate_ctor = 1;
                break;
              }
          }

      if (nonprivate_ctor == 0)
        {
          warning (OPT_Wctor_dtor_privacy,
                   "%q#T only defines private constructors and has no friends",
                   t);
          return;
        }
    }
}

static struct {
  gt_pointer_operator new_value;
  void *cookie;
} resort_data;

/* Comparison function to compare two TYPE_METHOD_VEC entries by name.  */

static int
method_name_cmp (const void* m1_p, const void* m2_p)
{
  const tree *const m1 = (const tree *) m1_p;
  const tree *const m2 = (const tree *) m2_p;

  if (*m1 == NULL_TREE && *m2 == NULL_TREE)
    return 0;
  if (*m1 == NULL_TREE)
    return -1;
  if (*m2 == NULL_TREE)
    return 1;
  if (DECL_NAME (OVL_CURRENT (*m1)) < DECL_NAME (OVL_CURRENT (*m2)))
    return -1;
  return 1;
}

/* This routine compares two fields like method_name_cmp but using the
   pointer operator in resort_field_decl_data.  */

static int
resort_method_name_cmp (const void* m1_p, const void* m2_p)
{
  const tree *const m1 = (const tree *) m1_p;
  const tree *const m2 = (const tree *) m2_p;
  if (*m1 == NULL_TREE && *m2 == NULL_TREE)
    return 0;
  if (*m1 == NULL_TREE)
    return -1;
  if (*m2 == NULL_TREE)
    return 1;
  {
    tree d1 = DECL_NAME (OVL_CURRENT (*m1));
    tree d2 = DECL_NAME (OVL_CURRENT (*m2));
    resort_data.new_value (&d1, resort_data.cookie);
    resort_data.new_value (&d2, resort_data.cookie);
    if (d1 < d2)
      return -1;
  }
  return 1;
}

/* Resort TYPE_METHOD_VEC because pointers have been reordered.  */

void
resort_type_method_vec (void* obj,
                        void* orig_obj ATTRIBUTE_UNUSED ,
                        gt_pointer_operator new_value,
                        void* cookie)
{
  VEC(tree,gc) *method_vec = (VEC(tree,gc) *) obj;
  int len = VEC_length (tree, method_vec);
  size_t slot;
  tree fn;

  /* The type conversion ops have to live at the front of the vec, so we
     can't sort them.  */
  for (slot = CLASSTYPE_FIRST_CONVERSION_SLOT;
       VEC_iterate (tree, method_vec, slot, fn);
       ++slot)
    if (!DECL_CONV_FN_P (OVL_CURRENT (fn)))
      break;

  if (len - slot > 1)
    {
      resort_data.new_value = new_value;
      resort_data.cookie = cookie;
      qsort (VEC_address (tree, method_vec) + slot, len - slot, sizeof (tree),
             resort_method_name_cmp);
    }
}

/* Warn about duplicate methods in fn_fields.

   Sort methods that are not special (i.e., constructors, destructors,
   and type conversion operators) so that we can find them faster in
   search.  */

static void
finish_struct_methods (tree t)
{
  tree fn_fields;
  VEC(tree,gc) *method_vec;
  int slot, len;

  method_vec = CLASSTYPE_METHOD_VEC (t);
  if (!method_vec)
    return;

  len = VEC_length (tree, method_vec);

  /* Clear DECL_IN_AGGR_P for all functions.  */
  for (fn_fields = TYPE_METHODS (t); fn_fields;
       fn_fields = TREE_CHAIN (fn_fields))
    DECL_IN_AGGR_P (fn_fields) = 0;

  /* Issue warnings about private constructors and such.  If there are
     no methods, then some public defaults are generated.  */
  maybe_warn_about_overly_private_class (t);

  /* The type conversion ops have to live at the front of the vec, so we
     can't sort them.  */
  for (slot = CLASSTYPE_FIRST_CONVERSION_SLOT;
       VEC_iterate (tree, method_vec, slot, fn_fields);
       ++slot)
    if (!DECL_CONV_FN_P (OVL_CURRENT (fn_fields)))
      break;
  if (len - slot > 1)
    qsort (VEC_address (tree, method_vec) + slot,
           len-slot, sizeof (tree), method_name_cmp);
}

/* Make BINFO's vtable have N entries, including RTTI entries,
   vbase and vcall offsets, etc.  Set its type and call the back end
   to lay it out.  */

static void
layout_vtable_decl (tree binfo, int n)
{
  tree atype;
  tree vtable;

  atype = build_cplus_array_type (vtable_entry_type,
                                  build_index_type (size_int (n - 1)));
  layout_type (atype);

  /* We may have to grow the vtable.  */
  vtable = get_vtbl_decl_for_binfo (binfo);
  if (!same_type_p (TREE_TYPE (vtable), atype))
    {
      TREE_TYPE (vtable) = atype;
      DECL_SIZE (vtable) = DECL_SIZE_UNIT (vtable) = NULL_TREE;
      layout_decl (vtable, 0);
    }
}

/* True iff FNDECL and BASE_FNDECL (both non-static member functions)
   have the same signature.  */

int
same_signature_p (const_tree fndecl, const_tree base_fndecl)
{
  /* One destructor overrides another if they are the same kind of
     destructor.  */
  if (DECL_DESTRUCTOR_P (base_fndecl) && DECL_DESTRUCTOR_P (fndecl)
      && special_function_p (base_fndecl) == special_function_p (fndecl))
    return 1;
  /* But a non-destructor never overrides a destructor, nor vice
     versa, nor do different kinds of destructors override
     one-another.  For example, a complete object destructor does not
     override a deleting destructor.  */
  if (DECL_DESTRUCTOR_P (base_fndecl) || DECL_DESTRUCTOR_P (fndecl))
    return 0;

  if (DECL_NAME (fndecl) == DECL_NAME (base_fndecl)
      || (DECL_CONV_FN_P (fndecl)
          && DECL_CONV_FN_P (base_fndecl)
          && same_type_p (DECL_CONV_FN_TYPE (fndecl),
                          DECL_CONV_FN_TYPE (base_fndecl))))
    {
      tree types, base_types;
      types = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
      base_types = TYPE_ARG_TYPES (TREE_TYPE (base_fndecl));
      if ((TYPE_QUALS (TREE_TYPE (TREE_VALUE (base_types)))
           == TYPE_QUALS (TREE_TYPE (TREE_VALUE (types))))
          && compparms (TREE_CHAIN (base_types), TREE_CHAIN (types)))
        return 1;
    }
  return 0;
}

/* Returns TRUE if DERIVED is a binfo containing the binfo BASE as a
   subobject.  */

static bool
base_derived_from (tree derived, tree base)
{
  tree probe;

  for (probe = base; probe; probe = BINFO_INHERITANCE_CHAIN (probe))
    {
      if (probe == derived)
        return true;
      else if (BINFO_VIRTUAL_P (probe))
        /* If we meet a virtual base, we can't follow the inheritance
           any more.  See if the complete type of DERIVED contains
           such a virtual base.  */
        return (binfo_for_vbase (BINFO_TYPE (probe), BINFO_TYPE (derived))
                != NULL_TREE);
    }
  return false;
}

typedef struct find_final_overrider_data_s {
  /* The function for which we are trying to find a final overrider.  */
  tree fn;
  /* The base class in which the function was declared.  */
  tree declaring_base;
  /* The candidate overriders.  */
  tree candidates;
  /* Path to most derived.  */
  VEC(tree,heap) *path;
} find_final_overrider_data;

/* Add the overrider along the current path to FFOD->CANDIDATES.
   Returns true if an overrider was found; false otherwise.  */

static bool
dfs_find_final_overrider_1 (tree binfo,
                            find_final_overrider_data *ffod,
                            unsigned depth)
{
  tree method;

  /* If BINFO is not the most derived type, try a more derived class.
     A definition there will overrider a definition here.  */
  if (depth)
    {
      depth--;
      if (dfs_find_final_overrider_1
          (VEC_index (tree, ffod->path, depth), ffod, depth))
        return true;
    }

  method = look_for_overrides_here (BINFO_TYPE (binfo), ffod->fn);
  if (method)
    {
      tree *candidate = &ffod->candidates;

      /* Remove any candidates overridden by this new function.  */
      while (*candidate)
        {
          /* If *CANDIDATE overrides METHOD, then METHOD
             cannot override anything else on the list.  */
          if (base_derived_from (TREE_VALUE (*candidate), binfo))
            return true;
          /* If METHOD overrides *CANDIDATE, remove *CANDIDATE.  */
          if (base_derived_from (binfo, TREE_VALUE (*candidate)))
            *candidate = TREE_CHAIN (*candidate);
          else
            candidate = &TREE_CHAIN (*candidate);
        }

      /* Add the new function.  */
      ffod->candidates = tree_cons (method, binfo, ffod->candidates);
      return true;
    }

  return false;
}

/* Called from find_final_overrider via dfs_walk.  */

static tree
dfs_find_final_overrider_pre (tree binfo, void *data)
{
  find_final_overrider_data *ffod = (find_final_overrider_data *) data;

  if (binfo == ffod->declaring_base)
    dfs_find_final_overrider_1 (binfo, ffod, VEC_length (tree, ffod->path));
  VEC_safe_push (tree, heap, ffod->path, binfo);

  return NULL_TREE;
}

static tree
dfs_find_final_overrider_post (tree binfo ATTRIBUTE_UNUSED, void *data)
{
  find_final_overrider_data *ffod = (find_final_overrider_data *) data;
  VEC_pop (tree, ffod->path);

  return NULL_TREE;
}

/* Returns a TREE_LIST whose TREE_PURPOSE is the final overrider for
   FN and whose TREE_VALUE is the binfo for the base where the
   overriding occurs.  BINFO (in the hierarchy dominated by the binfo
   DERIVED) is the base object in which FN is declared.  */

static tree
find_final_overrider (tree derived, tree binfo, tree fn)
{
  find_final_overrider_data ffod;

  /* Getting this right is a little tricky.  This is valid:

       struct S { virtual void f (); };
       struct T { virtual void f (); };
       struct U : public S, public T { };

     even though calling `f' in `U' is ambiguous.  But,

       struct R { virtual void f(); };
       struct S : virtual public R { virtual void f (); };
       struct T : virtual public R { virtual void f (); };
       struct U : public S, public T { };

     is not -- there's no way to decide whether to put `S::f' or
     `T::f' in the vtable for `R'.

     The solution is to look at all paths to BINFO.  If we find
     different overriders along any two, then there is a problem.  */
  if (DECL_THUNK_P (fn))
    fn = THUNK_TARGET (fn);

  /* Determine the depth of the hierarchy.  */
  ffod.fn = fn;
  ffod.declaring_base = binfo;
  ffod.candidates = NULL_TREE;
  ffod.path = VEC_alloc (tree, heap, 30);

  dfs_walk_all (derived, dfs_find_final_overrider_pre,
                dfs_find_final_overrider_post, &ffod);

  VEC_free (tree, heap, ffod.path);

  /* If there was no winner, issue an error message.  */
  if (!ffod.candidates || TREE_CHAIN (ffod.candidates))
    return error_mark_node;

  return ffod.candidates;
}

/* Return the index of the vcall offset for FN when TYPE is used as a
   virtual base.  */

static tree
get_vcall_index (tree fn, tree type)
{
  VEC(tree_pair_s,gc) *indices = CLASSTYPE_VCALL_INDICES (type);
  tree_pair_p p;
  unsigned ix;

  for (ix = 0; VEC_iterate (tree_pair_s, indices, ix, p); ix++)
    if ((DECL_DESTRUCTOR_P (fn) && DECL_DESTRUCTOR_P (p->purpose))
        || same_signature_p (fn, p->purpose))
      return p->value;

  /* There should always be an appropriate index.  */
  gcc_unreachable ();
}

/* Update an entry in the vtable for BINFO, which is in the hierarchy
   dominated by T.  FN has been overridden in BINFO; VIRTUALS points to the
   corresponding position in the BINFO_VIRTUALS list.  */

static void
update_vtable_entry_for_fn (tree t, tree binfo, tree fn, tree* virtuals,
                            unsigned ix)
{
  tree b;
  tree overrider;
  tree delta;
  tree virtual_base;
  tree first_defn;
  tree overrider_fn, overrider_target;
  tree target_fn = DECL_THUNK_P (fn) ? THUNK_TARGET (fn) : fn;
  tree over_return, base_return;
  bool lost = false;

  /* Find the nearest primary base (possibly binfo itself) which defines
     this function; this is the class the caller will convert to when
     calling FN through BINFO.  */
  for (b = binfo; ; b = get_primary_binfo (b))
    {
      gcc_assert (b);
      if (look_for_overrides_here (BINFO_TYPE (b), target_fn))
        break;

      /* The nearest definition is from a lost primary.  */
      if (BINFO_LOST_PRIMARY_P (b))
        lost = true;
    }
  first_defn = b;

  /* Find the final overrider.  */
  overrider = find_final_overrider (TYPE_BINFO (t), b, target_fn);
  if (overrider == error_mark_node)
    {
      error ("no unique final overrider for %qD in %qT", target_fn, t);
      return;
    }
  overrider_target = overrider_fn = TREE_PURPOSE (overrider);

  /* Check for adjusting covariant return types.  */
  over_return = TREE_TYPE (TREE_TYPE (overrider_target));
  base_return = TREE_TYPE (TREE_TYPE (target_fn));

  if (POINTER_TYPE_P (over_return)
      && TREE_CODE (over_return) == TREE_CODE (base_return)
      && CLASS_TYPE_P (TREE_TYPE (over_return))
      && CLASS_TYPE_P (TREE_TYPE (base_return))
      /* If the overrider is invalid, don't even try.  */
      && !DECL_INVALID_OVERRIDER_P (overrider_target))
    {
      /* If FN is a covariant thunk, we must figure out the adjustment
         to the final base FN was converting to. As OVERRIDER_TARGET might
         also be converting to the return type of FN, we have to
         combine the two conversions here.  */
      tree fixed_offset, virtual_offset;

      over_return = TREE_TYPE (over_return);
      base_return = TREE_TYPE (base_return);

      if (DECL_THUNK_P (fn))
        {
          gcc_assert (DECL_RESULT_THUNK_P (fn));
          fixed_offset = ssize_int (THUNK_FIXED_OFFSET (fn));
          virtual_offset = THUNK_VIRTUAL_OFFSET (fn);
        }
      else
        fixed_offset = virtual_offset = NULL_TREE;

      if (virtual_offset)
        /* Find the equivalent binfo within the return type of the
           overriding function. We will want the vbase offset from
           there.  */
        virtual_offset = binfo_for_vbase (BINFO_TYPE (virtual_offset),
                                          over_return);
      else if (!same_type_ignoring_top_level_qualifiers_p
               (over_return, base_return))
        {
          /* There was no existing virtual thunk (which takes
             precedence).  So find the binfo of the base function's
             return type within the overriding function's return type.
             We cannot call lookup base here, because we're inside a
             dfs_walk, and will therefore clobber the BINFO_MARKED
             flags.  Fortunately we know the covariancy is valid (it
             has already been checked), so we can just iterate along
             the binfos, which have been chained in inheritance graph
             order.  Of course it is lame that we have to repeat the
             search here anyway -- we should really be caching pieces
             of the vtable and avoiding this repeated work.  */
          tree thunk_binfo, base_binfo;

          /* Find the base binfo within the overriding function's
             return type.  We will always find a thunk_binfo, except
             when the covariancy is invalid (which we will have
             already diagnosed).  */
          for (base_binfo = TYPE_BINFO (base_return),
               thunk_binfo = TYPE_BINFO (over_return);
               thunk_binfo;
               thunk_binfo = TREE_CHAIN (thunk_binfo))
            if (SAME_BINFO_TYPE_P (BINFO_TYPE (thunk_binfo),
                                   BINFO_TYPE (base_binfo)))
              break;

          /* See if virtual inheritance is involved.  */
          for (virtual_offset = thunk_binfo;
               virtual_offset;
               virtual_offset = BINFO_INHERITANCE_CHAIN (virtual_offset))
            if (BINFO_VIRTUAL_P (virtual_offset))
              break;

          if (virtual_offset
              || (thunk_binfo && !BINFO_OFFSET_ZEROP (thunk_binfo)))
            {
              tree offset = convert (ssizetype, BINFO_OFFSET (thunk_binfo));

              if (virtual_offset)
                {
                  /* We convert via virtual base.  Adjust the fixed
                     offset to be from there.  */
                  offset = 
                    size_diffop (offset,
                                 convert (ssizetype,
                                          BINFO_OFFSET (virtual_offset)));
                }
              if (fixed_offset)
                /* There was an existing fixed offset, this must be
                   from the base just converted to, and the base the
                   FN was thunking to.  */
                fixed_offset = size_binop (PLUS_EXPR, fixed_offset, offset);
              else
                fixed_offset = offset;
            }
        }

      if (fixed_offset || virtual_offset)
        /* Replace the overriding function with a covariant thunk.  We
           will emit the overriding function in its own slot as
           well.  */
        overrider_fn = make_thunk (overrider_target, /*this_adjusting=*/0,
                                   fixed_offset, virtual_offset);
    }
  else
    gcc_assert (DECL_INVALID_OVERRIDER_P (overrider_target) ||
                !DECL_THUNK_P (fn));

  /* Assume that we will produce a thunk that convert all the way to
     the final overrider, and not to an intermediate virtual base.  */
  virtual_base = NULL_TREE;

  /* See if we can convert to an intermediate virtual base first, and then
     use the vcall offset located there to finish the conversion.  */
  for (; b; b = BINFO_INHERITANCE_CHAIN (b))
    {
      /* If we find the final overrider, then we can stop
         walking.  */
      if (SAME_BINFO_TYPE_P (BINFO_TYPE (b),
                             BINFO_TYPE (TREE_VALUE (overrider))))
        break;

      /* If we find a virtual base, and we haven't yet found the
         overrider, then there is a virtual base between the
         declaring base (first_defn) and the final overrider.  */
      if (BINFO_VIRTUAL_P (b))
        {
          virtual_base = b;
          break;
        }
    }

  if (overrider_fn != overrider_target && !virtual_base)
    {
      /* The ABI specifies that a covariant thunk includes a mangling
         for a this pointer adjustment.  This-adjusting thunks that
         override a function from a virtual base have a vcall
         adjustment.  When the virtual base in question is a primary
         virtual base, we know the adjustments are zero, (and in the
         non-covariant case, we would not use the thunk).
         Unfortunately we didn't notice this could happen, when
         designing the ABI and so never mandated that such a covariant
         thunk should be emitted.  Because we must use the ABI mandated
         name, we must continue searching from the binfo where we
         found the most recent definition of the function, towards the
         primary binfo which first introduced the function into the
         vtable.  If that enters a virtual base, we must use a vcall
         this-adjusting thunk.  Bleah! */
      tree probe = first_defn;

      while ((probe = get_primary_binfo (probe))
             && (unsigned) list_length (BINFO_VIRTUALS (probe)) > ix)
        if (BINFO_VIRTUAL_P (probe))
          virtual_base = probe;

      if (virtual_base)
        /* Even if we find a virtual base, the correct delta is
           between the overrider and the binfo we're building a vtable
           for.  */
        goto virtual_covariant;
    }

  /* Compute the constant adjustment to the `this' pointer.  The
     `this' pointer, when this function is called, will point at BINFO
     (or one of its primary bases, which are at the same offset).  */
  if (virtual_base)
    /* The `this' pointer needs to be adjusted from the declaration to
       the nearest virtual base.  */
    delta = size_diffop_loc (input_location,
                         convert (ssizetype, BINFO_OFFSET (virtual_base)),
                         convert (ssizetype, BINFO_OFFSET (first_defn)));
  else if (lost)
    /* If the nearest definition is in a lost primary, we don't need an
       entry in our vtable.  Except possibly in a constructor vtable,
       if we happen to get our primary back.  In that case, the offset
       will be zero, as it will be a primary base.  */
    delta = size_zero_node;
  else
    /* The `this' pointer needs to be adjusted from pointing to
       BINFO to pointing at the base where the final overrider
       appears.  */
    virtual_covariant:
    delta = size_diffop_loc (input_location,
                         convert (ssizetype,
                                  BINFO_OFFSET (TREE_VALUE (overrider))),
                         convert (ssizetype, BINFO_OFFSET (binfo)));

  modify_vtable_entry (t, binfo, overrider_fn, delta, virtuals);

  if (virtual_base)
    BV_VCALL_INDEX (*virtuals)
      = get_vcall_index (overrider_target, BINFO_TYPE (virtual_base));
  else
    BV_VCALL_INDEX (*virtuals) = NULL_TREE;
}

/* Called from modify_all_vtables via dfs_walk.  */

static tree
dfs_modify_vtables (tree binfo, void* data)
{
  tree t = (tree) data;
  tree virtuals;
  tree old_virtuals;
  unsigned ix;

  if (!TYPE_CONTAINS_VPTR_P (BINFO_TYPE (binfo)))
    /* A base without a vtable needs no modification, and its bases
       are uninteresting.  */
    return dfs_skip_bases;

  if (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), t)
      && !CLASSTYPE_HAS_PRIMARY_BASE_P (t))
    /* Don't do the primary vtable, if it's new.  */
    return NULL_TREE;

  if (BINFO_PRIMARY_P (binfo) && !BINFO_VIRTUAL_P (binfo))
    /* There's no need to modify the vtable for a non-virtual primary
       base; we're not going to use that vtable anyhow.  We do still
       need to do this for virtual primary bases, as they could become
       non-primary in a construction vtable.  */
    return NULL_TREE;

  make_new_vtable (t, binfo);

  /* Now, go through each of the virtual functions in the virtual
     function table for BINFO.  Find the final overrider, and update
     the BINFO_VIRTUALS list appropriately.  */
  for (ix = 0, virtuals = BINFO_VIRTUALS (binfo),
         old_virtuals = BINFO_VIRTUALS (TYPE_BINFO (BINFO_TYPE (binfo)));
       virtuals;
       ix++, virtuals = TREE_CHAIN (virtuals),
         old_virtuals = TREE_CHAIN (old_virtuals))
    update_vtable_entry_for_fn (t,
                                binfo,
                                BV_FN (old_virtuals),
                                &virtuals, ix);

  return NULL_TREE;
}

/* Update all of the primary and secondary vtables for T.  Create new
   vtables as required, and initialize their RTTI information.  Each
   of the functions in VIRTUALS is declared in T and may override a
   virtual function from a base class; find and modify the appropriate
   entries to point to the overriding functions.  Returns a list, in
   declaration order, of the virtual functions that are declared in T,
   but do not appear in the primary base class vtable, and which
   should therefore be appended to the end of the vtable for T.  */

static tree
modify_all_vtables (tree t, tree virtuals)
{
  tree binfo = TYPE_BINFO (t);
  tree *fnsp;

  /* Update all of the vtables.  */
  dfs_walk_once (binfo, dfs_modify_vtables, NULL, t);

  /* Add virtual functions not already in our primary vtable. These
     will be both those introduced by this class, and those overridden
     from secondary bases.  It does not include virtuals merely
     inherited from secondary bases.  */
  for (fnsp = &virtuals; *fnsp; )
    {
      tree fn = TREE_VALUE (*fnsp);

      if (!value_member (fn, BINFO_VIRTUALS (binfo))
          || DECL_VINDEX (fn) == error_mark_node)
        {
          /* We don't need to adjust the `this' pointer when
             calling this function.  */
          BV_DELTA (*fnsp) = integer_zero_node;
          BV_VCALL_INDEX (*fnsp) = NULL_TREE;

          /* This is a function not already in our vtable.  Keep it.  */
          fnsp = &TREE_CHAIN (*fnsp);
        }
      else
        /* We've already got an entry for this function.  Skip it.  */
        *fnsp = TREE_CHAIN (*fnsp);
    }

  return virtuals;
}

/* Get the base virtual function declarations in T that have the
   indicated NAME.  */

static tree
get_basefndecls (tree name, tree t)
{
  tree methods;
  tree base_fndecls = NULL_TREE;
  int n_baseclasses = BINFO_N_BASE_BINFOS (TYPE_BINFO (t));
  int i;

  /* Find virtual functions in T with the indicated NAME.  */
  i = lookup_fnfields_1 (t, name);
  if (i != -1)
    for (methods = VEC_index (tree, CLASSTYPE_METHOD_VEC (t), i);
         methods;
         methods = OVL_NEXT (methods))
      {
        tree method = OVL_CURRENT (methods);

        if (TREE_CODE (method) == FUNCTION_DECL
            && DECL_VINDEX (method))
          base_fndecls = tree_cons (NULL_TREE, method, base_fndecls);
      }

  if (base_fndecls)
    return base_fndecls;

  for (i = 0; i < n_baseclasses; i++)
    {
      tree basetype = BINFO_TYPE (BINFO_BASE_BINFO (TYPE_BINFO (t), i));
      base_fndecls = chainon (get_basefndecls (name, basetype),
                              base_fndecls);
    }

  return base_fndecls;
}

/* If this declaration supersedes the declaration of
   a method declared virtual in the base class, then
   mark this field as being virtual as well.  */

void
check_for_override (tree decl, tree ctype)
{
  if (TREE_CODE (decl) == TEMPLATE_DECL)
    /* In [temp.mem] we have:

         A specialization of a member function template does not
         override a virtual function from a base class.  */
    return;
  if ((DECL_DESTRUCTOR_P (decl)
       || IDENTIFIER_VIRTUAL_P (DECL_NAME (decl))
       || DECL_CONV_FN_P (decl))
      && look_for_overrides (ctype, decl)
      && !DECL_STATIC_FUNCTION_P (decl))
    /* Set DECL_VINDEX to a value that is neither an INTEGER_CST nor
       the error_mark_node so that we know it is an overriding
       function.  */
    DECL_VINDEX (decl) = decl;

  if (DECL_VIRTUAL_P (decl))
    {
      if (!DECL_VINDEX (decl))
        DECL_VINDEX (decl) = error_mark_node;
      IDENTIFIER_VIRTUAL_P (DECL_NAME (decl)) = 1;
    }
}

/* Warn about hidden virtual functions that are not overridden in t.
   We know that constructors and destructors don't apply.  */

static void
warn_hidden (tree t)
{
  VEC(tree,gc) *method_vec = CLASSTYPE_METHOD_VEC (t);
  tree fns;
  size_t i;

  /* We go through each separately named virtual function.  */
  for (i = CLASSTYPE_FIRST_CONVERSION_SLOT;
       VEC_iterate (tree, method_vec, i, fns);
       ++i)
    {
      tree fn;
      tree name;
      tree fndecl;
      tree base_fndecls;
      tree base_binfo;
      tree binfo;
      int j;

      /* All functions in this slot in the CLASSTYPE_METHOD_VEC will
         have the same name.  Figure out what name that is.  */
      name = DECL_NAME (OVL_CURRENT (fns));
      /* There are no possibly hidden functions yet.  */
      base_fndecls = NULL_TREE;
      /* Iterate through all of the base classes looking for possibly
         hidden functions.  */
      for (binfo = TYPE_BINFO (t), j = 0;
           BINFO_BASE_ITERATE (binfo, j, base_binfo); j++)
        {
          tree basetype = BINFO_TYPE (base_binfo);
          base_fndecls = chainon (get_basefndecls (name, basetype),
                                  base_fndecls);
        }

      /* If there are no functions to hide, continue.  */
      if (!base_fndecls)
        continue;

      /* Remove any overridden functions.  */
      for (fn = fns; fn; fn = OVL_NEXT (fn))
        {
          fndecl = OVL_CURRENT (fn);
          if (DECL_VINDEX (fndecl))
            {
              tree *prev = &base_fndecls;

              while (*prev)
                /* If the method from the base class has the same
                   signature as the method from the derived class, it
                   has been overridden.  */
                if (same_signature_p (fndecl, TREE_VALUE (*prev)))
                  *prev = TREE_CHAIN (*prev);
                else
                  prev = &TREE_CHAIN (*prev);
            }
        }

      /* Now give a warning for all base functions without overriders,
         as they are hidden.  */
      while (base_fndecls)
        {
          /* Here we know it is a hider, and no overrider exists.  */
          warning (OPT_Woverloaded_virtual, "%q+D was hidden", TREE_VALUE (base_fndecls));
          warning (OPT_Woverloaded_virtual, "  by %q+D", fns);
          base_fndecls = TREE_CHAIN (base_fndecls);
        }
    }
}

/* Check for things that are invalid.  There are probably plenty of other
   things we should check for also.  */

static void
finish_struct_anon (tree t)
{
  tree field;

  for (field = TYPE_FIELDS (t); field; field = TREE_CHAIN (field))
    {
      if (TREE_STATIC (field))
        continue;
      if (TREE_CODE (field) != FIELD_DECL)
        continue;

      if (DECL_NAME (field) == NULL_TREE
          && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
        {
          bool is_union = TREE_CODE (TREE_TYPE (field)) == UNION_TYPE;
          tree elt = TYPE_FIELDS (TREE_TYPE (field));
          for (; elt; elt = TREE_CHAIN (elt))
            {
              /* We're generally only interested in entities the user
                 declared, but we also find nested classes by noticing
                 the TYPE_DECL that we create implicitly.  You're
                 allowed to put one anonymous union inside another,
                 though, so we explicitly tolerate that.  We use
                 TYPE_ANONYMOUS_P rather than ANON_AGGR_TYPE_P so that
                 we also allow unnamed types used for defining fields.  */
              if (DECL_ARTIFICIAL (elt)
                  && (!DECL_IMPLICIT_TYPEDEF_P (elt)
                      || TYPE_ANONYMOUS_P (TREE_TYPE (elt))))
                continue;

              if (TREE_CODE (elt) != FIELD_DECL)
                {
                  if (is_union)
                    permerror (input_location, "%q+#D invalid; an anonymous union can "
                               "only have non-static data members", elt);
                  else
                    permerror (input_location, "%q+#D invalid; an anonymous struct can "
                               "only have non-static data members", elt);
                  continue;
                }

              if (TREE_PRIVATE (elt))
                {
                  if (is_union)
                    permerror (input_location, "private member %q+#D in anonymous union", elt);
                  else
                    permerror (input_location, "private member %q+#D in anonymous struct", elt);
                }
              else if (TREE_PROTECTED (elt))
                {
                  if (is_union)
                    permerror (input_location, "protected member %q+#D in anonymous union", elt);
                  else
                    permerror (input_location, "protected member %q+#D in anonymous struct", elt);
                }

              TREE_PRIVATE (elt) = TREE_PRIVATE (field);
              TREE_PROTECTED (elt) = TREE_PROTECTED (field);
            }
        }
    }
}

/* Add T to CLASSTYPE_DECL_LIST of current_class_type which
   will be used later during class template instantiation.
   When FRIEND_P is zero, T can be a static member data (VAR_DECL),
   a non-static member data (FIELD_DECL), a member function
   (FUNCTION_DECL), a nested type (RECORD_TYPE, ENUM_TYPE),
   a typedef (TYPE_DECL) or a member class template (TEMPLATE_DECL)
   When FRIEND_P is nonzero, T is either a friend class
   (RECORD_TYPE, TEMPLATE_DECL) or a friend function
   (FUNCTION_DECL, TEMPLATE_DECL).  */

void
maybe_add_class_template_decl_list (tree type, tree t, int friend_p)
{
  /* Save some memory by not creating TREE_LIST if TYPE is not template.  */
  if (CLASSTYPE_TEMPLATE_INFO (type))
    CLASSTYPE_DECL_LIST (type)
      = tree_cons (friend_p ? NULL_TREE : type,
                   t, CLASSTYPE_DECL_LIST (type));
}

/* Create default constructors, assignment operators, and so forth for
   the type indicated by T, if they are needed.  CANT_HAVE_CONST_CTOR,
   and CANT_HAVE_CONST_ASSIGNMENT are nonzero if, for whatever reason,
   the class cannot have a default constructor, copy constructor
   taking a const reference argument, or an assignment operator taking
   a const reference, respectively.  */

static void
add_implicitly_declared_members (tree t,
                                 int cant_have_const_cctor,
                                 int cant_have_const_assignment)
{
  /* Destructor.  */
  if (!CLASSTYPE_DESTRUCTORS (t))
    {
      /* In general, we create destructors lazily.  */
      CLASSTYPE_LAZY_DESTRUCTOR (t) = 1;
      /* However, if the implicit destructor is non-trivial
         destructor, we sometimes have to create it at this point.  */
      if (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t))
        {
          bool lazy_p = true;

          if (TYPE_FOR_JAVA (t))
            /* If this a Java class, any non-trivial destructor is
               invalid, even if compiler-generated.  Therefore, if the
               destructor is non-trivial we create it now.  */
            lazy_p = false;
          else
            {
              tree binfo;
              tree base_binfo;
              int ix;

              /* If the implicit destructor will be virtual, then we must
                 generate it now because (unfortunately) we do not
                 generate virtual tables lazily.  */
              binfo = TYPE_BINFO (t);
              for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
                {
                  tree base_type;
                  tree dtor;

                  base_type = BINFO_TYPE (base_binfo);
                  dtor = CLASSTYPE_DESTRUCTORS (base_type);
                  if (dtor && DECL_VIRTUAL_P (dtor))
                    {
                      lazy_p = false;
                      break;
                    }
                }
            }

          /* If we can't get away with being lazy, generate the destructor
             now.  */
          if (!lazy_p)
            lazily_declare_fn (sfk_destructor, t);
        }
    }

  /* [class.ctor]

     If there is no user-declared constructor for a class, a default
     constructor is implicitly declared.  */
  if (! TYPE_HAS_USER_CONSTRUCTOR (t))
    {
      TYPE_HAS_DEFAULT_CONSTRUCTOR (t) = 1;
      CLASSTYPE_LAZY_DEFAULT_CTOR (t) = 1;
    }

  /* [class.ctor]

     If a class definition does not explicitly declare a copy
     constructor, one is declared implicitly.  */
  if (! TYPE_HAS_INIT_REF (t) && ! TYPE_FOR_JAVA (t))
    {
      TYPE_HAS_INIT_REF (t) = 1;
      TYPE_HAS_CONST_INIT_REF (t) = !cant_have_const_cctor;
      CLASSTYPE_LAZY_COPY_CTOR (t) = 1;
    }

  /* Currently only lambdas get a lazy move ctor, but N2987 adds them for
     other classes.  */
  if (LAMBDA_TYPE_P (t))
    CLASSTYPE_LAZY_MOVE_CTOR (t) = 1;

  /* If there is no assignment operator, one will be created if and
     when it is needed.  For now, just record whether or not the type
     of the parameter to the assignment operator will be a const or
     non-const reference.  */
  if (!TYPE_HAS_ASSIGN_REF (t) && !TYPE_FOR_JAVA (t))
    {
      TYPE_HAS_ASSIGN_REF (t) = 1;
      TYPE_HAS_CONST_ASSIGN_REF (t) = !cant_have_const_assignment;
      CLASSTYPE_LAZY_ASSIGNMENT_OP (t) = 1;
    }
}

/* Subroutine of finish_struct_1.  Recursively count the number of fields
   in TYPE, including anonymous union members.  */

static int
count_fields (tree fields)
{
  tree x;
  int n_fields = 0;
  for (x = fields; x; x = TREE_CHAIN (x))
    {
      if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
        n_fields += count_fields (TYPE_FIELDS (TREE_TYPE (x)));
      else
        n_fields += 1;
    }
  return n_fields;
}

/* Subroutine of finish_struct_1.  Recursively add all the fields in the
   TREE_LIST FIELDS to the SORTED_FIELDS_TYPE elts, starting at offset IDX.  */

static int
add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec, int idx)
{
  tree x;
  for (x = fields; x; x = TREE_CHAIN (x))
    {
      if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
        idx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
      else
        field_vec->elts[idx++] = x;
    }
  return idx;
}

/* FIELD is a bit-field.  We are finishing the processing for its
   enclosing type.  Issue any appropriate messages and set appropriate
   flags.  Returns false if an error has been diagnosed.  */

static bool
check_bitfield_decl (tree field)
{
  tree type = TREE_TYPE (field);
  tree w;

  /* Extract the declared width of the bitfield, which has been
     temporarily stashed in DECL_INITIAL.  */
  w = DECL_INITIAL (field);
  gcc_assert (w != NULL_TREE);
  /* Remove the bit-field width indicator so that the rest of the
     compiler does not treat that value as an initializer.  */
  DECL_INITIAL (field) = NULL_TREE;

  /* Detect invalid bit-field type.  */
  if (!INTEGRAL_OR_ENUMERATION_TYPE_P (type))
    {
      error ("bit-field %q+#D with non-integral type", field);
      w = error_mark_node;
    }
  else
    {
      /* Avoid the non_lvalue wrapper added by fold for PLUS_EXPRs.  */
      STRIP_NOPS (w);

      /* detect invalid field size.  */
      w = integral_constant_value (w);

      if (TREE_CODE (w) != INTEGER_CST)
        {
          error ("bit-field %q+D width not an integer constant", field);
          w = error_mark_node;
        }
      else if (tree_int_cst_sgn (w) < 0)
        {
          error ("negative width in bit-field %q+D", field);
          w = error_mark_node;
        }
      else if (integer_zerop (w) && DECL_NAME (field) != 0)
        {
          error ("zero width for bit-field %q+D", field);
          w = error_mark_node;
        }
      else if (compare_tree_int (w, TYPE_PRECISION (type)) > 0
               && TREE_CODE (type) != ENUMERAL_TYPE
               && TREE_CODE (type) != BOOLEAN_TYPE)
        warning (0, "width of %q+D exceeds its type", field);
      else if (TREE_CODE (type) == ENUMERAL_TYPE
               && (0 > compare_tree_int (w,
                                         tree_int_cst_min_precision
                                         (TYPE_MIN_VALUE (type),
                                          TYPE_UNSIGNED (type)))
                   ||  0 > compare_tree_int (w,
                                             tree_int_cst_min_precision
                                             (TYPE_MAX_VALUE (type),
                                              TYPE_UNSIGNED (type)))))
        warning (0, "%q+D is too small to hold all values of %q#T", field, type);
    }

  if (w != error_mark_node)
    {
      DECL_SIZE (field) = convert (bitsizetype, w);
      DECL_BIT_FIELD (field) = 1;
      return true;
    }
  else
    {
      /* Non-bit-fields are aligned for their type.  */
      DECL_BIT_FIELD (field) = 0;
      CLEAR_DECL_C_BIT_FIELD (field);
      return false;
    }
}

/* FIELD is a non bit-field.  We are finishing the processing for its
   enclosing type T.  Issue any appropriate messages and set appropriate
   flags.  */

static void
check_field_decl (tree field,
                  tree t,
                  int* cant_have_const_ctor,
                  int* no_const_asn_ref,
                  int* any_default_members)
{
  tree type = strip_array_types (TREE_TYPE (field));

  /* An anonymous union cannot contain any fields which would change
     the settings of CANT_HAVE_CONST_CTOR and friends.  */
  if (ANON_UNION_TYPE_P (type))
    ;
  /* And, we don't set TYPE_HAS_CONST_INIT_REF, etc., for anonymous
     structs.  So, we recurse through their fields here.  */
  else if (ANON_AGGR_TYPE_P (type))
    {
      tree fields;

      for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
        if (TREE_CODE (fields) == FIELD_DECL && !DECL_C_BIT_FIELD (field))
          check_field_decl (fields, t, cant_have_const_ctor,
                            no_const_asn_ref, any_default_members);
    }
  /* Check members with class type for constructors, destructors,
     etc.  */
  else if (CLASS_TYPE_P (type))
    {
      /* Never let anything with uninheritable virtuals
         make it through without complaint.  */
      abstract_virtuals_error (field, type);

      if (TREE_CODE (t) == UNION_TYPE)
        {
          if (TYPE_NEEDS_CONSTRUCTING (type))
            error ("member %q+#D with constructor not allowed in union",
                   field);
          if (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (type))
            error ("member %q+#D with destructor not allowed in union", field);
          if (TYPE_HAS_COMPLEX_ASSIGN_REF (type))
            error ("member %q+#D with copy assignment operator not allowed in union",
                   field);
        }
      else
        {
          TYPE_NEEDS_CONSTRUCTING (t) |= TYPE_NEEDS_CONSTRUCTING (type);
          TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
            |= TYPE_HAS_NONTRIVIAL_DESTRUCTOR (type);
          TYPE_HAS_COMPLEX_ASSIGN_REF (t) |= TYPE_HAS_COMPLEX_ASSIGN_REF (type);
          TYPE_HAS_COMPLEX_INIT_REF (t) |= TYPE_HAS_COMPLEX_INIT_REF (type);
          TYPE_HAS_COMPLEX_DFLT (t) |= TYPE_HAS_COMPLEX_DFLT (type);
        }

      if (!TYPE_HAS_CONST_INIT_REF (type))
        *cant_have_const_ctor = 1;

      if (!TYPE_HAS_CONST_ASSIGN_REF (type))
        *no_const_asn_ref = 1;
    }
  if (DECL_INITIAL (field) != NULL_TREE)
    {
      /* `build_class_init_list' does not recognize
         non-FIELD_DECLs.  */
      if (TREE_CODE (t) == UNION_TYPE && any_default_members != 0)
        error ("multiple fields in union %qT initialized", t);
      *any_default_members = 1;
    }
}

/* Check the data members (both static and non-static), class-scoped
   typedefs, etc., appearing in the declaration of T.  Issue
   appropriate diagnostics.  Sets ACCESS_DECLS to a list (in
   declaration order) of access declarations; each TREE_VALUE in this
   list is a USING_DECL.

   In addition, set the following flags:

     EMPTY_P
       The class is empty, i.e., contains no non-static data members.

     CANT_HAVE_CONST_CTOR_P
       This class cannot have an implicitly generated copy constructor
       taking a const reference.

     CANT_HAVE_CONST_ASN_REF
       This class cannot have an implicitly generated assignment
       operator taking a const reference.

   All of these flags should be initialized before calling this
   function.

   Returns a pointer to the end of the TYPE_FIELDs chain; additional
   fields can be added by adding to this chain.  */

static void
check_field_decls (tree t, tree *access_decls,
                   int *cant_have_const_ctor_p,
                   int *no_const_asn_ref_p)
{
  tree *field;
  tree *next;
  bool has_pointers;
  int any_default_members;
  int cant_pack = 0;
  int field_access = -1;

  /* Assume there are no access declarations.  */
  *access_decls = NULL_TREE;
  /* Assume this class has no pointer members.  */
  has_pointers = false;
  /* Assume none of the members of this class have default
     initializations.  */
  any_default_members = 0;

  for (field = &TYPE_FIELDS (t); *field; field = next)
    {
      tree x = *field;
      tree type = TREE_TYPE (x);
      int this_field_access;

      next = &TREE_CHAIN (x);

      if (TREE_CODE (x) == USING_DECL)
        {
          /* Prune the access declaration from the list of fields.  */
          *field = TREE_CHAIN (x);

          /* Save the access declarations for our caller.  */
          *access_decls = tree_cons (NULL_TREE, x, *access_decls);

          /* Since we've reset *FIELD there's no reason to skip to the
             next field.  */
          next = field;
          continue;
        }

      if (TREE_CODE (x) == TYPE_DECL
          || TREE_CODE (x) == TEMPLATE_DECL)
        continue;

      /* If we've gotten this far, it's a data member, possibly static,
         or an enumerator.  */
      DECL_CONTEXT (x) = t;

      /* When this goes into scope, it will be a non-local reference.  */
      DECL_NONLOCAL (x) = 1;

      if (TREE_CODE (t) == UNION_TYPE)
        {
          /* [class.union]

             If a union contains a static data member, or a member of
             reference type, the program is ill-formed.  */
          if (TREE_CODE (x) == VAR_DECL)
            {
              error ("%q+D may not be static because it is a member of a union", x);
              continue;
            }
          if (TREE_CODE (type) == REFERENCE_TYPE)
            {
              error ("%q+D may not have reference type %qT because"
                     " it is a member of a union",
                     x, type);
              continue;
            }
        }

      /* Perform error checking that did not get done in
         grokdeclarator.  */
      if (TREE_CODE (type) == FUNCTION_TYPE)
        {
          error ("field %q+D invalidly declared function type", x);
          type = build_pointer_type (type);
          TREE_TYPE (x) = type;
        }
      else if (TREE_CODE (type) == METHOD_TYPE)
        {
          error ("field %q+D invalidly declared method type", x);
          type = build_pointer_type (type);
          TREE_TYPE (x) = type;
        }

      if (type == error_mark_node)
        continue;

      if (TREE_CODE (x) == CONST_DECL || TREE_CODE (x) == VAR_DECL)
        continue;

      /* Now it can only be a FIELD_DECL.  */

      if (TREE_PRIVATE (x) || TREE_PROTECTED (x))
        CLASSTYPE_NON_AGGREGATE (t) = 1;

      /* A standard-layout class is a class that:
         ...
         has the same access control (Clause 11) for all non-static data members,
         ...  */
      this_field_access = TREE_PROTECTED (x) ? 1 : TREE_PRIVATE (x) ? 2 : 0;
      if (field_access == -1)
        field_access = this_field_access;
      else if (this_field_access != field_access)
        CLASSTYPE_NON_STD_LAYOUT (t) = 1;

      /* If this is of reference type, check if it needs an init.  */
      if (TREE_CODE (type) == REFERENCE_TYPE)
        {
          CLASSTYPE_NON_LAYOUT_POD_P (t) = 1;
          CLASSTYPE_NON_STD_LAYOUT (t) = 1;
          if (DECL_INITIAL (x) == NULL_TREE)
            SET_CLASSTYPE_REF_FIELDS_NEED_INIT (t, 1);

          /* ARM $12.6.2: [A member initializer list] (or, for an
             aggregate, initialization by a brace-enclosed list) is the
             only way to initialize nonstatic const and reference
             members.  */
          TYPE_HAS_COMPLEX_ASSIGN_REF (t) = 1;
        }

      type = strip_array_types (type);

      if (TYPE_PACKED (t))
        {
          if (!layout_pod_type_p (type) && !TYPE_PACKED (type))
            {
              warning
                (0,
                 "ignoring packed attribute because of unpacked non-POD field %q+#D",
                 x);
              cant_pack = 1;
            }
          else if (DECL_C_BIT_FIELD (x)
                   || TYPE_ALIGN (TREE_TYPE (x)) > BITS_PER_UNIT)
            DECL_PACKED (x) = 1;
        }

      if (DECL_C_BIT_FIELD (x) && integer_zerop (DECL_INITIAL (x)))
        /* We don't treat zero-width bitfields as making a class
           non-empty.  */
        ;
      else
        {
          /* The class is non-empty.  */
          CLASSTYPE_EMPTY_P (t) = 0;
          /* The class is not even nearly empty.  */
          CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
          /* If one of the data members contains an empty class,
             so does T.  */
          if (CLASS_TYPE_P (type)
              && CLASSTYPE_CONTAINS_EMPTY_CLASS_P (type))
            CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t) = 1;
        }

      /* This is used by -Weffc++ (see below). Warn only for pointers
         to members which might hold dynamic memory. So do not warn
         for pointers to functions or pointers to members.  */
      if (TYPE_PTR_P (type)
          && !TYPE_PTRFN_P (type)
          && !TYPE_PTR_TO_MEMBER_P (type))
        has_pointers = true;

      if (CLASS_TYPE_P (type))
        {
          if (CLASSTYPE_REF_FIELDS_NEED_INIT (type))
            SET_CLASSTYPE_REF_FIELDS_NEED_INIT (t, 1);
          if (CLASSTYPE_READONLY_FIELDS_NEED_INIT (type))
            SET_CLASSTYPE_READONLY_FIELDS_NEED_INIT (t, 1);
        }

      if (DECL_MUTABLE_P (x) || TYPE_HAS_MUTABLE_P (type))
        CLASSTYPE_HAS_MUTABLE (t) = 1;

      if (! layout_pod_type_p (type))
        /* DR 148 now allows pointers to members (which are POD themselves),
           to be allowed in POD structs.  */
        CLASSTYPE_NON_LAYOUT_POD_P (t) = 1;

      if (!std_layout_type_p (type))
        CLASSTYPE_NON_STD_LAYOUT (t) = 1;

      if (! zero_init_p (type))
        CLASSTYPE_NON_ZERO_INIT_P (t) = 1;

      /* If any field is const, the structure type is pseudo-const.  */
      if (CP_TYPE_CONST_P (type))
        {
          C_TYPE_FIELDS_READONLY (t) = 1;
          if (DECL_INITIAL (x) == NULL_TREE)
            SET_CLASSTYPE_READONLY_FIELDS_NEED_INIT (t, 1);

          /* ARM $12.6.2: [A member initializer list] (or, for an
             aggregate, initialization by a brace-enclosed list) is the
             only way to initialize nonstatic const and reference
             members.  */
          TYPE_HAS_COMPLEX_ASSIGN_REF (t) = 1;
        }
      /* A field that is pseudo-const makes the structure likewise.  */
      else if (CLASS_TYPE_P (type))
        {
          C_TYPE_FIELDS_READONLY (t) |= C_TYPE_FIELDS_READONLY (type);
          SET_CLASSTYPE_READONLY_FIELDS_NEED_INIT (t,
            CLASSTYPE_READONLY_FIELDS_NEED_INIT (t)
            | CLASSTYPE_READONLY_FIELDS_NEED_INIT (type));
        }

      /* Core issue 80: A nonstatic data member is required to have a
         different name from the class iff the class has a
         user-declared constructor.  */
      if (constructor_name_p (DECL_NAME (x), t)
          && TYPE_HAS_USER_CONSTRUCTOR (t))
        permerror (input_location, "field %q+#D with same name as class", x);

      /* We set DECL_C_BIT_FIELD in grokbitfield.
         If the type and width are valid, we'll also set DECL_BIT_FIELD.  */
      if (! DECL_C_BIT_FIELD (x) || ! check_bitfield_decl (x))
        check_field_decl (x, t,
                          cant_have_const_ctor_p,
                          no_const_asn_ref_p,
                          &any_default_members);
    }

  /* Effective C++ rule 11: if a class has dynamic memory held by pointers,
     it should also define a copy constructor and an assignment operator to
     implement the correct copy semantic (deep vs shallow, etc.). As it is
     not feasible to check whether the constructors do allocate dynamic memory
     and store it within members, we approximate the warning like this:

     -- Warn only if there are members which are pointers
     -- Warn only if there is a non-trivial constructor (otherwise,
        there cannot be memory allocated).
     -- Warn only if there is a non-trivial destructor. We assume that the
        user at least implemented the cleanup correctly, and a destructor
        is needed to free dynamic memory.

     This seems enough for practical purposes.  */
  if (warn_ecpp
      && has_pointers
      && TYPE_HAS_USER_CONSTRUCTOR (t)
      && TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
      && !(TYPE_HAS_INIT_REF (t) && TYPE_HAS_ASSIGN_REF (t)))
    {
      warning (OPT_Weffc__, "%q#T has pointer data members", t);

      if (! TYPE_HAS_INIT_REF (t))
        {
          warning (OPT_Weffc__,
                   "  but does not override %<%T(const %T&)%>", t, t);
          if (!TYPE_HAS_ASSIGN_REF (t))
            warning (OPT_Weffc__, "  or %<operator=(const %T&)%>", t);
        }
      else if (! TYPE_HAS_ASSIGN_REF (t))
        warning (OPT_Weffc__,
                 "  but does not override %<operator=(const %T&)%>", t);
    }

  /* If any of the fields couldn't be packed, unset TYPE_PACKED.  */
  if (cant_pack)
    TYPE_PACKED (t) = 0;

  /* Check anonymous struct/anonymous union fields.  */
  finish_struct_anon (t);

  /* We've built up the list of access declarations in reverse order.
     Fix that now.  */
  *access_decls = nreverse (*access_decls);
}

/* If TYPE is an empty class type, records its OFFSET in the table of
   OFFSETS.  */

static int
record_subobject_offset (tree type, tree offset, splay_tree offsets)
{
  splay_tree_node n;

  if (!is_empty_class (type))
    return 0;

  /* Record the location of this empty object in OFFSETS.  */
  n = splay_tree_lookup (offsets, (splay_tree_key) offset);
  if (!n)
    n = splay_tree_insert (offsets,
                           (splay_tree_key) offset,
                           (splay_tree_value) NULL_TREE);
  n->value = ((splay_tree_value)
              tree_cons (NULL_TREE,
                         type,
                         (tree) n->value));

  return 0;
}

/* Returns nonzero if TYPE is an empty class type and there is
   already an entry in OFFSETS for the same TYPE as the same OFFSET.  */

static int
check_subobject_offset (tree type, tree offset, splay_tree offsets)
{
  splay_tree_node n;
  tree t;

  if (!is_empty_class (type))
    return 0;

  /* Record the location of this empty object in OFFSETS.  */
  n = splay_tree_lookup (offsets, (splay_tree_key) offset);
  if (!n)
    return 0;

  for (t = (tree) n->value; t; t = TREE_CHAIN (t))
    if (same_type_p (TREE_VALUE (t), type))
      return 1;

  return 0;
}

/* Walk through all the subobjects of TYPE (located at OFFSET).  Call
   F for every subobject, passing it the type, offset, and table of
   OFFSETS.  If VBASES_P is one, then virtual non-primary bases should
   be traversed.

   If MAX_OFFSET is non-NULL, then subobjects with an offset greater
   than MAX_OFFSET will not be walked.

   If F returns a nonzero value, the traversal ceases, and that value
   is returned.  Otherwise, returns zero.  */

static int
walk_subobject_offsets (tree type,
                        subobject_offset_fn f,
                        tree offset,
                        splay_tree offsets,
                        tree max_offset,
                        int vbases_p)
{
  int r = 0;
  tree type_binfo = NULL_TREE;

  /* If this OFFSET is bigger than the MAX_OFFSET, then we should
     stop.  */
  if (max_offset && INT_CST_LT (max_offset, offset))
    return 0;

  if (type == error_mark_node)
    return 0;

  if (!TYPE_P (type))
    {
      if (abi_version_at_least (2))
        type_binfo = type;
      type = BINFO_TYPE (type);
    }

  if (CLASS_TYPE_P (type))
    {
      tree field;
      tree binfo;
      int i;

      /* Avoid recursing into objects that are not interesting.  */
      if (!CLASSTYPE_CONTAINS_EMPTY_CLASS_P (type))
        return 0;

      /* Record the location of TYPE.  */
      r = (*f) (type, offset, offsets);
      if (r)
        return r;

      /* Iterate through the direct base classes of TYPE.  */
      if (!type_binfo)
        type_binfo = TYPE_BINFO (type);
      for (i = 0; BINFO_BASE_ITERATE (type_binfo, i, binfo); i++)
        {
          tree binfo_offset;

          if (abi_version_at_least (2)
              && BINFO_VIRTUAL_P (binfo))
            continue;

          if (!vbases_p
              && BINFO_VIRTUAL_P (binfo)
              && !BINFO_PRIMARY_P (binfo))
            continue;

          if (!abi_version_at_least (2))
            binfo_offset = size_binop (PLUS_EXPR,
                                       offset,
                                       BINFO_OFFSET (binfo));
          else
            {
              tree orig_binfo;
              /* We cannot rely on BINFO_OFFSET being set for the base
                 class yet, but the offsets for direct non-virtual
                 bases can be calculated by going back to the TYPE.  */
              orig_binfo = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
              binfo_offset = size_binop (PLUS_EXPR,
                                         offset,
                                         BINFO_OFFSET (orig_binfo));
            }

          r = walk_subobject_offsets (binfo,
                                      f,
                                      binfo_offset,
                                      offsets,
                                      max_offset,
                                      (abi_version_at_least (2)
                                       ? /*vbases_p=*/0 : vbases_p));
          if (r)
            return r;
        }

      if (abi_version_at_least (2) && CLASSTYPE_VBASECLASSES (type))
        {
          unsigned ix;
          VEC(tree,gc) *vbases;

          /* Iterate through the virtual base classes of TYPE.  In G++
             3.2, we included virtual bases in the direct base class
             loop above, which results in incorrect results; the
             correct offsets for virtual bases are only known when
             working with the most derived type.  */
          if (vbases_p)
            for (vbases = CLASSTYPE_VBASECLASSES (type), ix = 0;
                 VEC_iterate (tree, vbases, ix, binfo); ix++)
              {
                r = walk_subobject_offsets (binfo,
                                            f,
                                            size_binop (PLUS_EXPR,
                                                        offset,
                                                        BINFO_OFFSET (binfo)),
                                            offsets,
                                            max_offset,
                                            /*vbases_p=*/0);
                if (r)
                  return r;
              }
          else
            {
              /* We still have to walk the primary base, if it is
                 virtual.  (If it is non-virtual, then it was walked
                 above.)  */
              tree vbase = get_primary_binfo (type_binfo);

              if (vbase && BINFO_VIRTUAL_P (vbase)
                  && BINFO_PRIMARY_P (vbase)
                  && BINFO_INHERITANCE_CHAIN (vbase) == type_binfo)
                {
                  r = (walk_subobject_offsets
                       (vbase, f, offset,
                        offsets, max_offset, /*vbases_p=*/0));
                  if (r)
                    return r;
                }
            }
        }

      /* Iterate through the fields of TYPE.  */
      for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
        if (TREE_CODE (field) == FIELD_DECL && !DECL_ARTIFICIAL (field))
          {
            tree field_offset;

            if (abi_version_at_least (2))
              field_offset = byte_position (field);
            else
              /* In G++ 3.2, DECL_FIELD_OFFSET was used.  */
              field_offset = DECL_FIELD_OFFSET (field);

            r = walk_subobject_offsets (TREE_TYPE (field),
                                        f,
                                        size_binop (PLUS_EXPR,
                                                    offset,
                                                    field_offset),
                                        offsets,
                                        max_offset,
                                        /*vbases_p=*/1);
            if (r)
              return r;
          }
    }
  else if (TREE_CODE (type) == ARRAY_TYPE)
    {
      tree element_type = strip_array_types (type);
      tree domain = TYPE_DOMAIN (type);
      tree index;

      /* Avoid recursing into objects that are not interesting.  */
      if (!CLASS_TYPE_P (element_type)
          || !CLASSTYPE_CONTAINS_EMPTY_CLASS_P (element_type))
        return 0;

      /* Step through each of the elements in the array.  */
      for (index = size_zero_node;
           /* G++ 3.2 had an off-by-one error here.  */
           (abi_version_at_least (2)
            ? !INT_CST_LT (TYPE_MAX_VALUE (domain), index)
            : INT_CST_LT (index, TYPE_MAX_VALUE (domain)));
           index = size_binop (PLUS_EXPR, index, size_one_node))
        {
          r = walk_subobject_offsets (TREE_TYPE (type),
                                      f,
                                      offset,
                                      offsets,
                                      max_offset,
                                      /*vbases_p=*/1);
          if (r)
            return r;
          offset = size_binop (PLUS_EXPR, offset,
                               TYPE_SIZE_UNIT (TREE_TYPE (type)));
          /* If this new OFFSET is bigger than the MAX_OFFSET, then
             there's no point in iterating through the remaining
             elements of the array.  */
          if (max_offset && INT_CST_LT (max_offset, offset))
            break;
        }
    }

  return 0;
}

/* Record all of the empty subobjects of TYPE (either a type or a
   binfo).  If IS_DATA_MEMBER is true, then a non-static data member
   is being placed at OFFSET; otherwise, it is a base class that is
   being placed at OFFSET.  */

static void
record_subobject_offsets (tree type,
                          tree offset,
                          splay_tree offsets,
                          bool is_data_member)
{
  tree max_offset;
  /* If recording subobjects for a non-static data member or a
     non-empty base class , we do not need to record offsets beyond
     the size of the biggest empty class.  Additional data members
     will go at the end of the class.  Additional base classes will go
     either at offset zero (if empty, in which case they cannot
     overlap with offsets past the size of the biggest empty class) or
     at the end of the class.

     However, if we are placing an empty base class, then we must record
     all offsets, as either the empty class is at offset zero (where
     other empty classes might later be placed) or at the end of the
     class (where other objects might then be placed, so other empty
     subobjects might later overlap).  */
  if (is_data_member
      || !is_empty_class (BINFO_TYPE (type)))
    max_offset = sizeof_biggest_empty_class;
  else
    max_offset = NULL_TREE;
  walk_subobject_offsets (type, record_subobject_offset, offset,
                          offsets, max_offset, is_data_member);
}

/* Returns nonzero if any of the empty subobjects of TYPE (located at
   OFFSET) conflict with entries in OFFSETS.  If VBASES_P is nonzero,
   virtual bases of TYPE are examined.  */

static int
layout_conflict_p (tree type,
                   tree offset,
                   splay_tree offsets,
                   int vbases_p)
{
  splay_tree_node max_node;

  /* Get the node in OFFSETS that indicates the maximum offset where
     an empty subobject is located.  */
  max_node = splay_tree_max (offsets);
  /* If there aren't any empty subobjects, then there's no point in
     performing this check.  */
  if (!max_node)
    return 0;

  return walk_subobject_offsets (type, check_subobject_offset, offset,
                                 offsets, (tree) (max_node->key),
                                 vbases_p);
}

/* DECL is a FIELD_DECL corresponding either to a base subobject of a
   non-static data member of the type indicated by RLI.  BINFO is the
   binfo corresponding to the base subobject, OFFSETS maps offsets to
   types already located at those offsets.  This function determines
   the position of the DECL.  */

static void
layout_nonempty_base_or_field (record_layout_info rli,
                               tree decl,
                               tree binfo,
                               splay_tree offsets)
{
  tree offset = NULL_TREE;
  bool field_p;
  tree type;

  if (binfo)
    {
      /* For the purposes of determining layout conflicts, we want to
         use the class type of BINFO; TREE_TYPE (DECL) will be the
         CLASSTYPE_AS_BASE version, which does not contain entries for
         zero-sized bases.  */
      type = TREE_TYPE (binfo);
      field_p = false;
    }
  else
    {
      type = TREE_TYPE (decl);
      field_p = true;
    }

  /* Try to place the field.  It may take more than one try if we have
     a hard time placing the field without putting two objects of the
     same type at the same address.  */
  while (1)
    {
      struct record_layout_info_s old_rli = *rli;

      /* Place this field.  */
      place_field (rli, decl);
      offset = byte_position (decl);

      /* We have to check to see whether or not there is already
         something of the same type at the offset we're about to use.
         For example, consider:

           struct S {};
           struct T : public S { int i; };
           struct U : public S, public T {};

         Here, we put S at offset zero in U.  Then, we can't put T at
         offset zero -- its S component would be at the same address
         as the S we already allocated.  So, we have to skip ahead.
         Since all data members, including those whose type is an
         empty class, have nonzero size, any overlap can happen only
         with a direct or indirect base-class -- it can't happen with
         a data member.  */
      /* In a union, overlap is permitted; all members are placed at
         offset zero.  */
      if (TREE_CODE (rli->t) == UNION_TYPE)
        break;
      /* G++ 3.2 did not check for overlaps when placing a non-empty
         virtual base.  */
      if (!abi_version_at_least (2) && binfo && BINFO_VIRTUAL_P (binfo))
        break;
      if (layout_conflict_p (field_p ? type : binfo, offset,
                             offsets, field_p))
        {
          /* Strip off the size allocated to this field.  That puts us
             at the first place we could have put the field with
             proper alignment.  */
          *rli = old_rli;

          /* Bump up by the alignment required for the type.  */
          rli->bitpos
            = size_binop (PLUS_EXPR, rli->bitpos,
                          bitsize_int (binfo
                                       ? CLASSTYPE_ALIGN (type)
                                       : TYPE_ALIGN (type)));
          normalize_rli (rli);
        }
      else
        /* There was no conflict.  We're done laying out this field.  */
        break;
    }

  /* Now that we know where it will be placed, update its
     BINFO_OFFSET.  */
  if (binfo && CLASS_TYPE_P (BINFO_TYPE (binfo)))
    /* Indirect virtual bases may have a nonzero BINFO_OFFSET at
       this point because their BINFO_OFFSET is copied from another
       hierarchy.  Therefore, we may not need to add the entire
       OFFSET.  */
    propagate_binfo_offsets (binfo,
                             size_diffop_loc (input_location,
                                          convert (ssizetype, offset),
                                          convert (ssizetype,
                                                   BINFO_OFFSET (binfo))));
}

/* Returns true if TYPE is empty and OFFSET is nonzero.  */

static int
empty_base_at_nonzero_offset_p (tree type,
                                tree offset,
                                splay_tree offsets ATTRIBUTE_UNUSED)
{
  return is_empty_class (type) && !integer_zerop (offset);
}

/* Layout the empty base BINFO.  EOC indicates the byte currently just
   past the end of the class, and should be correctly aligned for a
   class of the type indicated by BINFO; OFFSETS gives the offsets of
   the empty bases allocated so far. T is the most derived
   type.  Return nonzero iff we added it at the end.  */

static bool
layout_empty_base (record_layout_info rli, tree binfo,
                   tree eoc, splay_tree offsets)
{
  tree alignment;
  tree basetype = BINFO_TYPE (binfo);
  bool atend = false;

  /* This routine should only be used for empty classes.  */
  gcc_assert (is_empty_class (basetype));
  alignment = ssize_int (CLASSTYPE_ALIGN_UNIT (basetype));

  if (!integer_zerop (BINFO_OFFSET (binfo)))
    {
      if (abi_version_at_least (2))
        propagate_binfo_offsets
          (binfo, size_diffop_loc (input_location,
                               size_zero_node, BINFO_OFFSET (binfo)));
      else
        warning (OPT_Wabi,
                 "offset of empty base %qT may not be ABI-compliant and may"
                 "change in a future version of GCC",
                 BINFO_TYPE (binfo));
    }

  /* This is an empty base class.  We first try to put it at offset
     zero.  */
  if (layout_conflict_p (binfo,
                         BINFO_OFFSET (binfo),
                         offsets,
                         /*vbases_p=*/0))
    {
      /* That didn't work.  Now, we move forward from the next
         available spot in the class.  */
      atend = true;
      propagate_binfo_offsets (binfo, convert (ssizetype, eoc));
      while (1)
        {
          if (!layout_conflict_p (binfo,
                                  BINFO_OFFSET (binfo),
                                  offsets,
                                  /*vbases_p=*/0))
            /* We finally found a spot where there's no overlap.  */
            break;

          /* There's overlap here, too.  Bump along to the next spot.  */
          propagate_binfo_offsets (binfo, alignment);
        }
    }

  if (CLASSTYPE_USER_ALIGN (basetype))
    {
      rli->record_align = MAX (rli->record_align, CLASSTYPE_ALIGN (basetype));
      if (warn_packed)
        rli->unpacked_align = MAX (rli->unpacked_align, CLASSTYPE_ALIGN (basetype));
      TYPE_USER_ALIGN (rli->t) = 1;
    }

  return atend;
}

/* Layout the base given by BINFO in the class indicated by RLI.
   *BASE_ALIGN is a running maximum of the alignments of
   any base class.  OFFSETS gives the location of empty base
   subobjects.  T is the most derived type.  Return nonzero if the new
   object cannot be nearly-empty.  A new FIELD_DECL is inserted at
   *NEXT_FIELD, unless BINFO is for an empty base class.

   Returns the location at which the next field should be inserted.  */

static tree *
build_base_field (record_layout_info rli, tree binfo,
                  splay_tree offsets, tree *next_field)
{
  tree t = rli->t;
  tree basetype = BINFO_TYPE (binfo);

  if (!COMPLETE_TYPE_P (basetype))
    /* This error is now reported in xref_tag, thus giving better
       location information.  */
    return next_field;

  /* Place the base class.  */
  if (!is_empty_class (basetype))
    {
      tree decl;

      /* The containing class is non-empty because it has a non-empty
         base class.  */
      CLASSTYPE_EMPTY_P (t) = 0;

      /* Create the FIELD_DECL.  */
      decl = build_decl (input_location,
                         FIELD_DECL, NULL_TREE, CLASSTYPE_AS_BASE (basetype));
      DECL_ARTIFICIAL (decl) = 1;
      DECL_IGNORED_P (decl) = 1;
      DECL_FIELD_CONTEXT (decl) = t;
      if (CLASSTYPE_AS_BASE (basetype))
        {
          DECL_SIZE (decl) = CLASSTYPE_SIZE (basetype);
          DECL_SIZE_UNIT (decl) = CLASSTYPE_SIZE_UNIT (basetype);
          DECL_ALIGN (decl) = CLASSTYPE_ALIGN (basetype);
          DECL_USER_ALIGN (decl) = CLASSTYPE_USER_ALIGN (basetype);
          DECL_MODE (decl) = TYPE_MODE (basetype);
          DECL_FIELD_IS_BASE (decl) = 1;

          /* Try to place the field.  It may take more than one try if we
             have a hard time placing the field without putting two
             objects of the same type at the same address.  */
          layout_nonempty_base_or_field (rli, decl, binfo, offsets);
          /* Add the new FIELD_DECL to the list of fields for T.  */
          TREE_CHAIN (decl) = *next_field;
          *next_field = decl;
          next_field = &TREE_CHAIN (decl);
        }
    }
  else
    {
      tree eoc;
      bool atend;

      /* On some platforms (ARM), even empty classes will not be
         byte-aligned.  */
      eoc = round_up_loc (input_location,
                      rli_size_unit_so_far (rli),
                      CLASSTYPE_ALIGN_UNIT (basetype));
      atend = layout_empty_base (rli, binfo, eoc, offsets);
      /* A nearly-empty class "has no proper base class that is empty,
         not morally virtual, and at an offset other than zero."  */
      if (!BINFO_VIRTUAL_P (binfo) && CLASSTYPE_NEARLY_EMPTY_P (t))
        {
          if (atend)
            CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
          /* The check above (used in G++ 3.2) is insufficient because
             an empty class placed at offset zero might itself have an
             empty base at a nonzero offset.  */
          else if (walk_subobject_offsets (basetype,
                                           empty_base_at_nonzero_offset_p,
                                           size_zero_node,
                                           /*offsets=*/NULL,
                                           /*max_offset=*/NULL_TREE,
                                           /*vbases_p=*/true))
            {
              if (abi_version_at_least (2))
                CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
              else
                warning (OPT_Wabi,
                         "class %qT will be considered nearly empty in a "
                         "future version of GCC", t);
            }
        }

      /* We do not create a FIELD_DECL for empty base classes because
         it might overlap some other field.  We want to be able to
         create CONSTRUCTORs for the class by iterating over the
         FIELD_DECLs, and the back end does not handle overlapping
         FIELD_DECLs.  */

      /* An empty virtual base causes a class to be non-empty
         -- but in that case we do not need to clear CLASSTYPE_EMPTY_P
         here because that was already done when the virtual table
         pointer was created.  */
    }

  /* Record the offsets of BINFO and its base subobjects.  */
  record_subobject_offsets (binfo,
                            BINFO_OFFSET (binfo),
                            offsets,
                            /*is_data_member=*/false);

  return next_field;
}

/* Layout all of the non-virtual base classes.  Record empty
   subobjects in OFFSETS.  T is the most derived type.  Return nonzero
   if the type cannot be nearly empty.  The fields created
   corresponding to the base classes will be inserted at
   *NEXT_FIELD.  */

static void
build_base_fields (record_layout_info rli,
                   splay_tree offsets, tree *next_field)
{
  /* Chain to hold all the new FIELD_DECLs which stand in for base class
     subobjects.  */
  tree t = rli->t;
  int n_baseclasses = BINFO_N_BASE_BINFOS (TYPE_BINFO (t));
  int i;

  /* The primary base class is always allocated first.  */
  if (CLASSTYPE_HAS_PRIMARY_BASE_P (t))
    next_field = build_base_field (rli, CLASSTYPE_PRIMARY_BINFO (t),
                                   offsets, next_field);

  /* Now allocate the rest of the bases.  */
  for (i = 0; i < n_baseclasses; ++i)
    {
      tree base_binfo;

      base_binfo = BINFO_BASE_BINFO (TYPE_BINFO (t), i);

      /* The primary base was already allocated above, so we don't
         need to allocate it again here.  */
      if (base_binfo == CLASSTYPE_PRIMARY_BINFO (t))
        continue;

      /* Virtual bases are added at the end (a primary virtual base
         will have already been added).  */
      if (BINFO_VIRTUAL_P (base_binfo))
        continue;

      next_field = build_base_field (rli, base_binfo,
                                     offsets, next_field);
    }
}

/* Go through the TYPE_METHODS of T issuing any appropriate
   diagnostics, figuring out which methods override which other
   methods, and so forth.  */

static void
check_methods (tree t)
{
  tree x;

  for (x = TYPE_METHODS (t); x; x = TREE_CHAIN (x))
    {
      check_for_override (x, t);
      if (DECL_PURE_VIRTUAL_P (x) && ! DECL_VINDEX (x))
        error ("initializer specified for non-virtual method %q+D", x);
      /* The name of the field is the original field name
         Save this in auxiliary field for later overloading.  */
      if (DECL_VINDEX (x))
        {
          TYPE_POLYMORPHIC_P (t) = 1;
          if (DECL_PURE_VIRTUAL_P (x))
            VEC_safe_push (tree, gc, CLASSTYPE_PURE_VIRTUALS (t), x);
        }
      /* All user-provided destructors are non-trivial.  */
      if (DECL_DESTRUCTOR_P (x) && user_provided_p (x))
        TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t) = 1;
    }
}

/* FN is a constructor or destructor.  Clone the declaration to create
   a specialized in-charge or not-in-charge version, as indicated by
   NAME.  */

static tree
build_clone (tree fn, tree name)
{
  tree parms;
  tree clone;

  /* Copy the function.  */
  clone = copy_decl (fn);
  /* Reset the function name.  */
  DECL_NAME (clone) = name;
  SET_DECL_ASSEMBLER_NAME (clone, NULL_TREE);
  /* Remember where this function came from.  */
  DECL_ABSTRACT_ORIGIN (clone) = fn;
  /* Make it easy to find the CLONE given the FN.  */
  TREE_CHAIN (clone) = TREE_CHAIN (fn);
  TREE_CHAIN (fn) = clone;

  /* If this is a template, do the rest on the DECL_TEMPLATE_RESULT.  */
  if (TREE_CODE (clone) == TEMPLATE_DECL)
    {
      tree result = build_clone (DECL_TEMPLATE_RESULT (clone), name);
      DECL_TEMPLATE_RESULT (clone) = result;
      DECL_TEMPLATE_INFO (result) = copy_node (DECL_TEMPLATE_INFO (result));
      DECL_TI_TEMPLATE (result) = clone;
      TREE_TYPE (clone) = TREE_TYPE (result);
      return clone;
    }

  DECL_CLONED_FUNCTION (clone) = fn;
  /* There's no pending inline data for this function.  */
  DECL_PENDING_INLINE_INFO (clone) = NULL;
  DECL_PENDING_INLINE_P (clone) = 0;

  /* The base-class destructor is not virtual.  */
  if (name == base_dtor_identifier)
    {
      DECL_VIRTUAL_P (clone) = 0;
      if (TREE_CODE (clone) != TEMPLATE_DECL)
        DECL_VINDEX (clone) = NULL_TREE;
    }

  /* If there was an in-charge parameter, drop it from the function
     type.  */
  if (DECL_HAS_IN_CHARGE_PARM_P (clone))
    {
      tree basetype;
      tree parmtypes;
      tree exceptions;

      exceptions = TYPE_RAISES_EXCEPTIONS (TREE_TYPE (clone));
      basetype = TYPE_METHOD_BASETYPE (TREE_TYPE (clone));
      parmtypes = TYPE_ARG_TYPES (TREE_TYPE (clone));
      /* Skip the `this' parameter.  */
      parmtypes = TREE_CHAIN (parmtypes);
      /* Skip the in-charge parameter.  */
      parmtypes = TREE_CHAIN (parmtypes);
      /* And the VTT parm, in a complete [cd]tor.  */
      if (DECL_HAS_VTT_PARM_P (fn)
          && ! DECL_NEEDS_VTT_PARM_P (clone))
        parmtypes = TREE_CHAIN (parmtypes);
       /* If this is subobject constructor or destructor, add the vtt
         parameter.  */
      TREE_TYPE (clone)
        = build_method_type_directly (basetype,
                                      TREE_TYPE (TREE_TYPE (clone)),
                                      parmtypes);
      if (exceptions)
        TREE_TYPE (clone) = build_exception_variant (TREE_TYPE (clone),
                                                     exceptions);
      TREE_TYPE (clone)
        = cp_build_type_attribute_variant (TREE_TYPE (clone),
                                           TYPE_ATTRIBUTES (TREE_TYPE (fn)));
    }

  /* Copy the function parameters.  */
  DECL_ARGUMENTS (clone) = copy_list (DECL_ARGUMENTS (clone));
  /* Remove the in-charge parameter.  */
  if (DECL_HAS_IN_CHARGE_PARM_P (clone))
    {
      TREE_CHAIN (DECL_ARGUMENTS (clone))
        = TREE_CHAIN (TREE_CHAIN (DECL_ARGUMENTS (clone)));
      DECL_HAS_IN_CHARGE_PARM_P (clone) = 0;
    }
  /* And the VTT parm, in a complete [cd]tor.  */
  if (DECL_HAS_VTT_PARM_P (fn))
    {
      if (DECL_NEEDS_VTT_PARM_P (clone))
        DECL_HAS_VTT_PARM_P (clone) = 1;
      else
        {
          TREE_CHAIN (DECL_ARGUMENTS (clone))
            = TREE_CHAIN (TREE_CHAIN (DECL_ARGUMENTS (clone)));
          DECL_HAS_VTT_PARM_P (clone) = 0;
        }
    }

  for (parms = DECL_ARGUMENTS (clone); parms; parms = TREE_CHAIN (parms))
    {
      DECL_CONTEXT (parms) = clone;
      cxx_dup_lang_specific_decl (parms);
    }

  /* Create the RTL for this function.  */
  SET_DECL_RTL (clone, NULL_RTX);
  rest_of_decl_compilation (clone, /*top_level=*/1, at_eof);

  if (pch_file)
    note_decl_for_pch (clone);

  return clone;
}

/* Implementation of DECL_CLONED_FUNCTION and DECL_CLONED_FUNCTION_P, do
   not invoke this function directly.

   For a non-thunk function, returns the address of the slot for storing
   the function it is a clone of.  Otherwise returns NULL_TREE.

   If JUST_TESTING, looks through TEMPLATE_DECL and returns NULL if
   cloned_function is unset.  This is to support the separate
   DECL_CLONED_FUNCTION and DECL_CLONED_FUNCTION_P modes; using the latter
   on a template makes sense, but not the former.  */

tree *
decl_cloned_function_p (const_tree decl, bool just_testing)
{
  tree *ptr;
  if (just_testing)
    decl = STRIP_TEMPLATE (decl);

  if (TREE_CODE (decl) != FUNCTION_DECL
      || !DECL_LANG_SPECIFIC (decl)
      || DECL_LANG_SPECIFIC (decl)->u.fn.thunk_p)
    {
#if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
      if (!just_testing)
        lang_check_failed (__FILE__, __LINE__, __FUNCTION__);
      else
#endif
        return NULL;
    }

  ptr = &DECL_LANG_SPECIFIC (decl)->u.fn.u5.cloned_function;
  if (just_testing && *ptr == NULL_TREE)
    return NULL;
  else
    return ptr;
}

/* Produce declarations for all appropriate clones of FN.  If
   UPDATE_METHOD_VEC_P is nonzero, the clones are added to the
   CLASTYPE_METHOD_VEC as well.  */

void
clone_function_decl (tree fn, int update_method_vec_p)
{
  tree clone;

  /* Avoid inappropriate cloning.  */
  if (TREE_CHAIN (fn)
      && DECL_CLONED_FUNCTION_P (TREE_CHAIN (fn)))
    return;

  if (DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (fn))
    {
      /* For each constructor, we need two variants: an in-charge version
         and a not-in-charge version.  */
      clone = build_clone (fn, complete_ctor_identifier);
      if (update_method_vec_p)
        add_method (DECL_CONTEXT (clone), clone, NULL_TREE);
      clone = build_clone (fn, base_ctor_identifier);
      if (update_method_vec_p)
        add_method (DECL_CONTEXT (clone), clone, NULL_TREE);
    }
  else
    {
      gcc_assert (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fn));

      /* For each destructor, we need three variants: an in-charge
         version, a not-in-charge version, and an in-charge deleting
         version.  We clone the deleting version first because that
         means it will go second on the TYPE_METHODS list -- and that
         corresponds to the correct layout order in the virtual
         function table.

         For a non-virtual destructor, we do not build a deleting
         destructor.  */
      if (DECL_VIRTUAL_P (fn))
        {
          clone = build_clone (fn, deleting_dtor_identifier);
          if (update_method_vec_p)
            add_method (DECL_CONTEXT (clone), clone, NULL_TREE);
        }
      clone = build_clone (fn, complete_dtor_identifier);
      if (update_method_vec_p)