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

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.

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.