Re: [Cardinal-dev] Parrot IR compiler

[Melvin Smith]

At 11:53 AM 5/30/2002 +0200, Erik Bågfors wrote:
> Do I understand this correctly?  What does this IR language do?  Does it
> only take care of register allocations?  Will it do more soon? If so

I guess that example was pretty useless, what I was showing
was how the expressions looked. I could have chose to do them
in a Parrot-with-symbolics style but instead I went with an intermediate
form that is close to what compilers generate in their intermediate
phase.

It's basically a quadruple language (or 3-address code).
You can emit code with unlimited temporaries and it will do the
final compilation phases which are:

1) Instruction selection
2) Register allocation and spilling
3) Optimization

Number 1 and 2 are phases that you will have to implement when you
target any language to Parrot (or another cpu). So I'm just making it much 
easier
by writing a common backend that will work for all high level compilers.

You can concentrate on writing the Lexer/Parser/Type Checking and Semantic
phases of your compiler and then generate IR directly from your AST or DAG,
or whatever it is you have.

> what?  Does it take care of variables on the stack if we run out of

Spilling, yes, soon. I have the allocator working with the graph-coloring
technique, and that'll be in the first commit. Then I'll be working on the
spiller which will insert appropriate saves/restores into your opcodes
before compilation.

> registers? If it could take care of saving registers when doing
> sub-calls that would help alot too.

That would be up for discussion. It would be trivial to do, but you
must also provide a way to have sub-calls that don't need to do
reg saves.

> I really could use a small language like this for my small
> basic-compiler (which I will release soon.. somehow).  As register
> allocations is really stupid in my compiler now (It only allows usage of
> as many variables as there are registers currently)

I know what you are going through. Cola currently has a stack based
allocator which works pretty good, but does no spilling. Spillage is
typically the hardest part of the allocator, fortunately, with 128 registers
in all, we can start with a stupid spiller because the allocator
does such a good job, you'll hardly ever need to spill, except in large,
pathological routines.

In theory a spiller should compute spill-costs before it chooses a register.
Mine won't, rather it will probably just grab the first register not
used in the previous, current and next instruction, and then work from there.

Here is a sample, although the registers aren't correct in this one,
I had to hack an output from Cola for it to work with imcc since Cola
currently only outputs temporaries in the form $R0-$Rxxx, and imcc
expects typed temporaries (I, N, S, P).



.sub Mandelbrot__Main
        .local int      k
        .local float    i
        .local float    c
        .local string   b
        .local float    Z
        .local float    C
        .local float    z
        .local int      y
        .local int      x
        .local float    t
        .local float    r
        b = " .:,;!/>)|&IH%*#"
        y = 30
LBL2:
        if y <= 0 goto LBL4
LBL3:
        $N0 = y
        $N1 = $N0 * 0.1
        C = $N1 - 1.5
        x = 0
LBL6:
        if x >= 75 goto LBL8
LBL7:
        $N2 = x
        $N3 = $N2 * 0.04
        $N4 = 2
        c = $N3 - $N4
        z = 0.0
        Z = 0.0
        r = c
        i = C
        k = 0
LBL10:
        if k >= 112 goto LBL12
LBL11:
        $N5 = z * z
        $N6 = Z * Z
        $N7 = $N5 - $N6
        t = $N7 + r
        $N8 = 2.0 * z
        $N9 = $N8 * Z
        Z = $N9 + i
        z = t
        $N10 = z * z
        $N11 = Z * Z
        $N12 = $N10 + $N11
        if $N12 <= 10.0 goto LBL16
LBL14:
        goto LBL12
LBL16:
LBL13:
        $N13 = k
        inc k
        goto LBL10
LBL12:
        $N14 = k % 16
        $N15 = b[$N14]
        .arg $N15
        call __puts
LBL9:
        $N16 = x
        inc x
        goto LBL6
LBL8:
        .arg "\n"
        call __puts
LBL5:
        $N17 = y
        dec y
        goto LBL2
LBL4:
LBL1:   ret

.emit
    __puts:
    pushs
    restore S31
    puts S31
    pops
    ret
.eom


Notice the .arg and .param directives are just high level representations
of how to pass arguments to subroutines. You could translate this to
whatever calling convention you wanted, with Parrot its save/restore,
but will be smart enough to use the scratch registers if possible.

The other benefit here is you can retain the names of your lexicals
and/or hand-write code using variable names rather than registers.
Thats sort of a nice side-effect of supporting Perl which has to
know the names of its symbols at run-time.

.emit -> .eom is a low level instruction block that the compiler doesn't
process. This is for emitting straight Parrot or including an inline
library in your program. There are more directives to come such as
.namespace, .class, .global, .start, .exception and whatever you
guys might suggest.

-Melvin