Again freestudy9 comes back with new post related to Register Allocation. Additionally, we have tried to make it with a point to point Information.
- Efficient utilization of registers is important in generating good code.
There are four strategies for deciding what values in a program should reside in a register and which register each value should reside. Strategies are,
Global register allocation
- Following are the strategies adopted while doing the global register allocation.
- The global register allocation has a strategy of storing the most frequently used variables in fixed registers throughout the loop.
- Another strategy is to assign some fixed number of global registers to hold the most some active values in each inner loop.
- The registers are not already allocated may use to hold values local to one block.
In certain languages like C or Bliss programmer can do the register allocation by using register declaration to keep certain values in a register for the duration of the procedure.
- The usage counts the count for the use of some variable x in some register used in any basic block.
- So that, The usage count gives the idea about how many units of cost can save by selecting a specific variable for global register allocation.
- The approximate formula for usage count for the Loop L in some basic block B can give as,
∑ (use(x,B) + 2* liv live(x,B))
block B in L
- Where use(x,B) number of times x used in block B prior to any definition of x here
live(x,B) =1 if x live on exit from B; otherwise live(x)=0.
Register assignment for an outer loop
- Consider that there are two loops L1 is an outer loop and L2 is an inner loop, and allocation of variable a is to done to some register. The approximate scenario is as given below,
- If an allocated in loop L2 then it should not allocate in L1 – L2.
- Also If a allocated in L1 and it not allocated in L2 then store a on an entrance to L2 and load a while leaving L2.
If a allocated in L2 and not in L1 then load a on entrance of L2 and store a on exit, not from L2.
Register allocation for graph coloring
The graph coloring works in two passes. The working is as given below,
- In the first pass, the specific machine instruction selected for register allocation. For each variable, a symbolic register allocated.
- Moreover, In the second pass, the register inference graph is prepared. In register inference graph each node a symbolic register and an edge connects two nodes where one is live at a point where other defined.
- Also, Then a graph coloring technique applied to this register inference graph using kk- color. The k-colors can assume to be a number of assignable registers. In graph colors coloring technique, no two adjacent nodes can have the same color. Hence in reregister
inference graph using such graph coloring principle each node (actually a variable) assigned the symbolic registers so that no two symbolic registers can interfere with each other with assigned physical registers.