Mon, 26 Jun 1995 15:53:34 GMT

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) |

Newsgroups: | comp.compilers |

From: | davidm@flora.Rational.com (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" <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.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.