With Sebastian Buchwald I have written my diploma thesis at the IPD Goos. The abstract:
PBQP (Partitioned Boolean Quadratic Problem) is a suitable optimization problem to model instruction selection. Such an instruction selection features direct processing of complex instruction patterns and a linear-time solving algorithm, which reduces an instruction selection problem to its core. However finding a PBQP-solution is NP-complete and was only empirically investigated in the context of instruction selection.
This thesis presents a formalization of the construction and solving of PBQP instruction selection for the verification of this technique. With two easily testable preconditions there is proof that solving can be guaranteed. With an implementation of an IA-32 instruction selection in libFirm requirements of a specification language were documented. The capabilities of this instruction selection were confirmed using the SPEC benchmark suite.
You can download it as pdf (german), likewise the presentation slides (german). For organizing your bib here is the article on CiteULike. To reference our work, please use the following bibtex:
@mastersthesis{Buchwald2008,
abstract = {Das PBQP (Partitioned Boolean Quadratic Problem) ist ein geeignetes Optimierungsproblem zur Modellierung einer Befehlsauswahl. Eine solche Befehlsauswahl zeichnet sich durch die direkte Verarbeitung komplexer Befehlsmuster und einen linearen L\"{o}sungsalgorithmus aus, der ein Befehlsauswahlproblem auf seinen Kern reduziert. Allerdings ist das Finden einer PBQP-L\"{o}sung NP-vollst\"{a}ndig und wurde im Rahmen der Befehlsauswahl bisher nur empirisch untersucht. Diese Arbeit gibt zur Verifikation des Verfahren eine Formalisierung f\"{u}r den Aufbau und die L\"{o}sung eines Befehlsauswahl-PBQP an. Mit zwei einfach pr\"{u}fbare Voraussetzungen wird gezeigt, dass eine L\"{o}sung garantiert werden kann. Anhand der Implementierung einer IA-32-Befehlsauswahl in libFirm wurden Anforderungen an eine Spezifikationssprache dokumentiert. Die Leistungsf\"{a}higkeit dieser Befehlsauswahl wurde mittels der SPEC-Testsammlung best\"{a}tigt.},
author = {Buchwald, Sebastian and Zwinkau, Andreas},
citeulike-article-id = {6095592},
citeulike-linkout-0 = {http://www.info.uni-karlsruhe.de/papers/da_buchwald_zwinkau.pdf},
keywords = {code-generation, compiler, firm, instruction-selection, pbqp},
month = {December},
posted-at = {2009-11-10 18:11:30},
priority = {0},
school = {Universit\"{a}t Karlsruhe (TH), IPD Goos},
title = {Befehlsauswahl auf expliziten Abh\"{a}ngigkeitsgraphen},
url = {http://www.info.uni-karlsruhe.de/papers/da_buchwald_zwinkau.pdf},
year = {2008}
}
qznc