Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 45

User Rating:  / 0
PoorBest 

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Liveness information allows us to keep values in registers if they will be used later. An obvious concern is why do we assume all variables are live at the end of blocks? Why do we need to save live variables at the end? It seems reasonable to perceive that we might have to reload them in the next block. To do this, we need to determine live/next use information across blocks and not just within a block. This requires global data-flow analysis.

 

Global Data-Flow Analysis

A Directed Acyclic Graph (DAG) for a basic block has the following labels for the nodes:

  • Leaves are labeled by unique identifiers.
  • Interior nodes are labeled by operator symbols.
  • Nodes can have multiple labels since they represent computed values.

Algorithm: Generate DAG from 3-address code

For statement i: x = y op z

  • if y op z node exists,
    add x to the label for that node.
    else
    add node for y op z.
  • if y or z exist in the dag,
    point to existing locations
    else
    add leaves for y and/or z and have
    the op node point to them.
  • label the op node with x.
  • if x existed previously as a leaf,
    subscript that previous entry.
  • if x is associated with other interior nodes,
    remove them from that list.

Here and an example of the DAG generated for the 3-address code

DAG generated

Here is another example

DAG generated1

DAGs and optimization

DAGs play an important role in code optimization. It is possible to detect common subexpressions and eliminate them; a node in the DAG with more than one parent is common sub-expression.

The order in which the DAG is traversed can lead to better code. For example, the following DAG can be traversed in two ways:

following DAG can be traversed in two ways

The code generated for order one with 2 registers is

MOV a, R0
ADD b,R0
MOV c, R1
ADD D, R1
MOV R0,t1
MOV e, R0
SUB R1,R0
MOV t1,R1
SUB R0, R1
MOV R1,t4

Ten machine instructions are generated.

Whereas, order #2 with 2 registers leads to

MOV c, R0
ADD D, R0
MOV e, R1
SUB R0,R1
MOV a,R0
ADD b, R0
MOV R0,t4

Only seven instructions are required, a saving of three machine instructions.
Reordering improved code because computation of t4 immediately followed computation of t1, its left operand. t1 must be in a register and it is.

Register Allocation

Registers in a machine are a scarce resource. The issue faced by the code generator is this how to best use the bounded number of registers. The matter is complicated by the fact that a few registers are reserved for special purposes. For example, the program counter is kept in a registers. A register is used for the keeping track of the top of the function call stack. Certain operators require multiple registers, often in pairs. Division is an example of such an operator.

The general register allocation problem is NP-complete. Heuristic algorithms exist to solve the problem. One such strategy is the by using the graph coloring algorithm: given a graph, color the nodes with different colors such that no two nodes that have an edge between them have the same color. Here is how the graph coloring algorithm can be used to compute register allocation for K registers in a machine.

Algorithm: K registers allocation with graph coloring

  1. Compute liveness information.
  2. Create interference graph G
  3. one node for each variable, an edge connects two variables if one is live at a point where the other is defined
  4. Simplify: for any node m with less than K neighbors, remove it from the graph and push it onto a stack. If (G - m ) can be colored with K colors, so can G. If we reduce the entire graph, goto step 5.
  5. Spill: if we get to the point where we are left with only nodes with degree >= K, mark some node for potential spilling (to memory). Remove and push onto stack.
    Back to step 3.
  6. Assign colors: starting with empty graph, rebuild graph by popping elements off the stack and assigning a color different from neighbors. Potential spill nodes may or may not be colorable.

Process may require iterations and rewriting of some of the code to create more temporaries.

Let us apply the algorithm to the following 3-address code

following 3-address code