Linear-time, Optimal Code Scheduling for Delayed-Load Architectures

Todd A. Proebsting, Charles N. Fischer

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


A fast, optimal code scheduling algorithm for processors with a delayed lo,ad of 1 instruction cycle is described. The algorithm minimizes both execution time and register use and runs in time proportional to the size of the expression tree. Extensions that spill registers when too few are available are also presented. The algorithm also performs very well for delayed loads of greater than 1 instruction cycle. For machines with load delays greater than 1, bounds are given for the minimal number of registers needed for optimally evaluating an expression tree.

Original languageEnglish (US)
Pages (from-to)256-267
Number of pages12
JournalSIGPLAN Notices (ACM Special Interest Group on Programming Languages)
Issue number6
StatePublished - Jan 5 1991

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Linear-time, Optimal Code Scheduling for Delayed-Load Architectures'. Together they form a unique fingerprint.

Cite this