[Mono-dev] CIL to CIL optimizer

[Zoltan Varga]

                                     Hi,

  What is the problem with try-finally ? There are two cases:
- if there is an exception, the runtime will call it, just with the catch clause
- if there is no exception, control flow just falls from the end of
the try block to
the beginning of the finally block. This is just a normal control flow edge.

                 Zoltan

On 8/10/06, Bjarke Hammersholt Roune <bjarke.roune at gmail.com> wrote:
> Hi,
>
> I am considering implementing a CIL to CIL optimizer as suggested at
> http://www.mono-project.com/Cecil. I have some questions and some ideas
> up for criticism.
>
> Having previously implemented an optimizing compiler in ML in a course,
> I think that SML.net (http://www.cl.cam.ac.uk/Research/TSG/SMLNET/)
> would be better suited to the task than C#. F# would be nice too, but it
> doesn't have an open source compiler as far as I can tell.
>
> The proof-of-concept I have in mind would do the following steps for a
> subset of the full CIL. This subset would include a conditional branch
> opcode, the addition opcode and full support of exception handling
> including (the dreaded) try...finally.
>
> 1. Read in an assembly using Cecil
> 2. Construct the control flow graph while converting to a quadruple
> format (i.e. eliminate the stack in favor of registers)
> 3. Convert to SSA form using the algorithm from
> http://www.hipersoft.rice.edu/grads/publications/dom14.pdf
> 4. Do intra-procedural conditional constant propagation as described on
> page 447 of "modern compiler implementation in ML".
> (http://portal.acm.org/citation.cfm?id=103136)
> 5. Eliminate phi-nodes using moves and convert to CIL (i.e. reintroduce
> the stack)
> 6. Output assembly using Cecil
>
> The next step would be to support at least the subset of CIL that is
> output by the Mono C# compiler. Then it would be nice to extend the
> optimization to be inter-procedural. Then I would focus on outputting
> better CIL code like eliminating some of those moves coming from SSA. I
> have plenty ideas for what to do after that, but I'll have to see how
> much time I have.
>
> Having taken a look at the ECMA CIL spec, I don't see anything in there
> that should present really big problems other than exceptions and the
> finally construct (which is a problem even without exceptions).
>
> Exceptions are annoying because of the way they complicate analyzing
> control flow, but after having thought and read about how to handle them
> for some time I think they will be manageable.
>
> The try ... finally construct, on the other hand, now that just seems
> painful to me. As in red-hot-pincers-jammed-into-the-eyes-
> while-being-electrocuted-naked-in-a-snow-storm painful. Having scoured
> the web to the best of my ability, I have find PLENTY of material on how
> to deal with try ... catch in Java bytecode and CIL, but somehow people
> usually never bother to explain how they handle try ... finally. I guess
> how to efficiently construct a precise CFG and do SSA form in the face
> of try ... finally is just obvious to everyone but me.
>
> A solution to the problem involving higher-order functions is described
> at http://flint.cs.yale.edu/flint/publications/lamjvm.pdf, though that
> solution seems unsuitable for an imperative representation.
>
> A different solution used in SafeTSA is described at
> http://www.google.dk/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fwww.cs.utsa.edu%2F~vonronne%2Fpubs%2Fjvr-dissertation.pdf&ei=f43aRKLBJ7nWwgHZvsGhCA&sig2=nhWafzjm_synZsuIHpXhqg
> which consists of making several copies of the code in the finally
> clause. The potential for code size explosion is huge, but on the other
> hand finally clauses are usually small... but it is still not a
> satisfying solution.
>
> An obvious alternative would be to represent finally blocks as what they
> are and then having every single pass of the optimizer be aware of how
> to deal with this in some ad-hoc fashion. I don't like that either
> because all the details just seem horrendous to deal with as far as I
> can tell.
>
> Another idea is putting the finally code in a function call with plenty
> of ref parameters. This should work nicely together with
> inter-procedural optimizations. It ought to be possible to reinsert
> these calls as a finally block in most cases when outputting the CIL.
> I'm not sure this will work well, though.
>
> So far the best solution I can think of is to copy the finally code if
> it is small and insert function calls if the finally code is large.
> Always inserting function calls and having a general inliner pass might
> work well too.
>
> If anyone has any ideas or experience they would like to share, I would
> love to hear it. Especially on the topic of try ... finally!
>
> Regards
> Bjarke Roune
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>