Local Register Allocation
Instructor: Dr. Fahed Jubair
Computer Engineering Department
University of Jordan
Register Allocation
Program with Register Program with
n Registers Allocator m Registers
• Register allocation is the process whereby a compiler takes, as
an input, a program that uses arbitrary number of registers and
produces, as an output, an equivalent program that fits into the
finite register set of a target machine
© All rights reserved.
Register Allocation Process
• The task of register allocator is to
§ Specify, at each point in the code, the program values to keep in
registers
§ Insert code to move program values between registers and memory
§ Minimize the needed code for register-memory movements
• Register allocation versus Register assignment
§ Allocation is deciding which program values to keep in registers
§ Assignment is choosing specific registers for those program values
• The compiler does both: allocation and assignment
© All rights reserved.
Register Allocation
Challenges
• If the number of program values is less than the number
of physical registers, then the problem is easy
• The problem is when the number of program values are
larger than the number of physical registers
⇒ this is the common case
• Register spilling: the process of moving values from
memory to registers, and vice versa
• To avoid degrading performance, register allocation
techniques aim to minimize register spelling
© All rights reserved.
Register Allocation Techniques
• Local allocation (within basic blocks)
§ Spill registers by reuse distance
• Global allocation (across multiple basic blacks)
§ Graph coloring
© All rights reserved.
Local
Register Allocation
• The key idea is to use liveness information about program
variables for smarter choices when choosing which
registers to spill (i.e., put their values back into memory)
• Spill registers that have dead data. If all registers have
live data, then spill the register with the most distant use
• This approach is efficient, in practice, when applied to
basic blocks (i.e., a maximal sequence of sequential
instructions)
© All rights reserved.
Assumptions
Without loss of generality, we will explain the algorithm of
local register allocation while making the following
assumptions:
• The assembly program is a three-address code with all
instructions have the format:
OPCODE RESULT OPERAND1 OPERAND2
• All operands have program values that reside in memory
§ But the algorithm can be modified to assume virtual registers instead
• The register allocation algorithm will insert load and store
operations to allocate and assign program values to the
finite register set of the target machine
© All rights reserved.
Local Register
Bottom-up
Allocation Algorithm registe
Bottom-up register allocation ensure(opr)
if opr is already in register r
return r
For each tuple op A B C in a BB, do else
Rx = ensure(A) r = allocate(opr)
Ry = ensure(B) generate load from opr into r
return r
if A dead after this tuple, free(Rx)
if B dead after this tuple, free(Ry) free(r)
Rz = allocate(C) //could use Rx or Ry if r is marked dirty and variable is live
generate code for op generate store
mark r as free
mark Rz dirty
allocate(opr)
At end of BB, for each dirty register if there is a free r
generate code to store register into appropriate variable choose r
else
choose r with most distant use
free(r)
mark r associated with opr
• We will present this as if A, B, C are variables© All in rights
[Link]. return r
Can be modified to assume that A, B and C are in virtual
Register Allocation Example
• We will show how to perform local register allocation
algorithm for the following three-address code. Assume the
machine has the three physical registers: R1, R2, and R3
ADD A, B, C // A = B + C
MUL D, A, C // D = A * C
MUL E, D, D // E = D * D
ADD F, E, D // F = E + D
ADD A, F, B // A = F + B
© All rights reserved.
Register Allocation Example
(Liveness Analysis)
• First step is to compute Liveout information for each
statement in the basic block
ADD A, B, C // Liveout = {A, C, B}
MUL D, A, C // Liveout = {D, B}
MUL E, D, D // Liveout = {E, D, B}
ADD F, E, D // Liveout = {F, B}
ADD A, F, B // Liveout = { }
© All rights reserved.
Register Allocation Example
(Initially)
Free § Initially, all registers are free
R1, R2, R3
List § Assign list keeps track of register-
Assign value assignment
List § Dirty list keeps track of dirty
Dirty registers (need to be written back
List to memory when freed)
ADD A, B, C // Liveout = {A, C, B}
MUL D, A, C // Liveout = {D, B}
MUL E, D, D // Liveout = {E, D, B}
ADD F, E, D // Liveout = {F, B}
ADD A, F, B // Liveout = { }
© All rights reserved.
Register Allocation Example
(First Statement)
Free • ensure(B) returns R1 and generates load
List • ensure(C) returns R2 and generates load
Assign • B is live ⇒ do nothing
R1=B, R2=C, R3=A
List • C is live ⇒ do nothing
Dirty • allocate(A) returns R3 and marks R3 dirty
R3 • Generate code with new register assignments
List
LD R1, B
LD R2, C
ADD A, B, C // Liveout = {A, C, B}
ADD R3, R1, R2
MUL D, A, C // Liveout = {D, B}
MUL E, D, D // Liveout = {E, D, B}
ADD F, E, D // Liveout = {F, B}
ADD A, F, B // Liveout = { }
© All rights reserved.
Register Allocation Example
(Second Statement)
Free • ensure(A) returns R3
R3 , R2
List • ensure(C) returns R2
Assign R1=B, R2=C, R3=A • A is dead ⇒ free R3 and generate store
List R2=D • C is dead ⇒ free R2
Dirty • allocate(D) returns R2 and marks R2 dirty
R2 R3 • Generate code with new register assignments
List
LD R1, B
LD R2, C
ADD A, B, C // Liveout = {A, C, B}
ADD R3, R1, R2
MUL D, A, C // Liveout = {D, B}
SW R3, A
MUL E, D, D // Liveout = {E, D, B}
MUL R2, R3, R2
ADD F, E, D // Liveout = {F, B}
ADD A, F, B // Liveout = { }
© All rights reserved.
Register Allocation Example
(Third Statement)
Free
R3
List • ensure(D) returns R2
Assign R1=B, R2=D • D is live ⇒ do nothing
List , R3=E • allocate(E) returns R3 and marks R3 dirty
• Generate code with new register assignments
Dirty
R2 , R3
List
LD R1, B
LD R2, C
ADD A, B, C // Liveout = {A, C, B}
ADD R3, R1, R2
MUL D, A, C // Liveout = {D, B}
SW R3, A
MUL E, D, D // Liveout = {E, D, B} MUL R2, R3, R2
ADD F, E, D // Liveout = {F, B} MUL R3, R2, R2
ADD A, F, B // Liveout = { }
© All rights reserved.
Register Allocation Example
(Fourth Statement)
Free • ensure(E) returns R3
R2 , R3
List • ensure(D) returns R2
Assign R1=B, R2=D, R3=E • E is dead ⇒ free R3 and generate store
List R2=F • D is dead ⇒ free R2 and generate store
• Allocate(F) returns R2 and marks R2 dirty
Dirty • Generate code with new register assignments
R2, R3 , R2
List
LD R1, B
LD R2, C
ADD A, B, C // Liveout = {A, C, B} ADD R3, R1, R2
MUL D, A, C // Liveout = {D, B} SW R3, A
MUL E, D, D // Liveout = {E, D, B} MUL R2, R3, R2
ADD F, E, D // Liveout = {F, B} MUL R3, R2, R2
ADD A, F, B // Liveout = { } SW R3, E
SW R2, D
© All rights reserved. ADD R2, R3, R2
Register Allocation Example
(Fifth Statement)
Free • ensure(F) returns R2
R3 , R1 , R2
List • ensure(B) returns R1
Assign R1=B, R2=F • F is dead ⇒ free R2 and generate store
List R1=A • B is dead ⇒ free R1
• allocate(A) returns R1 and marks R1 dirty
Dirty • Generate code with new register assignments
R2 , R1
List
LD R1, B
LD R2, C SW R2, F
ADD A, B, C // Liveout = {A, C, B} ADD R3, R1, R2 ADD R1, R2, R1
MUL D, A, C // Liveout = {D, B} SW R3, A
MUL E, D, D // Liveout = {E, D, B} MUL R2, R3, R2
ADD F, E, D // Liveout = {F, B} MUL R3, R2, R2
ADD A, F, B // Liveout = { } SW R3, E
SW R2, D
ADD
© All rights reserved. R2, R3, R2
Register Allocation Example
(Termination)
Free
R2, R3 At termination, the LD R1, B
List
algorithm writes LD R2, C
Assign back all dirty
R1=A
List ADD R3, R1, R2
registers to memory
Dirty SW R3, A
R1
List MUL R2, R3, R2
MUL R3, R2, R2
SW R3, E
ADD A, B, C // Liveout = {A, C, B} SW R2, D
MUL D, A, C // Liveout = {D, B} ADD R2, R3, R2
MUL E, D, D // Liveout = {E, D, B} SW R2, F
ADD F, E, D // Liveout = {F, B} ADD R1, R2, R1
ADD A, F, B // Liveout = { } SW R1, A
© All rights reserved.
Let us Take
A Second Example
• Perform local register allocation for the following three-
address code. Assume the machine has the three physical
registers: R1, R2, and R3
ADD A, B, C // A = B + C
MUL D, A, A // D = A * A
MUL E, A, B // E = A * B
MUL F, D, E // F = D * E
ADD A, F, C // A = F + C
© All rights reserved.
Second Example
(Liveness Analysis)
ADD A, B, C // Liveout = {A, C, B}
MUL D, A, A // Liveout = {D, C, A, B}
MUL E, A, B // Liveout = {D, E, C}
MUL F, D, E // Liveout = {F, C}
ADD A, F, C // Liveout = { }
© All rights reserved.
Second Example
(Initially)
Free • Initially, all registers are free
R1, R2, R3
List • Assign list keeps track of register-
Assign value assignment
List • Dirty list keeps track of dirty
registers (need to be written back
Dirty
to memory when freed)
List
ADD A, B, C // Liveout = {A, C, B}
MUL D, A, A // Liveout = {D, C, A, B}
MUL E, A, B // Liveout = {D, E, C}
MUL F, D, E // Liveout = {F, C}
ADD A, F, C // Liveout = { }
© All rights reserved.
Second Example
(First Statement)
Free • ensure(B) returns R1 and generates load
List • ensure(C) returns R2 and generates load
• B is live ⇒ do nothing
Assign
R1=B, R2=C, R3=A • C is live ⇒ do nothing
List
• allocate(A) returns R3 and marks R3 dirty
Dirty • Generate code with new register assignments
R3
List
ADD A, B, C // Liveout = {A, C, B} LD R1, B
LD R2, C
MUL D, A, A // Liveout = {D, C, A, B}
ADD R3, R1, R2
MUL E, A, B // Liveout = {D, E, C}
MUL F, D, E // Liveout = {F, C}
ADD A, F, C // Liveout = { }
© All rights reserved.
Second Example
(Second Statement)
• ensure(A) returns R3
Free • A is live ⇒ do nothing
List • allocate(D) will find no free registers ⇒ spill R2
Assign R1=B, R2=C, R3=A (because C has the most distant use)
List , R2 = D • Note that no store operation was needed
Dirty when R2 was spilled (why?) it is not Dirty
R3 , R2 • R2 becomes assigned to D and marked dirty
List
• Generate code with new register assignments
ADD A, B, C // Liveout = {A, C, B}
LD R1, B
MUL D, A, A // Liveout = {D, C, A, B}
LD R2, C
MUL E, A, B // Liveout = {D, E, C}
ADD R3, R1, R2
MUL F, D, E // Liveout = {F, C}
MUL R2, R3, R3
ADD A, F, C // Liveout = { }
© All rights reserved.
Second Example
(Third Statement)
Free • ensure(A) returns R3
R1, R3 • ensure(B) returns R1
List
• A is dead ⇒ free R3 and generate store
Assign R1=B, R2=D, R3=A
, R1 = E • B is dead ⇒ free R1
List
• allocate(E) returns R1 and marks R1 dirty
Dirty • Generate code with new register assignments
R2, R3 , R1
List
LD R1, B
ADD A, B, C // Liveout = {A, C, B} LD R2, C
MUL D, A, A // Liveout = {D, C, A, B} ADD R3, R1, R2
MUL E, A, B // Liveout = {D, E, C} MUL R2, R3, R3
MUL F, D, E // Liveout = {F, C} SW R3, A
MUL R1, R3, R1
ADD A, F, C // Liveout = { }
© All rights reserved.
Second Example
(Fourth Statement)
Free • ensure(D) returns R2
R1 , R2, R3
List • ensure(E) returns R1
• D is dead ⇒ free R2 and generate store
Assign R1=E , R2=D
• E is dead ⇒ free R1 and generate store
List , R1 = F
• allocate(F) returns R1 and marks R1 dirty
Dirty • Generate code with new register assignments
R1 , R2 , R1
List
LD R1, B
ADD A, B, C // Liveout = {A, C, B} LD R2, C
ADD R3, R1, R2
MUL D, A, A // Liveout = {D, C, A, B}
MUL R2, R3, R3
MUL E, A, B // Liveout = {D, E, C}
SW R3, A
MUL F, D, E // Liveout = {F, C}
MUL R1, R3, R1
ADD A, F, C // Liveout = { } SW R2, D
SW R1, E
© All rights reserved. MUL R1, R2, R1
Second Example
(Fifth Statement)
Free • ensure(F) returns R1
R2, R3 , R1 , R2 • ensure(C) returns R2 and generates load
List
• F is dead ⇒ free R1 and generate store
Assign R1=F
, R2 = C R1=A • C is dead ⇒ free R2
List
• allocate(A) returns R1 and marks R1 dirty
Dirty • Generate code with new register assignments
R1 , R1
List
LD R1, B
LD R2, C LD R2, C
ADD A, B, C // Liveout = {A, C, B}
ADD R3, R1, R2 SW R1, F
MUL D, A, A // Liveout = {D, C, A, B} ADD R1, R1, R2
MUL R2, R3, R3
MUL E, A, B // Liveout = {D, E, C} SW R3, A
MUL F, D, E // Liveout = {F, C} MUL R1, R3, R1
ADD A, F, C // Liveout = { } SW R2, D
SW R1, E
© All rights reserved. MUL R1, R2, R1
Second Example
(Termination)
Free LD R1, B
R2, R3 At termination, the
List LD R2, C
algorithm writes
Assign ADD R3, R1, R2
R1=A back all dirty
List registers to memory MUL R2, R3, R3
Dirty SW R3, A
R1
List
MUL R1, R3, R1
SW R2, D
ADD A, B, C // Liveout = {A, C, B} SW R1, E
MUL D, A, A // Liveout = {D, C, A, B} MUL R1, R2, R1
MUL E, A, B // Liveout = {D, E, C} LD R2, C
MUL F, D, E // Liveout = {F, C} SW R1, F
ADD R1, R1, R2
ADD A, F, C // Liveout = { }
SW R1, A
© All rights reserved.
Exercise
• Perform local register allocation for the following three-
address code. Assume the machine has the three physical
registers: R1, R2, and R3
ADD A, B, C // A = B + C
MUL D, B, C // D = B * C
ADD E, D, A // E = A + D
ADD C, E, B // C = E + B
© All rights reserved.
Local Register Allocation
Summary
• We studied a local register allocation algorithm that
utilizes liveness of program values for efficient
register spelling
• In practice, the algorithm works well for basic blocks
• What about register allocation whole program?
Ø We can apply local register allocation for each block in the
CFG independently
Ø Correct but inefficient
Ø Need a different algorithm for global register allocation
© All rights reserved.
