US 7,398,520 B2 · Efficient construction of pruned SSA form

Abstract

Intermediate representations of computer code are efficiently generated. More particularly, methods described herein may be used to construct a static single assignment representation of computer code without unnecessary phi-function nodes. Potentially necessary phi-function node assignments may be analyzed to determine whether they directly reach a non-phi use or a necessary phi-use of a corresponding variable. Those that ultimately reach such a use may be determined to be necessary and a pruned static single assignment may be constructed by including those potentially necessary phi-functions determined to be in fact necessary. Also, some phi-function nodes may be determined to be necessary based on their dependency relationship to other phi-functions previously determined to be necessary (e.g., because they directly reach a non-phi use). A phi-function dependency graph may be used to record dependency relationships between phi-function nodes. The analysis can proceed during a forward walk of a control flow representation of the program.

Claims17

Dependent claims

A method of generating a pruned static single assignment representation of a computer program, the method comprising:

receiving data indicative of potentially necessary phi-function nodes;
implementing an optimistic assumption that phi-function nodes are not necessary by initially marking nodes with unknown status as unnecessary;
during a forward reachability walk of a control flow representation of the computer program, determining phi-function nodes whose assignments reach non-phi uses as necessary;
during the forward reachability walk of a control flow representation of the computer program, determining other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses as necessary;
and constructing a pruned static single assignment representation of the computer program by including only those phi-function nodes that are determined to be necessary in the static single assignment representation.

2 more elements

Dependencies are inferred from the claim text.

Efficient construction of pruned SSA form

Life of this patent

Efficient construction of pruned SSA form

Life of this patent

Abstract

Claims17