Re: optimal scheduling with spills

  "Waleed M. Meleis" <waleed@eecs.umich.edu> writes:
> 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


Does it?


It is clear that the condition is not sufficient, but I don't think you
intended to imply that.


However, is it neccessary? What about this?




(a/b+(expression requiring n registers))


(where n is number of registers on machine)


Let us assume that the divide time is huge compared to anything
else including spills and fills. This is the case on many
machines, both old and new.


We therefore have to start the divide as early as possible. This
consumes a register so the remainder of the expression must be
evaluated in one less register. A spill must therefore occur.
However, this schedule is better than any schedule that avoids
a spill by evaluating (expression requiring n registers) since
the completion time is dependent entirely upon when we start
the divide.


--

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