REGISTER ALLOCATION AND ASSIGNMENT
Local register allocation
Register allocation is only within a basic block. It
follows top-down approach.
Assign registers to the most heavily used variables
Traverse the block
Use count as a priority function
Assign registers to higher priority variables first
Heavily used values reside in registers
Does not consider non-uniform distribution of uses
Need of global register allocation
Local allocation does
not take into account that some instructions (e.g. those in loops) execute more
frequently. It forces us to store/load at basic block endpoints since each
block has no knowledge of the context of others.
To find out the live
range(s) of each variable and the area(s) where the variable is used/defined
global allocation is needed. Cost of spilling will depend on frequencies and
locations of uses.
Register allocation depends on:
Size of live range
Number of uses/definitions
Frequency of execution
Number of loads/stores needed.
Cost of loads/stores needed.
Register allocation by graph coloring
Global register allocation can be seen as a graph
Identify the live range of each variable
Build an interference graph that
represents conflicts between live ranges (two nodes are connected if the
variables they represent are live at the same moment)
Try to assign as many colors to the
nodes of the graph as there are registers so that two neighbors have different
4.3 Flow graph of an inner loop
Fig 4.4 Code sequence using global