Improve handling of table overflows in modref_ref_node

gcc/ChangeLog:

	* ipa-modref-tree.h (modref_access_node::merge): Break out
	logic combining offsets and logic merging ranges to ...
	(modref_access_node::combined_offsets): ... here
	(modref_access_node::update2): ... here
	(modref_access_node::closer_pair_p): New member function.
	(modref_access_node::forced_merge): New member function.
	(modre_ref_node::insert): Do merging when table is full.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/modref-9.c: New test.

2 files changed, 264 insertions, 49 deletions

diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h
index a86e684..6a9ed5c 100644
--- a/gcc/ipa-modref-tree.h
+++ b/gcc/ipa-modref-tree.h
@@ -196,8 +196,9 @@ struct GTY(()) modref_access_node
      was prolonged and punt when there are too many.  */
   bool merge (const modref_access_node &a, bool record_adjustments)
     {
-      poly_int64 aoffset_adj = 0, offset_adj = 0;
-      poly_int64 new_parm_offset = parm_offset;
+      poly_int64 offset1 = 0;
+      poly_int64 aoffset1 = 0;
+      poly_int64 new_parm_offset = 0;
 
       /* We assume that containment was tested earlier.  */
       gcc_checking_assert (!contains (a) && !a.contains (*this));
@@ -209,29 +210,13 @@ struct GTY(()) modref_access_node
 	    {
 	      if (!a.parm_offset_known)
 		return false;
-	      if (known_le (a.parm_offset, parm_offset))
-		{
-		  offset_adj = (parm_offset - a.parm_offset)
-				<< LOG2_BITS_PER_UNIT;
-		  aoffset_adj = 0;
-		  new_parm_offset = a.parm_offset;
-		}
-	      else if (known_le (parm_offset, a.parm_offset))
-		{
-		  aoffset_adj = (a.parm_offset - parm_offset)
-				 << LOG2_BITS_PER_UNIT;
-		  offset_adj = 0;
-		}
-	      else
+	      if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
 		return false;
 	    }
 	}
       /* See if we can merge ranges.  */
       if (range_info_useful_p ())
 	{
-	  poly_int64 offset1 = offset + offset_adj;
-	  poly_int64 aoffset1 = a.offset + aoffset_adj;
-
 	  /* In this case we have containment that should be
 	     handled earlier.  */
 	  gcc_checking_assert (a.range_info_useful_p ());
@@ -255,46 +240,211 @@ struct GTY(()) modref_access_node
 	    return false;
 	  if (known_le (offset1, aoffset1))
 	    {
-	      if (!known_size_p (max_size))
+	      if (!known_size_p (max_size)
+		  || known_ge (offset1 + max_size, aoffset1))
 		{
-		  update (new_parm_offset, offset1, size, max_size,
-			  record_adjustments);
-		  return true;
-		}
-	      else if (known_ge (offset1 + max_size, aoffset1))
-		{
-		  poly_int64 new_max_size = max_size;
-		  if (known_le (max_size, a.max_size + aoffset1 - offset1))
-		    new_max_size = a.max_size + aoffset1 - offset1;
-		  update (new_parm_offset, offset1, size, new_max_size,
-			  record_adjustments);
+		  update2 (new_parm_offset, offset1, size, max_size,
+			   aoffset1, a.size, a.max_size,
+			   record_adjustments);
 		  return true;
 		}
 	    }
 	  else if (known_le (aoffset1, offset1))
 	    {
-	      if (!known_size_p (a.max_size))
-		{
-		  update (new_parm_offset, aoffset1, size, a.max_size,
-			  record_adjustments);
-		  return true;
-		}
-	      else if (known_ge (aoffset1 + a.max_size, offset1))
+	      if (!known_size_p (a.max_size)
+		  || known_ge (aoffset1 + a.max_size, offset1))
 		{
-		  poly_int64 new_max_size = a.max_size;
-		  if (known_le (a.max_size, max_size + offset1 - aoffset1))
-		    new_max_size = max_size + offset1 - aoffset1;
-		  update (new_parm_offset, aoffset1, size, new_max_size,
-			  record_adjustments);
+		  update2 (new_parm_offset, offset1, size, max_size,
+			   aoffset1, a.size, a.max_size,
+			   record_adjustments);
 		  return true;
 		}
 	    }
 	  return false;
 	}
-      update (new_parm_offset, offset + offset_adj,
+      update (new_parm_offset, offset1,
 	      size, max_size, record_adjustments);
       return true;
     }
+  /* Return true if A1 and B1 can be merged with lower informatoin
+     less than A2 and B2.
+     Assume that no containment or lossless merging is possible.  */
+  static bool closer_pair_p (const modref_access_node &a1,
+			     const modref_access_node &b1,
+			     const modref_access_node &a2,
+			     const modref_access_node &b2)
+    {
+      /* Merging different parm indexes comes to complete loss
+	 of range info.  */
+      if (a1.parm_index != b1.parm_index)
+	return false;
+      if (a2.parm_index != b2.parm_index)
+	return true;
+      /* If parm is known and parm indexes are the same we should
+	 already have containment.  */
+      gcc_checking_assert (a1.parm_offset_known && b1.parm_offset_known);
+      gcc_checking_assert (a2.parm_offset_known && b2.parm_offset_known);
+
+      /* First normalize offsets for parm offsets.  */
+      poly_int64 new_parm_offset, offseta1, offsetb1, offseta2, offsetb2;
+      if (!a1.combined_offsets (b1, &new_parm_offset, &offseta1, &offsetb1)
+	  || !a2.combined_offsets (b2, &new_parm_offset, &offseta2, &offsetb2))
+	gcc_unreachable ();
+
+
+      /* Now compute distnace of the intervals.  */
+      poly_int64 dist1, dist2;
+      if (known_le (offseta1, offsetb1))
+	{
+	  if (!known_size_p (a1.max_size))
+	    dist1 = 0;
+	  else
+	    dist1 = offsetb1 - offseta1 - a1.max_size;
+	}
+      else
+	{
+	  if (!known_size_p (b1.max_size))
+	    dist1 = 0;
+	  else
+	    dist1 = offseta1 - offsetb1 - b1.max_size;
+	}
+      if (known_le (offseta2, offsetb2))
+	{
+	  if (!known_size_p (a2.max_size))
+	    dist2 = 0;
+	  else
+	    dist2 = offsetb2 - offseta2 - a2.max_size;
+	}
+      else
+	{
+	  if (!known_size_p (b2.max_size))
+	    dist2 = 0;
+	  else
+	    dist2 = offseta2 - offsetb2 - b2.max_size;
+	}
+      /* It may happen that intervals overlap in case size
+	 is different.  Preffer the overlap to non-overlap.  */
+      if (known_lt (dist1, 0) && known_ge (dist2, 0))
+	return true;
+      if (known_lt (dist2, 0) && known_ge (dist1, 0))
+	return false;
+      if (known_lt (dist1, 0))
+	/* If both overlaps minimize overlap.  */
+	return known_le (dist2, dist1);
+      else
+	/* If both are disjoint look for smaller distance.  */
+	return known_le (dist1, dist2);
+    }
+
+  /* Merge in access A while losing precision.  */
+  void forced_merge (const modref_access_node &a, bool record_adjustments)
+    {
+      if (parm_index != a.parm_index)
+	{
+	  gcc_checking_assert (parm_index != -1);
+	  parm_index = -1;
+	  return;
+	}
+
+      /* We assume that containment and lossless merging
+	 was tested earlier.  */
+      gcc_checking_assert (!contains (a) && !a.contains (*this)
+			   && !merge (a, record_adjustments));
+      gcc_checking_assert (parm_offset_known && a.parm_offset_known);
+
+      poly_int64 new_parm_offset, offset1, aoffset1;
+      if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
+	{
+	  parm_offset_known = false;
+	  return;
+	}
+      gcc_checking_assert (range_info_useful_p ()
+			   && a.range_info_useful_p ());
+      if (record_adjustments)
+	adjustments += a.adjustments;
+      update2 (new_parm_offset,
+	       offset1, size, max_size,
+	       aoffset1, a.size, a.max_size,
+	       record_adjustments);
+    }
+private:
+  /* Merge two ranges both starting at parm_offset1 and update THIS
+     with result.  */
+  void update2 (poly_int64 parm_offset1,
+		poly_int64 offset1, poly_int64 size1, poly_int64 max_size1,
+		poly_int64 offset2, poly_int64 size2, poly_int64 max_size2,
+		bool record_adjustments)
+    {
+      poly_int64 new_size = size1;
+
+      if (!known_size_p (size2)
+	  || known_le (size2, size1))
+	new_size = size2;
+      else
+	gcc_checking_assert (known_le (size1, size2));
+
+      if (known_le (offset1, offset2))
+	;
+      else if (known_le (offset2, offset1))
+	{
+	  std::swap (offset1, offset2);
+	  std::swap (max_size1, max_size2);
+	}
+      else
+	gcc_unreachable ();
+
+      poly_int64 new_max_size;
+
+      if (!known_size_p (max_size1))
+	new_max_size = max_size1;
+      else if (!known_size_p (max_size2))
+	new_max_size = max_size2;
+      else
+	{
+	  max_size2 = max_size2 + offset2 - offset1;
+	  if (known_le (max_size, max_size2))
+	    new_max_size = max_size2;
+	  else if (known_le (max_size2, max_size))
+	    new_max_size = max_size;
+	  else
+	    gcc_unreachable ();
+	}
+
+      update (parm_offset1, offset1,
+	      new_size, new_max_size, record_adjustments);
+    }
+  /* Given access nodes THIS and A, return true if they
+     can be done with common parm_offsets.  In this case
+     return parm offset in new_parm_offset, new_offset
+     which is start of range in THIS and new_aoffset that
+     is start of range in A.  */
+  bool combined_offsets (const modref_access_node &a,
+			 poly_int64 *new_parm_offset,
+			 poly_int64 *new_offset,
+			 poly_int64 *new_aoffset) const
+    {
+      gcc_checking_assert (parm_offset_known && a.parm_offset_known);
+      if (known_le (a.parm_offset, parm_offset))
+	{
+	  *new_offset = offset
+			+ ((parm_offset - a.parm_offset)
+			   << LOG2_BITS_PER_UNIT);
+	  *new_aoffset = a.offset;
+	  *new_parm_offset = a.parm_offset;
+	  return true;
+	}
+      else if (known_le (parm_offset, a.parm_offset))
+	{
+	  *new_aoffset = a.offset
+	  		  + ((a.parm_offset - parm_offset)
+			     << LOG2_BITS_PER_UNIT);
+	  *new_offset = offset;
+	  *new_parm_offset = parm_offset;
+	  return true;
+	}
+      else
+	return false;
+    }
 };
 
 /* Access node specifying no useful info.  */
@@ -348,7 +498,7 @@ struct GTY((user)) modref_ref_node
       return false;
 
     /* Otherwise, insert a node for the ref of the access under the base.  */
-    size_t i;
+    size_t i, j;
     modref_access_node *a2;
 
     if (flag_checking)
@@ -390,11 +540,61 @@ struct GTY((user)) modref_ref_node
        all accesses and bail out.  */
     if (accesses && accesses->length () >= max_accesses)
       {
-	if (dump_file)
+	if (max_accesses < 2)
+	  {
+	    collapse ();
+	    if (dump_file)
+	      fprintf (dump_file,
+		       "--param param=modref-max-accesses limit reached;"
+		       " collapsing\n");
+	    return true;
+	  }
+	/* Find least harmful merge and perform it.  */
+	int best1 = -1, best2 = -1;
+	FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
+	  {
+	    for (j = i + 1; j < accesses->length (); j++)
+	      if (best1 < 0
+		  || modref_access_node::closer_pair_p
+		       (*a2, (*accesses)[j],
+			(*accesses)[best1],
+			best2 < 0 ? a : (*accesses)[best2]))
+		{
+		  best1 = i;
+		  best2 = j;
+		}
+	    if (modref_access_node::closer_pair_p
+		       (*a2, a,
+			(*accesses)[best1],
+			best2 < 0 ? a : (*accesses)[best2]))
+	      {
+		best1 = i;
+		best2 = -1;
+	      }
+	  }
+	(*accesses)[best1].forced_merge (best2 < 0 ? a : (*accesses)[best2],
+					 record_adjustments);
+	if (!(*accesses)[best1].useful_p ())
+	  {
+	    collapse ();
+	    if (dump_file)
+	      fprintf (dump_file,
+		       "--param param=modref-max-accesses limit reached;"
+		       " collapsing\n");
+	    return true;
+	  }
+	if (dump_file && best2 >= 0)
 	  fprintf (dump_file,
-		   "--param param=modref-max-accesses limit reached\n");
-	collapse ();
-	return true;
+		   "--param param=modref-max-accesses limit reached;"
+		   " merging %i and %i\n", best1, best2);
+	else if (dump_file)
+	  fprintf (dump_file,
+		   "--param param=modref-max-accesses limit reached;"
+		   " merging with %i\n", best1);
+	try_merge_with (best1);
+	if (best2 >= 0)
+	  insert_access (a, max_accesses, record_adjustments);
+	return 1;
       }
     a.adjustments = 0;
     vec_safe_push (accesses, a);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-9.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-9.c
new file mode 100644
index 0000000..02de2f0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-9.c
@@ -0,0 +1,15 @@
+/* { dg-options "-O2 --param modref-max-accesses=2 -fdump-tree-modref1"  } */
+/* { dg-do compile } */
+void
+test(char *a)
+{
+  a[0] = 0;
+  a[1] = 1;
+  a[3] = 3;
+  a[7] = 7;
+  a[9] = 9;
+}
+/* We allow only two accesses per function.
+   It is best to group together {0,1,3} and {7,9}.  */
+/* { dg-final { scan-tree-dump "access: Parm 0 param offset:0 offset:0 size:8 max_size:32" "modref1" } } */
+/* { dg-final { scan-tree-dump "access: Parm 0 param offset:7 offset:0 size:8 max_size:24" "modref1" } } */