CW 360

Peter Vanbroekhoven, Gerda Janssens, Maurice Bruynooghe, Henk Corporaal, Francky Catthoor
A Step towards a Scalable Dynamic Single Assignment Conversion

Abstract

In classic compiler optimizations, the static single assignment form of a program is an important intermediate form for doing code transformations. The idea of single assignment is to discard all the limitations because of the reuse of memory locations. When multiple values are stored in a single memory location during the run of a program, it is necessary that the statements that want to store the values take a certain protocol into account so they do not overwrite each other's values. This constrains the order in which reads and writes can happen as well as the transformations that try to change their order. Hence removing reuse of memory locations removes those limitations. Static single assignment does this in a textual way, but this is not enough for global optimizations like loop transformations. For this we need dynamic single assignment which discards all reuse of memory locations during execution of a program. Although methods exist to transform a program to dynamic single assignment, they are either limited in applicability or they are computationally too expensive when aplied to larger, real-life programs. Hence we are developing a new method where the resulting program is different from that resulting from existing methods. The method however is computationally less expensive, is more generally applicable but does not endanger the possibility for optimization. In this technical report we describe how the new dynamic single assignment transformation is split up in three separate transformation steps. Then we describe an automizable method for each of these transformation steps. Finally a sketch is given about extensions and refinements to these method, which will be part of future work.