Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Philippe Clauss Connect in order to contact the contributor
Submitted on : Wednesday, November 27, 2013 - 10:58:48 AM
Last modification on : Tuesday, October 25, 2022 - 4:20:46 PM

Links full text



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



Record views