Rethinking Code

Generation in
Compilers
Christian Schulte
KTH & SICS
Compilation
source back-end assembly

April 26, 2012

program front-end optimizer (code generator) program

Schulte, KTH & SICS

Rethinking Code Generation
Front-end: depends on source programming language
changes infrequently

Optimizer: independent optimizations

changes infrequently

Back-end: depends on processor architecture

2
changes often: new architectures, new features,
Building a Compiler
source back-end assembly

April 26, 2012

program front-end optimizer (code generator) program

Schulte, KTH & SICS

Rethinking Code Generation
LLVM

Infrequent changes: front-end & optimizer

reuse state-of-the-art: LLVM, for example

3
Building a Compiler
source back-end assembly

April 26, 2012

program front-end optimizer (code generator) program

Schulte, KTH & SICS

Rethinking Code Generation
Unison

Infrequent changes: front-end & optimizer

reuse state-of-the-art: LLVM, for example
Frequent changes: back-end
use flexible approach: Unison (this project) 4
State-of-the-art
instruction

April 26, 2012

selection

Schulte, KTH & SICS

Rethinking Code Generation
add r0 r1 r2
x = y + z;
mv $a6f0 r0

Code generation organized into stages

instruction selection,

5
State-of-the-art
register

April 26, 2012

allocation

x register r0

Schulte, KTH & SICS

Rethinking Code Generation
x = y + z; y memory (spill to stack)

Code generation organized into stages

instruction selection, register allocation,

6
State-of-the-art
instruction

April 26, 2012

scheduling

x = y + z; u = v w;

Schulte, KTH & SICS

Rethinking Code Generation

u = v w; x = y + z;

Code generation organized into stages

instruction selection, register allocation, instruction scheduling

7
State-of-the-art
instruction register instruction

April 26, 2012

selection allocation scheduling

Code generation organized into stages

Schulte, KTH & SICS

Rethinking Code Generation
instruction selection, register allocation, instruction scheduling
stages are interdependent: no optimal order possible

8
State-of-the-art
instruction instruction register

April 26, 2012

selection scheduling allocation

Code generation organized into stages

Schulte, KTH & SICS

Rethinking Code Generation
instruction selection, register allocation, instruction scheduling
stages are interdependent: no optimal order possible

9
State-of-the-art
instruction instruction register

April 26, 2012

selection scheduling allocation

Code generation organized into stages

Schulte, KTH & SICS

Rethinking Code Generation
instruction selection, register allocation, instruction scheduling
stages are interdependent: no optimal order possible

Stages use heuristic algorithms

for hard combinatorial problems
assumption: optimal solutions not possible anyway
difficult to take advantage of processor features
10
error-prone when adapting to change
State-of-the-art
instruction instruction register

April 26, 2012

selection scheduling allocation

Code generation organized into stages

Schulte, KTH & SICS

Rethinking Code Generation
instruction selection, register allocation, instruction scheduling
stages are interdependent: no optimal order possible

Stages use simple algorithmspreclude optimal code,

for hard combinatorial problems make development
assumption: optimal solutions not possible anyway
complex
difficult to take advantage of processor features
11
error-prone when adapting to change
Rethinking: Unison Idea
No more staging and heuristic algorithms!
many assumptions are several decades old...

April 26, 2012

Use state-of-the-art technology for solving combinatorial

Schulte, KTH & SICS

Rethinking Code Generation
optimization problems: constraint programming
tremendous progress in last two decades...

Generate and solve single model

captures all code generation tasks in unison
high-level of abstraction: based on processor description
flexible: ideally, just change processor description
potentially optimal: tradeoff between decisions accurately reflected
12
Constraint Programming
Model problem
variables and possible values problem parameters

April 26, 2012

constraints legal value combinations
objective function solution cost or quality

Schulte, KTH & SICS

Rethinking Code Generation
Modeling: turn problem into constraint model
high-level of abstraction
expressive and array of advanced modeling techniques available

Solving: find solution to constraint model

constraint propagation remove infeasible values
heuristic search simplify problem
13
Unison
instruction
constraint model
selection

April 26, 2012

constraints
input instruction
constraints
program scheduling
constraints

Schulte, KTH & SICS

Rethinking Code Generation
register
allocation

processor description

Generate constraint model

based on input program and processor description
constraints for all code generation tasks
generate but not solve: simpler and more expressive 14
Unison
instruction
constraint model
selection
off-the-shelf

April 26, 2012

constraints
input instruction constraint
constraints
program scheduling solver
constraints

Schulte, KTH & SICS

Rethinking Code Generation
register
allocation assembly
program
processor description

Off-the-shelf constraint solver solves constraint model

solution is assembly program
optimization takes inter-dependencies into account
15
Status
Advanced and novel models
register allocation

April 26, 2012

instruction scheduling
First attempts
instruction selection

Schulte, KTH & SICS

Rethinking Code Generation
Register allocation
several register banks (generalizing spilling to memory)
unifying coalescing and spilling
register packing
Instruction scheduling
full latency-based scheduling (including delay slots)
16
instruction bundling
Status
Advanced and novel models
register allocation

April 26, 2012

instruction scheduling
First attempts
instruction selection

Schulte, KTH & SICS

Rethinking Code Generation
notoriously difficult
we are proud
Register allocation
several register banks (generalizing spilling to memory)
unifying coalescing and spilling
register packing
Instruction scheduling
full latency-based scheduling (including delay slots)
17
instruction bundling
Status
Processor: simple RISC architecture (MIPS 32 bit)
compared to LLVM (state-of-the-art)

April 26, 2012

Benchmark: bzip2 (efficient compression tool)
part of SPECint 2006 benchmark suite

Schulte, KTH & SICS

Rethinking Code Generation
Code quality: on par

Robustness: scales to large functions (some 103 instructions)

use optimality preserving model decomposition

18
Status
Processor: simple RISC architecture (MIPS 32 bit)
compared to LLVM (state-of-the-art)

April 26, 2012

Benchmark: bzip2 (efficient compression tool)
part of SPECint 2006 benchmark suite

Schulte, KTH & SICS

Rethinking Code Generation
notoriously difficult
we are proud
Code quality: on par

Robustness: scales to large functions (some 103 instructions)

use optimality preserving model decomposition

19
Future
Complete model for instruction selection
yields complete constraint-based model

April 26, 2012

How to describe processor architectures?

Schulte, KTH & SICS

Rethinking Code Generation
Standard model improvements
tremendous scope

Mix of basic and applied research

Long (very long) term: establish idea as state-of-the-art

20
submit as open source to LLVM project (?)
Unison Fact Sheet
www.sics.se/projects/unison

April 26, 2012

People
Joe Armstrong Ericsson

Schulte, KTH & SICS

Rethinking Code Generation
Mats Carlsson SICS
Roberto Castaeda Lozano SICS
Frej Drejhammar SICS
Gabriel Hjort Blindell (from May 1st) KTH & SICS
Christian Schulte (lead) KTH & SICS

Funding
LM Ericsson AB SICS 2010 2013 21
Swedish Research Council (VR) KTH 2012 2014