Data-flow method for optimizing exception-handling instructions in programs

• US 7,120,904 B1
• Filed: 04/19/2000
• Issued: 10/10/2006
• Est. Priority Date: 04/19/2000
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Robison, Arch D.
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): Kiss, Eric B.
• Application Number:
  US09/552,292
• Time in Patent Office: 2,365 Days
• Field of Search: 717/127, 717/131, 717/144, 717/151, 717/154, 717/159, 717/155, 717/156, 712/244
• US Class Current: 717/155
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A method for analyzing and optimizing programs that operate on a data structure where the state of the data structure must be valid at certain program points. The program is represented as a control-flow graph. The method decomposes the state of the data structure into components, and applies partial redundancy elimination to place instructions that set the state of the data structure, with a variation that permits speculative placement. Application extends to manipulating a stack that keeps track of what to do should an exception arise during execution. In this context, a control-flow representation of contingencies is converted into placement of instructions that manipulate the stack.

Claims

1. For a computer-executable program that operates on a data structure, where the data structure must have a required state at selected program points, a computer-implemented method of transforming said program comprising:

analyzing the program to determine the state of said data structure at said selected program points, wherein the data structure stores items on a first-in-last-out basis;

partitioning said determined state at each said program point into components that may each be set separately;

determining operations to be inserted into the program in order to set each component of the state at each selected program point based on flow equations for an up-safety and a down-safety of setting the state at each selected program point, wherein the operations assure that the data structure will be in the required state at the selected program points; and

placing said operations to eliminate partial redundancies of said operations.

2. The computer-implemented method of claim 1, wherein the states of the data structure are represented as paths on a tree of nodes where:

each path traverses the tree towards the root; and

each node on the path represent a component of the state.

3. The computer-implemented method of claim 1, wherein the data structure represents actions to be taken by the program if an exception occurs.

4. The computer-implemented method of claim 3, wherein the selected program points are the points of execution immediately before instructions that might cause an exception.

5. The computer-implemented method of claim 3, further comprising representing the actions to be taken as exception paths in a graph.

6. For a computer-executable program that operates on a data structure, where the data structure must have a required state at selected program points, a computer-implemented method of transforming said program comprising:

analyzing the program to determine the state of an instance of said data structure at said selected program points, wherein the data structure stores items on a first-in-last-out basis;

partitioning said instance of said data structure into components;

determining a set of one or more operations to be inserted into the program in order to set each component of the state at each selected program point based on flow equations for an up-safety and a down-safety of setting the state at each selected program point, wherein the operations assure that the data structure will be in the required state at the selected program points;

computing placement of the set of operations to eliminate partial redundancies; and

inserting the set of operations at said program points according to the computed placement.

7. The computer-implemented method of claim 6 wherein the data structure is an exception handling stack.

8. The computer-implemented method of claim 7 wherein the components are a pointer to the exception handling stack and an exception handling data structure.

12. The machine-readable medium of claim 7, wherein the selected program points are the points of execution immediately before instructions that might cause an exception.

9. A machine-readable medium having a set of instructions, which when executed by a set of one or more processors, causes said set of processors to perform operations comprising:

analyzing a program that operates on a data structure, which must have a required state at selected program points in the program, to determine the state of an instance of said data structure at said selected program points, wherein the data structure stores items on a first-in-last-out basis;

partitioning said instance of said data structure into components;

determining a set of one or more operations to be inserted into the program in order to set each component of the state at each selected program point based on flow equations for an up-safety and a down-safety of setting the state at each selected program point, wherein the operations assure that the data structure will be in the required state at the selected program points;

computing placement of the set of operations to eliminate partial redundancies; and

inserting the set of operations at said program points according to the computed placement.

10. The machine-readable medium of claim 9, wherein the states of the data structure are represented as paths on a tree of nodes where:

each path traverses the tree towards the root; and

each node on the path represent a component of the state.

11. The machine-readable medium of claim 9, wherein the data structure represents actions to be taken by the program if an exception occurs.