One-way stack support

One-way stack support

[John Tobey]

Greetings!

I'd like to port GCC's cc1 to the Functional C ABI.  "Functional C" is
what I call C minus the rule against returning pointers to automatic
storage.  I'd appreciate suggestions ranging from "it's been done" to
"here's how" or even "you must abandon this idea".

The FuncC ABI differs from all GCC-supported ABIs (to my knowledge) in
one respect.  All the others require "the stack pointer" on function
return to have some relationship to its value on entry.  Typically,
they require it to equal is previous value, perhaps after "popping"
the arguments.  Functional C, in contrast, merely requires a valid
stack on return, in no particular relationship to the caller's frame.

Of course, this implies a need for a stack extension mechanism and
garbage collection in long-running programs, but these problems have
ready solutions.

This resembles Henry Baker's so-called Cheney-on-the-M.T.A. model used
successfully by Chicken Scheme.  I consider it a "one-way" stack in
that the stack pointer does not generally return to its starting
position.  [CheneyMTA ref:
http://home.pipeline.com/~hbaker1/CheneyMTA.html]

One-way stack code can call traditional, two-way code if it provides
enough space; I'd use something like -fsplit-stack's probing
implementation before each such call.

To call back into one-way code seems a little trickier, and I am
content to require the explicit use of a library for it.

Having browsed the internals doc and i386 port, it occurs to me to
start by marking ESP as an ordinary, call-clobbered register rather
than a fixed register.  I guess I'll need a fixed register to take its
place, so I'd choose EBP, the traditional frame pointer.

Then I'd try to express the new stack protocol: no more restoring ESP
at the end of functions, but leave it pointing to "the stack" at calls
and returns.  As an optimization, I'd try to reclaim space when safe
to do so, but in the general case, ESP moves only down.  You'd see
some form of jump instead of "ret", "mov" instead of "pop" in the
output.

Of course, I'd want to use tail calls whenever possible, so rather
than the current PIC register mechanism, I'd consider requiring the
callee's address to be in, say, ECX on entry.

I've typed up a few more (tentative) details to optimize the calling
convention for 32-bit x86.  [ref:
http://john-edwin-tobey.org/FuncC/funcc/funcc.txt] But the hardest
part, I think, will be to make GCC accept a one-way stack.

Thoughts?  Suggestions?  Readings?

Good day!
-John

Re: One-way stack support

[Ian Lance Taylor]

John Tobey <john.tobey@gmail.com> writes:

> But the hardest
> part, I think, will be to make GCC accept a one-way stack.

I don't think that part would be all that hard.  gcc requires the stack
pointer to be valid on function entry, but it doesn't particularly care
what happens on function exit.  Naturally most current epilogue routines
restore the stack; you would just have to change the epilogue code to do
something else.  Of course the caller would have to always use a frame
pointer, but that is already supported so that gcc works when stack
space is allocated dynamically.

Ian

Re: One-way stack support

[John Tobey]

On Thu, Nov 18, 2010 at 5:40 PM, Ian Lance Taylor <iant@google.com> wrote:
> I don't think that part would be all that hard.  gcc requires the stack
> pointer to be valid on function entry, but it doesn't particularly care
> what happens on function exit.  Naturally most current epilogue routines
> restore the stack; you would just have to change the epilogue code to do
> something else.  Of course the caller would have to always use a frame
> pointer, but that is already supported so that gcc works when stack
> space is allocated dynamically.

Ian,

Thanks, I feel reassured.  By the way, thanks for your wonderful
series on linkers.

Cheers,
John