Program analysis and transformation: beyond the Polytope Model

Albert Cohen

Compilation for todays microprocessor and multi-processor architectures is facing new challenges. Dealing with parallel execution, optimizations become overly specific and complex to be left to the programmer. Traditionally devoted to numerical applications, automatic parallelization addresses new program models, including non-affine nests of loops, recursive calls and pointer-based data structures. Parallelism detection is based on precise analyses, gathering compile-time information about run-time program properties. This information enables transformations useful to parallelism extraction and parallel code generation. We focus on aggressive analysis and transformation techniques from an instancewise point of view, that is from individual properties of each run-time instance of a program statement. Thanks to a novel formal language framework, we first investigate instancewise dependence and reaching definition analysis for recursive programs. This analysis is applied to memory expansion and parallelization of recursive programs, and promising results are exposed.

Details in PhD thesis.