[RFA] Transparent alias suport part 10: Fix base+offset alias analysis oracle WRT aliases

Hi,
this patch fixes base+offset alias oracles to consider variable aliases.
With this patch and one extra hack I can LTO bootstrap with variale symbol
merging disabled in lto-symtab.c

The basic idea is simple - there is new comparer compare_base_decls which knows
how to handle aliases via symbol table's address_equal_to predicate.
I went through the sources and tried to find all places where we compare bases
for equality and replace the copmarsion by this new predicate.

Bootstrapped/regtested x86_64-linux, looks sane?

Honza

	* tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Use compare_base_decls
	(nonoverlapping_component_refs_of_decl_p): Update sanity check.
	(decl_refs_may_alias_p): Use compare_base_decls.
	* alias.c: Include cgraph.h
	(rtx_equal_for_memref_p): Use rtx_equal_for_memref_p.
	(compare_base_decls): New function.
	(base_alias_check): Likewise.
	(memrefs_conflict_p): Likewise.
	(nonoverlapping_memrefs_p): Likewise.
	* alias.h (compare_base_decls): Declare.

	* gcc.c-torture/execute/alias-2.c: New testcase.

On Wed, 9 Dec 2015, Jan Hubicka wrote:

> Hi,
> this patch fixes base+offset alias oracles to consider variable aliases.
> With this patch and one extra hack I can LTO bootstrap with variale symbol
> merging disabled in lto-symtab.c
> 
> The basic idea is simple - there is new comparer compare_base_decls which knows
> how to handle aliases via symbol table's address_equal_to predicate.
> I went through the sources and tried to find all places where we compare bases
> for equality and replace the copmarsion by this new predicate.
> 
> Bootstrapped/regtested x86_64-linux, looks sane?
> 
> Honza
> 
> 	* tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Use compare_base_decls
> 	(nonoverlapping_component_refs_of_decl_p): Update sanity check.
> 	(decl_refs_may_alias_p): Use compare_base_decls.
> 	* alias.c: Include cgraph.h
> 	(rtx_equal_for_memref_p): Use rtx_equal_for_memref_p.
> 	(compare_base_decls): New function.
> 	(base_alias_check): Likewise.
> 	(memrefs_conflict_p): Likewise.
> 	(nonoverlapping_memrefs_p): Likewise.
> 	* alias.h (compare_base_decls): Declare.
> 
> 	* gcc.c-torture/execute/alias-2.c: New testcase.
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 231438)
> +++ tree-ssa-alias.c	(working copy)
> @@ -194,7 +194,7 @@ ptr_deref_may_alias_decl_p (tree ptr, tr
>  	ptr = TREE_OPERAND (base, 0);
>        else if (base
>  	       && DECL_P (base))
> -	return base == decl;
> +	return compare_base_decls (base, decl) != 0;
>        else if (base
>  	       && CONSTANT_CLASS_P (base))
>  	return false;
> @@ -805,8 +805,10 @@ nonoverlapping_component_refs_of_decl_p
>        ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0);
>      }
>  
> -  /* We must have the same base DECL.  */
> -  gcc_assert (ref1 == ref2);
> +  /* Bases must be either same or uncomparable.  */
> +  gcc_checking_assert (ref1 == ref2
> +		       || (DECL_P (ref1) && DECL_P (ref2)
> +			   && compare_base_decls (ref1, ref2)));

I prefer explicit != 0 here.

>  
>    /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
>       rank.  This is sufficient because we start from the same DECL and you
> @@ -989,7 +991,7 @@ decl_refs_may_alias_p (tree ref1, tree b
>    gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
>  
>    /* If both references are based on different variables, they cannot alias.  */
> -  if (base1 != base2)
> +  if (compare_base_decls (base1, base2) == 0)
>      return false;
>  
>    /* If both references are based on the same variable, they cannot alias if
> Index: testsuite/gcc.c-torture/execute/alias-2.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/alias-2.c	(revision 0)
> +++ testsuite/gcc.c-torture/execute/alias-2.c	(revision 0)
> @@ -0,0 +1,12 @@
> +/* { dg-require-alias "" } */
> +int a[10]={};
> +extern int b[10] __attribute__ ((alias("a")));
> +int off;
> +main()
> +{
> +  b[off]=1;
> +  a[off]=2;
> +  if (b[off]!=2)
> +   __builtin_abort ();
> +  return 0;
> +}
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 231438)
> +++ alias.c	(working copy)
> @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3.
>  #include "langhooks.h"
>  #include "cfganal.h"
>  #include "rtl-iter.h"
> +#include "cgraph.h"
>  
>  /* The aliasing API provided here solves related but different problems:
>  
> @@ -1747,7 +1748,15 @@ rtx_equal_for_memref_p (const_rtx x, con
>        return LABEL_REF_LABEL (x) == LABEL_REF_LABEL (y);
>  
>      case SYMBOL_REF:
> -      return XSTR (x, 0) == XSTR (y, 0);
> +      {
> +	tree x_decl = SYMBOL_REF_DECL (x);
> +	tree y_decl = SYMBOL_REF_DECL (y);
> +
> +	if (!x_decl || !y_decl)
> +	  return XSTR (x, 0) == XSTR (y, 0);
> +	else
> +	  return compare_base_decls (x_decl, y_decl) == 1;
> +      }
>  
>      case ENTRY_VALUE:
>        /* This is magic, don't go through canonicalization et al.  */
> @@ -2010,6 +2019,31 @@ may_be_sp_based_p (rtx x)
>    return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
>  }
>  
> +/* BASE1 and BASE2 are decls.  Return 1 if they refer to same object, 0
> +   if they refer to different objects and -1 if we can not decide.  */
> +
> +int
> +compare_base_decls (tree base1, tree base2)
> +{
> +  int ret;
> +  gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
> +  if (base1 == base2)
> +    return 1;
> +
> +  bool in_symtab1 = decl_in_symtab_p (base1);
> +  bool in_symtab2 = decl_in_symtab_p (base2);
> +
> +  /* Declarations of non-automatic variables may have aliases.  All other
> +     decls are unique.  */
> +  if (in_symtab1 != in_symtab2 || !in_symtab1)
> +    return 0;
> +  ret = symtab_node::get_create (base1)->equal_address_to
> +		 (symtab_node::get_create (base2), true);

And I don't like ::get_create too much, why's ::get not enough here?
Predicates really shouldn't end up changing global state.

> +  if (ret == 2)
> +    return -1;
> +  return ret;
> +}
> +
>  /* Return 0 if the addresses X and Y are known to point to different
>     objects, 1 if they might be pointers to the same object.  */
>  
> @@ -2047,6 +2081,17 @@ base_alias_check (rtx x, rtx x_base, rtx
>    if (rtx_equal_p (x_base, y_base))
>      return 1;
>  
> +  if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
> +    {
> +      tree x_decl = SYMBOL_REF_DECL (x_base);
> +      tree y_decl = SYMBOL_REF_DECL (y_base);
> +
> +      /* We can assume that no stores are made to labels.  */
> +      if (!x_decl || !y_decl)
> +	return 0;
> +      return compare_base_decls (x_decl, y_decl) != 0;
> +    }
> +
>    /* The base addresses are different expressions.  If they are not accessed
>       via AND, there is no conflict.  We can bring knowledge of object
>       alignment into play here.  For example, on alpha, "char a, b;" can
> @@ -2268,11 +2313,32 @@ memrefs_conflict_p (int xsize, rtx x, in
>    else
>      y = addr_side_effect_eval (y, abs (ysize), 0);
>  
> -  if (rtx_equal_for_memref_p (x, y))
> +  if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> +    {
> +      tree x_decl = SYMBOL_REF_DECL (x);
> +      tree y_decl = SYMBOL_REF_DECL (y);
> +      int cmp;
> +
> +      if (!x_decl || !y_decl)
> +	cmp = offset_overlap_p (c, xsize, ysize);
> +      else
> +        cmp = compare_base_decls (x_decl, y_decl);
> +
> +      /* If both decls are the same, decide by offsets.  */
> +      if (cmp == 1)
> +        return offset_overlap_p (c, xsize, ysize);

please refactor to avoid doing this twice WRT !x_decl / !y_decl

Ok with these changes.

Thanks,
Richard.

> +      /* If decls are different or we know by offsets that there is no overlap,
> +	 we win.  */
> +      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> +	return 0;
> +      /* Decls may or may not be different and offsets overlap....*/
> +      return -1;
> +    }
> +  else if (rtx_equal_for_memref_p (x, y))
>      {
>        return offset_overlap_p (c, xsize, ysize);
>      }
>  
>    /* This code used to check for conflicts involving stack references and
>       globals but the base address alias code now handles these cases.  */
>  
> @@ -2636,7 +2703,7 @@ nonoverlapping_memrefs_p (const_rtx x, c
>       are constants or if one is a constant and the other a pointer into the
>       stack frame.  Otherwise a different base means we can't tell if they
>       overlap or not.  */
> -  if (! rtx_equal_p (basex, basey))
> +  if (! compare_base_decls (exprx, expry))
>      return ((CONSTANT_P (basex) && CONSTANT_P (basey))
>  	    || (CONSTANT_P (basex) && REG_P (basey)
>  		&& REGNO_PTR_FRAME_P (REGNO (basey)))
> @@ -2647,6 +2714,10 @@ nonoverlapping_memrefs_p (const_rtx x, c
>    if (loop_invariant)
>      return 0;              
>  
> +  /* Offset based disambiguation is OK even if we do not know that the
> +     declarations are necessarily different
> +    (i.e. compare_base_decls (exprx, expry) == 2)  */
> +
>    sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
>  	   : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
>  	   : -1);
> Index: alias.h
> ===================================================================
> --- alias.h	(revision 231438)
> +++ alias.h	(working copy)
> @@ -36,6 +36,7 @@ extern int nonoverlapping_memrefs_p (con
>  extern void dump_alias_stats_in_alias_c (FILE *s);
>  tree reference_alias_ptr_type (tree);
>  bool alias_ptr_types_compatible_p (tree, tree);
> +int compare_base_decls (tree, tree);
>  
>  /* This alias set can be used to force a memory to conflict with all
>     other memories, creating a barrier across which no memory reference
> 
>

> > +  bool in_symtab1 = decl_in_symtab_p (base1);
> > +  bool in_symtab2 = decl_in_symtab_p (base2);
> > +
> > +  /* Declarations of non-automatic variables may have aliases.  All other
> > +     decls are unique.  */
> > +  if (in_symtab1 != in_symtab2 || !in_symtab1)
> > +    return 0;
> > +  ret = symtab_node::get_create (base1)->equal_address_to
> > +		 (symtab_node::get_create (base2), true);
> 
> And I don't like ::get_create too much, why's ::get not enough here?
> Predicates really shouldn't end up changing global state.

I will re-test with ::get here.  I think I only copied the code from folding.
One case we can get decls w/o corresponding symbol table entries during late
compilation is when we introduce a new builtin call.  We may just revisit
all those place and be sure we inser that to symbol table, but that is for next
stage1.

> 
> please refactor to avoid doing this twice WRT !x_decl / !y_decl
> 
> Ok with these changes.

Thanks!
I think I also need to update IPA-PTA code to work on alias targets same way as
I did for ipa-reference (need to construct a testcase) and we sould be down to
missed optimizations and not wrongcodes with extra aliases
(GVN/CSE/operand_equal_p should know about aliases to make them completely
no-op)

Honza
> 
> Thanks,
> Richard.
> 
> > +      /* If decls are different or we know by offsets that there is no overlap,
> > +	 we win.  */
> > +      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > +	return 0;
> > +      /* Decls may or may not be different and offsets overlap....*/
> > +      return -1;
> > +    }
> > +  else if (rtx_equal_for_memref_p (x, y))
> >      {
> >        return offset_overlap_p (c, xsize, ysize);
> >      }
> >  
> >    /* This code used to check for conflicts involving stack references and
> >       globals but the base address alias code now handles these cases.  */
> >  
> > @@ -2636,7 +2703,7 @@ nonoverlapping_memrefs_p (const_rtx x, c
> >       are constants or if one is a constant and the other a pointer into the
> >       stack frame.  Otherwise a different base means we can't tell if they
> >       overlap or not.  */
> > -  if (! rtx_equal_p (basex, basey))
> > +  if (! compare_base_decls (exprx, expry))
> >      return ((CONSTANT_P (basex) && CONSTANT_P (basey))
> >  	    || (CONSTANT_P (basex) && REG_P (basey)
> >  		&& REGNO_PTR_FRAME_P (REGNO (basey)))
> > @@ -2647,6 +2714,10 @@ nonoverlapping_memrefs_p (const_rtx x, c
> >    if (loop_invariant)
> >      return 0;              
> >  
> > +  /* Offset based disambiguation is OK even if we do not know that the
> > +     declarations are necessarily different
> > +    (i.e. compare_base_decls (exprx, expry) == 2)  */
> > +
> >    sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx))
> >  	   : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
> >  	   : -1);
> > Index: alias.h
> > ===================================================================
> > --- alias.h	(revision 231438)
> > +++ alias.h	(working copy)
> > @@ -36,6 +36,7 @@ extern int nonoverlapping_memrefs_p (con
> >  extern void dump_alias_stats_in_alias_c (FILE *s);
> >  tree reference_alias_ptr_type (tree);
> >  bool alias_ptr_types_compatible_p (tree, tree);
> > +int compare_base_decls (tree, tree);
> >  
> >  /* This alias set can be used to force a memory to conflict with all
> >     other memories, creating a barrier across which no memory reference
> > 
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)