Type-based alias analysis and alias sets

Type-based alias analysis and alias sets

[Eric Botcazou]

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

Hi Richard,

I just (re-)discovered that the new TBAA machinery is quite aggressive and 
breaks cases that used to work in Ada (-O2 testcase for SPARC64 attached).

The problem boils down to this:

  D.1416_1 = (struct p__rec &) &r.F;
  r.F = ...
  ... = D.1416_1->d;

DSE computes that the store to r.F is dead and eliminates it at -O2 because 
ultimately nonaliasing_component_refs_p returns false:

  /* 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.  */
  return false;

[Shouldn't nonaliasing_component_refs_p be named aliasing_component_refs_p or 
component_refs_may_alias_p instead]?

Yes, it's a blatant type-punning case but all the structure types are given 
the same alias set (struct p__rec, type of r, type of F) and 'd' is not 
addressable so all the memory accesses are done with the same alias set.

The root of the problem is that same_type_for_tbaa never returns true since 
the types don't have the same TYPE_CANONICAL (rightfully so, they are not 
equivalent) so we fall back to the final return of nonaliasing_c_r_p.

Shouldn't this final return be 'true' instead of 'false', like the final 
return in indirect_ref_may_alias_decl_p, so that the ultimate fallback is the 
comparison of alias sets like it used to be?

Thanks in advance.

-- 
Eric Botcazou

[-- Attachment #2: p.adb --]
[-- Type: text/x-adasrc, Size: 258 bytes --]

procedure P is

  type Rec (D : Natural) is record
    S : String (1..D);
  end record;

  procedure Test (R : Rec) is
  begin
    if R.D /= 9 then
      raise Program_Error;
    end if;
  end;

  R : Rec(9);

begin
  R := (9, "123456789");
  Test (R);
end;

Re: Type-based alias analysis and alias sets

[Richard Guenther]

On Fri, 23 Oct 2009, Eric Botcazou wrote:

> Hi Richard,
> 
> I just (re-)discovered that the new TBAA machinery is quite aggressive and 
> breaks cases that used to work in Ada (-O2 testcase for SPARC64 attached).
> 
> The problem boils down to this:
> 
>   D.1416_1 = (struct p__rec &) &r.F;
>   r.F = ...
>   ... = D.1416_1->d;
> 
> DSE computes that the store to r.F is dead and eliminates it at -O2 because 
> ultimately nonaliasing_component_refs_p returns false:
> 
>   /* 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.  */
>   return false;
> 
> [Shouldn't nonaliasing_component_refs_p be named aliasing_component_refs_p or 
> component_refs_may_alias_p instead]?

Err, yes ;)  I named it after the RTL variant in alias.c.

> Yes, it's a blatant type-punning case but all the structure types are given 
> the same alias set (struct p__rec, type of r, type of F) and 'd' is not 
> addressable so all the memory accesses are done with the same alias set.
> 
> The root of the problem is that same_type_for_tbaa never returns true since 
> the types don't have the same TYPE_CANONICAL (rightfully so, they are not 
> equivalent) so we fall back to the final return of nonaliasing_c_r_p.
> 
> Shouldn't this final return be 'true' instead of 'false', like the final 
> return in indirect_ref_may_alias_decl_p, so that the ultimate fallback is the 
> comparison of alias sets like it used to be?

I changed this default to false somewhen in the past.  There was a
big fat comment there on the alias-improvements branch (where I
wondered if returning false would be a safe thing to do).

I didn't find (or could construct) a single C or C++ testcase that
wasn't fine with the new default, so I switched it (IIRC the default
is disambiguating the most cases).

I'm fine with switching it back though, this time with a comment
explaining why it is not safe (instead of just speculating) and
a testcase (I guess you now indeed have one).  Care to prepare
a patch?

Thanks,
Richard.

Re: Type-based alias analysis and alias sets

[Eric Botcazou]

> I changed this default to false somewhen in the past.  There was a
> big fat comment there on the alias-improvements branch (where I
> wondered if returning false would be a safe thing to do).
>
> I didn't find (or could construct) a single C or C++ testcase that
> wasn't fine with the new default, so I switched it (IIRC the default
> is disambiguating the most cases).

OK, thanks for the explanation.

> I'm fine with switching it back though, this time with a comment
> explaining why it is not safe (instead of just speculating) and
> a testcase (I guess you now indeed have one).  Care to prepare
> a patch?

Sure.  Any preference for the new name of nonaliasing_component_refs_p?

The reduced testcase was extracted from ACATS c64106c:

		=== acats tests ===
FAIL:	c64106c

		=== acats Summary ===
# of expected passes		2314
# of unexpected failures	1
Native configuration is sparc64-sun-solaris2.10

-- 
Eric Botcazou

Re: Type-based alias analysis and alias sets

[Eric Botcazou]

> I didn't find (or could construct) a single C or C++ testcase that
> wasn't fine with the new default, so I switched it (IIRC the default
> is disambiguating the most cases).

Yes, the default is the optimistic answer and a few tests rely on it:

FAIL: gcc.dg/tree-ssa/alias-18.c scan-tree-dump fre "with 1"
FAIL: gcc.dg/tree-ssa/pr13146.c scan-tree-dump optimized "return 0;"
FAIL: gcc.dg/tree-ssa/pr27799.c (test for excess errors)
FAIL: gcc.dg/tree-ssa/pr38895.c scan-tree-dump optimized "return 1;"

For alias-18.c:

struct A {
  int i;
  int j;
  float x;
};
struct B {
  struct A a;
  int k;
};

int test1 (struct A *p, struct B *q)
{
  p->i = 1;
  q->k = -1;
  return p->i;
}

the 1 is expected to be propagated but isn't if the default is changed.

IIUC the key here is that 'struct A' is a sub-structure of 'struct B' so, if 
*p is not in the access path of *q, the references cannot alias.  So I can 
propose this for the end of nonaliasing_component_refs_p:

  /* We haven't found any common base to apply offset-based disambiguation.
     There are two cases:
       1. The base access types have the same alias set.  This can happen
	  in Ada when a function with an unconstrained parameter passed by
	  reference is called on a constrained object and inlined: the types
	  have the same alias set but aren't equivalent.  The references may
	  alias in this case.
       2. The base access types don't have the same alias set, i.e. one set
	  is a subset of the other.  We have proved that B1 is not in the
	  access path B2.path and that B2 is not in the access path B1.path
	  so the references may not alias.  */
  return get_alias_set (type1) == get_alias_set (type2);

-- 
Eric Botcazou

Re: Type-based alias analysis and alias sets

[Richard Guenther]

On Fri, 23 Oct 2009, Eric Botcazou wrote:

> > I didn't find (or could construct) a single C or C++ testcase that
> > wasn't fine with the new default, so I switched it (IIRC the default
> > is disambiguating the most cases).
> 
> Yes, the default is the optimistic answer and a few tests rely on it:
> 
> FAIL: gcc.dg/tree-ssa/alias-18.c scan-tree-dump fre "with 1"
> FAIL: gcc.dg/tree-ssa/pr13146.c scan-tree-dump optimized "return 0;"
> FAIL: gcc.dg/tree-ssa/pr27799.c (test for excess errors)
> FAIL: gcc.dg/tree-ssa/pr38895.c scan-tree-dump optimized "return 1;"

Indeed, I added them for this reason.

> For alias-18.c:
> 
> struct A {
>   int i;
>   int j;
>   float x;
> };
> struct B {
>   struct A a;
>   int k;
> };
> 
> int test1 (struct A *p, struct B *q)
> {
>   p->i = 1;
>   q->k = -1;
>   return p->i;
> }
> 
> the 1 is expected to be propagated but isn't if the default is changed.
> 
> IIUC the key here is that 'struct A' is a sub-structure of 'struct B' so, if 
> *p is not in the access path of *q, the references cannot alias.  So I can 
> propose this for the end of nonaliasing_component_refs_p:

btw, aliasing_component_refs_p would be a fine name.

>   /* We haven't found any common base to apply offset-based disambiguation.
>      There are two cases:
>        1. The base access types have the same alias set.  This can happen
> 	  in Ada when a function with an unconstrained parameter passed by
> 	  reference is called on a constrained object and inlined: the types
> 	  have the same alias set but aren't equivalent.  The references may
> 	  alias in this case.
>        2. The base access types don't have the same alias set, i.e. one set
> 	  is a subset of the other.  We have proved that B1 is not in the
> 	  access path B2.path and that B2 is not in the access path B1.path
> 	  so the references may not alias.  */
>   return get_alias_set (type1) == get_alias_set (type2);

That works for me.  A patch along this line is pre-approved.

Thanks,
Richard.