Re: Register allocation and instruction scheduling

anton@mips.complang.tuwien.ac.at (Anton Ertl)
31 Jan 1999 01:15:11 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: Register allocation and instruction scheduling greened@zip.eecs.umich.edu (David A. Greene) (1999-01-19)
Re: Register allocation and instruction scheduling bob.morgan@digital.com (1999-01-20)
Re: Register allocation and instruction scheduling greened@zip.eecs.umich.edu (David A. Greene) (1999-01-22)
Re: Register allocation and instruction scheduling bob.morgan@digital.com (1999-01-25)
Re: Register allocation and instruction scheduling mikesw@whiterose.net (1999-01-27)
Re: Register allocation and instruction scheduling zalman@netcom.com (1999-01-27)
Re: Register allocation and instruction scheduling anton@mips.complang.tuwien.ac.at (1999-01-31)
Re: Register allocation and instruction scheduling adrian@dcs.rhbnc.ac.uk (1999-02-01)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 31 Jan 1999 01:15:11 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 99-01-055
Keywords: code, registers

  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


Post a followup to this message

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