System, method, and computer program product for partial redundancy elimination based on static single assignment form during compilation

摘要

Partial redundancy elimination of a computer program is described that operates using a static single assignment (SSA) representation of a computer program. The SSA representation of the computer program is processed to eliminate partially redundant expressions in the computer program. This processing involves inserting &PHgr; functions for expressions where different values of the expressions reach common points in the computer program. A result of each of the &PHgr; functions is stored in a hypothetical variable h. The processing also involves a renaming step where SSA versions are assigned to hypothetical variables h in the computer program, a down safety step of determining whether each . PHI. function in the computer program is down safe, and a will be available step of determining whether each expression in the computer program will be available at each &PHgr; function following eventual insertion of code into the computer program for purposes of partial redundancy elimination. The processing also includes a finalize step of transforming the SSA representation of the computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination, and a code motion step of updating the SSA graph based on the insertion information to introduce real temporary variables t for the hypothetical variables h.