||Data Flow Analysis using Program Graphs
||Nielson, Hanne Riis (Language-Based Technology, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||Static code analysis is a powerful formal method of analysing software without
actually executing any code. It is very commonly used in compilers, but also
for bug detection and software verification purposes. Moreover, because of the
complexity of today's software, it is becoming more and more popular as a way
for ensuring higher code quality.
Data Flow Analysis is a technique for statically gathering/predicting the possible
sets of values at various points in the program, that would arise at the program
execution. In the standard approach the analysed program is transformed into
ow graph, where labeled blocks are nodes and edges represent control
Such a graph is then the basis for various analyses. This thesis explores the
idea of using program graphs for that purpose. In this case the blocks/actions
are associated with the edges and the nodes are simply labels. One of the main
advantages of this approach is the ability to easily compose multiple graphs and
then analyse the resulting one. So by redefining some classical analyses to work
on program graphs, it is possible not only to analyse sequential programs, but
also shared memory environments with concurrently executing processes.
The thesis defines the program graphs, shows how they can be then merged and
presents their semantics. It uses a simple imperative programming language
While and elaborates on how programs can be transformed into a program
graphs. Moreover it redefines a number of classical analyses to work on such
graphs, including Reaching Definitions, Live Variables and Constant Propagation. Finally, some interesting examples of analysing well known algorithms are
The thesis also includes an implementation of the presented ideas and analyses.
It is a web application written in Haskell, which helps to demonstrate how the
approach works in practice and what are its advantages.
||Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Creation date: 2010-06-03
Update date: 2010-06-03