Reversing : The Hacker's Guide to Reverse Engineering

One prominent feature of SSA is its support of φ-functions (pronounced “fy

functions”). φ-functions are positions in the code where the value of a register

is going to be different depending on which branch in the procedure is taken.

φ-functions typically take place at the merging point of two or more different

branches in the code, and are used for defining the possible values that the

specific registers might take, depending on which particular branch is taken.

Here is a little example presented in IA-32 code:

mov esi 1 , 0 ; Define esi 1

cmp eax 1 , esi 1

jne NotEquals

mov esi 2 , 7 ; Define esi 2

jmp After

NotEquals:

mov esi 3 , 3 ; Define esi 3

After:

esi 4 = ø(esi 2 , esi 3 ) ; Define esi 4

mov eax 2 , esi 4 ; Define eax 2

In this example, it can be clearly seen how each new assignment into ESI

essentially declares a new logical register. The definitions of ESI2and ESI3

take place in two separate branches on the control flow graph, meaning that

only one of these assignments can actually take place while the code is run-

ning. This is specified in the definition of ESI4, which is defined using a

φ-function as either ESI2or ESI3, depending on which particular branch is

actually taken. This notation simplifies the code analysis process because it

clearly marks positions in the code where a register receives a different value,

depending on which branches in the control flow graph are followed.

Data Propagation

Most processor architectures are based on register transfer languages(RTL),

which means that they must load values into registers in order to use them.

This means that the average program includes quite a few register load and

store operations where the registers are merely used as temporary storage to

enable certain instructions access to data. Part of the data-flow analysis

process in a decompiler involves the elimination of such instructions to

improve the readability of the code.

Let’s take the following code sequence as an example:

mov eax, DWORD PTR _z$[esp+36]

lea ecx, DWORD PTR [eax+4]

mov eax, DWORD PTR _y$[esp+32]

cdq

468 Chapter 13