[Mono-dev] [PATCH] Tree mover

[Massimiliano Mantione]

Warning: there are still problems with this patch :-(
A full rebuild fails on an amd64 machine (while it is successful
on x86), but at this point I'm posting it anyway...

This piece of code implements a "tree mover" for the mono JIT IR.

To make sense of it, consider this piece of C# code:

-------------------------------------------------------------------
private int f;

public int F {
        get {
                return f;
        }
        set {
                f = value;
        }
}

static int Inline (int a) {
        return a * 4;
}

public override int Cprop (int v) {
        return Inline (F + v);
}
-------------------------------------------------------------------

Method "Cprop", in the JIT, produces this IR:

 (outarg (ldind.i arg[0]))
 (stind.i4 local[2] call[get_F])
 (outarg (add (ldind.i4 local[2]) (ldind.i4 arg[1])))
 (setret call[Inline])

It contains two calls, one to the getter of a property and another
to a very simple method that just computes "argument times four".
Both calls should be inlined... this is the IR after inlining:

 (stind.ref local[3] (ldind.i arg[0]))
 (stind.i4 local[2] (ldind.i4 (add (ldind.ref local[3]) iconst[8])))
 (stind.i4 local[4] (ldind.i4 local[2]))
 (stind.i4 local[6] (add (ldind.i4 local[4]) (ldind.i4 arg[1])))
 (stind.i4 local[5] (mul (ldind.i4 local[6]) iconst[4]))
 (stind.i4 local[4] (ldind.i4 local[5]))
 (setret (ldind.i4 local[4]))

You can clearly see lots of temporary variables, created to keep
the semantics of argument passing while inlining.
The problem is that all those variables cause pressure on the regalloc,
which for now behaves badly under that pressure :-(
This is the resulting machine code (using copyprop, constprop and
deadce):

push   %ebp
mov    %esp,%ebp
push   %edi
push   %esi
sub    $0x4,%esp
mov    0x8(%ebp),%esi
mov    0xc(%ebp),%edi
mov    %esi,%esi
mov    0x8(%esi),%esi
mov    %edi,%eax
mov    %esi,%edi
add    %eax,%edi
shl    $0x2,%edi
mov    %edi,%eax
lea    0xfffffff8(%ebp),%esp
pop    %esi
pop    %edi
leave  
ret

You can see the issues...

Now, let's see what the tree mover does... the IR becomes like this:

 (setret (shl (add (ldind.i4 (add (ldind.ref arg[0]) iconst[8]))
(ldind.i4 arg[1])) iconst[2]))

Basically, all the useless locals went away, the code is just one
single tree.
The resulting machine code is this:

 push   %ebp
 mov    %esp,%ebp
 sub    $0xc,%esp
 mov    0x8(%ebp),%eax
 mov    0x8(%eax),%eax
 add    0xc(%ebp),%eax
 shl    $0x2,%eax
 leave  
 ret    

To be really fair, the code produced by this patch is not exactly
this, because in the IR local[4] was defined two times, and after
some debugging I sow I had to be less "liberal" in moving trees,
so that local[4] is not eliminated... but I plan to fix this soon.

Some preliminary benchmark shows a gain in SciMark, composite score
passes from 204 to 208.

Now some note to the implementation... it is meant to be used with
copyprop, consprop and deadce (and of course inlining), and in fact
the algorithm is applied inside "mono_local_cprop".

The idea is easy in principle: each variable that is defined and
used exactly once, in the same BB, and which is defined by a tree
whose value does not change between the definition and the use is
a candidate for tree moving: the definition is eliminated, and the
tree of MonoInst is moved to the use point.
Note that a global pass on all BBs is needed go be sure there are
not "misplaced" uses or definitions, so inside "mono_local_cprop"
the code fill some data structures, and only at the end the trees
that are really movable are transferred.

However, the devil is in the details ;-)
There are two subtle problems... first, one tree can "include" a
second tree, like here:

t1 = a + b;
t2 = t1 + c;
a = x;
v = t2 + d;

Here, one tree move would make "t2 = (a + b) + c", but at this
point the "t2" tree cannot be moved on, because of the "a = x"
statement.
This is called "indirect use" in the comments.

Then, copy propagation can move variables "under the nose" of the
tree mover... in this case the comments in the code say there is
a "tree forwarding".

When I'll solve the issue on amd64 I'll re-post the patch, and
include more documentation.
For now, this is it!

Ciao,
  Massi

-------------- next part --------------
A non-text attachment was scrubbed...
Name: treeprop.patch
Type: text/x-patch
Size: 35644 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20060123/4034c75c/attachment.bin