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.