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 coloring problem.
1. Identify the live range of each variable
2. 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)
3. Try to assign as many colors to the nodes of the graph as there are registers so that two neighbors have different colors
Fig 4.3 Flow graph of an inner loop
Fig 4.4 Code sequence using global register assignment
Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.