1 of 257

Register Allocation ( + Liveness, Dead code Elimination)

Note: newish-material�If something seems like a bug, it probably is…ask questions.

2 of 257

// rdi = load_local 0

// rdi = assert_integer rdi

call assert_integer

mov %rax %rdi

// rdi = get_integer rdi

call get_integer

mov %rax %rdi�

// rax = sub_const rdi 2

sub $2 %rdi

call new_integer

//return rax

// load_local 0

push %rdi�

// assert_integer

pop %rdi

call assert_integer

push %rax

// get_integer

pop %rdi

call get_integer

push %rax

// sub_const_2 2

pop %rdi

sub $2 %rdi

call new_integer

push %rax

// return

pop %rax

push %r12

mov <Address of Constants> %r12

// load_local 0

push %rdi

�// dup

pop %rax

push %rax

push %rax�

// assert_integer

pop %rdi

call assert_integer

// get_integer

pop %rdi

call get_integer

push %rax��// load_const 1

Mov 8(%r12) %rdx

push %rdx

�// dup

pop %rax

push %rax

�// assert_integer

pop %rdi

call assert_integer

// get_integer

pop %rdi

call get_integer

push %rax

// sub

pop %rcx

pop %rdi

sub %rcx %rdi

call new_integer

push %rax

// ret

pop %rax

push %r12

mov <Address of Constants> %r12

push %r13

push %r14

�// load_local 0

push %rdi

// load_const 1

mov 8(%r12) %rdx

push %rdx

�// Pop right op (Value *)

pop %r13

// Check right op is integer

mov %r13 %rdi

call assert_integer

// Load right op value (2)

mov %r13 %rdi

call get_integer

mov %rax %r13

// Pop left op y

pop %r14

// Check left op is integer

mov %r14 %rdi

call assert_integer

// Load left op value (y)

mov %r14 %rdi�call get_integer

mov %rax %rdi

sub %r13 %rdi

call new_integer

push %rax

// ret

pop %rax

pop %r14

pop %r13

pop %r12

Instructions: 25

Instructions: 24

Instructions: 13

Instructions: 7

Mem: 12

Mem: 18

Mem: 9 (stack) + 1 (object)

Mem: 2 (stack) + 2 (object)

Alloc: 1

Original

Exposed IR Ops

Type and Value Analysis

Register Allocation

Numbers need update!

3 of 257

Unoptimized Code Generation

// load_local 0

push %rdi

// load_const 1

mov 8(%r12) %rdx

push %rdx

�// Pop right op (Value *)

pop %r13

// Check right op is integer

mov %r13 %rdi

call assert_integer

// Load right op value (2)

mov %r13 %rdi

call get_integer

mov %rax %r13

// Pop left op y

pop %r14

// Check left op is integer

mov %r14 %rdi

call assert_integer

// Load left op value (y)

mov %r14 %rdi�call get_integer

mov %rax %rdi

sub %r13 %rdi

call new_integer

push %rax

// ret

pop %rax

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

sub

return

]

}

4 of 257

Type Analysis

// load_local 0

push %rdi�

// assert_integer

pop %rdi

call assert_integer

push %rax

// get_integer

pop %rdi

call get_integer

push %rax

�// load_const 1

mov 8(%r12) %rdx

push %rdx

// get_integer

pop %rdi

call get_integer

push %rax

// sub

pop %rcx

pop %rdi

sub %rcx %rdi

call new_integer

push %rax

// ret

pop %rax

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

5 of 257

Value Analysis

// load_local 0

push %rdi�

// assert_integer

pop %rdi

call assert_integer

push %rax

// get_integer

pop %rdi

call get_integer

push %rax

// get_integer 2

push $2

// sub

pop %rcx

pop %rdi

sub %rcx %rdi

call new_integer

push %rax

// ret

pop %rax

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

get_integer 2

sub

return

]

}

6 of 257

Value Analysis

// load_local 0

push %rdi�

// assert_integer

pop %rdi

call assert_integer

push %rax

// get_integer

pop %rdi

call get_integer

push %rax

// sub_int32_const 2

pop %rdi

sub $2 %rdi

call new_integer

push %rax

// return

pop %rax

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

7 of 257

Stack Caching

�

push %r13

// r13 = load_local 0

mov %rdi %r13

// r13 = assert_integer r13

mov %r13 %rdi

call assert_integer

mov %rax %r13

// r13 = get_integer r13

mov %r13 %rdi

call get_integer

mov %rax %r13��// r13 = sub_const_2 r13 2

sub $2 %r13

mov %r13 %rdi

call new_integer

mov %rax %r13

// return r13

mov %r13 %rax

pop %r13

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

r13 = get_integer r13

r13 = sub_int32 r13 2

return r13

]

}

8 of 257

Register �Allocation

// rdi = load_local 0

// rdi = assert_integer rdi

call assert_integer

mov %rax %rdi

// rdi = get_integer rdi

call get_integer

mov %rax %rdi�

// rax = sub_const rdi 2

sub $2 %rdi

call new_integer

//return rax

push %r13

// r13 = load_local 0

mov %rdi %r13

// r13 = assert_integer r13

mov %r13 %rdi

call assert_integer

mov %rax %r13

// r13 = get_integer r13

mov %r13 %rdi

call get_integer

mov %rax %r13

�// r13 = sub_const_2 r13 2

sub $2 %r13

mov %r13 %rdi

call new_integer

mov %rax %r13

// return r13

mov %r13 %rax

pop %r13

New

Old

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

rdi = load_local 0

rdi = assert_integer rdi

rdi = get_integer rdi

rax = sub_int32 rdi 2

return rax

]

}

9 of 257

Value Analysis (Constant Propagation)

We statically know the value of a constant.

We do we need to load it dynamically? Nope!

A static analysis to statically reason about values

Idea: statically simulate execution of program�and keep track of what values are known �and which aren’t.

Various levels of precision: exact values, �signs, range

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

10 of 257

Intermediate Representation (Illustrative)

Types

Integer, Bool, String, .. Etc
New Types

int32 – a primitive integer value (sometimes called unboxed vs boxed above)

Instructions

load_local <op 0>,load_const <op 0>, sub, return, …
New Instructions

assert_integer - pops argument of the task, checks type, places it back if successful. Otherwise, fail (exit or exception)
get_integer – pops integer argument off the stack, push int32 value back on the stack. Doesn’t check the type of argument. Behavior undefined if argument not int32
sub_int32 – pops two int32 arguments off the stack, pushes Integer result back onto the stack. Doesn’t check types of arguments. Behavior undefined if arguments not int32
get_integer <constant> - pushes the int32 value of the constant onto the stack

11 of 257

Value Analysis

Stack

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

12 of 257

Value Analysis

Stack
?

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

13 of 257

Value Analysis

Stack
?

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

14 of 257

Value Analysis

Stack
?

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

15 of 257

Value Analysis

Stack
?
2

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

16 of 257

Value Analysis

Stack
?
2

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer 2

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

17 of 257

Value Analysis

Stack
?
2

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

get_integer 2

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

The load_const is dead code

18 of 257

Value Analysis

Stack
?

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

get_integer 2

sub_int32

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

19 of 257

Value Analysis

Stack

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

get_integer 2

sub_int32

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

load_const 1

get_integer

sub_int32

return

]

}

20 of 257

Intermediate Representation (Illustrative)

Operands

Constants (1, 2, 4, 3)
Registers (r1, r2, …) (finite set according to ISA)
Virtual Registers (aka, “Temporaries”) (t1, t2, …)

Types

Integer, Bool, String, .. Etc
New Types

int32 – a primitive integer value (sometimes called unboxed vs boxed above)

Instructions

Simple “three address code” or register transfer language (RTL)
<r|t> = load_local <op 0>, <r|t> = load_const <op 0>
<r|t> = assert_integer <operand>
<r|t> = get_integer <operand>
<r|t> = sub_int32 <operand> <operand>

21 of 257

Last Time (How?)

Type Analysis

Value Analysis

Register Allocation

- Stack Caching

22 of 257

Intermediate Representation (Illustrative)

Operands

Constants (1, 2, 4, 3)
Registers (r1, r2, …) (finite set according to ISA)
Virtual Registers (aka, ”Temporaries”) (t1, t2, …)

Types

Integer, Bool, String, .. Etc
New Types

int32 – a primitive integer value (sometimes called unboxed vs boxed above)

Instructions

Simple “three address code” or register transfer language (RTL)

Op <register>
<register> = op
<register> = opcode <operand>
<register> = opcode <operand> <operand>

<register> = load_local <op 0>, <register> = load_const <op 0>
<register> = assert_integer <operand>
<register> = get_integer <operand>
<register> = sub_int32 <operand> <operand>

23 of 257

Stack to Three-Address Code

Stack
t1

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

]

}

(Code after Type and Constant Analysis)

24 of 257

Stack to Three-Address Code

Stack
t1

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

]

}

25 of 257

Stack to Three-Address Code

Stack
t2

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

26 of 257

Stack to Three-Address Code

Stack
t3

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

27 of 257

Stack to Three-Address Code

Stack
t4

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = sub_int32 t3 2

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

28 of 257

Stack to Three-Address Code

Stack

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = sub_int32 t3 2

return t4

]

}

29 of 257

Virtual Machine Showdown: Stack Versus Registers

Yunhe Shi, David Gregg, Andrew Beatty, and M. Anton Ertl

Which is a better virtual machine specification?

Representation size, performance, etc

Translations and Optimizations

Copy Propagation
Dead code elimination

30 of 257

Constant Propagation

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = load_const 1

t5 = get_integer t4

t6 = sub_int32 t3 t5

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = 2

t5 = get_integer t4

t6 = sub_int32 t3 t5

return

]

}

31 of 257

Constant Propagation

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = load_const 1

t5 = get_integer t4

t6 = sub_int32 t3 t5

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = 2

t5 = get_integer 2

t6 = sub_int32 t3 2

return

]

}

32 of 257

Dead Code

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = load_const 1

t5 = get_integer t4

t6 = sub_int32 t3 t5

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = 2

t5 = get_integer 2

t6 = sub_int32 t3 2

return

]

}

Neither t4 or t5 are live. Alternatively, they are dead.

33 of 257

Dead Code

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = load_const 1

t5 = get_integer t4

t6 = sub_int32 t3 t5

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t6 = sub_int32 t3 2

return

]

}

Neither t4 or t5 are live. Alternatively, they are dead.

34 of 257

Liveness Analysis

A variable v is live at point p if

v is used along some path starting at p, and
no definition of v along the path before the use.

When is a variable v dead at point p?

No use of v on any path from p to exit node, or
If all paths from p redefine v before using v.

Uses:

Dead code elimination
Computing interference between variables (webs) for register allocation

35 of 257

Conceptual Idea of Analysis

Simulate execution
But start from exit and go backwards in CFG
Compute liveness information from end to beginning of basic blocks

36 of 257

Liveness Example

a = x+y;

t = a;

c = a+x;

x == 0

b = t+z;

c = y+1;

1 1 0 0 1 0 0

1 1 1 0 0 0 0

Assume a,b,c visible outside method
So are live on exit
Assume x,y,z,t not visible
Represent Liveness Using Bit Vector

order is abcxyzt

1 1 0 0 1 1 1

1 0 0 0 1 1 1

1 1 0 0 1 0 0

0 1 0 1 1 1 0

a b c x y z t

37 of 257

Liveness as Dataflow

Facts (bitvectors)
Transfer functions (DEF, USE)
Join operators (union)

111

011

101

110

010

001

000

100

P = { 000, 001, 010, 011, 100, 101, 110, 111}

(standard boolean lattice, also called hypercube)

38 of 257

Transfer functions

Each basic block has

IN – the set of variables live at start of block
OUT - the set of variables live at end of block
USE - the set of variables with upwards exposed uses in block
DEF - the set of variables defined in block

USE[x = z; x = x+1;] = { z }
DEF[x = z; x = x+1;y = 1;] = {x, y}
Compiler scans each basic block to derive USE and DEF sets

Saman Amarasinghe 38 6.035 ©MIT Fall 1998

39 of 257

Liveness Algorithm

for all nodes n in N - { Exit }

IN[n] = emptyset;

OUT[Exit] = emptyset;

IN[Exit] = use[Exit];

Changed = N - { Exit };

while (Changed != emptyset)

choose a node n in Changed;

Changed = Changed - { n };

OUT[n] = emptyset;

for all nodes s in successors(n)

OUT[n] = OUT[n] U IN[p];

IN[n] = use[n] U (out[n] - def[n]);

if (IN[n] changed)

for all nodes p in predecessors(n)

Changed = Changed U { p };

40 of 257

Register Allocation

Credit: CS143 @ Stanford

41 of 257

The Memory Hierarchy

●

Idea: Try to get the best of all worlds by using multiple types of memory.

42 of 257

The Memory Hierarchy

●

Idea: Try to get the best of all worlds by using multiple types of memory.

Registers

L1 Cache

L2 Cache

Main Memory

Hard Disk

Network

43 of 257

The Memory Hierarchy

●

Idea: Try to get the best of all worlds by using multiple types of memory.

L1 Cache

L2 Cache

Main Memory

Hard Disk

Network

256B - 8KB

16KB – 64KB

1MB - 4MB

4GB – 256GB

500GB+

HUGE

Registers

44 of 257

The Memory Hierarchy

●

Idea: Try to get the best of all worlds by using multiple types of memory.

L1 Cache

L2 Cache

Main Memory

Hard Disk

Network

256B - 8KB

16KB – 64KB

1MB - 4MB

4GB – 256GB 25ns – 100ns

500GB+

HUGE

0.25 – 1ns

1ns – 5ns 5ns – 25ns

3 – 10ms

10 – 2000ms

Registers

45 of 257

The Challenges of Code Generation

●

Almost all programming languages expose a coarse view of the memory hierarchy:

●

All variables live in “memory.”

Disk and network explicitly handled separately.

●

(Interesting exception: Stanford's Sequoia

programming language)

Challenges in code generation:

●

Position objects in a way that takes maximum advantage of the memory hierarchy.

Do so without hints from the programmer.

●

46 of 257

Registers

●

Most machines have a set of registers, dedicated memory locations that

●

can be accessed quickly,

can have computations performed on them, and exist in small quantity.

●

Using registers intelligently is a critical step in any compiler.

●

A good register allocator can generate code orders of magnitude better than a bad register allocator.

47 of 257

Register Allocation

●

On a physical machine there are a small number of registers:

●

amd64 has 16 general-purpose registers and a number of specialized registers.

●

Register allocation is the process of assigning variables to registers and managing data transfer in and out of registers.

48 of 257

Challenges in Register Allocation

●

Registers are scarce.

●

Often substantially more IR variables than registers. Need to find a way to reuse registers whenever possible.

●

Registers are complicated.

●

x86: Certain instructions must store their results in specific registers; can't store values there if you want to use those instructions.

Most architectures: Some registers must be preserved across function calls.

●

49 of 257

Stack Caching

A simple form of register allocation
Idea: rather than using the stack to store temporaries, use registers

For each stack slot, use a specific register instead

50 of 257

Stack Caching

Stack

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

]

}

51 of 257

Stack Caching

Stack
r13

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

]

}

52 of 257

Stack Caching

Stack
r13

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

]

}

53 of 257

Stack Caching

Stack
r13

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

r13 = get_integer r13

]

}

54 of 257

Stack Caching

Stack
r13

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

r13 = get_integer r13

r13 = sub_int32 r13 2

]

}

55 of 257

Stack Caching

Stack

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

r13 = get_integer r13

r13 = sub_int32 r13 2

return r13

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

56 of 257

Sub optimal

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

r13 = get_integer r13

r13 = sub_int32 r13 2

return r13

]

}

push %r13

// r13 = load_local 0

mov %rdi %r13

// r13 = assert_integer r13

mov %r13 %rdi

call assert_integer

mov %rax %r13

// r13 = get_integer r13

mov %r13 %rdi

call get_integer

mov %rax %r13

�// r13 = sub_const_2 r13 2

sub $2 %r13

mov %r13 %rdi

call new_integer

mov %rax %r13

// return r13

mov %r13 %rax

pop %r13

57 of 257

Sub optimal

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

r13 = load_local 0

r13 = assert_integer r13

r13 = get_integer r13

r13 = sub_int32 r13 2

return r13

]

}

push %r13

// r13 = load_local 0

mov %rdi %r13

// r13 = assert_integer r13

mov %r13 %rdi

call assert_integer

mov %rax %r13

// r13 = get_integer r13

mov %r13 %rdi

call get_integer

mov %rax %r13

�// r13 = sub_const_2 r13 2

sub $2 %r13

mov %r13 %rdi

call new_integer

mov %rax %r13

// return r13

mov %r13 %rax

pop %r13

58 of 257

Constrained Optimization Problem

Assumptions:

local_local 0 is in register rdi

Constraints:

assert_integer: t1 in rdi

get_integer: t2 in rdi

sub: t3 in rdi

return: t4 in rax

Minimize Cost:

- Memory accesses

- Instructions (register to register moves)

Solution (Register Assignment):

t1 in rdi

t2 in rdi

t3 in rdi

t4 in rax

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = sub_int32 t3 2

return t4

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

rdi = load_local 0

rdi = assert_integer rdi

rdi = get_integer rdi

rax = sub_int32 rdi 2

return rax

]

}

59 of 257

Code

// rdi = load_local 0

// rdi = assert_integer rdi

call assert_integer

mov %rax %rdi

// rdi = get_integer rdi

call get_integer

mov %rax %rdi�

// rax = sub_const rdi 2

sub $2 %rdi

call new_integer

//return rax

push %r13

// r13 = load_local 0

mov %rdi %r13

// r13 = assert_integer r13

mov %r13 %rdi

call assert_integer

mov %rax %r13

// r13 = get_integer r13

mov %r13 %rdi

call get_integer

mov %rax %r13

�// r13 = sub_const_2 r13 2

sub $2 %r13

mov %r13 %rdi

call new_integer

mov %rax %r13

// return r13

mov %r13 %rax

pop %r13

New

Old

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

rdi = load_local 0

rdi = assert_integer rdi

rdi = get_integer rdi

rax = sub_int32 rdi 2

return rax

]

}

60 of 257

Goal

Explore two algorithms for register allocation:

Linear scan register allocation.

Graph-coloring register allocation.

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = sub_int32 t3 2

return t4

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_int32_const 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

rdi = load_local 0

rdi = assert_integer rdi

rdi = get_integer rdi

rax = sub_int32 rdi 2

return rax

]

}

61 of 257

Building a Better Allocator

●

Goal: Try to hold as many variables in registers as possible.

●

Reduces memory reads/writes. Reduces total memory usage.

●

We will need to address these questions:

●

Which registers do we put variables in? What do we do when we run out of registers?

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

d = e + f

d = e – f

g = d

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

67 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

d = e + f

d = e – f

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ g }

68 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

d = e + f

d = e – f

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

69 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

d = e + f

{ d }

d = e – f

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

70 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

{ e, f } d = e + f

{ d }

d = e – f

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

71 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

{ e, f } d = e + f

{ d }

d = e – f

{ d }

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

72 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

73 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

74 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

75 of 257

Live Ranges and Live Intervals

e = d + a

f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e = d + a

f = b + c f = f + b

IfZ e Goto _L0 d = e + f Goto _L1;

_L0:

d = e - f

_L1:

g = d

{ d }

g = d

{ g }

76 of 257

Live Ranges and Live Intervals

e = d + a

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e	=	d	+	a
f	=	b	+	c
f	=	f	+	b
IfZ		e	Goto		_L0
d =		e	+ f

{ d }

g = d

{ g }

Goto _L1;

_L0:

d = e - f

_L1:

g = d

77 of 257

Live Ranges and Live Intervals

e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e	=	d	+	a
f	=	b	+	c
f	=	f	+	b
IfZ		e	Goto		_L0
d =		e	+ f

{ d }

g = d

{ g }

Goto _L1;

_L0:

d = e - f

_L1:

g = d

78 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e	=	d	+	a
f	=	b	+	c
f	=	f	+	b
IfZ		e	Goto		_L0
d =		e	+ f

{ d }

g = d

{ g }

Goto _L1;

_L0:

d = e - f

_L1:

g = d

79 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e	=	d	+	a
f	=	b	+	c
f	=	f	+	b
IfZ		e	Goto		_L0
d =		e	+ f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

{ d }

g = d

{ g }

80 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }


e = d + a
e = d + a
f = b + c
f = f + b
IfZ e Goto _L0
d = e + f
Goto _L1;
_L0:
d = e - f
_L1:
g = d

{ d }

g = d

{ g }

a

81 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a b

e = d + a

{ d }

g = d

{ g }

f = b + c

f = f + b

IfZ e Goto _L0

d = e + f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

82 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a b c

e = d + a

{ d }

g = d

{ g }

f = b + c

f = f + b

IfZ e Goto _L0

d = e + f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

83 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a b c d

e = d + a

{ d }

g = d

{ g }

f = b + c

f = f + b

IfZ e Goto _L0

d = e + f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

84 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a b c d

e = d + a

{ d }

g = d

{ g }

f = b + c

f = f + b

IfZ e Goto _L0

d = e + f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

85 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a b c d e

e = d + a

{ d }

g = d

{ g }

f = b + c

f = f + b

IfZ e Goto _L0

d = e + f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

86 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

e = d + a

{ d }

g = d

{ g }

f = b + c

f = f + b

IfZ e Goto _L0

d = e + f

d = e - f

Goto _L1;

_L0:

_L1:

g = d

a b c d e f

87 of 257

Live Ranges and Live Intervals

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a b c d e f g


e = d + a
e = d + a
f = b + c
f = b + c
f = f + b
f = f + b
IfZ e Goto _L0
d = e + f
Goto _L1;
_L0:
d = e - f
d = e - f
_L1:
g = d
g = d

{ d }

g = d

{ g }

88 of 257

Register Allocation with Live Intervals

●

Given the live intervals for all the variables in the program, we can allocate registers using a simple greedy algorithm.

Idea: Track which registers are free at each point.

When a live interval begins, give that variable a free register.

When a live interval ends, the register is once again free.

We can't always fit everything into a register; we'll see what do to in a minute.

●

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

3 registers instead of 4

105 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

106 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

107 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

108 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

109 of 257

Another Example

R₀	R₁	R₂

Free Registers

What do we do now?

a

_b _c _d _e _f _g

110 of 257

Register Spilling

●

If a register cannot be found for a variable v, we may need to spill a variable.

When a variable is spilled, it is stored in memory rather than a register.

When we need a register for the spilled variable:

●

Evict some existing register to memory. Load the variable into the register.

When done, write the register back to memory and reload the register with its original value.

●

Spilling is slow, but sometimes necessary.

111 of 257

Another Example

R₀	R₁	R₂

Free Registers

What do we do now?

a

_b _c _d _e _f _g

112 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

113 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

114 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

115 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

116 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

117 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

118 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

119 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

120 of 257

Another Example

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

121 of 257

Linear Scan Register Allocation

●

This algorithm is called linear scan register allocation

and is a comparatively new algorithm (1999).

Advantages:

●

Very efficient (after computing live intervals, runs in linear time)

Produces good code in many instances.

Allocation step works in one pass; can generate code during iteration.

Often used in JIT compilers like Java HotSpot.

●

Disadvantages:

●

Imprecise due to use of live intervals rather than live ranges. Other techniques known to be superior in many cases.

●

122 of 257

Correctness Proof Sketch

Live intervals are conservative approximations of live ranges.

No two variables with overlapping live ranges placed in the same register.

●

No register holds two live variables at once:

●

At each program point, every variable is in the same location:

●

All variables assigned a unique location.

123 of 257

Second-Chance Bin Packing

●

A more aggressive version of linear-scan. Uses live ranges instead of live intervals.

If a variable must be spilled, don't spill all uses of it.

●

A later live range might still fit into a register.

●

Requires a final data-flow analysis to confirm variables are assigned consistent locations.

See “Quality and Speed in Linear-scan Register Allocation” by Traub, Holloway, and Smith.

●

124 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

125 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

126 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

127 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

128 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

129 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

130 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

131 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

132 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

133 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

134 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

135 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

136 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

137 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

138 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

139 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

140 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

141 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

142 of 257

Second-Chance Bin Packing

R₀	R₁	R₂

Free Registers

a

_b _c _d _e _f _g

143 of 257

An Entirely Different Approach

144 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

g = d

{ g }

145 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

What can we infer from all these variables being live at this point?

{ d }

g = d

{ g }

146 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

g = d

{ g }

147 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a

b

c

d

e

f

g

{ d }

g = d

{ g }

148 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a

b

c

d

e

f

g

{ d }

g = d

{ g }

149 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a

b

c

d

e

f

g

{ d }

g = d

{ g }

150 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a

b

c

d

e

f

g

{ d }

g = d

{ g }

151 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a

b

c

d

e

f

g

R₀	R₁	R₂	R₃

{ d }

g = d

{ g }

Registers

152 of 257

An Entirely Different Approach

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

a

b

c

d

e

f

g

R₀	R₁	R₂	R₃

{ d }

g = d

{ g }

Registers

153 of 257

The Register Interference Graph

●

The register interference graph (RIG) of a control-flow graph is an undirected graph where

●

Each node is a variable.

There is an edge between two variables that are live at the same program point.

●

Perform register allocation by assigning each variable a different register from all of its neighbors.

There's just one catch...

●

154 of 257

The One Catch

This problem is equivalent to graph- coloring, which is NP-hard if there are at least three registers.

No good polynomial-time algorithms (or even good approximations!) are known for this problem.

Not quite. Polynomial for static single assignment form programs.

We have to be content with a heuristic that is good enough for RIGs that arise in practice.

●

155 of 257

The One Catch to The One Catch

156 of 257

The One Catch to The One Catch

If you can figure out a way to assign registers to arbitrary RIGs, you've just proven P = NP and will get a $1,000,000 check from the Clay Mathematics Institute.

157 of 257

The One Catch to The One Catch

If you can figure out a way to assign registers to arbitrary RIGs, you've just proven P = NP and will get a $1,000,000 check from the Clay Mathematics Institute.

158 of 257

Battling NP-Hardness

159 of 257

Chaitin's Algorithm (1982)

Suppose we are trying to k-color a graph and find a node with fewer than k edges.

If we delete this node from the graph and color what remains, we can find a color for this node if we add it back in.

Reason: With fewer than k neighbors, some color must be left over.

●

a

b

c

d

e

g

f

c

Registers

165 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

c

Registers

166 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

c

Registers

167 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

b c

Registers

168 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

b c

Registers

169 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

b c

Registers

170 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

d b c

Registers

171 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

d b c

Registers

172 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

Registers

173 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

a

Registers

174 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

g a

Registers

175 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

f g a

Registers

176 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

g a

Registers

177 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

g a

Registers

178 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

a

Registers

179 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

a

Registers

180 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

Registers

181 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

e d b c

Registers

182 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

d b c

Registers

183 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

d b c

Registers

184 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

b c

Registers

185 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

b c

Registers

186 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

c

Registers

187 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

c

Registers

188 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

Registers

189 of 257

Chaitin's Algorithm

R₀	R₁	R₂	R₃

a

b

c

d

e

g

f

Registers

190 of 257

One Problem

What if we can't find a node with fewer than k neighbors?

Choose and remove an arbitrary node, marking it “troublesome.”

Otherwise, we have to spill that node.

●

Use heuristics to choose which one.

●

When adding node back in, it may be possible to find a valid color.

191 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

a

b

c

d

e

f

g

Registers

<- Note 3 registers this time rather than 4

192 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

a

b

c

d

e

f

g

Registers

g

193 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

c

d

e

f g

Registers

g

194 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

e

f

a

b

c

d

e f g

Registers

g

195 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

d

e

f

a

b

c

d e f g

Registers

g

196 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

c d e f g

Registers

g

197 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

b c d e f g

g

Registers

198 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

a b c d e f g

g

Registers

199 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

b c d e f g

g

Registers

200 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

b c d e f g

g

Registers

201 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

c d e f g

g

Registers

202 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

c

d

e

f

a

b

c d e f g

g

Registers

203 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

d

e

f

a

b

d e f g

g

c

Registers

204 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

d

e

f

a

b

d e f g

g

c

Registers

205 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

d

e

f

a

b

e f g

g

c

Registers

206 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

d

e

f

a

b

e f g

g

c

Registers

207 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

e

f

a

b

e f g

g

d

c

Registers

(spilled)

208 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

f g

g

d

c

e

(spilled)

Registers

209 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

f g

g

d

c

e

(spilled)

Registers

210 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

g

d

c

e

(spilled)

Registers

211 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

g

d

c

e

(spilled)

Registers

212 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

g

d

c

e

(spilled)

Registers

213 of 257

Chaitin's Algorithm Reloaded

R₀	R₁	R₂

f

a

b

g

d

c

e

(spilled)

Registers

214 of 257

A Smarter Algorithm

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

R₀	R₁	R₂

Registers

f

a

b

g

d

c

(spilled)

e

{ d }

g = d

{ g }

215 of 257

A Smarter Algorithm

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d = e + f

{ d }

{ e, f } d = e – f

{ d }

R₀	R₁	R₂

Registers

f

a

b

g

d

c

(spilled)

e

{ d }

g = d

{ g }

Concept of a web, includes:

- A definition and all reachable uses� - All definitions that reach the same use

216 of 257

A Smarter Algorithm

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d' = e + f

{ d' }

{ e, f } d' = e – f

{ d' }

R₀	R₁	R₂

Registers

f

a

b

g

d

c

(spilled)

e

{ d' }

g = d'

{ g }

Concept of a web, includes:

- A definition and all reachable uses� - All definitions that reach the same use

217 of 257

A Smarter Algorithm

{ a, b, c, d } e = d + a

{ b, c, e }

{ b, c, e } f = b + c

{ b, e, f}

{ b, e, f } f = f + b

{ e, f }

{ e, f } d' = e + f

{ d' }

{ e, f } d' = e – f

{ d' }

R₀	R₁	R₂

Registers

e

a

b

g

c

d'

f

a

b

c

d

e

f

a

Registers

222 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

c a

Registers

223 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

b c a

Registers

224 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

Registers

225 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

f

Registers

226 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

d f

Registers

227 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

f

Registers

228 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

f

Registers

229 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

Registers

230 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

Registers

231 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

b c a

Registers

232 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

b c a

Registers

233 of 257

Another Example

R₀	R₁	R₂

c

a

d

e

f

c a

b

Registers

234 of 257

Another Example

R₀	R₁	R₂

c

a

d

e

f

c a

b

Registers

235 of 257

Another Example

R₀	R₁	R₂

c

a

d

e

f

a

b

Registers

236 of 257

Another Example

R₀	R₁	R₂

c

a

d

e

f

a

b

Registers

237 of 257

Another Example

R₀	R₁	R₂

c

a

d

e

f

b

Registers

238 of 257

Another Example

R₀	R₁	R₂

c

a

d

e

f

b

Registers

239 of 257

Another Example (Different Coloring)

240 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

d f

Registers

241 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

f

Registers

242 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

f

Registers

243 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

Registers

244 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

e

f

e b c a

Registers

Unlike last time, choose purple instead of yellow

245 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

b c a

Registers

e

246 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

b c a

Registers

e

247 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

c a

Registers

e

248 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

c a

Registers

e

249 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

a

e

Registers

250 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

a

Registers

e

(spilled)

251 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

e

Registers

(spilled)

252 of 257

Another Example

R₀	R₁	R₂

c

a

b

d

f

e

Registers

(spilled)

Takeaway: fundamental nondeterminism �in color assignments and nodes to traverse = NP.�Heuristics may be suboptimal

253 of 257

Chaitin's Algorithm

●

Advantages:

●

For many control-flow graphs, finds an excellent assignment of variables to registers.

When distinguishing variables by use, produces a precise RIG.

Often used in production compilers like GCC.

●

Disadvantages:

●

Core approach based on the NP-hard graph coloring problem.

Heuristic may produce pathologically worst-case assignments.

●

254 of 257

Correctness Proof Sketch

●

No two variables live at some point are assigned the same register.

●

Forced by graph coloring.

●

At any program point each variable is always in one location.

●

Automatic if we assign each variable one register.

Requires a few tricks if we separate by use case.

●

255 of 257

Improvements to the Algorithm

Choose what to spill intelligently.

●

Use heuristics (least-commonly used, greatest improvement, etc.) to determine what to spill.

Handle spilling intelligently.

●

When spilling a variable, recompute the RIG based on the spill and use a new coloring to find a register.

256 of 257

Summary of Register Allocation

●

Critical step in all optimizing compilers.

The linear scan algorithm uses live intervals to greedily assign variables to registers.

●

Often used in JIT compilers due to efficiency. �Original LLVM approach, now tweaked

●

Chaitin's algorithm uses the register interference graph (based on live ranges) and graph coloring to assign registers.

●

The basis for the technique used in GCC.

257 of 257

Takeaway of Register Allocation

Many many other tricks: live range splitting, rematerialization, coalescing, scalar replacement of aggregates, spill heuristics.

Design principle: a little bit of register allocation is a lot better than none. A lot of register allocation is…hard.��Don’t get lost in the details! Simple, robust approaches work well.