C++ PATCH: PR 8218

[Mark Mitchell]

This patch fixes C++ PR 8218, a compile-time performance regression.

I wanted to fix this completely, using interval trees, but that is too
risky for the branch.  This partial fix should be enough to handle
most cases, and is an appropriate first step in any event.

Tested on i686-pc-linux-gnu, applied on the mainline and on the
branch.

-- 
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

2002-10-21  Mark Mitchell  <mark@codesourcery.com>

	PR c++/8218
	* cp-tree.h (lang_type_class): Add contains_empty_class_p.
	(CLASSTYPE_CONTAINS_EMPTY_CLASS_P): New macro.
	* class.c (check_bases): Update CLASSTYPE_CONTAINS_EMPTY_CLASS_P.
	(check_field_decls): Likewise.
	(layout_class_type): Likewise.
	(finish_struct_1): Initialize it.
	(walk_subobject_offsets): Use it to prune searches.

Index: class.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/class.c,v
retrieving revision 1.480
diff -c -p -r1.480 class.c
*** class.c	18 Oct 2002 21:46:53 -0000	1.480
--- class.c	21 Oct 2002 08:38:08 -0000
*************** check_bases (t, cant_have_default_ctor_p
*** 1352,1357 ****
--- 1352,1359 ----
        TYPE_OVERLOADS_ARRAY_REF (t) |= TYPE_OVERLOADS_ARRAY_REF (basetype);
        TYPE_OVERLOADS_ARROW (t) |= TYPE_OVERLOADS_ARROW (basetype);
        TYPE_POLYMORPHIC_P (t) |= TYPE_POLYMORPHIC_P (basetype);
+       CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t) 
+ 	|= CLASSTYPE_CONTAINS_EMPTY_CLASS_P (basetype);
      }
  }
  
*************** check_field_decls (tree t, tree *access_
*** 3167,3176 ****
--- 3169,3186 ----
  	    ;
  	  else
  	    {
+ 	      tree element_type;
+ 
  	      /* 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.  */
+ 	      element_type = strip_array_types (type);
+ 	      if (CLASS_TYPE_P (element_type) 
+ 		  && CLASSTYPE_CONTAINS_EMPTY_CLASS_P (element_type))
+ 		CLASSTYPE_CONTAINS_EMPTY_CLASS_P (element_type) = 1;
  	    }
  	}
  
*************** walk_subobject_offsets (type, f, offset,
*** 3440,3445 ****
--- 3450,3459 ----
        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)
*************** walk_subobject_offsets (type, f, offset,
*** 3523,3531 ****
--- 3537,3551 ----
      }
    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.  */
*************** layout_class_type (tree t, int *vfuns_p,
*** 4988,4993 ****
--- 5008,5017 ----
    else
      CLASSTYPE_AS_BASE (t) = t;
  
+   /* Every empty class contains an empty class.  */
+   if (CLASSTYPE_EMPTY_P (t))
+     CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t) = 1;
+ 
    /* Set the TYPE_DECL for this type to contain the right
       value for DECL_OFFSET, so that we can use it as part
       of a COMPONENT_REF for multiple inheritance.  */
*************** finish_struct_1 (t)
*** 5076,5085 ****
  
    fixup_inline_methods (t);
    
!   /* Assume that the class is both empty and nearly empty; we'll clear
!      these flag if necessary.  */
    CLASSTYPE_EMPTY_P (t) = 1;
    CLASSTYPE_NEARLY_EMPTY_P (t) = 1;
  
    /* Do end-of-class semantic processing: checking the validity of the
       bases and members and add implicitly generated methods.  */
--- 5100,5110 ----
  
    fixup_inline_methods (t);
    
!   /* Make assumptions about the class; we'll reset the flags if
!      necessary.  */
    CLASSTYPE_EMPTY_P (t) = 1;
    CLASSTYPE_NEARLY_EMPTY_P (t) = 1;
+   CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t) = 0;
  
    /* Do end-of-class semantic processing: checking the validity of the
       bases and members and add implicitly generated methods.  */
Index: cp-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/cp-tree.h,v
retrieving revision 1.760
diff -c -p -r1.760 cp-tree.h
*** cp-tree.h	15 Oct 2002 23:59:19 -0000	1.760
--- cp-tree.h	21 Oct 2002 08:38:09 -0000
*************** struct lang_type_class GTY(())
*** 1135,1140 ****
--- 1135,1141 ----
    unsigned anon_aggr : 1;
    unsigned non_zero_init : 1;
    unsigned empty_p : 1;
+   unsigned contains_empty_class_p : 1;
  
    /* When adding a flag here, consider whether or not it ought to
       apply to a template instance if it applies to the template.  If
*************** struct lang_type_class GTY(())
*** 1143,1149 ****
    /* There are some bits left to fill out a 32-bit word.  Keep track
       of this by updating the size of this bitfield whenever you add or
       remove a flag.  */
!   unsigned dummy : 5;
  
    int vsize;
  
--- 1144,1150 ----
    /* There are some bits left to fill out a 32-bit word.  Keep track
       of this by updating the size of this bitfield whenever you add or
       remove a flag.  */
!   unsigned dummy : 4;
  
    int vsize;
  
*************** struct lang_type GTY(())
*** 1456,1461 ****
--- 1457,1466 ----
     virtual function table pointer.  */
  #define CLASSTYPE_NEARLY_EMPTY_P(NODE) \
    (LANG_TYPE_CLASS_CHECK (NODE)->nearly_empty_p)
+ 
+ /* Nonzero if this class contains an empty subobject.  */
+ #define CLASSTYPE_CONTAINS_EMPTY_CLASS_P(NODE) \
+   (LANG_TYPE_CLASS_CHECK (NODE)->contains_empty_class_p)
  
  /* A list of class types of which this type is a friend.  The
     TREE_VALUE is normally a TYPE, but will be a TEMPLATE_DECL in the