Method, system, and computer program product for extending sparse partial redundancy elimination to support speculative code motion within an optimizing compiler

A method to perform conservative speculative code motion within a static single assignment partial redundancy elimination (SSAPRE) register promotion compiler optimization, the SSAPRE optimization including six steps:

• (1) .PHI.-Insertion, (2) Rename, (3) DownSafety, (4) WillBeAvail, (5) Finalize, and (6) CodeMotion, the method comprising the steps of:
• (1) accessing a static single assignment (SSA) representation of a computer program;
• (2) performing steps (1) and (2) of the SSAPRE optimization on said SSA representation, thereby obtaining a dense SSA graph of said computer program;
• (3) performing a can speculate function on said dense SSA graph, thereby marking at least one .PHI. function of said dense SSA graph as being downsafe;
• and
• (4) performing steps (3), (4), (5) and (6) of the SSAPRE optimization on said dense SSA graph;
• whereby the compiler can produce more efficient, speculated executable program code from said dense SSA graph.

A method to perform profile-driven speculative code motion within a static single assignment partial redundancy elimination (SSAPRE) register promotion compiler optimization, the SSAPRE optimization including six steps:

• (1) .PHI.-Insertion, (2) Rename, (3) DownSafety, (4) WillBeAvail, (5) Finalize, and (6) CodeMotion, the method comprising the steps of:
• (1) accessing a static single assignment (SSA) representation of a computer program;
• (2) accessing a collection of profile data for said computer program;
• (3) performing steps (1), (2) (3), (4) and (5) of the SSAPRE optimization on said SSA representation, thereby resulting in a precise SSA graph;
• (4) performing a speculating function, using said collection of profile data, on said precise SSA graph thereby determining whether at least one .PHI. function of said precise SSA graph should be marked as being downsafe;
• (5) performing steps (4) and (5) of the SSAPRE optimization on said precise SSA graph if step (4) determines that at least one .PHI. function of said precise SSA graph should be marked as being downsafe;
• and
• (6) performing step (6) of the SSAPRE optimization on said precise SSA graph;
• whereby the compiler can produce more efficient, speculated executable program code from said precise SSA graph.

A compiler that performs speculative code motion within a single static form partial redundancy elimination (SSAPRE) optimization, comprising:

• means for accessing a static single assignment (SSA) representation of a computer program;
• means for obtaining an SSA graph of the hypothetical variable from said SSA representation of said computer program, wherein said SSA graph comprises a plurality of connected components;
• means for using a heuristic to determine a plurality of points to enable speculation within each of said plurality of connected components of said SSA graph;
• and
• means for performing the SSAPRE optimization whereby setting a down.sub.-- safety flag to true for a .PHI. function of each of said determined plurality of points within each of said plurality of connected components of said SSA graph;
• whereby the compiler can produce more efficient executable program code from said SSA graph by speculating at each of said determined plurality of points where said down safety flag is true.

A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that performs speculative code motion within a single static form partial redundancy elimination (SSAPRE) optimization, within an compiler, said computer readable program code means comprising:

• a first computer readable program code means for causing the computer to access a static single assignment (SSA) representation of a computer program;
• a second computer readable program code means for causing the computer to obtain an SSA graph of the hypothetical variable from said SSA representation of said computer program, wherein said SSA graph comprises a plurality of connected components;
• a third computer readable program code means for causing the computer to use a heuristic to determine a plurality of points to enable speculation within each of said plurality of connected components of said SSA graph;
• and
• a fourth computer readable program code means for causing the computer to perform the SSAPRE optimization whereby setting a down.sub.-- safety flag to true for a .PHI. function of each of said determined plurality of points within each of said plurality of connected components of said SSA graph;
• whereby the compiler can produce more efficient executable program code from said SSA graph by speculating at each of said determined plurality of points where said down safety flag is true.

A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that performs conservative speculative code motion within a static single assignment partial redundancy elimination (SSAPRE) register promotion compiler optimization, the SSAPRE optimization including six steps:

• (1) .PHI.-Insertion (2) Rename, (3) DownSafety, (4) WillBeAvail, (5) Finalize, and (6) CodeMotion, said computer readable program code means comprising:
• a first computer readable program code means for causing the computer to access a static single assignment (SSA) representation of a computer program;
• a second computer readable program code means for causing the computer to perform steps (1) and (2) of the SSAPRE optimization on said SSA representation, thereby obtaining a dense SSA graph of said computer program;
• a third computer readable program code means for causing the computer to perform a can.sub.-- speculate function on said dense SSA graph, thereby marking at least one .PHI. function of said dense SSA graph as being downsafe;
• and
• a fourth computer readable program code means for causing the computer to perform steps (3), (4), (5) and (6) of the SSAPRE optimization on said dense SSA graph;
• whereby the compiler can produce more efficient, speculated executable program code from said dense SSA graph.

A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that performs profile-driven speculative code motion within a static single assignment partial redundancy elimination (SSAPRE) register promotion compiler optimization, the SSAPRE optimization including six steps:

• (1) .PHI.-Insertion, (2) Rename, (3) DownSafety, (4) WillBeAvail, (5) Finalize, and (6) CodeMotion, said computer readable program code means comprising:
• a first computer readable program code means for causing the computer to access a static single assignment (SSA) representation of a computer program;
• a second computer readable program code means for causing the computer to access a collection of profile data for said computer program;
• a third computer readable program code means for causing the computer to perform steps (1), (2) (3), (4) and (5) of the SSAPRE optimization on said SSA representation, thereby resulting in a precise SSA graph;
• a fourth computer readable program code means for causing the computer to perform a speculating function, using said collection of profile data, on said precise SSA graph thereby determining whether at least one .PHI. function of said precise SSA graph should be marked as being downsafe;
• a fifth computer readable program code means for causing the computer to perform steps (4) and (5) of the SSAPRE optimization on said precise SSA graph if step (4) determines that at least one .PHI. function of said precise SSA graph should be marked as being downsafe;
• and
• a sixth computer readable program code means for causing the computer to perform step (6) of the SSAPRE optimization on said precise SSA graph;
• whereby the compiler can produce more efficient, speculated executable program code from said precise SSA graph.