An interactive system for program dependence analysis

Since the introduction of parallel computers system, designers have been trying to make parallel programming easier. Several efforts have taken place in easing the burden of programmers who target supercomputers for their applications: (1) implementation of high level languages, (2) design of tools to aid in programming, and (3) the use of low level programming interfaces specific for to architecture. The desired approach to producing code for a particular architecture is dependent on many factors including the skill level of the programmer and the effort required to produce the correct code. However, there is also another problem domain. There exists many applications that have been written for the scientific and engineering communities that were originally designed for sequential architectures. Some of this code is still essential to scientific research and the efficiency of that research could be improved if the runtime of the code could be reduced, therefore allowing the scientist to concentrate on analysis. It is, therefore, desirable for some of these applications to be "ported" to some current su-percomputer architecture. The porting of this complex scientific code would potentially take many man years, especially when dealing with supercomputers and their program-ming environments. This problem has inspired an area of research focused around designing supercompilers. A supercompiler transforms code written in sequential pro-gramming languages into optimized code for use on a particular target supercomputer. With the success of supercompiler technology the burden of programmers could poten-tially be eased. Given the idiosyncrasies of supercomputer programming environments, if a programmer could write sequential code and have the compiler do the transforma-tion to the parallel environment these architectures would potentially be more widely used. Minimally, the use of these computers could be spread to programmers who are less familiar with the details of a particular architecture. One of the most important areas of interest inside of supercompiler research is depen-dence analysis. In dependence analysis the compiler tries to determine if there exists a dependence between two or more expressions, usually inside of a loop, in order to facilitate the production of parallel or vector code for the target machine. Current algo-rithms used in dependence analysis use a data flow system in a feed-forward manner. In other words, they proceed from the top of the control flow graph and propagate informa-tion forward. This thesis presents a backward-chaining algorithm as another approach which has the potential to uncover some independent expressions that would otherwise be inaccessible to conventional dependence algorithms. Also presented is an interactive environment for testing the application of the proposed algorithms inside a compiler.