Use of different color sequences for variables of different sizes and different semantics

• US 20070074190A1
• Filed: 11/30/2006
• Published: 03/29/2007
• Est. Priority Date: 03/28/2003
• Status: Abandoned Application

• Current Assignee: Net Navigation Systems LLC
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Verbitsky, George
• Application Number:
  US11/607,314
• Publication Number:
  US 20070074190A1
• Time in Patent Office: Days
• US Class Current: 717/144
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

Colors to be used in register allocation are grouped into a number of sequences. Each sequence is associated with an attribute (e.g. size and/or type) of variables whose nodes in an interference graph can be colored by colors in the sequence. In certain embodiments, in addition to the above-described grouping, colors within a group are ordered in a sequence. The specific order that is used may depend on, for example, an attribute (such as size) and a predetermined preference. One example of such a predetermined preference is that a color that represents a register of the size that is associated with the sequence is located at the front of the sequence. Another color located later in the sequence represents a register of a different size than the size associated with the sequence.

Claims

1. A method of allocating registers to variables in a software program, the method comprising:

generating an interference graph for said software program, each node in the interference graph representing a web of a variable in the software program;

ordering nodes of the graph into a sequence (also called “

node sequence”

) in a descending order based on the number of edges of each node;

identifying a node in sequential order from the node sequence;

selecting a sequence of colors from among a plurality of sequences of colors, each sequence containing colors that are arranged in a specific order based on a predetermined preference;

identifying a color in sequential order from the selected sequence of colors;

checking if any register associated with the identified color is used by a neighbor of the identified node and if not, using the identified color for coloring the identified node; and

if the identified color cannot be used, repeatedly performing the acts of “

identifying a color” and

“

checking”

until all colors in the selected sequence are used.

2. The method of claim 1 wherein:

the attribute is size;

each sequence of colors is associated with a predetermined size from among a plurality of sizes.

3. The method of claim 2 wherein:

a first color located at the beginning of the selected sequence represents a register of the size associated with the selected sequence.

4. The method of claim 2 wherein:

a last color located at the end of the selected sequence represents another register of a larger size than the size associated with the selected sequence.

5. The method of claim 4 wherein:

the selected sequence comprises at least one more color (hereinafter “

middle color”

) located in the selected sequence between the first color and the last color, the middle color representing a plurality of registers of size equal to the size associated with the selected sequence.

6. The method of claim 5 wherein:

the selected sequence is associated with a size of N bits;

the first color represents a N bit register;

the last color represents a 2N bit register; and

the middle color represents a pair of (N/2) bit registers.

7. The method of claim 6 wherein:

the value of N is 16.

8. The method of claim 1 wherein:

the attribute is type;

each sequence of colors is identified as being suitable for a specific type.

9. The method of claim 8 wherein:

the type is one of;

data or pointer.

10. A computer programmed to allocate registers to variables in a software program, the programmed computer comprising:

means for generating an interference graph for said software program, each node in the interference graph representing a web of a variable in the software program;

means for ordering nodes of the graph into a sequence (also called “

node sequence”

) in a descending order based on the number of edges of each node;

means for identifying a node in sequential order from the node sequence;

means for selecting a sequence of colors from among a plurality of sequences of colors, each sequence containing colors that are arranged in a specific order based on a predetermined preference;

means for identifying a color in sequential order from the selected sequence of colors;

means for checking if any register associated with the identified color is used by a neighbor of the identified node and if not, using the identified color for coloring the identified node; and

means for repeatedly performing the acts of “

identifying a color” and

“

checking”

until all colors in the selected sequence are used, if the identified color cannot be used.

11. The computer of claim 10 wherein:

the attribute is size;

each sequence of colors is associated with a predetermined size from among a plurality of sizes.

12. The computer of claim 11 wherein:

a first color located at the beginning of the selected sequence represents a register of the size associated with the selected sequence.

13. The computer of claim 11 wherein:

a last color located at the end of the selected sequence represents another register of a larger size than the size associated with the selected sequence.

14. The computer of claim 13 wherein:

the selected sequence comprises at least one more color (hereinafter “

middle color”

) located in the selected sequence between the first color and the last color, the middle color representing a plurality of registers of size equal to the size associated with the selected sequence.

15. The computer of claim 14 wherein:

the selected sequence is associated with a size of N bits;

the first color represents a N bit register;

the last color represents a 2N bit register; and

the middle color represents a pair of (N/2) bit registers.

16. The computer of claim 15 wherein:

the value of N is 16.

17. The computer of claim 10 wherein:

the attribute is type;

each sequence of colors is identified as being suitable for a specific type.

18. The method of claim 17 wherein:

the type is one of;

data or pointer.