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
