# US 12,182,549 B1 · Color selection schemes for storage allocation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,182,549 B1 - Document ID: US12182549B1 - Status: Granted - Kind: B1 - Application number: 18/230,988 - Filed: 2023-08-07 - Granted: 2024-12-31 - Earliest claimed: 2021-06-08 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Preston Pengra Briggs; Ron Diamant; Robert Geva - Web page: https://patentgrep.com/patent/US12182549B1 ## CPC - G06F 8/41: Compilation - G06F 8/441: {Register allocation; Assignment of physical memory space to logical memory space} - G06F 9/30123: {according to context, e.g. thread buffers} - G06F 12/0646: {Configuration or reconfiguration} - G06F 2212/1024: Latency reduction - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A compiler-implemented technique for performing a storage allocation is described. Computer code to be converted into machine instructions for execution on an integrated circuit device is received. The integrated circuit device includes a memory having a set of memory locations. Based on the computer code, a set of values that are to be stored on the integrated circuit device are determined. An interference graph that includes the set of values and a set of interferences is constructed. While traversing the interference graph, a set of memory location assignments are generated by assigning the set of values to the set of memory locations in accordance with one or more color selection schemes. ## Claims ### Claim 1 A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions configured to cause a processor to perform operations for executing a compiler, the operations comprising: determining a set of values that are to be stored at a set of memory locations of an integrated circuit device based on computer code; constructing an interference graph that includes the set of values and a set of interferences connecting the set of values, each of the set of interferences connecting two of the set of values that are concurrently stored during execution of machine instructions on the integrated circuit device; performing a simplification process to incrementally remove each value of the set of values from the interference graph in accordance with a first order until all values are removed; at a particular point while performing the simplification process: determining that none of the remaining set of values are connected to a quantity of other values that is less than a threshold; selecting one of the remaining set of values to be a spill candidate; removing the spill candidate from the interference graph; and continuing performing the simplification process until all values in the interference graph are removed; performing a rebuilding process to add the set of values back to the interference graph in accordance with a second order determined from the first order by repeatedly assigning one of the set of values to one of the set of memory locations in accordance with a first color selection scheme; at the particular point at which the spill candidate was removed from the interference graph, and while performing the rebuilding process, switching from the first color selection scheme to a second color selection scheme that is different from the first color selection scheme; continuing the rebuilding process to add the remaining set of values back to the interference graph in accordance with the second order by repeatedly assigning one of the remaining set of values to one of the set of memory locations in accordance with the second color selection scheme; and generating, by the compiler, the machine instructions incorporating the assigned set of values to the set of memory locations. ### Claim 2 (depends on 1) The computer-program product of claim 1, wherein performing the simplification process includes, repeatedly: identifying a value of the set of values that is connected to a quantity of other values less than the threshold; and removing the value from the interference graph. ### Claim 3 (depends on 1) The computer-program product of claim 1, wherein the first color selection scheme is a color reuse scheme that provides that a set of colors are unevenly considered for selection for the set of values. ### Claim 4 (depends on 3) The computer-program product of claim 3, wherein the second color selection scheme is a color rotation scheme that provides that the set of colors are sequentially and evenly considered for selection for the set of values. ### Claim 5 (depends on 1) The computer-program product of claim 1, wherein the operations further comprise: receiving the computer code to be converted into the machine instructions for execution on the integrated circuit device. ### Claim 6 (depends on 1) The computer-program product of claim 1, wherein the set of memory locations are of a memory comprising a set of processor registers, a scratchpad memory, or a cache. ### Claim 7 (depends on 1) The computer-program product of claim 1, wherein the computer code is an intermediate representation of source code. ### Claim 8 (depends on 1) The computer-program product of claim 1, wherein each of the set of values is one of a scalar, a vector, a tensor, or an array. ### Claim 9 A computer-implemented method comprising: determining a set of values that are to be stored at a set of memory locations of an integrated circuit device based on computer code; constructing an interference graph that includes the set of values and a set of interferences connecting the set of values, each of the set of interferences connecting two of the set of values that are concurrently stored during execution of machine instructions on the integrated circuit device; performing a simplification process to incrementally remove each value of the set of values from the interference graph in accordance with a first order until all values are removed; at a particular point while performing the simplification process: determining that none of the remaining set of values are connected to a quantity of other values that is less than a threshold; selecting one of the remaining set of values to be a spill candidate; removing the spill candidate from the interference graph; and continuing performing the simplification process until all values in the interference graph are removed; performing a rebuilding process to add the set of values back to the interference graph in accordance with a second order determined from the first order by repeatedly assigning one of the set of values to one of the set of memory locations in accordance with a first color selection scheme; at the particular point at which the spill candidate was removed from the interference graph, and while performing the rebuilding process, switching from the first color selection scheme to a second color selection scheme that is different from the first color selection scheme; continuing the rebuilding process to add the remaining set of values back to the interference graph in accordance with the second order by repeatedly assigning one of the remaining set of values to one of the set of memory locations in accordance with the second color selection scheme; and generating, by a compiler, the machine instructions incorporating the assigned set of values to the set of memory locations. ### Claim 10 (depends on 9) The computer-implemented method of claim 9, wherein performing the simplification process includes, repeatedly: identifying a value of the set of values that is connected to a quantity of other values less than the threshold; and removing the value from the interference graph. ### Claim 11 (depends on 9) The computer-implemented method of claim 9, wherein the first color selection scheme is a color reuse scheme that provides that a set of colors are unevenly considered for selection for the set of values. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, wherein the second color selection scheme is a color rotation scheme that provides that the set of colors are sequentially and evenly considered for selection for the set of values. ### Claim 13 (depends on 9) The computer-implemented method of claim 9, further comprising: receiving the computer code to be converted into the machine instructions for execution on the integrated circuit device. ### Claim 14 (depends on 9) The computer-implemented method of claim 9, wherein the set of memory locations are of a memory comprising a set of processor registers, a scratchpad memory, or a cache. ### Claim 15 (depends on 9) The computer-implemented method of claim 9, wherein the computer code is an intermediate representation of source code. ### Claim 16 (depends on 9) The computer-implemented method of claim 9, wherein each of the set of values is one of a scalar, a vector, a tensor, or an array. ### Claim 17 A system comprising: one or more processors; and a non-transitory computer-readable medium comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform operations for executing a compiler, the operations comprising: determining a set of values that are to be stored at a set of memory locations of an integrated circuit device based on computer code; constructing an interference graph that includes the set of values and a set of interferences connecting the set of values, each of the set of interferences connecting two of the set of values that are concurrently stored during execution of machine instructions on the integrated circuit device; performing a simplification process to incrementally remove each value of the set of values from the interference graph in accordance with a first order until all values are removed; at a particular point while performing the simplification process: determining that none of the remaining set of values are connected to a quantity of other values that is less than a threshold; selecting one of the remaining set of values to be a spill candidate; removing the spill candidate from the interference graph; and continuing performing the simplification process until all values in the interference graph are removed; performing a rebuilding process to add the set of values back to the interference graph in accordance with a second order determined from the first order by repeatedly assigning one of the set of values to one of the set of memory locations in accordance with a first color selection scheme; at the particular point at which the spill candidate was removed from the interference graph, and while performing the rebuilding process, switching from the first color selection scheme to a second color selection scheme that is different from the first color selection scheme; continuing the rebuilding process to add the remaining set of values back to the interference graph in accordance with the second order by repeatedly assigning one of the remaining set of values to one of the set of memory locations in accordance with the second color selection scheme; and generating, by the compiler, the machine instructions incorporating the assigned set of values to the set of memory locations. ### Claim 18 (depends on 17) The system of claim 17, wherein performing the simplification process includes, repeatedly: identifying a value of the set of values that is connected to a quantity of other values less than the threshold; and removing the value from the interference graph. ### Claim 19 (depends on 17) The system of claim 17, wherein the first color selection scheme is a color reuse scheme that provides that a set of colors are unevenly considered for selection for the set of values. ### Claim 20 (depends on 19) The system of claim 19, wherein the second color selection scheme is a color rotation scheme that provides that the set of colors are sequentially and evenly considered for selection for the set of values.