|optimal scheduling with spills email@example.com (Waleed M. Meleis) (1995-06-24)|
|Re: optimal scheduling with spills davidm@flora.Rational.com (1995-06-26)|
|From:||"Waleed M. Meleis" <firstname.lastname@example.org>|
|Keywords:||optimize, registers, question|
|Date:||Sat, 24 Jun 1995 12:31:55 GMT|
I have a technical question about algorithms that find optimal
schedules for expression trees. Here I assume that all arithmetic
load and store operations have the same cost, one operation can be
issued per time unit, and the number of registers is bounded.
Therefore the optimal schedule minimizes the number of load/store
In Sethi and Ullman (1970) and Aho and Johnson (1976) algorithms are
described that schedule an expression tree to minimize spill code.
They assume machine instructions of the form:
1. Ri <- Rj op Rk
2. Ri <- Rj op (mem)
3. Ri <- Load (mem)
4. Store (mem) <- Ri
where Rx refers to register x and (mem) refers to a memory location.
I'm interested in optimal schedules for a machine that does not have
instructions of type 2. It seems to me, and the literature implies,
that minor modifications of the above algorithms will still work. Can
anyone point me towards publications that consider such a machine
Waleed Meleis email@example.com
Return to the
Search the comp.compilers archives again.