Re: Global Instruction Scheduling

> Does anyone know about any heuristics or algorithms for global
> instruction scheduling that try not to schedule operations earlier
> than necessary. Ideally, the heuristic should avoid delaying the
> operation so much that it lengthens the schedule or causes it to be
> duplicated by being pushed below a branch.


I think Susan Eggers' group at U Washington has done some nice-looking
work in recent years, I think they call it "balanced scheduling".
Don't know if it actually works in a production compiler, but I recall
that they at least gave lip service to solving some of the problems
encountered by other people working on a production compiler.


There was also an interesting paper or two on scheduling that had
Barbara Simons as a co-author; I cannot remember the names of the
other authors (Barry Rosen, perhaps?) but I think it was supposed to
contain some good results.


One problem that you don't mention, that I don't recall if either
paper addressed, was register pressure. You'd like to think that this
could not possibly be a problem on a RISC, but that was pre-register
blocking and pre-software pipelining. Those both provide big
opportunities for scheduling, but also suck up registers like crazy.
--
David Chase, chase@world.std.com
--

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