@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},
}