Expression propagation also improves code structuring, because it creates legal expressions out of statements, and expressions can be joined through the && and || operators:

   MOV R1, var_1       if(var_1
   CMP R1,#10                   != 10
   JEQ L1              &&   
   MOV R1, var_2          var_2          if(var_1 != 10 && var_2 != 20)
   CMP R1,#20                   != 20)
   JNE L2                goto L2;           goto L2;
L1: ...            L1: ...
L2:                L2:

Several complex expressions can be built by scanning the list of instructions and saving for each assignment to a register the right-hand-side of the assignment. Later, when the register is used, we can replace it with the right-hand-side we saved earlier.

Here's an algorithm that uses this approach:

PropagateExpressions()
{
    for each block in CFG
        b.savedRegs = new BitSet(processor.getNumberOfRegs)
    for each block in CFG
        for each instruction i in block
            replaceUses(i.op1)
            replaceUses(i.op2)
            if i.op == Assign && isRegister(i.dest)
                saveDefinition(block, i)  // remember rhs
                continue
            replaceUses(block, i.dest)  // e.g. for indexed addr. modes
}

saveDefinition(Block b, Node i)
{
    b.savedRegs[i.dest.regnum] = i
}

replaceUses(Block b, Node n)
{
    if n == null
         return null
    n.op1 = replaceUses(n.op1)
    n.op2 = replaceUses(n.op2)
    if n.op == Register && b.savedRegs[n.regnum] != null
        reg = n.regnum
        if n.liveout.isSet(reg)
            b.savedRegs[reg] = 0  // keep assignment to reg
            return n
        n = b.savedRegs[reg].op1  // get rhs of original assignment
        b.savedRegs[reg] = 0      // remove original assignment to reg
    return n
}

This is still a simplistic algorithm, which only works on a basic block at a time. Enhancements to the algorithm would be to allow the saved expressions to propagate to other basic blocks. However, we need to be careful not to allow propagation across instructions that may change any value that's in the saved array. This is a common problem, referred in compiler implementation literature as the alias detection problem.

Consider the following code:

   R1 = var_1
   *R2 = 0                 *R2 = 0
   var_2 = R1              var_2 = var_1 ?

In this code, we cannot move the reference to var_1 to the final statement unless we know for sure that the *R2 = 0 assignment will not change the var_1 location. Since R2 contains a pointer, we have to make sure that R2 doesn't contain the value &var_1, otherwise the resulting decompiled program would not behave the same as the input binary code.

This problem is very difficult to solve; even an advanced compiler cannot always decide whether a variable "has been aliased" by a pointer. In this case, we have to be conservative, thus avoiding moving var_1 to the last statement.

A lot of work can be put in deciding whether it is safe to keep the definition of R1 or whether to remove it. The conservative approach is to invalidate the savedRegs entry for R1 (and actually for all other registers) whenever there is an assignment through an indirect pointer. It is always safe to keep references to constant values, including fixed address references, which by definition cannot be aliased.

Another case where it is difficult to decide what to remember and what to forget is when there are function calls in one of the statements:

   R1 = local_1
   call f                  f()
   var_2 = R1              var_2 = local_1 ?

In this case it's okay to keep local_1 in R1 across the call to f(), but only under certain conditions:

• no pointer to the local frame is passed to f() or is saved in a global variable that may be used by f()
• f() does not change the value of R1

It's very difficult, although not impossible, to keep track of which address is saved to global variables, and which is used by another function. This case is very rare, though, so it should be safe to assume that a function does not change aliased locations in global memory (for example we can analyze the function and decide that it does not write any global memory location).

The second condition is somewhat easier to compute, although even in this case there are common cases where it is not known which registers are changed by the function. There are 2 ways to compute register use by a function:

• perform a global data flow analysis on the function, computing the liveness information at the entry point and at the exit point of the function. This approach is complicated by the fact that most functions save and restore a number of registers during their prologue and epilogue code, so the standard life time algorithm may have to be modified to take into account the frame layout of the function
• determine which of a set of standard calling conventions is used by the function. Calling conventions are set by a compiler writer, or by an operating system vendor, so that code compiled by different vendors can communicate according to a fixed set of rules. These rules usually define which registers can be changed by a function call, and which registers must be preserved across the call, thus making it possible to decide whether it's okay to move an assignment across a function call instruction.