Method for optimizing a computer program by moving certain load and store instructions out of a loop

Claim 3

The method of claim 1, wherein the first block does not have any unambiguous definition instructions.

Claim 6

The method of claim 3, wherein profiling is utilized to determine the frequently executed block and the less frequently executed block.

Claim 7

The method of claim 3, wherein the frequently executed block does not have any unambiguous definition instructions.

Claim 10

The method of claim 6, wherein the first block does not have any unambiguous definition instructions.

Claim 13

The method of claim 8, wherein profiling is utilized to determine the frequently executed block and the less frequently executed block.

Claim 14

The method of claim 8, wherein the frequently executed block does not have any unambiguous definition instructions.

Claim 15

A computer program encoded on a computer-readable medium for execution by a computer, the program including a plurality of instructions that form a loop, the loop including a first block and a second block, the first block including at least one instruction for using a variable, the second block including at least one ambiguous definition instruction for defining the variable, the computer program being formed by: (a) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop; (b) replacing the at least one instruction for using the variable with an instruction for using the register; and (c) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction.

Claim 16

A computer program encoded on a computer-readable medium for execution by a computer, the program including a plurality of instructions that form a loop, the loop including a first block and a second block, the first block including at least one instruction for using a variable, the second block including at least one ambiguous definition instruction for defining the variable, the computer program being formed by: (a) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop; (b) replacing the at least one instruction for using the variable with an instruction for using the register; and (c) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction.

Claim 17

A computer program encoded on a computer-readable medium for execution by a computer, the program including a plurality of instructions that form a loop, the loop including at least one exit point, a first block, and a second block, the first block including at least one unambiguous definition instruction for defining a variable and at least one instruction for using the variable, the second executed block including an ambiguous definition instruction, the computer program being formed by: (a) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop; (b) replacing the at least one instruction for unambiguously defining the variable with an instruction for defining the register; (c) replacing the at least one instruction for using the variable with an instruction for using the register; (d) inserting a store instruction for storing the register into the variable before the at least one ambiguous definition instruction; (e) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction; and (f) inserting an instruction for storing the register into the variable after each loop exit point.

Claim 18

A computer program encoded on a computer-readable medium for execution by a computer, the program including a plurality of instructions that form a loop, the loop including at least one exit point, a first block, and a second block, the first block including at least one unambiguous definition instruction for defining a variable and at least one instruction for using the variable, the second executed block including an ambiguous definition instruction, the computer program being formed by: (a) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop; (b) replacing the at least one instruction for unambiguously defining the variable with an instruction for defining the register; (c) replacing the at least one instruction for using the variable with an instruction for using the register; (d) inserting a store instruction for storing the register into the variable before the at least one ambiguous definition instruction; (e) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction; and (f) inserting an instruction for storing the register into the variable after each loop exit point.

Claim 19

The computer program of claim 11, wherein the first block does not have any unambiguous definition instructions.

Claim 20

The computer program of claim 12, wherein the first block does not have any unambiguous definition instructions.

Claim 21

A computer-readable medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program, the method comprising: (a) inserting a load instruction for loading a variable into a register, the load instruction being inserted prior to a plurality of instructions forming a loop, the loop further comprising: i) a first block including an instruction for using the variable; and ii) a second block including an ambiguous definition instruction for defining the variable; (b) replacing the instruction for using the variable with an instruction for using the register; and (c) inserting a load instruction for loading the variable into the register after the ambiguous definition instruction.

Claim 22

A computer-readable medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program, the method comprising: (a) inserting a load instruction for loading a variable into a register, the load instruction being inserted prior to a plurality of instructions forming a loop, the loop further comprising: i) a first block including an instruction for using the variable; and ii) a second block including an ambiguous definition instruction for defining the variable; (b) replacing the instruction for using the variable with an instruction for using the register; and (c) inserting a load instruction for loading the variable into the register after the ambiguous definition instruction.

Claim 23

The computer-readable storage medium of claim 15, wherein the first block does not include any unambiguous definition instructions.

Claim 24

A computer-readable medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program comprising a plurality of instructions forming a loop including a frequently executed block and a less frequently executed block, the frequently executed block further including at least one instruction for using a variable and the less frequently executed block further including at least one ambiguous definition instruction for defining the variable, the method comprising: (a) determining if there is sufficient profit in optimizing the frequently executed block; (b) determining if register pressure is low; and (c) if there is sufficient profit in assigning the variable to a register and register pressure is low, then i) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop; ii) replacing the at least one instruction for using the variable with an instruction for using the register; and iii) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction.

Claim 25

A computer-readable medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program comprising a plurality of instructions forming a loop including a frequently executed block and a less frequently executed block, the frequently executed block further including at least one instruction for using a variable and the less frequently executed block further including at least one ambiguous definition instruction for defining the variable, the method comprising: (a) determining if there is sufficient profit in optimizing the frequently executed block; (b) determining if register pressure is low; and (c) if there is sufficient profit in assigning the variable to a register and register pressure is low, then i) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop; ii) replacing the at least one instruction for using the variable with an instruction for using the register; and iii) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction.

Claim 26

The computer-readable medium of claim 17, wherein the method further comprises profiling the loop to determine the frequently executed block and the less frequently executed block.

Claim 27

The computer-readable medium of claim 17, wherein the frequently executed block does not have any unambiguous definition instructions.

Claim 28

A computer-readable medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program, the method comprising: (a) inserting a load instruction for loading a variable into a register, the load instruction being inserted prior to a plurality of instructions that form a loop comprising at least one exit point, a first block including at least one unambiguous definition instruction for defining the variable and at least one instruction for using the variable, and a second executed block including an ambiguous definition instruction; (b) replacing the at least one instruction for unambiguous definition instruction for defining the variable with an instruction for defining the register; (c) replacing the at least one instruction for using the variable with an instruction for using the register; (d) inserting a store instruction for storing the register into the variable before the at least one ambiguous definition instruction; (e) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction; and (f) inserting an instruction for storing the register into the variable after each loop exit point.

Claim 29

A computer-readable medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program, the method comprising: (a) inserting a load instruction for loading a variable into a register, the load instruction being inserted prior to a plurality of instructions that form a loop comprising at least one exit point, a first block including at least one unambiguous definition instruction for defining the variable and at least one instruction for using the variable, and a second executed block including an ambiguous definition instruction; (b) replacing the at least one instruction for unambiguous definition instruction for defining the variable with an instruction for defining the register; (c) replacing the at least one instruction for using the variable with an instruction for using the register; (d) inserting a store instruction for storing the register into the variable before the at least one ambiguous definition instruction; (e) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction; and (f) inserting an instruction for storing the register into the variable after each loop exit point.

Claim 30

The computer-readable medium of claim 20, wherein the first block does not have any unambiguous definition instructions.

Claim 31

A computer-readable storage medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program, the method comprising: (a) determining if there is sufficient profit in optimizing a frequently executed block in a plurality of instructions that form a loop, the loop comprising at least one exit point, the frequently executed block, and a less frequently executed block, the frequently executed block including at least one unambiguous definition instruction for defining a variable and at least one instruction for using the variable, and the less frequently executed block including an ambiguous definition instruction; (b) determining if register pressure is low; and (c) if there is sufficient profit in assigning the variable to a register and register pressure is low, then i) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop, ii) replacing the at least one instruction for unambiguously defining the variable with an instruction for defining the register, iii) replacing the at least one instruction for using the variable with an instruction for using the register, iv) inserting a store instruction for storing the register into the variable before the at least one ambiguous definition instruction, v) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction, and vi) inserting an instruction for storing the register into the variable after each exit point.

Claim 32

A computer-readable storage medium encoded with instructions that, when executed by a computer, perform a method for optimizing a computer program, the method comprising: (a) determining if there is sufficient profit in optimizing a frequently executed block in a plurality of instructions that form a loop, the loop comprising at least one exit point, the frequently executed block, and a less frequently executed block, the frequently executed block including at least one unambiguous definition instruction for defining a variable and at least one instruction for using the variable, and the less frequently executed block including an ambiguous definition instruction; (b) determining if register pressure is low; and (c) if there is sufficient profit in assigning the variable to a register and register pressure is low, then i) inserting a load instruction for loading the variable into a register, the load instruction being inserted prior to the plurality of instructions that form the loop, ii) replacing the at least one instruction for unambiguously defining the variable with an instruction for defining the register, iii) replacing the at least one instruction for using the variable with an instruction for using the register, iv) inserting a store instruction for storing the register into the variable before the at least one ambiguous definition instruction, v) inserting a load instruction for loading the variable into the register after the at least one ambiguous definition instruction, and vi) inserting an instruction for storing the register into the variable after each exit point.

Claim 33

The computer-readable medium of claim 22, wherein the method further comprises profiling utilized to determine the frequently executed block and the less frequently executed block.

Claim 34

The computer-readable medium of claim 22, wherein the frequently executed block does not have any unambiguous definition instructions.