IL for decompiler to human-readable format

Question

After writing my own disassembler, I am now looking to making its assembly listing more human readable, e.g. from an (artificial) example

push    ebp
mov     ebp, esp
sub     esp, 10h
mov     eax, dword ptr [55431824h]
imul    eax, dword ptr [ebp+8]
add     eax, dword ptr [ebp+0ch]
mov     dword ptr [ebp-4], eax
mov     eax, dword ptr [ebp-4]
leave
ret     10h

via (> marks an auto-recognized prologue/epilogue):

>push    ebp
>mov     ebp, esp
>sub     esp, 10h

 mov     eax, dword ptr [_global_55431824]
 imul    eax, dword ptr [arg_0]
 add     eax, dword ptr [arg_4]
 mov     dword ptr [local_4], eax
 mov     eax, dword ptr [local_4]

>leave
>ret     10h

towards

eax = 10
eax *= arg_0
eax += arg_4
local_4 = eax
eax = local_4
return

At this point, each pseudo instruction is still tied to its original disassembled representation. When printing out, I can scan for certain sequences and so I replace the first two lines with

eax = 10 * arg_0

and then just skip printing the next line. However, there is a limit to how far I can get with that. Concatenating the next operation, which would lead to

eax = 10 * arg_0 + arg_4

requires to look ahead two instructions, and would only work for this specific combination of mov, imul, and add, while assuring the same destination register is still targeted and the intermediate instructions have no lasting effect on other registers.

The goal is to end up with something like this:

local_4 = 10 * arg_0 + arg_4
eax = local_4
return

where obviously eax is specifically assigned a value before a return, so the last line can be

return eax

and finally the entire construction can be collapsed into

return 10 * arg_0 + arg_4

(which is very close to what I started with in the original trivial C program). I am struggling with the internal representation of composite lines such as the last one. The otherwise very reliable decompiler page backerstreet.com/creating_statements casually switches between raw assembler and C-like compound statements:

if(!expr1 && !expr2)
  ...

without explaining how this intermediate step is stored in memory and can create the output string.

What type of intermediate storage form should I be looking at, which (a) can be constructed from the original disassembled instructions, (b) can have its elements combined and rearranged, and (c) can be translated into human-readable output such as the last line?

It may be worth mentioning that I am not aiming to create the Definitive Universal Decompiler :) My test input was compiled with an ancient version (most likely pre-1993) of Delphi Pascal, but while its assembly is not really optimized and fairly readable to begin with, I'd still like to go the extra mile and make my computer do what it does best and make it yet easier to understand the code.

---

A longer real world example

Below is some actual disassembly. The basic block number is followed by a dominator bit set (the loops hex number; I generate them but have not used that data yet). The ENTRY and EXIT numbers are to basic blocks again and used to generate a .dot view of the function.

; ## BLOCK 0; loops: 01; EXIT to 1, 4
401966A8    (  0)  8B 15 42201590       mov     edx,dword ptr [42201590]
401966AE    (  0)  8B 12                mov     edx,dword ptr [edx]
401966B0    (  0)  80 BA 39 01 00 00 02 cmp     byte ptr [edx+139h],2
401966B7    (  0)  75 11                jnz     label_4

; ## BLOCK 1; loops: 03; ENTER from 0; EXIT to 2, 4
401966B9    (  0)  83 78 24 02          cmp     dword ptr [eax+24h],2
401966BD    (  0)  7D 0B                jge     label_4

; ## BLOCK 2; loops: 07; ENTER from 1; EXIT to 3=RET
401966BF    (  0)  BA 02 00 00 00       mov     edx,2
401966C4    (  0)  2B 50 24             sub     edx,dword ptr [eax+24h]
401966C7    (  0)  8B C2                mov     eax,edx

; ## BLOCK 3 (epilog); loops: 0F; ENTER from 2
401966C9          >C3                   retn    

; ## BLOCK 4; loops: 11; ENTER from 0, 1; EXIT to 5, 7
                        label_4:
401966CA    (  0)  8B 15 42201590       mov     edx,dword ptr [42201590]
401966D0    (  0)  8B 12                mov     edx,dword ptr [edx]
401966D2    (  0)  80 BA 39 01 00 00 01 cmp     byte ptr [edx+139h],1
401966D9    (  0)  75 0D                jnz     label_7

; ## BLOCK 5; loops: 31; ENTER from 4; EXIT to 6, 7
401966DB    (  0)  83 78 24 00          cmp     dword ptr [eax+24h],0
401966DF    (  0)  75 07                jnz     label_7

; ## BLOCK 6; loops: 71; ENTER from 5; EXIT to 8=RET
401966E1    (  0)  B8 01 00 00 00       mov     eax,1
401966E6    (  0)  EB 02                jmp     label_8

; ## BLOCK 7; loops: 91; ENTER from 4, 5; EXIT to 8=RET
                        label_7:
401966E8    (  0)  33 C0                xor     eax,eax

; ## BLOCK 8 (epilog); loops: 0111; ENTER from 6, 7
                        label_8:
401966EA          >C3                   retn    

401966EB                align 4

This is the .dot image; clear ifs are yellow, and the nodes contain their dominator bit sets so I can try and make sense of them (a TO-DO as yet). This explains the flow but you cannot see how much code each node represents.

The disassembly gets parsed into the following pseudo-code. Some notes are manually added.

; #### PARSED
401966A8    (  0)       edx = Main.UnitList@20551314 ;
401966AE    (  0)       edx = (dword)[edx] ;
401966B0    (  0)       if ((byte)[edx + 139h] != 2) goto label_4 ;

401966B9    (  0)       if ((dword)[eax + 24h] >= 2) goto label_4 ;

401966BF    (  0)       edx = 2 ;
401966C4    (  0)       edx -= (dword)[eax + 24h] ;
401966C7    (  0)       return edx ; MOV EAX,.. where an exit block follows

                        return ;  .. and this line is generated by the actual exit block

                    label_4:
401966CA    (  0)       edx = Main.UnitList@20551314 ;
401966D0    (  0)       edx = (dword)[edx] ;
401966D2    (  0)       if ((byte)[edx + 139h] != 1) goto label_7 ;

401966DB    (  0)       if ((dword)[eax + 24h] != 0) goto label_7 ;

401966E1    (  0)       eax = 1 ;
401966E6    (  0)       return ;  this was a jump-to-exit-block, so missed

                    label_7:
401966E8    (  0)       eax = 0 ; this was a XOR, not a MOV, so missed

                    label_8:
                        return ;

The loss in verbosity is already worth the effort: from 21 lines of code to 16 lines, even though the lookahead to check if EAX got written to right before a RET failed twice.

Yet, it is obvious that the two successive ifs at 401966B0 can be combined into a single one, with an OR. Inverting the condition, that whole block can be a single if and braced up to the return, removing label_4.
The manipulation of edx from 401966BF onwards can be concatenated into a single return statement.
Also, the if conditions at 401966D2 can be combined into a single one and put inside an if block. Since there is a return at its end, an else is not necessary there. Manually reconstructed:

401966A8    (  0)       edx = Main.UnitList@20551314 ;
401966AE    (  0)       edx = (dword)[edx] ;
401966B0    (  0)       if ((byte)[edx + 139h] == 2 &&
401966B9    (  0)           (dword)[eax + 24h] < 2)
                        {
401966BF    (  0)           return 2 - (dword)[eax + 24h] ;
                        }

401966CA    (  0)       edx = Main.UnitList@20551314 ;
401966D0    (  0)       edx = (dword)[edx] ;
401966D2    (  0)       if ((byte)[edx + 139h] == 1 &&
401966DB    (  0)          (dword)[eax + 24h] == 0)
                        {
401966E1    (  0)           return 1 ;
                        }

401966E8    (  0)       return 0 ;

reducing the original 21 lines to a mere 11. Furthermore, register value propagation resolves the references to the global class Main.UnitList. I manually created names for its elements; 401966A8 and forwards collapses into

401966B0    (  0)       if (Main.UnitList.flag == 2 &&
401966B9    (  0)           Main.UnitList.count < 2)

which makes the code practically readable.

^{Accessing eax before it gets written is not an error here. The function is a class function, and eax points to a class instance, so (dword)[eax + 24h] reads a data member of the structure. Main.UnitList is a pointer to a globally declared class instance, since it points into the BSS.}

Answer 1

For creating "humanly" readable expressions, i'd use an arithmetic parse tree. In fact, one separate parse tree for each of the registers and memory locations that are involved.

Every assignment copies the root of the target tree to the destination tree.

Every arithmetic operation creates a new root containing the operation, with the operands as the left & right child. The resulting tree is assigned to the target of the arithmetic operation.

Your example builds up like this:

From there, emitting the resulting formula is just a ltr tree walk. You'll probably want to simplify your expression first; you can replace an operator that has two constant subnodes with the operation result, and you might want to transform your tree by moving constants down where possible, like this:

              eax
               |
              add
               |
     +---------+--------+
     |                  |
    add                 5
     |                  
+----+-------+          
|            |
2           ebx


              eax
               |
              add
               |
     +---------+--------+
     |                  |
    add                ebx
     |                  
+----+-------+         
|            |
2            5

              eax
               |
              add
               |
     +---------+--------+
     |                  |
     7                 ebx

Google for "expression tree" and "constant folding" for more resources on this.

Mind that trees might be "self-referencing", especially in loops; the loop control variable will be seen at the top node, and somewhere down the tree as well. This is actually a good way to identify loop variables.

I'd probably start with trying to recognize basic blocks (everything that doesn't contain a jmp instruction or destination), and then build and dump the expression trees for these basic blocks. If you get this working well, you might continue by identifying stuff that stretches over several blocks, but is constant in some of them, like loops, to find out what's being built over the whole function.

EDIT: Another example, which shows how to treat register moves

A raw register move just copies the tree from the source register to the destination register. This is from an old watcom C program, compiled when imul was slow, and a series of shift/add instructions was faster; the compiler calculates var*45 here:

mov eax, [var]
mov edx, eax      <-- tree copy here (not much of a tree, however)
shl edx, 2
add eax, edx
mov edx, eax      <-- tree copy again
shl eax, 3
add eax, edx

Answer 2

What you're describing here is essentially the same as a static binary translator that uses a high level language such as C as its output target rather than a specific architecture. It's not quite as advanced a mechanism as decompiling but it has proven quite effective in restricted domains such as arcade video games. (eg http://vide.malban.de/vectrex-programs/vecfever ) There have been a few of these written; I have code for work in progress that does this for 6809, 6502, z80 and Cinematronic CPUs for example (though probably not immediately usable - it's a coming-together of four separate background projects with no great urgency). Anyway feel free to poke around and see if there's anything here that is helpful to you: http://gtoal.com/SBTPROJECT/ (the 6809 one is probably the cleanest code if you're just browsing and not actually running it)

There's a bit of a writeup of the overall method at http://gtoal.com/sbt/

Output looks something like this:

            //        LDA   $FFFF,X                 ; 0431: A6 1F         
      A = memory[(UINT16)(X + 0xffff)];
  //  N = A;
  //  Z = A;
  //  V = 0;

            //        LEAU  ,X                      ; 0433: 33 84         
      U = X;

            //        LDX   #$0EC8                  ; 0435: 8E 0E C8      
      X = 0x0ec8;
  //  Z = X;
  //  N = (X) >> 8;
  //  V = 0;

(the commented out lines are due to optimisation of redundant stores)

Rather than output functional code for execution, you could satisfy the OP's request by outputting comments that describe in detail what the operations are doing.

Other practical translators have been written by David Welch, Norbert Keher, Thomas Sontowski and others. There is also Project Orion which is a multi-person multi-target translator headed up by Neil Bradley (respected emulator author) and several other members of the Orion mailing list - that translator had working front ends for 6502 and z80, with 68000 and 6809 also being under development, and built an internal AST (Abstract Syntax Tree, much as described in one of the earlier answers in this thread) in order to output cleaner and more efficient code to a variety of back ends including C. (There is also some academic work produced by Christina Cifuentes et al.)

Graham

PS When the output is a generic IR (Internal Representation) such as C or LLVM's internal IR, as opposed to when you produce binary directly, or indirectly by outputting asm for a specific architecture) the technique is properly called "Compiled Instruction Set Simulation" - but most people just call it static binary translation.