reg-allocation.js

// Available registers: r0, r1, r2

// Source code
a = 1
b = 1
c = 1

d = (a + b) + c

b = a + c

// SSA/Three-address code
a0 = 1
b0 = 1
c0 = 1

t0 = a0 + b0
d0 = t0 + c0

b1 = a0 + c0

// Liveness
// a0: [111111]
// b0: [011100]
// c0: [001111]
// t0: [000110]
// d0: [000010]
// b1: [000001]

// Linear scan results:
// a0 <- r0
// b0 <- r1
// c0 <- r2
// t0 <- r0, a0 - spill
// d0 <- r1, b0 - expired
// b1 <- r0, t0, d0 - expired

// Pseudo-assembly
r0 <- 1
r1 <- 1
r2 <- 1

st[0] <- r0      // spill

r0 <- st[0]      // mov(st[0], r0)
r0 <- r0 + r1    // add(r1, r0)
r1 <- r0         // mov(r0, r1)
r1 <- r1 + r2    // add(r2, r1)

r0 <- st[0]      // mov(st[0], r0)
r0 <- r0 + r2    // add(r2, r0)