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