Design of an SSA-based Register Allocator Register allocation is one of the most important optimizations in a modern compiler. It maps the variables of a program to the processor's registers in order to accelerate the program's execution. Graph coloring, as introduced by Chaitin, has been the most popular and most successful register allocation technique since its introduction in the late 1970s. It reduces the assignment problem to coloring the so-called interference graph that is constructed from the program to compile. Since graph coloring is NP-complete and each undirected graph can occur as an interference graph, register allocation is NP-complete, too. However, if we require the program to be in static single-assignment form (SSA), a widely used program representation, interference graphs are no longer general. As we will show, they belong to the class of chordal graphs. Their most appealing property is that they can be colored optimally in quadratic time. We show how these properties can be used to build efficient and effective allocators that work entirely under SSA. Furthermor, we present how constraints of architectures like the ia32 can be incorporated into such an allocator.