Beta 1


Title Data Flow Analysis using Program Graphs
Author Terepeta, Michal
Supervisor Nielson, Hanne Riis (Language-Based Technology, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Napieralski, Andrzej
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2010
Abstract 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 a ow graph, where labeled blocks are nodes and edges represent control ow. 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 presented. 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.
Imprint Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Series IMM-M.Sc.-2010-33
Fulltext
Original PDF ep10_33_net.pdf (1.36 MB)
Admin Creation date: 2010-06-03    Update date: 2010-06-03    Source: dtu    ID: 262937    Original MXD