Beginners Introduction Forward tools Reverse tools Simple decompiler Problems   Intermediate Architecture Object formats Code vs. data Basic blocks Control flow graph Loops Statements Data Flow Expression propagation The stack Stack frames Frameless functions Saved registers Recovering types   Advanced Advanced topics Switch statements Code vs. Data 2 Call Optimizations

Prev: Creating Statements

---

Data Flow Analysis

So far we have only considered code execution paths without consideration for what each arithmetic instruction does. We've only been concerned about branches and compare instructions.
However we have seen in the previous page that we cannot collapse multiple if statements without collapsing at least some of the instructions between the branch instructions.

Since registers are not directly accessible by a C program, a good guideline is to try to remove all register references from instructions. What's left should be fairly close to the original source file.

But when is it safe to collapse multiple instructions without changing the behavior of the converted program?

The answer is: when we are sure that there is no loss of data when we remove an instruction.

Consider the following sequence of instructions:

    MOV  R1, var_1              R1 = var_1;
    CMP  R1,#10                 if(R1 == 10 ||
L0: JEQ  L1
    CMP  R1,#20                    R1 == 20) {
    JNE  L2
L1: ....
L2:                             }

In this sequence we cannot simply collapse the first 2 instructions into a single "CMP var_1, #10", because the value in R1 is used again in the second CMP instruction. In this case it is safe to assume that the second CMP instruction also checks the value of "var_1", so it is safe to convert it to "CMP var_1, #20". This would lead to the final statement:

    if(var_1 == 10 || var_1 == 20) {
    } 

If the value of register R1 is used at or after the instruction L0, we say that the register is "alive" at L0.
Instead, if the register is reloaded with another value in a subsequent instruction, we say that the register is "dead" at L0.

Thus, the "liveness" of a register is an attribute of each instruction.

It's easy to compute the liveness of a register in a basic block. It's more difficult to compute the lifetime of a register across basic blocks. For example in the following code:

    MOV  R2, var_2
    ...
    JEQ  L3
    ...
L4:
    MOV  R1, var_1              
    CMP  R1,#10                  if(var_1 == 10 ||
    JEQ  L1
    CMP  R2,#20                     var_2 == 20) {  // ?
    JNE  L2
L1: ....
L2:                              }

How do we know that R2 still has the value of var_2 at the CMP R2,#20 instruction?

There may be an execution path from another R2 assignment that enters the block L4, in which case we cannot know what the value of R2 is. Or, there can be another use of R2 after the compare instruction.

We need to perform a global lifetime analysis on all the basic blocks of the function, considering how execution flows from block to block, and computing whether each register is "dead" or "alive" at each instruction.

Data Representation

Liveness information is typically represented as a set of bits per each instruction. Each bit in the set represents one of the variables we want to track. Despite the importance of data flow analysis, books on compiler implementation use different terms to identify the information described in the liveness sets. Some compute the sets of killed and used variables; others compute the sets of live and dead variables, although this definition doesn't say if the variables are live when entering the instruction or when exiting the instruction.

I think a clearer identification of the liveness information involves computing the "livein" and "liveout" sets, meaning the set of variables that are alive before executing the instruction, and those that are alive after executing the instruction.

Since we are dealing with assembly instructions and we want to track the liveness information of each register, it makes sense to have a bit set where each bit represents a CPU register. Here's an example:

Instruction stream    LiveIn(i) Set   LiveOut(i) Set    Def(i) Set   Use(i) Set
R1 = var_2                            R1                R1
R2 = R1 + 1           R1              R1?  R2           R2           R1
var_2 = R2            R1? R2          R1?  R2?                       R2

Computing Use and Defs

You can see that the LiveIn and LiveOut sets depend on the information provided by 2 functions of each instruction. The Def(i) function returns the set of registers that are "defined" (written) by instruction 'i'; the Use(i) function returns the set of registers "used" (read) by instruction 'i'. Def(i) and Use(i) only depend on each instruction. Here is some code that computes Def(i) and Use(i):

ComputeUseDefs()
{
   for each instruction i in each block in CFG
       i.defs = 0
       if i.op == Assign && isRegister(i.dest)
          i.defs = BitSet(i.dest.regnum)
       i.use = 0
       if i.src1 && isRegister(i.src1)
          i.use |= BitSet(i.src1.regnum)
       if i.src2 && isRegister(i.src2)
          i.use |= BitSet(i.src2.regnum)
}

This code assumes that each operand can only be a memory location, a constant or a register. If an operand can be something more complex, such as an indexed addressing mode, then we need to consider every single piece referenced by the addressing mode and set all the relevant bits in the Def(i) and Use(i) sets.

A more robust algorithm, using a tree to represent both source and destinations operands is as follows:

ComputeUseDefs()
{
    for each instruction i in each block in CFG
        i.defs = 0
        i.use = 0
        if i.op == Assign && isRegister(i.result)
            i.defs = BitSet(i.result.regnum)
        else
            i.use |= getUses(i.result)
        i.use |= getUses(i.op1)
        i.use |= getUses(i.op2)
}

getUses(Node n)
{
    if n == null
       return 0
    use  = getUses(n.op1)
    use |= getUses(n.op2)
    if n.op == Register
       use |= BitSet(n.regnum)
    return use
}

We will see in the advanced section that it is not always possible to compute the Defs(i) and Use(i) sets, in particular for call instructions when the destination of the call in not known.

Global Lifetime Analysis

Armed with the knowledge of which register is used and defined by each instruction, we can now compute the liveness information.

The algorithm to compute LiveIn(i) and LiveOut(i) performs several passes through  the control flow graph, computing and propagating the liveness information to all the other blocks until there is some entry that is changed. When the computed sets are not changed anymore, it means that we have computed all the needed information and we can exit the algorithm.

The algorithm works in 3 phases. The first phase computes the liveness information for each basic block without considering how that basic block is related to the other basic blocks:

   for each b in CFG
      b.use = 0
      b.defs = 0
      b.input = 0
      b.output = 0
      i = b.lastInstr
      do
          i.liveout = i.use
          i.dead = i.defs & ~i.liveout

          b.use = i.liveout | (b.use & ~i.dead)
          b.defs = i.dead | (b.defs & ~i.liveout)

          i = i.prevInstr
      while i != null
   end for each b

The second phase works on the information in each block by propagating the liveness information from each block to all the other blocks in the CFG:

    do
        changed = false
        for each block in CFG
            out = b.defs
            for each succ in block.succs
                out |= succ.input

            in = block.use | (out & ~block.defs)
            if in != block.input || out != block.output
                changed = true
                block.input = in
                block.output = out
        end for each block
    while changed

The third phase adds the information collected from the other blocks to each instruction present in each block:

    for each block in CFG
        live = 0
        for each succ in block.succs
            live |= succ.input

        i = block.lastInstr
        do
           newlive = i.liveout | (live & ~i.dead)
           i.liveout = live
           live = newlive
           i = i.prevInstr
        while i != null
    end for each block

After the algorithm we can use the LiveIn(i) and LiveOut(i) information in our attempt to eliminate register references and to compress multiple instructions into complex expressions.

---

Next: Expression Propagation