First Code Transformation: Removing Flag Computations

Short introduction to code transformations

If you intend to write a decompiler, you’ll find yourself writing code transformations.
In our context, code transformations are operations that take as input an expression tree, and return an equivalent but different expression tree.

An equivalent expression tree is one that does the same thing as the original. More formally, it’s an expression tree that when run, will reach the same final state as the original expression tree.

Here’s a simple example, converting a while loop to a do-while loop:

Before:

while cond:
    stmt

After:

if cond:
    do:
        stmt
    while cond

Code transformations are a very tricky business. You may find yourself changing the meaning of your expression trees without noticing. That’s one of the reasons we wrote the VM: we wanted to make sure that our code transformations will be correct.

Generally, you’ll want to transform your code to a somewhat ‘better’ version. ‘Better’ in what sense?
Well, the code may be:

• More readable. A good purpose, as we are writing a decompiler for human beings. Unfortunately, this goal is not well defined. ‘More readable’ will have to be defined by heuristics.
• Shorter/smaller. An easier goal to define, smaller code has the following advantages:
  • It might be faster to execute.
  • It might faster to process by other algorithms – after all, it is shorter.
  • It might be more readable.
• Simpler, in the sense that it uses less types of operations. For example, take transforming a while to a do-while (shown above). If we wanted to analyze loops, it will allow us to write code to handle just do-while loops, instead of handling both cases.

There are many more possible goals for code transformations. The bottom line is that code transformations may do any of the following:
* Make the life of the human reader easier.
* Make the life of the decompiler programmer easier.
* Make the life of the decompiler easier.

An important aspect of code transformations is when to do them. Here is a good rule of thumb:

If it makes it harder for the programmer or the decompiler – it should be done as late as possible.
Otherwise – it should be done as early as possible.

Removing Flag Computations

This is the first code transformation we intend to write. Consider the following case:
[c]
sub eax, ebx
sub ebx, ecx
[/c]

The equivalent expression tree for these two instructions looks something like this:

eax = eax - ebx
zf = eax == 0
ebx = ebx - ecx
zf = ebx == 0

Here I listed only the changes to zf and the actual registers. All the other flags (OF,CF,…) are changed as well. In a sequence of such instructions, all the modifications to the flags in the middle are actually dead code, and may be removed. This transformation will make the code shorter, faster to execute on our VM and faster to analyze by later stages.

This is a special case of dead code removal. This raises a valid question: why not let some general dead code removal transformation handle the flags?

There are a few reasons:

• A general dead code removal might be more complex to write. Just writing exactly the same algorithm for general purpose registers will be more complicated, because of overlapping registers.
• This transformation may remove up to 80% of many of the disassembled instructions. Flag calculations take up a lot nodes in the expression trees!
• This transformation may be run as soon as the disassembly stage itself, while a general dead code removal transformation will not. This is so because of some assumptions we are allowed to make on the way flags behave. For example, an instruction template (“%0=%0-%1; ZF=%0==0” for sub) might have its parameters changed, but the flags affected stay the same.

The implementation of this transformation is not yet complete. When it is, I’ll talk a bit about the mechanics behind it. It is much more complicated than it seems!