Link to CALCM Home  

Near-Optimal Instruction Selection for Resource Constrained Embedded Architectures

Tuesday October 16, 2007
Hamerschlag Hall D-210
4:30 pm

Dave Koes
Carnegie Mellon University

Code size, although often ignored in the workstation space, is an important optimization goal when targeting embedded processors. Embedded designs often have a small, fixed amount of on-chip memory to store and execute code with. A small difference in code size could necessitate a costly redesign. Instruction selection is an important part of code size optimization since the instruction selector is responsible for effectively exploiting the complexity of the target instruction set.

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 demonstrated average code size improvements of up to 9.5%.

Dave doesn't think computers are fast enough or that compilers are good enough. After working as a compiler writer for Green Hills Software in dreary Santa Barbara, CA, he entered grad school in an attempt to remedy that situation. He is an Nth year graduate student in the computer science department with a thesis topic on the principled integration of register allocation and instruction selection in a progressive backend optimizer. There is a high probability that cookies will be provided at his talk and an even higher probability that his presentation will contain an above average number of baby pictures. His advisor is Seth Goldstein.


Department of Electrical and Computer EngineeringCarnegie Mellon UniversitySchool of Computer Science