Patent US5457799A successfully refreshed from Google Patents.
US5457799A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimizer for program loops
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-03-01
•
Granted: 1995-10-10
•
Expires: 2014-03-01
Abstract
Abstract In a method for optimizing loops of a program, the program is partitioned into a plurality of procedures, each procedure including instructions related for execution. A program call graph is constructed for the program, the call graph indicating the flow of execution among the several procedures. A specific one of the procedures is identified as a dominating procedure if the specific procedure is executed more than once. Procedures called from the dominating procedure are identified as descendant procedures. The descendent and dominating procedures are designated as a loop region. Any of the descendant procedure which are called by any of procedures of the program other than the dominating procedure and the descendant procedure are identified as step procedures. Step procedures are removed from the loop region. Instructions of the loop region that do not change the execution state of the computer are removed from the loop region in a sequence as determined by the frequency of execution of such instructions.
Inventors
- 👤 Amitabh Srivastava
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 16:14
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
167 words
A computer implemented method for optimizing loops of a program, comprising the steps of: partitioning the program into a plurality of procedures, each procedure of said plurality of procedures including instructions related for execution; constructing a program call graph for the program, said program call graph to indicate a flow of execution among said plurality of procedures; identifying a specific one of said plurality of procedures as a dominating procedure, a dominating procedure being one of said plurality of procedures that calls any of said plurality of procedures more than once; identifying a particular procedure of said plurality of procedures as a descendant procedure of said dominating procedure, said second procedure being called by said dominating procedure, said descendant procedure and said dominating procedure designated as a loop region; identifying said descendant procedure as a step procedure when said descendant procedure is called by any of said plurality of procedures other than said dominating procedure and said descendant procedure; removing said step procedure from said loop region.
Claim 2
Dependent Claim
167 words
A computer implemented method for optimizing loops of a program, comprising the steps of: partitioning the program into a plurality of procedures, each procedure of said plurality of procedures including instructions related for execution; constructing a program call graph for the program, said program call graph to indicate a flow of execution among said plurality of procedures; identifying a specific one of said plurality of procedures as a dominating procedure, a dominating procedure being one of said plurality of procedures that calls any of said plurality of procedures more than once; identifying a particular procedure of said plurality of procedures as a descendant procedure of said dominating procedure, said second procedure being called by said dominating procedure, said descendant procedure and said dominating procedure designated as a loop region; identifying said descendant procedure as a step procedure when said descendant procedure is called by any of said plurality of procedures other than said dominating procedure and said descendant procedure; removing said step procedure from said loop region.
Claim 3
Dependent Claim
89 words
The method as in claim 1 further comprising: identifying specific instructions of said loop region as invariant instructions when said specific instructions do not change an execution state of the computer while executing said specific instructions of said loop region; determining the number of times each of said invariant instructions will be executed; ordering said invariant instructions according to the number of times said invariant instructions will be executed; moving said invariant instructions from said loop region in a sequence as determined by said ordering of said invariant instructions.
Claim 4
Dependent Claim
121 words
A computer implemented method for optimizing loops of a program to be executed in a computer system, comprising: partitioning the program into a plurality of procedures; constructing a program call graph for the program; identifying dominating procedures of said plurality of procedures, each of said dominating procedures calling any of the plurality of procedures more than once; identifying descendant procedures of the dominating procedures, the descendant procedure being called via the dominating procedures; designating the descendant procedures and the dominating procedures as a loop region; identifying step procedures of the loop region, the step procedures being called by any of the plurality of procedures other than the dominating procedures and the descendant procedures; removing the step procedure from the loop region.
Claim 5
Dependent Claim
121 words
A computer implemented method for optimizing loops of a program to be executed in a computer system, comprising: partitioning the program into a plurality of procedures; constructing a program call graph for the program; identifying dominating procedures of said plurality of procedures, each of said dominating procedures calling any of the plurality of procedures more than once; identifying descendant procedures of the dominating procedures, the descendant procedure being called via the dominating procedures; designating the descendant procedures and the dominating procedures as a loop region; identifying step procedures of the loop region, the step procedures being called by any of the plurality of procedures other than the dominating procedures and the descendant procedures; removing the step procedure from the loop region.
Claim 6
Dependent Claim
80 words
The method as in claim 3 further comprising: identifying invariant instructions of the plurality of procedures, the invariant instructions to maintain an execution state of the computer while executing; determining the number of times each of the invariant instructions will be executed; ordering the invariant instructions according to the number of times each of the invariant instructions will be executed; moving said invariant instructions from said loop region in a sequence as determined by the ordering of the invariant instructions.
Claim 7
Dependent Claim
158 words
The method as in claim 3 wherein the program call graph includes nodes and edges, each node representing one of the plurality of procedures, and each edge representing an execution interface between a calling one of the plurality of procedures, and a called one of the plurality of procedures, further comprising: assigning a value to each of the edges of the program call graph, the value representative of the number of times that the edge is traversed during an execution of the program; weighing each value of each edge of the program call graph by a relative depth of the edge in the loop region; ordering the edges according to the weighted values of each of the edges; identifying invariant code in the loop region, the invariant code to maintain an invariant state of the computer system; and moving the invariant code from the loop region according to the ordering of the edges of the program call graph.
Claim 8
Dependent Claim
49 words
The method of claim 5 further comprising: initially setting the weighing of each value of each edge to a value of zero; and increasing the weighing of each value of each edge by a factor of ten for each level of nesting of the edge in the loop region.
Claim 9
Dependent Claim
31 words
The method of claim 4 further comprising: allocating registers of the computer system to invariant code as determined by the ordering of the invariant code until all registers have been allocated.
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) | 1998-10-09 | 1999-04-10 | 1999-10-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-10-09 | 2003-04-10 | 2003-10-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-10-09 | 2007-04-10 | 2007-10-10 | $7700.00 | Window Closed / Lapsed |