Branch Exception Mechanism
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Disclosed is a branch exception mechanism for software performance analysis and enhancement. The branch exception mechanism is a tool for a compiler, software testing, profiler, trace generation and statistical branch prediction.
Branch Exception Mechanism
a branch exception mechanism for software
performance analysis and enhancement. The branch exception mechanism
is a tool for a compiler, software testing, profiler, trace
generation and statistical branch prediction.
System/6000 machines lack hardware support for
performance analysis, making it difficult to analyze bottlenecks and
weaknesses in the architecture that could be improved upon in the
later releases. The branch exception mechanism is proposed to aid
system analysis and enhancement.
program consists of a sequence of BASIC BLOCKS of
codes. A basic block is a sequence of sequential code execution with
the following properties:
1) If one instruction in the basic block is executed,
all instructions in that block are executed.
2) The last instruction in the basic block is a
instructions in a basic block are executed, the
instruction execution sequence can be determined from the basic block
execution sequence. Other program behaviors such as code hot spots,
code coverage, opcode mixes, branch behavior, etc., can be precisely
determined from a basic block execution sequence.
exception mechanism provides a means to gather basic
block execution statistics. The basic idea is as follows:
A branch exception (trap signal) is generated whenever a branch
is executed. This exception invokes the branch exception service
routine after the branch is resolved. The service routine collects
statistics on the basic block such as execution frequency, branch
frequency, etc. Since all instructions in a basic code block are
executed, accuracy down to instruction granularity is achieved.
No branch exception should occur during the
transfer of program
control to the branch exception service routine, during the execution
of the service routine and upon the return of program control from
the service routine.
1) A hardware unit to generate branch exception.
2) Branch exception must be maskable.
3) Branch exception disable/enable is privileged.
exception mechanism can be used in a number of ways,
such as with a compiler, software testing, profiler, trace generation
and statistical branch prediction.
Compiler: Most compilers today do
optimization by representing
the program as a directed graph. Optimization begins with
partitioning the graph into strongly connected subgraphs
corresponding to loops. Reduction/transformation starts from the
innermost subgraph and working outward. There are two problems with
this approach. First, the constraints of optimization are TIME and
SPACE. More time and memory space are required...