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.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@129727 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 75 insertions, 4 deletions

diff --git a/gcc/tree-flow-inline.h b/gcc/tree-flow-inline.h
index b87f3d2fc84..4669588558e 100644
--- a/gcc/tree-flow-inline.h
+++ b/gcc/tree-flow-inline.h
@@ -1610,17 +1610,88 @@ static inline tree
 get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
 {
   subvar_t sv = get_subvars_for_var (var);
-  unsigned int i;
+  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;
 
-  /* ???  Binary search would be possible here.  */
-  for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
-    if (SFT_OFFSET (subvar) == offset)
+  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.  */