Browse Prior Art Database

Handling Branch and Link Instructions during Trace Directed Program Restructuring

IP.com Disclosure Number: IPCOM000112158D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 87K

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

The technique of Trace Directed Program Restructuring (TDPR) is a well known method for reorganizing the instructions in a program, based on an address trace of the actual execution of that program, so as to improve the utilization of the instruction cache (which typically results in improved performance) as well as the utilization of real memory (which typically results in a reduction in real memory requirements). The address trace is used to build a Directed Flow Graph (DFG) which indicates which basic blocks are the most active and where control is transferred and how often from these basic blocks. From this DFG, a sequential address reorder list can be built that is used to restructure the executable program.

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

Handling Branch and Link Instructions during Trace Directed Program
Restructuring

      The technique of Trace Directed Program Restructuring (TDPR) is
a well known method for reorganizing the instructions in a program,
based on an address trace of the actual execution of that program, so
as to improve the utilization of the instruction cache (which
typically results in improved performance) as well as the utilization
of real memory (which typically results in a reduction in real memory
requirements).  The address trace is used to build a Directed Flow
Graph (DFG) which indicates which basic blocks are the most active
and where control is transferred and how often from these basic
blocks.  From this DFG, a sequential address reorder list can be
built that is used to restructure the executable program.  This
reorder list can be generated in a variety of ways, depending upon
how the DFG is traversed, but is typically generated by following the
"hot paths" through the DFG.  However, for some programs, the
automatic reordering or inlining of these "hot paths" through the
code, especially procedure calls and returns, can reduce the amount
of speedup provided by TDPR.

      This disclosure presents an optimization to the address reorder
list generation process used for TDPR.  The idea is simple; detect
procedure calls (branch & links in the RS/6000*) and delay reordering
or inlining the hot paths through the procedure until the current hot
path (with the branch & link to the procedure) has been reordered
(the term "inlining" as used here may be somewhat misleading in that
true procedure inlining, ie, removing the calls and returns, is not
implemented).  This technique eliminates the extra branch
instruction, which is required after the branch & link instruction to
branch around the inlined procedure code, as well as maintains good
program locality by placing the procedure close to the code that
calls it.

As a simple example, consider the following DFG from a short program
loop which contains a procedure call:

             ____________________________________________

            |                                            |

            v                                            |

    ----> [100] ----> [2000] ----> [2010] ----> [110] -->|

           BB1:         BB2:         BB3:        BB4:

           I1           I4            I7         I10

           I2           I5            I8         I11

           I3           I6            I9         I12

           Call  2000   BC  2010      Return     BC  100

In this example, program execution flows from the instructions in
basic blo...