Register spilling mechanism

I'm currently want to make an inlining for methods of specific format
(lets call them 'native' methods),
these methods should work as ST methods (same calling convention &
stack layout when you entering method), but
these methods don't do polymorphic sends unless specified exclusively,
instead all sends are inlined statically with compiler.
I don't want to describe much details here, just want you to help me
how to deal with register spilling when inlining.

Suppose i inlining a send like:

object message: a+b with: c+d with: a+d with: ....

so, all arguments to method now should use machine temporary registers
instead of stack, because it's more effective.

What i fear of that if register allocator sees that there is not
enough registers in CPU to fit them all it starts using stack for
storing temp values
and there is some situations where i need to know exact stack depth
for a method.
Is there any way in Exupery to get know, how many registers will be
spilled on stack, so this information can be used by my compiler?


--
Best regards,
Igor Stasenko AKA sig.
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery

More broader explanation why i need this..
I want to allow direct stack manipulation for native methods to some extent.

In code, one can write:

(object1 expression1) push.
(object2 expression2) push.
address call.

Now i need to make sure that Exupery will produce correct stack frame
for a call, regardless what code inlined in expression1/expression2
it should not interfere with top stack layout, which should be:

<result of expression1>
<result of expression2>
<return address>

when entering routine at (address call).

--
Best regards,
Igor Stasenko AKA sig.
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery

Igor Stasenko writes:
 > More broader explanation why i need this..
 > I want to allow direct stack manipulation for native methods to some extent.
 >
 > In code, one can write:
 >
 > (object1 expression1) push.
 > (object2 expression2) push.
 > address call.
 >
 > Now i need to make sure that Exupery will produce correct stack frame
 > for a call, regardless what code inlined in expression1/expression2
 > it should not interfere with top stack layout, which should be:
 >
 > <result of expression1>
 > <result of expression2>
 > <return address>
 >
 > when entering routine at (address call).

Are you talking about the C stack or the Smalltalk stack?

If you're talking about the Smalltalk stack then in Exupery it's only
dealt with in the front half of Exupery. It's handled in the
ByteCodeReader and IntermediateSimplifier. Exupery uses exactly the
same stack locations as the interpreter so doesn't need to check the
stack height. It'll break for exactly the same methods that will cause
the interpreter to crash. Exupery does model the stack in both classes
so it would be fairly easy to monitor stack height if you were
interested.

The C stack is maintained by Exupery, and is currently a fixed size
but will be dynamically sized sometime in the future. Exupery will
fail to compile if it uses more C stack than exists. The amount of C
stack used isn't known until after register allocation because that's
where registers are spilled to.

It's also possible to spill directly into the context (into the
Smalltalk stack) which is done for stack registers. That's new in
0.14 and will be extended to temporaries as well.

Bryce
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery

2008/4/22  <[hidden email]>:
No, forget about Smalltalk stack, i plan to use Exupery at lower
levels to produce machine code fed by my own compiler.

>  The C stack is maintained by Exupery, and is currently a fixed size
>  but will be dynamically sized sometime in the future. Exupery will
>  fail to compile if it uses more C stack than exists. The amount of C
>  stack used isn't known until after register allocation because that's
>  where registers are spilled to.
>

I don't know what you mean under 'C stack'.
Isn't Exupery compiles directly to machine code? Then why you speaking
about C stack at all? ;)

As i understand (correct me if i'm wrong) by fixed size stack you
mean, that after done register allocation, Exupery determines the
exact size of stack, and then it inserts an instruction in method's
preamble to allocate it, like:

push %ebp
mod %ebp, %esp
sub %esp, stacksize

and at return point it does reverse:

add %esp, stacksize
pop %ebp
ret

or, does just 'ret' , in case if caller are responsible from cleaning
the stack and can restore %ebp.

And by dynamic stack size, you mean that instead of preallocating
fixed amount of bytes on stack, in future, it can use pushes/pops in
code based on demand?

I having nothing against both models, just need a safe way how i can
manipulate stack directly without being endangered by register
allocator to corrupt stack layout which developer expecting to have.

Let me elaborate the problem in the way how i see it.
Suppose my compiler generates the code in form, what we call 'Exupery
low-level intermediate'.
So, there are a 'virtual' machine instructions arranged in blocks and
using N temporary registers.
Now, after register allocator did its job, we are know, that we need
extra K bytes on stack to hold temporary values which is not fit in
CPU registers at some points of code.
And now, an instruction selector for particular temps should use
instructions to store/read values on stack.
But also there are need to generate instructions to preallocate the
stack space to hold these values and deallocate it at some point,
where they no longer needed.
Now, who is controlling these actions? And can outer subsystem
influence where to put stack allocation instruction, for instance?

Can be there any contracts between Exupery and caller, where i can
state that code should compile under certain rules, like:
- specify a set of registers, which should be preserved after given
code done working
- specify, what registers code expects to be preserved when doing calls
- specify, what registers should be reverted just before ret/non-local
jump instructions



--
Best regards,
Igor Stasenko AKA sig.
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery

Igor Stasenko writes:
 > 2008/4/22  <[hidden email]>:
 > >
 > > Igor Stasenko writes:
 > >   > More broader explanation why i need this..
 > >   > I want to allow direct stack manipulation for native methods to some extent.
 > >   >
 > >   > In code, one can write:
 > >   >
 > >   > (object1 expression1) push.
 > >   > (object2 expression2) push.
 > >   > address call.
 > >   >
 > >   > Now i need to make sure that Exupery will produce correct stack frame
 > >   > for a call, regardless what code inlined in expression1/expression2
 > >   > it should not interfere with top stack layout, which should be:
 > >   >
 > >   > <result of expression1>
 > >   > <result of expression2>
 > >   > <return address>
 > >   >
 > >   > when entering routine at (address call).
 > >
 > >  Are you talking about the C stack or the Smalltalk stack?
 > >
 > >  If you're talking about the Smalltalk stack then in Exupery it's only
 > >  dealt with in the front half of Exupery. It's handled in the
 > >  ByteCodeReader and IntermediateSimplifier. Exupery uses exactly the
 > >  same stack locations as the interpreter so doesn't need to check the
 > >  stack height. It'll break for exactly the same methods that will cause
 > >  the interpreter to crash. Exupery does model the stack in both classes
 > >  so it would be fairly easy to monitor stack height if you were
 > >  interested.
 > >
 >
 > No, forget about Smalltalk stack, i plan to use Exupery at lower
 > levels to produce machine code fed by my own compiler.
 >
 > >  The C stack is maintained by Exupery, and is currently a fixed size
 > >  but will be dynamically sized sometime in the future. Exupery will
 > >  fail to compile if it uses more C stack than exists. The amount of C
 > >  stack used isn't known until after register allocation because that's
 > >  where registers are spilled to.
 > >
 >
 > I don't know what you mean under 'C stack'.
 > Isn't Exupery compiles directly to machine code? Then why you speaking
 > about C stack at all? ;)

The machine stack which C also uses. The stack follow's C's
conventions for calls and returns. It's the stack that the C
in the interpreter uses.

 > As i understand (correct me if i'm wrong) by fixed size stack you
 > mean, that after done register allocation, Exupery determines the
 > exact size of stack, and then it inserts an instruction in method's
 > preamble to allocate it, like:
 >
 > push %ebp
 > mod %ebp, %esp
 > sub %esp, stacksize
 >
 > and at return point it does reverse:
 >
 > add %esp, stacksize
 > pop %ebp
 > ret
 >
 > or, does just 'ret' , in case if caller are responsible from cleaning
 > the stack and can restore %ebp.

It generates sequences like you suggest but they're generated
as low level intermediate then instruction selected before
register allocation. So the size is set before the number of
spills is known. I've been using a fixed size stack frame as
at temporary measure, it's been good enough for now, there isn't
a great deal of pressure on that memory especially as Exupery
can now spill directly into the context frame.

If you're planning on generating C style calls in code be careful.
If a GC happens as part of the call any object may be moved. Exupery
doesn't really save the C (machine) stack because it doesn't have any
state at any time it would risk making calls, it moves all the state
back into real objects so the GC can see it.

 > Can be there any contracts between Exupery and caller, where i can
 > state that code should compile under certain rules, like:
 > - specify a set of registers, which should be preserved after given
 > code done working
 > - specify, what registers code expects to be preserved when doing calls
 > - specify, what registers should be reverted just before ret/non-local
 > jump instructions

It would be possible to control what you want to, but there's no
published interface. The intermediate languages will change as
Exupery evolves.

Bryce
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery

2008/4/24  <[hidden email]>:
Don't worry about it. I'm planning to overthrow the rule of C and make
every bit in VM be implemented as native methods
which can be compiled at run time. :)
So, i care little about what calling convention C or other libraries having.
All foreign calls will be handled by FFI class(es) (compiled as
anything else as well), while inside i'll have methods compiled to
machine code and i'm free to choose any calling convention for them,
as well as choose own stack layout which will be convenient for GC and
object memory.
That's why i asked how i can control these aspects with Exupery.

Thank you for explanation. I will look forward for any updates
concerning these features.
Maybe, as temporary solution, i can patch register allocator to get
some feedback on how many stack space i need, and then
re-run it again.
Or i can try to measure maximum number of live temps in code by own.

>
>
>  Bryce
>  _______________________________________________
>  Exupery mailing list
>  [hidden email]
>  http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery
>



--
Best regards,
Igor Stasenko AKA sig.
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery

Igor Stasenko writes:
 > Don't worry about it. I'm planning to overthrow the rule of C and make
 > every bit in VM be implemented as native methods
 > which can be compiled at run time. :)
 > So, i care little about what calling convention C or other libraries having.
 > All foreign calls will be handled by FFI class(es) (compiled as
 > anything else as well), while inside i'll have methods compiled to
 > machine code and i'm free to choose any calling convention for them,
 > as well as choose own stack layout which will be convenient for GC and
 > object memory.
 > That's why i asked how i can control these aspects with Exupery.

If an signal comes in from the OS, then the signal will be executed on
the machine (C) stack, so the stack pointer must always be correct. If
not you risk having your C stack trashed by the signal.

 > >
 > >   > Can be there any contracts between Exupery and caller, where i can
 > >   > state that code should compile under certain rules, like:
 > >   > - specify a set of registers, which should be preserved after given
 > >   > code done working
 > >   > - specify, what registers code expects to be preserved when doing calls
 > >   > - specify, what registers should be reverted just before ret/non-local
 > >   > jump instructions
 > >
 > >  It would be possible to control what you want to, but there's no
 > >  published interface. The intermediate languages will change as
 > >  Exupery evolves.
 > >
 >
 > Thank you for explanation. I will look forward for any updates
 > concerning these features.
 > Maybe, as temporary solution, i can patch register allocator to get
 > some feedback on how many stack space i need, and then
 > re-run it again.
 > Or i can try to measure maximum number of live temps in code by own.

The best bet would be to read the final stack height from the register
allocator. Though for now it'll always be 64 bytes big. Look
at SpillInserter and MachineX86>>newSpillSlot. That's the code
responsible for managing the stack.

Also look at the loadStack and the storeStack instructions as they
generate the Smalltalk stack loading and storing instructions in the
register allocator after all spills have been made. This is to avoid
loading spilled values from the Smalltalk stack.

Bryce
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery