A GENERALIZED THEORY OF BIT VECTOR DATA-FLOW ANALYSIS

被引:29
作者
KHEDKER, UP [1 ]
DHAMDHERE, DM [1 ]
机构
[1] INDIAN INST TECHNOL,DEPT COMP SCI & ENGN,BOMBAY 400076,MAHARASHTRA,INDIA
来源
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS | 1994年 / 16卷 / 05期
关键词
BIDIRECTIONAL DATA FLOWS; DATA FLOW ANALYSIS; DATA FLOW FRAMEWORKS;
D O I
10.1145/186025.186043
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:1472 / 1511
页数:40
相关论文
共 27 条
[1]  
Aho A.V, 1986, COMPILERS PRINCIPLES
[2]  
ALLEN FE, 1977, COMMUN ACM, V19, P137
[3]   A COMPARISON OF SOME ALGORITHMS FOR LIVE VARIABLE ANALYSIS [J].
BISWAS, S ;
BHATTACHARJEE, GP ;
DHAR, P .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1980, 8 (02) :121-134
[4]  
CHOW FC, 1988, SIGPLAN NOTICES, V23, P85, DOI 10.1145/960116.53999
[5]   REGISTER ASSIGNMENT USING CODE PLACEMENT TECHNIQUES [J].
DHAMDHERE, DM .
COMPUTER LANGUAGES, 1988, 13 (02) :75-93
[6]  
DHAMDHERE DM, 1988, SIGPLAN NOTICES, V23, P172, DOI 10.1145/51607.51621
[7]   AN ELIMINATION ALGORITHM FOR BIDIRECTIONAL-DATA FLOW PROBLEMS USING EDGE PLACEMENT [J].
DHAMDHERE, DM ;
PATIL, H .
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1993, 15 (02) :312-336
[8]   PRACTICAL ADAPTATION OF THE GLOBAL OPTIMIZATION ALGORITHM OF MOREL AND RENVOISE [J].
DHAMDHERE, DM .
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1991, 13 (02) :291-294
[9]  
DHAMDHERE DM, 1992, ACM SIGPLAN 92
[10]   FAST AND USUALLY LINEAR ALGORITHM FOR GLOBAL FLOW ANALYSIS [J].
GRAHAM, SL ;
WEGMAN, M .
JOURNAL OF THE ACM, 1976, 23 (01) :172-202