Record Details

A GENERALIZED THEORY OF BIT VECTOR DATA-FLOW ANALYSIS

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A GENERALIZED THEORY OF BIT VECTOR DATA-FLOW ANALYSIS
 
Creator KHEDKER, UP
DHAMDHERE, DM
 
Subject strength reduction transformation
global program optimization
path problems
algorithm
frameworks
bidirectional data flows
data flow analysis
data flow frameworks
 
Description The classical theory of data flow analysis, which has its roots in unidirectional flows, is inadequate to characterize bidirectional data flow problems. We present a generalized theory of bit vector data flow analysis which explains the known results in unidirectional and bidirectional data flows and provides a deeper insight into the process of data flow analysis. Based on the theory, we develop a worklist-based generic algorithm which is uniformly applicable to unidirectional and bidirectional data flow problems. It is simple, versatile, and easy to adapt for a specific problem. We show that the theory and the algorithm are applicable to all bounded monotone data flow problems which possess the property of the separability of solution. The theory yields valuable information about the complexity of data flow analysis. We show that the complexity of worklist-based iterative analysis is the same for unidirectional and bidirectional problems. We also define a measure of the complexity of round-robin iterative analysis. This measure, called width, is uniformly applicable to unidirectional and bidirectional problems and provides a tighter bound for unidirectional problems than the traditional measure of depth. Other applications include explanation of isolated results in efficient solution techniques and motivation of new techniques for bidirectional flows. In particular, we discuss edge splitting and edge placement and develop a feasibility criterion for decomposition of a bidirectional flow into a sequence of unidirectional flows.
 
Publisher ASSOC COMPUTING MACHINERY
 
Date 2011-07-18T19:54:12Z
2011-12-26T12:50:48Z
2011-12-27T05:36:54Z
2011-07-18T19:54:12Z
2011-12-26T12:50:48Z
2011-12-27T05:36:54Z
1994
 
Type Article
 
Identifier ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 16(5), 1472-1511
0164-0925
http://dx.doi.org/10.1145/186025.186043
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5045
http://hdl.handle.net/10054/5045
 
Language en