Patent ID: 7117490

Claim:
A computer-implemented method, comprising: assigning a definition-node for one or more definition statements in an intermediate language program; assigning a use-node for one or more use statements in the intermediate language program; performing a memory alias analysis of the intermediate language program to partition memory accesses into equivalence classes such that any two memory accesses that reference the same storage location belong to the same equivalence class; assigning an alias-node for one or more aliases representing the equivalence class of the memory accesses; introducing an edge into a dependence flow graph connecting each definition-node to the alias-node corresponding to the alias representing the equivalence class to which the definition-node belongs; introducing an edge in the dependence flow graph connecting each use-node to the alias-node corresponding to the alias representing the equivalence class to which the use-node belongs; and performing a program analysis using the dependence flow graph by assigning, for each alias-node in the dependence flow graph, an initial value to the alias corresponding to the alias-node and adding the alias-node to a set of nodes; wherein a number of the edges in the dependence flow graph is linear to a number of the nodes in the dependence flow graph, and wherein the number of edges is independent of a definition-use structure of the intermediate language program; wherein the program analysis further comprises iteratively performing while the set of nodes is not empty; removing a node from the set of nodes; if the node is an alias-node, adding successors of the node in the dependence flow graph to the set of nodes; and if the node is a definition-node for a statement that defines a storage location: determining a value for an expression to be written to the storage location updating the initial value based on the value of the expression; and adding the storage location to the set of nodes.