Re: Global Instruction Scheduling

David Chase <>
15 Mar 1998 15:56:04 -0500

          From comp.compilers

Related articles
Global Instruction Scheduling (David Gregg) (1998-03-15)
Re: Global Instruction Scheduling (David Chase) (1998-03-15)
| List of all articles for this month |

From: David Chase <>
Newsgroups: comp.compilers
Date: 15 Mar 1998 15:56:04 -0500
Organization: Natural Bridge LLC
References: 98-03-146
Keywords: architecture, optimize

> 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,

Post a followup to this message

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