US 12,182,549 B1Granted

Color selection schemes for storage allocation

AssigneeAmazon Technologies, Inc.

InventorsPreston Pengra Briggs, Ron Diamant, Robert Geva

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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.

11 more elements

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.

11 more elements

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.

14 more elements

Dependencies are inferred from the claim text.

Facts

Application: 18/230,988Filed 7 Aug 2023 · continuation
Priority: 8 Jun 2021
Granted: 31 Dec 2024
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 8/41
Transformation of program code: compilation
G06F 8/441
Encoding: register allocation; Assignment of physical memory space to logical memory space
G06F 9/30123
Organisation of register space, e.g. banked or distributed register file: according to context, e.g. thread buffers
G06F 12/0646
Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication: configuration or reconfiguration

Family

Application17/341,762Parent of this continuation · filed 8 Jun 2021
US 11,775,268 B1Parent of this continuation
US 12,182,549 B1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key