Home | | Compiler Design | | Compiler Design | Register Allocation and Assignment

Register Allocation and Assignment - | Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

Chapter: Principles of Compiler Design - Code Generation

Register Allocation and Assignment

Register allocation is only within a basic block. It follows top-down approach.


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

 

Count uses

 

Use count as a priority function

 

Assign registers to higher priority variables first

 

Advantage

Heavily used values reside in registers

 

Disadvantage

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.

Basic idea:

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


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.