|
|
|
| | |
| Masters Thesis| [1] | Sebastian Buchwald, Andreas Zwinkau, Befehlsauswahl auf expliziten Abhängigkeitsgraphen, Universität Karlsruhe (TH), IPD Goos, Dec 2008.
|
AbstractPBQP (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.
Authors
| | | |
