ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Automatic construction of sparse data flow evaluation graphs
Full text PdfPdf (1.00 MB)
Source Annual Symposium on Principles of Programming Languages archive
Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents
Orlando, Florida, United States
Pages: 55 - 66  
Year of Publication: 1991
ISBN:0-89791-419-8
Authors
Jong-Deok Choi  IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY
Ron Cytron  IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY
Jeanne Ferrante  IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY
Sponsors
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 15,   Downloads (12 Months): 70,   Citation Count: 45
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/99583.99594
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.

 
ASU86
Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
AWZ88
B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States  [doi>10.1145/73560.73561]
 
CCF
Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. On the efficient treatment of preserving definitions. In preparation.
CFR*89a
R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States  [doi>10.1145/75277.75280]
CFR*89b
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]
CLZ86
Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida  [doi>10.1145/512644.512651]
FOW87
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]
 
Hec77
Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
 
Ken81
Ken Kennedy. A survey of data flow analysis techniques. Program Flow Analysis: Theory and Applications, 1981.
Kil73
Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts  [doi>10.1145/512927.512945]
LT79
Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979  [doi>10.1145/357062.357071]
 
Mar89
Thomas J. Marlowe , Barbara G. Ryder, Data-flow analysis and incremental iteration, 1989
RL77
John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California  [doi>10.1145/512950.512961]
Ros79
Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979  [doi>10.1145/322123.322135]
 
Ros81
Barry K. Rosen. Degrees of availability as an introduction to the general theory of data flow analysis. Program Flow Analysis: Theory and Applications, 1981.
 
RT82
j.H. Reif and Robert Tarjan. Symbohc program analysis in almost linear time. SIAM Journal of Computing, 11(1):81-93, February 1982.
RWZ88
B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States  [doi>10.1145/73560.73562]
Tar81
Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981  [doi>10.1145/322261.322273]
WZ85
Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States  [doi>10.1145/318593.318659]
 
YHR89
Wuu Yang, Susan Horwitz, and Thomas Reps. De~ec~ing Program Components With Equivalen~ Behaviors. Technical Report, University of Wisconsin, Madison, April 1989. Computer Sciences Technical Report Number 840.
Zad84
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  45
Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999
Carl McConnell , Ralph E. Johnson, Using static single assignment form in a code optimizer, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.152-160, June 1992
Preston Briggs , Keith D. Cooper , Linda Torczon, Rematerialization, ACM SIGPLAN Notices, v.27 n.7, p.311-321, July 1992
Steven W. K. Tjiang , John L. Hennessy, Sharlit—a tool for building optimizers, ACM SIGPLAN Notices, v.27 n.7, p.82-93, July 1992
Matthew B. Dwyer , Lori A. Clarke, A flexible architecture for building data flow analyzers, Proceedings of the 18th international conference on Software engineering, p.554-564, March 25-29, 1996, Berlin, Germany
Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
Karthik Gargi, A sparse algorithm for predicated global value numbering, ACM SIGPLAN Notices, v.37 n.5, May 2002
Darren C. Atkinson , William G. Griswold, The design of whole-program analysis tools, Proceedings of the 18th international conference on Software engineering, p.16-27, March 25-29, 1996, Berlin, Germany
Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, ACM SIGPLAN Notices, v.27 n.7, p.212-223, July 1992
Deepak Goyal, Transformational Derivation of an Improved Alias Analysis Algorithm, Higher-Order and Symbolic Computation, v.18 n.1-2, p.15-49, June 2005
Robert Kennedy , Sun Chan , Shin-Ming Liu , Raymond Lo , Peng Tu , Fred Chow, Partial redundancy elimination in SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.627-676, May 1999
Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, ACM SIGPLAN Notices, v.29 n.6, p.159-170, June 1994
Fred Chow , Sun Chan , Robert Kennedy , Shin-Ming Liu , Raymond Lo , Peng Tu, A new algorithm for partial redundancy elimination based on SSA form, ACM SIGPLAN Notices, v.32 n.5, p.273-286, May 1997
Brian R. Murphy , Monica S. Lam, Program analysis with partial transfer functions, ACM SIGPLAN Notices, v.34 n.11, p.94-103, Nov. 1999
Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States
William G. Griswold, Direct update of data flow representations for a meaning-preserving program restructuring tool, ACM SIGSOFT Software Engineering Notes, v.18 n.5, p.42-55, Dec. 1993
Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, ACM SIGPLAN Notices, v.35 n.5, p.196-207, May 2000
Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, ACM SIGPLAN Notices, v.28 n.6, p.36-45, June 1993
Erik Ruf, Partitioning dataflow analyses using types, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.15-26, January 15-17, 1997, Paris, France
Richard Johnson , David Pearson , Keshav Pingali, The program structure tree: computing control regions in linear time, ACM SIGPLAN Notices, v.29 n.6, p.171-185, June 1994
Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States
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
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
Michael Burke , Jong-Deok Choi, Precise and efficient integration of interprocedural alias information into data-flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.14-21, March 1992
Rajiv Gupta , Mary Lou Soffa , Denise Ombres, Efficient register allocation via coloring using clique separators, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.370-386, May 1994
G. Ramalingam, On sparse evaluation representations, Theoretical Computer Science, v.277 n.1-2, p.119-147, April 28, 2002
Richard Johnson , Keshav Pingali, Dependence-based program analysis, ACM SIGPLAN Notices, v.28 n.6, p.78-89, June 1993
G. Ramalingam, On loops, dominators, and dominance frontier, ACM SIGPLAN Notices, v.35 n.5, p.233-241, May 2000
John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, ACM SIGPLAN Notices, v.29 n.10, p.324-340, Oct. 1994
Allen Leung , Lal George, Static single assignment form for machine code, ACM SIGPLAN Notices, v.34 n.5, p.204-214, May 1999
Michael Hind , Anthony Pioli, Which pointer analysis should I use?, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.113-123, Sept. 2000
Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994
Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States
Preston Briggs , Keith D. Cooper , Ken Kennedy , Linda Torczon, Coloring heuristics for register allocation, ACM SIGPLAN Notices, v.39 n.4, April 2004
Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, ACM SIGPLAN Notices, v.29 n.6, p.230-241, June 1994
Sorin Lerner , David Grove , Craig Chambers, Composing dataflow analyses and transformations, ACM SIGPLAN Notices, v.37 n.1, p.270-282, Jan. 2002
Margarida F. Jacome , Gustavo de Veciana , Satish Pillai, Clustered VLIW architecture with predicated switching, Proceedings of the 38th conference on Design automation, p.696-701, June 2001, Las Vegas, Nevada, United States
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
On loops, dominators, and dominance frontiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.5, p.455-490, September 2002
Aniruddha S. Gokhale , Douglas C. Schmidt, Measuring and Optimizing CORBA Latency and Scalability Over High-Speed Networks, IEEE Transactions on Computers, v.47 n.4, p.391-413, April 1998
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
Philip Brisk , Ajay Kumar Verma , Paolo Ienne, An optimistic and conservative register assignment heuristic for chordal graphs, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
Vugranam C. Sreedhar , Guang R. Gao , Yong-fong Lee, Incremental computation of dominator trees, ACM SIGPLAN Notices, v.30 n.3, p.1-12, March 1993
Erik Ruf, Optimizing sparse representations for dataflow analysis, ACM SIGPLAN Notices, v.30 n.3, p.50-61, March 1993
Ben Hardekopf , Calvin Lin, Semi-sparse flow-sensitive pointer analysis, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees


General Terms:
Algorithms, Design, Languages

Collaborative Colleagues:
Jong-Deok Choi: colleagues
Ron Cytron: colleagues
Jeanne Ferrante: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player