Method and apparatus for doing program analysis

A machine-readable medium that stores instructions, which when executed by a processor, cause the processor to perform operations 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.

An apparatus, comprising:

• a memory;
• a processor coupled to the memory and having a set of instructions which when executed by the processor cause the processor to perform operations 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.

An computer-implemented apparatus, comprising:

• means for assigning a definition-node for one or more definition statements in an intermediate language program;
• means for assigning a use-node for one or more use statements in the intermediate language program;
• means for 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;
• means for assigning an alias-node for one or more aliases representing the equivalence class of the memory accesses;
• means for 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;
• means for 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
• means for 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.