optimal scheduling with spills

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
instructions


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
model? Thanks.


--
Waleed Meleis waleed@eecs.umich.edu


--

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