Method and apparatus for performing register allocation

Patent metadata

Field	Value
Publication number	US-9841975-B2
Application number	US-201314917962-A
Country	US
Kind code	B2
Filing date	Sep 18, 2013
Priority date	Sep 18, 2013
Publication date	Dec 12, 2017
Grant date	Dec 12, 2017

Abstract

A method is provided of performing register allocation for at least one program code module. The method includes constructing a restriction graph for program variables within at least one program instruction, and determining whether the constructed restriction graph is colorable. If it is determined that the constructed restriction graph is not colorable, then the method determines whether at least one alternative form of the at least one program instruction is available, and modifies the at least one program instruction to comprise an alternative form if it is determined that at least one alternative form is available.

First claim

The invention claimed is:

1. A method executed by software instructions on a hardware processor of performing register allocation for at least one program code module, the method comprising:
constructing a restriction graph for program variables within at least one program instruction; and
performing at least a partial colourability check of the constructed restriction graph;
wherein the method further comprises, if it is determined that the constructed restriction graph is not colourable:
determining whether at least one alternative form of the at least one program instruction is available;
determining that such a restriction graph updated to take into account the alternative form of the at least one program instruction is not colourable;
determining whether at least one further alternative form of the at least one program instruction is available;
determining whether a restriction graph updated to take into account the further alternative form of the at least one program instruction is colourable; and
progressively updating the constructed restriction graph in accordance with alternative forms of the at least one program instruction until a colourable restriction graph is achievable.

2. The method of claim 1 , wherein the method comprises, if it is determined that the constructed restriction graph is not colourable:
identifying a set of instructions comprising at least one program instruction comprising program variables connected to an edge of the constructed restriction graph to be broken;
determining whether at least one alternative form of at least one program instruction within the identified set of instructions is available; and
modifying at least one program instruction within the identified set of instructions to comprise an alternative form if it is determined that at least one alternative form of at least one program instruction within the identified set of instructions is available.

3. The method of claim 1 , wherein the method further comprises, if it is determined that at least one alternative form is available:
determining whether a restriction graph updated to take into account the alternative form of the at least one program instruction is colourable; and
modifying the at least one program instruction to comprise the alternative form, if it is determined that such an updated restriction graph is colourable.

4. The method of claim 1 , wherein the method further comprises, if a colourable restriction graph is not achievable following progressively updating the restriction graph in accordance with all available alternative forms of the program instructions comprising variables within the restriction graph:
progressively reverting back to previous configurations of program instruction forms until an alternative form of at least one program instruction comprising variables within the restriction graph that produces a new configuration of program instruction forms is available;
determining whether a restriction graph updated to take into account the alternative form of the at least one program instruction that produces a new configuration of program instruction forms is colourable; and
modifying the program instructions comprising variables within the restriction graph to comprise the new configuration of program instruction forms, if it is determined that such an updated restriction graph is colourable.

5. The method of claim 1 , wherein the method comprises adding transfer instructions to the at least one program code module to achieve a colourable restriction graph if no alternative form of a program instruction comprising variables within the restriction graph that produces a new configuration of program instruction forms becomes available when progressively reverting back to previous configurations of program instruction forms.

6. The method of claim 1 , wherein the at least partial colourability check is performed at least with respect to restrictions imposed by restricted operands associated with the constructed restriction graph.

7. A computer system comprising a hardware processor and at least one signal processing module arranged to perform register allocation, the at least one signal processing module being arranged to:
construct a restriction graph for program variables within at least one program instruction; and
determine whether the constructed restriction graph is colourable;
wherein at least one signal processing module is further arranged to, if it is determined that the constructed restriction graph is not colourable:
determine whether at least one alternative form of the at least one program instruction is available;
determine that such a restriction graph updated to take into account the alternative form of the at least one program instruction is not colourable; and
determine whether at least one further alternative form of the at least one program instruction is available;
determine whether a restriction graph updated to take into account the further alternative form of the at least one program instruction is colourable; and
progressively update the constructed restriction graph in accordance with alternative forms of the at least one program instruction until a colourable restriction graph is achievable.

8. A non-transitory computer program product having executable program code stored therein for performing register allocation, the program code operable for:
constructing a restriction graph for program variables within at least one program instruction; and
determining whether the constructed restriction graph is colourable;
wherein the program code is further operable for, if it is determined that the constructed restriction graph is not colourable:
determining whether at least one alternative form of the at least one program instruction is available;
determining that such a restriction graph updated to take into account the alternative form of the at least one program instruction is not colourable;
determining whether at least one further alternative form of the at least one program instruction is available;
determining whether a restriction graph updated to take into account the further alternative form of the at least one program instruction is colourable; and
progressively updating the constructed restriction graph in accordance with alternative forms of the at least one program instruction until a colourable restriction graph is achievable.

9. The non-transitory computer program product of claim 8 , wherein the non-transitory computer program product comprises at least one from a group including: a hard disk, a CD-ROM, an optical storage device, a magnetic storage device, a Read Only Memory, ROM, a Programmable Read Only Memory, PROM, an Erasable Programmable Read Only Memory, EPROM, an Electrically Erasable Programmable Read Only Memory, EEPROM, and a Flash memory.

Assignees

• Nicolescu Andreea Florina
• Palalau Rene Catalin
• Nxp Usa Inc

Inventors

• Nicolescu Andreea Florina
• Palalau Rene Catalin

Classifications

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06F8/447

  Target code generation · CPC title

• G06F9/30145

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

• G06F9/30098 Primary

  Register arrangements · CPC title

• G06F30/30

  Circuit design · CPC title