[Mono-devel-list] SSA and try/catch/finally regions

[Massimiliano Mantione]

I'm going to do some work in the SSA construction code, so that
we will have proper SSA "versions" to represent field accesses.

While working on that code, I thought it would be nice to enable
SSA also when we currently cannot do it.

Now we disable SSA for the following reasons:
- Aliasing risks (the address of a local has been taken)
- try/catch/finally regions

The first issue is addressed by alias analysis, which (in a
limited form, but enough for this purpose) is already done.

The second one is related to the fact that try and catch/finally
blocks currently are not properly connected in the CFG.
But the real issue is not just how to connect the blocks, but how
to take into account the fact that when we reach a catch/finally
region the value of some variable is unpredictable.

I explain with a simple example:

int v = 0;
try {
v = 1;
DoSomething ();
v = 2;
DoSomeMore ();
v = 3;
DoEvenMore ();
} finally {
Console.WriteLine (v);
}

Here, the value of 'v' in the finally BB depends from which of the
"Do..." methods (eventually) throws an exception.
So, simply connecting the try BB to the finally BB in the CFG (and,
by the way, also the finally BB to its "next" BB, which we now don't
do!) is not enough.

My idea is to use a sequence of OP_DUMMY_STORE instructions at the
beginning of catch/finally regions, one for each variable that is
assigned in the corresponding try region (and is actually used in
the catch/finally region, of course).

The complexity of doing this is low, and I think I can easily embed
this kind of scanning in the alias analysis pass (which already does
a full pass on the whole compiled method, looking for all load and
store instructions).
Maybe handling nested try regions will give me some trouble, but in
the end it should be easy...

In this way SSA would know that those variables have an unknown
value in those blocks.

Do you think this is a reasonable approach?

Ciao,
Massi

[Zoltan Varga]

Hi,

A simpler solution would be to mark those variables used in
catch/finally blocks as volatile.
This is already done.

Zoltan

Post by Massimiliano Mantione
I'm going to do some work in the SSA construction code, so that
we will have proper SSA "versions" to represent field accesses.
While working on that code, I thought it would be nice to enable
SSA also when we currently cannot do it.
- Aliasing risks (the address of a local has been taken)
- try/catch/finally regions
The first issue is addressed by alias analysis, which (in a
limited form, but enough for this purpose) is already done.
The second one is related to the fact that try and catch/finally
blocks currently are not properly connected in the CFG.
But the real issue is not just how to connect the blocks, but how
to take into account the fact that when we reach a catch/finally
region the value of some variable is unpredictable.
int v = 0;
try {
v = 1;
DoSomething ();
v = 2;
DoSomeMore ();
v = 3;
DoEvenMore ();
} finally {
Console.WriteLine (v);
}
Here, the value of 'v' in the finally BB depends from which of the
"Do..." methods (eventually) throws an exception.
So, simply connecting the try BB to the finally BB in the CFG (and,
by the way, also the finally BB to its "next" BB, which we now don't
do!) is not enough.
My idea is to use a sequence of OP_DUMMY_STORE instructions at the
beginning of catch/finally regions, one for each variable that is
assigned in the corresponding try region (and is actually used in
the catch/finally region, of course).
The complexity of doing this is low, and I think I can easily embed
this kind of scanning in the alias analysis pass (which already does
a full pass on the whole compiled method, looking for all load and
store instructions).
Maybe handling nested try regions will give me some trouble, but in
the end it should be easy...
In this way SSA would know that those variables have an unknown
value in those blocks.
Do you think this is a reasonable approach?
Ciao,
Massi
_______________________________________________
Mono-devel-list mailing list
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Zoltan Varga]

Hi,

Post by Zoltan Varga
A simpler solution would be to mark those variables used in
catch/finally blocks as volatile.
This is already done.

Thanks for reminding me this issue (I really forgot it!).
It is a simpler approach, but it also prevents optimizations on
those variables in the *whole* method.

I'm not sure there is a need to optimize accesses to those variables. The bigger
problem is that currently all variables which are used in bblocks reachable from
catch blocks are also marked volatile, since the liveness info is not correctly
computed for them because of the CFG problems with catch blocks.

Zoltan

A different approach would be to flag them as MONO_INST_INDIRECT
instead of MONO_INST_VOLATILE (to still prevent them from being
allocated in registers) and use the OP_DUMMY_STORE trick to mark
the places where they behave as "volatile", like I described.
I think this would still produce correct code, but enable more
optimizations opportunities.
So, my preference would go to the OP_DUMMY_STORE "trick", but
flagging catch/finally vars as MONO_INST_INDIRECT.
By the way, currently it seems to me that this flagging is done
in "mono_analyze_liveness", but what if we had some optimization
pass that runs *before* liveness has been computed but needs to
take this issue into account?
I know we have not this problem now, but the scenario is possible.
Suppose we go to semi-pruned SSA (which does not require liveness)
and also enable SSA in the presence of try/catch/finally clauses,
relying on the MONO_INST_VOLATILE flag to mark variables used in
catch/finally regions.
The flag will not be set, so the optimizations relying on it to
produce correct code would not work.
So, if we choose the MONO_INST_VOLATILE way, wouldn't it be better
to perform the flagging in a pass that we are *sure* will happen
before all the optimizations that need it?
Now we do one full code scan (handle_exception_clauses) just for
this purpose, but we do it inside mono_analyze_liveness...
Ciao,
Massi

[Massimiliano Mantione]

Post by Zoltan Varga
A simpler solution would be to mark those variables used in
catch/finally blocks as volatile.
This is already done.

Thanks for reminding me this issue (I really forgot it!).

It is a simpler approach, but it also prevents optimizations on
those variables in the *whole* method.

A different approach would be to flag them as MONO_INST_INDIRECT
instead of MONO_INST_VOLATILE (to still prevent them from being
allocated in registers) and use the OP_DUMMY_STORE trick to mark
the places where they behave as "volatile", like I described.

I think this would still produce correct code, but enable more
optimizations opportunities.
So, my preference would go to the OP_DUMMY_STORE "trick", but
flagging catch/finally vars as MONO_INST_INDIRECT.

By the way, currently it seems to me that this flagging is done
in "mono_analyze_liveness", but what if we had some optimization
pass that runs *before* liveness has been computed but needs to
take this issue into account?

I know we have not this problem now, but the scenario is possible.
Suppose we go to semi-pruned SSA (which does not require liveness)
and also enable SSA in the presence of try/catch/finally clauses,
relying on the MONO_INST_VOLATILE flag to mark variables used in
catch/finally regions.
The flag will not be set, so the optimizations relying on it to
produce correct code would not work.

So, if we choose the MONO_INST_VOLATILE way, wouldn't it be better
to perform the flagging in a pass that we are *sure* will happen
before all the optimizations that need it?
Now we do one full code scan (handle_exception_clauses) just for
this purpose, but we do it inside mono_analyze_liveness...

Ciao,
Massi

[Kelly Leahy]

So does the CFG problems with catch blocks refer to
the fact that the CFG doesn't reflect all of the edges
from every place that can throw the exception to the
catch block?

I just spoke with a colleague of mine (one of the guys
that wrote a lot of those SSA papers) and he said he
thought there should be an edge for each place the
exception could be thrown and if there was, there is
no ambiguity as each of the edges contributes the
value of the var on its path to the PHI expression at
the catch node.

Kelly

Hi,
On Apr 4, 2005 4:29 PM, Massimiliano Mantione

On Mon, 2005-04-04 at 14:28 +0200, Zoltan Varga

Post by Zoltan Varga
A simpler solution would be to mark those

variables used in

Post by Zoltan Varga
catch/finally blocks as volatile.
This is already done.

Thanks for reminding me this issue (I really

forgot it!).

It is a simpler approach, but it also prevents

optimizations on

those variables in the *whole* method.

I'm not sure there is a need to optimize accesses to
those variables. The bigger
problem is that currently all variables which are
used in bblocks reachable from
catch blocks are also marked volatile, since the
liveness info is not correctly
computed for them because of the CFG problems with
catch blocks.
Zoltan

A different approach would be to flag them as

MONO_INST_INDIRECT

instead of MONO_INST_VOLATILE (to still prevent

them from being

allocated in registers) and use the OP_DUMMY_STORE

trick to mark

the places where they behave as "volatile", like I

described.

I think this would still produce correct code, but

enable more

optimizations opportunities.
So, my preference would go to the OP_DUMMY_STORE

"trick", but

flagging catch/finally vars as MONO_INST_INDIRECT.
By the way, currently it seems to me that this

flagging is done

in "mono_analyze_liveness", but what if we had

some optimization

pass that runs *before* liveness has been computed

but needs to

take this issue into account?
I know we have not this problem now, but the

scenario is possible.

Suppose we go to semi-pruned SSA (which does not

require liveness)

and also enable SSA in the presence of

try/catch/finally clauses,

relying on the MONO_INST_VOLATILE flag to mark

variables used in

catch/finally regions.
The flag will not be set, so the optimizations

relying on it to

produce correct code would not work.
So, if we choose the MONO_INST_VOLATILE way,

wouldn't it be better

to perform the flagging in a pass that we are

*sure* will happen

before all the optimizations that need it?
Now we do one full code scan

(handle_exception_clauses) just for

this purpose, but we do it inside

mono_analyze_liveness...

Ciao,
Massi

_______________________________________________
Mono-devel-list mailing list

http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Zoltan Varga]

Hi,

I don't know much about the CFG stuff, but given the following code:

int i = 0;

try {
}
catch {
...
}

i = i + 1

with the current JIT, the liveness range of 'i' does not include the
catch block, so if
i is not made volatile, the JIT might allocate 'i' and a variable used
in the catch block to
the same global register, screwing things up.

Zoltan

Post by Kelly Leahy
So does the CFG problems with catch blocks refer to
the fact that the CFG doesn't reflect all of the edges
from every place that can throw the exception to the
catch block?
I just spoke with a colleague of mine (one of the guys
that wrote a lot of those SSA papers) and he said he
thought there should be an edge for each place the
exception could be thrown and if there was, there is
no ambiguity as each of the edges contributes the
value of the var on its path to the PHI expression at
the catch node.
Kelly

Hi,
On Apr 4, 2005 4:29 PM, Massimiliano Mantione

On Mon, 2005-04-04 at 14:28 +0200, Zoltan Varga

Post by Zoltan Varga
A simpler solution would be to mark those

variables used in

Post by Zoltan Varga
catch/finally blocks as volatile.
This is already done.

Thanks for reminding me this issue (I really

forgot it!).

It is a simpler approach, but it also prevents

optimizations on

those variables in the *whole* method.

I'm not sure there is a need to optimize accesses to
those variables. The bigger
problem is that currently all variables which are
used in bblocks reachable from
catch blocks are also marked volatile, since the
liveness info is not correctly
computed for them because of the CFG problems with
catch blocks.
Zoltan

A different approach would be to flag them as

MONO_INST_INDIRECT

instead of MONO_INST_VOLATILE (to still prevent

them from being

allocated in registers) and use the OP_DUMMY_STORE

trick to mark

the places where they behave as "volatile", like I

described.

I think this would still produce correct code, but

enable more

optimizations opportunities.
So, my preference would go to the OP_DUMMY_STORE

"trick", but

flagging catch/finally vars as MONO_INST_INDIRECT.
By the way, currently it seems to me that this

flagging is done

in "mono_analyze_liveness", but what if we had

some optimization

pass that runs *before* liveness has been computed

but needs to

take this issue into account?
I know we have not this problem now, but the

scenario is possible.

Suppose we go to semi-pruned SSA (which does not

require liveness)

and also enable SSA in the presence of

try/catch/finally clauses,

relying on the MONO_INST_VOLATILE flag to mark

variables used in

catch/finally regions.
The flag will not be set, so the optimizations

relying on it to

produce correct code would not work.
So, if we choose the MONO_INST_VOLATILE way,

wouldn't it be better

to perform the flagging in a pass that we are

*sure* will happen

before all the optimizations that need it?
Now we do one full code scan

(handle_exception_clauses) just for

this purpose, but we do it inside

mono_analyze_liveness...

Ciao,
Massi

_______________________________________________
Mono-devel-list mailing list

http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Massimiliano Mantione]

Post by Zoltan Varga
with the current JIT, the liveness range of 'i' does not include the
catch block, so if i is not made volatile, the JIT might allocate 'i'
and a variable used in the catch block to the same global register,
screwing things up.

Yes, the code has a comment pointing to bug #42136 about this.

But just to be sure I understand: if we had proper CFG edges,
the liveness range would be correct, would it?

My plan was to make sure the CFG had the following edges in
place:
[1] Connection from the "end" of the try region to the catch
region, *and* to the finally region if present, otherwise
to the place where the control flow goes on.
[2] Connection from the end of the catch region to the
start of the finally region, or to the place where the
control flow goes on if there is no finally region.
[2] Connection from the end of the finally region to the
place where the control flow goes on (like above, the one
just "after" the whole try/catch/finally block).

A CFG of this shape looks like if the catch region were under
a conditional branch after the "end" of the try region, and
is then followed by the finally region.

Both the catch and the finally regions are dominated by the
try one (which is correct).
Also, the catch part is sort of "optional" (because in point
[1] we make it look that it can be "skipped"), while it is
evident that the finally region is "mandatory".
The only inaccuracy is the fact that in principle one could
reach the catch/finally regions from many places inside the
try region, which is not modeled in this CFG, because it is
done like if the try region were always executed entirely.

IMHO, trying to model correctly each edge from each point in
the try region that could throw an exception is overkill.
It is true that the resulting SSA representation would be
"perfect", but in practice all those "large" phi nodes would
not give us any useful information, because we cannot really
know which of those edges will be taken.

Instead, I was proposing to keep the CFG relatively simple.
The fact that some variables have "unpredictable" values
after the try block (because the try block *could* have not
been executed entirely) would be modeled using dummy store
instructions, which would force the SSA generation code to
give those variables a new SSA version.

I still have to check the exact places where those dummy
store instructions should be put.
Ideally, with a CFG of this shape, they should be put
exactly at the "end" of the try region.
In fact, it is the "exit" from the try region that we are
not modeling correctly, so it is that point that should be
"patched".
If there is no single BB representing this "exit", I still
have to verify what would be the best thing to do... but
this is just an "implementation detail" ;-)
In any case, control flow transfers from the try region are
rigidly regulated and represented with special opcodes, so
it should not be hard tracking them.

This, for me, is a nice balance between the "perfectly
accurate" approach (one CFG edge for each place that could
throw an exception in the try region), and the "easy" one
(forget all optimizations on those variables in the whole
method because they are made volatile).
It gives you (almost?) all the optimization opportunities
of the accurate method, but keeps the CFG reasonable.

I hope I explained this clearly this time :-)

Ciao,
Massi

[Kelly Leahy]

Post by Massimiliano Mantione
IMHO, trying to model correctly each edge from each
point in
the try region that could throw an exception is
overkill.
It is true that the resulting SSA representation
would be
"perfect", but in practice all those "large" phi
nodes would
not give us any useful information, because we
cannot really
know which of those edges will be taken.

You may be correct on this. I'm not sure, myself, but
we (Ron and I) have always done it with these edges
and never really had any problems. In reality, the
number of edges is still small compared to the number
of instructions (in general), as there are only a
handful of instructions that can throw an exception.
Among these are call instructions, hard cast
instructions, integer division, possibly floating
division (don't know about .NET on this one), throw
and rethrow instructions, and I'm sure there's a few I
missed here. However, in most code blocks, this is
probably not going to be a large percentage of the
code, I think.

Anyway, I think the method you describe works, but I
would recommend implementing both methods (since the
"every possible path" method is quite easy to
implement) so that you can do some testing to see
which actually does perform better, and also so that
you can fall back on the theoretically correct method
in case your heuristic does not in fact work properly.

Kelly

[Massimiliano Mantione]

Post by Kelly Leahy
Anyway, I think the method you describe works, but I
would recommend implementing both methods (since the
"every possible path" method is quite easy to
implement) so that you can do some testing to see
which actually does perform better, and also so that
you can fall back on the theoretically correct method
in case your heuristic does not in fact work properly.

Well, actually I think the "every possible path" method
is not so easy to implement in Mono.
We cannot model CFG edges that start from the "middle" of
a BB, only from the end of it (in other words, we don't
support extended basic blocks).

So, my comment was more something like "the complete
solution would be hard to do and unlikely to be worth
because it doesn't really add usable information"...

Ciao,
Massi