CPS and RTL

CPS and RTL

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1957 bytes --]

Hello,

I've had several conversations on this list about using
continuation-passing style in Guile. I recently decided to take the hint
and implement it. I've pushed a new branch called wip-rtl-cps that I'd
appreciate comments on (but I do not necessarily think that this is the
branch that will be merged with master - it's still pretty rough).

The branch contains a CPS data structure based on the paper "Compiling with
Continuations, Continued", by Andrew Kennedy. It lives in
module/language/cps.scm. The branch is based on the RTL branch, and there's
a CPS->RTL compiler in module/language/cps/compile-rtl.scm. There are also
tests for it in test-suite/tests/cps.test. Here are some notes:

- It may have been a mistake to do a CPS->RTL compiler first. Even if we
want to use RTL eventually, it probably would have been more sensible to do
CPS->GLIL first, so the change would be independent of the switch to RTL.
However, the code is already here - we can use it as-is, or change to GLIL,
or something else.

- There's no Tree-IL->CPS compiler yet, mostly because I'm confident that
we can do it, so I figured we could always add it later.

- There are three major language features missing from the compiler:
top-level variables, closures, and anything to do with the dynamic
environment. Those are all pretty major features - that's why I said this
was rough.

- Right now the register allocation pass operates directly on the CPS. I
have been thinking about making some higher-order functions for traversing
it, similar to tree-il-fold, but I haven't done it yet.

Basically, I have a very rough compiler. I'd like to show it to people now,
even though it's not fully formed, so that you can point out any issues,
and so that we can see if this is something that could eventually wind up
in mainline Guile. I'd rather fix problems now than later on. (And of
course I would appreciate help from anyone else who wants to contribute.)

Thanks,
Noah

[-- Attachment #2: Type: text/html, Size: 2257 bytes --]

Re: CPS and RTL

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 5774 bytes --]

Hi Noha,

very clean code indeed, nice work, (mine rtl compiler is much more a bit of
a hack btw :-))

One thing to think about from the beginning is how to protect variables
from gc and at the same time
offer unreachable vars to be gc:d at an early state. In guile-2.0 we kept
using a stack for e.g. the middle terms
in the executions of expressions like (+ (+ x y) (+ w z)) and there the end
stack pointer was updated after each
primitive. This is an overhead and in the rtl code wingo's trying to remove
the need for a sp register in hardware
and in stead occasionally update a vp->sp value probably sitting in the
memory cache. The problem with this is that now
we must take care to occasionally write over memory regions in order to
allow the contents therein being gc'd at an
early state. This means that we must record which registers have been used
between the erasing's. Now what I tried
to use is that the activities for which we will need to have well defined
sp is mostly quite expensive so we can allow to
update it then. Then looking at instructions like (add dst argx argy) in
most cases the place to put in vp->sp is the dst
location, but not always, I took the path to keep a base sp memory location
which we could call bsp and I stored it in
vp->sp. Now when the add need to go out to the slow path, which may cons,
it will check if dst is below bsp, if so it will use bsp as the
sp position, else it will use dsp e.g. it will temporary set vp->sp to
&fp[dst]. when executing the slow path. This method
will mean that we need at times set the bsp as the code flows, but it will
not be many places in practice, and they will most often be out of the hot
path, so I added a (set-sp pos) rtl vm-op and tried with that. In all this
means that I got a very effective
way of keeping track of the end of the stack with the same or better
accuracy as before and it's really fast and there is no need to keep
vp->sp  in a hardware register. The problem is that the code base got more
comlpex both in C land and in scheme and I needed to store the bsp across
function call's along with fp because bsp could be pointing at somewhere
other the start of the next function frame. We could solve this on the
other hand by demanding the destination of a call
always sit's at the end of the sp and add a mov operation after teh call if
needed instead, meaning that we can save on the amount of storage needed to
be done on each frame.

Anyway my message here is that one need to make sure that the register
allocator play's nicely with the mechanism of marking the region eligible
for gc or not for gc.

Another thing to look out for is the tail call's and berhaps multiple value
returns, You will need to fill in the start of the frame
with the at say register 0 and make sure that if it's not used later just
overwrite or if it's used later move it and use that
location for that's register location (actually named let is another
similar activity where you do a goto back to the start but then 0 is not
the start of the registers to mangle. Maybe You solved this. And one can do
that by just parsing the continuation of that call to see if there is a
reference to it. If one chooses that it can be ok, I choose to delay the
evaluations of the actual register number to a later phase by in stead of
numbers store (lambda () (+ (d) i)), where is is the number I would have
chosen if there was no problem and d is a function who's value is
determined later by later usages of the same variable identity. I think
that this is overly complicated and would today just go after a simple scan
of the continuation.

I will try to comment more later.

Regards
Stefan


On Sat, Nov 17, 2012 at 4:35 PM, Noah Lavine <noah.b.lavine@gmail.com>wrote:

> Hello,
>
> I've had several conversations on this list about using
> continuation-passing style in Guile. I recently decided to take the hint
> and implement it. I've pushed a new branch called wip-rtl-cps that I'd
> appreciate comments on (but I do not necessarily think that this is the
> branch that will be merged with master - it's still pretty rough).
>
> The branch contains a CPS data structure based on the paper "Compiling
> with Continuations, Continued", by Andrew Kennedy. It lives in
> module/language/cps.scm. The branch is based on the RTL branch, and there's
> a CPS->RTL compiler in module/language/cps/compile-rtl.scm. There are also
> tests for it in test-suite/tests/cps.test. Here are some notes:
>
> - It may have been a mistake to do a CPS->RTL compiler first. Even if we
> want to use RTL eventually, it probably would have been more sensible to do
> CPS->GLIL first, so the change would be independent of the switch to RTL.
> However, the code is already here - we can use it as-is, or change to GLIL,
> or something else.
>
> - There's no Tree-IL->CPS compiler yet, mostly because I'm confident that
> we can do it, so I figured we could always add it later.
>
> - There are three major language features missing from the compiler:
> top-level variables, closures, and anything to do with the dynamic
> environment. Those are all pretty major features - that's why I said this
> was rough.
>
> - Right now the register allocation pass operates directly on the CPS. I
> have been thinking about making some higher-order functions for traversing
> it, similar to tree-il-fold, but I haven't done it yet.
>
> Basically, I have a very rough compiler. I'd like to show it to people
> now, even though it's not fully formed, so that you can point out any
> issues, and so that we can see if this is something that could eventually
> wind up in mainline Guile. I'd rather fix problems now than later on. (And
> of course I would appreciate help from anyone else who wants to contribute.)
>
> Thanks,
> Noah
>
>

[-- Attachment #2: Type: text/html, Size: 6481 bytes --]

Re: CPS and RTL

[Andy Wingo]

Hi Noah,

On Sat 17 Nov 2012 16:35, Noah Lavine <noah.b.lavine@gmail.com> writes:

> I've had several conversations on this list about using
> continuation-passing style in Guile. I recently decided to take the hint
> and implement it. I've pushed a new branch called wip-rtl-cps that I'd
> appreciate comments on (but I do not necessarily think that this is the
> branch that will be merged with master - it's still pretty rough).

I really like it.  It's clean and expressive.  Of course it needs a lot
of work as well :)  But I think it's a good enough start that we should
just merge it to wip-rtl and see where it goes from there.

Some thoughts off the top of my head:

  * It would be good to organize the compiler as a set of passes.  For
    example, closure conversion, assignment conversion, CSE, and
    register allocation should all be separate passes (perhaps in that
    order).  Of course porting the CSE pass would be quite a bit of
    work...  And actually, partial evaluation could work on the CPS form
    as well (but would be the first pass).  Things for the future.

  * We should still compile Scheme to tree-il I think; it's convenient,
    and other languages may well prefer a more direct-style IL as a
    target.

  * We really need the tree-il -> CPS compiler now.

Of course there's more!  But as a start, this this good.

What do you think?

Cheers, and thanks!

Andy
-- 
http://wingolog.org/

Re: CPS and RTL

[Mark H Weaver]

Andy Wingo <wingo@pobox.com> writes:
>   * We should still compile Scheme to tree-il I think; it's convenient,
>     and other languages may well prefer a more direct-style IL as a
>     target.

I like CPS for later passes of the compiler, but it should not come
first.  The problem is that CPS fixes the order in which everything is
evaluated, such as the order in which procedure arguments are evaluated,
the order in which 'let' or 'letrec' initializers are evaluated, etc.
The fact that these orders are unspecified in the direct-style gives the
compiler freedom to choose an order that generates the best code, and
apparently this freedom can often result in significant gains.  Such
ordering decisions must be made before the conversion to CPS.

      Mark

Re: CPS and RTL

[Andy Wingo]

Hi!

On Thu 24 Jan 2013 10:28, Mark H Weaver <mhw@netris.org> writes:

> The problem is that CPS fixes the order in which everything is
> evaluated, such as the order in which procedure arguments are
> evaluated, the order in which 'let' or 'letrec' initializers are
> evaluated, etc.  The fact that these orders are unspecified in the
> direct-style gives the compiler freedom to choose an order that
> generates the best code, and apparently this freedom can often result
> in significant gains.  Such ordering decisions must be made before the
> conversion to CPS.

Agreed with the sentiment; however, two points:

  * we can have a CPS with let / letrec / * operators that bind a number
    of values in unspecified order, and have a pass later that fixes
    their order.

  * code motion passes like CSE depend on effects analysis, and can
    often commute some operations

Anyway, violent agreement!

Cheers,

Andy
-- 
http://wingolog.org/

Re: CPS and RTL

[Nala Ginrut]

[-- Attachment #1: Type: text/plain, Size: 1155 bytes --]

Are you guys going to use CSP to implement SSA for AOT?
在 2013-1-24 PM6:36，"Andy Wingo" <wingo@pobox.com>写道：

> Hi!
>
> On Thu 24 Jan 2013 10:28, Mark H Weaver <mhw@netris.org> writes:
>
> > The problem is that CPS fixes the order in which everything is
> > evaluated, such as the order in which procedure arguments are
> > evaluated, the order in which 'let' or 'letrec' initializers are
> > evaluated, etc.  The fact that these orders are unspecified in the
> > direct-style gives the compiler freedom to choose an order that
> > generates the best code, and apparently this freedom can often result
> > in significant gains.  Such ordering decisions must be made before the
> > conversion to CPS.
>
> Agreed with the sentiment; however, two points:
>
>   * we can have a CPS with let / letrec / * operators that bind a number
>     of values in unspecified order, and have a pass later that fixes
>     their order.
>
>   * code motion passes like CSE depend on effects analysis, and can
>     often commute some operations
>
> Anyway, violent agreement!
>
> Cheers,
>
> Andy
> --
> http://wingolog.org/
>
>

[-- Attachment #2: Type: text/html, Size: 1603 bytes --]

Re: CPS and RTL

[Andy Wingo]

On Thu 24 Jan 2013 11:38, Nala Ginrut <nalaginrut@gmail.com> writes:

> Are you guys going to use CSP to implement SSA for AOT?

Too many acronyms!  I think the answer in short is that we are
interested in using a continuation-passing style intermediate language.
We don't know if it will work well or not, but we will try.

Andy
-- 
http://wingolog.org/

Re: CPS and RTL

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 2735 bytes --]

Hello Andy and Mark,

Thanks for the review! There has actually been more progress since I pushed
that branch. I hit a point in the CPS->RTL stuff where I had trouble
because I didn't know how to do things (like mutable variables) in RTL. So
I've actually ported the compiler to GLIL in a branch on my computer. I
also have a working Tree-IL->CPS compiler for some of Tree-IL (it's not
done yet).

I thought that might be a better way forward because CPS and RTL are, to a
certain extent, separate ideas. I'll push my wip-cps branch, which contains
a Tree-IL->CPS compiler and a CPS->GLIL compiler. What I'm working on now
is actually how to represent mutable variables in CPS. I think having
explicit environment structures would be nice (and fit with Kennedy's
paper), but I haven't figured out the details yet.

I realize it might be confusing to start with CPS->RTL, then switch to
CPS->GLIL, then switch back later when the RTL branch is ready. If you'd
rather do it that way, we can skip the CPS->GLIL phase.

Some thoughts:

* Yes, passes might be good. I had thought of writing some generic
control-flow operators like 'compute-fixpoint' and then writing other
things in terms of those.

* Using tree-il first sounds good to me.

* I also think that CPS should have some construct which says 'do these
things in any order'. I haven't put one in yet, mostly because the compiler
wouldn't take advantage of it anyway.

Noah


On Thu, Jan 24, 2013 at 5:38 AM, Nala Ginrut <nalaginrut@gmail.com> wrote:

> Are you guys going to use CSP to implement SSA for AOT?
> 在 2013-1-24 PM6:36，"Andy Wingo" <wingo@pobox.com>写道：
>
> Hi!
>>
>> On Thu 24 Jan 2013 10:28, Mark H Weaver <mhw@netris.org> writes:
>>
>> > The problem is that CPS fixes the order in which everything is
>> > evaluated, such as the order in which procedure arguments are
>> > evaluated, the order in which 'let' or 'letrec' initializers are
>> > evaluated, etc.  The fact that these orders are unspecified in the
>> > direct-style gives the compiler freedom to choose an order that
>> > generates the best code, and apparently this freedom can often result
>> > in significant gains.  Such ordering decisions must be made before the
>> > conversion to CPS.
>>
>> Agreed with the sentiment; however, two points:
>>
>>   * we can have a CPS with let / letrec / * operators that bind a number
>>     of values in unspecified order, and have a pass later that fixes
>>     their order.
>>
>>   * code motion passes like CSE depend on effects analysis, and can
>>     often commute some operations
>>
>> Anyway, violent agreement!
>>
>> Cheers,
>>
>> Andy
>> --
>> http://wingolog.org/
>>
>>

[-- Attachment #2: Type: text/html, Size: 3817 bytes --]

Re: CPS and RTL

[Andy Wingo]

Hi!

On Thu 24 Jan 2013 14:50, Noah Lavine <noah.b.lavine@gmail.com> writes:

> Thanks for the review! There has actually been more progress since I
> pushed that branch. I hit a point in the CPS->RTL stuff where I had
> trouble because I didn't know how to do things (like mutable variables)
> in RTL. So I've actually ported the compiler to GLIL in a branch on my
> computer. I also have a working Tree-IL->CPS compiler for some of
> Tree-IL (it's not done yet).
>
> I thought that might be a better way forward because CPS and RTL are, to
> a certain extent, separate ideas.

Cool, please push so we can see.

Honestly I think RTL and CPS go together very well.  CPS is all about
giving a name to everything, but that can be inefficient in a stack VM,
because referencing and updating named variables requires separate push
and pop instructions.  RTL makes this easy and cheap.

Regarding mutable variables: we probably still need to box them in
general because of call/cc.  There are cases in which they can be
unboxed, but I think that store-to-load forwarding with DCE can probably
recover many of those cases.  Dunno.  I would box them as part of an
assignment conversion pass.

> I realize it might be confusing to start with CPS->RTL, then switch to
> CPS->GLIL, then switch back later when the RTL branch is ready. If you'd
> rather do it that way, we can skip the CPS->GLIL phase.

Personally I would prefer to target RTL.  But that is a personal opinion
:)

Cheers, and happy hacking :)

Andy
-- 
http://wingolog.org/

Re: CPS and RTL

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1991 bytes --]

Hello,

On Thu, Jan 24, 2013 at 10:12 AM, Andy Wingo <wingo@pobox.com> wrote:

> Hi!
>
> On Thu 24 Jan 2013 14:50, Noah Lavine <noah.b.lavine@gmail.com> writes:
>
> > Thanks for the review! There has actually been more progress since I
> > pushed that branch. I hit a point in the CPS->RTL stuff where I had
> > trouble because I didn't know how to do things (like mutable variables)
> > in RTL. So I've actually ported the compiler to GLIL in a branch on my
> > computer. I also have a working Tree-IL->CPS compiler for some of
> > Tree-IL (it's not done yet).
> >
> > I thought that might be a better way forward because CPS and RTL are, to
> > a certain extent, separate ideas.
>
> Cool, please push so we can see.
>

Given the rest of your email, maybe I'll move the Tree-IL->CPS compiler
back to wip-cps-rtl branch and push that.


> Honestly I think RTL and CPS go together very well.  CPS is all about
> giving a name to everything, but that can be inefficient in a stack VM,
> because referencing and updating named variables requires separate push
> and pop instructions.  RTL makes this easy and cheap.
>

Yes, I hadn't thought about that. RTL does make sense.


> Regarding mutable variables: we probably still need to box them in
> general because of call/cc.  There are cases in which they can be
> unboxed, but I think that store-to-load forwarding with DCE can probably
> recover many of those cases.  Dunno.  I would box them as part of an
> assignment conversion pass.
>

I think I was imagining about the same thing you're thinking.


> > I realize it might be confusing to start with CPS->RTL, then switch to
> > CPS->GLIL, then switch back later when the RTL branch is ready. If you'd
> > rather do it that way, we can skip the CPS->GLIL phase.
>
> Personally I would prefer to target RTL.  But that is a personal opinion
> :)
>

I'm happy to! You've convinced me that it's better. I see that you just
implemented toplevel-refs, too, so my problem is solved.

Best,
Noah

[-- Attachment #2: Type: text/html, Size: 3119 bytes --]

Re: CPS and RTL

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 2342 bytes --]

The push is complete. If I'm not mistaken, you should now see a wip-rtl-cps
branch with a Tree-IL->CPS compiler. The compiler is used in cps.test.
Please let me know if I did anything wrong.

Noah



On Thu, Jan 24, 2013 at 11:03 AM, Noah Lavine <noah.b.lavine@gmail.com>wrote:

> Hello,
>
> On Thu, Jan 24, 2013 at 10:12 AM, Andy Wingo <wingo@pobox.com> wrote:
>
>> Hi!
>>
>> On Thu 24 Jan 2013 14:50, Noah Lavine <noah.b.lavine@gmail.com> writes:
>>
>> > Thanks for the review! There has actually been more progress since I
>> > pushed that branch. I hit a point in the CPS->RTL stuff where I had
>> > trouble because I didn't know how to do things (like mutable variables)
>> > in RTL. So I've actually ported the compiler to GLIL in a branch on my
>> > computer. I also have a working Tree-IL->CPS compiler for some of
>> > Tree-IL (it's not done yet).
>> >
>> > I thought that might be a better way forward because CPS and RTL are, to
>> > a certain extent, separate ideas.
>>
>> Cool, please push so we can see.
>>
>
> Given the rest of your email, maybe I'll move the Tree-IL->CPS compiler
> back to wip-cps-rtl branch and push that.
>
>
>> Honestly I think RTL and CPS go together very well.  CPS is all about
>> giving a name to everything, but that can be inefficient in a stack VM,
>> because referencing and updating named variables requires separate push
>> and pop instructions.  RTL makes this easy and cheap.
>>
>
> Yes, I hadn't thought about that. RTL does make sense.
>
>
>> Regarding mutable variables: we probably still need to box them in
>> general because of call/cc.  There are cases in which they can be
>> unboxed, but I think that store-to-load forwarding with DCE can probably
>> recover many of those cases.  Dunno.  I would box them as part of an
>> assignment conversion pass.
>>
>
> I think I was imagining about the same thing you're thinking.
>
>
>>  > I realize it might be confusing to start with CPS->RTL, then switch to
>> > CPS->GLIL, then switch back later when the RTL branch is ready. If you'd
>> > rather do it that way, we can skip the CPS->GLIL phase.
>>
>> Personally I would prefer to target RTL.  But that is a personal opinion
>> :)
>>
>
> I'm happy to! You've convinced me that it's better. I see that you just
> implemented toplevel-refs, too, so my problem is solved.
>
> Best,
> Noah
>
>

[-- Attachment #2: Type: text/html, Size: 3842 bytes --]