Method for optimizing a computer program by moving certain load and store instructions out of a loop
AssigneeIntel Corporation
InventorPo-Hua Chang
Life of this patent
Estimating the term…
Abstract
A method, performed by a computer, for optimizing a computer program having a plurality of instructions that form a loop. The loop has a first block and a second block. The first block has at least one instruction for using a variable and the second block has an ambiguous definition instruction for defining the variable. A load instruction for loading the variable into a register is inserted prior to the plurality of instructions that form the loop. In addition, at least one instruction for using the variable is replaced with an instruction for using the register. Further, a load instruction for loading the variable into the register is inserted after the ambiguous definition instruction.
Claims24
A method, performed by a microprocessor, for optimizing a computer program having a plurality of instructions that form a loop, the loop having a first block and a second block, the first block having at least one instruction for using a variable, the second block having at least one ambiguous definition instruction for defining the variable, the method comprising:
- (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.
A method, performed by a microprocessor, for optimizing a computer program having a plurality of instructions that form a loop, the loop having a frequently executed block and a less frequently executed block, the frequently executed block having at least one instruction for using a variable, the less frequently executed block having 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.
A method, performed by a microprocessor, for optimizing a computer program having a plurality of instructions that form a loop, the loop having at least one exit point, a first block, and a second block, the first block having at least one unambiguous definition instruction for defining a variable and at least one instruction for using the variable, the second executed block having a ambiguous definition instruction, the method comprising:
- (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.
A method, performed by a microprocessor, for optimizing a computer program having a plurality of instructions that form a loop, the loop having at least one exit point, a frequently executed block, and a less frequently executed block, the frequently executed block having at least one unambiguous definition instruction for defining a variable and at least one instruction for using the variable, the less frequently executed block having a ambiguous definition instruction, 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 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 loop exit point.
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.