Patent ID: 7743370

Claim:
A computer-implemented method for optimizing the operation of sequences of computer program instructions executing within a computing system by determining independence of a sub-graph in a code graph, wherein the code graph is a graph-based representation of the sequences of computer program instructions and the sub-graph represents part of the computer program that would be affected by the certain rearrangement of sequences of instructions for optimization, comprising the steps of: visiting a plurality of nodes in the code graph in post-order fashion; determining for a current node being visited whether a sub-graph of the current node has an alias node that refers to a target node, said target node being a node representing an argument which is the result of a previous program instruction; determining whether the target node is outside of the sub-graph of the current node by determining a smallest post-order node number of all said target nodes of all alias nodes in the sub-graph of the current node, comparing said smallest post-order node number of all said target nodes to a smallest post-order node number overall in the sub-graph of the current node and indicating the target node is outside the sub-graph of the current node if said smallest post-order node number of all said target nodes is not greater than or equal to the smallest post-order node number overall in the sub-graph of the current node; determining a total number of alias nodes in the sub-graph of the current node; determining a total number of alias nodes generated as a result of program instructions represented in the sub-graph of the current node; indicating that the sub-graph of the current node is not independent if the total number of alias nodes in the sub-graph does not equal the total number of alias nodes generated as a result of program instructions represented in the sub-graph; and indicating that the sub-graph is not independent if the target node is outside the sub-graph of the current node.