|
Cover summary
-
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.
This thesis focuses 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. The second part of this work
addresses nests of loops with unrestricted conditionals, bounds
and array subscripts. Parallelization via memory expansion is
revisited in this context and solutions to challenging
optimization problems are proposed.
|