Method and apparatus for enabling global compiler optimizations in the presence of exception handlers within a computer program

• US 5,778,233 A
• Filed: 10/11/1996
• Issued: 07/07/1998
• Est. Priority Date: 10/11/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haugen, Patrick Todd, Lipasti, Mikko Herman, Besaw, Keith Vernon, Hessler, Mark Jonathon, Donovan, Robert John, Roediger, Robert Ralph
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): ROSENHOLM, ROBERT STEPHEN
• Application Number:
  US08/729,609
• Time in Patent Office: 634 Days
• Field of Search: 395/700, 395/705, 395/709, 395/708
• US Class Current: 717/154
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A method and apparatus allows a compiler to optimize code in the presence of exception handlers. According to a first embodiment, arcs are added to a control flow graph, prior to performing global optimizations, to account for exception handling code. According to the second embodiment, information relating to control flow to exception handlers is provided in pseudo-references in the code, which allows the compiler to determine how to appropriately optimize the code.

Claims

1. A computer apparatus comprising:

(A) an optimizer for optimizing a first instruction stream that is used to generate a second instruction stream, the first instruction stream being generated by a compiler and comprising a plurality of variables, the optimizer including;

an exception range determiner, the exception range determiner determining at least one exception range of the first instruction stream during which at least one exception may occur;

a resume point identifier, the resume point identifier identifying at least one resume point within the first instruction stream, each resume point identifying a range of at least one instruction that is executed when the at least one exception occurs;

a live range calculator, the live range calculator determining the liveness of the plurality of variables, the liveness of a selected variable that is used in the at least one instruction in the exception handling range defined by a resume point before the selected variable is defined extending to at least one instruction within the at least one exception range defined by the exception range determiner; and

(B) a CPU, the CPU executing the second instruction stream.

2. The computer apparatus of claim 1 wherein the compiler includes the optimizer.

3. The computer apparatus of claim 1 wherein the first instruction stream comprises an intermediate language instruction stream, and wherein the second instruction stream comprises a machine code instruction stream.

4. A computer apparatus for generating a second instruction stream from a first instruction stream, the second instruction stream being executable on a processor having a plurality of registers, the first instruction stream having a plurality of variables, the computer apparatus comprising:

an optimizer for optimizing the first instruction stream, the optimizer including;

an exception range determiner, the exception range determiner determining at least one exception range of the first instruction stream during which at least one exception may occur;

a resume point identifier, the resume point identifier identifying at least one resume point within the first instruction stream, each resume point identifying a range of at least one instruction that is executed when the at least one exception occurs; and

a live range calculator, the live range calculator determining the liveness of the plurality of variables, the liveness of a selected variable that is used in the at least one instruction in the exception handling range define by a resume point before the selected variable is defined extending to at least one instruction within the at least one exception range defined by the exception range determiner.

5. The computer apparatus of claim 4 wherein the compiler includes the optimizer.

6. The computer apparatus of claim 4 wherein the first instruction stream comprises an intermediate language instruction stream, and wherein the second instruction stream comprises a machine code instruction stream.

7. The computer apparatus of claim 4 wherein the first instruction stream comprises a first intermediate language instruction stream, and wherein the second instruction stream comprises a second intermediate language instruction stream.

8. A program product comprising:

(A) an optimizer, the optimizer being used on a computer apparatus to optimize an instruction stream, the instruction stream having a plurality of variables, the optimizer including;

an exception range determiner, the exception range determiner determining at least one exception range of the instruction stream during which at least one exception may occur;

a resume point identifier, the resume point identifier identifying at least one resume point within the instruction stream, each resume point identifying a range of at least one instruction that is executed when the at least one exception occurs; and

a live range calculator, the live range calculator determining the liveness of the plurality of variables, the liveness of a selected variable that is used in the at least one instruction in the exception handling range defined by a resume point before the selected variable is defined extending to at least one instruction within the at least one exception range defined by the exception range determiner; and

(B) signal bearing media bearing the optimizer.

9. The program product of claim 8 wherein the signal bearing media comprises recordable media.

10. The program product of claim 8 wherein the signal bearing media comprises transmission media.

11. A method for optimizing an instruction stream having a plurality of variables, the method comprising the steps of:

determining at least one exception range of the instruction stream during which at least one exception may occur;

identifying at least one resume point within the first instruction stream, each resume point identifying a range of at least one instruction that is executed when the at least one exception occurs; and

determining the liveness of the plurality of variables, the liveness of a selected variable that is used in the at least one instruction in the exception handling range defined by a resume point before the selected variable is defined extending to at least one instruction within the at least one exception range.

12. The method of claim 11 wherein the step of determining the liveness of the plurality of variables includes the steps of:

determining a set of the plurality of variables that are live at the at least one resume point;

locating all definitions of the set of variables within the at least one range;

adding a control flow arc from at least one exit of the at least one range to the at least one resume point; and

adding a control flow arc just prior to the definition of a selected variable to each of the resume points that contain a use of the selected variable before the selected variable is defined.

13. The method of claim 12 further including the step of:

splitting at least one basic block containing the definition of the selected variable into a plurality of basic blocks if the step of adding the control flow arc results in control flow potentially branching from the middle of the at least one basic block.

14. The method of claim 11 wherein the step of determining the liveness of the plurality of variables includes the steps of:

determining a set of the plurality of variables that are live at the at least one resume point;

locating all definitions of the set of variables within the at least one range; and

inserting at least one pseudo-reference into the instruction stream that defines which of the plurality of variables have uses before being defined in the exception handling ranges of instructions defined by resume points corresponding to exceptions that may occur in the at least one exception range;

the at least one pseudo-reference comprising a directive to an optimizer that performs the optimization of the instruction stream.