|
 ABSTRACT
We present an algorithm for updating data flow information derived from a program, in response to program edits. Our algorithm, applicable to intraprocedural or interprocedural data flow problems, is more general than previous methods because it can update any monotone data flow problem defined on a reducible flow graph and can handle arbitrary program edits.
Rather than design yet another special-purpose data flow update algorithm, we show how to reduce the class of data flow problems to another class of problems which already has a fast update algorithm. More specifically, we reduce a monotone data flow problem formulated for solution using Graham-Wegman elimination [12] to the problem of constructing and decorating an attributed tree structurally isomorphic to the dominator tree of the program flow graph.
To update this dominator tree in response to program changes, we first show how to express domination in terms of two local properties of nodes and edges in the flow graph — niceness and deepness. Domination is then updated in response to an edge addition or deletion by repeatedly performing two local operations on the dominator tree, each operation restoring the local properties violated by the edge change. Second, we extend Reps' attributed tree update techniques [19,21,20] and his complexity analysis, to update attribute values in response to changes in this structure.
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
|
B. Alpern, A. Curie, B. Rosen, P. Sweeney, and F. Zadeck. Incremental Evaluation of Attributed Graphs. Unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1987.
|
| |
3
|
W. Babich and M. Jazayeri. The method of attributes for data flow analysis~ part l: exhaustive analysis. Act.a Informatica, 10:245-264~ 1978.
|
| |
4
|
W. Babich and M. Jazayeri. The method of attributes for data flow analysis~ part H: demand analysis. Acta Informatica, 10:265-272, 1978.
|
| |
5
|
M. Burke. An Interval-based Approach to Ezhaustive and incremental Interprocedural Data Flow Analysis. Computer Science Technical Report RC12701, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, April 1987.
|
| |
6
|
M. Burke and B. Ryder. Incremental Iterative Data Flow Analysis Algorithms. Technical Report LCSR-093, Department of Computer Science, Rutgers University, July 1987. Also available as Computer Science Technical Report RC13730, IBM Thomas J. Watson Research Center, Yorktown Heights, New York.
|
| |
7
|
M. Carroll. Dataflow Update via Attribute and Dornina. tar Updates. PhD thesis, Department of Computer Science, Rutgers University, 1987. In preparation.
|
| |
8
|
|
 |
9
|
|
| |
10
|
S. Even and H. Gazit. Updating distances in dynamic graphs. 1984. Unpublished manuscript.
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
J. Kam and J. Ullman. Monotone data flow analysis frameworks. Acta In}orma$ica, 7:305-317, 1977.
|
| |
16
|
|
| |
17
|
|
| |
18
|
L. Pollock and M. Sofia. An Incremental Version of Iteratire Data Flow Analysis. Computer Science Techmc~l Report 87-58, Department of Computer Science~ Rice University, August 1987.
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
| |
22
|
B. Rosen. Monoids for rapid data flow analysis. SlAM Journal of Computing, 9(1):159-196, November 1980.
|
| |
23
|
B. Ryder. Art application of static program analysis to software maintenance. In B. D. Shriver, editor, Proceedings of the Twentieth Hawaii International Conference on System Sciences, col. H: Soflware~ pages 82-91, January 1987.
|
| |
24
|
|
| |
25
|
|
| |
26
|
B. Ryder, T. Marlowe, and M. Paul}. Incremental Itera- Lion: When Will It Work? Laboratory for Computer Science Research Technical Report LCSR-TR-89, Department of Computer Science, Rutgers University, March 1987. to appear in Science of Programming.
|
| |
27
|
|
| |
28
|
J. Schwartz and M. Sharir. A Design for Optimizations of the Bitvectoring Class. Computer Science Techxtical Report 17~ Couraxtt Institute of Mathematical Sciences~ New York Un.iversity~ September 1979.
|
| |
29
|
|
| |
30
|
|
| |
31
|
|
CITED BY 27
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.12-21, January 22-24, 1990, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3