|
 ABSTRACT
Our exhaustive and incremental hybrid data flow analysis algorithms, based on iteration and elimination techniques, are designed for incremental update of a wide variety of monotone data flow problems in response to source program changes. Unlike previous incremental iterative methods, this incremental algorithm efficiently computes precise and correct solutions. We give theoretical results on the imprecision of restarting iteration for incremental update by fixed point iteration which provided motivation for our algorithm design. Described intuitively, the main algorithm idea is to factor the data flow solution on strong connected components of the flow graph into local and external parts, solving for the local parts by iteration and propagating these effects on the condensation of the flow graph to obtain the entire data flow solution. The incremental hybrid algorithm re-performs those algorithm steps affected by the program changes.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
|
 |
2
|
|
| |
3
|
|
| |
4
|
M. Burke. An interval analysis approach toward exhaustive and incremental interprocedural data flow analysis. Technical Report RC 12702, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., July, 1987.
|
| |
5
|
|
| |
6
|
M. Burke, B.G. Ryder. Incrementa/ iterative data flow analysis algorithms, Laboratory for Computer Sckmce Research Technical Report LCSR-TR-96, Rutgers University, New Brunswick, N.J., 1987.
|
| |
7
|
|
| |
8
|
|
| |
9
|
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
T.J. Marlowe. Incremental iteration and data flow analysis. PhD thesis, Department of Computer Science, Rutgers University, 1989.
|
| |
17
|
|
| |
18
|
|
| |
19
|
Lori L. Pollock , Mary Lou Soffa, INCOMINANT—an INCRemental Optimizer for Machine Independent Transformation, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.162-171, December 1985, San Francisco, California, United States
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
| |
23
|
B. Rosen. A lubricant for data flow analysis. SIAM Journal of Computing 11(3):493-511, 1982.
|
| |
24
|
|
| |
25
|
|
| |
26
|
|
| |
27
|
|
| |
28
|
J.T. Schwartz, M. Shadr. A design for optimizations of the bitvectoring class. Courant Computer Science Report 17, New York University, New York. N.Y., 1979.
|
| |
29
|
|
| |
30
|
|
| |
31
|
|
CITED BY 35
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gregg Rothermel , Lixin Li , Christopher DuPuis , Margaret Burnett, What you see is what you test: a methodology for testing form-based visual programs, Proceedings of the 20th international conference on Software engineering, p.198-207, April 19-25, 1998, Kyoto, Japan
|
|
|
|
|
|
|
|
|
Jyh-shiarn Yur , Barbara G. Ryder , William A. Landi, An incremental flow- and context-sensitive pointer aliasing analysis, Proceedings of the 21st international conference on Software engineering, p.442-451, May 16-22, 1999, Los Angeles, California, United States
|
|
|
Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jyh-Shiarn Yur , Barbara G. Ryder , William A. Landi , Phil Stocks, Incremental analysis of side effects for C software system, Proceedings of the 19th international conference on Software engineering, p.422-432, May 17-23, 1997, Boston, Massachusetts, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.3