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 im- plement, fast, and effective with a demonstrated average code size improvement of 5.1% compared to the traditional tree decomposi- tion and tiling approach.

Published:

Download:

Paper:

• Near-Optimal Instruction Selection on DAGs (PDF)