Efficient instruction scheduling for a pipelined architecture (with retrospective)

Steven S. Muchnick, Phillip B. Gibbons

Abstract

As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.Previous algorithms for reducing pipeline interlocks have had worst-case runtimes of at least O(n4). By using a dag representation which prevents scheduling deadlocks and a selection method that requires no lookahead, the resulting algorithm reorganizes instructions almost as effectively in practice, while having an O(n2) worst-case runtime.
BibTeX
@inproceedings{muchnick1986efficient,
  author = {Steven S. Muchnick and Phillip B. Gibbons},
  title = {{Efficient instruction scheduling for a pipelined architecture (with retrospective)}},
  booktitle = {Best of PLDI},
  year = {1986},
  doi = {10.1145/989393.989413},
}

Loading related content...

Figure