Browse Prior Art Database

Handling Dynamically Calculated Branches for Trace Directed Program

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

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

Disclosed is a technique for reducing or eliminating the negative effects of dynamically calculated branches (i.e., computed goto's) in an executable program which is to be reorganized by performing Trace Directed Program Restructuring (TDPR). The TDPR process reorganizes the basic blocks in a program so as to minimize the run-time real memory requirements and to improve performance by increasing available cache spacefor that program.

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

Handling Dynamically Calculated Branches for Trace Directed Program

      Disclosed is a technique for reducing or eliminating the
negative effects of dynamically calculated branches (i.e., computed
goto's) in an executable program which is to be reorganized by
performing Trace Directed Program Restructuring (TDPR).  The TDPR
process reorganizes the basic blocks in a program so as to minimize
the run-time real memory requirements and to improve performance by
increasing available cache spacefor that program.

      The basic blocks in a program are repositioned according to a
list of addresses, representing the highest executed instruction
paths, derived in a separate process from an instruction address
trace for that program.  In the implementation described here, basic
blocks are moved from the original text section in the executable
file to the end of the original text section, referred to here as the
new text area.  Each instruction in the basic block that is moved is
replaced with a branch to the location in the new text area where
that instruction was moved.  Once an executable has been
restructured, performance and memory usage will be optimal when
program execution is contained in the new text area.  This
containment, however, is aggravated by dynamically calculated
branches which continue to calculate target addresses in the original
text area and force control transfer out of the new text area.  This
results in unwanted double branches that typically reference two real
memory pages, one in the original text area and one in the new text
area, and an unwanted increase in the real memory requirements for
that program.

      The two major sources of dynamically calculated branches in a
typical C program are 1.) calling a function through a pointer and
2.)  the branch table which results from the switch/case statement.
The addresses calculated for these two cases must be adjusted to
point to the new text area in order to eliminate the problems caused
by dynamically calculated branches.

      Given an unstripped original executable program (i.e., one that
still contains the program symbol table, in par...