Philipp Klaus Krause

Teaching

[an error occurred while processing this directive]
WS 2014

Grundlagen der Informationsintegration

SS 2013

Tree Decomposition, Algorithms and Logic

WS 2013

Diskrete Modellierung

SS 2013

Graphstrukturtheorie im Übersetzerbau

WS 2012

Logik und Datenbanken

WS 2011

Baumzerlegungen, Algorithmen und Logik

SS 2011

Kombinatorische Spiele und diskrete Systeme

Übersetzerbau

WS 2010

Graphstruktur, Algorithmen und Logik

Perlen der theoretischen Informatik

SS 2010

Datenstrukturen

WS 2009

Baumzerlegungen, Algorithmen und Logik

SS 2009

Security Aspects of Embedded Systems

Publications

[an error occurred while processing this directive]

Register allocation

AVOS

ftc

Software

[an error occurred while processing this directive]
Graph theory

rank-width and -decomposition

linear nlc-width and -expressions

Programming tools

sdcc

Libraries and tools for the ColecoVision

Computer graphics

DSSIM

Contact

Theorie der Informatik

Isolde Adler

Philipp Klaus Krause

Register Allocation

I discovered a graph-coloring register allocator that optimally allocates registers for structured programs in polynomial time. It can handle register aliasing. The assignment of registers is optimal with respect to spill and rematerialization costs, register preferences and coalescing. The register allocator is not restricted to programs in SSA form or chordal interference graphs. It requires the input program to be structured, which is automatically true for many programming languages and for others, such as C, is equivalent to a bound on the number of goto labels per function. The number of registers is assumed to be fixed. Non-structured programs can be handled at the cost of either a loss of optimality or an increase in runtime.

I implemented a prototype, which is already the default register allocator in the Z80, Z180, Rabbit 2000/3000, Rabbit 3000A, LR35902 (Gameboy CPU), HC08 and S08 backends of sdcc, a cross-compiler for embedded systems.

Significant improvements in runtime over my approach are unlikely, since I found proof that optimal register allocation for structured programs is W[SAT]-hard, even for programs of tree-width 2.

Publications

CC 2013 “Optimal Register Allocation in Polynomial Time”

Describes the XP algorithm.

Preprint

DAM “The Complexity of Register Allocation”

Contains the W[SAT]-hardness proof.

Preprint

This preprint version is mostly identical to the final version. The only difference is that the preprint uses notation that I prefer and is consistent with the CC 2013 paper above, while the published version uses notation that one reviewer prefered.