Data-flow method for optimizing exception-handling instructions in programs
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 Claims
-
1-9. -9. (Cancelled).
-
10. A method of eliminating partial redundancy comprising:
-
(A) speculatively computing down-safety by ignoring rarely taken branches in a control-flow graph; and
(B) computing up-safety using the results of the down-safety calculation to determine where operations are speculatively available. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A method comprising:
-
(A) representing the program with a control-flow graph in which actions to take in event of an exceptional situation are represented by explicit paths in the graph;
(B) analyzing said program to determine at which points the stack must be in a valid state;
(C) building a forest of tress that represent the stack state at said points where;
(i) each node of the tree represents a possible item on the stack, and (ii) a stack state is represented as a path from a tree node to the root of the tree;
(D) computing where to place operations that set the state of items on the stack by performing the steps of;
(i) constructing flow equations for down-safety of operations that set the state of items on the stack, where the equations ignore rarely taken branches, (ii) solving said flow equations for down-safety of operations that set the state of items on the stack, (iii) constructing flow equations for up-safety of operations that set the state of items on the stack, where the equations use the solution for down-safety to determine which setting operations are speculatively available, and (iv) solving said flow equations for up-safety of operations that set the state of items on the stack, (E) using the results of said flow equations to place instructions that maintain the stack;
(F) removing edges from the control-flow graph which represent said actions for exceptional events; and
(G) inserting a prologue at entry to the control-flow graph that saves the existing pointer to the top of the EH stack.
-
Specification