Optimized Code Generation Targeting a High Locality Software Cache

• US 20100088673A1
• Filed: 10/07/2008
• Published: 04/08/2010
• Est. Priority Date: 10/07/2008
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Gonzalez Tallada, Marc, O'Brien, Kathryn M., Zhang, Tao, Eichenberger, Alexandre E., O'Brien, John K., Sura, Zehra N., Chen, Tong
• Granted Patent: US 8,561,044 B2
• Time in Patent Office: Days
• US Class Current: 717/110
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

Mechanisms for optimized code generation targeting a high locality software cache are provided. Original computer code is parsed to identify memory references in the original computer code. Memory references are classified as either regular memory references or irregular memory references. Regular memory references are controlled by a high locality cache mechanism. Original computer code is transformed, by a compiler, to generate transformed computer code in which the regular memory references are grouped into one or more memory reference streams, each memory reference stream having a leading memory reference, a trailing memory reference, and one or more middle memory references. Transforming of the original computer code comprises inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations associated with the leading memory reference and trailing memory reference in a different manner from initialization, lookup, and cleanup operations for the one or more middle memory references.

Claims

1. A method, in a data processing system, for optimizing regular memory references in original computer code, comprising:

parsing the original computer code to identify memory references in the original computer code;

classifying the memory references in the original computer code as either regular memory references or irregular memory references, wherein accesses to a software cache by regular memory references are controlled by a high locality cache mechanism;

transforming the original computer code, by a compiler, to generate transformed computer code; and

outputting the transformed computer code for generating executable code to be executed on a computing device, wherein transforming the original computer code comprises;

grouping regular memory references into one or more memory reference streams, each memory reference stream having a leading memory reference, a trailing memory reference, and one or more middle memory references; and

inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations associated with the leading memory reference and trailing memory reference in a different manner from initialization, lookup, and cleanup operations for the one or more middle memory references.

2. The method of claim 1, wherein grouping regular memory references into one or more memory reference streams comprises generating pairs of memory references in which, if one memory reference is present in a cache line, the other memory reference is guaranteed to be within the cache line.

3. The method of claim 1, wherein grouping regular memory references into one or more memory reference streams comprises gathering the regular memory references into one or more memory reference streams where coalesced regular memory references of a memory reference stream span less than the size of a single cache line.

4. The method of claim 3, wherein coalesced regular memory references of a memory reference stream at most span two cache lines in a software cache.

5. The method of claim 4, wherein inserting instructions in the original computer code includes inserting instructions for the one or more middle memory references to determine which cache handle of the two cache lines to use for each of the one or more middle memory references.

6. The method of claim 1, wherein inserting instructions in the original computer code inserting instructions to perform a single lookup operation for a cache line in the software cache is performed for only the leading memory reference of each memory reference stream and a single freeing operation for freeing the cache line in the software cache for replacement is performed for only the trailing memory reference of each memory reference stream, and wherein the lookup operation and freeing operation are not performed for the one or more middle memory references.

7. The method of claim 1, wherein inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations comprises, for each leading edge memory reference of each of the one or more memory reference streams:

initialization code to install a cache line corresponding to a cache line handle h1associated with the leading edge memory reference;

lookup code that determines if a number of remaining memory reference accesses in the cache line associated with the cache line handle h1 is zero or not and for looking up a cache line handle of a next cache line in the software cache if the number of remaining memory reference accesses is zero;

code for calculating a trip value that identifies a number of iterations of an inner loop to iterate over without exceeding a cache line size of the installed cache line; and

cleanup code that decrements a reference counter associated with the cache line handle h1.

8. The method of claim 7, wherein inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations comprises, for each trailing edge memory reference of each of the one or more memory reference streams:

initialization code to perform a lookup of a base address corresponding to a cache line handle h3, associated with the trailing edge memory reference, in the software cache and to determine if a cache line corresponding to the cache line handle h3 is in the software cache and load the cache line corresponding to the cache line handle h3 into the software cache if it is determined to not be in the software cache;

lookup code that determines if a number of available memory accesses in the cache line corresponding to the cache line handle h3 is greater than zero and, if not, freeing the cache line corresponding to the cache line handle h3 for replacement; and

cleanup code that determines if the cache line handle h1 is not equal to the cache line handle h3 and, if they are not equal, decrements a reference counter associated with the cache line handle h3.

9. The method of claim 8, wherein inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations comprises, for each middle memory reference of each of the one or more memory reference streams:

initialization code to perform a lookup operation of a cache line handle h2 associated with the middle memory reference;

lookup code that determines if a number of available memory accesses in a cache line associated with the cache line handle h2 is greater than zero or not and, if not, the cache line handle h2 is set to the cache line handle h1; and

code for calculating a new trip value indicating a maximum number of iterations that can be executed in the inner loop without exceeding a cache line size of the installed cache line.

10. The method of claim 1, further comprising:

reorganizing code in the transformed computer code to perform memory reference checks in an order in which memory reference checks that are most likely to result in a software cache miss are executed before memory reference checks that are less likely to result in a software cache miss.

11. A computer program product comprising a computer recordable medium having a computer readable program recorded thereon, wherein the computer readable program, when executed on a computing device, causes the computing device to:

parse the original computer code to identify memory references in the original computer code;

classify the memory references in the original computer code as either regular memory references or irregular memory references, wherein accesses to a software cache by regular memory references are controlled by a high locality cache mechanism;

transform the original computer code, by a compiler, to generate transformed computer code; and

output the transformed computer code for generating executable code to be executed on a computing device, wherein the computer readable program causes the computing device to transform the original computer code by;

grouping regular memory references into one or more memory reference streams, each memory reference stream having a leading memory reference, a trailing memory reference, and one or more middle memory references; and

inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations associated with the leading memory reference and trailing memory reference in a different manner from initialization, lookup, and cleanup operations for the one or more middle memory references.

12. The computer program product of claim 11, wherein grouping regular memory references into one or more memory reference streams comprises generating pairs of memory references in which, if one memory reference is present in a cache line, the other memory reference is guaranteed to be within the cache line.

13. The computer program product of claim 11, wherein grouping regular memory references into one or more memory reference streams comprises gathering the regular memory references into one or more memory reference streams where coalesced regular memory references of a memory reference stream span less than the size of a single cache line.

14. The computer program product of claim 13, wherein coalesced regular memory references of a memory reference stream at most span two cache lines in a software cache.

15. The computer program product of claim 14, wherein inserting instructions in the original computer code includes inserting instructions for the one or more middle memory references to determine which cache handle of the two cache lines to use for each of the one or more middle memory references.

16. The computer program product of claim 11, wherein inserting instructions in the original computer code inserting instructions to perform a single lookup operation for a cache line in the software cache is performed for only the leading memory reference of each memory reference stream and a single freeing operation for freeing the cache line in the software cache for replacement is performed for only the trailing memory reference of each memory reference stream, and wherein the lookup operation and freeing operation are not performed for the one or more middle memory references.

17. The computer program product of claim 11, wherein inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations comprises, for each leading edge memory reference of each of the one or more memory reference streams:

initialization code to install a cache line corresponding to a cache line handle h1 associated with the leading edge memory reference;

lookup code that determines if a number of remaining memory reference accesses in the cache line associated with the cache line handle h1 is zero or not and for looking up a cache line handle of a next cache line in the software cache if the number of remaining memory reference accesses is zero;

code for calculating a trip value that identifies a number of iterations of an inner loop to iterate over without exceeding a cache line size of the installed cache line; and

cleanup code that decrements a reference counter associated with the cache line handle h1.

18. The computer program product of claim 17, wherein inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations comprises, for each trailing edge memory reference of each of the one or more memory reference streams:

initialization code to perform a lookup of a base address corresponding to a cache line handle h3, associated with the trailing edge memory reference, in the software cache and to determine if a cache line corresponding to the cache line handle h3 is in the software cache and load the cache line corresponding to the cache line handle h3 into the software cache if it is determined to not be in the software cache;

lookup code that determines if a number of available memory accesses in the cache line corresponding to the cache line handle h3 is greater than zero and, if not, freeing the cache line corresponding to the cache line handle h3 for replacement; and

cleanup code that determines if the cache line handle h1 is not equal to the cache line handle h3 and, if they are not equal, decrements a reference counter associated with the cache line handle h3.

19. The computer program product of claim 18, wherein inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations comprises, for each middle memory reference of each of the one or more memory reference streams:

initialization code to perform a lookup operation of a cache line handle h2 associated with the middle memory reference;

lookup code that determines if a number of available memory accesses in a cache line associated with the cache line handle h2 is greater than zero or not and, if not, the cache line handle h2 is set to the cache line handle h1; and

code for calculating a new trip value indicating a maximum number of iterations that can be executed in the inner loop without exceeding a cache line size of the installed cache line.

20. The computer program product of claim 11, wherein the computer readable program further causes the computing device to:

reorganize code in the transformed computer code to perform memory reference checks in an order in which memory reference checks that are most likely to result in a software cache miss are executed before memory reference checks that are less likely to result in a software cache miss.

21. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

parse the original computer code to identify memory references in the original computer code;

classify the memory references in the original computer code as either regular memory references or irregular memory references, wherein accesses to a software cache by regular memory references are controlled by a high locality cache mechanism;

transform the original computer code, by a compiler, to generate transformed computer code; and

output the transformed computer code for generating executable code to be executed on a computing device, wherein the instructions causes the processor to transform the original computer code by;

grouping regular memory references into one or more memory reference streams, each memory reference stream having a leading memory reference, a trailing memory reference, and one or more middle memory references; and

inserting, into the original computer code, instructions to execute initialization, lookup, and cleanup operations associated with the leading memory reference and trailing memory reference in a different manner from initialization, lookup, and cleanup operations for the one or more middle memory references.