Near-Optimal Instruction Selection on DAGs

 

In Proceedings of the International Symposium on Code Generation and Optimization (CGO'08)

David Ryan Koes and Seth Copen Goldstein

Washington, DC, USA

2008

Abstract


download pdf


@inproceedings{koes-cgo08,
  author = {Koes, David Ryan and Goldstein, Seth Copen},
  title = {Near-Optimal Instruction Selection on {DAG}s},
  booktitle = {Proceedings of the International Symposium on Code
     Generation and Optimization {(CGO'08)}},
  year = {2008},
  keywords = {Compilers:Instruction Selection},
  abstract = {Instruction selection is a key component of code
     generation. High quality instruction selection is of particular
     importance in the embedded space where complex instruction sets
     are common and code size is a prime concern. Although instruction
     selection on tree expressions is a well understood and easily
     solved problem, instruction selection on directed acyclic graphs
     is NP-complete. In this paper we present NOLTIS, a near-optimal,
     linear time instruction selection algorithm for DAG expressions.
     NOLTIS is easy to implement, fast, and effective with a
     demonstrated average code size improvement of 5.1\% compared to
     the traditional tree decomposition and tiling approach.},
  publisher = {IEEE Computer Society},
  url = {http://www.cs.cmu.edu/~seth/papers/koes-cgo08.pdf},
  address = {Washington, DC, USA}
}

Related Papers

Compilers:Instruction Selection
Near-Optimal Instruction Selection on DAGs
David Ryan Koes and Seth Copen Goldstein. In Proceedings of the International Symposium on Code Generation and Optimization (CGO'08), 2008.


Back to publications list