In trying to add Fixed interval support on the register allocation algorithm, to preserve registers across call sites, I ran into a problem with our current representation.
Given a call instruction like this:
20: ... 22: (9) $t_9 = call $t_8, global, $t_7 continue call_cont 24: ...
I need to be able to express the fact that all registers will be used during a function call. The algorithm given in the paper expresses it by assigning a live range interval [22,23[ for all registers. They call this a fixed interval. This effectively forces all live values in registers to be spilled at a function call site, because their own live range intersect with the fixed interval.
However, given our current notation, I would say that 't_9' starts being live at 22, which intersects with the fixed interval of any of the registers. For the fixed interval to be used correctly, I would need to be able to express the fact that the return value live range starts right after the fixed interval ends, in this case $t_9 = [23,...[. I see it as a decoupling between the function call and the return value.
At this point, I don't know if this could have unintended consequences down the road and I would like your opinion on this.
Erick
Afficher les réponses par date
Hmmm. Is this part of the on-the-fly register allocation technique? You seem to be implementing something else.
Marc
On 2010-07-24, at 4:51 PM, Erick Lavoie wrote:
In trying to add Fixed interval support on the register allocation algorithm, to preserve registers across call sites, I ran into a problem with our current representation.
Given a call instruction like this:
20: ... 22: (9) $t_9 = call $t_8, global, $t_7 continue call_cont 24: ...
I need to be able to express the fact that all registers will be used during a function call. The algorithm given in the paper expresses it by assigning a live range interval [22,23[ for all registers. They call this a fixed interval. This effectively forces all live values in registers to be spilled at a function call site, because their own live range intersect with the fixed interval.
However, given our current notation, I would say that 't_9' starts being live at 22, which intersects with the fixed interval of any of the registers. For the fixed interval to be used correctly, I would need to be able to express the fact that the return value live range starts right after the fixed interval ends, in this case $t_9 = [23,...[. I see it as a decoupling between the function call and the return value.
At this point, I don't know if this could have unintended consequences down the road and I would like your opinion on this.
Erick _______________________________________________ Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
This is part of the linear scan register allocation algorithm as explained in:
Optimized interval splitting in a linear scan register allocator, by C Wimmer and H Mössenböck ACM/USENIX 2005
Maxime and I chose this algorithm because recently, it has been shown that register allocation could be performed directly on SSA form in:
Linear scan register allocation on ssa form, by C Wimmer and M Franz at CGO 2010
The algorithm relies on a number of things to work, namely:
linear block ordering of CFG live range intervals: one or more ranges defining intervals for temporaries possibly with "holes" in them use positions: positions where temporaries are read or written and a flag telling if they require a register for the operation or not fixed positions: intervals where a physical register is unavailable for allocation
Given the information above, the algorithm will possibly split different intervals for temporaries and assign a register or a memory location for each of those intervals.
The authors explained that the information given is sufficient to modelize architecture specific constraints such that no "scratch" register will need to be reserved. They also showed in the second paper that live range computation could be done without an expensive dataflow analysis as long as the block ordering was satisfying two properties: 1. Dominator blocks appear before their successors 2. All blocks in a loop are contiguous
Finally, also in the second paper they show that SSA form deconstruction, i.e. transforming Phi nodes to moves, could be integrated in the resolution phase of the linear scan register allocation, when moves are inserted to resolve differences in location for intervals present in a predecessor and a successor block.
Erick
Le 10-07-24 21:31 , Marc Feeley a écrit :
Hmmm. Is this part of the on-the-fly register allocation technique? You seem to be implementing something else.
Marc
On 2010-07-24, at 4:51 PM, Erick Lavoie wrote:
In trying to add Fixed interval support on the register allocation algorithm, to preserve registers across call sites, I ran into a problem with our current representation.
Given a call instruction like this:
20: ... 22: (9) $t_9 = call $t_8, global, $t_7 continue call_cont 24: ...
I need to be able to express the fact that all registers will be used during a function call. The algorithm given in the paper expresses it by assigning a live range interval [22,23[ for all registers. They call this a fixed interval. This effectively forces all live values in registers to be spilled at a function call site, because their own live range intersect with the fixed interval.
However, given our current notation, I would say that 't_9' starts being live at 22, which intersects with the fixed interval of any of the registers. For the fixed interval to be used correctly, I would need to be able to express the fact that the return value live range starts right after the fixed interval ends, in this case $t_9 = [23,...[. I see it as a decoupling between the function call and the return value.
At this point, I don't know if this could have unintended consequences down the road and I would like your opinion on this.
Erick _______________________________________________ Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
The return value temporary is produced by the function call, and so starts being live after the call has returned, and the return value has been recuperated (from the stack or from another register). I think it would make perfect sense to say that its live interval starts right after the call or at the call. This would also be coherent with the way the live intervals of other instruction output temporaries are treated, I believe.
In effect, I think it doesn't matter if the live interval of $t_9 starts at 22. What matters is that all live used registers be spilled before the function call, and that after the call, the function's return value ends up in whichever register is assigned to $t_9.
- Maxime
In trying to add Fixed interval support on the register allocation algorithm, to preserve registers across call sites, I ran into a problem with our current representation.
Given a call instruction like this:
20: ... 22: (9) $t_9 = call $t_8, global, $t_7 continue call_cont 24: ...
I need to be able to express the fact that all registers will be used during a function call. The algorithm given in the paper expresses it by assigning a live range interval [22,23[ for all registers. They call this a fixed interval. This effectively forces all live values in registers to be spilled at a function call site, because their own live range intersect with the fixed interval.
However, given our current notation, I would say that 't_9' starts being live at 22, which intersects with the fixed interval of any of the registers. For the fixed interval to be used correctly, I would need to be able to express the fact that the return value live range starts right after the fixed interval ends, in this case $t_9 = [23,...[. I see it as a decoupling between the function call and the return value.
At this point, I don't know if this could have unintended consequences down the road and I would like your opinion on this.
Erick _______________________________________________ Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
-
chevalma＠iro.umontreal.ca -
Erick Lavoie -
Marc Feeley