Re: optimal scheduling with spills (David Moore)
Mon, 26 Jun 1995 15:53:34 GMT

          From comp.compilers

Related articles
optimal scheduling with spills (Waleed M. Meleis) (1995-06-24)
Re: optimal scheduling with spills (1995-06-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (David Moore)
Keywords: optimize, registers
Organization: Rational Software Corp
References: 95-06-064
Date: Mon, 26 Jun 1995 15:53:34 GMT

  "Waleed M. Meleis" <> 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.


Post a followup to this message

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