1. 5

Abstract: “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.”


  2. 1

    Meta: As in previous discussion about side effect of filters, I used CompSci and Programming instead of Fortran since it’s about a generic algorithm whose example just happened to be Fortran. Folks filtering fortran might like the generic algorithms, data structures, or whatever in these kinds of papers. So, I’m doing either just Programming or Programming + CompSci depending on source, nature of work, and so on. Sound reasonable @pushcx, @Irene, and @alynpost?

    1. 2

      Please tag the implementation language if we have the tag for it, and programming if there’s no implementation language or it’s one we don’t have a tag for. There’s something to learn about the fundamentals in just about every post and there’s no other good place to draw a clear line whether to use a language-specific tag or just compsci.

      1. 1

        Thanks for the response. Will do! :)