I am trying to first clarify what elements are necessary for program execution and which of those might be worth putting in registers. I call register usage configuration which of those elements are put in a register and which are located in memory. I am trying to anticipate the different configurations we might want to try to see what is worth being made configurable. Feel free to add anything you think should be included and any ideas of optimizations that might have an impact on register usage.
__Definitions__
X86_REG means any of EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP X64_REG means any of RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8-R15
REG means any one of X86_REG or X64_REG (depending on the platform) excluding those previously used for a special purpose
MEM means an emplacement in memory either accessible from the context or the stack.
GLO means an emplacement in memory determined at linking time (like a global variable) which can be seen as static from the runtime code.
Here are the elements we might want to put in a register or not. Possible configurations are given between brackets separated by commas.
__Runtime elements and possible configurations__
Stack Pointer (xSP, xBP): Mark suggested using xBP to possibly use xSP for object allocation and I am also including xSP in case we might want to keep it in the standard location ( Would it simplify a future Foreign Function Interface?).
Heap Pointer (xSP, GLO): Pointer to the remaining free space on the heap when using a compacting GC, like stop© or to the beginning of the free list when using a non-compacting GC like mark&sweep. If not in a register, I would suggest having it as a global variable since it is common to all Runtime Contexts.
Runtime Context (REG, GLO): Contains all the information specific to a given instance of tachyon. An instance might be a browser tab/window or the compiler itself. The runtime context is an object in memory containing minimally the global object and the root object (Object.prototype). The runtime context object might contain handlers references when accessed from a register to preserve a register for other usage.
Handlers (REG, GLO): Contains references to general handlers to perform the general but less common case for various operations such as additions, multiplication, etc. or for expensive but less common operations such as exception handling. When accessed from a register, the handlers references might be put at the end of the runtime context object.
Argument Nb (REG, MEM): The number of arguments given by the caller of a function. When in a register, can be combined with the Runtime Context to save a register, given that the context object are aligned to a given value, liberating the lower bits of the Runtime Context register. When in memory, it will be saved on the stack as part of the function call protocol.
Return Address (REG, MEM): Return address of the currently executing function. Whether in memory or in a register, it will be saved, restored or set as part of the function call protocol.
Implicit Function Arguments (2 REG, REG + MEM, MEM): Arguments to a function not explicitly part of the function definition (not given between the brackets), such as the function reference (when arguments.callee is used or when calling a closure) and the this object, which can either be any object or the global object. When passed in registers, each implicit argument use a different register. When passed in memory, they are passed on the stack. In the two cases, this is part of the function call protocol. I separated them from the explicit function arguments because it might happen that most functions in a real world application are not used in an object-oriented style or as closures so it would liberate two registers for other arguments. If the distinction turns out not to be really useful, we might simply consider all of the arguments as explicit function arguments in the same order as given in the current IR.
Explicit Function Arguments (k REG + (n-k) MEM): Arguments to a function explicitly part of the function definition (given between the brackets). k are the first k arguments given to a function call from left to right and n is the total number of arguments given to that function call. k is a register usage configuration parameter that applies to the whole program. n is the specific number of arguments at a given call site. The first k arguments are passed in registers and the remaining (n-k) arguments are passed on the stack. The parameter k is part of the function call protocol.
That's it!
As a complementary discussion, so far I have assumed that every register was caller-save. Do you guys think that it might be worth reserving some registers to be callee-save? In that case, when those should be spilled, at the entry of a function or at the site of usage?
Erick
Afficher les réponses par date
Your parametrization of the configuration seems reasonable. However, I would add that when you indicate that something can be in GLO you should also try MEM (accessible from the context). That's because accessing something in the context (if there is a register pointing to the context) is an x86 addressing mode that is more compact and faster than accessing an absolute memory location. For example, the heap pointer and handlers.
I dont' understand what you mean by "handlers in registers". Go you want the instruction to be fast or take less space? It seems hard to justify dedicating one or more of the 8 (or 16) registers to point to handlers. The handler would have to be called very often for this to be worthwhile.
So
On 2010-09-06, at 8:16 PM, Erick Lavoie wrote:
I am trying to first clarify what elements are necessary for program execution and which of those might be worth putting in registers. I call register usage configuration which of those elements are put in a register and which are located in memory. I am trying to anticipate the different configurations we might want to try to see what is worth being made configurable. Feel free to add anything you think should be included and any ideas of optimizations that might have an impact on register usage.
__Definitions__
X86_REG means any of EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP X64_REG means any of RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8-R15
REG means any one of X86_REG or X64_REG (depending on the platform) excluding those previously used for a special purpose
MEM means an emplacement in memory either accessible from the context or the stack.
GLO means an emplacement in memory determined at linking time (like a global variable) which can be seen as static from the runtime code.
Here are the elements we might want to put in a register or not. Possible configurations are given between brackets separated by commas.
__Runtime elements and possible configurations__
Stack Pointer (xSP, xBP): Mark suggested using xBP to possibly use xSP for object allocation and I am also including xSP in case we might want to keep it in the standard location ( Would it simplify a future Foreign Function Interface?).
Heap Pointer (xSP, GLO): Pointer to the remaining free space on the heap when using a compacting GC, like stop© or to the beginning of the free list when using a non-compacting GC like mark&sweep. If not in a register, I would suggest having it as a global variable since it is common to all Runtime Contexts.
Runtime Context (REG, GLO): Contains all the information specific to a given instance of tachyon. An instance might be a browser tab/window or the compiler itself. The runtime context is an object in memory containing minimally the global object and the root object (Object.prototype). The runtime context object might contain handlers references when accessed from a register to preserve a register for other usage.
Handlers (REG, GLO): Contains references to general handlers to perform the general but less common case for various operations such as additions, multiplication, etc. or for expensive but less common operations such as exception handling. When accessed from a register, the handlers references might be put at the end of the runtime context object.
Argument Nb (REG, MEM): The number of arguments given by the caller of a function. When in a register, can be combined with the Runtime Context to save a register, given that the context object are aligned to a given value, liberating the lower bits of the Runtime Context register. When in memory, it will be saved on the stack as part of the function call protocol.
Return Address (REG, MEM): Return address of the currently executing function. Whether in memory or in a register, it will be saved, restored or set as part of the function call protocol.
Implicit Function Arguments (2 REG, REG + MEM, MEM): Arguments to a function not explicitly part of the function definition (not given between the brackets), such as the function reference (when arguments.callee is used or when calling a closure) and the this object, which can either be any object or the global object. When passed in registers, each implicit argument use a different register. When passed in memory, they are passed on the stack. In the two cases, this is part of the function call protocol. I separated them from the explicit function arguments because it might happen that most functions in a real world application are not used in an object-oriented style or as closures so it would liberate two registers for other arguments. If the distinction turns out not to be really useful, we might simply consider all of the arguments as explicit function arguments in the same order as given in the current IR.
Explicit Function Arguments (k REG + (n-k) MEM): Arguments to a function explicitly part of the function definition (given between the brackets). k are the first k arguments given to a function call from left to right and n is the total number of arguments given to that function call. k is a register usage configuration parameter that applies to the whole program. n is the specific number of arguments at a given call site. The first k arguments are passed in registers and the remaining (n-k) arguments are passed on the stack. The parameter k is part of the function call protocol.
That's it!
As a complementary discussion, so far I have assumed that every register was caller-save. Do you guys think that it might be worth reserving some registers to be callee-save? In that case, when those should be spilled, at the entry of a function or at the site of usage?
Erick
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
My first suggestion is to put your notes on Google docs. Your notes seem pretty good so far.
Some notes:
Since the heap pointer is common to all code executing in a given thread, it makes some sense to keep it in a register, as opposed to duplicating it in multiple context objects. On the other hand, on x86-32, we have very few registers already, so it might make sense to have it in some kind of global context or thread-specific context. If we optimize code well enough, we could actually significantly decrease the use of allocations. So, perhaps a good initial option would be to keep it in a register because its easy, and later on, do some profiling to see how much allocations we do, and think about moving it in a global variable.
The context object will probably store quite a few objects from the low-level JavaScript library hierarchy. It might also contain performance counters.
What's not super clear to me is how context switching will be achieved. Tachyon compiler code needs its own global object, so do program instances, but some low-level library code should execute in the context of (using the global object of) the calling code.
I would not differentiate between implicit and explicit call arguments. They are essentially the same thing at a low-level. Our optimization system will take care of specializing functions and eliminating the unnecessary call arguments when possible.
The return address should probably be pushed on the stack. Ideally, short-running functions should be aggressively inlined, and the long-running functions that are left uninlined will only need to read the return address once.
I would keep the call protocol simple for now, so having everything caller-save makes sense.
- Maxime
I am trying to first clarify what elements are necessary for program execution and which of those might be worth putting in registers. I call register usage configuration which of those elements are put in a register and which are located in memory. I am trying to anticipate the different configurations we might want to try to see what is worth being made configurable. Feel free to add anything you think should be included and any ideas of optimizations that might have an impact on register usage.
__Definitions__
X86_REG means any of EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP X64_REG means any of RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8-R15
REG means any one of X86_REG or X64_REG (depending on the platform) excluding those previously used for a special purpose
MEM means an emplacement in memory either accessible from the context or the stack.
GLO means an emplacement in memory determined at linking time (like a global variable) which can be seen as static from the runtime code.
Here are the elements we might want to put in a register or not. Possible configurations are given between brackets separated by commas.
__Runtime elements and possible configurations__
Stack Pointer (xSP, xBP): Mark suggested using xBP to possibly use xSP for object allocation and I am also including xSP in case we might want to keep it in the standard location ( Would it simplify a future Foreign Function Interface?).
Heap Pointer (xSP, GLO): Pointer to the remaining free space on the heap when using a compacting GC, like stop© or to the beginning of the free list when using a non-compacting GC like mark&sweep. If not in a register, I would suggest having it as a global variable since it is common to all Runtime Contexts.
Runtime Context (REG, GLO): Contains all the information specific to a given instance of tachyon. An instance might be a browser tab/window or the compiler itself. The runtime context is an object in memory containing minimally the global object and the root object (Object.prototype). The runtime context object might contain handlers references when accessed from a register to preserve a register for other usage.
Handlers (REG, GLO): Contains references to general handlers to perform the general but less common case for various operations such as additions, multiplication, etc. or for expensive but less common operations such as exception handling. When accessed from a register, the handlers references might be put at the end of the runtime context object.
Argument Nb (REG, MEM): The number of arguments given by the caller of a function. When in a register, can be combined with the Runtime Context to save a register, given that the context object are aligned to a given value, liberating the lower bits of the Runtime Context register. When in memory, it will be saved on the stack as part of the function call protocol.
Return Address (REG, MEM): Return address of the currently executing function. Whether in memory or in a register, it will be saved, restored or set as part of the function call protocol.
Implicit Function Arguments (2 REG, REG + MEM, MEM): Arguments to a function not explicitly part of the function definition (not given between the brackets), such as the function reference (when arguments.callee is used or when calling a closure) and the this object, which can either be any object or the global object. When passed in registers, each implicit argument use a different register. When passed in memory, they are passed on the stack. In the two cases, this is part of the function call protocol. I separated them from the explicit function arguments because it might happen that most functions in a real world application are not used in an object-oriented style or as closures so it would liberate two registers for other arguments. If the distinction turns out not to be really useful, we might simply consider all of the arguments as explicit function arguments in the same order as given in the current IR.
Explicit Function Arguments (k REG + (n-k) MEM): Arguments to a function explicitly part of the function definition (given between the brackets). k are the first k arguments given to a function call from left to right and n is the total number of arguments given to that function call. k is a register usage configuration parameter that applies to the whole program. n is the specific number of arguments at a given call site. The first k arguments are passed in registers and the remaining (n-k) arguments are passed on the stack. The parameter k is part of the function call protocol.
That's it!
As a complementary discussion, so far I have assumed that every register was caller-save. Do you guys think that it might be worth reserving some registers to be callee-save? In that case, when those should be spilled, at the entry of a function or at the site of usage?
Erick
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2010-09-06, at 9:08 PM, chevalma@iro.umontreal.ca wrote:
My first suggestion is to put your notes on Google docs. Your notes seem pretty good so far.
Some notes:
Since the heap pointer is common to all code executing in a given thread, it makes some sense to keep it in a register, as opposed to duplicating it in multiple context objects. On the other hand, on x86-32, we have very few registers already, so it might make sense to have it in some kind of global context or thread-specific context. If we optimize code well enough, we could actually significantly decrease the use of allocations. So, perhaps a good initial option would be to keep it in a register because its easy, and later on, do some profiling to see how much allocations we do, and think about moving it in a global variable.
The context object will probably store quite a few objects from the low-level JavaScript library hierarchy. It might also contain performance counters.
What's not super clear to me is how context switching will be achieved. Tachyon compiler code needs its own global object, so do program instances, but some low-level library code should execute in the context of (using the global object of) the calling code.
I would not differentiate between implicit and explicit call arguments. They are essentially the same thing at a low-level. Our optimization system will take care of specializing functions and eliminating the unnecessary call arguments when possible.
The return address should probably be pushed on the stack. Ideally, short-running functions should be aggressively inlined, and the long-running functions that are left uninlined will only need to read the return address once.
I would keep the call protocol simple for now, so having everything caller-save makes sense.
- Maxime
The point of Erick's parameterization is to allow us to evaluate various sensible assignments of resources to see how well they perform (speed, space) on a number of benchmarks. So the goal at this point is not to choose the best assignment, but instead to make sure we cover all the reasonable assignments.
Concerning the passing of the return address the two reasonable options are in a register and on the stack. We should explore both, but let me quickly compare them to show that it is not clear which one is best.
Passing the return address on the stack can be done with the "call" x86 instruction which implicitly pushes the return address on the stack. This is compact and we can expect the processor to be designed to handle this efficiently. On the other hand, it does involve memory operations (one push and one pop), and in general it is good to avoid memory operations as much as possible. Moreover the call instruction combines two operations (i.e. "push return address" and "jump to function entry") and sometimes it is useful to do these operations separately, to do tail-call optimization and when the reordering of the basic blocks puts a recursive call immediately before the entry point of the function such as:
;; With a "call" instruction entry: if condition jump recursive_case A ret recursive_case: B call entry C ret
;; With a "jump" instruction and reordering of basic blocks recursive_case: B move ret_reg, stack_slot move $ret_point, ret_reg entry: if condition jump recursive_case A jump ret_reg .data descriptor ret_point: C jump stack_slot
In the second case, there is one fewer branch instructions in the recursive case. Branch instructions are usually expensive (note that branch prediction can alleviate this cost, but there's nothing like actually trying the code to know how well the processor handles this).
Note also that using a call instruction makes it harder to efficiently assign a descriptor to the return point (for garbage collection). It is not efficient to put the descriptor after the call instruction because it has to be "skipped" with an extra jump instruction, or by computing the proper return address in the called function. When using jump instructions the descriptor can be put just before the return point.
Another point is that using the stack may make the code easier to interface with other languages (C) which use the stack for the return address. This is not a very strong argument because to interface with other languages seamlessly we also need the parameters to be passed in the same location (where on the stack, which registers?), the execution context must be the same (frame pointer, no context register), and finally the representation of data must be the same.
Marc
I'm not necessarily suggesting we use the call and ret instructions. I simply believe that on an 8 register machine, we want to keep as many registers available as we can. If we reserve 3, 4 or even 5 of them, it seems to me like that would almost guarantee that spills occur in any non-trivial function, thereby defeating the goal of avoiding memory operations. Since the return address is only used once at the end of a function call, it seems like a logical candidate to spill.
On another note... So far, we've been discussing going caller-save, ~2 argument registers for function calls. Perhaps we ought to consider a different model, where we pass the return address as a hidden argument in a register, and as many call arguments in registers as we can manage... And let the callee spill the return address and arguments if necessary. The return address probably shouldn't be a reserved, never spilled register, and if we can get away with passing 4-6 arguments in registers (especially on x86-64), that could be effective.
- Maxime
On 2010-09-06, at 9:08 PM, chevalma@iro.umontreal.ca wrote:
My first suggestion is to put your notes on Google docs. Your notes seem pretty good so far.
Some notes:
Since the heap pointer is common to all code executing in a given thread, it makes some sense to keep it in a register, as opposed to duplicating it in multiple context objects. On the other hand, on x86-32, we have very few registers already, so it might make sense to have it in some kind of global context or thread-specific context. If we optimize code well enough, we could actually significantly decrease the use of allocations. So, perhaps a good initial option would be to keep it in a register because its easy, and later on, do some profiling to see how much allocations we do, and think about moving it in a global variable.
The context object will probably store quite a few objects from the low-level JavaScript library hierarchy. It might also contain performance counters.
What's not super clear to me is how context switching will be achieved. Tachyon compiler code needs its own global object, so do program instances, but some low-level library code should execute in the context of (using the global object of) the calling code.
I would not differentiate between implicit and explicit call arguments. They are essentially the same thing at a low-level. Our optimization system will take care of specializing functions and eliminating the unnecessary call arguments when possible.
The return address should probably be pushed on the stack. Ideally, short-running functions should be aggressively inlined, and the long-running functions that are left uninlined will only need to read the return address once.
I would keep the call protocol simple for now, so having everything caller-save makes sense.
- Maxime
The point of Erick's parameterization is to allow us to evaluate various sensible assignments of resources to see how well they perform (speed, space) on a number of benchmarks. So the goal at this point is not to choose the best assignment, but instead to make sure we cover all the reasonable assignments.
Concerning the passing of the return address the two reasonable options are in a register and on the stack. We should explore both, but let me quickly compare them to show that it is not clear which one is best.
Passing the return address on the stack can be done with the "call" x86 instruction which implicitly pushes the return address on the stack. This is compact and we can expect the processor to be designed to handle this efficiently. On the other hand, it does involve memory operations (one push and one pop), and in general it is good to avoid memory operations as much as possible. Moreover the call instruction combines two operations (i.e. "push return address" and "jump to function entry") and sometimes it is useful to do these operations separately, to do tail-call optimization and when the reordering of the basic blocks puts a recursive call immediately before the entry point of the function such as:
;; With a "call" instruction entry: if condition jump recursive_case A ret recursive_case: B call entry C ret
;; With a "jump" instruction and reordering of basic blocks recursive_case: B move ret_reg, stack_slot move $ret_point, ret_reg entry: if condition jump recursive_case A jump ret_reg .data descriptor ret_point: C jump stack_slot
In the second case, there is one fewer branch instructions in the recursive case. Branch instructions are usually expensive (note that branch prediction can alleviate this cost, but there's nothing like actually trying the code to know how well the processor handles this).
Note also that using a call instruction makes it harder to efficiently assign a descriptor to the return point (for garbage collection). It is not efficient to put the descriptor after the call instruction because it has to be "skipped" with an extra jump instruction, or by computing the proper return address in the called function. When using jump instructions the descriptor can be put just before the return point.
Another point is that using the stack may make the code easier to interface with other languages (C) which use the stack for the return address. This is not a very strong argument because to interface with other languages seamlessly we also need the parameters to be passed in the same location (where on the stack, which registers?), the execution context must be the same (frame pointer, no context register), and finally the representation of data must be the same.
Marc
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2010-09-07, at 10:58 AM, chevalma@iro.umontreal.ca wrote:
I'm not necessarily suggesting we use the call and ret instructions. I simply believe that on an 8 register machine, we want to keep as many registers available as we can. If we reserve 3, 4 or even 5 of them, it seems to me like that would almost guarantee that spills occur in any non-trivial function, thereby defeating the goal of avoiding memory operations. Since the return address is only used once at the end of a function call, it seems like a logical candidate to spill.
On another note... So far, we've been discussing going caller-save, ~2 argument registers for function calls. Perhaps we ought to consider a different model, where we pass the return address as a hidden argument in a register, and as many call arguments in registers as we can manage... And let the callee spill the return address and arguments if necessary. The return address probably shouldn't be a reserved, never spilled register, and if we can get away with passing 4-6 arguments in registers (especially on x86-64), that could be effective.
That's what I was assuming all along! We definitely don't want to reserve a register for the return address for the duration of the called function. Even the context register can be spilled if we are clever about it (but in our first prototype we should probably reserve a register for the context register and argument count).
Marc
-
chevalma＠iro.umontreal.ca -
Erick Lavoie -
Marc Feeley