Browse Prior Art Database

Generating an Address List Used for Trace-Directed Program Restructuring

IP.com Disclosure Number: IPCOM000110788D
Original Publication Date: 1994-Jan-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 57K

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

This disclosure presents an algorithm for generating a sequence of addresses for the most highly executed instructions from an instruction address trace for a particular program. This address list is generated for the purpose of directing the restructuring of basic blocks in a program so as to optimize the use of real and cache memory during execution for that program. The instruction address trace is captured in a separate process and typically formatted as a sequence of addresses representing the exact flow of instructions, or of basic blocks, seen as the program was executed. In order to use this address trace for program restructuring, the most highly executed address paths need to be created from this address trace and converted to a sequential list of instruction addresses.

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

Generating an Address List Used for Trace-Directed Program Restructuring

      This disclosure presents an algorithm for generating a sequence
of addresses for the most highly executed instructions from an
instruction address trace for a particular program.  This address
list is generated for the purpose of directing the restructuring of
basic blocks in a program so as to optimize the use of real and cache
memory during execution for that program.  The instruction address
trace is captured in a separate process and typically formatted as a
sequence of addresses representing the exact flow of instructions, or
of basic blocks, seen as the program was executed.  In order to use
this address trace for program restructuring, the most highly
executed address paths need to be created from this address trace and
converted to a sequential list of instruction addresses.  This list
would then represent a desired ordering of the basic blocks in the
program to optimize runtime real and cache memory usage by that
program.

      The algorithm consists of two phases: the first phase reads the
instruction address trace and builds a directed flow graph where the
nodes of the graph represent the instruction addresses traced and the
edges leaving a node indicate the instruction addresses that are
executed next and how often.  The second phase of the algorithm
traverses this directed graph recursively through the most highly
executed paths and generates a sequential list of those addresses.

Phase 1:

        while ( there are more addresses in the address trace )

            get the current address and the next address

            if ( this address has been seen previously )

             ...