Use of different color sequences for variables of different sizes and different semantics
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.
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.