llvm dev - Apr 2010 - [LLVMdev] Injecting code before function prolog

I'm trying to implement something similar to this:
http://gcc.gnu.org/wiki/SplitStacks in LLVM.  The reason I want this
is so that I can have dynamically growing and shrinking stacks in my
programming language.  In order to do this, I need to be able to check
for overflow of a stack frame.  The methods of doing this are outlined
in the link above, but my intention is to pass the current stack limit
as the first argument to the function.

What I'm hoping to do is to be able to inject the following code (in
x86 asm, c calling convention) on entry to each function:
_foo:
  lea -frame_size(%esp), %eax
  cmpl %eax, 4(%esp)
  jb function_entry
  // handle overflow
function_entry:
  function prolog
  ...

The problem I'm encountering is how to force this before the prolog.
I'm attempting to add a machine function pass after the emit
prolog/epilog pass that injects this code, but directly injecting x86
code seems to be very messy as I have to figure out how LLVM encodes
the addressing modes and instructions specific to x86.  Additionally,
directly inject x86 code produces an LLVM that is not target
independent anymore.

Is there a better way to do this?  Can I maintain target independence?
 All I really need is to be able to access the stack pointer.

Thanks for your help,
Arlen Cox

On Apr 7, 2010, at 10:43 AM, Arlen Cox wrote:
> I'm trying to implement something similar to this:
> http://gcc.gnu.org/wiki/SplitStacks in LLVM.  The reason I want this
> is so that I can have dynamically growing and shrinking stacks in my
> programming language.  In order to do this, I need to be able to check
> for overflow of a stack frame.  The methods of doing this are outlined
> in the link above, but my intention is to pass the current stack limit
> as the first argument to the function.
> 
> What I'm hoping to do is to be able to inject the following code (in
> x86 asm, c calling convention) on entry to each function:
> _foo:
>  lea -frame_size(%esp), %eax
>  cmpl %eax, 4(%esp)
>  jb function_entry
>  // handle overflow
> function_entry:
>  function prolog
>  ...
> 
> The problem I'm encountering is how to force this before the prolog.
> I'm attempting to add a machine function pass after the emit
> prolog/epilog pass that injects this code, but directly injecting x86
> code seems to be very messy as I have to figure out how LLVM encodes
> the addressing modes and instructions specific to x86.  Additionally,
> directly inject x86 code produces an LLVM that is not target
> independent anymore.
> 
> Is there a better way to do this?  Can I maintain target independence?
> All I really need is to be able to access the stack pointer.
Would it make sense to do this within the TargetRegisterInfo::emitPrologue 
hooks?

Dan

On Wed, Apr 7, 2010 at 12:43 PM, Arlen Cox <arlencox at gmail.com>
wrote:
> I'm trying to implement something similar to this:
> http://gcc.gnu.org/wiki/SplitStacks in LLVM.  The reason I want this
> is so that I can have dynamically growing and shrinking stacks in my
> programming language.  In order to do this, I need to be able to check
> for overflow of a stack frame.  The methods of doing this are outlined
> in the link above, but my intention is to pass the current stack limit
> as the first argument to the function.
>
> What I'm hoping to do is to be able to inject the following code (in
> x86 asm, c calling convention) on entry to each function:
> _foo:
>  lea -frame_size(%esp), %eax
>  cmpl %eax, 4(%esp)
>  jb function_entry
>  // handle overflow
> function_entry:
>  function prolog
>  ...
>
> The problem I'm encountering is how to force this before the prolog.
> I'm attempting to add a machine function pass after the emit
> prolog/epilog pass that injects this code, but directly injecting x86
> code seems to be very messy as I have to figure out how LLVM encodes
> the addressing modes and instructions specific to x86.  Additionally,
> directly inject x86 code produces an LLVM that is not target
> independent anymore.
>
> Is there a better way to do this?  Can I maintain target independence?
>  All I really need is to be able to access the stack pointer.
>
> Thanks for your help,
> Arlen Cox
I wonder if it might be better to inject something at callsites. That
way you don't have to copy part of the preexisting stack... just
adjust the stack pointer and then lay down the arguments and return
address.  (Of course you'd have to be able to get to your own stack
variables while you're doing this somehow).  Also, this makes all
issues regarding calling conventions, combining split-stack functions
and non-split-stack functions, and so forth go away.

It seems like doing this would require one of three things:
1) it would require two overflow checks per function call.  One prior
to to the function call to handle the arguments and one after call to
handle the stack frame.  Since I am already concerned about the cost
of the overflow checks, I don't believe this is a particularly good
option (also it doesn't solve my problem of the pre-prologue code).
2) The second overflow check could be eliminated if the callee is
known at compile time.  Since the frame size of the callee could be
known at compile time, it could be combined with the callee overflow
check.  This is not adequate for many languages because of function
pointers.  If a dynamic function call is made, there is no way of
knowing the frame size of the called function, unless...
3) The function frame size is part of a function closure, allowing it
to be dynamically calculated.  I'm not sure what the overhead of this
would be in terms of memory or performance.  It would have to be
evaluated.  The only think I know to be wrong with this approach is
that it restricts these dynamic stacks to languages with some sort of
meta-information for functions.  This does not handle the
general-case, which a split stack approach, should.

Thanks for the suggestions.  I may look at number 3 in the future, but
for a first pass, I believe my current approach to be the best.  If
you have any other ideas, do please share.



On Sat, Apr 10, 2010 at 5:14 PM, Kenneth Uildriks <kennethuil at
gmail.com> wrote:
> On Wed, Apr 7, 2010 at 12:43 PM, Arlen Cox <arlencox at gmail.com>
wrote:
>> I'm trying to implement something similar to this:
>> http://gcc.gnu.org/wiki/SplitStacks in LLVM.  The reason I want this
>> is so that I can have dynamically growing and shrinking stacks in my
>> programming language.  In order to do this, I need to be able to check
>> for overflow of a stack frame.  The methods of doing this are outlined
>> in the link above, but my intention is to pass the current stack limit
>> as the first argument to the function.
>>
>> What I'm hoping to do is to be able to inject the following code
(in
>> x86 asm, c calling convention) on entry to each function:
>> _foo:
>>  lea -frame_size(%esp), %eax
>>  cmpl %eax, 4(%esp)
>>  jb function_entry
>>  // handle overflow
>> function_entry:
>>  function prolog
>>  ...
>>
>> The problem I'm encountering is how to force this before the
prolog.
>> I'm attempting to add a machine function pass after the emit
>> prolog/epilog pass that injects this code, but directly injecting x86
>> code seems to be very messy as I have to figure out how LLVM encodes
>> the addressing modes and instructions specific to x86.  Additionally,
>> directly inject x86 code produces an LLVM that is not target
>> independent anymore.
>>
>> Is there a better way to do this?  Can I maintain target independence?
>>  All I really need is to be able to access the stack pointer.
>>
>> Thanks for your help,
>> Arlen Cox
>
> I wonder if it might be better to inject something at callsites. That
> way you don't have to copy part of the preexisting stack... just
> adjust the stack pointer and then lay down the arguments and return
> address.  (Of course you'd have to be able to get to your own stack
> variables while you're doing this somehow).  Also, this makes all
> issues regarding calling conventions, combining split-stack functions
> and non-split-stack functions, and so forth go away.
>