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.