Equivalence class based synchronization optimization

A computer readable medium having stored thereon computer-executable components comprising:

• a thread closure component for determining a subset of procedures in a call graph reachable by a thread associated with a thread allocation site;
• a procedure summary component for generating polymorphic summaries of procedures in the call graph;
• and
• a specialization component for specializing procedures separately when separate optimizations for each procedure can be performed.

A method of performing an alias analysis over a call graph, the method comprising:

• for each procedure in the call graph, creating an equivalence class representative for each formal parameter and return value, and grouping the equivalence class representative for each formal parameter and return value into a polymorphic summary;
• traversing the call graph upward starting at leaf nodes, and unifying equivalence class representatives whenever expressions associated with distinct equivalence class representatives become aliased;
• and
• traversing the call graph downward starting at a root procedure, and specializing procedures using the polymorphic summaries.

A computer-readable medium having computer-executable components comprising:

• an equivalence class representative generation component for creating an equivalence class representative for each formal parameter and return value of each procedure in a call graph, and for grouping the equivalence class representative for each formal parameter and return value into a polymorphic summary of the procedure;
• a procedure summary generation component for traversing the call graph upward starting at leaf nodes, and unifying equivalence class representatives whenever expressions associated with distinct equivalence class representatives become aliased;
• and
• a specialization component for traversing the call graph downward starting at a root procedure, and specializing procedures using the polymorphic summaries.