[Mono-dev] CIL optimizer

[Rodrigo Kumpera]

On Sat, Oct 2, 2010 at 3:23 PM, Justin Malcolm <malcolm.justin at gmail.com>wrote:

> Thank you for the reply Rodrigo,
>
> Do you mean that there is not much room for optimization of the output from
> 'mcs' or just of CIL in general?  I have heard that the Microsoft C++
> compiler output better code than the C# one did (at least at some point) so
> I assumed that CIL efficiency mattered.
>

There is only anedoctal evidence of such thing. Managed C++ probably emit
faster code by virtue of doing lots of unsafe operations than by producing
faster CIL.



>
> I was thinking that a generic CIL optimizer would make it possible for
> compiler writers (and others) to worry less about optimization.  I am
> writing a compiler myself and I was thinking of keeping the compiler
> optimization stupid and implementing a stand-alone CIL optimizer to go with
> it.  That is why I wanted to know if anybody else had done any work on it.
>
> I know one thing, my current compiler puts out some pretty bad CIL.  For
> example, compiling 5+4*3-6/3 in my compiler results in a bunch of 'i4'
> literals along with 'mul', 'add', 'sub', and 'div' instructions.  Clearly
> this could be better.  I figured, why do it in every compiler when I could
> just write a generic optimizer instead.
>
> I guess I do not really know what optimizations .NET and Mono do at the JIT
> level so I am not sure how the CIL affects the quality of the machine code
> that actually gets executed.  Do things like dead code elimination, constant
> propagation, loop unrolling, conversion avoidance, and changing things like
> "idc.i4" to "idc.i4.s" affect the final result at all or just the JIT time?
>

Most of those optimization would make no difference at all since the JIT can
do them by itself.


>
> It sounds like you are implying that the JIT manages pretty well even when
> you feed it inefficient CIL.  Then again, your instrumentation comment makes
> me wonder if I have that right.  If you could elaborate, I would appreciate
> knowing if I would be wasting my time to go down this road.
>

Instrumentation usually produce a lot of high level redundancy that takes
quite some effort for the JIT to eliminate.


>
> If you were going to optimize the CIL, where would you expect to get a
> return on your efforts?
>

First, you need to do it against a specific compiler/JIT pair to know what
kind of inefficient code the compiler produces that the JIT can't digest
properly.

You also must know that all JITs are built targeting a specific set of
compilers, so they encode a lot of optimizations based on IL patterns
produced by those
compilers - generating theoretically better CIL that the JIT won't be able
to digest doesn't help.

Now onto the cases that I know the pair mcs/mono don't handle well:

-string switches, mcs uses a dictionary for that when a perfect hash
function will be a lot faster;
-the following pattern "if (foo is Bla) { Bla b = (Bla)foo; ... }" is JITed
to 2 casts instead of one;
-integer division doesn't handle non power of 2 divisors (using the mul
trick, for example)
-intrisification of patterns like "if (x > y) r = x; else r = y;" to proper
Math methods.

Things like loop unrolling, auto-vectorization or loop-invariant code motion
are extremely tricky to do
because their improvement depends on what hardware it will run. For example,
moving too much out
of a loop can result is worse code since the JIT won't be able to handle all
those variables live at the
same time.

There are other fancier optimizations that could be done, like code
scheduling, but I have no idea
how effective or viable it is.

In the end, I would love that some would work on this, if only just to
answer if it's worth or not. I believe
it's possible to have it produce CIL that JITs better (not by much) but the
human cost of writing all
the needed code is what made it not happen so far.

In case you need some motivation if such thing existed, worked well and had
a license that allowed
it to be used by mcs, I'm pretty such the compiler guys would love to use
it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20101002/84e8e8f2/attachment.html