Incremental computation of dominator trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Incremental computation of dominator trees

Full text

Pdf (259 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 19 , Issue 2 (March 1997) table of contents

Pages: 239 - 252

Year of Publication: 1997

ISSN:0164-0925

Authors

Vugranam C. Sreedhar	Hewlett-Packard Company, Cupertino, CA
Guang R. Gao	McGill Univ., Montre´al, P.Q., Canada
Yong-Fong Lee	Intel Corporation, Santa Clara, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 33, Citation Count: 5

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/244795.244799 What is a DOI?

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	Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
	3	M. D. Carroll , B. G. Ryder, Incremental data flow analysis via dominator and attribute update, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.274-284, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73584]
	4	Ron K. Cytron , Jeanne Ferrante, Efficiently computing Φ-nodes on-the-fly, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.487-506, May 1995 [doi>10.1145/203095.203099]
	5	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	6	D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22166]
	7	JOHNSON, R. 1994. Dependence based program analysis. Ph.D. thesis, Cornell Univ., Ithaca, N.Y.
	8	L. L. Pollock , M. L. Soffa, An Incremental Version of Iterative Data Flow Analysis, IEEE Transactions on Software Engineering, v.15 n.12, p.1537-1549, December 1989 [doi>10.1109/32.58766]
	9	Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
	10	G. Ramalingam , Thomas Reps, An incremental algorithm for maintaining the dominator tree of a reducible flowgraph, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.287-296, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177905]
	11	B. G. Ryder , T. J. Marlowe , M. C. Paull, Conditions for incremental iteration: examples and counterexamples, Science of Computer Programming, v.11 n.1, p.1-15, Oct. 1988 [doi>10.1016/0167-6423(88)90061-5]
	12	Vugranam C. Sreedhar, Efficient program analysis using DJ graphs, McGill University, Montreal, Que., Canada, 1996
	13	SREEDHAR, V. C. AND GAO, G. R. 1996. Computing qS-nodes in linear time using dj graphs. J. of Program. Lang. 3, 4, 191-213.
	14	Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, A new framework for exhaustive and incremental data flow analysis using DJ graphs, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.278-290, May 21-24, 1996, Philadelphia, Pennsylvania, United States
	15	Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

CITED BY 5

	Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.2, p.388-435, March 1998
	Karthik Gargi, A sparse algorithm for predicated global value numbering, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Sumit Gupta , Mehrdad Reshadi , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Dynamic common sub-expression elimination during scheduling in high-level synthesis, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan
	Sumit Gupta , Rajesh Kumar Gupta , Nikil D. Dutt , Alexandru Nicolau, Coordinated parallelizing compiler optimizations and high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.441-470, October 2004
	Miranda Mowbray , Antonio Lain, Dominator-tree analysis for distributed authorization, Proceedings of the third ACM SIGPLAN workshop on Programming languages and analysis for security, June 07-13, 2008, Tucson, AZ, USA

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Optimization

General Terms:
Algorithms, Languages

Keywords:
DJ graphs, dominance frontiers, dominator trees, incremental compilation

REVIEW

"Svetlana Segarceanu : Reviewer"

A new incremental algorithm for maintaining the dominator tree of a flowgraph is presented. The first section of the paper defines a flowgraph, some domination relations in a flowgraph, and the dominator tree of a flowgraph. Maintaining the do more...

Collaborative Colleagues:

Vugranam C. Sreedhar: colleagues

Guang R. Gao: colleagues

Yong-Fong Lee: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player