Dave Korn wrote:
Albert Cohen wrote:
Unfortunately, the state of the art (more recent that the thesis
referenced in the original email, see Touati's web page) is limited to
basic block and software-pipelining scopes, and limited to scheduling.
Compared to the tasks currently managed by reload, it certainly misses a
whole bunch of instruction selection and immediate operand/address mode
corner case problems (depending on the target). It also misses global
scheduling, but extended BB scheduling is not very hard to approximate,
as well as superblock scheduling.
I'm not at all a knowledgeable person to tell you what to do in the case
of GCC, but for sure saturation/sufficiency-based approches are not
sufficient to kill the dragon.
If a clever pass running before reload could
insert explicit spill/reload code at well-chosen places (bearing in mind
class-based register pressure), it could relieve reload of the necessity to
generate its own spill code most of the time, and let it just do what it does
best.
This is basically what I've been working on. Effectively there's two
stages.
The first is a localization phase which localizes pseudos which didn't
get hard registers to live within basic blocks. This obviously creates
new pseudos.
I then run a block-local register allocation phase to attempt to
allocate those newly created pseudos (or any pre-existing block locals
that didn't get hard registers) to hard registers. The block local
allocator also has some spilling capabilities (which can create, yes,
even more new pseudos which it'll then proceed to assign to hard registers).
Reload is then allowed to run in the normal fashion for the time being,
though obviously the long term goal is a drastically simpler reload.
Right now the block-local allocator doesn't deal with constraint
mismatches, but there's no reason it can't in the future. There's some
clear problems with double-word values, but I'm happy with the code so far.
Note that I don't iterate IRA -- I went down that path for a while, but
couldn't ever get comfortable with the hacks necessary to ensure
iteration would ultimately finish.
Jeff
