KIT | KIT-Bibliothek | Impressum | Datenschutz

Instruction Selection by Graph Transformation

Buchwald, Sebastian; Zwinkau, Andreas

Common generated instruction selections are based on tree pattern matching, but modern and custom architectures feature instructions, which cannot be covered by trees. To overcome this limitation, we are the first to employ graph transformation, the natural generalization of tree rewriting. Currently, the only approach allowing us to pair graph-based instruction selection with linear time complexity is the mapping to the Partitioned Boolean Quadratic Problem (PBQP). We present formal foundations to verify this approach and therewith identify two problems of the common method and resolve them. We confirm the capabilities of PBQP-based instruction selection by a comparison with a finely-tuned hand-written instruction selection.

DOI: 10.1145/1878921.1878926
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Proceedingsbeitrag
Jahr 2010
Sprache Englisch
Identifikator ISBN: 978-1-60558-903-
KITopen-ID: 1000027785
Erschienen in Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems, October 24 - 29, 2010, Scottsdale, Arizona, USA
Verlag ACM, New York (NY)
Seiten 31-40
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page