Browse Prior Art Database

Branch Replacement Algorithm for Trace Directed Program Restructuring

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

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

This disclosure presents an algorithm for generating branch instruction sequences for basic blocks moved during the process of Trace Directed Program Restructuring (TDPR). The TDPR process groups highly executed instructions of a program together so as to minimize the working set (i.e., real memory) requirements as well as improving performance by increasing available cache space for a given executable program. In moving these instruction sequences or basic blocks the original control transfer target and fall through addresses must be adjusted to account for basic blocks that have already been moved or that are about to be moved so as to preserve original program functionality.

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

Branch Replacement Algorithm for Trace Directed Program Restructuring

      This disclosure presents an algorithm for generating branch
instruction sequences for basic blocks moved during the process of
Trace Directed Program Restructuring (TDPR).  The TDPR process groups
highly executed instructions of a program together so as to minimize
the working set (i.e., real memory) requirements as well as improving
performance by increasing available cache space for a given
executable program.  In moving these instruction sequences or basic
blocks the original control transfer target and fall through
addresses must be adjusted to account for basic blocks that have
already been moved or that are about to be moved so as to preserve
original program functionality.  Also, due to the reduced maximum
branch distance for conditional branches, conditional branches cannot
be arbitrarily repositioned and may require the inclusion of an
unconditional (far) branch.

      The algorithm described here has been implemented for and used
on AIX* 3.2 executable files and demonstrates both working set size
reductions as well as performance improvements due to increased cache
availability.  The algorithm requires a list of basic block addresses
that are to be moved and the original executable file as input.  This
address list is generated, in a separate process, by tracing the
execution of the program and following the most highly traversed
instruction paths.  Instructions in the original text section of the
executable program are moved to the end of the original text section
(referred to here as the new text area).

      The main loop for the algorithm is shown below.  The Branch
Replacement Algorithm is shown in Algorithms 1 and 1a.  The three
types of general instruction sequences supported by the algorithms
are shown in Table 1 below.  The instruction sequences in the basic
block are represented as 'IA' & 'IB'.  The branch target address is
indicated with a 'T' and the branch fall through or branch and link
return address (i.e., the address immediately after the branch) is
indicated with a 'FT'.  The first instruction at the fall through
address is indicated as 'IC'.

        Conditional   Branch               Unconditional

        Branch        and link Branch      Branch

   ________________________________________________________

        IA              IA                   IA

        IB              IB                   IB

        BC  T        BL  T               B   T

FT:     IC        FT:   IC

                  Table 1  Branch Types

Main loop:

   while ( there are more addresses in the address list )
      get the current address and the next address to be moved
      move all the instructions in the basic block at the current
      addres...