Record Details

Comprehensive Path-sensitive Data-flow Analysis

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Comprehensive Path-sensitive Data-flow Analysis
 
Creator Thakur, Aditya
 
Subject Compilers
Data-flow Analysis
Control-flow Graphs
Automata Theory
Destructive Merge
Scale Compiler
Split Approach
Complex Control-flow
Computer Science
 
Description Data-flow analysis is an integral part of any aggressive optimizing compiler. We propose a framework for improving the precision of data-flow analysis in the presence of complex control-flow. We initially perform data-flow analysis to determine those control-flow merges which cause the loss in data-flow analysis precision. The control-flow graph of the program is then restructured such that performing data-flow analysis on the resulting restructured graph gives more precise results. The proposed framework is both simple, involving the familiar notion of product automata, and also general, since it is applicable to any forward or backward data-flow analysis. Apart from proving that our restructuring process is correct, we also show that restructuring is effective in that it necessarily leads to more optimization opportunities.
Furthermore, the framework handles the trade-off between the increase in data-flow precision and the code size increase inherent in the restructuring. We show that determining an optimal restructuring is NP-hard, and propose and evaluate a greedy heuristic.
The framework has been implemented in the Scale research compiler, and instantiated for the specific problems of Constant Propagation and Liveness analysis. On the SPECINT 2000 benchmark suite we observe an average speedup of 4% in the running times over Wegman-Zadeck conditional constant propagation algorithm and 2% over a purely path profile guided approach for Constant Propagation. For the problem of Liveness analysis, we see an average speedup of 0.8% in the running times over the baseline implementation.
 
Contributor Govindarajan, R
 
Date 2010-08-25T05:24:08Z
2010-08-25T05:24:08Z
2010-08-25
2008-07
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/836
 
Language en_US
 
Relation G22613