Language independent optimal size-based storage allocation

Abstract

Compiler performance is improved without compromising program correctness by altering the commonly expected ordering that has been used in the past. A more efficient memory image is provided which results in smaller stack frames (activation records), less required heap space (static data memory storage), improved variable access time due to better spacial locality, and improved cache-hit ratios. An optimal size space storage allocation technique optimizes the run time code, such that fewer instructions are required per each data access. A smaller local area, which is part of the activation record, is provided, such that there is a much greater level of nesting and better cache locality. Improved alignment base sorting is provided such that, based on alignment, the smallest stack frame possible is provided. Profile based optimization, which gathers information about the behavior of the program, is used to determine how best to order and layout storage during the next storage allocation pass, such that items that are accessed more often are allocated further up in the activation record. Temporal locality is used to determine what variables are going to be accessed in what order, where a graph that represents all of the variables is built up. The graph is weighted by the number of times each variable is accessed immediately before or after each other variable. Allocated variables are then laid out in such an order that variables that are accessed temporally close to each other are allocated on the same cache line. Thus, when a cache line hosting a variable is brought into the cache, the variables that are to be accessed next are also automatically brought into the cache because they have been allocated on the same cache line. Therefore, the need to retrieve additional cache lines is greatly reduced. This results in a reduced number of cache misses. Static duration storage is also used to relate to static defined data that is heap allocated.