Efficient construction of pruned SSA form
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.
1. 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. The method of claim 1 , wherein determining the phi-function nodes whose assignments reach non-phi uses comprises: maintaining a record of the phi-function assignments encountered during a reachability walk of a control flow representation of the computer program; and upon reaching a non-phi use, determining which of the previously encountered phi-function assignments it relies on.
3. The method of claim 1 , wherein determining the other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses comprises: maintaining a record of the phi-function assignments encountered during a reachability walk of a control flow representation of the computer program; upon encountering a necessary phi-function node, determining which of the previously encountered assignments it relies on.
4. The method of claim 1 , wherein determining the other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses comprises: determining relationships between phi-function nodes by constructing a phi-function dependency data structure comprising representations of dependency relationships between phi-function nodes.
5. The method of claim 4 , wherein the phi-function dependency data structure comprises: edges from the phi-function nodes comprising a potential assignment related to one or more variables of the computer program to the phi-function nodes comprising a potential use of the one of the one or more variables.
6. The method of claim 4 , wherein determining the other phi-function nodes further comprises: conducting a live-closure of the phi-function dependency data structure.
7. The method of claim 1 , wherein the forward reachability walk is a depth-first walk.
8. The method of claim 1 , wherein determining which of the potentially necessary phi-function nodes are necessary comprises: determining those potentially necessary phi-function nodes whose assignments reach a necessary phi-function node or a non-phi use of one or more variables of the computer program.
9. The method of claim 1 , wherein determining which of the potentially necessary phi-function nodes are necessary comprises: constructing a phi-function dependency data structure comprising representations of dependency relationships between the potentially necessary phi-function nodes.
10. The method claim 9 , wherein constructing the phi-function dependency data structure comprises: maintaining a record of assignment nodes encountered during the forward reachability walk; and recording edges from the recorded assignments nodes to nodes comprising a use of the one of one or more variables of the computer program.
11. The method of claim 9 , wherein determining which of the potentially necessary phi-function nodes are necessary further comprises: completing a live-closure of the phi-function dependency data structure wherein the potentially necessary phi-function nodes identified in the phi-function dependency data structure as predecessors of phi-functions previously determined to be necessary are also determined to be necessary.
12. The method of claim 1 , further comprising maintaining a data structure comprising liveness status of the potentially necessary phi-function nodes, wherein the liveness status associated with the potentially necessary phi-function nodes is initially recorded as unnecessary and updated when the potentially necessary phi-function nodes are determined to be necessary.
13. At least one computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1 .
14. In a computer system comprising a complier program for compiling computer programs a method of generating a pruned static single assignment representation of the computer program, the method comprising:
receiving data related to potentially necessary phi-function nodes;
initializing liveness status of the potentially necessary phi-function nodes as unnecessary;
constructing a phi-function dependency graph for determining phi-functions whose assignments reach non-phi-uses and for determining other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses,
the construction comprising:
during a forward reachability walk,
changing the liveness status to neccessary for those potentially necessary phi-function nodes comprising:
the phi-function nodes whose assignments reach non-phi uses and the other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses;
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.
15. The method of claim 14 , further comprising changing the liveness status to necessary for those potentially necessary phi-function nodes that are identified in the phi-function dependency graph as predecessors of necessary phi-function nodes.
16. The method of claim 14 , wherein constructing the phi-function dependency graph comprises: recording edges from the potentially necessary phi-function nodes comprising a potential assignment associated with one or more variables of the computer program to the potentially necessary phi-function nodes comprising a potential use of the one or more variables.
17. The method of claim 1 , wherein determining phi-function nodes whose assignments reach non-phi uses further comprises marking the phi-function nodes whose assignments reach non-phi uses as necessary; wherein determining other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses further comprises marking the other phi-function nodes that are relied on by the phi-function nodes whose assignments reach non-phi uses as necessary; and further comprising not including the nodes marked as unnecessary in the static single assignment representation of the computer program.