Systems and methods for register allocation

Patent metadata

Field	Value
Publication number	US-9690584-B2
Application number	US-201414484522-A
Country	US
Kind code	B2
Filing date	Sep 12, 2014
Priority date	Oct 18, 2013
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

System and methods are provided for register allocation. An original code block and a target code block associated with a branch of an execution loop are determined. An original allocation of a plurality of physical registers to one or more original variables associated with the original code block is detected. A target allocation of the plurality of physical registers to one or more target variables associated with the target code block is determined. One or more temporary registers are selected from the plurality of physical registers based at least in part on the original allocation and the target allocation. The original allocation is changed to the target allocation using the selected temporary registers. Specifically, one or more instructions are generated to change the original allocation to the target allocation using the selected temporary registers. The instructions are executed using one or more processors.

First claim

What is claimed is:

1. A method for register allocation, the method comprising:
determining an original code block and a target code block associated with a branch of an execution loop, for execution by a processor device that comprises one or more processors and that includes physical processor registers including a first register and a second register;
detecting an original allocation of the registers to variables associated with the original code block, which has been executed by the processor device;
determining a target allocation of the registers to variables associated with the target code block, which is to be executed by the processor device;
selecting a register, from among the processor registers, to be a temporary register, based at least in part on the register conforming to at least one of (i) the register not being allocated to a variable in the original allocation and (ii) the register not being allocated to a variable in the target allocation, wherein the selection of a register to be the temporary register includes:
maintaining a first data structure having one bit for each register;
setting each first data structure having one bit to a first state in response to the corresponding register being allocated in the target allocation to a variable that is allocated to a different register in the original allocation, and otherwise setting the first data structure to a second state;
maintaining a second data structure having one bit for each register;
setting each second data structure bit to the first state in response to the corresponding register being allocated in the original allocation to a variable that is allocated to a different register in the target allocation, and otherwise setting the second data structure bit to the second state;
maintaining a third data structure having one bit for each register;
determining each third data structure bit as a Boolean logic function of the corresponding first data structure bit and the corresponding second data structure bit;
wherein the selection of a register to be a temporary register is based on the state of the corresponding third data structure bit;

changing, by the processor device, from the original allocation to the target allocation using a process that includes:
in response to determining that a first variable is allocated to the first register in the original allocation and to the second register in the target allocation, and that the second register is storing a value of a second variable,
moving the value of the first variable from the first register to the temporary register,
moving the value of the second variable from the second register to free up the second register, and
moving the value of the first variable from the temporary register to the second register, such that the first variable is not used as an execution operand while being temporarily stored in the temporary register; and

executing the target code block.

2. The method of claim 1 , wherein:
the branch of the execution loop corresponds to a backward loop branch from the original code block to the target code block; and
the execution loop further includes a forward loop branch from the target code block to the original code block.

3. The method of claim 1 , wherein the selecting the register includes:
in response to determining that the selected register is allocated to a third variable in the original allocation and not allocated in the target allocation, freeing up the selected register by moving a value of the third variable from the selected register to a storage medium.

4. The method of claim 1 , wherein the moving of the second variable from the second register includes moving the second variable from the second register to a third register in response to determining that the third register is allocated to the second variable in the target allocation.

5. The method of claim 1 , further comprising:
in response to determining that a fourth variable is not allocated in the original allocation and is allocated to a fourth register, from among the registers, in the target allocation, and that the fourth register is not currently allocated to a variable, loading a value of the fourth variable from a storage medium to the fourth register.

6. The method of claim 1 , wherein the first state is “1” and the second state is “0”, and the Boolean logic function includes ANDing the corresponding third data structure bit with an inverse of the corresponding second data structure bit, and the selection of a register to be a temporary register is based on the corresponding tempBitVector third data structure bit being a “1”.

7. A method for register allocation, the method comprising:
determining an original code block and a target code block associated with a branch of an execution loop, for execution by a processor device that comprises one or more processors and that includes physical processor registers including a first register and a second register;
detecting an original allocation of the registers to variables associated with the original code block, which has been executed by the processor device;
determining a target allocation of the registers to variables associated with the target code block, which is to be executed by the processor device;
selecting a register, from among the processor registers, to be a temporary register, based at least in part on the register conforming to at least one of (i) the register not being allocated to a variable in the original allocation and (ii) the register not being allocated to a variable in the target allocation, wherein the selection of a register to be the temporary register includes:
maintaining a first data structure having one bit for each register;
setting each first data structure having one bit to a first state in response to the corresponding register being allocated in the target allocation to a variable that is allocated to a different register in the original allocation, and otherwise setting the first data structure to a second state;
maintaining a second data structure having one bit for each register;
setting each second data structure bit to the first state in response to the corresponding register being allocated in the original allocation to a variable that is allocated to a different register in the target allocation, and otherwise setting the second data structure bit to the second state;

changing, by the processor device, from the original allocation to the target allocation using a process that includes:
in response to determining that a first variable is allocated to the first register in the original allocation and to the second register in the target allocation, and that the second register is storing a value of a second variable,
moving the value of the first variable from the first register to the temporary register,
moving the value of the second variable from the second register to free up the second register, and
moving the value of the first variable from the temporary register to the second register, such that the first variable is not used as an execution operand while being temporarily stored in the temporary register; and

executing the target code block;
maintaining a fourth data structure having one bit for each register; and
determining each fourth data structure bit as a Boolean logic function of the corresponding first data structure bit and the corresponding second data structure bit;
selecting a register, from among the registers, based on the respective fourth data structure being set in the first state; and
moving a value from the selected register to a storage medium.

8. The method of claim 7 , wherein the first state is “1” and the second state is “0”, and the Boolean logic function incl

Assignees

• Marvell World Trade Ltd

Inventors

• Jian Ningsheng
• Zhang Yuheng
• Gao Liping
• Huang Haitao
• Qi Xinyu

Classifications

• G06F9/30098 Primary

  Register arrangements · CPC title

• G06F9/30145

  Instruction analysis, e.g. decoding, instruction word fields · CPC title

• G06F8/441 Primary

  Register allocation; Assignment of physical memory space to logical memory space · CPC title