Re: [PATCH] Make alias_sets_conflict_p less conservative

[Michael Matz <matz at suse dot de>]

Hi,

On Wed, 5 Mar 2008, Richard Kenner wrote:

> I moved this to the main list because I think it's of general interest.
> 
> I fail to understand how the issue of which alias set is used has any
> appreciable effect on the amount of memory used at compile time.
> 
> The issue here is with something like:
> 
> 	struct X {int i; unsigned int iu; short s; unsigned short us;} x;
> 
> and then you have x.i as a reference someplace and you need to know
> what it conflicts with.  The RTL pass correctly assigns this the alias
> set corresponding to "int".  From what I'm reading here, the tree optimizers
> assign this the alias set corresponding to "struct X".  That means that x.i
> will conflict not just with accesses to int, but to unsigned int, short,
> and unsigned short as well.  That's wrong and unnecessary and I don't
> understand how fixing this will cost memory.

The problem lies in the way how we represent load and store dependencies 
as virtual operands.  Conflicts between a pair of mem accesses are not 
evaluated by asking alias_set_conflicts_p() on both accesses, but instead 
via a chain of virtual def and use operands.  E.g. (for the following 
let's ignore SFTs and other means to get more precise again):

struct X {int i; unsigned int iu; short s; unsigned short us;} x, y;
x = something;   // 1
x.i = bla1;      // 2
x.s = bla2;      // 3
y = x;           // 4
bla3 = y.i;      // 5

We know that set(int) and set(X) conflict (like also set(short) and 
set(X)), so there needs to be a dependency from 2 and 3 to 1, from 
4 to 3, 2 and 1, and from 5 to 4.

These dependencies are represented as V2 = DEF<V1> pseudo effects attached 
to the individual statements.  The way it is implemented right now is by 
noting that the store to x.i and x.s "modify" a virtual variable 
associated with the whole struct X, so we have:

  #X_1 = DEF<...>
x = something;   // 1
  #X_2 = DEF<X_1>
x.i = bla1;      // 2
  #X_3 = DEF<X_2>
x.s = bla2;      // 3
  #Y_1 = DEF<X_3>
y = x;           // 4
  # USE<Y_1>
bla3 = y.i;      // 5

The ordering is correct, but not the same as the ideal ordering from 
above.  In particular 3 depends on 2 now, which it doesn't in the ideal 
ordering.  But to represent the ideal ordering we would have to do 
something like this:

  #X_1 = DEF<...>     // as point to attach further full reads of struct X
  #int_1 = DEF<...>   // to attach further reads from ints, the x.i member
  #uint_1 = DEF<...>  // same for x.iu
  #short_1 = DEF<...> // x.s
  #ushort_1 = DEF<...>// x.us
x = something;  // 1
  #int_2 = DEF<int_1>
x.i = bla1;     // 2
  #short_2 = DEF<short_1>
x.s = bla2;     // 3
  #Y_1 = DEF<X_1>
  #int_3 = DEF<int_2>
  #uint_2 = DEF<int_1>
  #short_3 = DEF<short_2>
  #ushort_2 = DEF<ushort_1>
y = x           // 4
  # USE<int_3>
bla3 = y.i;     // 5

As you can see all stores to the full struct would require clobbering all 
virtual variables for the member types (otherwise there wouldn't be any 
mean to create a dependency from a further access to individual members to 
this store).

Needless to say that these virtual operands (vops) require space.  Indeed 
they require extremely much space when you want to have a precise 
description of memory access dependencies due to combinatoric explosion.

RTL doesn't have this problem because the dependencies are not represented 
explicitely but implicitely (they are evaluated on-demand whenever we have 
two mem accesses and wonder if they conflict or not).

Richis alias oracle work for tree-ssa tries to do something similar to 
what RTL already has.  Making the explicit dependencies even more 
imprecise (but needing less memory) while improving several optimization 
passes to ask questions in the same way as RTL passes do to disambiguate 
mem accesses.

> This is hardly a pathalogical corner case that it's OK to get wrong.  
> This is the *central case* around which much of the aliasing system has 
> been designed.  I don't believe that getting this wrong is reasonable.

I sort of agree with you.  The representation of mem access dependencies 
in tree-ssa is less than ideal for the real world.  It makes SSA 
optimizers work quite naturally also for loads and stores (all these vops 
are in SSA form too), but at a very high cost (either in memory or 
in imprecisness).


Ciao,
Michael.