HOME | ENGLISH | IMPRESSUM | KIT

Konferenzartikel: Instruction Selection by Graph Transformation

[buchwald10cases]Sebastian Buchwald, Andreas Zwinkau, Instruction Selection by Graph Transformation, Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems, pp. 31--40, ACM, New York, NY, USA, October 2010.

Zusammenfassung

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.

Download

  [PDF]   [DOI]

BibTeX

Institutsinterne Autoren

Wissenschaftliche Mitarbeiter
Sebastian Buchwald
Andreas Zwinkau

Projekte

Projekt
libFirm