US5812855A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for constaint propagation cloning for unknown edges in IPA
Assignee: RPX Corp
•
Filing: 1996-06-03
•
Granted: 1998-09-22
•
Expires: 2016-06-03
Abstract
Abstract The present invention provides a system and method for solving interprocedural problems on incomplete call graphs. For a given program, the present invention constructs a standard call graph on which the edges are updated with summary information needed to solve a given interprocedural problem such as constant propagation. Each node of the call graph having an unknown incoming edge is cloned. The call graph is then updated so that the unknown incoming edges are directed to the clone nodes and the known edges are directed to the original nodes. This results in a purified call graph on which an interprocedural problem can be solved. The present invention then creates a real clone of the procedure associated with each clone node of the call graph. The real clones are optimized according to the interprocedural solution. The present invention updates the known procedure calls of the program to call the real clones. Therefore, known procedure calls take advantage of optimized code, while unknown procedure calls continue to call unoptimized code.
Inventors
- 👤 Seema Hiranandani
- 👤 Wingsturn Wilson Ho
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 07:56
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433; G06F8/44; G06F8/443; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
124 words
A complete executed method for solving interprocedural problems on incomplete call graphs, comprising the steps of: (a) constructing a call graph having one or more nodes and one or more edges connecting said nodes, wherein each said node corresponds to a procedure in a computer program and each said edge corresponds to a procedure call; (b) updating said call graph with initial edge and node summary annotation information needed to solve a given interprocedural problem; (c) cloning said nodes having an unknown incoming edge, thereby creating one or more clones; (d) updating said call graph to reflect the creation of said clones created in step (c), thereby creating a purified call graph; and (e) solving said given interprocedural problem on said purified call graph.
Claim 2
Dependent Claim
124 words
A complete executed method for solving interprocedural problems on incomplete call graphs, comprising the steps of: (a) constructing a call graph having one or more nodes and one or more edges connecting said nodes, wherein each said node corresponds to a procedure in a computer program and each said edge corresponds to a procedure call; (b) updating said call graph with initial edge and node summary annotation information needed to solve a given interprocedural problem; (c) cloning said nodes having an unknown incoming edge, thereby creating one or more clones; (d) updating said call graph to reflect the creation of said clones created in step (c), thereby creating a purified call graph; and (e) solving said given interprocedural problem on said purified call graph.
Claim 3
Dependent Claim
63 words
The complete executed method of claim 1, further comprising: (f) creating a real clone for each clone created in step (c); (g) optimizing said real clone, thereby said real clone contains an optimized version of a procedure that solves said given interprocedural problem; and (h) updating procedure calls of said purified call graph to call said real clone, thereby creating updated procedure calls.
Claim 4
Dependent Claim
21 words
The complete executed method of claim 2, further comprising: (i) cleaning up said updated procedure calls of said purified call graph.
Claim 5
Dependent Claim
14 words
The complete executed method of claim 3, further comprising: (j) removing unnecessary real clones.
Claim 6
Dependent Claim
15 words
The complete executed method of claim 1, wherein said given interprocedural problem is constant propagation.
Claim 7
Dependent Claim
36 words
The complete executed method of claim 5, further comprising: (k) solving interprocedural alias analysis by determining whether a procedure can modify a parameter value; wherein step (k) is executed after step (a) and before step (b).
Claim 8
Dependent Claim
96 words
The complete executed method of claim 6, wherein step (b) comprises: (b.1) replacing a "formal -- mod" annotation that corresponds to a parameter value of a procedure with a "formal" annotation, if it is determined in step (k) that said procedure corresponding to said "formal -- mod" annotation cannot modify said parameter value; and (b.2) replacing said "formal -- mod" annotation that corresponds to a parameter value of a procedure with a "symbolic" annotation, if it is determined in step (k) that said procedure corresponding to said "formal -- mod" annotation can modify said parameter value.
Claim 9
Dependent Claim
25 words
The complete executed method of claim 5, wherein step (d) comprises: (d.1) redrawing unknown incoming edges of said call graph to point to said clones.
Claim 10
Dependent Claim
132 words
A computer system for solving interprocedural problems on incomplete call graphs, comprising: constructing means for constructing a call graph having one or more nodes and one or more edges connecting said nodes, wherein each said node corresponds to a procedure in a computer program and each said edge corresponds to a procedure call; first updating means for updating said call graph with initial edge and node summary annotation information needed to solve a given interprocedural problem; cloning means for cloning said nodes having an unknown incoming edge, thereby creating one or more clones; second updating means for updating said call graph to reflect the creation of said clones created by said cloning means, thereby creating a purified call graph; and solving means for solving said\given interprocedural problem on said purified call graph.
Claim 11
Dependent Claim
132 words
A computer system for solving interprocedural problems on incomplete call graphs, comprising: constructing means for constructing a call graph having one or more nodes and one or more edges connecting said nodes, wherein each said node corresponds to a procedure in a computer program and each said edge corresponds to a procedure call; first updating means for updating said call graph with initial edge and node summary annotation information needed to solve a given interprocedural problem; cloning means for cloning said nodes having an unknown incoming edge, thereby creating one or more clones; second updating means for updating said call graph to reflect the creation of said clones created by said cloning means, thereby creating a purified call graph; and solving means for solving said\given interprocedural problem on said purified call graph.
Claim 12
Dependent Claim
70 words
The computer system of claim 9, further comprising: creating means for creating a real clone for each clone created by said cloning means; optimizing means for optimizing said real clone, thereby said real clone contains an optimized version of a procedure that solves said given interprocedural problem; and third updating means for updating procedure calls of said purified call graph to call said real clone, thereby creating updated procedure calls.
Claim 13
Dependent Claim
22 words
The computer system of claim 10, further comprising: cleaning means for cleaning up said updated procedure calls of said purified call graph.
Claim 14
Dependent Claim
15 words
The computer system of claim 11, further comprising: removing means for removing unnecessary real clones.
Claim 15
Dependent Claim
14 words
The computer system of claim 9, wherein said given interprocedural problem is constant propagation.
Claim 16
Dependent Claim
43 words
The computer system of claim 13, further comprising: second solving means for solving interprocedural alias analysis by determining whether a procedure can modify a parameter value; wherein said second solving means is executed after said constructing means and before said first updating means.
Claim 17
Dependent Claim
107 words
The computer system of claim 14, wherein said first updating means comprises: first replacing means for replacing a "formal -- mod" annotation that corresponds to a parameter value of a procedure with a "formal" annotation, if it is determined by said second solving means that said procedure corresponding to said "formal -- mod" annotation cannot modify said parameter value; and second replacing means for replacing said "formal -- mod" annotation that corresponds to a parameter value of a procedure with a "symbolic" annotation, if it is determined by said second solving means that said procedure corresponding to said "formal -- mod" annotation can modify said parameter value.
Claim 18
Dependent Claim
28 words
The computer system of claim 13, wherein said second updating means comprises: redrawing means for redrawing unknown incoming edges of said call graph to point to said clones.
Claim 19
Dependent Claim
182 words
A computer program product for use with a computer system, comprising: a computer usable medium having a computer readable program code means embodied in said medium for enabling a processor to solve interprocedural problems on incomplete call graphs, said computer program product having: first program readable program code means for constructing a call graph having one or more nodes and one or more edges connecting said nodes, wherein each said node corresponds to a procedure in a computer program and each said edge corresponds to a procedure call; second program readable program code means for updating said call graph with initial edge and node summary annotation information needed to solve a given interprocedural problem; third program readable program code means for cloning said nodes having an unknown incoming edge, thereby creating one or more clones; fourth program readable program code means for updating said call graph to reflect the creation of said clones created by said cloning means, thereby creating a purified call graph; and fifth program readable program code means for solving said given interprocedural problem on said purified call graph.
Claim 20
Dependent Claim
182 words
A computer program product for use with a computer system, comprising: a computer usable medium having a computer readable program code means embodied in said medium for enabling a processor to solve interprocedural problems on incomplete call graphs, said computer program product having: first program readable program code means for constructing a call graph having one or more nodes and one or more edges connecting said nodes, wherein each said node corresponds to a procedure in a computer program and each said edge corresponds to a procedure call; second program readable program code means for updating said call graph with initial edge and node summary annotation information needed to solve a given interprocedural problem; third program readable program code means for cloning said nodes having an unknown incoming edge, thereby creating one or more clones; fourth program readable program code means for updating said call graph to reflect the creation of said clones created by said cloning means, thereby creating a purified call graph; and fifth program readable program code means for solving said given interprocedural problem on said purified call graph.
Claim 21
Dependent Claim
86 words
The computer program product of claim 17, further comprising: sixth program readable program code means for creating a real clone for each clone created by said third program readable program code means; seventh program readable program code means for optimizing said real clone, thereby said real clone contains an optimized version of a procedure that solves said given interprocedural problem; and eighth program readable program code means for updating procedure calls of said purified call graph to call said real clone, thereby creating updated procedure calls.
Claim 22
Dependent Claim
27 words
The computer program product of claim 18, further comprising: ninth program readable program code means for cleaning up said updated procedure calls of said purified call graph.
Claim 23
Dependent Claim
20 words
The computer program product of claim 19, further comprising: tenth program readable program code means for removing unnecessary real clones.
Claim 24
Dependent Claim
15 words
The computer program product of claim 17, wherein said given interprocedural problem is constant propagation.
Claim 25
Dependent Claim
57 words
The computer program product of claim 21, further comprising: eleventh program readable program code means for solving interprocedural alias analysis by determining whether a procedure can modify a parameter value; wherein said eleventh program readable program code means is executed after said first program readable program code means and before said second program readable program code means.
Claim 26
Dependent Claim
117 words
The computer program product of claim 22, wherein said second program readable program code means comprises: first replacing means for replacing a "formal -- mod" annotation that corresponds to a parameter value of a procedure with a "formal" annotation, if it is determined by said eleventh program readable program code means that said procedure corresponding to said "formal -- mod" annotation cannot modify said parameter value; and second replacing means for replacing said "formal -- mod" annotation that corresponds to a parameter value of a procedure with a "symbolic" annotation, if it is determined by said eleventh program readable program code means that said procedure corresponding to said "formal -- mod" annotation can modify said parameter value.
Claim 27
Dependent Claim
32 words
The computer program product of claim 21, wherein said fourth program readable program code means comprises: redrawing means for redrawing unknown incoming edges of said call graph to point to said clones.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-21 | 2002-03-23 | 2002-09-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-21 | 2006-03-23 | 2006-09-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-21 | 2010-03-23 | 2010-09-22 | $7700.00 | Window Closed / Lapsed |