C++ PATCH: PR 16273

[Mark Mitchell <mark at codesourcery dot com>]

[Resend: I also applied this to the 3.4 branch, but failed to mention
that the first time.]

This PR is about a test case which caused us to use 650MB.  With this
patch, it's now 40MB.  (The fix is to avoid generating temporary
TREE_LISTs that we don't need.)

There's a corresponding decrease in time, but how much seems to depend
a lot on how well the memory system has adapted.  The first time I ran
the test case with the unpatched compiler, it took 45s -- but
rerunning it a few times go it down to about 12s.  With the patched
compiler, it takes about 6s, reliably.

There are more improvements that could be made, but I think that with
this fix, this test case is no longer a major problem, so I'm closing
the PR.

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

--
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

2004-08-12  Mark Mitchell  <mark@codesourcery.com>

	PR c++/16273
	* class.c (count_depth_data): New type.
	(dfs_depth_post): New function.
	(dfs_depth_q): Likewise.
	(find_final_overrider_data_s): Change type of vpath.
	Add vpath_list.
	(dfs_find_final_overrider_1): New function.
	(dfs_find_final_overrider): Use it.
	(dfs_find_final_overrider_q): Adjust use of vpath.
	(dfs_find_final_overrider_post): Likewise.
	(find_final_overrider): Use dfs_depth.  Allocate and deallocate
	vpath_list.

Index: class.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/class.c,v
retrieving revision 1.650
retrieving revision 1.652
diff -c -5 -p -r1.650 -r1.652
*** class.c	6 Aug 2004 10:40:35 -0000	1.650
--- class.c	12 Aug 2004 18:03:15 -0000	1.652
*************** base_derived_from (tree derived, tree ba
*** 1840,1944 ****
  		!= 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 most derived class in the hierarchy.  */
    tree most_derived_type;
    /* The candidate overriders.  */
    tree candidates;
!   /* Binfos which inherited virtually on the current path.  */
!   tree vpath;
  } find_final_overrider_data;
  
! /* Called from find_final_overrider via dfs_walk.  */
  
! static tree
! dfs_find_final_overrider (tree binfo, void* data)
  {
!   find_final_overrider_data *ffod = (find_final_overrider_data *) data;
  
!   if (binfo == ffod->declaring_base)
      {
!       /* We've found a path to the declaring base.  Walk the path from
! 	 derived to base, looking for an overrider for FN.  */
!       tree path, probe, vpath;
! 
!       /* Build the path, using the inheritance chain and record of
! 	 virtual inheritance.  */
!       for (path = NULL_TREE, probe = binfo, vpath = ffod->vpath;;)
  	{
! 	  path = tree_cons (NULL_TREE, probe, path);
! 	  if (same_type_p (BINFO_TYPE (probe), ffod->most_derived_type))
! 	    break;
! 	  if (BINFO_VIRTUAL_P (probe))
! 	    {
! 	      probe = TREE_VALUE (vpath);
! 	      vpath = TREE_CHAIN (vpath);
! 	    }
  	  else
! 	    probe = BINFO_INHERITANCE_CHAIN (probe);
! 	}
!       /* Now walk path, looking for overrides.  */
!       for (; path; path = TREE_CHAIN (path))
! 	{
! 	  tree method = look_for_overrides_here
! 	    (BINFO_TYPE (TREE_VALUE (path)), ffod->fn);
! 	  
! 	  if (method)
! 	    {
! 	      tree *candidate = &ffod->candidates;
! 	      path = TREE_VALUE (path);
! 
! 	      /* 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), path))
! 		    return NULL_TREE;
! 		  /* If METHOD overrides *CANDIDATE, remove *CANDIDATE.  */
! 		  if (base_derived_from (path, TREE_VALUE (*candidate)))
! 		    *candidate = TREE_CHAIN (*candidate);
! 		  else
! 		    candidate = &TREE_CHAIN (*candidate);
! 		}
! 	      
! 	      /* Add the new function.  */
! 	      ffod->candidates = tree_cons (method, path, ffod->candidates);
! 	      break;
! 	    }
  	}
      }
  
    return NULL_TREE;
  }
  
  static tree
  dfs_find_final_overrider_q (tree derived, int ix, void *data)
  {
    tree binfo = BINFO_BASE_BINFO (derived, ix);
    find_final_overrider_data *ffod = (find_final_overrider_data *) data;
  
    if (BINFO_VIRTUAL_P (binfo))
!     ffod->vpath = tree_cons (NULL_TREE, derived, ffod->vpath);
    
    return binfo;
  }
  
  static tree
  dfs_find_final_overrider_post (tree binfo, void *data)
  {
    find_final_overrider_data *ffod = (find_final_overrider_data *) data;
  
!   if (BINFO_VIRTUAL_P (binfo) && TREE_CHAIN (ffod->vpath))
!     ffod->vpath = TREE_CHAIN (ffod->vpath);
    
    return NULL_TREE;
  }
  
  /* Returns a TREE_LIST whose TREE_PURPOSE is the final overrider for
--- 1840,1978 ----
  		!= NULL_TREE);
      }
    return false;
  }
  
+ typedef struct count_depth_data {
+   /* The depth of the current subobject, with "1" as the depth of the
+      most derived object in the hierarchy.  */
+   size_t depth;
+   /* The maximum depth found so far.  */
+   size_t max_depth;
+ } count_depth_data;
+ 
+ /* Called from find_final_overrider via dfs_walk.  */
+ 
+ static tree
+ dfs_depth_post (tree binfo ATTRIBUTE_UNUSED, void *data)
+ {
+   count_depth_data *cd = (count_depth_data *) data;
+   if (cd->depth > cd->max_depth)
+     cd->max_depth = cd->depth;
+   cd->depth--;
+   return NULL_TREE;
+ }
+ 
+ /* Called from find_final_overrider via dfs_walk.  */
+ 
+ static tree
+ dfs_depth_q (tree derived, int i, void *data)
+ {
+   count_depth_data *cd = (count_depth_data *) data;
+   cd->depth++;
+   return BINFO_BASE_BINFO (derived, i);
+ }
+ 
  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 most derived class in the hierarchy.  */
    tree most_derived_type;
    /* The candidate overriders.  */
    tree candidates;
!   /* Each entry in this array is the next-most-derived class for a
!      virtual base class along the current path.  */
!   tree *vpath_list;
!   /* A pointer one past the top of the VPATH_LIST.  */
!   tree *vpath;
  } 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, 
! 			    tree *vpath, 
! 			    find_final_overrider_data *ffod)
  {
!   tree method;
  
!   /* If BINFO is not the most derived type, try a more derived class.
!      A definition there will overrider a definition here.  */
!   if (!same_type_p (BINFO_TYPE (binfo), ffod->most_derived_type))
!     {
!       tree derived;
! 
!       if (BINFO_VIRTUAL_P (binfo))
! 	derived = *--vpath;
!       else
! 	derived = BINFO_INHERITANCE_CHAIN (binfo);
!       if (dfs_find_final_overrider_1 (derived, vpath, ffod))
! 	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 (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->vpath, ffod);
+ 
    return NULL_TREE;
  }
  
  static tree
  dfs_find_final_overrider_q (tree derived, int ix, void *data)
  {
    tree binfo = BINFO_BASE_BINFO (derived, ix);
    find_final_overrider_data *ffod = (find_final_overrider_data *) data;
  
    if (BINFO_VIRTUAL_P (binfo))
!     *ffod->vpath++ = derived;
    
    return binfo;
  }
  
  static tree
  dfs_find_final_overrider_post (tree binfo, void *data)
  {
    find_final_overrider_data *ffod = (find_final_overrider_data *) data;
  
!   if (BINFO_VIRTUAL_P (binfo))
!     ffod->vpath--;
    
    return NULL_TREE;
  }
  
  /* Returns a TREE_LIST whose TREE_PURPOSE is the final overrider for
*************** dfs_find_final_overrider_post (tree binf
*** 1948,1957 ****
--- 1982,1992 ----
  
  static tree
  find_final_overrider (tree derived, tree binfo, tree fn)
  {
    find_final_overrider_data ffod;
+   count_depth_data cd;
  
    /* Getting this right is a little tricky.  This is valid:
  
         struct S { virtual void f (); };
         struct T { virtual void f (); };
*************** find_final_overrider (tree derived, tree
*** 1969,1991 ****
       
       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);
!   
    ffod.fn = fn;
    ffod.declaring_base = binfo;
    ffod.most_derived_type = BINFO_TYPE (derived);
    ffod.candidates = NULL_TREE;
!   ffod.vpath = NULL_TREE;
  
    dfs_walk_real (derived,
  		 dfs_find_final_overrider,
  		 dfs_find_final_overrider_post,
  		 dfs_find_final_overrider_q,
  		 &ffod);
  
    /* If there was no winner, issue an error message.  */
    if (!ffod.candidates || TREE_CHAIN (ffod.candidates))
      {
        error ("no unique final overrider for `%D' in `%T'", fn, 
  	     BINFO_TYPE (derived));
--- 2004,2034 ----
       
       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.  */
!   cd.depth = 0;
!   cd.max_depth = 0;
!   dfs_walk (derived, dfs_depth_post, dfs_depth_q, &cd);
! 
    ffod.fn = fn;
    ffod.declaring_base = binfo;
    ffod.most_derived_type = BINFO_TYPE (derived);
    ffod.candidates = NULL_TREE;
!   ffod.vpath_list = (tree *) xcalloc (cd.max_depth, sizeof (tree));
!   ffod.vpath = ffod.vpath_list;
  
    dfs_walk_real (derived,
  		 dfs_find_final_overrider,
  		 dfs_find_final_overrider_post,
  		 dfs_find_final_overrider_q,
  		 &ffod);
  
+   free (ffod.vpath_list);
+ 
    /* If there was no winner, issue an error message.  */
    if (!ffod.candidates || TREE_CHAIN (ffod.candidates))
      {
        error ("no unique final overrider for `%D' in `%T'", fn, 
  	     BINFO_TYPE (derived));