Validity of Interprocedural Data Remapping

Programming languages like Fortran or C define exactly the layout of array elements in memory. Programmers often use that definition to access the same memory via variables declared as arrays of different types. This is done, for instance, to access a slice of larger array or to access data as a linear array, so that subscript computation is simpler giving performance improvements on some architectures and allowing the use of single procedure to perform some operation (e.g., copying) on variables of different types. For many real programs this practice makes changing the layout of an array impossible without violating the semantics of the program since the same memory block may be accessed via a variable of a different type---such an access will now receive wrong array elements. On the other hand, changing array layout is often necessary to obtain good parallel performance or even to improve sequential performance by providing better cache locality. The techniques that achieve that range from manually inserted array distribution directives to automatic compiler transformations. Our paper demonstrates that the problem of changing array layouts in the presence of multiple variables of different types accessing the same memory can be solved with our algorithms for 1) detecting overlapping arrays, 2) using procedure cloning to reduce overlapping, 3) array type coercion, and 4) code structure recovery. We describe the algorithms used in our compiler and present experimental results showing speedups which are not possible with other techniques