The transitive closure of control dependence

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The transitive closure of control dependence: the iterated join

Full text

Pdf (834 KB)

Source

ACM Letters on Programming Languages and Systems (LOPLAS) archive
Volume 1 , Issue 2 (June 1992) table of contents

Pages: 178 - 190

Year of Publication: 1992

ISSN:1057-4514

Author

Michael Weiss

Compass, Inc.

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 40, Citation Count: 9

Additional Information:

abstract references cited by index terms review

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/151333.151337 What is a DOI?

ABSTRACT

We characterize the transitive closure of the control dependence relation and give an application to the theory of control fow guards. We relate our result to characterizations by Beck et al., by Sarkar, and by Cytron et al., and strengthen a result of the latter concerning dominance frontiers and join sets.

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	J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
	2	Micah Beck , Richard Johnson , Keshav Pingali, From control flow to dataflow, Journal of Parallel and Distributed Computing, v.12 n.2, p.118-129, June 1991 [doi>10.1016/0743-7315(91)90016-3]
	3	BESAW, K. V. Advanced techniques for vectorizing dusty decks. In Proceedings of the Second International Conference on SupQrcomputing, Vol. I (1987), pp. 111-132.
	4	CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F.K. Efficiently computing static single assignment form and the control dependence graph. Tech. Rep. RC-14756, IBM Watson Research Center, July 1989.
	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	Ron Cytron , Jeanne Ferrante , V. Sarkar, Compact representations for control dependence, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.337-351, June 1990, White Plains, New York, United States
	7	Ron Cytron , J. Ferrante , V. Sarkar, Experiences using control dependence in PTRAN, Selected papers of the second workshop on Languages and compilers for parallel computing, p.186-212, May 1990, Urbana, Illinois, United States
	8	Jeanne Ferrante , Mary Mace, On linearizing parallel code, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.179-190, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318636]
	9	J. Ferrante , M. Mace , B. Simons, Generating sequential code from parallel code, Proceedings of the 2nd international conference on Supercomputing, p.582-592, June 1988, St. Malo, France [doi>10.1145/55364.55421]
	10	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	11	GUPTA, R., AND SOFFA, M.L. Region scheduling. In Proceedings of the Second International Conference on Supercomputing, Vol. III, 1987, pp. 141-148.
	12	Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
	13	S. Horwitz , J. Prins , T. Reps, Integrating non-intering versions of programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-145, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73572]
	14	S. Horwitz , J. Prins , T. Reps, On the adequacy of program dependence graphs for representing programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-157, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73573]
	15	Ken Kennedy , Kathryn S. McKinley, Loop distribution with arbitrary control flow, Proceedings of the 1990 conference on Supercomputing, p.407-416, October 1990, New York, New York, United States
	16	Vivek Sarkar, PTRAN—the IBM parallel translation system, Parallel functional languages and compilers, ACM Press, New York, NY, 1991 [doi>10.1145/107214.129260]
	17	SELKE, R.P. Program dependence graphs: A formal treatment. Tech. Rep. COMP TR90-130, Dept. of Computer Science, Rice Univ., Aug. 1990.
	18	SELKE, R.P. Transforming program dependence graphs. Tech. Rep. COMP TR90-131, Dept. of Computer Science, Rice Univ., Aug. 1990.
	19	WEISS, M. Control dependence and partial IF-conversion for MIMD architectures. Tech. Rep. CA-8802-0301, Compass, Inc., Feb. 1988.

CITED BY 9

	Gianfranco Bilardi , Keshav Pingali, A framework for generalized control dependence, ACM SIGPLAN Notices, v.31 n.5, p.291-300, May 1996
	Vugranam C. Sreedhar , Guang R. Gao, A linear time algorithm for placing &phgr;-nodes, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.62-73, January 23-25, 1995, San Francisco, California, United States
	G. Ramalingam, On loops, dominators, and dominance frontier, ACM SIGPLAN Notices, v.35 n.5, p.233-241, May 2000
	On loops, dominators, and dominance frontiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.5, p.455-490, September 2002
	Dibyendu Das , U. Ramakrishna, A practical and fast iterative algorithm for φ-function computation using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.426-440, May 2005
	Gianfranco Bilardi , Keshav Pingali, Algorithms for computing the static single assignment form, Journal of the ACM (JACM), v.50 n.3, p.375-425, May 2003
	Yutaka Matsuno , Atsushi Ohori, A type system equivalent to static single assignment, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
	Michael Wolfe, J+=J, ACM SIGPLAN Notices, v.29 n.7, p.51-53, July 1994
	Minh Ngoc Ngo , Hee Beng Kuan Tan, Detecting large number of infeasible paths through recognizing their patterns, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.3 Language Constructs and Features
Subjects: Control structures

General Terms:
Languages, Theory

Keywords:
IF-conversion, SSA form, control dependence, control flow guards, dominance frontiers, iterated join set, transitive closure

REVIEW

"James Curtis Miller : Reviewer"

Control dependency flowgraphs are often used in compiling for many purposes. This paper contains a basic review of the necessary graph-theoretic concepts and characterizes the transitive closure of control dependence. The character more...

Adobe Acrobat

QuickTime

Windows Media Player

Real Player