Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Executable Program Restructuring for Optimal Cache/Real Memory Utilization

IP.com Disclosure Number: IPCOM000106676D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 83K

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

Disclosed is a technique for reorganizing the instructions in an existing executable program file which allows for unanticipated or previously unencountered control transfers due to dynamically calculated branches. Basic blocks or instruction sequences can be completely reorganized, in particular for the purpose of optimizing the utilization of both real and cache memory, without concern for unknown control transfers to instructions which have been moved.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Executable Program Restructuring for Optimal Cache/Real Memory Utilization

      Disclosed is a technique for reorganizing the instructions in
an existing executable program file which allows for unanticipated or
previously unencountered control transfers due to dynamically
calculated branches.  Basic blocks or instruction sequences can be
completely reorganized, in particular for the purpose of optimizing
the utilization of both real and cache memory, without concern for
unknown control transfers to instructions which have been moved.

      The idea of organizing the instructions in a program in such a
way as to minimize the use of real and cache memory is not a new one;
several papers exist detailing the advantages of positioning highly
used instructions or groups of instructions together in a program to
reduce the runtime memory requirements as well as improving program
performance by eliminating unexecuted instructions from a cache line
and freeing cache space.  The technique described here provides an
implementation of program restructuring which can be used on an
existing executable program that guarantees the preservation of
program functionality despite unknown control transfers.

The technique is described as follows:

1.  The original executable program is traced while the program is
    used in its typical manner; this provides a list of instruction
    addresses for the most highly executed instructions (i.e., those
    that should be placed together as close as possible).

2.  Using the list of addresses produced in step (1), the
    instructions at those addresses are moved to an area at the end
    of the instruction text section in the original executable,
    referred to here as the new text area, while making any necessary
    adjustments to the instructions so as to preserve the original
    control transfer target and fall through paths.

3.  Each instruction in the original text area that is moved to the
    new text area in step (2) is replaced with an unconditional
    branch to the location in the next text area where it was moved.

4.  When all instructions in the...