Recovering memory access patterns of executable programs

Alain Ketterlin 1, 2, 3 Philippe Clauss 1, 2, 3
3 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : This paper deals with the binary analysis of executable programs, with the goal of understanding how they access memory. It explains how to statically build a formal model of all memory accesses. Starting with a control flow graph of each procedure, well-known techniques are used to structure this graph into a hierarchy of loops in all cases. The paper shows that much more information can be extracted by performing a complete data-flow analysis over machine registers after the program has been put in static single assignment (SSA) form. By using the SSA form, registers used in addressing memory can be symbolically expressed in terms of other previously set registers. By including the loop structures in the analysis, loop indices and trip counts can also often be expressed symbolically. The whole process produces a formal model made of loops where memory accesses are linear expressions of loop counters and registers. The paper provides a quantitative evaluation of the results when applied to several dozens of SPEC benchmark programs. Because static analysis has no access to input data, the paper ends by describing a lightweight instrumentation strategy that collects at run time enough information to rebuild an exact trace. The section on applications also describes how the techniques developed in this paper can be used to perform automatic parallelization of binary code.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Philippe Clauss <>
Soumis le : mercredi 27 novembre 2013 - 10:58:48
Dernière modification le : jeudi 29 mars 2018 - 09:10:05




Alain Ketterlin, Philippe Clauss. Recovering memory access patterns of executable programs. Science of Computer Programming, Elsevier, 2014, 80, pp.440-456. 〈〉. 〈10.1016/j.scico.2012.08.002〉. 〈hal-00909961〉



Consultations de la notice