Reducing branch costs via branch alignment.
Several researchers have proposed algorithms for basic block reordering. We call these branch alignment algorithms. The primary emphasis of these algorithms has been on improving instruction cache locality, and the few studies concerned with branch prediction reported small or minimal improvements. As wide-issue architectures become increasingly popular the importance of reducing branch costs will increase, and branch alignment is one mechanism which can effectively reduce these costs.In this paper, we propose an improved branch alignment algorithm that takes into consideration the architectural cost model and the branch prediction architecture when performing the basic block reordering. We show that branch alignment algorithms can improve a broad range  of static and dynamic branch prediction architectures. We also show that a program performance can be improved by approximately 5% even when using recently proposed, highly accurate branch prediction architectures. The programs are compiled by any existing compiler and then transformed via binary transformations. When implementing these algorithms on a Alpha AXP 21604 up to a 16% reduction in total execution time is achieved.
Introduction
Conventional processor architectures, particularly modern super-scalar
designs, are extremely sensitive to control flow changes.
Changes in control flow, be they conditional or unconditional
branches, direct or indirect function calls or returns, are not detected
until those instructions are decoded. To keep the pipeline
fully utilized, processors typically fetch the address following the
To appear in the 6th International Conference on Architectural Support for Programming
Languages and Operating Systems (ASPLOS-VI), San Jose, California.
October 1994.
most recent address. If the decoded instruction breaks the control
flow, the previously fetched instruction can not be used, and a
new instruction must be fetched, introducing a "pipeline bubble" or
unused pipeline step. This is called an instruction misfetch penalty.
The final destination for conditional branches, indirect function
calls and returns are typically not available until a latter stage of
the pipeline. At this point the branch has been completely eval-
uated. The processor may elect to fetch and decode instructions
on the assumption that the eventual branch target can be accurately
predicted. If the processor mispredicts the branch destination, the
instructions fetched from the incorrect instruction stream must be
discarded, leading to several "pipeline bubbles" and causing a mispredict
penalty. In practice, pipeline bubbles due to mispredicted
breaks in control flow degrade a programs performance more than
the misfetch penalty. For example, the combined branch mispredict
penalty for the Digital Alpha AXP 21064 processor is ten
instructions. By comparison, the AXP 21064 would lose only two
instructions from instruction misfetches.
Almost all modern architectures use some form of branch pre-
diction, and reducing the number of misfetch and misprediction
penalties will be increasingly important for wide-issue architec-
tures. In this paper, we examine algorithms that reorder the structure
of a program to improve the accuracy of the branch fetch
and prediction architectures. Our code transformations reduce the
number of mispredicted branches and the number of misfetched
instructions. Essentially, the method is this: we restructure the
control flow graph so that fall-through branches occur more fre-
quently. We use profile information to direct the transformation,
and an architectural cost model to decide if the transformation is
warranted. Transformations include rearranging the placement of
basic blocks, changing the sense of conditional operations, moving
unconditional branches out of the frequently executed path, and
occasionally inserting unconditional branches.
We show that static and dynamic branch prediction mechanisms
we examine benefit from such transformations, with the static
branch architectures benefiting more than the dynamic. We implemented
the branch alignment binary transformation algorithms on
a DEC Alpha AXP 21064, and measured total execution time improvements
of up to 16%.
There has been considerable work on profile-driven program opti-
mization. In this section weconsider relevant work onoptimizations
for instruction caches and branch mechanisms.
Optimization for Memory Hierarchies: Due to the expense of
memory on early computers, much early work focused on reducing
paging in virtual memory systems. Several researchers explored
ways to group related subroutines or basic blocks onto the same
virtual memory pages [1, 8, 11, 13, 10]. Other researchers extended
this work to lower levels of the memory hierarchy, optimizing
the performance of instruction caches. McFarling [15] described
an algorithm to reduce instruction cache conflicts for a particular
class of programs. Hwu and Chang [18] describe a more general
and more effective technique using compile time analysis in the
IMPACT-I compiler system. Using profile-based transformations,
the IMPACT-I compiler inlines subroutinesand performs trace anal-
ysis. For each subroutine, instructions are packed using the most
frequently executed traces, moving infrequently executed traces to
the end of the function. Following this, global analysis arranges
functions to reduce inter-function cache conflicts. Similar transformations
were applied by Pettis and Hansen [21] for programs on
the HP PA-RISC.
Optimizations for Control Flow: McFarling and Hennessy [17]
described a number of methods to reduce branch misprediction and
instruction fetch penalties, including profile-driven static branch
prediction, delay slots and aform of branch alignment. Their variant
of branch alignment only considered if/then/else constructs.
Later, Bray and Flynn [4] extended the work of McFarling et al
while examining various branch target buffer (BTB) architectures.
Yet, they also only examined if/then/else constructs.
Yeh et al [26] commented that with trace scheduling, taken
branches could only be reduced from - 62% of the executed conditional
branches to - 50% of executed conditional branches. The
earlier study by Hwu and Chang [18] showed a - 58% fall-through
rate after branch alignment. The papers by McFarling and Hen-
nessy, Bray and Flynn, and Pettis and Hansen did not report the
change in the percentage of taken branches.
The branch alignment reordering algorithm proposed by Hwu
et al is more general than McFarling's and Bray's. Hwu and Chang
examined all basic blocks, rearranging them to achieve a better
branch alignment. They were able to handle branches that do
not form an if/then/else structure. The work by Pettis and
Hansen [21] describes a greedy algorithm for branch alignment
which is similar to Hwu and Chang's since they look at all basic
blocks. The Pettis and Hansen greedy algorithm is more general
than the Hwu and Chang algorithm, and performs better in terms of
reducing the cost of branches.
In this paper we describe an algorithm which is an extension
of the Pettis and Hansen algorithm, and we compare our results to
their greedy algorithm. We also improve upon the analysis and the
effectiveness of branch alignment over that of McFarling, Bray and
Flynn, Hwu and Chang, and Pettis and Hansen. We describe how
to efficiently apply branch alignment to various static and dynamic
prediction architectures and we measure the effectiveness of branch
alignment on these architectures.
Our technique is similar to the methods of McFarling, Bray and
Flynn, Hwu and Chang, and Pettis and Hansen. However, we do
not inline functions, perform global analysis or duplicate code. We
perform the analysis using an object code post-processor rather than
a compiler. This simplifies the analysis and avoids recompiling the
full program for these simple transformations. This also allows
us to apply branch alignment to the full program, including portions
normally not compiled by the user, such as program libraries,
and to process many programs generated by a number of different
compilers. With such a post-processor tool, branch alignment
would normally be only one of several optimizations applied to the
program.
3 Branch Prediction Architectures
Most branch architectures that donot include aBTB incur a misfetch
penalty while a branch is decoded. Some architectures use branch
delay slots or other mechanisms [5, 7, 17] to avoid this penalty. In
this paper we assume the fall-through instruction is fetched while a
branch is decoded (except for the branch target buffer architecture).
Thus, 'taken' branches always incur a misfetch penalty. We modeled
three static branch prediction architectures and two dynamic
prediction architectures.
Static Branch Prediction Architectures: The "FALLTHROUGH"
model assumes the fall-through execution path is always executed.
The "BT/FNT" (backward-taken, forward not taken) assumesback-
ward branches are always taken while forward branches are not
taken. This branch model is fairly common, and variants of it are
implemented on the HP PA-RISC and the Alpha AXP-21064. The
"LIKELY" model assumes that encoded information in the branch
instruction indicates whether the branch is likely to be taken or not
taken. This branch model is used by several architectures including
the Tera [2]. The "likely/unlikely" flag can be set either using
compile-time estimates [3] or profile information [9]. We use profile
information since it is much more accurate and simple to gather
with appropriate tools [23].
Program transformation can help these branch prediction architectures
reduce misfetch and misprediction delays. In the FALL-THROUGH
architecture, the fall-through path should be executed
most frequently, both to reduce misfetch and improve prediction.
In the BT/FNT architecture, it's useful to have the fall-through be
the most common path, but if that's not possible or cost-effective,
the branch target should be placed before the conditional branch
so a backwards branch is predicted. Since the branch mispredict
penalty is larger than the misfetch penalty, it may be better to correctly
predict the backwardsbranch even if this results in a misfetch.
In the LIKELY model, the compiler can specify the likely branch out-
come, therefore the code transformations can only eliminate mis-
fetch penalties when making the fall-through the most frequently
executed path. We should expect that there are more opportunities
for optimization with the FALLTHROUGH method than the BT/FNT
model because all taken branches will be mispredicted in the FALL-THROUGH
method. Likewise, we would expect more optimization
opportunities for the BT/FNT model than the LIKELY model since
we can only improve the misfetch rate when transforming programs
using the LIKELY model.

Figure

1 shows how code transformations can help each static
(a) Original Code (b) Transformed Code

Figure

1: Benefits of code transformation for elim lowering
in ESPRESSO. The darkened edges are fall-through and the dotted
edges are taken. Nodes represent basic blocks.
prediction model. Figure 1 shows a portion of the control flow
graph from the routine elim lowering in the ESPRESSO bench-
mark. Nodes are labeled with numbers and the number in parenthesis
indicates the number of instructions in that basic block. Edges
are labeled by frequency of execution. The edge labeled "16" is executed
for 16% of all edge transitions in that subroutine. Unlabeled
edges are executed less than 1% of the time. Fall-through edges are
darkened while "taken" edges are dotted.
In the original code in Figure 1(a) the LIKELY architecture can
correctly predict the most likely targets having misfetch penalties on
edges In comparison, the FALL-THROUGH
architecture will mispredict edges
and since these are all taken branches. The BT/FNT
architecture will also mispredict edges
will correctly predict edge since the target is before the
branch instruction resulting in a backwards branch.
The transformed code in Figure 1(b) is an efficient layout in
terms of branch costs for each of the static prediction architectures.
Since node 25 is now the fall-through of node 31 all of the architectures
can correctly predict edge penalty,
and since 31 is laid out before 25 the BT/FNT can accurately predict
edge only a misfetch penalty. Also, since node
29 is laid out before 27 the branch can be accurately
predicted. The transformed program gives an optimal layout for
the BT/FNT since it will have the same prediction as the LIKELY(20)(4)(14)(4)(11)(4)6

Figure

2: Routine input hidden from ALVINN
architecture. This is also a good layout for the FALLTHROUGH ar-
chitecture. Though it still suffers by mispredicting edges
and but it can predict the less likely executed edge
Notice that in the transformed code that there are two
taken edges coming out of node 28. Since one of the edges has
to be the fall-through, we need to add a unconditional branch to
the fall-through which will in turn jump to the correct destination
node. The transformed code in Figure 1(b) gives an efficient transformation
for each of the static architectures, but in general, a single
branch alignment transformation will not always give an optimal
alignment for the different architectures.
Code transformations to reduce branch penalties should consider
the underlying branch model when performing the branch
alignment. Later, we examine transformation algorithms that model
the underlying branch architecture and show that they can perform
better than algorithms that do not.
There are many optimizations such as un-rolling loops that we
did not investigate. For example when we traced the ALVINN pro-
gram, which is a neural net simulator, we found that 46% of the
time was spent in routine input hidden and another 46% was
spent in hidden input. Figure 2 shows the control flow graph
for input hidden. Nearly 100% of the branches in that sub-
routine, or - 46% of all branches in ALVINN, arise from a single
branch from basic block 4. If we unrolled that loop, duplicating
the 11-instruction basic block 4, we could reduce the misfetch
penalty for all architectures and improve the branch prediction for
the FALLTHROUGH architecture. Normally, loop unrolling is a more
complex transformation that also attempts to reduce the total number
of executed branches within the unrolled code. We feel that
simply duplicating the basic block 4 and then inverting (aligning)
the branch condition for the added conditional branches in this example
would offer some performance improvement, even if the
other optimizations offered by loop unrolling were ignored.
Dynamic Branch Prediction Methods: While static prediction
mechanisms, particularly profile-based methods, accurately predict
70-90% of the conditional branches, many current computer architectures
use dynamicprediction,such as branch target buffers (BTB)
and pattern history tables (PHT) to accurately predict 90-95% of
the branches.
Originally, BTB's were used as a mechanism for branch pre-
diction, effectively predicting the prior behavior of a branch - even
small BTB's were found to be very effective [4, 17, 20, 22, 26]. The
Intel Pentium is an example of a current architecture using BTB's -
it has a 256-entry BTB organized as a 64 line four-way associative
cache. Only branches that are 'taken' are entered into the BTB.
If a branch address appears in the BTB, the stored address is used
to fetch future instructions. Otherwise, the fall-through address is
used. For each BTB entry, the Pentium also uses a two-bit saturating
counter to predict the direction of a conditional branch [14].
Conditional branches can be predicted using much simpler
mechanisms, but these methods do nothing for misfetch penal-
ties. A pattern history table PHT eliminates the site and target
addresses from the table and the table only predicts the direction
for conditional branches. These designs use the branch site address
as an index into a table of prediction bits. More recently Pan
et al [19] and Yeh and Patt [27] investigated branch-correlation
or two-level branch prediction mechanisms. Although there are a
number of variants, these mechanisms generally combine the history
of several recent branches to predict the outcome of a branch.
The simplest example is the degeneratemethod of Pan et al. When
using a 4096 entry table, the processor maintains a 12-bit shift
register (the global history register) that records the outcome of
previous branches. If the previous 12 branches that executed were
a sequence of three taken branches, six non-taken branches and
three more taken branches (TTTNNNNNNTTT), the register might
store the value 111000000111 2 , or 3591. This value is used as an
index into the 4096-entry pattern history table, providing contextual
information about particular patterns of branches.
We simulated two PHTs, a direct mapped PHT and the degenerate
two-level correlation PHT using a variant that McFarling [16]
found to be the most accurate. This method performs an exclusive-or
of the branch address with the global history register and uses this
as an index into the PHT. Both of the PHTs we simulated contained
saturating up-down counters, for a total of 1KBytes of
storage. We also simulated two BTB configurations. We modeled
a 64-entry 2-way associative BTB and a 256-entry 4-way BTB -
the latter configuration is used in the Intel Pentium. The BTBs we
simulated store only taken branches in the BTB and predict fall-through
on a BTB miss. Each BTB entry contains a 2-bit saturating
up-down counter used to predict the destination for conditional
branches. The BTB in our simulations hold entries for conditional
branches, unconditional branches, indirect jumps, procedure calls
and returns [5, 26].
4 Branch Alignment Algorithms
We implemented the branch alignment algorithm suggested by Pettis
and Hansen [21]. We did not implement the algorithms of
McFarling and Hennessy or Bray and Flynn, because they only
examine 'if/then/else' constructs. This limits their effective-
Unconditional branch 2 (instruction
Correctly predicted fall-through 1 (instruction)
Correctly predicted taken 2 (instruction
Mispredicted

Table

1: Cost, in cycles, for different branches.
ness since many of our transformations are applied to loops. For
example, those algorithms would not perform the transformations
shown in Figure 1. In our results, we perform branch alignment
for each procedure in a program. We are mainly concerned with
reducing branch cost, although instruction cache performance may
also be improved. We represent a procedure by a directed control
flow graph containing a set of basic blocks represented by nodes
and edges between nodes. We trace the program execution, recording
the number of times each edge is traversed. We call this the
execution weight for edge e of node n.
When transforming a program we look at all nodes that have an
out degree of one or two. An unconditional branch is a basic block
with a single out-going edge, the 'taken' edge. A conditional basic
block has two edges, the 'taken' and the `fall-through' edges, and
a fall through basic block has an out-going 'fall-through' edge. All
other edges are given a weight of zero and are not considered when
applying branch alignment. Thus, we ignore indirect branches,
procedure returns and subroutine calls. In this section we discuss
three branch alignment algorithms.
Greedy: Pettis and Hansen [21] proposed two heuristics to align
branches. We only describe their bottom-up ('greedy') algorithm,
since it has better performance. The Greedy algorithm was directed
towards the BT/FNT architecture, and did not consider the implications
of different branch architectures. In the terminology of [21],
a chain is a contiguous sequence of basic blocks threaded by 'head'
and 'tail' pointers. The first basic block in each chain has a null
head pointer and the last basic block in each chain has a null tail
pointer.
The algorithm aligns each procedure in turn. The edge
where S is the source and D the destination, with the largest weight
is selected. The algorithm then attempts to position node D as
the "fall-through" of node S. If S does not already have a fall-through
basic block, and D does not already have a head, then
these two basic blocks are combined into a chain. Otherwise, these
blocks cannot be linked. If these basic blocks are part of existing
chains, the two chains are merged when the basic blocks are linked.
This is repeated until all edges have been examined and chains
can no longer be merged. Pettis and Hansen implemented their
technique for the HP PA-RISC architecture. This architecture uses
the BT/FNT conditional branch prediction model. After all the
edges in a procedure have been examined, a precedence relation is
defined between chains to determine an ordering between chains
that would achieve the best prediction using the BT/FNT model.
The chains are positioned using this precedence relation, inserting
unconditional branches when needed.
Cost: The Greedy algorithm does not consider the underlining
architecture when constructing chains. We include these underlining
architecture costs in our algorithms in order to reduce the cost
of branches beyond that of the Greedy algorithm. Our architecture
assumesspecific costs for different branches, shown in Table 1. The
"Cost" transformation algorithm tries to minimize the cost of the
branches for a procedure using simple heuristics, hoping that each
local minimization will result in a global performance improvement.
As in the Greedy algorithm, the Cost algorithm starts with the
edge with the highest weight. When we pick an edge S ! D, we
determine if having D be the fall-through for S will locally benefit
the program using our cost model before trying to link S and D. We
examine all the predecessors of D to see if it is more cost effective
to connect D to another node. Our algorithm considers basic blocks
with one and two exit edges. We consider two possible alignments
for single-exit nodes. We examine the cost of aligning the edge as
a fall through (thereby avoiding an unconditional branch) or adding
an unconditional branch. For example, if S were a single-exit node,
we could either include S and D in the same chain, or insert a jump
to D at the end of S, allowing S and D to be in different chains.
For conditional branches we examine three possible alignments.
Assume S has another edge, S ! D 2 . We consider including the
or the S ! D 2 edge in the current chain or adding a jump
to the end of S making the jump the fall-through of S. This latter
transformation may be useful if it is more cost effective to have
both D and D 2 as fall-throughs in other chains.
In certain cases, not aligning either edge of a conditional branch
canimprove performanceon the FALLTHROUGHandBT/FNT archi-
tectures. For example, consider a loop consisting of a single basic
block, such as that shown in Figure 2. Using the FALLTHROUGH
model, the original loop in node 4 incurs a five cycle penalty (one
cycle for the branch instruction and four cycles for the misprediction
penalty) using our cost-model. It is cost-effective to invert the
sense of the conditional ending the block and follow the block with
an inserted jump instruction. This combination takes only three cycles
(the correctly predicted conditional branch, the unconditional
branch and a single misfetch penalty). Any loop can be structured
this way - we illustrated the point using the single block loop because
the Greedy algorithm would not restructure such loops and
they occur frequently.
Try15: Our simulation study showed that the 'Cost' heuristic
gave sizable improvements for the FALLTHROUGH architecture,
modest improvements for BT/FNT and negligible improvements
for LIKELY. We briefly considered using the cost model to assess
the cost of every possible basic block alignment using an exhaustive
search and selecting the minimal cost ordering. In practice, this
sounds expensive, but in the common case procedures contain 5-15
basic blocks. However, most programs have procedures containing
hundreds of blocks, making exhaustive search impossible for those
procedures. For example, the GCC program contains a procedure
(yyparse) containing 712 basic blocks. However, many edges
were never executed in those large procedures, and a few basic
blocks contribute most of the execution time.
We devised a heuristic that balanced time against performance.
For each procedure,we select the 15 most frequently executededges
and attempt all possible alignments for these nodes. We then select
A
CDA9000(a) Original Code (b) Aligned

Figure

3: Example illustrating where Try15 reduces branch costs.
The darkened edges are fall-through and the dotted edges are taken.
Nodes represent basic blocks.
the next 15 edges, and so on. This allows us to try all possible
combinations for each group of 15 nodes. The possibilities to try
for each node is similar to that described for the Cost algorithm.
For single-exit nodes (unconditional and fall through basic blocks)
the two possibilities are to make the outgoing edge either a fall
through or taken edge, and for nodes with two-exit edges (condi-
tional branches) we try aligning separately each of the two outgoing
edgesas the fall-through and then try having neither of the out-going
edges as the fall-through. We call this the 'Try15' method. This
heuristic took more time than the Greedy and Cost heuristics, but
produced better results and still ran in a few minutes. Considering
10 nodes at a time gave slightly worse results than Try15 for a few
programs, but it took less than a minute to run and still resulted in
better performance than the Greedy algorithm.
To improve the performance of our algorithm we only examined
edges that were executedmore than once. This eliminated over half
of the edges from consideration in each program. If more profiles
are used or combined for a program, one could reduce the execution
time of the Try15 algorithm by examining only those conditional
branches that account for 99% of the executed branches.
For branch alignment algorithms, aligning loops is difficult, and
this is one case where our heuristics perform better than the Greedy
algorithm. Figure 3(a) shows a fragment of code with a loop. The
Greedy algorithm would not modify this code assuming it chooses
to align edge A. Whereas, the
Try15 algorithm transforms the code as shown in Figure 3(b). Note
that in the transformed code the unconditional branch from C ! A
is removed. Using our cost model in Table 1 for the LIKELY and
BT/FNT architecture, the execution cost for the original code with
the edge-weightsshown is 9000+8999+8999   2+1
cycles, while the cost for our transformed version is 8999+ 9000
cycles. This reduces the branch execution cost
by 33%.
Ideally, we want the most likely path through the loop to be in
a single chain. The Greedy and Cost algorithms do not examine
enough of the loop to minimize this cost. This is one of the main
reasons why the Try15 heuristic is able to produce better results
than the other algorithms. The Try15 heuristic can can try all the
combinations to find the correct place to "break" a loop.
5 Experimental Methodology
We constructed two tools to study branch alignment. Initially, we
simulated several different branch architectures using trace driven
simulation. Later, we implemented the different branch alignment
algorithms using the OM [24, 25] system for link-time code trans-
formation. The simulations provide more detailed insight on why
branch alignment is useful on the different branch architectures.
The implementation illustrates that these techniques have practical
value.
During the simulation study, we instrumented the programs
from the SPEC92 benchmark suite and other programs, including
object-oriented programs written in C++. We used ATOM [23] to
instrument the programs. Due to the structure of ATOM, we did not
need to record traces and could trace very long-running programs.
The programs were compiled on a DEC 3000-400 using the Alpha
processor using either the DEC C compiler or DEC
C++ compiler. The systems were running the standard OSF/1 V1.3
operating systems. All programs were compiled with standard
optimization (-O). We constructed several simulators to analyze
the program. Each simulator was run once to collect information
about branches targets and a second time to use profile information
from the prior run. For the SPEC92 programs, we used the largest
input distributed with the SPEC92 suite.

Table

2 shows the basic statistics for the programs we instru-
mented. The first columns lists the number of instructions traced
and the second column gives the percentage of instructions which
cause a break in control flow. The columns labeled 'Q-50', `Q-90',
'Q-99' and `Q-100' show the number of branch instruction sites
that contribute to 50, 90, 99 and 100% of all executed conditional
branches in the program. While the next column 'Static' shows the
total number of conditional branch sites in each program. Thus,
in doduc, three branch instructions constitute 50% of all executed
branches. The '%Taken' column shows the percentage of conditional
branches that are 'taken' during execution. The last five
columns provide details about the five types of breaks in control
flow encountered during tracing: conditional branches (CBr), indirect
jumps (IJ), unconditional branches (Br), procedure calls (Call)
and procedure returns (Ret). Note, that dynamic dispatch calls are
implemented as indirect jumps in C++ and are therefore included
in the indirect jump metric.
The 'other' programs include: cfront, version 3.0.1 of the
AT&T C++ language preprocessor written in C++, groff, a version
of the ditroff text formatter written in C++, idl, a C++
parser for the CORBA interface description language, db++, a version
of the 'deltablue' constraint solution system written in C++ and
formating system. We selected these programs because
we found that the SPEC92 suite did not typify the behavior seen in
large programs or C++ programs [6]. For these alternate programs,
we used sizable inputs we hoped would exercise a large part of
the program - for example, the T E X program formated a 45-page
document.
6 Results
For all of our results we only rearrange basic blocks within a proce-
dure, and we do not perform procedure splitting nor any procedure
rearranging. Since each branch alignment method adds and removes
instructions in the program there is no clear cut performance
metric to compare the performance for these different alignments.
Simple metrics such as prediction accuracy are not useful, because
one method may have removed or added unconditional branches to
achieve a particular branch alignment.
We define the branch execution penalty (BEP) to be the execution
penalty associated with misfetched and mispredicted branches.
For our simulations we assumed a misfetched branch causes a one
cycle misfetch penalty and a mispredicted branch causes a four
cycle mispredict penalty. For the static branch and PHT architec-
tures, unconditional branches, correctly predicted taken conditional
branches and direct procedure calls all cause misfetch penalties.
Whereas, mispredicted conditional branches, mispredicted returns,
and all indirect jumps cause mispredict penalties. Since the BTB architecture
tries to predict all types of branches, taken branches (pro-
cedure calls, unconditional jumps, and taken conditional branches)
found in the BTB do not necessarily cause misfetch penalties. In
all of our static and dynamic architecture simulations we simulated
a 32-entry return stack [12], which is very accurate at predicting the
destination for return instructions.
In order to evaluate the performance of the different alignments
and architectures, we add the BEP to the number of instructions
executed in the aligned program and divide by the number of instructions
executed in the original program. This essentially defines
the cycles per instruction relative to the original program. This also
assumes that each instruction takes one cycle. For example, if
the original program issues 1,000 instructions and encounters 347
cycles from branch penalties, it would have a CPI of 1:347. If a
modified program issues 978 instructions, assuming some branches
were avoided, and incurred 347 cycles from branch penalties, it
would have a relative CPI of (978 + 347)=1000, or 1:325 cycles.
We call this relative CPI since we are dividing the cost of the aligned
program by number of instructions in the original program.

Table

3 shows the relative CPI for each program using the various
alignments on the three static branch architectures. The table
also shows the percent of executed conditional branches which are
fall-through after the alignment has been performed for the varying
architectures. The percent of fall-through branches does not
change for the Pettis algorithm on the varying branch architec-
tures, whereas the fall-through percentage for the Try15 algorithm
changes for each architecture since the cost model algorithm is different
for each architecture. Table 4 shows the relative CPI for the
PHT and BTB architectures. Arithmetic averages are shown for
each group of programs (SPECfp92, SPECint92, and 'Other'). The
'Orig' column for each architecture shows the performance when
we instrumented and traced the original program. For the LIKELY
architecture, we used the profiles that are used to create the branch
alignments in order to predict the likely branch direction for a given
branch site. For each architecture, we use the same input to 'align'
the program and to measure the improvement from that alignment.
The branch alignment heuristics that use the architectural cost
model usually perform better than the simpler Greedy algorithm -
# Insn's Conditional Branches Percentage of Breaks during Tracing
Program Traced % Breaks Q-50 Q-90 Q-99 Q-100 Static %Taken %CBr %IJ %Br %Call %Ret
doduc 1,149,864,756 8.53 3 175 296 1,447 7,073 48.68 81.31 0.01 4.97 6.86 6.86
hydro2d 5,682,546,752 6.28 14 74
spice
su2cor 4,776,762,363 4.36 8 26
compress 92,629,658 13.91 4 12
espresso 513,008,174 17.11 44 163 470 1,737 4,568 61.90 93.25 0.20 1.88 2.29 2.39
gcc 143,737,915 15.97 245 1,612 3,724 7,640 16,294 59.42 78.85 2.86 5.75 6.04 6.49
li 1,355,059,387 17.67
sc 1,450,134,411 20.93 14 94 336 1,471 4,478 66.88 85.96 0.98 2.62 5.18 5.26
cfront 19,001,390 16.08 112 946 3,055 5,783 15,509 53.18 73.45 2.17 6.40 8.72 9.26
groff 41,522,284 16.10 86 372 1,021 2,511 7,434 54.17 66.12 4.80 7.80 8.77 12.51

Table

2: Measured attributes of the traced programs.
this is particularly notable in the FALLTHROUGH architecture. The
FALLTHROUGH architecture is no longer a realistic architecture to
consider, but is used in combination with BTBs - the fall-through
can be predicted on a BTB miss. The improved performance occurs
because the Try15 heuristic does not align either of the out-going
edges for some conditional branches. Instead, unconditional
branches are added to one of the conditional branch edges to take
advantage of the FALLTHROUGH prediction cost model. In fact,
the Try15 heuristic converts up to 99%, as seen in Table 3, of all
conditional branches in some programs to be fall-through in the
FALLTHROUGH model. Adding an unconditional jump works especially
well for single basic block loops which end with a conditional
branch, as described earlier for ALVINN and many of the FORTRAN
programs.
The BT/FNT architecture sees reasonable improvement from
branch alignment. In the BT/FNT architecture, it is difficult to
create chains for the BT/FNT architecture. When forming chains,
it is not known where the taken branch will be located in the final
procedure until the chains are formed and laid out. The destination
of a taken branch could be placed before or after the current node,
affecting the final branch prediction costs.
The small benefit for the LIKELY architecture occurs because
we eliminate the misfetch penalty for many branches and we can
remove unconditional branches from the likely execution path.
Eliminating instruction misfetches will be increasingly important
as super-scalar architectures become more common - a four-issue
super-scalar architecture could encounter a branch every two or
three cycles. It should benefit such architectures to have frequent
"fall-through" branches. However, the relative CPI metric shown
only reflects the improvement of a single issue architecture.
The cost model used for the static architectures is different than
that for the dynamic architectures. When examining the costs of
aligning a conditional branch for the static architecture, the costs for
aligning the conditional branch are clear cut, meaning only one of
the targets of the conditional branch can be predicted and the other
must always be mispredicted. In the dynamic architectures this is
not the case. In order to compensate for the increased accuracy
for predicted conditional branches, our cost model for the PHT
architectures assume that conditional branches are mispredicted
only 10% of the time. Similarly in the BTB architectures we also
assume that conditional branches are mispredicted only 10% of the
time and in addition, we assume that the BTB architectures have a
10% miss rate. This means that taken unconditional and conditional
branches will only cause a misfetch penalty 10% of the time.
As seen in Table 4, branch alignment offers some improvement
for the PHT architectures and little improvement to the BTB architectures
except for small BTBs. As with the LIKELY architecture,
the major improvement in performance for the PHT architecture
comes from moving unconditional branches from the frequently
executed path and reducing the misfetch penalty that occurs for
taken conditional branches. The original program performance for
the BTB architecture is already efficient because it stores and predicts
indirect jumps, procedure calls, unconditional and conditional
branches. The small BTB architecture can benefit more from branch
alignment than the larger BTB since only taken branches are stored
in the BTB. Therefore removing unconditional branches and making
more branches fall-through will cause the aligned program to
use less entries in the BTB.
An important observation is that branch alignment reduces the
difference in performancebetween the various branch architectures.
For example, the aligned FALLTHROUGHandBT/FNT architectures
have almost identical performance. Both are slightly slower than the
LIKELY and PHT architectures, while the BTB architecture has the
Relative Cycles Per Instruction % of Fall-Through Conditional Branches
FALLTHROUGH BT/FNT LIKELY FALLTHROUGH BT/FNT LIKELY
Program Orig Greedy Try15 Orig Greedy Try15 Orig Greedy Try15 Orig Greedy Try15 Try15 Try15
alvinn 1.35 1.34 1.17 1.09 1.09 1.09 1.09 1.09 1.09 2.23 3.76 99.57 3.71 3.75
doduc 1.15 1.09 1.05 1.09 1.04 1.04 1.05 1.04 1.03 51.32 68.90 95.08 68.77 92.24
hydro2d 1.18 1.10 1.06 1.10 1.10 1.04 1.06 1.04 1.04 26.66 57.68 95.44 53.43 53.45
ora 1.13 1.02 1.02 1.12 1.02 1.05 1.05 1.02 1.02 46.76 94.67 94.96 90.36 90.50
spice 1.34 1.29 1.25 1.15 1.14 1.13 1.12 1.11 1.11 28.37 38.37 92.31 37.42 37.74
su2cor 1.11 1.07 1.05 1.05 1.04 1.04 1.04 1.04 1.03 26.93 52.27 89.82 38.12 38.12
tomcatv 1.13 1.08 1.04 1.08 1.02 1.02 1.03 1.02 1.02 0.72 43.71 99.38 43.71 43.71
compress 1.35 1.14 1.12 1.26 1.17 1.10 1.16 1.12 1.10 31.75 81.73 84.14 68.72 68.72
li 1.27 1.12 1.11 1.26 1.14 1.13 1.15 1.10 1.10 52.70 83.03 85.63 83.03 83.11
sc 1.51 1.27 1.18 1.36 1.17 1.16 1.20 1.14 1.14 33.12 66.37 90.91 65.66 65.72
cfront 1.25 1.12 1.10 1.23 1.10 1.10 1.13 1.09 1.09 46.82 81.05 89.64 80.52 81.20
groff 1.31 1.11 1.10 1.26 1.17 1.09 1.14 1.09 1.08 45.86 84.20 94.06 82.16 84.53
idl 1.31 1.14 1.13 1.30 1.13 1.13 1.19 1.13 1.13 53.30 90.37 96.11 89.96 90.00
tex 1.20 1.10 1.08 1.17 1.09 1.09 1.10 1.07 1.07 42.53 73.23 87.43 70.67 71.43
Other Avg 1.28 1.14 1.12 1.25 1.13 1.12 1.15 1.11 1.11 46.33 80.56 91.49 79.36 80.30

Table

3: Relative cycles per instruction for static prediction architectures and the corresponding % of fall-through branches
Direct Mapped PHT 4096 Correlation PHT 64-Entry, 2-way BTB 256-Entry, 4-way BTB
Program Orig Greedy Try15 Orig Greedy Try15 Orig Greedy Try15 Orig Greedy Try15
alvinn 1.09 1.09 1.09 1.09 1.09 1.09 1.01 1.00 1.00 1.00 1.00 1.00
doduc 1.06 1.04 1.04 1.06 1.03 1.04 1.03 1.02 1.02 1.02 1.01 1.01
hydro2d 1.05 1.04 1.04 1.05 1.04 1.04 1.01 1.02 1.01 1.01 1.02 1.01
spice 1.12 1.11 1.12 1.11 1.10 1.11 1.04 1.04 1.07 1.04 1.04 1.07
su2cor 1.05 1.04 1.04 1.05 1.04 1.04 1.02 1.02 1.01 1.02 1.02 1.01
compress 1.15 1.12 1.10 1.15 1.11 1.09 1.08 1.08 1.06 1.06 1.08 1.06
espresso 1.17 1.15 1.15 1.14 1.12 1.12 1.11 1.10 1.10 1.07 1.09 1.09
gcc 1.17 1.12 1.12 1.17 1.11 1.11 1.18 1.10 1.10 1.12 1.08 1.08
li 1.15 1.11 1.10 1.12 1.08 1.07 1.13 1.07 1.07 1.07 1.06 1.05
sc 1.17 1.11 1.11 1.16 1.10 1.10 1.08 1.04 1.04 1.04 1.03 1.03
cfront 1.14 1.09 1.09 1.14 1.09 1.09 1.19 1.09 1.09 1.13 1.07 1.07
groff 1.14 1.09 1.08 1.13 1.08 1.07 1.13 1.07 1.05 1.06 1.05 1.03
idl 1.19 1.13 1.12 1.18 1.12 1.12 1.11 1.02 1.02 1.03 1.01 1.01
tex 1.10 1.07 1.07 1.09 1.06 1.06 1.08 1.05 1.04 1.05 1.04 1.04
Other Avg 1.15 1.11 1.11 1.14 1.10 1.10 1.12 1.05 1.05 1.06 1.04 1.04

Table

4: Relative cycles per instruction for dynamic prediction architectures.
ALVINN EAR COMPRESS EQNTOTT ESPRESSO GCC LI SC0.60.81.0Relative
Execution
Time
Original
Pettis & Hansen

Figure

4: Total execution time improvement on DEC 3000-600
Alpha AXP for the SPEC92 C programs.
best overall performance. In comparing the static BT/FNT architecture
performance to the 4096-entry correlated PHT, before alignment
the PHT architecture performs 7% better than the BT/FNT
architecture, but after alignment it performs only 2% better than
the BT/FNT architecture when taking the averaged CPI over all the
simulated programs.
Lastly, we note there is a significant difference between the different
program classes. The SPECint92 and 'Other' programs see
more benefit from branch alignment than the SPECfp92 programs.
A reason for this, as seen in Table 2, is that for the SPECfp92 programs
- 6:5% of the instructions executed cause a break in control
flow. Whereas in the the SPECint92 and 'Other' programs - 16%
of the instructions cause a break in control.
6.1 Performance Comparison
We implemented both the Greedy and Try15 alignment algo-
rithms. Figure 4 indicates the improvement in the total execution
time for the SPEC92C programs on a DEC 3000-600 with an Alpha
AXP 21064 processor running OSF/2 V2.0. For each program, we
show the execution time for the original program, as compiled by
the native compiler, the transformed program using the Pettis and
Hanson (Greedy) algorithm, and the transformed program using the
Try15 algorithm. We scaled the execution time for each program
by the time for the original program.
The programs were compiled as previously described but not
linked. We then used OM to link the resulting object files and
standard libraries using OM-full as described in [25]. Therefore,
the Original program execution times shown in Figure 4 use the
standard OM link time optimizations. We then modified OM to
produce the desired branch alignments and used this to link the
programs.
The Alpha AXP 21064 is a dual issue architecture which uses a
combination of dynamic and static branch prediction. Each instruction
in the on-chip cache has a single bit indicating the previous
branch direction for that instruction. When a cache line is flushed,
all the bits are initialized with the bit from each instruction where
the sign displacement should be located. Thus the performance
expected by this architecture is a cross between a direct mapped
PHT table and a BT/FNT architecture.
Not surprisingly the floating point programs, ALVINN and EAR,
do not see any benefit from the branch alignment which agrees with
our simulation results. We believe some benefit could be gained if
the single loop basic blocks (shown in Figure 2) were duplicated.
The GCC, EQNTOTT and SC programs benefit the most from branch
alignment. It is difficult to understand from where the actual performance
improvement from branch alignment comes. Our tools did
not allow us to instrument and measure the transformed programs,
and our trace simulations did not completely model the Alpha AXP
architecture.
For the simulations described in the previous section, two different
chain layout algorithms where used for the Greedy and Try15
alignments. One algorithm laid out chains for a procedure starting
with the highest executed chain continuing down to the lowest executed
chain. The other algorithm laid out chains using the BT/FNT
model described in [21]. We implemented both chain layouts in
OM and found that the algorithms that laid the chains out from
highest executed to lowest executed performed slightly better than
the one that laid out chains using the BT/FNT model. We believe
this performance comes from the fact that laying out the chains
from highest to lowest executed satisfies many of the branch priorities
for the BT/FNT model, and at the same time allowing better
cache locality. Therefore the results shown in Figure 4 uses the
same Greedy alignment used for all of the simulations (except the
BT/FNT simulation) with the highest to lowest chain ordering.
In OM we also implemented the BT/FNT, PHT and BTB alignments
for Try15 that were used in the simulations. We found that the
alignment performed the same or slightly better than the PHT
alignment which was better than the BT/FNT alignment. Recall
that when creating a PHT alignment, all taken conditional branches
and unconditional branches have a one cycle misfetch penalty associated
with it in the cost model. In contrast our BTB cost model
assumes a 10% BTB miss rate, which means it assumes the one
cycle misfetch penalty only occurs for 10% of the taken branches.
In the Alpha AXP 21604 architecture misfetch penalties can be
squashed if the pipeline is currently waiting on other stalls. There-
fore, the cost model which would more actually fit the Alpha AXP
21604 architecture would assume that taken branches are squashed
rufely 30% of the time. The results in Figure 4 uses the same
alignment as used for the BTB simulations shown in Table 4.
Conclusions
We simulated a number of branch prediction architectures and
showed that branch alignment is useful for each architecture. These
simulation results assumed a single issue architecture. As wide
issue architectures become more popular, branch alignment algorithms
will have a larger impact on the performance of programs.
When these alignment algorithms were implemented, we saw up
to 16% improvement in execution time for the dual issue Alpha
AXP 21604 architecture. The total reduction in program execution
time results from a combination of reduction in the misfetch and
misprediction penalties, the instruction cache miss rates, and the
number of instructions issued.
We described an improvedalignment algorithm and also showed
that a few branchesdetermine the branch behavior of manycommon
benchmark programs. Our technique addresses a broader class of
program structures than [15] and [4] anddoes not require the recompilation
needed by Hwu and Chang[18] or Pettis and Hansen [21].
We haveshownhow a simple object code transformation, taking
no more than a few minutes to run, even for very large programs, can
improve a programs performance. Branch alignment does not benefit
all programs, but for integer programs a reasonable improvement
is seen for the various branch prediction architectures.

Acknowledgments

We'd like to thank Alan Eustace and Amitabh Srivastava for developing
ATOM, and especially Amitabh Srivastava for developing
OM. We'd also like to thank Keith Farkas, Dennis Lee, and the
anonymous reviewers for their useful comments. This work was
funded in part by NSF grant No. ASC-9217394, an ARPA Fellowship
and a DEC-WRL summer internship. This work is part
of a continued effort to make languages such as C++ suitable for
scientific computing.



--R

On the performance enhancement of paging systems through program analysis and trans- formation
The tera computer system.
Branch prediction for free.
Strategies for branch target buffers.
In 21st Annual Annual International Symposium on Computer Architecture
Quantifying behavioral differences between C and C
Branch folding in the CRISP microprocessor: Reducing branch delay to zero.
Improving locality by critical working sets.
Predicting conditional branch directions from previous runs of a program.

Program restructuring for virtual memory.
Branch history table prediction of moving target branches due to subroutine returns.
Optimal sequential partitions of graphs.
Branch prediction strategies and branch target buffer design.
Program optimization for instruction caches.
Combining branch predictors.
Reducing the cost of branches.
Hwu and Pohua P.
Improvingthe accuracyof dynamic
Branch target buffer design and optimization.
Profile guided code positioning.
A. study of
A system for building customized program analysis tools.
A practical system for intermodule code optimizations at link-time

A comprehensive instruction fetch mechanism for a processor supporting speculative execution.
A comparisonof dynamic branchpredic- tors that use two levels of branch history
--TR
Reducing the cost of branches
Branch folding in the CRISP microprocessor: reducing branch delay to zero
Compile-Time Program Restructuring in Multiprogrammed Virtual Memory Systems
Program optimization for instruction caches
Achieving high instruction cache performance with an optimizing compiler
Profile guided code positioning
Branch history table prediction of moving target branches due to subroutine returns
Strategies for branch target buffers
Improving the accuracy of dynamic branch prediction using branch correlation
Predicting conditional branch directions from previous runs of a program
A comprehensive instruction fetch mechanism for a processor supporting speculative execution
Branch prediction for free
A comparison of dynamic branch predictors that use two levels of branch history
Link-time optimization of address calculation on a 64-bit architecture
ATOM
Fast and accurate instruction fetch and branch prediction
The Tera computer system
Optimal Sequential Partitions of Graphs
Improving locality by critical working sets
Branch Target Buffer Design and Optimization
A study of branch prediction strategies

--CTR
Chunling Hu , John McCabe , Daniel A. Jimnez , Ulrich Kremer, The Camino Compiler infrastructure, ACM SIGARCH Computer Architecture News, v.33 n.5, December 2005
Steven Wallace , Nader Bagherzadeh, Modeled and Measured Instruction Fetching Performance for Superscalar Microprocessors, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.570-578, June 1998
Nicolas Gloy , Michael D. Smith , Cliff Young, Performance issues in correlated branch prediction schemes, Proceedings of the 28th annual international symposium on Microarchitecture, p.3-14, November 29-December 01, 1995, Ann Arbor, Michigan, United States
I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, ACM SIGPLAN Notices, v.31 n.9, p.128-137, Sept. 1996
Young , David S. Johnson , Michael D. Smith , David R. Karger, Near-optimal intraprocedural branch alignment, ACM SIGPLAN Notices, v.32 n.5, p.183-193, May 1997
Robert Cohn , P. Geoffrey Lowney, Hot cold optimization of large Windows/NT applications, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.80-89, December 02-04, 1996, Paris, France
Brad Calder , Dirk Grunwald , Joel Emer, A system level perspective on branch architecture performance, Proceedings of the 28th annual international symposium on Microarchitecture, p.199-206, November 29-December 01, 1995, Ann Arbor, Michigan, United States
Gadi Haber , Moshe Klausner , Vadim Eisenberg , Bilha Mendelson , Maxim Gurevich, Optimization opportunities created by global data reordering, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
M. Anton Ertl , David Gregg, Optimizing indirect branch prediction accuracy in virtual machine interpreters, ACM SIGPLAN Notices, v.38 n.5, May
Brad Calder , Dirk Grunwald , Amitabh Srivastava, The predictability of branches in libraries, Proceedings of the 28th annual international symposium on Microarchitecture, p.24-34, November 29-December 01, 1995, Ann Arbor, Michigan, United States
Alex Ramirez , Oliverio J. Santana , Josep L. Larriba-Pey , Mateo Valero, Fetching instruction streams, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
Minghui Yang , Gang-Ryung Uh , David B. Whalley, Improving performance by branch reordering, ACM SIGPLAN Notices, v.33 n.5, p.130-141, May 1998
Alex Ramirez , Josep L. Larriba-Pey , Mateo Valero, Software Trace Cache, IEEE Transactions on Computers, v.54 n.1, p.22-35, January 2005
Daniel A. Jimnez, Code placement for improving dynamic branch prediction accuracy, ACM SIGPLAN Notices, v.40 n.6, June 2005
Minghui Yang , Gang-Ryung Uh , David B. Whalley, Efficient and effective branch reordering using profile data, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.667-697, November 2002
Amir H. Hashemi , David R. Kaeli , Brad Calder, Efficient procedure mapping using cache line coloring, ACM SIGPLAN Notices, v.32 n.5, p.171-182, May 1997
Bernard Goossens , David Defour, The instruction register file micro-architecture, Future Generation Computer Systems, v.21 n.5, p.767-773, May 2005
Paramjit S. Oberoi , Gurindar S. Sohi, Parallelism in the front-end, ACM SIGARCH Computer Architecture News, v.31 n.2, May
Nikolas Gloy , Michael D. Smith, Procedure placement using temporal-ordering information, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.977-1027, Sept. 1999
Glenn Reinman , Brad Calder , Todd Austin, Optimizations Enabled by a Decoupled Front-End Architecture, IEEE Transactions on Computers, v.50 n.4, p.338-355, April 2001
Matthew Arnold , David Grove, Collecting and Exploiting High-Accuracy Call Graph Profiles in Virtual Machines, Proceedings of the international symposium on Code generation and optimization, p.51-62, March 20-23, 2005
Wankang Zhao , David Whalley , Christopher Healy , Frank Mueller, Improving WCET by applying a WC code-positioning optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.4, p.335-365, December 2005
Ann Gordon-Ross , Frank Vahid , Nikil Dutt, A first look at the interplay of code reordering and configurable caches, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
Brad Calder , Dirk Grunwald , Donald Lindsay , James Martin , Michael Mozer , Benjamin Zorn, Corpus-based static branch prediction, ACM SIGPLAN Notices, v.30 n.6, p.79-92, June 1995
Glenn Reinman , Todd Austin , Brad Calder, A scalable front-end architecture for fast instruction delivery, ACM SIGARCH Computer Architecture News, v.27 n.2, p.234-245, May 1999
Mikko H. Lipasti , William J. Schmidt , Steven R. Kunkel , Robert R. Roediger, SPAID: software prefetching in pointer- and call-intensive environments, Proceedings of the 28th annual international symposium on Microarchitecture, p.231-236, November 29-December 01, 1995, Ann Arbor, Michigan, United States
Brad Calder , Dirk Grunwald , Michael Jones , Donald Lindsay , James Martin , Michael Mozer , Benjamin Zorn, Evidence-based static branch prediction using machine learning, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.188-222, Jan. 1997
Sangwook P. Kim , Gary S. Tyson, Analyzing the working set characteristics of branch execution, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.49-58, November 1998, Dallas, Texas, United States
Young , Michael D. Smith, Static correlated branch prediction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.1028-1075, Sept. 1999
Pierre Michaud , Andr Seznec , Stphan Jourdan, An Exploration of Instruction Fetch Requirement in Out-of-Order Superscalar Processors, International Journal of Parallel Programming, v.29 n.1, p.35-58, February 2001
profile-based optimization;trace scheduling;branch target buffers;branch prediction