Structuring Overview¶

Introduction¶

Academically introduced in Dr. Cifuentes' 1994 Dissertation¹, decompilation control flow structuring is the process used to turn a control flow graph (CFG) into a structured high-level language. Control flow structuring in decompilation is highly related to the general control flow structuring process found in compiler research. Although the goal of control flow structuring, referred to as structuring, is to output linear high-level code, the level of abstraction of that code is open research. Additionally, few works exist in structuring for targeting language output other than C.

General Structuring Example¶

Although often thought of in the context of assembly, control flow structuring requires a control flow graph and conditions ³. For example, the attributed control flow graph below can be used as input:

                            +-----+
                            |  A  |
                            +-----+
                              |   |
                           ~x |   +--+
                              V      |
                         +-----+     |
                         |  B  |     | x
                         +-----+     |
                           |  +--+   |
                        ~y |     | y |
                           V     V   V
                       +-----+  +-----+
                       |  D  |  |  C  |
                       +-----+  +-----+
                            |    |
                            V    V
                            +-----+
                            |  E  |
                            +-----+

Using a schmea-based structuring algorithm, the graph can be turned into the following C:

A();
if(x)
    goto label_c;
B();
if (y) {
label_c:
    C();
}
else {
    D();
}
E();

There are multiple ways of turning the graph into linear C code ⁴. For instance, the first condition on x can be flipped, changing where the goto appears and how many if scopes exist in the program.

Types of Structuring¶

There are two dominant types of structuring algorithms⁸:

1. Schema-based: Algorithms that construct code based on pre-known graph patterns that are omitted by compilers. These algorithms attempt to only make structured code when they are aware of a direct mapping to its source structure.
2. Gotoless: Algorithms that prioritize removing all unstructured regions from code. These algorithms may use schema-based methods initially but are unique in their pattern-matching of structures that may not exist in its source.

The biggest difference between these two is their reliance on known compiler patterns⁵. In schema-based algorithms, the decompiler author creates a set of known compiler output patterns to recover a target language. In gotoless algorithms, the decompiler author uses patterns outside of graph schemas, which may be compiler and language-independent. One such example is condition-based structuring, as used in the DREAM ⁵ decompiler.

Related Fields¶

Structuring in decompilation was directly inspired by compiler works in structuring and general data-flow analysis³. One of these earliest works was the 1970s paper "Control flow analysis."², which laid out the fundamental ideas for constructing control flow graphs. Additionally, many of the ideas for eliminating gotos, which were often a byproduct of schema-based structuring, were inspired by work in restructuring source code^{6 7}.