[PATCH] Fix PR29512, O(c^N) complexity algorithm in the i386 backend

[Richard Guenther]

This removes two O(c^N) (with c >= 2) algorithms which caused the testcase
in PR29512 to take >980 minutes to compile at -O0 (the reporter canceled
the compile at that point).  With the patch an unoptimized, checking
enabled compiler finishes after 5s.

The problem is that both classify_argument and 
contains_128bit_aligned_vector_p walk both BINFOs and TYPE_FIELDs
recursively but recursing through the functions itself, not restricting
to the BINFO or TYPE_FIELD part.  But the BINFO walking is redundant
completely anyway, as we are only interested in seeing all structure
data members which are also available by walking the TYPE_FIELDs like
the rest of the middle-end does.

Bootstrapped and tested on x86_64-unknown-linux-gnu, a selection of
C++ applications produces identical assembler output before and after
the patch.

Compile time for those C++ applications is unaffected by this patch
(though I didn't check -O0 compiles).

Ok for mainline?  (note this doesn't seem to be a regression other than
a regression from i686 to x86_64)

Thanks,
Richard.

:ADDPATCH i386:

2006-10-20  Richard Guenther  <rguenther@suse.de>

	PR target/29512
	* config/i386/i386.c (classify_argument): Remove redundant
	walking of the BINFOs.
	(contains_128bit_aligned_vector_p): Likewise.

Index: config/i386/i386.c
===================================================================
*** config/i386/i386.c	(revision 117885)
--- config/i386/i386.c	(working copy)
*************** classify_argument (enum machine_mode mod
*** 2951,2982 ****
        switch (TREE_CODE (type))
  	{
  	case RECORD_TYPE:
- 	  /* For classes first merge in the field of the subclasses.  */
- 	  if (TYPE_BINFO (type))
- 	    {
- 	      tree binfo, base_binfo;
- 	      int basenum;
- 
- 	      for (binfo = TYPE_BINFO (type), basenum = 0;
- 		   BINFO_BASE_ITERATE (binfo, basenum, base_binfo); basenum++)
- 		{
- 		   int num;
- 		   int offset = tree_low_cst (BINFO_OFFSET (base_binfo), 0) * 8;
- 		   tree type = BINFO_TYPE (base_binfo);
- 
- 		   num = classify_argument (TYPE_MODE (type),
- 					    type, subclasses,
- 					    (offset + bit_offset) % 256);
- 		   if (!num)
- 		     return 0;
- 		   for (i = 0; i < num; i++)
- 		     {
- 		       int pos = (offset + (bit_offset % 64)) / 8 / 8;
- 		       classes[i + pos] =
- 			 merge_classes (subclasses[i], classes[i + pos]);
- 		     }
- 		}
- 	    }
  	  /* And now merge the fields of structure.  */
  	  for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
  	    {
--- 2951,2956 ----
*************** classify_argument (enum machine_mode mod
*** 3044,3053 ****
  	case QUAL_UNION_TYPE:
  	  /* Unions are similar to RECORD_TYPE but offset is always 0.
  	     */
- 
- 	  /* Unions are not derived.  */
- 	  gcc_assert (!TYPE_BINFO (type)
- 		      || !BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
  	  for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
  	    {
  	      if (TREE_CODE (field) == FIELD_DECL)
--- 3018,3023 ----
*************** contains_128bit_aligned_vector_p (tree t
*** 3735,3752 ****
  	  {
  	    tree field;
  
! 	    if (TYPE_BINFO (type))
! 	      {
! 		tree binfo, base_binfo;
! 		int i;
! 
! 		for (binfo = TYPE_BINFO (type), i = 0;
! 		     BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
! 		  if (contains_128bit_aligned_vector_p
! 		      (BINFO_TYPE (base_binfo)))
! 		    return true;
! 	      }
! 	    /* And now merge the fields of structure.  */
  	    for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
  	      {
  		if (TREE_CODE (field) == FIELD_DECL
--- 3705,3711 ----
  	  {
  	    tree field;
  
! 	    /* Walk all the structure fields.  */
  	    for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
  	      {
  		if (TREE_CODE (field) == FIELD_DECL