The design and implementation of an accurate array data-flow analyzer in the HPC compiler

Parallelizing compilers are increasingly relying on accurate data dependence information to exploit parallelism. This thesis addresses the problem of array data-flow analysis which provides more accurate information than traditional scalar data-flow analysis and array data dependence analysis. We describe the design and implementation of an array data-flow analyzer which has been integrated into our HPC compiler. The HPC compiler automatically parallelizes programs written in the HPC language, an extension of the C language, and generates SPMD codes for distributed memory machines. Two other important parts of the compiler, the automatic data and computation decomposition tool and the SPMD code generator, use the array data-flow information.We introduce the array data-flow representation source tree which allows us to compute array data-flow information more effectively and efficiently. We perform array data-flow computation from the highest dependence level to the lowest dependence level and sequence the writes by lexicographical order in the presence of multiple writes. The check of a source tree against the coverage conditions allows us to avoid any further computation once the sources have been found.We introduce our global array data-flow analysis to compute array data-flow information beyond a single loop nest. This is useful for advanced program transformation and optimizations in the scope of a cluster of loop nests.We have investigated the pragmatic issues of applying Feautrier's method in the HPC compiler framework. We have performed experiments of both local array data-flow analysis and global array data-flow analysis on seven programs of the Perfect Benchmarks, under the platform of the HPC compiler. The experimental results show that our method has acceptable performances for analyzing scientific and engineering applications