Optimizer for program loops

• US 5,457,799 A
• Filed: 03/01/1994
• Issued: 10/10/1995
• Est. Priority Date: 03/01/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Srivastava, Amitabh
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US08/204,835
• Time in Patent Office: 588 Days
• Field of Search: 395/700, 395/650
• US Class Current: 717/160
• CPC Class Codes: G06F 8/443 Optimisation

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.