TODO

Read [ 2004 ] : Using Hammock Graphs to Structure Programs

paper

%3 cluster_9089990a_4b6d_4b56_a778_410c439013d5 Read [2004]: Using Hammock Graphs to Structure Programs _50592515_2079_46c9_b168_c704c5ad3e38 Programs as Graphs _c66b0d34_4029_483d_a307_6e18505c3ec7 Compilers _50592515_2079_46c9_b168_c704c5ad3e38->_c66b0d34_4029_483d_a307_6e18505c3ec7 __0:cluster_9089990a_4b6d_4b56_a778_410c439013d5->_50592515_2079_46c9_b168_c704c5ad3e38 __1:cluster_9089990a_4b6d_4b56_a778_410c439013d5->_c66b0d34_4029_483d_a307_6e18505c3ec7 

Advanced computer architectures rely mainly on compiler optimizations for
parallelization, vectorization, and pipelining.

Efficient code generation is based on a control dependence analysis to find
the basic blocks and to determine the regions of control. However,
unstructured branch statements, such as jumps and goto’s, render the control
flow analysis difficult, time-consuming, and result in poor code generation.

Branches are part of many programming languages and occur in legacy and
maintenance code as well as in assembler, intermediate languages, and byte
code. A simple and effective technique is presented to convert unstructured
branches into hammock graph control structures. Using three basic
transformations, an equivalent program is obtained in which all control
statements have a well-defined scope.

In the interest of predication and branch prediction, the number of control
variables has been minimized, thereby allowing a limited code replication.
The correctness of the transformations has been proven using an axiomatic
proof rule system.

With respect to previous work, the algorithm is simpler and the branch
conditions are less complex, making the program more readable and the code
generation more efficient. Additionally, hammock graphs define single entry
single exit regions and therefore allow localized optimizations. The
restructuring method has been implemented into the parallelizing compiler FPT
and allows to extract parallelism in unstructured programs. The use of
hammock graph transformations in other application areas such as
vectorization, decompilation, and assembly program restructuring is also
demonstrated.

Existing front-end compiler methods are directed towards loop normalization
[3] and goto elimination [13].

[...]

The present method is a front-end approach which repairs unstructured
regions by creating hammock graph structures in the control flow graph.

The conversion of the program is based on three elementary transformations,
namely, the backward copy, forward copy, and cut operations.

The transformations reorganize the program into a set of nested hammock
graphs, each having a single entry and a single exit.