optimal scheduling with spills

"Waleed M. Meleis" <waleed@eecs.umich.edu>
Sat, 24 Jun 1995 12:31:55 GMT

          From comp.compilers

Related articles
optimal scheduling with spills waleed@eecs.umich.edu (Waleed M. Meleis) (1995-06-24)
Re: optimal scheduling with spills davidm@flora.Rational.com (1995-06-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: "Waleed M. Meleis" <waleed@eecs.umich.edu>
Keywords: optimize, registers, question
Organization: Compilers Central
Date: Sat, 24 Jun 1995 12:31:55 GMT
Status: RO

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

Waleed Meleis waleed@eecs.umich.edu


Post a followup to this message

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