SSA Back-Translation

Abstract

A compiler translates one representation of a software program into another. Beside translation compilers often have other tasks such as optimizating the result and warning the programmer for mistakes. Internally a compiler uses an Intermediate Representation (IR) for analysis and manipulation of the program at hand. Data dependencies in most programming languages are implicit. Some compilers use an IR in Static Single Assignment (SSA) in which each local variable is only defined once to simplify analysis of data dependencies. If the number of assignments in the IR is not restricted, it is said to be in normal form. Input of a compiler is in normal form and translation is needed to bring the IR in SSA form. SSA-form contains phi functions to merge values based on control flow. After optimizations on SSA-form are performed it is not trivial to translate SSA-form back to normal form because the properties of phi nodes cannot be translated directly to processor instructions. The algorithms of Briggs and Sreedhar are the two major methods of back-translation. This thesis presents a modification that can be applied to the methods of Briggs and Sreedhar. The original methods append copy instructions to the end of existing source blocks. The presented modification splits edges between source and target by inserting phiblocks where the algorithms of Sreedhar and Briggs emit copy operations to replace phi functions. For this study a bridge between LLVM and CoSy was built such that LLVM can be used for the optimizations on SSA-form and CoSy for the post back-translation optimizations. Four back-translation algorithms are implemented in CoSy. The methods are compared through experiments with six testcases from the SPEC benchmark suite. On average the presented modification reduces the execution time of the resulting code with 5% for Briggs’ method and 3% for Sreedhar’s method. Experiments also show that the result of back-translation with or without phiblocks is suboptimal: repeating optimizations after back-translation that were already done on the IR in SSA-form can reduce the execution time on average with 18%.