Efficient Instruction Sequencing with Inline Target Insertion.
Inline target insertion, a specific compiler and pipeline implementation method for delayed branches with squashing, is defined. The method is shown to offer two important features not discovered in previous studies. First, branches inserted into branch slots are correctly executed. Second, the execution returns correctly from interrupts or exceptions with only one program counter. These two features result in better performance and less software/hardware complexity than conventional delayed branching mechanisms.
Introduction
The instruction sequencing mechanism of a processor determines the instructions to be fetched from
the memory system for execution. In the absence of branch instructions, the instruction sequencing
mechanism keeps requesting the next sequential instructions in the linear memory space. In this
This research has been supported by the National Science Foundation (NSF) under Grant MIP-8809478, Dr. Lee
Hoevel at NCR, the Joint Services Engineering Programs (JSEP) under Contract N00014-90-J-1270, the National
Aeronautics and Space Administration (NASA) under Contract NASA NAG 1-613 in cooperation with the Illinois
Computer laboratory for Aerospace Systems and Software (ICLASS), and the Office of Naval Research under Contract
N00014-88-K-0656.
W. W. Hwu is with the Department of Electrical and Computer Engineering, University of Illinois, Urbana-
Champaign, Illinois, 61801.
3 P. P. Chang is with the Intel Corporation, 5200 N.E. Elam Young Parkway, Hillsboro, OR 97124. The work
presented in this paper was conducted while he was with the Department of Electrical and Computer Engineering,
University of Illinois, Urbana-Champaign, Illinois, 61801.
sequential mode, it is easy to maintain a steady supply of instructions for execution. Branch
instructions, however, disrupt the sequential mode of instruction sequencing. Without special
hardware and/or software support, branches can significantly reduce the performance of pipelined
processors by breaking the steady supply of instructions to the pipeline [26].
Many hardware methods for handling branches in pipelined processors have been studied
[39][28][9][29][17][10]. An important class of hardware methods, called Branch Target Buffers (or
Branch Target Caches), use buffering and extra logic to detect branches at an early stage of the
pipeline, predict the branch direction, fetch instructions according to the prediction, and nullify
the instructions fetched due to an incorrect prediction[28]. Branch Target Buffers have been
adopted by many commercial processors [28][16]. The performance of such hardware methods is
determined by their ability to detect the branches early and to predict the branch directions accu-
rately. High branch prediction accuracy, about 85-90% hit ratio, has been reported for hardware
methods[39][28][29]. Another advantage of using Branch Target Buffers is that they do not require
recompilation or binary translation of existing code. However, the hardware methods suffer
from the disadvantage of requiring a large amount of fast hardware to be effective[28][20]. Their
effectiveness is also sensitive to the frequency of context switching [28].
Compiler-assisted methods have also been proposed to handle branches in pipelined processors.

Table

lists three such methods. Delayed Branching has been a popular method to absorb branch
delay in microsequencers of microprogrammed microengines. This technique has also been adopted
by many recent processor architectures including IBM 801[37], Stanford MIPS[14], Berkeley RISC
[33], HP Spectrum [3], SUN SPARC [43], MIPS R2000 [25], Motorola 88000[30], and AMD 29000[1].
In this approach, instruction slots immediately after a branch are reserved as the delay slots for
that branch. The number of delay slots has to be large enough to cover the delay for evaluating the
branch direction. During compile-time, the delay slots following a branch are filled with instructions
that are independent of the branch direction, if the data and control dependencies allow such code
movement[13]. Regardless of the branch direction, these instructions in the delay slots are always
executed. McFarling and Hennessy reported that the first delay slot can be successfully filled by
the compiler for approximately 70% of the branches, and the second delay slot can be filled only
25% of the time[29]. It is clear that delayed branching is not effective for processors requiring more
than one slot.
Another compiler-assisted method, called Delayed Branches with Squashing, has been adopted
by some recent processors to complement delayed branching[29][15][8][30][23]. That is, the method
is used when the compiler cannot completely fill the delay slots for delayed branching. In this
scheme, the number of slots after each branch still has to be large enough to cover the branch
delay. However, instead of moving independent instructions into branch delay slots, the compiler
can fill the slots with the predicted successors of the branch. If the actual branch direction differs
from the prediction, the instructions in the branch slots are scratched (squashed or nullified) from
the pipeline.
On the least expensive side, the hardware predicts all conditional branches to be either always
taken (as in Stanford MIPS-X [8]) or always not-taken (as in Motorola 88000 [30]). Predicting all
the instructions to be taken achieves about 65% accuracy whereas predicting not-taken does about
[11]. Predicting all the branches to be either taken or not taken limits the performance of
delayed branches with squashing. Furthermore, filling the branch slots for predicted-taken branches
requires code copying in general. Predicting all branches to be taken can result in a large amount
of code expansion.
McFarling and Hennessy proposed Profiled Delayed Branches with Squashing. In this scheme,
an execution profiler is used to collect the dynamic execution behavior of programs such as the
preferred direction of each branch[29]. The profile information is then used by a compile-time code
restructurer to predict the branch direction and to fill the branch slots according to the prediction.
In order to allow each branch to be predicted differently, an additional bit to indicate the predicted
direction is required in the branch opcode in general[23]. Through this bit, the compiler can
convey the prediction decision to the hardware. McFarling and Hennessy also suggested methods
for avoiding adding a prediction bit to the branch opcode. Using pipelines with one and two
branch slots, McFarling and Hennessy showed that the method can offer comparable performance
with hardware methods at a much lower hardware cost. They suggested that the stability of using
execution profile information in compile-time code restructuring should be further evaluated.
This paper examines the extension of McFarling and Hennessy's idea to processors employing
deep pipelining and multiple instruction issue. These techniques increase the number of slots for
each branch. As a result, four issues arise. First, there are only 3 to 5 instructions between branches
in the static program (see Section 4.2) . In order to fill a large number of slots (on the order of
ten), one must be able to insert branches into branch slots. Questions arise regarding the correct
execution of branches in branch slots. Second, the state information about all branch instructions
in the instruction pipeline becomes large. Brute force implementations of return from interrupts
and exceptions can involve saving/restoring a large amount of state information of the instruction
sequencing mechanism. Third, the code expansion due to code restructuring can be very large.
It is important to control such code expansion without sacrificing performance. Fourth, the time
penalty for refilling the instruction fetch pipeline due to each incorrectly predicted branch is large.
It is very important to show extensive empirical results on the performance and stability of using
profile information in compile-time code restructuring. The first three issues were not addressed by
McFarling and Hennessy [29]. The second issue was not addressed by previous studies of hardware
support for precise interrupt [18] [40].
In order to address these issues, we have specified a compiler and pipeline implementation
method for Delayed Branches with Squashing. We refer to this method as Inline Target Insertion
to reflect the fact that the compiler restructures the code by inserting predicted successors
of branches into their sequential locations. Based on the specification, we show that the method
exhibits desirable properties such as simple compiler and hardware implementation, clean inter-
rupt/exception return, moderate code expansion, and high instruction sequencing efficiency. We
also provide a proof that Inline Target Insertion is correct. Our correctness proof of filling branch
slots with branch instructions is also applicable to a previously proposed hardware scheme [34].
The paper is organized into five sections. Section 2 presents background and motivation for
Inline Target Insertion. Section 3 defines the compiler and pipeline implementation, proves the
correctness of the proposed implementation, and suggests a clean method to return from interrupt
and exception. Section 4 provides empirical results on code expansion control and instruction
sequencing efficiency. Section 5 offers concluding remarks regarding the cost-effectiveness and
applicability of Inline Target Insertion.
Background and Motivation
2.1 Branch Instructions
Branch instructions reflect the decisions made in the program algorithm. Figure 1(a) shows a C
program segment which finds the largest element of an array. There are two major decisions in the
algorithm. One decides if all the elements have been visited and the other decides if the current
element is larger than all the other ones visited so far.
With the register allocation/assignment assumption in Figure 1(b), a machine language program
can be generated as given in Figure 2. There are three branches in the machine language program.
Instruction D ensures that the looping condition is checked before the first iteration. Instruction I
checks if the loop should iterate any more. Instruction F determines if the current array element
is larger than all the others visited so far.
The simplified view of the machine language program in Figure 2 highlights the effect of
branches. Each arc corresponds to a branch where the head of an arc is the target instruction.
The percentage on each arc indicates the probability for the corresponding branch to occur in
execution. The percentages can be derived by program analysis and/or execution profiling. If
the percentage on an arc is greater than 50%, it corresponds to a likely branch. Otherwise, it
corresponds to an unlikely branch.
The instructions shown in Figure 2(a) are static instructions. These are the instructions generated
by the compilers and machine language programmers. During program execution, each static
instruction can be executed multiple times due to loops. Each time a static instruction is executed,
it generates a dynamic instruction. A dynamic branch instruction which redirects the instruction
fetch is called a taken branch.
2.2 Instruction Sequencing for Pipelined Processors
The problems with instruction sequencing for pipelined processors are due to the latency of decoding
and/or executing branches. A simple hardware example suffices to illustrate the problem
of instruction sequencing for pipelined processors. The processor shown in Figure 3 is divided
into four stages: instruction fetch (IF ), instruction decode (ID), instruction execution (EX), and
result write-back (WB). The instruction sequencing logic is implemented in the EX stage. The
sequencing pipeline consists of the IF , ID, and EX stages of the processor pipeline. When a
compare-and-branch 4 instruction is processed by the EX stage 5 , the instruction sequencing logic
determines the next instruction to fetch from the memory system based on the comparison result.
The dynamic pipeline behavior is illustrated by the timing diagram in Figure 4. The vertical
dimension gives the clock cycles and the horizontal dimension the pipeline stages. For each cycle,
the timing diagram indicates the pipeline stage in which each instruction can be found.
The pipeline fetches instructions sequentially from memory until a branch is encountered. In

Figure

4, the instructions to be executed are
the direction of branch I is not known until cycle 7. By this time instructions J and K have
already entered the pipeline. Therefore, in cycle 8 instruction E enters the pipeline while J and
K are scratched. The nonproductive cycles introduced by incorrectly fetching J and K reduce the
throughput of the pipeline.
2.3 Deep Pipelining and Multiple Instruction Issue
The rate of instruction execution is equal to the clock frequency times the number of instructions
executed per clock cycle. One way to improve the instruction execution rate is to increase the clock
frequency. The pipeline stages with the longest delay (critical paths) limit the clock frequency.
Therefore, subdividing these stages can potentially increase the clock frequency and improve the
overall performance. This adds stages in the pipeline and creates a deeper pipeline. For example,
if the instruction cache access and the instruction execution limit the clock frequency, subdividing
these stages may improve the clock frequency. A timing diagram of the resultant pipeline is shown
in

Figure

5. Now four instructions are scratched if a compare-and-branch redirects the instruction
fetch. For example, I 2
may be scratched if I 1
redirects the instruction fetch.
Another method to improve instruction execution rate is to increase the number of instructions
executed per cycle. This is done by fetching, decoding, and executing multiple instructions per
cycle. This is often referred to as multiple instruction issue [44] [12] [27] [31] [32] [19] [35] [36]
. The timing diagram of such a pipeline is shown in Figure 6. In this example, two
4 Although the compare-and-branch instructions are assumed in the example, the methods in this paper apply to
condition code branches as well.
5 Although unconditional branch instructions can redirect the instruction fetch at the ID stage, we ignore the
optimization in this example for simplicity.
instructions are fetched per cycle. When a compare-and-branch (I 1
reaches the EX stage, five
instructions may be scratched from the pipeline. 6
As far as instruction sequencing is concerned, multiple instruction issue has the same effect
as deep pipeling. They both result in increased number of instructions which may be scratched
when a branch redirects the instruction fetch. 7 Combining deep pipelining and multiple instruction
issue will increase the number of instructions to be scratched to a relatively large number. For
example, the TANDEM Cyclone processor requires 14 branch slots due to deep pipeline and multiple
instruction issue[16]. 8 The discussions in this paper do not distinguish between deep pipelining and
multiple instruction issue; they are based on the number of instructions to be scratched by branches.
3 Inline Target Insertion
Inline Target Insertion consists of a compile-time code restructuring algorithm and a run-time
pipelined instruction fetch algorithm. The compile-time code restructuring algorithm transforms a
sequential program P s to a parallel program P p . Inline Target Insertion is correct if the instruction
sequence generated by executing P p on a pipelined instruction fetch unit is identical to that
generated by executing P s on a sequential instruction fetch unit. In this section, we first formally
define the sequential instruction fetch algorithm. Then, we formally define the code restructuring
algorithm and the pipelined instruction fetch algorithm of Inline Target Insertion. From the formal
models of implementation, we will derive a proof of correctness.
3.1 Sequential Instruction Fetch
In a sequential instruction fetch unit, I s (t) is defined as the dynamic instruction during cycle t.
The address of I s
(t) will be referred to as A s
(t)). The target instruction of a branch instruction
I s (t) will be referred to as target(I s (t)). The next sequential instruction of a branch instruction
6 The number of instructions to be scratched from the pipeline depends on the instruction alignment. If I2 rather
than I1 were a branch, four instructions would be scratched.
7 A difference between multiple instruction issue and deep pipelining is that multiple likely control transfer instructions
could be issued in one cycle. Handling multiple likely control transfer instructions per cycle in a multiple
instruction issue processor is not difficult in Inline Target Insertion. The details are not within the scope of this
paper.
8 The processor currently employs an extension to the instruction cache which approximates the effect of a Branch
Target Buffer to cope with the branch problem.
I s (t) will be referred to as fallthru(I s (t)). The sequential instruction fetch algorithm (SIF ) is
shown below.
Algorithm SIF begin
(t) is a taken branch) then
else
A s
The correct successors of a dynamic instruction I s
(t) is defined as the dynamic instructions to
be executed after I s (t) as specified by SIF . The k th correct successors of I s (t) will be denoted
as CS(I s (t); k). It should be noted that CS(I s (t); k). For a sequential program, P s ,
whose execution starts from instruction I 0
, the instruction sequence is (I 0
n) is the first terminating instruction.
3.2 Compiler Implementation
The compiler implementation of Inline Target Insertion involves compile-time branch prediction
and code restructuring. Branch prediction marks each static branch as either likely or unlikely.
The prediction is based on the estimated probability for the branch to redirect instruction fetch
at the run time. The probability can be derived from program analysis and/or execution profiling.
The prediction is encoded in the branch instructions.
The predicted successors (PS) of an instruction I are the instructions which tend to execute after
I . The definition of predicted successors is complicated by the frequent occurrence of branches.
refer to the k th predicted successor of I . The predicted successors of an instruction
can be defined recursively:
9 In the discussions, all address arithmetics are in terms of instruction words. For example, address / address+1
advances the address to the next instruction.
1. If I is a likely branch, then PS(I ; 1) is target(I). Otherwise PS(I ; 1) is fallthru(I).
2.
1).
For example, one can identify the first five predicted successors of F in Figure 2 as shown
below. Since F is a likely branch, its first predicted successor is its target instruction H . The
second predicted successor of F is I , which is a likely branch itself. Thus the third predicted
successor of F is I's target instruction E.
The code restructing algorithm for Inline Target Insertion is shown below. It is also illustrated
by

Figure

7.
Algorithm ITI(N) begin
1. Open N insertion slots after every likely branch 10 .
2. For each likely branch I , adjust its target label from the address of PS(I ; 1) to
(the address of PS(I
3. For each likely branch I , copy its first N predicted successors (PS(I ; 1),PS(I; 2),
its slots 11 . If some of the inserted instructions are branches, make
sure they branch to the same target after copying. 12
It is possible to extend the proofs to a non-uniform number of slots in the same pipeline. The details are not in
the scope of this paper.
This step can be performed iteratively. In the first iteration, the first predicted successors of all likely branches are
determined and inserted. Each subsequent iteration inserts one more predicted successor for all the likely branches.
It takes N iterations to insert all the target instructions to their assigned slots.
12 This is trivial if the code restructuring works on assembly code. In this case, the branch targets are specified as
labels. The assembler automatically generates the correct branch offset for the inserted branches.
The goal of ITI is to ensure that all original instructions find their predicted successors in the
next sequential locations. This is achieved by inserting the predicted successors of likely branches
into their next sequential locations.
We refer to the slots opened by the ITI Algorithm as insertion slots instead of more traditional
terms such as delay slots or squashing delay slots. The insertion slots are only associated with likely
branches. The instructions in the insertion slots are duplicate copies. All the others are original.
This is different from what the terms delay slots and squashing delay slots usually mean. They often
refer to sequential locations after both likely and unlikely branches, which can contain original as
well as duplicate copies.

Figure

8 illustrates the application of IT to a part of the machine program in Figure
2. Step 1 opens two insertion slots for the likely branches F and I . Step 2 adjusts the branch label
so that F branches to H I branches to 2. Step 3 copies the predicted successors of F
(H and I) and I (E and F ) into the insertion slots of F (H 0 and I 0 ) and I(E 0 and F 0 ). Note that
the offset is adjusted so that I 0 and F 0 branches to the same target instructions as I and F . The
reader is encouraged to apply IT to the code for more insights into the algorithm.
With Inline Target Insertion, each instruction may be duplicated into multiple locations. There-
fore, the same instruction may be fetched from one of the several locations. The original address,
of a dynamic instruction is the address of the original copy of I . The fetch address, A f (I), of
a dynamic instruction I is the address from which I was fetched. In Figure 8, the original address
of both I and I 0 is the address of I . The fetch addresses of I and I 0 are their individual addresses.
It should be noted that IT I moves fallthru(I) of a likely branch I to A which is
an original address.
3.3 Sequencing Pipeline Implementation
The sequencing pipeline is divided into N +1 stages. The sequencing pipeline processes all instructions
in their fetch order. If any instruction is delayed due to a condition in the sequencing pipeline
(e.g. instruction cache miss), all the other instructions in the sequencing pipeline are delayed. This
includes the instructions ahead of the one being delayed. The net effect is that the entire sequencing
pipeline freezes. This ensures that the relative pipeline timing among instructions is accurately exposed
1to the compiler. It guarantees that when a branch redirects instruction fetch, all instructions
in its insertion slots have entered the sequencing pipeline. Note that this restriction only applies to
the instructions in the sequencing pipeline, the instructions in the execution pipelines (e.g., data
memory access and floating point evaluation) can still proceed while the instruction sequencing
pipeline freezes.
The definition of time in instruction sequencing separates the freeze cycles from execution cycles.
Freeze cycles do not affect the relative timing among instructions in the sequencing pipeline. In
this paper, cycle t refers to the t th cycle of program execution excluding the freeze cycles. I(k; t) is
defined as the dynamic instruction at the k th stage of the sequencing pipeline during cycle t. The
implementation keeps an array of fetch addresses for all the instructions in the sequencing pipeline.
The fetch address for the instruction at stage i in cycle t will be referred to as A f
A hardware function REF ILL 13 is provided to reload the instruction fetch pipeline from any
original address. REF ILL is called when there is a program startup, an incorrect branch prediction,
or a return from interrupt/exception. It is easy to guarantee that the program startup address is
an original address. We will show in the next subsection that the appropriate original address for
a program to resume after incorrect branch prediction and interrupt/exception handling is always
available.
REF ILL(pc) begin
A f
The pipelined instruction fetch algorithm (PIF ) that is implemented in hardware is shown
below. The sequencing pipeline fetches instructions sequentially by default. Each branch can
13 REFILL is excluded from the accounting of time when proving correctness of Inline Target Insertion. REFILL
may be physically implemented as loading an initial address into Af (I(1; t)) and subsequently computing Af
. REFILL is included in the accounting of time when evaluating the
performance of Inline Target Insertion (Section 4).
redirect the instruction fetch and/or scratch the subsequent instructions when it reaches the end
of the sequencing pipeline. If a branch redirects the instruction fetch, the next fetch address is the
adjusted target address determined in Algorithm IT I . If the decision of a branch is incorrectly
predicted, it scratches all the subsequent instructions from the sequencing pipeline.
Algorithm P IF (N) begin
is not a branch) then
A f
else if (I(N is likely and is taken) then
A f
else if (I(N is unlikely and is not taken) then
A f
else if (I(N is unlikely but is taken) then
else if (I(N is likely but is not taken) then

Figure

9(a) shows a timing diagram for executing the instruction sequence
I ! E) of the machine program in Figure 8(a). With Inline Target Insertion (Figure 8(e)), the
instruction sequence becomes In this case, the branch decision for F
is predicted correctly at compile time. When F reaches the EX stage in cycle 4, no instruction is
scratched from the pipeline. Since F redirects the instruction fetch, the instruction to be fetched by
the IF stage in cycle 5 is E 0 (the adjusted target of F ) rather than the next sequential instruction
G.
Figure

9(b) shows a similar timing diagram for executing the instruction sequence
G). With Inline Target Insertion, the instruction fetch sequence becomes
In this case, the branch decision for F is predicted incorrectly at the compile time. When F reaches
the EX stage in cycle 4, instructions H 0 and I 0 are scratched from the pipeline. Since F does not
redirect the instruction fetch, the instruction fetch pipeline is refilled from the next sequential
instruction G.
3.4 Correctness of Implementation
Branches are the central issue of Inline Target Insertion. Without branches, the sequencing
pipeline would simply fetch instructions sequentially. The instructions emerging from the sequencing
pipeline would be the correct sequence. Therefore, the correctness proofs of the compiler and
pipeline implementation will focus on the correct execution of branches. For pipelines with many
slots, it is highly probable to have branches inserted into insertion slots (see Section 4.2). In the
case where there are no branches in insertion slots, the correctness follows from the description
of the ITI Algorithm. All branch instructions would be original and they would have their first
predicted successors in the next N sequential locations. Whereas a branch instruction in an
insertion slot cannot have all its N predicted successors in the next N sequential locations. For
example, in Figure 8(e), questions arise regarding the correct execution of F 0 . When F 0 redirects
the instruction fetch, how do we know that the resulting instruction sequence is always equivalent
to the correct sequence F
Insertion is correct if the instruction sequence that is generated by
n) is the first stop instruction.
We shall prove that the instruction sequence that is issued by (P IF , P p
is identical to that
by (SIF , P s
Unfortunately, it is difficult to compare the output of PIF and SIF on a step
by step basis. We will first identify sufficient conditions for (PIF , P p ) to generate the same
instruction sequence as (SIF , P s ), and then show that these conditions are guaranteed by Inline
Target Insertion.
To help the reader to read the following lemmas and theorems, we list important terms in Table
2. We define two equality relations on the state variables of the instruction fetch pipeline.
Theorem 1 states that these two equality relations are sufficient to ensure the correctness of
Inline Target Insertion.
Theorem 1 If R(t) and S(t) are true for all t, then I(N
Proof: The theorem can be proved by induction on t.
Induction basis: From the definition of REF ILL, I(N
Induction step: Assuming P (t) is true, show
Case 1: I(N is not an incorrectly predicted branch.
According to P IF , I(N+1; implies that I(N; 1). For
a correctly predicted instruction I(N is equal to CS(I(N 1).
Hence, I(N
Case 2: I(N is unlikely but is taken.
PIF performs at t. According to the definition of REF ILL,
which is CS(I(N+1; t); 1). Hence, I(N+1;
Case 3: I(N is likely but is not taken.
PIF performs t. According to the definition of REF ILL and
Because I(N +1; t) is a
likely branch, IT I allocates N insertion slots after A
is at A is not taken, CS(I(N
It should be noted that, if I(N is a likely branch, the original copy of fallthru(I(N is always at
according to ITI. Therefore, Ao(I(N argument for REFILL.
Theorem 1 shows that R(t) and S(t) are sufficient to ensure correct execution. Therefore, we
formulate the next theorem as the ultimate correctness proof of Inline Target Insertion.
Theorem 2 IT I and PIF ensure that R(t) and S(t) are true for all t.
Theorem 2 has a standard induction proof. We start by proving that R(0) and S(0) are true.
Then we show that, if R(t) and S(t) are true, R(t+1) and S(t+1) are also true. Because PIF and
IT I are complex algorithms, we need to consider several cases in each step of the proof. Instead
of presenting the proof as a whole, we will first present several lemmas, from which the proof of
Theorem 2 naturally follows.
is performed at time t so that I entry is I(N
are true.
Proof:
IT I ensures that the original instructions find their N predicted successors in their next N
sequential addresses. R(t naturally follows the definition of REFILL.
implied by the definition of REFILL. Because
Therefore,
shows that refilling the instruction fetch pipeline from an original address ensures that
R(t+1) and S(t+1) are true. The instruction sequence pipeline is initialized by
)),
where I 0
is the entry point of a program. It follows from Lemma 1 that R(0) and S(0) are true.
We proceed to prove that, if R(t) and S(t) are true, S(t + 1) is also true. We first prove for
the case when I(N is fetched from its original address, and then prove for the case when
is fetched from one of its duplicate addresses.
Lemma 2 If R(t) and S(t) are true and A f (I(N
is also true.
Proof:
is fetched from its original address, I(N cannot be a likely branch. We
need to consider only the following two cases.
Case 1: I(N is not a branch or is an unlikely branch which is not taken.
PIF performs A f
Adding 1 to both sides of S(t) results in A f
Because IT I allocates insertion slots only for likely branches and I(N is not a likely
branch, the original addresses of I(N must be adjacent to each
other. In other words, A
true.
Case 2: I(N is an unlikely branch but is taken.
PIF performs REF t. Correctness of S(t
from Lemma 1. Note that A is an original (and therefore legal) address
for REFILL.The case where I(N is fetched from an insertion slot is fairly difficult to prove. We
will first prove an intermediate lemma.
Lemma 3 If A f (I(N 1)), then there must be a k that satisfies all
the following four conditions.
likely branch.
(3) There can be no likely branches between I(N inclusively.
(4) There is no incorrectly predicted branch between I(N inclusively.
Proof:
not fetched from its original address, it must be fetched from an insertion
slot. Therefore, there must be at least one likely branch among the N instructions fetched before
1). The one that is fetched closest to I(N (1), (2), and (3).
We can prove (4) by contradiction. Assume that there was an incorrectly predicted branch
between I(N inclusively. Then, a REF ILL was performed after
at an original address. Because there was no likely branch between I(N
inclusively, I(N must be fetched from its original address. This is a contradiction to the
precondition of this Lemma: A f (I(N Therefore, our assumption
that there was an incorrectly predicted branch between I(N
cannot be true.Lemma 4 If A f
and S(t) are true, then
is also true.
Proof:
We will use the k found in Lemma 3.
Case 1:
is a likely branch. In this case, P IF performs A f
implies that I(N; 1). Because PIF performs A f
and A
Case 2:
(1) Because I(N likely branch, PIF performed A f
A
(2) Because likely branch, I(N;
A
(3) Because there was no likely branch between I(N inclusively,
From (1), (2) and (3), A f
(5) Because there was no likely branch between I(N inclusively,
A
From (4) and (5), A f could be included in Case 2 of the proof. We separate the two cases to make the proof more clear.
Lemma 2 and Lemma 4 collectively ensure that, if S(i) and R(i) are true for
is also true. We proceed to show that R(t + 1) is also true.
Lemma 5 If R(t), S(t), and S(t + 1) are true, then R(t + 1) is also true.
Proof:
Case 1: I(N is an incorrectly predicted branch.
For this case, PIF performs a REFILL. Lemma 1 ensures that I(i; t
after a REFILL.
It remains to be shown that the argument to REF ILL is an original address. If I(N +1; t) is
an unlikely branch, the argument to REFILL is A which is an original
address.
is a likely branch, the argument to REF ILL is A f
1. According to
is a
likely branch, ITI ensures that A
Case 2: I(N is not an incorrectly predicted branch.
(1) From Lemma 2 and Lemma 4, A f
(2) According to IT I, an original instruction can find its predicted successors in the next
sequential instructions. Therefore, must be PS(I(N to be placed in
A
(3) Because I(N is not an incorrectly predicted branch, P IF performs "f or
1::N do A f
t))". Therefore, R(t) implies that I(i;
From (2) and (3), R(t + 1) is true.Proof of Theorem 2 By induction on t. It follows from Lemma 1 that R(0) and S(0) are true.
From Lemma 2, Lemma 4, and Lemma 5, if R(t) and S(t) are true, R(t are also
true.
3.5 Interrupt/Exception Return
The problem of interrupt/exception return arises when interrupts and exceptions occur to instructions
in insertion slots. For example, assume that the execution of code in Figure 8(e) involves
an instruction sequence, Branch F is correctly predicted to be
taken. The question is, if H 0 caused a page fault, how much instruction sequencing information
must be saved so that the process can resume properly after the page fault is handled? If one saved
only the address of H 0 , the information about F being taken is lost. Since H 0 is a not a branch,
the hardware would assume that I 0 was to be executed after H 0 . Since I 0 is a likely branch and
is taken, the hardware would incorrectly assume that G and H resided in the insertion slots of I 0 .
The instruction execution sequence would become which is incorrect.
The problem is that resuming execution from H 0 violated the restriction that an empty sequencing
pipeline always starts fetching from an original instruction. The hardware does not have
the information that H 0 was in the first branch slot of F and that F was taken before the page
occurred. Because interrupts and exceptions can occur to instructions in all insertion slots
of a branch and there can be many likely branches in the slots, the problem cannot be solved by
simply remembering the branch decision for one previous branch.
A popular solution to this problem is to save all the previous N fetch addresses plus the fetch
address of the re-entry instruction. During exception return, all the N will be
used to reload their corresponding instructions to restore the instruction sequencing state to before
the exception. The disadvantage of this solution is that it increases the number of states in the
pipeline control logic and can therefore slow down the circuit. The problem becomes more severe
for pipelines with a large number of slots.
In Inline Target Insertion, interrupt/exception return to an instruction I is correctly performed
by available in the form of A f (Theorem 2).
One can record the original addresses when delivering an instruction to the execution units. This
guarantees that the original address of all instructions active in the execution units are available.
Therefore, when an interrupt/exception occurs to an instruction, the processor can save the original
address of that instruction as the return address. Lemma 1 ensures that R(t are
true after REF ILL from an original address.

Figure

shows the effect of an exception on the sequencing pipeline. Figure 10(a) shows the
timing of a correct instruction sequence Figure 8(e) without
exception. Figure 10(b) shows the timing with an exception to H 0 . When H 0 reaches the end of the
sequencing pipeline (EX stage) at t, its A availble in the form of A f (I(1; 2. This
address will be maintained by the hardware until H 0 finishes execution 16 . When an exception is
detected, A
saved as the return address. During exception return, the sequencing pipeline
resumes instruction fetch from H , the original copy of H 0 . Note that the instruction sequence
produced is H which is equivalent to the one without exception.
Note that the original copies must be preserved to guarantee clean implementation of inter-
rupt/exception return. In Figure 8(e), if normal control transfers always enter the section at
there is an opportunity to remove E and F after Inline Target Insertion to reduce code size. How-
ever, this would prevent clean interrupt/exception return if one occurs to E 0 or F 0 . Section 4.2
presents an alternative approach to reducing code expansion.
3.6 Extension to Out-of-order Execution
Inline Target Insertion can be extended to handle instruction sequencing for out-of-order execution
machines [46] [47] [45] [18] [19] [41] . The major instruction sequencing problem for out-of-order execution
machines is the indeterminate timing of deriving branching conditions and target addresses.
It is not feasible in general to design an efficient sequencing pipeline where branches always have
their conditions and target addresses at the end of the sequencing pipeline. To allow efficient
out-of-order execution, the sequencing pipeline must allow the subsequent instructions to proceed
whenever possible.
To make Inline Target Insertion and its correctness proofs applicable to out-of-order execution
machines, the following changes should be made to the pipeline implementation.
1. The sequencing pipeline is designed to be long enough to identify the target addresses for
program-counter-relative branches and for those whose target addresses can be derived without
interlocking.
2. When a branch reaches the end of the sequencing pipeline, the following conditions may occur:
The real original address does not have to be calculated until an exception is detected. One can simply save
Af (I(1; t)) and only calculate Ao(I(N when an exception actually occurs. This avoids requiring an extra
subtractor in the sequencing pipeline.
(a) The branch is a likely one and its target address is not available yet. In this case, the
sequencing pipeline freezes until the interlock is resolved.
(b) The branch is an unlikely one and its target address is not yet available. In this case, the
sequencing pipeline proceeds with the subsequent instructions. Extra hardware must be
added to secure the target address when it becomes available to recover from incorrect
branch prediction. The execution pipeline must also be able to cancel the effects of the
subsequent instructions emerging from the sequencing pipeline for the same reason.
(c) The branch condition is not yet available. In this case, the sequencing pipeline proceeds
with the subsequent instructions. Extra hardware must be added to secure the repair
address to recover from incorrect branch prediction. The execution pipeline must be
able to cancel the effects of the subsequent instructions emerging from the sequencing
pipeline for the same reason.
If a branch is program counter relative, both the predicted and alternative addresses are available
at the end of the sequencing pipeline. The only difference from the original sequencing pipline model
is that the condition might be derived later. Since the hardware secures the alternative address, the
sequencing state can be properly recovered from incorrectly predicted branches. If the branch target
address is derived from run-time data, the target address of a likely branch may be unavailable
at the end of the sequencing pipeline. Freezing the sequencing pipeline in the above specification
ensures that all theorems hold for this case. As for unlikely branches, the target address is the
alternative address. The sequencing pipeline can proceed as long as the alternative address is
secured when it becomes available. Therefore, all the proofs above hold for out-of-order execution
machines.
Experimentation
The code expansion cost and instruction sequencing efficiency of Inline Target Insertion can only be
evaluated empirically. This section reports experimental results based on a set of production quality
software from UNIX 17 and CAD domains. The purpose is to show that Inline Target Insertion is
17 UNIX is a trademark of AT&T.
an effective method for achieving high instruction sequencing efficiency for pipelined processors.
All the experiments are based on the an instruction set architecture which closely resembles MIPS
R2000/3000[25] with modifications to accommodate Inline Target Insertion. The IMPACT-I C
Compiler, an optimizing C compiler developed for deep pipelining and multiple instruction issue
at the University of Illinois, is used to generate code for all the experiments [4][21][6][7].
4.1 The Benchmark

Table

3 presents the benchmarks chosen for this experiment. The C lines column describes the
size of the benchmark programs in number of lines of C code (not counting comments). The runs
column shows the number of inputs used to generate the profile databases and the performance
measurement. The input description column briefly describes the nature of the inputs for the
benchmarks. The inputs are realistic and representative of typical uses of the benchmarks. For
example, the grammars for a C compiler and for a LISP interpreter are two of ten realistic inputs
for bison and yacc. Twenty files of several production quality C programs, ranging from 100 to
3000 lines, are inputs to the cccp program. All the twenty original benchmark inputs form the input
to espresso. The experimental results will be reported based on the mean and sample deviation
of all program and input combinations shown in Table 3. The use of many different real inputs to
each program is intended to verify the stability of Inline Target Insertion using profile information.
The IMPACT-I compiler automatically applies trace selection and placement, and has removed
unnecessary unconditional branches via code restructuring [4][6].
4.2 Code Expansion
The problem of code expansion has to do with the frequent occurrence of branches in programs.
Inserting target instructions for a branch adds N instructions to the static program. In Figure 8,
target insertion for F and I increases the size of the loop from 5 to 9 instructions. In general, if Q is
the probability for static instructions to be likely branches among all the benchmarks),
Inline Target Insertion can potentially increase the code size by N   Q (180% for
One may argue that the originals of the inserted instructions may be deleted to save space if the flow of control
allows. We have shown, however, preserving the originals is crucial to the clean return from exceptions in insertion
slots (see Section 3.5).
Because large code expansion can significantly reduce the efficiency of hierarchical
memory systems, the problem of code expansion must be addressed for pipelines with a large
number of slots.

Table

4 shows the static control transfer characteristics of the benchmarks. The static cond.
(static uncond.) column gives the percentage of conditional (unconditional) branches among all
the static instructions in the programs. The numbers presented in Table 4 confirm that branches
appear frequently in static programs. This shows for the need for being able to insert branches in
the insertion slots (see Section 3.4). The high percentage of branches suggests that code expansion
must be carefully controlled for these benchmarks.
A simple solution is to reduce the number of likely branches in static programs using a threshold
method. A conditional branch that executes fewer number of times than a threshold value is
automatically converted into an unlikely branch. An unconditional branch instruction that executes
a fewer number of times than a threshold value can also be converted into an unlikely branch whose
branch condition is always satisfied. The method reduces the number of likely branches at the
cost of some performance degradation. A similar idea has been implemented in the IBM Second
Generation RISC Architecture[2].
For example, if there are two likely branches A and B in the program. A is executed 100 times
and it redirects the instruction fetch 95 times. B is executed 5 times and it redirects the instruction
fetch 4 times. Marking A and B as likely branches achieves correct branch prediction 99 (95+4)
times out of a total of 105 (100+5). The code size increases by 2   N . Since B is not executed
nearly as frequently as A, one can mark B as an unlikely branch. In this case, the accuracy of
branch prediction is reduced to be 96 (95+1) times out of 105. The code size only increases by
N . Therefore, a large saving in code expansion could be achieved at the cost of a small loss in
performance.
The idea is that all static likely branches cause the same amount of code expansion but their
execution frequency may vary widely. Therefore, by reversing the prediction for the infrequently
executed likely branches reduces code expansion at the cost of slight loss of prediction accuracy.
This is confirmed by results shown in Table 5. The threshold column specifies the minimum
dynamic execution count per run, below which, likely branches are converted to unlikely branches.
The E[Q] column lists the mean percentage of likely branches among all instructions and the SD[Q]
column indicates the sample deviations. The code expansion for a pipeline with N slots is N   E[Q].
For example, for with a threshold value of 100, one can expect a 2.2% increase in the static
code size. Without code expansion control (threshold=0), the static code size increase would be
36.2% for the same sequencing pipeline. For another example, for a 11-stage sequencing pipeline
with a threshold value of 100, one can expect about 11% increase in the static code size.
code expansion control (threshold=0), the static code size increase would be 181% for the
same sequencing pipeline. Note that the results are based on control intensive programs. The code
expansion cost should be much lower for programs with simple control structures such as scientific
applications.
4.3 Instruction Sequencing Efficiency
The problem of instruction sequencing efficiency is concerned with the total number of dynamic
instructions scratched from the pipeline due to all dynamic branches. Since all insertion slots are
inserted with predicted successors, the cost of instruction sequencing is a function of only N and
the branch prediction accuracy. The key issue is whether the accuracy of compile-time branch
prediction is high enough to ensure that the instruction sequencing efficiency remains high for large
values of N .
Evaluating the instruction sequencing efficiency with Inline Target Insertion is straighforward.
One can profile the program to find the frequency for the dynamic instances of each branch to go
in one of the possible directions. Once a branch is predicted to go in one direction, the frequency
for the branch to go in other directions contributes to the frequency of incorrect prediction. Note
that only the correct dynamic instructions reach the end of the sequencing pipeline where branches
are executed. Therefore, the frequency of executing incorrectly predicted branches is not affected
by Inline Target Insertion.
In

Figure

11(a), the execution frequencies of F and I are both 100. E and F redirect the
instruction fetch 80 and 99 times respectively. By marking F and I as likely branches, we predict
them correctly for 179 times out of 200. That is, 21 dynamic branches will be incorrectly predicted.
Since each incorrectly predicted dynamic branch creates N nonproductive cycles in the sequencing
pipeline, we know that the instruction frequencing cost is 21*N . Note that this number is not
changed by Inline Target Insertion. Figure 11(b) shows the code generated by ITI(2). Although
we do not know exactly how many times F and F 0 were executed respectively, we know that their
total execution count is 100. We also know that the total number of incorrect predictions for F
and F 0 is 20. Therefore, the instruction sequencing cost of Figure 11(b) can be derived from the
count of incorrect prediction in Figure 11(a) multiplied by N .
Let P denote the probability that any dynamic instruction is incorrectly predicted. Note
that this probability is calculated for all dynamic instructions, including both branches and non-
branches. The average instruction sequencing cost can be estimated by the following equation:
relative sequencing cost per instruction
If the peak sequencing rate is 1=K cycles per instruction, the actual rate would be (1
cycles per instruction 19 .

Table

4 highlights the dynamic branch behavior of the benchmarks. The dynamic cond. (dy-
namic uncond.) column gives the percentage of conditional (unconditional) branches among all
the dynamic instructions in the measurement. The dynamic percentages of branches confirm that
branch handling is critical to the performance of processors with large number of branch slots. For
example, 20% of the dynamic instructions of bison are branches. The P value for this program
is the branch prediction miss ratio times 20%. Assume that the sequencing pipeline has a peak
sequencing rate of one cycle per instruction and it has three slots 3). The required
prediction accuracy to achieve a sequencing rate of 1.1 cycles per instruction can be calculated as
follows:
The prediction accuracy must be at least 83.3%.

Table

6 provides the mean and sample deviation of P for a spectrum of threshholds averaged
over all benchmarks. Increasing the threshhold effectively converts more branches into unlikely
branches. With 2, the relative sequencing cost per instruction is 1.036 per instruction for
threshhold equals zero (no optimization). For a sequencing pipeline whose peak sequencing rate
is one instruction per cycle, this means a sustained rate of 1.036 cycles per instruction. For a
sequencing pipeline which sequences k instructions per cycle, this translates into 1:036=k (.518
This formula provides a measure of the efficiency of instruction sequencing. It does not take external events such
as instruction misses into account. Since such external events freeze the sequencing pipeline, one can simply add the
extra freeze cycles into the formula to derive the actual instruction fetch rate.
cycles per instruction. When the threshhold is set to 100, the relative sequencing
cost per instruction is 1.04. With 10, the relative sequencing cost per instruction is 1.18
for threshhold equals zero (no optimization). When the threshhold is set to 100, the sequencing
cost per instruction instruction becomes 1.20. Comparing Table 5 and Table 6, it is obvious that
converting infrequently executed branches into unlikely branches reduces the code expansion at
little cost of instruction sequencing efficiency.
5 Conclusion
We have defined Inline Target Insertion, a cost-effective instruction sequencing method extended
from the work of McFarling and Hennessy[29]. The compiler and pipeline implementation offers
two important features. First, branches can be freely inserted into branch slots. The instruction
sequencing efficiency is limited solely by the accuracy of compile-time branch prediction. Second,
the execution can return from an interruption/exception to a program with one single program
counter. There is no need to reload other sequencing pipeline state information. These two features
make Inline Target Insertion a superior alternative (better performance and less software/hardware
complexity) to the conventional delayed branching mechanisms.
Inline Target Insertion has been implemented in the IMPACT-I C Compiler to verify the compiler
implementation complexity. The software implementation is simple and straightforward. The
IMPACT-I C Compiler is used in experiments reported in this paper. A code expansion control
method is also proposed and included in the IMPACT-I C Compiler implementation. The code
expansion and instruction sequencing efficiency of Inline Target Insertion have been measured for
UNIX and CAD programs. The experiments involve the execution of more than a billion in-
structions. The size of programs, variety of programs, and variety of inputs to each program are
significantly larger than those used in the previous experiments.
The overall compile-time branch prediction accuracy is about 92% for the benchmarks in this
study. For a pipeline which requires 10 branch slots and fetches two instructions per cycle, this
translates into an effective instruction fetch rate of 0.6 cycles per instruction(see Section 4.3). In
order to achieve the performance level reported in this paper, the instruction format must give
the compiler complete freedom to predict the direction of each static branch. While this can be
easily achieved in a new instruction set architecture, it could also be incorporated into an existing
architecture as an upward compatible feature.
It is straightforward to compare the performance of Inline Target Insertion and that of Branch
Target Buffers. For the same pipeline, the performance of both are determined by the branch
prediction accuracy. Hwu, Conte and Chang[20] performed a direct comparison between Inline
Target Insertion and Branch Target Buffers based on a similar set of benchmarks. The conclusion
was that, without context switches, Branch Target Buffers achieved an instruction sequencing
efficiency slightly lower than Inline Target Insertion. Context switches could significantly enlarge
the difference[28]. All in all, Branch Target Buffers have the advantages of binary compatibility
with existing architectures and no code expansion. Inline Target Insertion has the advantage of
not requiring extra hardware buffers, better performance, and performance insensitive to context
switching.
The results in this paper do not suggest that Inline Target Insertion is always superior to
Branch Target Buffering. But rather, the contribution is to show that Inline Target Insertion is a
cost-effective alternative to Branch Target Buffer. The performance is not a major concern. Both
achieve very good performance for deep pipelining and multiple instruction issue. The compiler
complexity of Inline Target Insertion is simple enough not to be a major concern either. This has
been proven in the IMPACT-I C Compiler implementation. If the cost of fast hardware buffers and
context switching are not major concerns but binary code compatibility and code size are, then
Branch Target Buffer should be used. Otherwise, Inline Target Insertion should be employed for
its better performance characteristics and lower hardware cost.

Acknowledgements

The authors would like to thank Michael Loui, Guri Sohi, Nancy Warter, Sadun Anik, Thomas
Conte, and all members of the IMPACT research group for their support, comments and sugges-
tions. We also like to thank the anonymous referees for their comments which were extremely
helpful in improving the quality of this paper. This research has been supported by the National
Science Foundation (NSF) under Grant MIP-8809478, Dr. Lee Hoevel at NCR, the Joint Services
Engineering Programs (JSEP) under Contract N00014-90-J-1270, the National Aeronautics and
Space Administration (NASA) under Contract NASA NAG 1-613 in cooperation with the Illinois
Computer laboratory for Aerospace Systems and Software (ICLASS), and the Office of Naval
Research under Contract N00014-88-K-0656.



--R

"Am29000 Streamlined Instruction Processor, Advance Informa- tion,"
"IBM Second-Generation RISC Machine Organization,"
"Beyond RISC: High Precision Architecture"
"Trace Selection for Compiling Large C Application Programs to Microcode"
"Forward Semantic: A Compiler-Assisted Instruction Fetch Method For Heavily Pipelined Processors"
"Control Flow Optimization for Supercomputer Scalar Pro- cessing"
"Aggressive Code Improving Techniques Based on Control Flow Analysis"
"Architecture Tradeoffs in the Design of MIPS-X"
"An Evaluation of Branch Architectures"
"Branch Folding in the CRISP Microprocessor: Reducing Branch Delay to Zero"
"A Characterization of Processor Performance in the VAX-11/780"
"Percolation of Code to Enhance Parallel Dispatching and Execution"
"Optimizing Delayed Branches"
"MIPS: A VLSI Processor Architecture"
"Design Decisions in SPUR"
"Multiple Instruction Issue in the NonStop Cyclone Processor"
"Highly Concurrent Scalar Processing"
"Checkpoint Repair for High Performance Out-of-order Execution Machines"
"Exploiting Concurrency to Achieve High Performance in a Single-chip Microar- chitecture"
"Comparing Software and Hardware Schemes For Reducing the Cost of Branches"
"Inline Function Expansion for Compiling Realistic C Pro- grams"
"Efficient Instruction Sequencing with Inline Target Insertion"
"i860(TM) 64-bit Microprocessor"
"Available Instruction-Level Parallelism for Superscalar and Superpipelined Machines"
MIPS R2000 RISC Architecture
The Architecture of Pipelined Computers
"On the Number of Operations Simultaneously Executable in Fortran-likePrograms and Their Resulting Speedup"
"Branch Prediction Strategies and Branch Target Buffer Design"
"Reducing the Cost of Branches"
"The Design of the 88000 RISC Family"
"Measuring the Parallelism Available for Very Long Instruction Word Architectures"
"HPS, A New Microarchitecture: Rationale and Introduction"
"A VLSI RISC"
"WISQ: A Restartable Architecture Using Queues"
"Multiple Instruction Issue and Single-chip Processors"
"The Performance Potential of Multiple Functional Unit Processors"
"The 801 Minicomputer"
"Espresso-MV: Algorithms for Multiple-Valued Logic Minimization"
"A Study of Branch Prediction Strategies"
"Implementation of Precise Interrupts in Pipelined Processors"
"Limits on Multiple Instruction Issue"
"Tradeoffs in Instruction Format Design for Horizontal Ar- chitectures"
The SPARC(TM) Architecture Manual
"Detection and Parallel Execution of Independent Instruc- tions"
"An Instruction Issuing Approach to Enhancing Performance in Multiple Functional Unit Processors"
"An Efficient Algorithm for Exploiting Multiple Arithmetic Units"
"Instruction Issue Logic in Pipelined Supercomputers"
--TR
Design decisions in SPUR
An instruction issuing approach to enhancing performance in multiple functinal unit processors
Highly concurrent scalar processing
Reducing the cost of branches
HPS, a new microarchitecture: rationale and introduction
Branch folding in the CRISP microprocessor: reducing branch delay to zero
WISQ: a restartable architecture using queues
Architectural tradeoffs in the design of MIPS-X
Checkpoint repair for high-performance out-of-order execution machines
The performance potential of multiple functional unit processors
Trace selection for compiling large C application programs to microcode
Multiple instruction issue and single-chip processors
Tradeoffs in instruction format design for horizontal architectures
Available instruction-level parallelism for superscalar and superpipelined machines
Limits on multiple instruction issue
Inline function expansion for compiling C programs
Comparing software and hardware schemes for reducing the cost of branches
Forward semantic: a compiler-assisted instruction fetch method for heavily pipelined processors
Control flow optimization for supercomputer scalar processing
Multiple instruction issue in the NonStop cyclone processor
Implementation of precise interrupts in pipelined processors
The Design of the 88000 RISC Family
Optimizing delayed branches
The 801 minicomputer
A study of branch prediction strategies
A Characterization of Processor Performance in the vax-11/780
Hpsm

--CTR
Apoorv Srivastava , Alvin M. Despain, Prophetic branches: a branch architecture for code compaction and efficient execution, Proceedings of the 26th annual international symposium on Microarchitecture, p.94-99, December 01-03, 1993, Austin, Texas, United States
Oliver Rthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA
Sofine Tahar , Ramayya Kumar, A Practical Methodology for the Formal Verification of RISC Processors, Formal Methods in System Design, v.13 n.2, p.159-225, Sept. 1998
compiler;instruction sequencing;exceptions;interrupts;pipeline;branch slots;pipeline processing;delayed branches;inline target insertion;parallel programming;squashing;program counter;program compilers