Efficient construction of pruned SSA form

Details Efficient construction of pruned SSA form Efficient construction of pruned SSA form

2008-07-08

2008-07-08

Zhen, Wei (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S140000

Reexamination Certificate

active

10863000

ABSTRACT:
Intermediate representations of computer code are efficiently generated. More particularly, methods described herein may be used to construct a static single assignment representation of computer code without unnecessary phi-function nodes. Potentially necessary phi-function node assignments may be analyzed to determine whether they directly reach a non-phi use or a necessary phi-use of a corresponding variable. Those that ultimately reach such a use may be determined to be necessary and a pruned static single assignment may be constructed by including those potentially necessary phi-functions determined to be in fact necessary. Also, some phi-function nodes may be determined to be necessary based on their dependency relationship to other phi-functions previously determined to be necessary (e.g., because they directly reach a non-phi use). A phi-function dependency graph may be used to record dependency relationships between phi-function nodes. The analysis can proceed during a forward walk of a control flow representation of the program.

REFERENCES:
patent: 5448737 (1995-09-01), Burke et al.
patent: 5659754 (1997-08-01), Grove et al.
patent: 5768596 (1998-06-01), Chow et al.
patent: 6026241 (2000-02-01), Chow et al.
patent: 6151706 (2000-11-01), Lo et al.
patent: 6182284 (2001-01-01), Sreedhar et al.
patent: 6427234 (2002-07-01), Chambers et al.
patent: 6571387 (2003-05-01), Chow et al.
patent: 6738967 (2004-05-01), Radigan
patent: 2004/0098710 (2004-05-01), Radigan
patent: 2005/0166194 (2005-07-01), Rubin et al.
patent: 2006/0070050 (2006-03-01), Chen
Cooper, Keith, Simpson, L. Taylor, Vick, Christopher A.. “Operartor Strength Reduction.” ACM Transaction on Programming Languages and Systems 23 No. 5(2001): 603-623.
Kaplan, Adam, Brisk, Philip, Kastner, Ryan. “Data Communication Estimation and Reduction for Reconfigurable Systems.” Annual ACM IEEE Design Automation Conference (2003): 616-621.
Ron Cytron, Jeanne Ferrante, Barry K.Rosen, Mark N. Wegman, and F. Kenneth Zadeck. “An efficient method for computing static single assignment form”, Annual ACM Symposium on Principles of Programming Languages, 16(1989): 25-35.
Automatic Construction of Sparse Data Flow Evaluation Graphs, Jong-Deok Choi, Ron Cytron and Jeanne Ferrante, InConference Record of the 20thAnnual Association of Computing Machinery Symposium on Principles of Programming Languages, 1991, pp. 55-66.
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman and F. Kenneth Zadeck, Association of Computing Machinery, vol. 13, No. 4, Oct. 1991, pp. 451-490.
Practical Improvements to the Construction and Destruction of Static Single Assignment Form, Preston Briggs, Keith D. Cooper, Timothy J. Harvey, and L. Taylor Simpson, Software-Parctioce and Experience, vol. 28, Issue 8, pp. 859-881, Published by John Wiley & Sons, Inc., Jul. 1998.
Efficiently Computing Ø-Nodes On-The-Fly, Ron K. Cytron and Jeanne Ferrante, Association of Computing Machinery, vol. 17, No. 3, May 1995, pp. 487-506.
Single-Pass Generation of Static Single-Assignment Form for Structured Languages, Marc M. Branis and Hanspeter Mössenböck, Association of Computing Machinery, vol. 16, No. 6, Nov. 1994, pp. 1684-1698.
Data Specialization, Todd B. Knoblock and Erik Ruf, Microsoft Research, Advanced Technology Division, Microsoft Corporation, Feb. 5, 1996.
Algorithms for Computing the Static Single Assignment Form, Gianfranco Bilardi and Keshav-Pingali, Association of Computing Machinery, vol. 50, No. 3, May 2003, pp. 375-425.
Characterizing the Optimility of Minimal SSA Using the Value Flow Graph, Hideki Saito, Constantine D. Polychronopoulos, Center for Super Computing Research and Development, University of Illinois at Urbana, Champaign, Jul. 17, 1996.

Affiliated with

Also associated with

Rating

Efficient construction of pruned SSA form does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient construction of pruned SSA form, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient construction of pruned SSA form will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3930531