US 2026/0299904 A1 · COMPILER-AUTOMATED COLLECTION ELEMENT ADDRESS COMPRESSION AND ACCESS

Abstract

A compiler automatically generates pointer-compression instructions for collections. An index size is determined to index each collection element uniquely. Index values are stored in respective segments in a register. Each can be retrieved by applying a shift value and a mask to isolate it, to access an element at runtime. Throughput is increased with repeated accesses without reloading the register. Compressing access instructions reduces memory requirements and reduces cache misses. In one model, a mapping table for the collection includes physical addresses for each element. In another, the collection is instantiated such that its elements have physical memory addresses aligned with a scaling factor to allow direct access with an appropriately scaled index. Instructions to pack pointers into values for loading in an offset register are compiler-generated, as well as instructions necessary for pointer selection and memory access. Dynamic updating of models are supported: changes in number and/or size of elements result in corresponding changes to index size and number of segments during runtime. With the compiled executable, pointer compression is performed at runtime automatically and accurately without intervention in source code by a programmer.

Claims22

Dependent claims

A method of compiling source code defining a collection with a plurality of elements to be instantiated in a memory at runtime, the method comprising:

determining an index size as the number of bits required to index each of the elements in the collection uniquely;
and
generating instructions compilable to runtime instructions operable with a register to:
specify a mask of the index size;
specify a shift value responsive to an instruction to access an element of the collection;
select an index value stored in one of a plurality of segments of the register by masking with the mask and shifting according to the shift value;
and
access the element of the collection in the memory using the selected index value.

5 more elements

A method comprising:

instantiating in a memory a collection comprising a plurality of elements, the collection having a memory location associated with a base address, each of the plurality of elements having memory locations referenceable by one of a plurality of offsets from the base address;
determining a first index size as the number of bits required to index each of the collection elements uniquely;
loading a base register in a processor with the base address;
loading an offset register in the processor with a first packed value comprising a first plurality of concatenated pointers each having the first index size and each associated with one of the plurality of elements;
accessing the memory at an element address derived by extracting one of the concatenated pointers from the offset register and adding the extracted pointer to the base register;
modifying the collection;
determining whether the first index size is suitable to index each of the modified elements of the collection uniquely;
responsive to the first index size not being suitable, recomputing a second index size as the number of bits required to index each of the modified collection elements uniquely;
loading the offset register in the processor with a second packed value comprising a second plurality of concatenated pointers each having the second index size and each associated with one of the plurality of elements;
and
accessing the memory at an element address derived by extracting one of the concatenated pointers from the offset register and adding the extracted pointer to the base register.

8 more elements

A system comprising:

one or more processors;
a memory coupled to the one or more processors;
and
one or more programs stored in the memory and configured to be executed by the one or more processors, the one or more programs including program instructions operable to:
instantiate in the memory a collection comprising a plurality of elements, the collection having a memory location associated with a base address, each of the plurality of elements having memory locations referenceable by one of a plurality of offsets from the base address;
determine a first index size as a number of bits required to index each of the collection elements uniquely;
load a base register with the base address;
load an offset register with a first packed value comprising a first plurality of concatenated pointers, each having the first index size and associated with one of the plurality of elements;
access the memory at an element address derived by extracting one of the concatenated pointers from the offset register and adding the extracted pointer to the base register;
modify the collection;
determine whether the first index size is suitable to index each of the modified collection elements uniquely;
responsive to the first index size not being suitable, recompute a second index size as the number of bits required to index each of the modified collection elements uniquely;
load the offset register with a second packed value comprising a second plurality of concatenated pointers each having the second index size and associated with one of the plurality of elements;
and
access the memory at an element address derived by extracting one of the concatenated pointers from the offset register and adding the extracted pointer to the base register.

12 more elements

Dependencies are inferred from the claim text.

Compiler-automated collection element address compression and access

Life of this patent

Compiler-automated collection element address compression and access

Life of this patent

Abstract

Claims22