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

• US 7,185,329 B1
• Filed: 03/28/2003
• Issued: 02/27/2007
• Est. Priority Date: 03/28/2003
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Verbitsky, George
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): DAO, THUY CHAN
• Application Number:
  US10/402,736
• Time in Patent Office: 1,432 Days
• Field of Search: 717/100, 717155-158, 717/144, 713/190, 716/1
• US Class Current: 717/156
• 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 creating a plurality of sequences of colors to be used in register allocation for a software program, the method comprising:

identifying a plurality of sizes of variables allowed in a language of the software program;

selecting a size in the plurality of sizes;

identifying a number of colors that can be used for coloring a variable of the selected size;

associating said colors with said size thereby to form a group;

ordering the colors in said group in a sequence, based on a predetermined preference; and

repeating said selecting, said identifying of number of colors, said associating and said ordering, for each size in the plurality of sizes other than said selected size.

2. The method of claim 1 further comprising:

identifying a set of registers available for register allocation;

identifying all combinations of registers in the set that can be allocated to variables of the selected size; and

associating a color with each of the identified combinations of registers;

wherein each of the associated colors is included in the group of colors to be used for coloring variables of the selected size.

3. The method of claim 1 wherein the variables hold only data, and the method further comprises:

identifying an additional group of colors that can be used for coloring a variable that holds a pointer to memory.

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

means for ordering webs of variables of the software program into a sequence (also called “

web sequence”

);

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

memory encoded with a plurality of sequences of colors, each sequence containing colors that are arranged in a specific order based on a predetermined preference;

means coupled to said memory, for identifying a color from a sequence in said plurality of sequences, wherein each color is identified one at a time in said specific order within said sequence;

means for checking if a register, associated with the color identified by said means coupled to memory, is used by a neighbor of one of the variables in the web identified by the means for identifying; and

means for using the identified color for coloring said one of the variables if the means for checking indicates that the register is not used.

5. The computer of claim 4 wherein:

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

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

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.

6. The computer of claim 4 wherein:

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

7. A method of creating a plurality of sequences of colors to be used in register allocation for a software program, the method comprising:

identifying a plurality of attributes of variables allowed in a language of the software program;

selecting an attribute in the plurality of attributes;

identifying a number of colors that can be used for coloring a variable of the selected attribute;

associating said colors with said attribute thereby to form a group;

ordering the colors in said group in a sequence, based on a predetermined preference; and

repeating said selecting, said identifying of number of colors, said associating and said ordering for each attribute in the plurality of attributes other than said selected attribute.

8. The method of claim 7 wherein:

the attribute indicates whether the variable holds data or a pointer.

9. The method of claim 7 wherein:

the attribute indicates a size of the variable.