Do not ask alias subset query when access patch can not extend

Do not ask alias subset query when access patch can not extend

[Jan Hubicka]

Hi
in most common cases we have access paths that ends by read/write of a
non-composite type.  When aliasing_component_refs_p finds no match in
the acccess path it asks alias oracle if the one alias set is subset of
other to figure out whether one access path can be extended to the
other.

This is unnecessarily conservatie especially for pointers where we say tru
for
 foo->ptr
 bar->ptr
where foo and bar are two structures containing pointers of different type.

This patch bypasses the alis oracle check for non-composite types.  Along with
yesterday patch and patch to handle pointers in types_same_for_tbaa_p we now
get:

  refs_may_alias_p: 3019081 disambiguations, 3318862 queries
  ref_maybe_used_by_call_p: 7112 disambiguations, 3044693 queries
  call_may_clobber_ref_p: 817 disambiguations, 817 queries
  aliasing_component_ref_p: 2259 disambiguations, 17881 queries
  TBAA oracle: 1421561 disambiguations 2922798 queries
               552636 are in alias set 0
               569791 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               260727 are dependent in the DAG
               118083 are aritificially in conflict with void *

Compared to:

  refs_may_alias_p: 3013678 disambiguations, 3314059 queries
  ref_maybe_used_by_call_p: 7112 disambiguations, 3039278 queries
  call_may_clobber_ref_p: 817 disambiguations, 817 queries
  aliasing_component_ref_p: 636 disambiguations, 15844 queries
  TBAA oracle: 1417999 disambiguations 2915696 queries
               552182 are in alias set 0
               569795 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               259437 are dependent in the DAG
               116283 are aritificially in conflict with void *

(my original prototype patch did about 14000 disambiguations out of 40000
querries while passing testuite, so we are slowly getting closer).

I have a testcase but it depends on same_type_for_tbaa not giving up on
pointers, so I plan to send it as a followup.

Bootstrapped/regtested x86_64-linux (all languages&LTO), OK?

	* tree-ssa-alias.c (access_patch_may_continue_p): New function.
	(aliasing_component_refs_p): Use it.

Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 271747)
@@ -822,6 +842,16 @@ same_type_for_tbaa (tree type1, tree typ
   return 0;
 }
 
+/* Return true if TYPE is a composite type (i.e. we may apply one of handled
+   components on it).  */
+
+static bool
+access_patch_may_continue_p (tree type)
+{
+  return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
+	 || TREE_CODE (type) == COMPLEX_TYPE;
+}
+
 /* Determine if the two component references REF1 and REF2 which are
    based on access types TYPE1 and TYPE2 and of which at least one is based
    on an indirect reference may alias.  REF2 is the only one that can
@@ -965,6 +1028,7 @@ aliasing_component_refs_p (tree ref1,
      if there is no B2 in the tail of path1 and no B1 on the
      tail of path2.  */
   if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
+      && (access_patch_may_continue_p (TREE_TYPE (ref2)))
       && (base1_alias_set == ref2_alias_set
           || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
     {
@@ -974,6 +1038,7 @@ aliasing_component_refs_p (tree ref1,
   /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
   if (!ref2_is_decl
       && compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
+      && (access_patch_may_continue_p (TREE_TYPE (ref1)))
       && (base2_alias_set == ref1_alias_set
 	  || alias_set_subset_of (base2_alias_set, ref1_alias_set)))
     {

Re: Do not ask alias subset query when access patch can not extend

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 4307 bytes --]

On Fri, 31 May 2019, Jan Hubicka wrote:

> Hi
> in most common cases we have access paths that ends by read/write of a
> non-composite type.  When aliasing_component_refs_p finds no match in
> the acccess path it asks alias oracle if the one alias set is subset of
> other to figure out whether one access path can be extended to the
> other.
> 
> This is unnecessarily conservatie especially for pointers where we say tru
> for
>  foo->ptr
>  bar->ptr
> where foo and bar are two structures containing pointers of different type.
> 
> This patch bypasses the alis oracle check for non-composite types.  Along with
> yesterday patch and patch to handle pointers in types_same_for_tbaa_p we now
> get:
> 
>   refs_may_alias_p: 3019081 disambiguations, 3318862 queries
>   ref_maybe_used_by_call_p: 7112 disambiguations, 3044693 queries
>   call_may_clobber_ref_p: 817 disambiguations, 817 queries
>   aliasing_component_ref_p: 2259 disambiguations, 17881 queries
>   TBAA oracle: 1421561 disambiguations 2922798 queries
>                552636 are in alias set 0
>                569791 queries asked about the same object
>                0 queries asked about the same alias set
>                0 access volatile
>                260727 are dependent in the DAG
>                118083 are aritificially in conflict with void *
> 
> Compared to:
> 
>   refs_may_alias_p: 3013678 disambiguations, 3314059 queries
>   ref_maybe_used_by_call_p: 7112 disambiguations, 3039278 queries
>   call_may_clobber_ref_p: 817 disambiguations, 817 queries
>   aliasing_component_ref_p: 636 disambiguations, 15844 queries
>   TBAA oracle: 1417999 disambiguations 2915696 queries
>                552182 are in alias set 0
>                569795 queries asked about the same object
>                0 queries asked about the same alias set
>                0 access volatile
>                259437 are dependent in the DAG
>                116283 are aritificially in conflict with void *
> 
> (my original prototype patch did about 14000 disambiguations out of 40000
> querries while passing testuite, so we are slowly getting closer).
> 
> I have a testcase but it depends on same_type_for_tbaa not giving up on
> pointers, so I plan to send it as a followup.
> 
> Bootstrapped/regtested x86_64-linux (all languages&LTO), OK?
> 
> 	* tree-ssa-alias.c (access_patch_may_continue_p): New function.
> 	(aliasing_component_refs_p): Use it.
> 
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 271747)
> @@ -822,6 +842,16 @@ same_type_for_tbaa (tree type1, tree typ
>    return 0;
>  }
>  
> +/* Return true if TYPE is a composite type (i.e. we may apply one of handled
> +   components on it).  */
> +
> +static bool
> +access_patch_may_continue_p (tree type)

'path', but I think type_has_components_p would be a better fit?

> +{
> +  return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
> +	 || TREE_CODE (type) == COMPLEX_TYPE;
> +}
> +
>  /* Determine if the two component references REF1 and REF2 which are
>     based on access types TYPE1 and TYPE2 and of which at least one is based
>     on an indirect reference may alias.  REF2 is the only one that can
> @@ -965,6 +1028,7 @@ aliasing_component_refs_p (tree ref1,
>       if there is no B2 in the tail of path1 and no B1 on the
>       tail of path2.  */
>    if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
> +      && (access_patch_may_continue_p (TREE_TYPE (ref2)))

extra parens around the call here and below.

OK with all these issues fixed.

Richard.

>        && (base1_alias_set == ref2_alias_set
>            || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
>      {
> @@ -974,6 +1038,7 @@ aliasing_component_refs_p (tree ref1,
>    /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
>    if (!ref2_is_decl
>        && compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
> +      && (access_patch_may_continue_p (TREE_TYPE (ref1)))
>        && (base2_alias_set == ref1_alias_set
>  	  || alias_set_subset_of (base2_alias_set, ref1_alias_set)))
>      {
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG NÌrnberg)

Re: Do not ask alias subset query when access patch can not extend

[Jan Hubicka]

> > +/* Return true if TYPE is a composite type (i.e. we may apply one of handled
> > +   components on it).  */
> > +
> > +static bool
> > +access_patch_may_continue_p (tree type)
> 
> 'path', but I think type_has_components_p would be a better fit?

Thanks, looks better indeed!
> 
> > +{
> > +  return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
> > +	 || TREE_CODE (type) == COMPLEX_TYPE;
> > +}
> > +
> >  /* Determine if the two component references REF1 and REF2 which are
> >     based on access types TYPE1 and TYPE2 and of which at least one is based
> >     on an indirect reference may alias.  REF2 is the only one that can
> > @@ -965,6 +1028,7 @@ aliasing_component_refs_p (tree ref1,
> >       if there is no B2 in the tail of path1 and no B1 on the
> >       tail of path2.  */
> >    if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
> > +      && (access_patch_may_continue_p (TREE_TYPE (ref2)))
> 
> extra parens around the call here and below.
> 
> OK with all these issues fixed.

Thanks. That is leftover of a debug code to compare old and new oracle.
I will be more careful next time.

Honza
> 
> Richard.
> 
> >        && (base1_alias_set == ref2_alias_set
> >            || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
> >      {
> > @@ -974,6 +1038,7 @@ aliasing_component_refs_p (tree ref1,
> >    /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
> >    if (!ref2_is_decl
> >        && compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
> > +      && (access_patch_may_continue_p (TREE_TYPE (ref1)))
> >        && (base2_alias_set == ref1_alias_set
> >  	  || alias_set_subset_of (base2_alias_set, ref1_alias_set)))
> >      {
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
> GF: Felix ImendĂśrffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG NĂźrnberg)

Re: Do not ask alias subset query when access patch can not extend

[Bernhard Reutner-Fischer]

Honza,

On 31 May 2019 11:44:09 CEST, Jan Hubicka <hubicka@ucw.cz> wrote:

>Bootstrapped/regtested x86_64-linux (all languages&LTO), OK?
>
>	* tree-ssa-alias.c (access_patch_may_continue_p): New function.
>	(aliasing_component_refs_p): Use it.

s/patch/path/g

I suspect your fingers play tricks on you on this one more often than not, please double-check the (recent) tree for "_patch" and "patch_" :)

TIA,