Method for identifying partial redundancies in a new processor architecture

Claim 1

A method for compiling at least a portion of a computer program, the method comprising: (a) inserting a phi-function for a global variable reaching a join point in an intermediate language representation subsequent to the join point even in the presence of ambiguity; (b) renaming a definition and any subsequent use of the definition in the intermediate language representation; and (c) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

Claim 2

A method for compiling at least a portion of a computer program, the method comprising: (a) inserting a phi-function for a global variable reaching a join point in an intermediate language representation subsequent to the join point even in the presence of ambiguity; (b) renaming a definition and any subsequent use of the definition in the intermediate language representation; and (c) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

Claim 21

A method for compiling at least a portion of a computer program, wherein a phi-function having a plurality of operands has been inserted for a global variable reaching a join point subsequent to the join point and a definition and any subsequent use thereof has been renamed, the method comprising: (a) identifying a partially redundant load by determining whether the inserted phi-function contains an unregisterized operand; (b) inserting an advanced load preceding the join point along an unbalanced flow control path of the operands in the phi-function; and (c) inserting a load check prior to each use of the unregisterized operand subsequent to the advanced load.

Claim 22

A method for compiling at least a portion of a computer program, wherein a phi-function having a plurality of operands has been inserted for a global variable reaching a join point subsequent to the join point and a definition and any subsequent use thereof has been renamed, the method comprising: (a) identifying a partially redundant load by determining whether the inserted phi-function contains an unregisterized operand; (b) inserting an advanced load preceding the join point along an unbalanced flow control path of the operands in the phi-function; and (c) inserting a load check prior to each use of the unregisterized operand subsequent to the advanced load.

Claim 33

A method for compiling at least a portion of a computer program, the method comprising: (a) determining a flow of control along an execution path through an intermediate language representation of the portion of the computer program; (b) ascertaining a dominance relationship from the flow of control; (c) identifying a global variable in the intermediate language representation reaching a join point; (d) inserting a phi-function having a plurality of operands for the global variable in the intermediate language representation subsequent to the join point as indicated by the dominance relationship even in the presence of ambiguity; (e) renaming a definition and any subsequent use of the definition in the intermediate language representation; and (f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

Claim 34

A method for compiling at least a portion of a computer program, the method comprising: (a) determining a flow of control along an execution path through an intermediate language representation of the portion of the computer program; (b) ascertaining a dominance relationship from the flow of control; (c) identifying a global variable in the intermediate language representation reaching a join point; (d) inserting a phi-function having a plurality of operands for the global variable in the intermediate language representation subsequent to the join point as indicated by the dominance relationship even in the presence of ambiguity; (e) renaming a definition and any subsequent use of the definition in the intermediate language representation; and (f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

Claim 57

A method for compiling at least a portion of a computer program into machine readable object code, the method comprising: (a) determining a flow of control along an execution path through an intermediate language representation of the portion of the computer program; (b) ascertaining a dominance relationship from the flow of control; (c) identifying a global variable in the intermediate language representation reaching a join point; (d) inserting a phi-function having a plurality of operands for the global variable in the intermediate language representation subsequent to the join point as indicated by the dominance relationship; (e) renaming a definition and only subsequent use of the definition in the intermediate language representation; (f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed; and (g) eliminating the partial redundancy of the identified partially redundant load by inserting: (1) an advanced load preceding a join point along an unbalanced flow control path of the operands in the inserted phi-function; and (2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

Claim 58

A method for compiling at least a portion of a computer program into machine readable object code, the method comprising: (a) determining a flow of control along an execution path through an intermediate language representation of the portion of the computer program; (b) ascertaining a dominance relationship from the flow of control; (c) identifying a global variable in the intermediate language representation reaching a join point; (d) inserting a phi-function having a plurality of operands for the global variable in the intermediate language representation subsequent to the join point as indicated by the dominance relationship; (e) renaming a definition and only subsequent use of the definition in the intermediate language representation; (f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed; and (g) eliminating the partial redundancy of the identified partially redundant load by inserting: (1) an advanced load preceding a join point along an unbalanced flow control path of the operands in the inserted phi-function; and (2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

Claim 78

A method for compiling at least a portion of a computer program into machine readable object code, the method comprising: (a) determining a flow of control along each execution path through an intermediate language representation, including constructing at least one of a flow control graph and a dominator-join graph; (b) ascertaining a dominance relationship from the flow of control, including: (1) constructing at least one of a dominator tree and a dominator-join graph; and (2) calculating an iterative dominance frontier for each instruction, (c) identifying each global variable in the intermediate language representation; (d) inserting a phi-function for each global variable reaching a join point in the intermediate language representation as indicated by the dominance relationship even in the presence of ambiguity, including maintaining a linked list of a plurality of inserted phi-function locations; (e) renaming a definition and subsequent uses thereof in the intermediate language representation, the renaming including: (1) performing a depth-first ordered traversal of the intermediate language representation; and (2) assigning temp values to each rank-n expression; (f) repeating acts (b)-(e) at least once to create a rank-n SSA intermediate language where n is a positive integer greater than zero; (g) identifying a partially redundant load by determining whether the inserted phi-function contains an unregisterized operand; (h) eliminating the identified partial redundancy by inserting: (1) an advanced load into a basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregisterized operand; and (2) a load check immediately prior to each use of the unregisterized operand subsequent to the advanced load; and (i) generating machine readable code.

Claim 79

A method for compiling at least a portion of a computer program into machine readable object code, the method comprising: (a) determining a flow of control along each execution path through an intermediate language representation, including constructing at least one of a flow control graph and a dominator-join graph; (b) ascertaining a dominance relationship from the flow of control, including: (1) constructing at least one of a dominator tree and a dominator-join graph; and (2) calculating an iterative dominance frontier for each instruction, (c) identifying each global variable in the intermediate language representation; (d) inserting a phi-function for each global variable reaching a join point in the intermediate language representation as indicated by the dominance relationship even in the presence of ambiguity, including maintaining a linked list of a plurality of inserted phi-function locations; (e) renaming a definition and subsequent uses thereof in the intermediate language representation, the renaming including: (1) performing a depth-first ordered traversal of the intermediate language representation; and (2) assigning temp values to each rank-n expression; (f) repeating acts (b)-(e) at least once to create a rank-n SSA intermediate language where n is a positive integer greater than zero; (g) identifying a partially redundant load by determining whether the inserted phi-function contains an unregisterized operand; (h) eliminating the identified partial redundancy by inserting: (1) an advanced load into a basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregisterized operand; and (2) a load check immediately prior to each use of the unregisterized operand subsequent to the advanced load; and (i) generating machine readable code.

Claim 80

A method for compiling at least a portion of high-level source code, into machine readable object code, the method comprising: (a) determining a flow of control along each execution path through an intermediate language representation, including: (1) constructing at least one of the following: (A) a flow control graph; and (B) a dominator-join graph; (b) ascertaining a dominance relationship from the flow of control, including: (1) constructing at least one of the following: (A) a dominator tree; and (B) a dominator-join graph; and (2) calculating an iterative dominance frontier for each instruction, (c) identifying each global variable in the intermediate language representation; (d) inserting a phi-function for each global variable in the intermediate language representation as indicated by the dominance relationship, including maintaining a linked list of inserted phi-function locations; (e) renaming definitions in the intermediate language representation, the renaming including: (1) performing a depth-first ordered traversal of the intermediate language representation; and (2) assigning temp values to each rank-n expression; (f) repeating acts (b)-(e) at least once to create a rank-n SSA intermediate language where n is a positive integer greater than zero; (g) identifying a partial redundancy by determining whether an inserted phi-function contains an unregisterized operand; (h) eliminating the identified partial redundancy by inserting: (1) an advanced load into a basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregisterized operand; and (2) a load check immediately prior to each use of the unregisterized operand subsequent to the advanced load; (i) eliminating a second identified partial redundancy by at least one of the following: (1) inserting an artificial load into the basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregistered operand after identifying the partial redundancy; and (2) moving the second identified partially redundant load to a nearest common ancestor in the dominance relationship of the operands in at least one phi-function containing the unregistered operand after identifying the partial redundancy; and (j) generating machine readable code.

Claim 81

A method for compiling at least a portion of high-level source code, into machine readable object code, the method comprising: (a) determining a flow of control along each execution path through an intermediate language representation, including: (1) constructing at least one of the following: (A) a flow control graph; and (B) a dominator-join graph; (b) ascertaining a dominance relationship from the flow of control, including: (1) constructing at least one of the following: (A) a dominator tree; and (B) a dominator-join graph; and (2) calculating an iterative dominance frontier for each instruction, (c) identifying each global variable in the intermediate language representation; (d) inserting a phi-function for each global variable in the intermediate language representation as indicated by the dominance relationship, including maintaining a linked list of inserted phi-function locations; (e) renaming definitions in the intermediate language representation, the renaming including: (1) performing a depth-first ordered traversal of the intermediate language representation; and (2) assigning temp values to each rank-n expression; (f) repeating acts (b)-(e) at least once to create a rank-n SSA intermediate language where n is a positive integer greater than zero; (g) identifying a partial redundancy by determining whether an inserted phi-function contains an unregisterized operand; (h) eliminating the identified partial redundancy by inserting: (1) an advanced load into a basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregisterized operand; and (2) a load check immediately prior to each use of the unregisterized operand subsequent to the advanced load; (i) eliminating a second identified partial redundancy by at least one of the following: (1) inserting an artificial load into the basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregistered operand after identifying the partial redundancy; and (2) moving the second identified partially redundant load to a nearest common ancestor in the dominance relationship of the operands in at least one phi-function containing the unregistered operand after identifying the partial redundancy; and (j) generating machine readable code.