aliasing_component_refs_p tweek

Hi,
this patch makes aliasing_component_refs_p little bit stronger, especially
with LTO increasing number of disambiguations on tramp3d by 2%.

It took me a while to uderstand that function so a bit summary what it
does.

Function analyzes chains of nested references like

 ref1: a.b.c.d.e
 ref2: c.d.f

(Here I assume that type of a is a and type of b is b etc.)

On such chains it looks for outermost common type (c) and then compares
accesss c.d.e and c.d.f for range overlap. This is safe because we know
that both copies of type c are either overlaping or completely
different.

Walk is done in both directions so

 ref1: c.d.f
 ref2: a.b.c.d.e

Gives the same answer.

In the final step it is assumed that the reference chains do not have
common type and may reference one to another only if one is continuation
of the other (with some intermediate steps omitted).

So function is organized as follows

 1) perform walk of ref1 looking for type of base of ref2.
    If we sucessful use base+offset oracle.
 2) perform walk of ref2 looking for type of base of ref1
    If we sucessful use base+offset oracle.
 3) assume that chains are disjoiont and see of base type of one is subset
    of ref type of the other (i.e. one can be can be a continuation of the
    chain).

Now same_type_for_tbaa can return -1 for some odd cases which include the case
where TYPE_CANONICAL==NULL the function gives up.  This is quite common with
LTO because TYPE_CANONICAL is NULL for pointers, vectors and arrays and thus we
often give up after the innermost reference.

If the first walk in 1) terminates with -1 then it still makes sense to do the
walk in 2) and see if the common type is found.  If there is no common type we
need to give up on the final test.

I wonder if as an optimization we do not want to terminate the walk when one
type is too small to hold the second.

Bootstrapped/regtested x86_64-linux, OK?

	* tree-ssa-alias.c (aliasing_component_refs_p): Walk references
	both directions even if first walk fails.

On Mon, 6 May 2019, Jan Hubicka wrote:

> Hi,
> this patch makes aliasing_component_refs_p little bit stronger, especially
> with LTO increasing number of disambiguations on tramp3d by 2%.
> 
> It took me a while to uderstand that function so a bit summary what it
> does.
> 
> Function analyzes chains of nested references like
> 
>  ref1: a.b.c.d.e
>  ref2: c.d.f
> 
> (Here I assume that type of a is a and type of b is b etc.)
> 
> On such chains it looks for outermost common type (c) and then compares
> accesss c.d.e and c.d.f for range overlap. This is safe because we know
> that both copies of type c are either overlaping or completely
> different.
> 
> Walk is done in both directions so
> 
>  ref1: c.d.f
>  ref2: a.b.c.d.e
> 
> Gives the same answer.
> 
> In the final step it is assumed that the reference chains do not have
> common type and may reference one to another only if one is continuation
> of the other (with some intermediate steps omitted).
> 
> So function is organized as follows
> 
>  1) perform walk of ref1 looking for type of base of ref2.
>     If we sucessful use base+offset oracle.
>  2) perform walk of ref2 looking for type of base of ref1
>     If we sucessful use base+offset oracle.
>  3) assume that chains are disjoiont and see of base type of one is subset
>     of ref type of the other (i.e. one can be can be a continuation of the
>     chain).
> 
> Now same_type_for_tbaa can return -1 for some odd cases which include the case
> where TYPE_CANONICAL==NULL the function gives up.  This is quite common with
> LTO because TYPE_CANONICAL is NULL for pointers, vectors and arrays and thus we
> often give up after the innermost reference.
>
> If the first walk in 1) terminates with -1 then it still makes sense to do the
> walk in 2) and see if the common type is found.  If there is no common type we
> need to give up on the final test.
> 
> I wonder if as an optimization we do not want to terminate the walk when one
> type is too small to hold the second.
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> 	* tree-ssa-alias.c (aliasing_component_refs_p): Walk references
> 	both directions even if first walk fails.
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 270877)
> +++ tree-ssa-alias.c	(working copy)
> @@ -814,10 +841,7 @@ aliasing_component_refs_p (tree ref1,
>  	 && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
>      refp = &TREE_OPERAND (*refp, 0);
>    same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
> -  /* If we couldn't compare types we have to bail out.  */
> -  if (same_p == -1)
> -    return true;
> -  else if (same_p == 1)
> +  if (same_p == 1)
>      {
>        poly_int64 offadj, sztmp, msztmp;
>        bool reverse;
> @@ -827,24 +851,31 @@ aliasing_component_refs_p (tree ref1,
>        offset1 -= offadj;
>        return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
>      }
> -  /* If we didn't find a common base, try the other way around.  */
> -  refp = &ref1;
> -  while (handled_component_p (*refp)
> -	 && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
> -    refp = &TREE_OPERAND (*refp, 0);
> -  same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
> -  /* If we couldn't compare types we have to bail out.  */
> -  if (same_p == -1)
> -    return true;
> -  else if (same_p == 1)
> +  else 
>      {

No need for the else {} and thus indenting the rest since the if ()
arm always returns from the function.

OK with eliding this else { } wrapping.

Thanks,
Richard.

> -      poly_int64 offadj, sztmp, msztmp;
> -      bool reverse;
> -      get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
> -      offset1 -= offadj;
> -      get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
> -      offset2 -= offadj;
> -      return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
> +      int same_p2;
> +
> +      /* If we didn't find a common base, try the other way around.  */
> +      refp = &ref1;
> +      while (handled_component_p (*refp)
> +	     && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
> +	refp = &TREE_OPERAND (*refp, 0);
> +      same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type2);
> +      if (same_p2 == 1)
> +	{
> +	  poly_int64 offadj, sztmp, msztmp;
> +	  bool reverse;
> +	  get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
> +	  offset1 -= offadj;
> +	  get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
> +	  offset2 -= offadj;
> +	  return ranges_maybe_overlap_p (offset1, max_size1,
> +					 offset2, max_size2);
> +	}
> +      /* In the remaining test we assume that there is no overlapping type
> +	 at all.  So if we are unsure, we need to give up.  */
> +      else if (same_p == -1 || same_p2 == -1)
> +	return true;
>      }
>  
>    /* If we have two type access paths B1.path1 and B2.path2 they may
>

> 
> No need for the else {} and thus indenting the rest since the if ()
> arm always returns from the function.
> 
> OK with eliding this else { } wrapping.

Ah, right, I changed the function bit too many times :)
Here is updated patch I re-tested and comitted.

	* tree-ssa-alias.c (aliasing_component_refs_p): Continue looking
	for comparaible types in the second direction even if first one
	hits incomparable type.
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 270877)
+++ tree-ssa-alias.c	(working copy)
@@ -795,7 +795,7 @@ aliasing_component_refs_p (tree ref1,
   tree base1, base2;
   tree type1, type2;
   tree *refp;
-  int same_p;
+  int same_p, same_p2;
 
   /* Choose bases and base types to search for.  */
   base1 = ref1;
@@ -814,10 +814,7 @@ aliasing_component_refs_p (tree ref1,
 	 && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
     refp = &TREE_OPERAND (*refp, 0);
   same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
-  /* If we couldn't compare types we have to bail out.  */
-  if (same_p == -1)
-    return true;
-  else if (same_p == 1)
+  if (same_p == 1)
     {
       poly_int64 offadj, sztmp, msztmp;
       bool reverse;
@@ -827,26 +824,31 @@ aliasing_component_refs_p (tree ref1,
       offset1 -= offadj;
       return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
     }
+
   /* If we didn't find a common base, try the other way around.  */
   refp = &ref1;
   while (handled_component_p (*refp)
 	 && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
     refp = &TREE_OPERAND (*refp, 0);
-  same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
-  /* If we couldn't compare types we have to bail out.  */
-  if (same_p == -1)
-    return true;
-  else if (same_p == 1)
+  same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type2);
+  if (same_p2 == 1)
     {
       poly_int64 offadj, sztmp, msztmp;
       bool reverse;
       get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
       offset1 -= offadj;
       get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
       offset2 -= offadj;
-      return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
+      return ranges_maybe_overlap_p (offset1, max_size1,
+				     offset2, max_size2);
     }
 
+  /* In the remaining test we assume that there is no overlapping type
+     at all.  So if we are unsure, we need to give up.  */
+  if (same_p == -1 || same_p2 == -1)
+    return true;
+
   /* If we have two type access paths B1.path1 and B2.path2 they may
      only alias if either B1 is in B2.path2 or B2 is in B1.path1.
      But we can still have a path that goes B1.path1...B2.path2 with