System and method for solving monotone information propagation problems

Patent 5327561 Issued on July 5, 1994. Estimated Expiration Date:

September 20, 2011. 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 global common subexpression elimination and code motion in an optimizing compiler
Patent #: 4656583
Issued on: 04/07/1987
Inventor: Auslander , et al.

System for inserting constructs into compiled code, defining scoping of common blocks and dynamically binding common blocks to tasks Patent #: 5093916
Issued on: 03/03/1992
Inventor: Karp, et al.

Inventors

Application

No. 763099 filed on 09/20/1991

US Classes:

717/157, Using procedure or function call graph717/144Including graph or tree representation (e.g., abstract syntax tree or AST)

Examiners

Primary: Kriess, Kevin A.
Assistant: Richey, Michael T.

Attorney, Agent or Firm

Sterne, Kessler, Goldstein & Fox

International Classes

G06F 009/45
G06F 009/44
G06F 009/00

Abstract

A method and system is provided for constructing sparse evaluation graphs for forward or backward monotone data flow problems. The sparse graph combines information as early as possible, yet directly connects nodes that generate and use information. This allows problems from the large, general class of monotone data flow problems to enjoy the advantages of solutions based on Static Single Assignment (SSA) form.The present invention includes a compiler configured to transform a source program into optimized executable code. The compiler contains an optimizer which is configured to optimize the source program, in which the source program and optimization program are represented by a data flow framework. The optimizer includes a sparse evaluation graph generator which generates a sparse evaluation graph and an evaluator connected to evaluate the sparse evaluation graph in relation to the data flow framework.

Other References

Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Tansactions on Programming Languages and Systems, vol. 13, No. 4, pp. 451-490, (1991)
Cytron et al., An Efficient Method of Computing Static Single Assignment Form, ACM Transations on Programming Languages and Systems, pp. 25-35, (1989)
Jeanne Ferrante, The Program Dependence Graph And Its Use In Optimization, Jun. 1984, 1-3