Explicitly Managed Stack Frames

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Explicitly Managed Stack Frames

Ben Chambers-2
I was wondering what the current state of this (explicitly managed stack frames)
is.  Is it being worked on?  If not, how hard do you think it would be for me to
add it?  I am more than willing to work on it, but don't have any experience
with LLVM, so it might take a while.  The reason I ask is because I am starting
work on a project to make a language similar to ML with which to experiment, and
hope to build it upon LLVM.  Unfortunately, in order to implement things like
lexical scoping and closures, I need to be able to not only access variables on
the frame but also pass in a static link.

As far as I can tell from reading the notes on the topic, the static link could
be resolved by simply passing a pointer to the appropriate stack frame, so this
isn't a serious issue.

Also, if the continuation passing scheme were to be employed, how many new
optimizations would have to be written to make it actually efficient?  Is the
only necessary change transforming the code to use CPS, or would other passes
have to be written to make it efficient?  How badly would CPS break the other
optimizations that LLVM performs?

Are there ane resources on CPS that provide more insight?  Most of what I could
find online only talked about it from a theoretical perspective and did a lot of
hand waving on the actual specifics.

Thank you for your time,
Ben Chambers

P.S. The document I was referring to for the notes on how to implement this in
LLVM is available at this location:
   http://www.nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Explicitly Managed Stack Frames

Chris Lattner
On Wed, 11 Jan 2006, Ben Chambers wrote:
> I was wondering what the current state of this (explicitly managed stack frames)
> is.  Is it being worked on?  If not, how hard do you think it would be for me to
> add it?

I'm not sure what you mean.  It depends on correct tail calls, but no
other LLVM-level support.

> I am more than willing to work on it, but don't have any experience
> with LLVM, so it might take a while.  The reason I ask is because I am starting
> work on a project to make a language similar to ML with which to experiment, and
> hope to build it upon LLVM.  Unfortunately, in order to implement things like
> lexical scoping and closures, I need to be able to not only access variables on
> the frame but also pass in a static link.

Ok.  Are you planning on garbage collecting your stack frames, or do you
just need a static link?  If you just need a static link (because of
nested functions like pascal) but don't need GC'd stack frames, there is
no need even for tail call support and CPS and other craziness, just pass
your static link or display as an argument: lower to LLVM just like you
would lower to machine code.

> As far as I can tell from reading the notes on the topic, the static link could
> be resolved by simply passing a pointer to the appropriate stack frame, so this
> isn't a serious issue.

See above: if all you need is a static link, you don't need anything fancy
from LLVM.

> Also, if the continuation passing scheme were to be employed, how many new
> optimizations would have to be written to make it actually efficient?  Is the
> only necessary change transforming the code to use CPS, or would other passes
> have to be written to make it efficient?  How badly would CPS break the other
> optimizations that LLVM performs?

It is unclear.  Noone has ported a performant language to use LLVM in this
way.  My guess (from similar other experiences) is that it will be
relatively easy to get the first 80% of performance and relatively hard to
get the last 20%.  It seems that's how things always go :)

> Are there ane resources on CPS that provide more insight?  Most of what I could
> find online only talked about it from a theoretical perspective and did a lot of
> hand waving on the actual specifics.

I don't know of anything off-hand, but there are books that talk about it
and google can probably dig some stuff up.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Explicitly Managed Stack Frames

Ben Chambers-2
Chris Lattner wrote:

> On Wed, 11 Jan 2006, Ben Chambers wrote:
>
>> I was wondering what the current state of this (explicitly managed
>> stack frames)
>> is.  Is it being worked on?  If not, how hard do you think it would
>> be for me to
>> add it?
>
>
> I'm not sure what you mean.  It depends on correct tail calls, but no
> other LLVM-level support.

Really?  But if there are explicitly managed stack frames, it would be
best for LLVM to spill registers into that location.  Otherwise, the
front-end will be generating code to store the variable into the
explicit stack frame before performing a call, and LLVM may emit some
spill code to load that variable off the real stack frame (the one that
LLVM uses).  So it seems like it is pretty easy to make code that will
work, but at the same time I think it will either prevent or make less
useful a good portion of the optimization work that has gone into LLVM.  
I guess the only way to know for sure is to implement it... so I'll get
started on that :P

>
>> I am more than willing to work on it, but don't have any experience
>> with LLVM, so it might take a while.  The reason I ask is because I
>> am starting
>> work on a project to make a language similar to ML with which to
>> experiment, and
>> hope to build it upon LLVM.  Unfortunately, in order to implement
>> things like
>> lexical scoping and closures, I need to be able to not only access
>> variables on
>> the frame but also pass in a static link.
>
>
> Ok.  Are you planning on garbage collecting your stack frames, or do
> you just need a static link?  If you just need a static link (because
> of nested functions like pascal) but don't need GC'd stack frames,
> there is no need even for tail call support and CPS and other
> craziness, just pass your static link or display as an argument: lower
> to LLVM just like you would lower to machine code.

In order to return closures (which are functions, but may have some
dependence on the environment in which they are created), you need to
keep all the preceeding stack frames alive until after the closure goes
dead.  The easiest way to implement this, by far, is through the use of
garbage collected stack frames.  It also results in the highest efficiency.

-- Ben Chambers

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Explicitly Managed Stack Frames

Chris Lattner
On Sat, 14 Jan 2006, Ben Chambers wrote:

> Chris Lattner wrote:
>> On Wed, 11 Jan 2006, Ben Chambers wrote:
>>> I was wondering what the current state of this (explicitly managed stack
>>> frames)
>>> is.  Is it being worked on?  If not, how hard do you think it would be for
>>> me to
>>> add it?
>> I'm not sure what you mean.  It depends on correct tail calls, but no other
>> LLVM-level support.
>
> Really?  But if there are explicitly managed stack frames, it would be best
> for LLVM to spill registers into that location.  Otherwise, the front-end
> will be generating code to store the variable into the explicit stack frame
> before performing a call, and LLVM may emit some spill code to load that
> variable off the real stack frame (the one that LLVM uses).

Really really.  The point of converting to CPS style and using tail calls
is so that the code generator can use the local stack for spills without
getting into trouble.

> So it seems like it is pretty easy to make code that will work, but at
> the same time I think it will either prevent or make less useful a good
> portion of the optimization work that has gone into LLVM.  I guess the
> only way to know for sure is to implement it... so I'll get started on
> that :P

Cool! :)

>> Ok.  Are you planning on garbage collecting your stack frames, or do you
>> just need a static link?  If you just need a static link (because of nested
>> functions like pascal) but don't need GC'd stack frames, there is no need
>> even for tail call support and CPS and other craziness, just pass your
>> static link or display as an argument: lower to LLVM just like you would
>> lower to machine code.
>
> In order to return closures (which are functions, but may have some
> dependence on the environment in which they are created), you need to keep
> all the preceeding stack frames alive until after the closure goes dead.  The
> easiest way to implement this, by far, is through the use of garbage
> collected stack frames.  It also results in the highest efficiency.

Yup, makes sense!

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev