\chapter{Example of RISC Architecture: MIPS} \label{chap:mips} \section{Introduction} The term {\bf RISC} is an acronym for \underline{r}educed \underline{i}nstruction \underline{s}et \underline{c}omputer, the antonym being {\bf CISC}, for \underline{c}omplex \underline{i}nstruction \underline{s}et \underline{c}omputer. During the 1970s and early 1980s, computers became more and more CISC-like, with richer and richer instruction sets. The most cited example is that of the VAX family (highly popular in the early 1980s), whose architecture included 304 instructions, including such highly specialized instructions as {\bf poly}, which evaluates polynomials. By contrast, the UC Berkeley RISC I architecture, which later became the basis for what is now the commercial SPARC chip in Sun Microsystems computers, had only 32 instructions. At the same time, the single-chip CPU was starting out on its path to dominance of the market. The more components a computer has, the more expensive it is to manufacture, so single-chip CPUs became very attractive.\footnote{And there is a performance gain as well. Multi-chip CPUs suffer from the problem that off-chip communication is slower than within-chip.} But the problem then became that the very limited space on a chip---this space is colloquially called ``real estate''---made it very difficult, if not impossible, to fit a CISC architecture onto a single chip.\footnote{It would seem that the solution is to simply make larger chips. However, this idea has not yet worked. For example, larger chips have lower {\bf yield} rates, i.e. lower rates of flaw-free chips. Of course, one can try to make chips denser as well, but there are limits here too.} The VAX was a clear casualty of this. When the Digital Equipment Corporation (DEC) tried to produce a ``VAX-on-a-chip,'' they found that they could not fit the entire instruction set on one chip. They were then forced to implement the remaining instructions in software. For example, when the CPU encountered a {\bf poly} instruction, that would cause an ``illegal op code'' condition, which triggered a {\bf trap} (i.e. internal interrupt); the trap-service routine would then be a procedure consisting of ordinary {\bf add} and {\bf mul} instructions which compute the polynomial. At this point, some researchers at IBM decided to take a fresh look at the whole question of instruction set formulation. The main point is optimal use of real estate. In a CISC CPU chip, a large portion of the chip is devoted to circuitry which is rarely, if ever used.\footnote{Actually, most CISC chips use a technique called {\bf microcode}, which would make the use of the word ``circuitry'' here a bit overly simplistic, but we will not pursue that here.} For example, most users of VAX machines did not make use of the {\bf poly} instruction, and yet the circuitry for that instruction would occupy valuable-but-wasted real estate in the chips comprising a VAX CPU. True, for those programs which did use the {\bf poly} instruction, execution speed increased somewhat,\footnote{You should think about this. First, {\bf poly}, being a single instruction, would require only one instruction fetch, compared to many fetches which would be needed if one wrote a function consisting of many instructions which would collectively perform the work that {\bf poly} does. Second, at the circuitry level, we might be able to perform more than one register transfer at once.} but for most programs the {\bf poly} instruction was just getting in the way of fast performance. Other factors came into play. For example, the richer the instruction set, the longer the decode portion of the instruction cycle would take. Even more important is the issue of pipelining, which is much harder to do in CISC machine, due to lack of uniformity in the instruction set (in a CISC machine, instructions tend to have different lengths). For this reason, the IBM people asked, ``Why do we need all this complexity,'' and they built the first RISC machine. Unfortunately, IBM scrapped their RISC project, but later David Patterson of the Division of Computer Science at UC Berkeley became interested in the idea, and developed two RISC CPU chips, RISC I and RISC II, which later became the basis of the commercial SPARC chip, as mentioned earlier. Patterson's team did not invent the RISC concept, nor did they invent the specific features of their design such as delayed branch (see below). Nevertheless, these people singlehandedly changed the thinking of the entire computer industry, by showing that RISC could really work well. The team considered the problem as a whole, investigating all aspects, ranging from the questions of chip layout and VLSI electronics technology to issues of compiler writing, and through this integrated approach were able to make a good case for the RISC concept. Manolis Katevenis, a Ph.D. student who wrote his dissertation on RISC under Professor Patterson, won the annual ACM award for the best dissertation in Computer Science.\footnote{Published as {\it Reduced Instruction Set Computer Architectures for VLSI}, M. Katevenis, MIT Press, 1984.} At about the same time, Professor John Hennessy at Stanford University (who was later to become president of the university) was conducting his own RISC project, leading to his founding of the MIPS Corporation, which produced his RISC chip. Silicon Graphics, Inc. eventually bought MIPS Inc. and SGI uses MIPS processors in its servers and so on, and though SGI is no longer one of the big players in those segments of the industry, MIPS processors are popular in the world of embedded applications. Today virtually every computer manufacturer has placed a major emphasis on RISC. Even Intel, the ultimate CISC company, has turned to RISC for its most powerful chips. Sun Microsystems has the SPARC chip, IBM and Motorola have the Power PC chip series used in Macs,\footnote{Though Apple has announced plans to switch to Intel starting 2008.} and so on. Of course, this does not imply that RISC is inherently ``superior,'' and as electronic technologies advance in the future, there may well be some resurgence of CISC ideas, at least to some degree. \section{A Definition of RISC} There is no universally-agreed-upon definition of RISC, but most people would agree at least to the following characteristics: \begin{itemize} \item Most instructions execute in a single clock cycle. \item ``Load/store architecture''---the only instructions which access memory are of the LOAD and STORE type, i.e. instructions that merely copy from memory to a register or vice versa, such as Intel's \begin{Verbatim}[fontsize=\relsize{-2}] movl (%eax), %ebx \end{Verbatim} and \begin{Verbatim}[fontsize=\relsize{-2}] movl %ecx, (%edx) \end{Verbatim} Instructions like Intel's {\bf addl \%eax, (\%ebx)} are not possible. \item Every instruction has the same length, e.g. 4 bytes. By contrast, Intel instructions range in length from 1 to several bytes. \item {\bf Orthogonal architecture} --- any operation can use any operand. This is in contrast, for example, to the Intel instruction STOS, which stores multiple copies of a string.\footnote{In this context it must be used with the REP prefix.} Here the only available operands are the registers EAX, ECX and EDI; one is not allowed to use any other register in place of these. \item The instruction set is limited to only those instructions which are truly justified in terms of performance/space/pipeline tradeoffs. The SPARC chip, for instance, does not even have a multiply instruction. If the compiler sees an expression like, say, \begin{Verbatim}[fontsize=\relsize{-2}] i = j * k; \end{Verbatim} in a source code file, the compiler must generate a set of add and shift instructions to synthesize the multiply operation, compared to the Intel case, in which the compiler would simply generate an {\bf imull} instruction. \item Hardwired implementation, i.e. not microcoded.\footnote{Again, we will not discuss microcode here.} \end{itemize} All but the last of the traits listed above make pipelining smoother and easier. \section{Beneficial Effects for Compiler Writers} Computer architects used to partly justify including instructions like {\bf poly} in the instruction set by saying that this made the job of compiler writers easier. However, it was discovered that this was not the case, for several reasons. \begin{itemize} \item Compiler writers found it difficult to write compilers which would automatically recognize situations in (say) C source code in which instructions like {\bf poly} could be used. \item Compiler writers found that some specialized instructions that were actually motivated by high-level language constructs did not match the latter well. For example, the VAX had a CASE instruction, obviously motivated by the Pascal {\bf case} and C {\bf switch} constructs; yet it turned out to be too restrictive to use well for compiling those constructs. \item CISC generally led to very nonorthogonal architectures, which made the job of compiler writers quite difficult. For instance, in Intel, the requirement that the EAX, ECX and EDI registers be used in STOS, \underline{plus} the requirement that some of these registers be used in certain other instructions, implies that compiler writers ``don't have any spare registers to work with,'' and thus they must have the compiler generate code to save and restore ``popular'' registers such as EAX; this is a headache for the compiler writer. \end{itemize} All of this inhibits development of compilers which produce very fast code. Most RISC machines do ask that the compiler writers do additional work of other kinds, though, in that they have to try to fill {\bf delay slots}; more on this below. \section{Introduction to the MIPS Architecture} MIPS is one of the most popular RISC chips, used for example in SGI workstations and in a number of embedded applications.\footnote{MIPS is also the subject of a simulator, SPIM, which is used in many university computer architecture courses. See \url{http://www.cs.wisc.edu/\~larus/spim.html}.} Every MIPS instruction is 32 bits, i.e. one word, in length, and every instruction which does not access memory executes in one cycle. Those that do access memory are assumed to ``usually'' take two cycles, meaning that this will be the case if the desired memory access results in a cache hit; otherwise, the CPU enters a {\bf stall} mode until the memory access is satisfied. \subsection{Register Set} There are 32 general registers, named \$0, \$1, ..., \$31. The assembler also has an alternate set of names for the registers, which show their suggested uses; here is a partial list: \begin{Verbatim}[fontsize=\relsize{-2}] $0 zero contains the hard-wired constant 0 $1-$2 v0-v1 for expression evaluation and function return values $4-$7 a0-a3 for passing arguments $8-$15 t0-t7 for temporary results ... $28 gp pointer to global area $29 sp stack pointer $30 fp frame pointer (not used) $31 ra return address \end{Verbatim} The usages listed above, e.g. \$29 as the stack pointer, are merely suggested; in keeping with the RISC philosophy of orthogonality, the registers are treated uniformly by the architecture. \subsection{Example Code} To introduce the MIPS architecture, here is a C program which calls a MIPS assembly language subroutine, {\bf addone()}: TryAddOne.c: \begin{Verbatim}[fontsize=\relsize{-2}] int x; main() { x = 7; addone(&x); printf("%d\n",x); // should print out 8 exit(1); } \end{Verbatim} AddOneMIPS.s: \begin{Verbatim}[fontsize=\relsize{-2}] .text .globl addone addone: lw $2,0($4) addu $2,$2,1 sw $2,0($4) j $31 \end{Verbatim} To begin, let's look at the compiled code we obtain by applying {\bf gcc -S} to TryAddOne.c. The source lines \begin{Verbatim}[fontsize=\relsize{-2}] x = 7; addone(&x); \end{Verbatim} translate to: \begin{Verbatim}[fontsize=\relsize{-2}] # x = 7; li $2,7 sw $2,x # addone(&x); la $4,x la $25,addone jal $31,$25 \end{Verbatim} The {\bf li} (Load Immediate) instruction puts 7 into the register \$2.\footnote{Actually, {\bf li} is not a real MIPS instruction, but is instead a macro, from which the assembler will generate an {\bf ori} instruction. More on this later.} The {\bf sw} (Store Word) instruction then copies what is in \$2 to the memory location x. Now, what about the call? Many RISC architectures are less stack-oriented than are the classical CISC ones. This is because stacks are in memory, and memory access is slow.\footnote{Some architectures, such as SPARC, try to solve this problem by actually having space on the CPU chip for the top few elements of the stack.} MIPS is an example of this philosophy. Both the argument to {\bf addone()}, as well as the return address, will be put in registers, rather than on the stack. The {\bf la} (Load Address) instruction here puts the argument, the address of {\bf x}, into register \$4.\footnote{Recall that registers \$4-\$7 are used for passing arguments. If there are more arguments, we can store them in memory, and one of the arguments can be a pointer to them.} We then use this same instruction to put the jump target, i.e. the address of {\bf addone()}, into \$25. We then call {\bf addone()} with the instruction \begin{Verbatim}[fontsize=\relsize{-2}] jal $31,$25 \end{Verbatim} which says to ``jump and link'' (i.e. do a subroutine call) to the subroutine pointed to by \$25, saving the return address (the address of the instruction following the {\bf jal}) in \$31. The return from the subroutine thus makes use of \$31: \begin{Verbatim}[fontsize=\relsize{-2}] j $31 \end{Verbatim} This is an unconditional jump, to the location pointed to by \$31. Note that operands have different meanings depending on the operation. In {\bf sw \$2, x}, the {\bf x} meant the memory location named {\bf x}, whereas in {\bf la \$4, x}, {\bf x} meant the address of {\bf x}. Recall that {\bf main()} had placed the argument in \$4. The subroutine then uses it: \begin{Verbatim}[fontsize=\relsize{-2}] lw $2,0($4) addu $2,$2,1 sw $2,0($4) \end{Verbatim} The {\bf lw} (Load Word) instruction is the opposite of {\bf sw}, fetching a word from memory rather than storing it. Both the {\bf lw} and {\bf sw} here use the more general format, which is based addressing. For example, \begin{Verbatim}[fontsize=\relsize{-2}] lw $2,0($4) \end{Verbatim} adds \$4 to 0, and then treats that as an address, fetching the contents of that address and putting it in register \$2. The {\bf addu} (Add Unsigned) instruction has three operands; it adds the second and third, and places the sum in the first. \subsection{MIPS Assembler Pseudoinstructions} Recall that most assembly languages allow {\bf macros}. MIPS assemblers go a step further, offering the programmer use of {\bf pseudoinstructions}; these appear to be machine instructions, but are actually like macros, which the assembler translates to one or more real MIPS instructions. Several ``instructions'' which we saw in the example above are actually pseudoinstructions. The first of those was {\bf li}, allegedly the Load Immediate instruction. There actually is no such instruction, and our line containing {\bf li} was actually treated by the assembler as \begin{Verbatim}[fontsize=\relsize{-2}] ori $2, $0, 7 \end{Verbatim} where {\bf ori} is the MIPS' OR Immediate instruction. Remember, the register \$0 contained the hardwired value 0, so the instruction above applies the logical OR operation to 0 and 7, yielding 7, and thus placing 7 into the register \$2, just as desired. So, why couldn't the designers of the MIPS architecture include {\bf li} Load Immediate instruction? To see the answer, suppose we wish to load a large number like 0xabcd1234, which is 32 bits in length. Remember, all MIPS instructions are 32 bits long, so this operand would occupy the entire instruction, with no room for an op code! Indeed, if our assembly language source code contains a line \begin{Verbatim}[fontsize=\relsize{-2}] li $2,0xabcd1234 \end{Verbatim} the assembler will actually treat it as if it were two instructions: \begin{Verbatim}[fontsize=\relsize{-2}] lui $1,0xabcd ori $2, $1, 0x1234 \end{Verbatim} The MIPS instruction {\bf lui} places the given immediate constant, 0xabcd in this case, and placing it in upper 16 bits of the destination, the register \$1 here, and places 0s in the lower 16 bits. The MIPS instruction {\bf ori} then puts 0x1234 in the lower 16 bits of a copy of \$1, then placing the result in \$2. This gets 0xabcd1234 into \$2, as desired. So, the use of pseudoinstructions here frees the programmer from having to think about the size of the operand she is using. Similarly, in the line \begin{Verbatim}[fontsize=\relsize{-2}] la $4, x \end{Verbatim} from our example code above, {\bf la} is just a pseudoinstruction, not a real MIPS machine instruction. One of the issues here is like the one with {\bf li} above; the address of x is a 32-bit quantity, and thus could not be fit into one instruction. The other issue is that we need a way of letting the assembler know that ``x'' here means the address of x, and our use of the pseudoinstruction {\bf la} tells the assembler that. Finally, there is even some chicanery in the line \begin{Verbatim}[fontsize=\relsize{-2}] sw $2, x \end{Verbatim} Actually, {\bf sw} IS a real MIPS instruction. But the real instruction has three operands, as in our other line, \begin{Verbatim}[fontsize=\relsize{-2}] sw $2, 0($4) \end{Verbatim} (the three operands are \$2, 0 and \$4), whereas \begin{Verbatim}[fontsize=\relsize{-2}] sw $2, x \end{Verbatim} has only two operands. The fact that there are only two operands here is a signal to the assembler that this too is a pseudoinstruction, in spite of the fact that there is a real MIPS instruction {\bf sw}. So, the assembler will convert this to an {\bf lui} and {\bf ori} and then a (real) {\bf sw}. \subsection{Programs Tend to Be Longer on RISC Machines} Note in our example above that it took two instructions \begin{Verbatim}[fontsize=\relsize{-2}] li $2,7 sw $2,x \end{Verbatim} to do what, for example, on Intel would take only one: \begin{Verbatim}[fontsize=\relsize{-2}] movl $7,x \end{Verbatim} In fact, we later found that those two instructions were actually pseudoinstructions, so here MIPS is taking four instructions to do what Intel does in one. This is typical of RISC machines, and means that RISC programs tend to be longer than CISC ones. For example, the compiled version of TryAddOne.c above\footnote{This is TryAddOne.o, generated from applying {\bf gcc -c} to TryAddOne.c.} is 1276 bytes long on an SGI machine but only 1048 on an Intel platform. \subsection{Instruction Formats} One very ``RISC-y'' feature of MIPS is that it has only three instruction formats.\footnote{By contrast, the Intel chip, a CISC, has a large number of instruction formats, and even the RISC SPARC chip has six.} To present them, let us number the most- and least-significant bits in a word as 31 and 0, respectively. Also, we will use the following abbreviations: \begin{Verbatim}[fontsize=\relsize{-2}] op op code -- ------- rs register operand rt register operand rd register operand imm immediate constant shamt shift amount funct special function (like an additional op code) dist distance factor to branch (i.e. jump) target \end{Verbatim} the formats are as follows. \begin{itemize} \item I (``immediate'') format: \begin{itemize} \item op: bits 31-26 \item rs (source): bits 25-21 \item rt (destination): bits 20-16 \item imm: bits 15-0 \end{itemize} \item J (``jump'') format: \begin{itemize} \item op: bits 31-26 \item dist: bits 25-0 \end{itemize} \item R (``register'') format: \begin{itemize} \item op: bits 31-26 \item rs (source): bits 25-21 \item rt (source): bits 20-16 \item rd (destination): bits 15-11 \item shamt: bits 10-6 \item funct: bits 5-0 \end{itemize} \end{itemize} The {\bf shamt} field is used if the instruction is to perform a right- or left-shift; the shift will be {\bf shamt} bits in the specified direction. The {\bf dist} field in J instructions is somewhat unusual, but actually clever: It is equal to 1/4 of the distance to the branch target.\footnote{Recall that {\it branch} is a synonym for {\it jump}.} Since all instructions are 4 bytes long, then every instruction address is a multiple of 4, and thus the distance from any branch instruction to its target is a multiple of 4, i.e. the distance has two 0 bits at the right end. That last point means that there is no point in storing the last two bits of the distance; they are simply tacked on by the CPU when the instruction is executed. This effectively multiplies the jump range by 4. The J format is used only for unconditional branches, including {\bf call}. Conditional branches use the I or R format. Note that the {\bf imm} field can have two interpretations, depending on {\bf op}. The {\bf addi} instruction, for example, treats the immediate constant as a signed number, while {\bf addiu} treats it as unsigned. Since MIPS has word size 32 bits, its ALU deals with 32-bit quantities, not the 16-bit quantity in an {\bf imm} field. Thus the latter must be extended to 32 bits before entering the ALU, by copying the leftmost bit to the leading 16 bits. Thus for instance in the instructions \begin{Verbatim}[fontsize=\relsize{-2}] addi $6, $7, 0xb123 addiu $9, $10, 0xb123 \end{Verbatim} in the first case the 0xb123 becomes 0xffffb123 while in the second case it becomes 0x0000b123. \subsection{Arithmetic and Logic Instruction Set} Here is a partial listing of the MIPS instruction set for arithmetic and logic operations: \begin{Verbatim}[fontsize=\relsize{-2}] add rd, rs, rt # rd <-- rs + rt addu rd, rs, rt # rd <-- rs + rt (without overflow) addi rd, rs, imm # rd <-- rs + imm and rd, rs, rt # rd <-- rs AND rt ani rd, rs, imm # rd <-- rs AND imm not rd, rs # rs <-- NOT rd or rd, rs, rt # rd <-- rs OR rt ori rd, rs, imm # rd <-- rs OR imm sll rd, rt, shamt # rd <-- rt << shamt srl rd, rt, shamt # rd <-- rt >> shamt sub rd, rs, rt # rd <-- rs - rt subu rd, rs, rt # rd <-- rs - rt (without overflow) \end{Verbatim} \subsection{Conditional Branches in MIPS} On a MIPS machine, applying {\bf gcc -S} to \begin{Verbatim}[fontsize=\relsize{-2}] if (i == 20) j = 2; \end{Verbatim} produces \begin{Verbatim}[fontsize=\relsize{-2}] lw $2,i li $3,20 bne $2,$3,.L4 li $2,2 sw $2,j \end{Verbatim} where .L4 is a label of the branch target. The {\bf bne} instruction compares the two registers and then branches to the target if they are not equal. (There is nothing like Intel's Z and S Flags in MIPS.) \section{Some MIPS Op Codes} \begin{Verbatim}[fontsize=\relsize{-2}] ORI 001101 LUI 001111 SW 101011 JAL 000011 J 000010 BNE 000101 ADDI 001000 ADDU 001001 \end{Verbatim} \section{Dealing with Branch Delays} RISC architectures are especially good at having smooth pipeline operation, due to the uniformity of instruction execution time: Every instruction executes in one clock cycle, except for branches and load/store instructions, which access memory and thus take longer. Even to go to the cache takes up an extra clock cycle, and going to full memory takes even longer. Thus the pipeline is delayed. For example, consider this MIPS code: \begin{Verbatim}[fontsize=\relsize{-2}] subiu $2, $2, $1 bne $4, $3, yyy addiu $5, $5 12 \end{Verbatim} While the fetch/decode/execute cycle for the {\bf bne} is taking place, the CPU is prefetching the {\bf addiu}. But if the branch is taken, the instruction at yyy will be the one we need, and it will not have been prefetched. \subsection{Branch Prediction} One possible way to deal with the branch-delay problem is to design the hardware to try to predict whether a conditional branch will be taken or not. The hardware will prefetch from the instruction which it predicts will be executed next. If it is correct, there is no delay; if the prediction is false, we must fetch the other instruction, incurring the delay. Even non-RISC architectures do this. Intel CPUs, for example do the following when a given conditional branch instruction is executed for the first time: If it is a branch backward, the prediction is that the branch will be taken; this design is motivated by the assumption that backward branches will typically be the last instruction within a loop, and usually such branches will be taken. If the branch is forward, the prediction is that it will not be taken. In subsequent times this particular branch instruction is executed, a complicated prediction algorithm is applied, based on previous history. \subsection{Delayed Branch} MIPS---as well as most RISC chips---solves this problem by using something called {\bf delayed branch}. The CPU actually executes the instruction which sequentially follows the branch instruction in memory, in this case the {\bf addiu}, before executing the instruction at the branch target. That way useful work is being done during the delay involving fetching of the branch target. But wait! This can't work as it stands. After all, if the branch is taken, we do not want to execute that {\bf addiu}! So, the assembler (or compiler, in the case of C/C++) must put in a ``do nothing'' instruction: {\bf nop}, pronounced ``no-op'' for ``no operation.''\footnote{Almost every CPU architecture has this kind of instruction. On MIPS, its op code is all 0s.} \begin{Verbatim}[fontsize=\relsize{-2}] subiu $2, $2, $1 bne $4, $3, yyy nop addiu $5, $5 12 \end{Verbatim} But now we are back to the original problem --- no useful work is being done while the instruction at yyy is being fetched. So, next an optimizer within the assembler (or compiler) will try to actually rearrange the instructions. It will look for some instruction elsewhere in the code which can be moved into the slot currently occupied by the {\bf nop}. In this case, the {\bf subiu} can be safely moved: \begin{Verbatim}[fontsize=\relsize{-2}] bne $4, $3, yyy subiu $2, $2, $1 addiu $5, $5, 12 \end{Verbatim} The reasoning is this: The {\bf bne} is not affected by the outcome of the {\bf subiu} which precedes it (this would not be true if the {\bf bne} compared \$4 with \$2, for example), so it doesn't matter if we move the {\bf subiu}. Remember, the latter will still be executed, because the CPU is designed to execute the instruction which immediately follows the branch in memory. \checkpoint The setup for load/store instructions is similar. The MIPS CPU will execute the instruction which immediately follows a load/store instruction in memory while performing the load/store. This is done because the latter requires a time-consuming memory access. But as with branches, we need to watch out for dependencies. For example, consider \begin{Verbatim}[fontsize=\relsize{-2}] lw $2, 0($4) addiu $2, $2, 1 \end{Verbatim} The CPU would execute the add simultaneously with fetching register \$2, with potentially disastrous consequences. Thus the assembler will at first change this to \begin{Verbatim}[fontsize=\relsize{-2}] lw $2, 0($4) nop addiu $2, $2, 1 \end{Verbatim} and then the optimizer will try to find some instruction elsewhere to move to the position now occupied by the {\bf nop}. The instruction position following a branch or load/store is called a {\bf delay slot}. Machines such as MIPS and SPARC have one delay slot, but some other machines have more than one. Clearly, the more delay slots there are, the harder it is to ``fill'' them, i.e. to find instructions to move to put in the slots, and thus avoid simply putting wasteful NOPs in them. How hard is it to fill even one delay slot? The Katevenis dissertation on RISC says: \begin{quote} Measurements have shown [citation given] that the [compiler] optimizer is able to remove about 90\% of the no-ops following unconditional transfers and 40\% to 60\% of those following conditional branches. The unconditional and conditional transfer-instructions each represent approximately 10\% of all executed instructions (20\% total). Thus, while a conventional pipeline would lose $\approx$ 20\% of the cycles, optimized RISC code only loses about 6\% of them. \end{quote}