Address calculation of invariant references within a run-time environment
View Patent ↗Efficient address calculation of invariant reference within a run-time environment is attained by a self-relative numeric reference format for run-time storage of references. A self-relative numeric reference format specifies the location of a reference object relative to a pointer to the referencing object as an integer value. The machine pointers and numeric references may be tagged, and a tag assignment is disclosed so that a self-relative numeric reference is generated from machine pointers by calculating a pointer difference, and a machine pointer to the referenced object is generated by adding the self-relative numeric reference to a machine pointer to the referencing object.
1. A method of generating a first tagged machine pointer to a first object referenced by a second object, said method comprising the computer-implemented steps of:
fetching a tagged numeric reference stored within the second object based on a second tagged machine pointer that points to the second object; and
generating the first tagged machine pointer as a sum including the tagged numeric reference and the second tagged machine pointer.
2. The method of claim 1 , wherein the sum further includes a predetermined constant.
3. The method of claim 1 , wherein the tagged numeric reference includes a tag portion that indicates whether the first object has a same or a different contiguity as a contiguity of the second object.
4. The method of claim 3 , wherein:
the tag portion includes N bits of the first tagged numeric reference that are less significant than bits used for an offset portion; and
the tag portion contains one of at least a first tag value indicating that the first object is contiguous and a second tag value indicating that the second object is non-contiguous, wherein a difference of the first tag value and the second tag value is congruent to 2 N−1 modulo 2 N .
5. The method of claim 1 , wherein:
tag potions of the tagged numeric reference comprise N bits and store at least a first tag value and a second value indicating complementary properties; and
a difference of the first tag value and the second tag value is congruent to 2 N−1 modulo 2 N .
6. The method of claim 1 , wherein the sum consists of the tagged numeric reference and the second tagged machine pointer.
7. A method of managing memory, comprising the computer-implemented steps of:
storing a first object and a second object in a memory, wherein the first object and the second object do not overlap each other; and
storing a reference within a first object to a second object in the memory as a numeric reference that encodes a location of the second object as an offset from an address of the first object in the memory.
8. The method of claim 7 , further comprising the step of calculating a pointer difference between a first machine pointer to the first object and a second machine pointer to the second object to produce the numeric reference.
9. The method of claim 8 , wherein the first machine pointer is a first tagged machine pointer, the second machine pointer is a second tagged machine pointer, and the numeric reference is a tagged numeric reference.
10. The method of claim 9 , wherein the pointer difference further includes a predetermined constant.
11. The method of claim 9 , wherein a tag portion of the tagged numeric reference indicates whether the first object has a same or a different contiguity as a contiguity of the second object.
12. The method of claim 11 , wherein:
the tag portion includes N bits of the tagged numeric reference that are less significant than bits used for an offset portion of the tagged numeric reference; and
the tag portion contains one of at least a first tag value indicating that the first object is contiguous and a second tag value indicating that the second object is non-contiguous, wherein a difference of the first tag value and the second tag value is congruent to 2 N−1 modulo 2 N .
13. The method of claim 7 , wherein:
the memory is subdivided into a plurality of pages;
the first object is stored on a first page; and
the second object is stored on a second page, other than the first page.
14. A computer-readable medium bearing instructions for generating a first tagged machine pointer to a first object referenced by a second object, said instructions arranged, when executed, to cause one or more processors to perform the steps of:
fetching a tagged numeric reference stored within the second object based on a second tagged machine pointer that points to the second object; and
generating the first tagged machine pointer as a sum including the tagged numeric reference and the second tagged machine pointer.
15. The computer-readable medium of claim 14 , wherein the sum further includes a predetermined constant.
16. The computer-readable medium of claim 14 , wherein the tagged numeric reference includes a tag portion that indicates whether the first object has a same or a different contiguity as a contiguity of the second object.
17. The computer-readable medium of claim 16 , wherein:
the tag portion includes N bits of the first tagged numeric reference that are less significant than bits used for an offset portion; and
the tag portion contains one of at least a first tag value indicating that the first object is contiguous and a second tag value indicating that the second object is non-contiguous, wherein a difference of the first tag value and the second tag value is congruent to 2 N−1 modulo 2 N .
18. The computer-readable medium of claim 14 , wherein:
tag potions of the tagged numeric reference comprise N bits and store at least a first tag value and a second value indicating complementary properties; and
a difference of the first tag value and the second tag value is congruent to 2 N−1 modulo 2 N .
19. The computer-readable medium of claim 14 , wherein the sum consists of the tagged numeric reference and the second tagged machine pointer.
20. A computer-readable medium bearing instructions for managing memory, said instructions arranged, when executed, to cause one or more processors to perform the steps of:
storing a first object and a second object in a memory, wherein the first object and the second object do not overlap each other; and
storing a reference within a first object to a second object in the memory as a numeric reference that encodes a location of the second object as an offset from an address of the first object in the memory.
21. The computer-readable medium of claim 20 , said instructions further arranged to cause said one or more processors to perform the step of calculating a pointer difference between a first machine pointer to the first object and a second machine pointer to the second object to produce the numeric reference.
22. The computer-readable medium of claim 21 , the first machine pointer is a first tagged machine pointer, the second machine pointer is a second tagged machine pointer, and the numeric reference is a tagged numeric reference.
23. The computer-readable medium of claim 22 , wherein the pointer difference further includes a predetermined constant.
24. The computer-readable medium of claim 22 , wherein a tag portion of the tagged numeric reference indicates whether the first object has a same or a different contiguity as a contiguity of the second object.
25. The computer-readable medium of claim 24 , wherein:
the tag portion includes N bits of the tagged self-relative numeric reference that are less significant than bits used for an offset portion; and
the tag portion contains one of at least a first tag value indicating that the first object is contiguous and a second tag value indicating that the second object is non-contiguous, wherein a difference of the first tag value and the second tag value is congruent to 2 N−1 modulo 2 N .
26. The computer-readable medium of claim 20 , wherein:
the memory is subdivided into a plurality of pages;
the first object is stored on a first page; and
the second object is stored on a second page, other than the first page.