Dependency Analysis for Assembly Languages Seminars/Workshops

Abstract

1. ParaMod---Data Dependence Analysis in Programs with Pointers

Global objective of the ParaMod project is the development of a complete paralleliezer for arbitrary in Modula-2 written programs. The choice for Modula-2 has been motivated by the fact that in Modula-2 the very problematical treatment of pointer arithmetic can be fade out completely. A transmission of our techniques to a parallelization of programs written in other imperative languages like C, FORTRAN 90 and JAVA seems possible.

In the ParaMod project we developed a method for data dependence analysis in programs with pointers. Our method is based on storage representations called A/D graphs, that cover both reaching definitions and alias information simultaneously. The developed technique can be integrated into most current compilers, as it is based on a well-known algorithm of static analysis---a monotone data flow system. This fact strengthens the practical utility of our approach. Initial experiments show the accuracy and speed of a data dependence analysis with A/D graphs.

In cooperation with the research group 'Advanced Analysis and Code Optimization' of the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, France, we develop in the ADAM project advanced techniques for data dependence analysis of assembler code.

Determination of data dependences is a task typically performed with high-level language source code in today's optimizing and parallelizing compilers. Very little work has been done in the field of data dependence analysis on assembly language code, but this area will be of growing importance, e.g. for increasing ILP. A central element of a data dependence analysis in this case is a method for memory reference disambiguation which decides whether two memory operations may/must access the same memory location.

In ADAM we have developed a new technique of data dependence analysis for machine code. Our method is based on a sophisticated algorithm for symbolic value propagation---an extention of the well-known constant propagation algorithm, and it can derive value-based dependences between memory operations instead of address-based dependences, only.

We have integrated our method into the Salto system for assembly language optimization. SALTO is a framework to develop optimization and transformation techniques for various processors. First experimental results show that our approach greatly improves the accuracy of the dependence analysis in many cases.