Control transfer table structuring

It has been discovered that a control transfer table can be structured to reduce the overhead resulting from its use (e.g., misses from accessing the control transfer table). Entries of a control transfer table (e.g., a jump table or a procedure linkage table) can be organized in accordance with their respective use frequencies, as well as other parameters. For example, entries can be organized in a manner that would group the most frequently used entries, thus facilitating their contemporaneous availability in a memory (e.g., cache). The use frequencies may be determined from profile information for a code that references the control transfer table.

BACKGROUND

1. Field of the Invention

The present invention relates to the field of computers, and more specifically relates to structuring control transfer tables.

2. Description of the Related Art

The typical software application consists of a dynamically linked executable and several shared objects (or dynamic libraries) which are linked together at runtime to form an executable process. The main executable and shared objects that it depends on are called loadable objects or modules. Since there are usually numerous cross-module dependencies that cannot be resolved at compile time, the compiler and linker provide facilities that reduce the amount of work that needs to be done at runtime. One such facility is a control transfer table (e.g., a Procedure Linkage Table (PLT), a jump table, etc.). A control transfer table is used for execution transfers (such as function calls) from one module to another. Whenever a cross-module execution transfer request occurs in code, a compiler generates instructions to transfer execution locally to an entry in the control transfer table. The first time this entry actually gets called, the runtime linker updates it to transfer execution to the requested function in another module. Effectively, all calls to an external function go through one place, the control transfer table. Instead of updating all of these calls at runtime to refer to the external function, only the entry for the external function is updated.

While a control transfer table provides flexibility, it also induces an overhead on the cross-module function calls. Each cross-module function call goes through a control transfer code that consists of an address calculation and a jump to the called function. This code is loaded and executed, which puts additional demand on the memory hierarchy. The random nature of control transfer table generation results in a less effective memory hierarchy utilization. This overhead from the control transfer table can adversely impact the performance, especially for more cache-hungry applications. In large transaction processing applications, control transfer table related cache misses may account for more than 3% of all the instruction cache misses. Furthermore, the overhead may be even more noticeable in applications that have large control transfer tables spanning multiple memory pages. The most frequently accessed entries (i.e., the hot entries) in these tables are usually sparse, which results in heavier paging.

Modern compilers provide numerous optimizations that restructure code in an attempt to better utilize the underlying system's memory hierarchy (e.g., function and basic block ordering). However, restructuring a control transfer table goes beyond the realm of compiler optimizations, because a control transfer table is created by a linker. The compiler has little control over construction of the control transfer table by the linker.

SUMMARY

It has been discovered that a control transfer table can be structured to reduce misses from accessing the control transfer table. The structuring can rely on collected profile information that indicates execution frequency (hotness) of entries of the control transfer table. A software tool utilizes this information to structure or organize the control transfer table in accordance with hotness of the entries, as well as particular characteristics of an architecture and/or an application. Entries can be regrouped with various techniques, such as ordering by hotness, which facilitates increased density of the most frequently used entries. Other techniques may be based on caller-callee relationships, cache line sizes, identifying the code/data that a particularly placed entry will clash with and avoiding placement that may lead to “hot code/data/entry-hot entry” clashes, etc. These techniques ensure that when a portion of the control transfer table is fetched one level closer to the processor, this portion contains more heavily used entries, as well as fewer underutilized entries likely to be evicted due to a conflict with other parts of the program. For example, if hot entries are grouped together, a fetch of a hot entry will also bring its hot neighbors to the cache, making them available for access as well (more cache hits) and thus lowering a chance for a cache miss by not polluting the cache with underutilized, cold entries.

DESCRIPTION OF THE PREFERRED EMBODIMENT(S)

The description that follows includes exemplary systems, methods, techniques, instruction sequences and computer program products that embody techniques of the present invention. However, it is understood that the described invention may be practiced without these specific details. For instance, reference is made to a control transfer table which may be a jump table, a procedure linkage table, etc. In addition, although some ordering techniques are described in detail, these described techniques and other techniques may be employed individually or in various combinations to improve memory hierarchy performance. For example, a given number of those entries of a control transfer table that exceed a threshold of executions may be ordered instead of ordering all entries of the table. In other instances, well-known protocols, structures and techniques have not been shown in detail in order not to obscure the invention.

Ordering entries of a control transfer table by hotness creates a concentrated hot area. Most of the control transfer table related fetches will be from that area, and most of the fetched entries will be hot entries. Having a greater number of hotter entries reside in memory longer improves the chances of finding the next needed entry already available in memory, thus reducing misses in memory (e.g., instruction cache misses, external cache misses, etc.), as well as prevent entries from evicting each other. This ordering also reduces page fault rate, which typically occurs from sparse population of hot entries of a control transfer table over multiple pages. A concentrated hot area normally fits into just a few of the pages that are normally used. This also reduces the number of translation buffer (i.e., TLB) misses as there will be fewer address translations that need to be cached.

FIG. 1depicts an exemplary software tool that generates a compatibility preservation redirection table and an ordered control transfer table. A control transfer table101is input into a software tool103. The control transfer table101may be separate from its corresponding executable code or part of an executable code or binary, etc. The software tool103may be part of a code execution environment such as a runtime linker, a separate tool within the code execution environment, a tool within a code preparation environment such as a static linker, a tool separate from the code preparation environment, etc. The software tool103reads profile information105for the control transfer table101. The profile information105may be embedded in object files, binary, separate files, etc. Any of a number of techniques may be used to obtain the profile information105(e.g., a compiler mechanism, a tool that instruments binary for profiling, hardware profiling, etc.).

The profile information105indicates access frequency, or hotness, of the control transfer table101entries. The software tool103may be a linker that reads the profile information from a file generated by a compiler or reads the intermediate code representations with embedded profile information, may be a tool that reads a binary produced by a compiler and linker with profile information embedded inside or a separate file with profile information, may be a tool that has access to profile counts in an optimized binary generated from a version of the original binary instrumented by a tool to collect execution counts, etc. The software tool103reads the profile information105and, in accordance with the profile information, orders the entries of the control transfer table101to generate a new ordered control transfer table109.

Profile information may be applied for grouping of hot control transfer table entries differently. For example, if profile information for the entries is not directly available, a tool may read profile information for basic blocks from an input binary, object files or separate file, and propagate the profile counts for the basic blocks to the entries used in these blocks. Propagating the profile information, for example, involves applying code block execution counts to the entries of the control transfer table. If a code block includes references to 2 entries and the code block is executed 10,000 times, then each of the referenced entries is considered as accessed 10,000 times. In another example, a static linker reads profile information stored in input object files, and creates a list of the control transfer table entries. The static linker then propagates the profile information to the list and groups the entries in accordance with hotness (e.g., orders the entries according to hotness). The linker generates a binary with an ordered control transfer table.

In addition, the software tool103modifies the initial control transfer table101and generates a compatibility preservation redirection table107, which maintains compatibility with code that is not updated to reference the new control transfer table109. A software tool that reads a program with a control table already constructed (e.g., by a linker), such as a software tool separate from a code preparation environment, generates the compatibility preservation redirection table. However, if regrouping or structuring of the control transfer table is implemented by a software tool that is part of a code preparation environment, such as a linker, then the software tool may not generate a compatibility preservation redirection table. For example, a static linker may be extended to structure a control transfer table to concentrate entries according to hotness of entries during construction of the control transfer table. The static linker receives object files of a program as input with relocations that require construction of the control transfer table. Grouping together of the hottest entries defines the order of the entries in the control transfer table. The software tool resolves these locations in code causing the program to use the defined order. Depending on the implementation of the software tool, the software tool may generate the new ordered control transfer table109after construction of the control transfer table as inFIG. 1, during construction of the control transfer table, for example by a linker, etc.

FIG. 1is provided as an exemplary illustration. Various techniques can be applied to structure a control transfer table. These techniques may include, but are not limited to, techniques based on caller-callee relationships, reducing conflicts, etc. These techniques can be introduced individually, or be applied in coordination to facilitate efficient utilization of a control transfer table. Exemplary structuring of a control transfer table based on caller-callee relationships involves (1) building a call graph, (2) building sequences of entries that are likely to be used shortly one after another, and (3) building the final entry order from these sequences. Grouping the entries of a control transfer table to minimize the number of clashes of entries with other parts of the program, such as code, data, other entries, etc. Exemplary structuring of a control transfer tabled based on reducing conflicts involves (1) finding units (e.g., blocks, modules, etc.) of the program that will fight for the same memory locations as the entries, (2) deciding if an entry can be placed against a part of the program (based on entry's and the unit's hotness), and (3) finding a better location for the new (optimized) table. In addition to employing the above techniques or any combination of the above techniques or other techniques, can be enhanced with additional knowledge of a program and/or architecture.

FIG. 2depicts use of the new ordered control transfer table and the compatibility preservation redirection table. Each of the entries of the compatibility preservation redirection table107references a corresponding entry in the new ordered control transfer table109. A code201that has not been updated to reference the new ordered control transfer table109(either cannot or need not be updated) references the entries of the compatibility preservation redirection table107. The code201may not be updated because it has been designated as non-modifiable code (e.g., to prevent optimizations that may incur undesired side effects). If the software tool cannot recognize references to the new ordered control transfer table109, then it cannot update code to reference the new ordered control transfer table109. If a user does not want to the software tool to update certain references to the control transfer table, then the software tool does not update those references. When the code201references the compatibility preservation redirection table107, the mechanism that handles the control transfer (e.g., a separate thread, a trap handler, etc.) reads the referenced entry and follows a reference to a corresponding entry of the new ordered control transfer table109(i.e., control is transferred to a corresponding entry in the new ordered control transfer table109). An updated code203directly references the entries of the new ordered control transfer table109.

As previously stated, a control transfer table may be modified to group entries by hotness and preserve compatibility with code that was not updated.FIG. 3depicts an exemplary tool that modifies a control transfer table to impose a new order on entries. In the example illustrated byFIG. 3, the new imposed order is in accordance with hotness of entries. A software tool303receives a control transfer table301as input (e.g., as part of a binary). The software tool303reads profile information305, which is similar to the profile information105ofFIG. 1. However, instead of generating a new control transfer table, the software tool303rewrites the control transfer table301and orders the entries in accordance with the profile information305. The rewritten control transfer table309includes embedded references to preserve compatibility with non-annotated code.

FIG. 4depicts exemplary use of the rewritten control transfer table. The rewritten control transfer table309includes entries405and407. The entry405has been modified to indicate an Old G indirection reference for a new entry G and a reference for a new entry F. The Old G is maintained for compatibility with a non-updated code401. The entry405has been modified to branch to a new location within the control transfer table309of the reference to new entry G, which is at entry407, to preserve compatibility as well as indicate an entry that has been moved to reorder entries by their hotness. A code403is updated to use the new entry locations F (frequently used) and G (less frequently used and moved to occur later in the control transfer table309), respectively found at entries405and407.

When the non-updated code401is executed, a reference to entry G is encountered. The non-updated code401requests access to the original location of G in the control transfer table309, which is entry405. The mechanism handling access to the control transfer table309accesses the entry405and then follows the branch always operation to entry407and invokes module G. The updated code403references both entries F and G. When the updated code403is executed, the entry F is accessed via entry405, without indirection. In addition, when the updated code403references module G, it directly accesses the entry407.

As already stated, structuring techniques are not limited to simple ordering by hotness. Structuring may also be applied to a chosen set of table entries, based on a certain criteria. For example, a tool may identify and work on just those entries that are accessed beyond a certain threshold number of accesses. The control transfer table entries may also be organized in accordance with other information, such as temporal locality, spatial locality, etc. Furthermore, coloring can be applied to prevent entries from conflicting in memory. Coloring may also be utilized to prevent control transfer table entries from conflicting with program code and/or program data.

FIG. 5depicts an exemplary computer system according to realizations of the invention. A computer system500includes a processor unit501(possibly including multiple processors, a single threaded processor, a multi-threaded processor, a multi-core processor, etc.). The computer system500also includes a system memory507A-507F (e.g., one or more of cache, SRAM DRAM, RDRAM, EDO RAM, DDR RAM, EEPROM, etc.), a system bus503(e.g., LDT, PCI, ISA, etc.), a network interface505(e.g., an ATM interface, an Ethernet interface, a Frame Relay interface, etc.), and a storage device(s)509A-509D (e.g., optical storage, magnetic storage, etc.). Realizations of the invention may include fewer or additional components not illustrated inFIG. 5(e.g., video cards, audio cards, additional network interfaces, peripheral devices, etc.). The processor unit501, the storage device(s)509A-509D, the network interface705, and the system memory507A-507F are coupled to the system bus503. The system memory507A-507F embodies a tool that condenses entries of a control transfer table by access frequency, although part or all of the tool may be embodied within the processing unit501, the storage device(s)509A-509D, etc. For example, the tool may be part of an operating system to dynamically restructure a control transfer table at runtime to adjust to changing workload

While the invention has been described with reference to various realizations, it will be understood that these realizations are illustrative and that the scope of the invention is not limited to them. Many variations, modifications, additions, and improvements are possible. For example, order may be a variable in construction of a control transfer table, a table may be constructed without order and then rewritten in accordance with ordering of the entries, a new table and a compatibility table (the old control transfer table) may be maintained, etc. In another example, entries accessed more than a threshold number of times may be organized to occur at the beginning of a control transfer table without rearranging other entries, the hottest entries beyond a given threshold may be ordered while other entries are not ordered, etc. More generally, realizations in accordance with the present invention have been described in the context of particular realizations. Functionality may be separated or combined in blocks differently in various realizations of the invention or described with different terminology. These and other variations, modifications, additions, and improvements may fall within the scope of the invention as defined in the claims that follow.