PCO: Dynamic analysis and optimization

Collaborative Static and Dynamic analysis for feedback-directed optimisations

Profiling a program consists in collecting opportune informations during its execution in order to guide efficient optimizations (dead code elimination, prefetching, instruction scheduling, memory layout transformation, ...). Those optimisations can be applied either by transforming the initial source code or by re-compiling it guided by the collected informations.

Profiling is essential when optimizing codes where dynamic control structures occur and for which static analysis is inadequate. But this approach has several drawbacks :

Preliminary executions can be very time-consumable. Moreover initial versions of programs have not been optimized yet.
The computation volume during profiling is often small compared to real executions for the above reason. Hence collected informations can lead to program transformations that would be inadequate for larger computations.
Interactions between optimizations of the initial code are often not considered although some transformations applied on some parts can have bad effects on some other parts.
Existing profiling tools collect global informations that can be slightly refined. Static analysis should be used in order to guide the profiling process in order to eliminate any useless tracing and to refine useful observations.

Our objective is to develop some automatic methods for collaborative static and dynamic analysis of programs :

Static analysis adaptation and extensions allowing to focus the profiling process on presumed expensive parts of the initial code and allowing to identify some possible interactions,
Automatic generation of entries guiding the profiling process,
Development of a customizable profiling software,
Validation of the approach by applying some optimizations guided by the static/dynamic analysis results.

We recently proposed a model of program behavior capture called the periodic-linear model (PLI). Program profiling traces are analyzed and represented as periodic-linear functions that exhibit useful information about periodicity and repetitive behaviors of the analyzed program. Moreover, the whole trace is represented as a sequence of loop nests that constitutes a rich analysis and optimization framework. More details and the current software implementation can be found here.

Ph. Clauss, B. Kenmei and J.C. Beyler, The Periodic-Linear Model of Program Behavior Capture, Euro-Par 2005, LNCS 3648, pages 325-335, Springer, Lisboa, Portugal, September 2005.
Ph. Clauss, Bénédicte Kenmei Youta and Odile Rousselet, Modeling Program Traces with Nested Loops, Workshop on Exploring the Trace Space for Dynamic Optimization Techniques, held in conjunction with ICS'03, San Francisco, USA, june 2003.