Analyse des pointeurs pour le langage C

Abstract : Static analysis algorithms strive to extract the information necessary for the understanding and optimization of programs at compile time. The potential values of the variables of type pointer are the most difficult information to determine. This information is often used to assess if two pointers are potential aliases, i.e. if they can point to the same memory area. An analysis of pointers, also called points-to analysis, may provide more precision to other analyses such as constant propagation, analysis of dependencies or analysis of live variables. The analysis of pointers is very important for the exploitation of parallelism in scientific C programs since the most important structures they manipulate are arrays, which are typically accessed by pointers. It is necessary to analyse the dependencies between arrays in order to exploit the parallelism between loops. C language is very hard to analyse since it allows to users to manipulate the memory through pointers. These difficulties arise for example when accessing arrays by pointers, dynamic allocation (via "malloc") and recursive data structures. Points-to analysis may also attempt to handle recursive data structures and other structures that are accessed by pointers. This work provides a points-to analysis which is : - flow-sensitive, by taking into account the order of execution of instructions ; - field-sensitive, since structure fields are treated as individual locations ; - context-insensitive, because functions summaries are computed to avoid re-analyzing functions bodies. Other issues such as heap modeling, pointer arithmetics and pointers to arrays are also taken into account while analyzing C programs. Our intraprocedural analysis provides precise results to client analyses, in particular it allows parallelization when accessing the array elements loops via pointers, detecting useless code or computing the dependency graph. while our interprocedural one allows to propagate them efficiently. Our work is implemented within the PIPS (Parallélisation Interprocédurale de Programmes Scientifiques) parallelizer, a framework designed to analyze, optimize and parallelize scientific and signal processing applications. Keywords : static analysis, points-to analysis, flow-sensitive, context-insensitive, field-sensitive.
Document type :
Theses
Complete list of metadatas

Cited literature [66 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00944703
Contributor : Abes Star <>
Submitted on : Tuesday, February 11, 2014 - 9:33:08 AM
Last modification on : Monday, November 12, 2018 - 11:02:34 AM
Long-term archiving on : Monday, May 12, 2014 - 2:00:14 AM

File

2012ENMP0104.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : pastel-00944703, version 1

Citation

Amira Mensi. Analyse des pointeurs pour le langage C. Autre [cs.OH]. Ecole Nationale Supérieure des Mines de Paris, 2013. Français. ⟨NNT : 2013ENMP0032⟩. ⟨pastel-00944703⟩

Share

Metrics

Record views

850

Files downloads

2171