Re: Register allocation and instruction scheduling

  mikesw@whiterose.net (Chris) writes:
> 1) How to take into account register renaming by the hardware by the
> compiler: especialy when using graph coloring techniques?
>
> 2) How to take into account hardware instruction scheduling/reordering
> when trying to do different types of compiler instruction optimzation.


Normally you don't take these features into account at all in the
compiler. At least I have seen no papers about it.


However, I have thought a little bit about it, and you could exploit
these features to reduce the (logical) register pressure: after
instruction scheduling, but before register allocation, you perform a
rescheduling pass: it moves the instructions up or down by a few
cycles (as much as will be undone by the hardware scheduler) such that
the register pressure is reduced. E.g., you would move a store
upwards, if it kills its operands; this reduces the (logical) register
pressure on the instructions that the store is moved over, and might
avoid some spill code. At run-time the hardware moves the store down
again, using its additional physical registers for the intermediate
storage.


Of course, the rescheduler has to honour dependences, just as the
original scheduler.


> Doesn't the hardware essentially undo all of my hard work in trying to
> write an optimized compiler?


No, it tries to do your work.


In the golden age of RISC work the task of getting the maximum speed
was divided between the computer architecture and compiler guys
accoring to their capabilities. These fields seem to drift apart
again, with lots of parallel work, but maybe IA64 will reforge the
marriage.


Looking closely, though, we see that the hardware has better knowledge
of the actual situation (e.g., cache misses) and is not hindered by
scheduling boundaries such as procedure calls, wherease the compiler
can apply more sophisticated heuristics, and is not limited by an
N-entry instruction window and M-wide instruction fetcher. So,
although doing both hardware and compiler scheduling leads to some
redundant work, they still complement each other in some respects.


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

Return to the comp.compilers page.
Search the comp.compilers archives again.