Lesson 10--Register Allocation Flashcards
(23 cards)
True or False: Register allocation is a must for CISC
False. All operands are in memory and there are long instructions to retrieve and use them.
True or False: Register allocation is a must for RISC
True
True or False: Register allocation is a must for VLIW
True
True or False: Register allocation saves energy on embedded processors
True. It reduces memory accesses, which are energy hogs.
Register allocation
Determines which of the values should be in registers at each execution point
Register assignment
Determines which register should be used by each allocated value
Goal of register allocation
To minimize the traffic between the CPU and the memory hierarchy
Three parameters that are positively impacted by better register allocation
Speed
Code size
energy efficiency
gen
variable is newly defined
kill
old value is no longer accessible
def
on the left hand side
use
on the right hand side
live
variable will be used again
dead
variable will never be used again
web
The live range for each value
interference
overlapping ranges
spill cost
how many definitions and uses are in a range
allocation
which webs get a register
spilling and splitting
Split webs if needed
def-use (DU) chains
–connects definition to all reachable uses
–conditions for putting defs and uses into the same web
–definition and all reachable uses must be part of the same web
–all defs that reach the same use must be in the same web
Graph Coloring Heuristics
–Remove nodes that have degree < N
–push the removed nodes onto the stack
–When all the remaining nodes have a degree >= N
–Find the node with the least spill cost and push it onto the stack
–What we are doing is ordering the nodes on the stack in the order of their spill cost. The
top of the stack will have the highest spill cost, the bottom of the stack will have the least
spill cost. The nodes with the highest spill costs will get registers.
–When all the list of nodes is empty, it is time to start coloring.
Options when coloring fails
- Pick a web and allocate the value in memory. All the definitions go to memory, all uses come from memory.
- Split the web into multiple webs.
Cost
of executions * cost of instruction
