[Mono-devel-list] Alias analysis

[Massimiliano Mantione]

On Thu, 2005-01-27 at 01:00, Ben Maurer wrote:
> On Thu, 2005-01-27 at 00:44 +0100, Zoltan Varga wrote:
> >  Wouldn't be easier to just disable optimizations on variables whose address is
> > taken ? It usually happens in unsafe code, and with taking addresses
> > of valuetypes.
> 
> I like this approach better as well.

Well, actually I also wanted to do it in some cases.

For instance, in the end I got convinced that it could be nice
to be able to apply SSA only to a subset of the variables (the
ones that are not aliased in an incontrollable way, and are not
used in exception handlers).
This would mean that all variables would need a flag that states
if SSA has been applied to them or not, and all SSA based code
should handle variables without that flag as "unknown values"
(like if they were the unpredictable result of a function call).
We would basically get rid of the disable_ssa flag in MonoCompile
because we would handle it on a per variable basis.

Maybe a similar approach could be used in other (non SSA based)
optimizations as well.

In any case, the code that performs the optimizations should be
modified, because it must be made aware of this new flag, so that
problematic variables will be ignored.
Always thinking about SSA, this would mean touching many places:
first the SSA construction and destruction code, and then deadce,
abcrem and ssapre.

As I said, I am convinced this should be done, only I didn't
want to do it immediately.
Instead, I needed proper tracking of aliasing to have accurate
liveness information in order to implement deadce without SSA
(in order to make inlining effective without SSA...).

Even if my explanation was long, the approach in itself is not
that hard, it is more "alias tracking" than alias analysis.
As a result, every variable and instruction would be flagged
correctly, that's all.
And I would provide some utility to handle call instructions
appropriately (case [a] of my explanation), and to find all
variables affected by cases [b] and [c].
Then, each individual optimization could use those flags and
utility functions as it seems best for the developer of that
optimization... one possible approach would be disabling the
optimization for individual variables, another would be making
use of the utility functions to handle accesses through aliases
properly. It would also be possible to have mixed approaches if
we see it's better doing so.

One of the nice things of this approach is that all the existing
code would continue to work using the old LOAD and STORE flags.
It can then be migrated incrementally into making good use of the
new flags... if this "good use" means "disable the optimization
for individual variables, because it's not worth handling uses
through aliases", fine :-)

But for deadce without SSA I really wanted to have more accurate
liveness information, and I have the suspect that this would be
useful also for the new regalloc, so I still think this kind of
"alias tracker" is worth doing.

> Maybe some effort should be made to make the valuetype operations
> "smarter" for example in this code:
> 
> struct X {
> ...
> }
> 
> if (foo) {
>     X x = new X (blah);
>     // do stuff with x
> }
> 
> if (bar) {
>     X y = new X (baz);
>    // do stuff with y
> }
> 
> We could assign x and y the same stack slot, even though ldarga is
> probably executed on both of them.

If I understood what you mean, to solve this you need accurate
liveness information, so that you know that when you assign 'y',
'x' is already dead, so its storage on the stack can be recycled.
And this is also why I think that improving liveness will help
the regalloc...

Extending my approach to handle case [c] in the case of value
types would give you exactly this ;-)
(if you look at my explanation, you'll see that I say that in case
[c] there are subcases, but for now I was ignoring them)

Thanks for the comments, and I hope I've been able to clarify
something...

Ciao,
  Massi