Method for performing common subexpression elimination on a rack-N static single assignment language

Patent 6002879 Issued on December 14, 1999. Estimated Expiration Date:

April 1, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Method for improving the efficiency of arithmetic code generation in an optimizing compiler using machine independent update instruction generation
Patent #: 5287510
Issued on: 02/15/1994
Inventor: Hall, et al.

System and method for solving monotone information propagation problems
Patent #: 5327561
Issued on: 07/05/1994
Inventor: Choi, et al.

System and method for optimizing computer code using a compact data flow representation
Patent #: 5448737
Issued on: 09/05/1995
Inventor: Burke, et al.

Method of compilation optimization using an N-dimensional template for relocated and replicated alignment of arrays in data-parallel programs for reduced data communication during execution
Patent #: 5475842
Issued on: 12/12/1995
Inventor: Gilbert, et al.

Method and apparatus for finding induction variables for use in compiling computer instructions
Patent #: 5584027
Issued on: 12/10/1996
Inventor: Smith

Method and apparatus for an improved optimizing compiler
Patent #: 5659754
Issued on: 08/19/1997
Inventor: Grove, et al.

System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation Patent #: 5768596
Issued on: 06/16/1998
Inventor: Chow, et al.

Inventors

Application

No. 829856 filed on 04/01/1997

US Classes:

715/527, Print preview717/142, Scanning and lexical analysis717/146, Including intermediate code717/159Code restructuring

Examiners

Primary: Trammell, James P.
Assistant: Smith, Demetra R.

Attorney, Agent or Firm

Arnold White & Durkee

International Classes

G06F 009/45
G06F 009/44

Abstract

Briefly, in one embodiment, the invention is a method for eliminating common subexpressions in an initial SSA intermediate language representation of at least a portion of a computer program. The method includes (a) inserting a phi-node for an unambiguous definition used in an unambiguous subexpression reaching a join point in the initial intermediate language subsequent to the join point; (b) inserting a phi-node for the unambiguous common subexpression; (c) renaming the unambiguous definition and a subsequent use reached by the definition; and (d) renaming the unambiguous common subexpression.

Other References

Cytron and Gershbein, "Efficient Accommodation of May-Alias Information in SSA Form", published at ACM, pp. 36-45, 1993
Munehiro and Ken'ichi, "Efficient Partial Redundancy Elimination Based on Phi-Function Motion", Hoho Shori Gakkai Kenkyu Hokoku, vol. 95, No. 15, pp. 21-30, 199