[PATCH] More performance fallout from the PR33870 fix

[Richard Guenther <rguenther at suse dot de>]

This does more performance optimization on the PR33870 fix (and localizes
the fix to a single place again to be able to revert it w/o reverting the
performance work).  The performance improvements are from using binary
search instead of linear search and for verifying if the to-be added
SFT is in the MPT we are considering pointed-to SFTs from to avoid 
redundant work.

This gets us from 125s (49% operand scanning time) down to 91s (still 32%
operand scanning time) for tramp3d -O2 compile.  Still way higher than
before the fix for PR33870 (66s and only 5% operand scanning time).
The oprofile shows

samples  %        symbol name
55016     5.0405  add_vars_for_offset
43952     4.0268  bitmap_bit_p
30131     2.7606  walk_tree_1
24596     2.2534  htab_find_with_hash
22683     2.0782  ggc_alloc_stat

So we might consider going for the alternative approach of forcing
memory partitioning to honor the operand scanners pre-requesites of
not partitioning SFTs of one variable separately.

Bootstrapped and tested (for C and C++, all languages currently 
re-building) on x86_64-unknown-linux-gnu.

Richard.


2007-10-29  Richard Guenther  <rguenther@suse.de>

	* tree-flow-inline.h (get_subvar_at): Use binary search.
	(get_first_overlapping_subvar): New function to binary search
	for the first overlapping subvar.
	* tree-ssa-operands.c (add_vars_for_offset): Strip down to
	just handle adding subvars for a pointed-to subvar.  Optimize
	and use get_first_overlapping_subvar.
	(add_vars_for_bitmap): Fold into single caller.
	(add_virtual_operand): Streamline, inherit add_vars_for_bitmap
	and non pointed-to bits of add_vars_for_offset.

Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c	(revision 129715)
--- tree-ssa-operands.c	(working copy)
*************** access_can_touch_variable (tree ref, tre
*** 1386,1474 ****
     This is necessary because foop only actually points to foo's first
     member, so that is all the points-to set contains.  However, an access
     to foop->a may be touching some single SFT if we have created some
!    SFT's for a structure.  If AS_PTO is false, just add VAR to the vops.  */
  
  static bool
! add_vars_for_offset (tree full_ref, tree var, HOST_WIDE_INT offset,
! 		     HOST_WIDE_INT size, bool is_call_site, bool is_def,
! 		     bool as_pto)
  {
    bool added = false;
    subvar_t sv;
    unsigned int i;
-   tree subvar;
  
  
!   /* Call-clobbered tags may have non-call-clobbered
!      symbols in their alias sets.  Ignore them if we are
!      adding VOPs for a call site.  */
!   if (is_call_site && !is_call_clobbered (var))
      return false;
  
!   /* For SFTs we have to consider all subvariables of the parent var.  */
!   if (TREE_CODE (var) != STRUCT_FIELD_TAG
!       || !as_pto)
!     {
!       /* If we do not know the full reference tree or if the access is
! 	 unspecified [0, -1], we cannot prune it.  Otherwise try doing
! 	 so using access_can_touch_variable.  */
!       if (full_ref
! 	  && !(offset == 0 && size == -1)
! 	  && !access_can_touch_variable (full_ref, var, offset, size))
! 	return false;
! 
!       if (is_def)
! 	append_vdef (var);
!       else
! 	append_vuse (var);
!       return true;
!     }
! 
!   sv = get_subvars_for_var (SFT_PARENT_VAR (var));
!   for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
      {
!       /* Once we hit the end of the parts that could touch,
! 	 stop looking.  */
!       if (size != -1
! 	  && SFT_OFFSET (var) + offset + size <= SFT_OFFSET (subvar))
  	break;
!       if (overlap_subvar (SFT_OFFSET (var) + offset, size, subvar, NULL))
  	{
- 	  added = true;
  	  if (is_def)
  	    append_vdef (subvar);
  	  else
  	    append_vuse (subvar);
  	}
      }
-   return added;
- }
- 
- /* Consider all SFTs in ALIASES as points-to location and add virtual
-    operands for the SFT parent var for the access FULL_REF at OFFSET
-    and size SIZE.  IS_CALL_SITE is true if the stmt of the reference is
-    a call.  IS_DEF is true if we should add VDEF virtual operands,
-    otherwise we'll add VUSEs.  *NONE_ADDED is set to false once the first
-    virtual operand was added.  */
- 
- static void
- add_vars_for_bitmap (bitmap aliases, tree full_ref,
- 		     HOST_WIDE_INT offset, HOST_WIDE_INT size,
- 		     bool is_call_site, bool is_def, bool *none_added)
- {
-   bitmap_iterator bi;
-   unsigned int i;
- 
-   EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
-     {
-       tree al = referenced_var (i);
- 
-       gcc_assert (TREE_CODE (al) != MEMORY_PARTITION_TAG);
  
!       if (TREE_CODE (al) == STRUCT_FIELD_TAG)
! 	*none_added &= !add_vars_for_offset (full_ref, al, offset, size,
! 					     is_call_site, is_def, true);
!     }
  }
  
  /* Add VAR to the virtual operands array.  FLAGS is as in
--- 1386,1431 ----
     This is necessary because foop only actually points to foo's first
     member, so that is all the points-to set contains.  However, an access
     to foop->a may be touching some single SFT if we have created some
!    SFT's for a structure.  */
  
  static bool
! add_vars_for_offset (tree var,
! 		     unsigned HOST_WIDE_INT offset, unsigned HOST_WIDE_INT size,
! 		     bool is_def, bitmap mpt_vars)
  {
    bool added = false;
+   tree subvar;
    subvar_t sv;
    unsigned int i;
  
+   /* Adjust offset by the pointed-to location.  */
+   offset += SFT_OFFSET (var);
  
!   /* Add all subvars of var that overlap with the access.
!      Binary search for the first relevant SFT.  */
!   sv = get_subvars_for_var (SFT_PARENT_VAR (var));
!   if (!get_first_overlapping_subvar (sv, offset, size, &i))
      return false;
  
!   for (; VEC_iterate (tree, sv, i, subvar); ++i)
      {
!       if (size <= SFT_OFFSET (subvar) - offset)
  	break;
! 
!       /* Avoid adding a SFT that is contained in the same MPT as the
! 	 pointed-to location as this MPT will be added as alias anyway.  */
!       if (!mpt_vars
! 	  || !bitmap_bit_p (mpt_vars, DECL_UID (subvar)))
  	{
  	  if (is_def)
  	    append_vdef (subvar);
  	  else
  	    append_vuse (subvar);
  	}
+       added = true;
      }
  
!   return added;
  }
  
  /* Add VAR to the virtual operands array.  FLAGS is as in
*************** add_virtual_operand (tree var, stmt_ann_
*** 1552,1562 ****
  	     But only if we start with NMT aliases.  */
  	  if (TREE_CODE (al) == MEMORY_PARTITION_TAG
  	      && TREE_CODE (var) == NAME_MEMORY_TAG)
! 	    add_vars_for_bitmap (MPT_SYMBOLS (al), full_ref, offset, size,
! 				 is_call_site, flags & opf_def, &none_added);
! 	  none_added &= !add_vars_for_offset (full_ref, al, offset, size,
! 					      is_call_site, flags & opf_def,
! 					      TREE_CODE (var) == NAME_MEMORY_TAG);
  	}
  
        if (flags & opf_def)
--- 1509,1557 ----
  	     But only if we start with NMT aliases.  */
  	  if (TREE_CODE (al) == MEMORY_PARTITION_TAG
  	      && TREE_CODE (var) == NAME_MEMORY_TAG)
! 	    {
! 	      bitmap_iterator bi;
! 	      unsigned int i;
! 
! 	      EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (al), 0, i, bi)
! 		{
! 		  tree ptsft = referenced_var (i);
! 
! 		  if (TREE_CODE (ptsft) == STRUCT_FIELD_TAG)
! 		    none_added &= !add_vars_for_offset (ptsft, offset, size,
! 							flags & opf_def,
! 							MPT_SYMBOLS (al));
! 		}
! 	    }
! 
! 	  /* For SFTs we have to consider all subvariables of the parent var
! 	     if it is a potential points-to location.  */
! 	  if (TREE_CODE (al) == STRUCT_FIELD_TAG
! 	      && TREE_CODE (var) == NAME_MEMORY_TAG)
! 	    none_added &= !add_vars_for_offset (al, offset, size,
! 					        flags & opf_def, NULL);
! 	  else
! 	    {
! 	      /* Call-clobbered tags may have non-call-clobbered
! 		 symbols in their alias sets.  Ignore them if we are
! 		 adding VOPs for a call site.  */
! 	      if (is_call_site && !is_call_clobbered (al))
! 		 continue;
! 
! 	      /* If we do not know the full reference tree or if the access is
! 		 unspecified [0, -1], we cannot prune it.  Otherwise try doing
! 		 so using access_can_touch_variable.  */
! 	      if (full_ref
! 		  && !(offset == 0 && size == -1)
! 		  && !access_can_touch_variable (full_ref, al, offset, size))
! 		continue;
! 
! 	      if (flags & opf_def)
! 		append_vdef (al);
! 	      else
! 		append_vuse (al);
! 	      none_added = false;
! 	    }
  	}
  
        if (flags & opf_def)
Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h	(revision 129715)
--- tree-flow-inline.h	(working copy)
*************** static inline tree
*** 1610,1626 ****
  get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
  {
    subvar_t sv = get_subvars_for_var (var);
!   unsigned int i;
    tree subvar;
  
!   /* ???  Binary search would be possible here.  */
!   for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
!     if (SFT_OFFSET (subvar) == offset)
        return subvar;
  
    return NULL_TREE;
  }
  
  /* Return true if V is a tree that we can have subvars for.
     Normally, this is any aggregate type.  Also complex
     types which are not gimple registers can have subvars.  */
--- 1610,1697 ----
  get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
  {
    subvar_t sv = get_subvars_for_var (var);
!   int low, high;
! 
!   low = 0;
!   high = VEC_length (tree, sv) - 1;
!   while (low <= high)
!     {
!       int mid = (low + high) / 2;
!       tree subvar = VEC_index (tree, sv, mid);
!       if (SFT_OFFSET (subvar) == offset)
! 	return subvar;
!       else if (SFT_OFFSET (subvar) < offset)
! 	low = mid + 1;
!       else
! 	high = mid - 1;
!     }
! 
!   return NULL_TREE;
! }
! 
! 
! /* Return the first subvariable in SV that overlaps [offset, offset + size[.
!    NULL_TREE is returned, if there is no overlapping subvariable, else *I
!    is set to the index in the SV vector of the first overlap.  */
! 
! static inline tree
! get_first_overlapping_subvar (subvar_t sv, unsigned HOST_WIDE_INT offset,
! 			      unsigned HOST_WIDE_INT size, unsigned int *i)
! {
!   int low = 0;
!   int high = VEC_length (tree, sv) - 1;
!   int mid;
    tree subvar;
  
!   if (low > high)
!     return NULL_TREE;
! 
!   /* Binary search for offset.  */
!   do
!     {
!       mid = (low + high) / 2;
!       subvar = VEC_index (tree, sv, mid);
!       if (SFT_OFFSET (subvar) == offset)
! 	{
! 	  *i = mid;
! 	  return subvar;
! 	}
!       else if (SFT_OFFSET (subvar) < offset)
! 	low = mid + 1;
!       else
! 	high = mid - 1;
!     }
!   while (low <= high);
! 
!   /* As we didn't find a subvar with offset, adjust to return the
!      first overlapping one.  */
!   if (SFT_OFFSET (subvar) < offset
!       && SFT_OFFSET (subvar) + SFT_SIZE (subvar) <= offset)
!     {
!       mid += 1;
!       if ((unsigned)mid >= VEC_length (tree, sv))
! 	return NULL_TREE;
!       subvar = VEC_index (tree, sv, mid);
!     }
!   else if (SFT_OFFSET (subvar) > offset
! 	   && size <= SFT_OFFSET (subvar) - offset)
!     {
!       mid -= 1;
!       if (mid < 0)
! 	return NULL_TREE;
!       subvar = VEC_index (tree, sv, mid);
!     }
! 
!   if (overlap_subvar (offset, size, subvar, NULL))
!     {
!       *i = mid;
        return subvar;
+     }
  
    return NULL_TREE;
  }
  
+ 
  /* Return true if V is a tree that we can have subvars for.
     Normally, this is any aggregate type.  Also complex
     types which are not gimple registers can have subvars.  */