S E C O N D ED IT ION
`
`Computer Organization and Design
`
`THE HARDWARE/SOFTWARE
`
`INTERFACE
`
`INTEL - 1012
`
`

`

`T R A D E M A R K S
`
`The following trademarks are the property of the following organizations:
`
`TeX is a trademark of America! Mathematical Society.
`
`Apple ll and Macintosh are trademarks of Apple Computers, Inc.
`
`CDC 6600, CDC 7600, CDC STAR-100, CYBER-180, CYBER-
`180/990, and CYBER-205 are trademarks of Control Data Corpora(cid:173)
`tion .
`
`The Cosmic Cube is a trademark of California Institute of Technol(cid:173)
`ogy.
`CP3100 is a trademark of Conner Peripherals.
`
`Cray, CRAY-1, CRAY )90, CRAY T90, CRAY X-MP/416, and
`CRAY Y-MI' are trademarks of Cray Research.
`
`Alpha, AlphaServer, AlphaStation, DEC, DECsystem, DECsystem
`3100, DECstation, PDP-8, PDP-11, Unibus, VAX, VAX 8700, and
`VAXl 1 / 780 are trademarks of Digital Equipment Corporation.
`
`MP2361 A, Super Eagle, VPlOO, VP200, and VPP300 are trademarks
`of Fujitsu Corporation.
`
`Gnu C Compiler is a trademark of Free Software Foundation.
`
`Goodyear MP!' is a trademark of Goodyear Tire and Rubber Co.,
`Inc.
`
`Apollo ON 300, Apollo ON 10000, Convex, HP, HP Precision
`Architectu re, HPl'A, HP850, HP 3000, HP 300/70, PA-RISC, and
`Precision are registered trademarks of Hew let-Packard Company.
`
`432, 960 CA, 4004, 8008, 8080, 8086, 8087, 8088, 80186, 80286, 80386,
`80486, Delta, iAPX 432, i860, Intel, lntel486, Intel Hypercube, iP(cid:173)
`SC/2, MMX, Multibus, Multibus II, Paragon, and Pentium are
`trad emarks of Intel Corporation. Intel Inside is a registered trad e(cid:173)
`mark of Intel Corporation.
`
`360, 360/30, 360/40, 360/50, 360/65, 360/85, 360/91, 370, 370/158,
`370/165, 370/168, 370-XA, ESA /370, 701,704,709,801, 3033, 3080,
`3080 series, 3080 VF, 3081, 3090, 3090/100, 3090/200, 3090/400,
`3090/ 600, 3090/600S, 3090 VF, 3330, 3380, 3380D, 3380 Disk Mod el
`AK4, 3380), 3390, 3880-23, 3990, 7090, 7094, IBM, IBM PC, IBM PC(cid:173)
`AT, IBM SYS, ISAM, MYS, l'L.8, Powerl'C, l'OWERstation, RT-PC,
`RAMAC, RS / 6000, Sage, Stretch, System/360, Vector Faility, and
`VM are trademarks of International Business Machines Corpora(cid:173)
`l'OWERserver, RISC System /6000, and SP2 are registered
`tion.
`trad emarks of International Business Machines Corporation.
`
`!CL OAP is a trad emark of Internationa l Computers Limited.
`
`lnmos and Transputer arc trad emarks of lnmos.
`
`FutureBus is a trademark of the In stitute of Electrical and Electron(cid:173)
`ic Engineers.
`
`KSR- 1 is a trademark of Kendall Square Resea rch.
`
`MASl'AR MP-1 and MASPAR MP-2 are trademarks of MasPar
`Corpora lion.
`
`MIPS, R2000, R3000, and RlOOOO are registered trademarks of
`MIPS Technology, Inc.
`
`Windows is a trademark of Microsoft Corporation.
`
`Nu Bus is a trademark of Massachusetts Institute of Technology.
`
`Delta Series 8608, System V /88 R32Vl, VME bus, 6809, 68000,
`68010, 68020, 68030, 68881, 68882, 88000, 88000 1.8.4m 14, 88100,
`and 88200 are trademarks of Motorola Corporation.
`
`Ncube and nCube / ten are trademarks of cube Corporation.
`
`NEC is a registered trademark of NEC Corporation.
`
`Network Computer is a trademark of Oracle Corporation.
`
`Parsytec CC is a trademark of Parsytec, Inc.
`lmprimis, JPl-2, Sabre, Sabre 97209, Seagate, and Wren IV are
`trademarks of Seagate Technology, Inc.
`
`NUMA-Q, Sequent, and Symmetry are trademarks of Sequent
`Computers.
`
`Power Cha llenge, Silicon Graphics, Silicon Graphics 43 / 240,
`Silicon Graphics 4D/60, Silicon Graphics 4D/240, and Silicon
`Graphics 4D Series are trademarks of Silicon Graphics. Origin2000
`is a registered trad emark of Silicon Graphics.
`
`SPEC is a registered trademark of the Standard Performance Eval(cid:173)
`uation Corporation.
`
`Spice is a trademark of University of California at Berkeley.
`
`Enterprise, Java, Sun, Sun Ultra, Sun Microsystems, and Ultra are
`trademarks of Sun Microsystems, Inc. SPARC and UltraSPARC
`are registered trademarks of SPARC International, Inc., licensed to
`Sun Microsystems, Inc.
`
`Connection Machine, CM-2, and CM-5 are trademarks of Thinking
`Ma chines.
`
`Burroughts 6500, 85000, 85500, D-machine, UN IV AC, UNIVAC I,
`and UNIVAC 1103 are trademarks of UN ISYS.
`
`Alto, I' ARC, Palo Alto Research Center, and Xerox are trademarks
`of Xerox Corporation.
`
`The UN IX trademark is licensed exclusively through X/Open
`Company Ltd.
`
`All other product names are trademarks or registered trademarks
`of their respective companies. Where trademarks appear in this
`book and Morgan Kaufmann Publishers was aware of a trademark
`claim, the trademarks have been printed in initial caps or all caps.
`
`S E C O N D
`
`E D
`
`T
`
`0 N
`
`Computer Organization and Design
`T H E HARDWARE /SOFTWARE
`
`I N T E R F A C E
`
`John L. Hennessy
`Stanford University
`
`David A. Patterson
`University of California, Berkeley
`
`With a contribution by
`James R. Larus
`University of Wisconsin
`
`M::(cid:141)
`
`Morgan Kaufmann Publishers, Inc.
`San Francisco, California
`
`INTEL - 1012
`
`

`

`Sponsoring Editor Denise Penrose
`Production Manager Y,mie Overton
`Production Editor Julie Pabst
`Editorial Coordinator Jane Elliott
`Text and Cover Design Ross Carron Design
`Illustration Alexander Teshin Associates, with second edition modifications by Dartmouth
`Publishing, Inc.
`Chapter Opener Illustrations Canary Studios
`Copyeditor Ken DellaPenta
`Composition Nancy Logan
`Proofreader Jennifer McClain
`Indexer Steve Rath
`Printer Courier Corporation
`
`Morgan Kaufmann Publishers, Inc.
`Editorial and Sales Office:
`340 Pine Street, Sixth Floor
`San Francisco, CA 94104-3205
`USA
`
`Telephone 415/392-2665
`Facsimile 415/982-2665
`Email mkp@mkp.com
`WWW http://www.mkp.com
`Order toll free 800/745-7323
`
`© 1998 by Morgan Kaufmann Publishers, Inc.
`All rights reserved
`Printed in the United States of America
`
`02 01
`
`10 9 8 7
`
`No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form
`or by any means-electronic, mechanical, photocopying, recording, or otherwise-without the prior
`written permission of the publisher.
`
`Advice, Praise, and Errors: Any correspondence related to this publication or intended for the authors
`should be sent electronically to cod2bugs@mkp.com. Information regarding error sightings is encouraged.
`Any error sightings that are accepted for correction in subsequent printings will be rewarded by the
`authors with a payment of $1.00 (U.S.) per correction at the time of their implementation in a reprint.
`
`Library of Congress Cataloging-in-Publication Data
`Patterson, David A.
`Computer organization and design: the hardware/software interface
`/ David A. Patterson, John L. Hennessy.-2nd ed.
`p. cm.
`Includes bibliographical references and index.
`ISBN 1-55860-428-6 (cloth).-ISBN 1-55860-491-X (paper)
`l. Computer organization. 2. Computers-Design and construction.
`I. Hennessy, John L.
`3. Computer interfaces.
`II. Title
`QA76.9.C643H46
`1997
`004.2'2-dc21
`
`97-16050
`
`~--···-···· •••• --;"·™™-•'l'lailiiii:=i=·•il!Na"··=• =--~•~-'""'---"'IW=:l·::!l'=•m•==--·=·-'AlfXt'lli®
`
`T 0
`
`L I N D A
`
`A N D
`
`A N D R E A
`
`INTEL - 1012
`
`

`

`r
`
`3.1
`3.2
`3.3
`3.4
`3.5
`3.6
`3.7
`3.8
`3.9
`3.10
`3.11
`3.12
`3.13
`3.14
`3.15
`3.16
`3.17
`
`Introduction 106
`Operations of the Computer Hardware 107
`Operands of the Computer Hardware 109
`Representing Instructions in the Computer 116
`Instructions for Making Decisions 122
`Supporting Procedures in Computer Hardware 132
`Beyond Numbers 142
`Other Styles of MIPS Addressing 145
`Starting a Program 156
`An Example to Put It All Together 163
`Arrays versus Pointers 171
`Real Stuff: PowerPC and 80x86 Instructions 175
`Fallacies and Pitfalls 185
`Concluding Remarks 187
`Historical Perspective and Further Reading 189
`Key Terms 196
`Exercises 196
`
`The Five Classic Components of a Computer
`
`Instructions:
`Language of
`the Machine
`
`I speak Spanish to God,
`Italian to women,
`French to men,
`and German to my horse.
`
`Charles V, King of France
`1337-1380
`
`Evaluating
`performance
`
`INTEL - 1012
`
`

`

`106
`
`Chapter 3
`
`Instructions: Language of the Machine
`
`3.2 Operations of the Computer Hardware
`
`107
`
`(cid:127)
`
`Introduction
`
`To command a computer's hardware, you must speak its language. The
`words of a machine's language are called instructions, and its vocabulary 1s
`called an instruction set. In this chapter you will see the instruction set of a real
`computer, both in the form written by human~ and in tl:e form read by ~he
`machine. Starting from a notation that looks hke a restricted programmmg
`language, we refine it step-by-step until you see the real language of a real
`computer.
`.
`You might think that the languages of machines wo~ld ?e _as diverse_ as
`those of humans, but in reality machine languages are quite s1m1lar, more hke
`regional dialects than like independent languages. Hence once you learn one,
`it is easy to pick up others. This similarity occurs because all com_puter~ ar_e
`constructed from hardware technologies based on similar underlymg prmc1-
`ples and because there are a few basic operations that all mach_ines must pro(cid:173)
`vide. Moreover, computer designers have a common goal: to fmd a language
`that makes it easy to build the hardware and the compiler while maximiz!ng
`performance and minimizing cost. This goal is time-honored; the followmg
`quote was written before you could buy a computer, and it 1s as true today as
`it was in 1947.
`It is easy to see by fonnnl-logical methods that there exist certain [instruction sets]
`that are in abstract adequate to control nnd cause tire executwn of nn_y sequence of
`operations . ... The really decisive considerations from the present point_ of view, in
`selecting an [instruction set], are more of n practical nature: s11npl1nty of the
`equipment demanded by the {instru ction set], and the clnnty of its ap_pl1cat1on to
`the actually important problems together with tire speed of its lrn11dl111g of those
`problems.
`
`Burks, Goldstine, and von Neumann, 1947
`
`The "simplicity of the equipment" is as valuable a considerati~n for the
`machines of the 2000s as it was for those of the 1950s. The goal of this chapter
`is to teach an instruction set that follows this advice, showing both how it is
`represented in the hardware and the relationship between high-level progrnm(cid:173)
`ming languages and this more primitive one. We are using the C programmmg
`language. (If you are familiar with Pascal, you may wish to refer _to Web Ext~n(cid:173)
`sion III, available at www.mkp.com/cod2e.htm, for a short comparison of C with
`Pascal.)
`By learning how instructions are represented, you will abo disc~ver the
`secret of computing: the stored-program concept. And you will exercise your
`"foreign language" skills by writing programs in the language of the machme
`
`(cid:127)
`
`and running them on the simulator that comes with this book. We conclude
`with a look at the historical evolution of instruction sets and an overview of
`other machine dialects.
`The chosen instruction set comes from MIPS, used by NEC, Nintendo,
`Silicon Graphics, and Sony, among others, and is typical of instruction sets de(cid:173)
`signed since the ea rly 1980s. We reveal the MIPS instruction set a piece at a
`time, giving the rationale along with the machine structures. This step-by-step
`tutorial weaves the components with their ex planations, making assembly lan(cid:173)
`guage more palatable. To keep the overall picture in mind, each section ends
`with a figure summarizing the MIPS instruction set revealed thus far, high(cid:173)
`lighting the portions presented in that section.
`
`Operations of the Computer Hardware
`
`There must certainly be instructions for performing the f11ndn111entn l nrit/1111ctic
`operations.
`
`Burks, Goldstine, c1nd von Neumann, 1947
`
`Every computer must be able to perform c1rithmetic. The MIPS assembly lan(cid:173)
`guage notation
`adda , b ,c
`instructs a computer to add the two variables b and c and to put their sum
`in a.
`This notation is rigid in that each MIPS arithmetic instruction performs only
`one operation and m.ust always have exactly three variables. For example, sup(cid:173)
`pose we want to place the sum of variables b, c, d, and e into variable a. (In this
`section we are being deliberately vague about what a "variable" is; in the next
`section we'll give a more detailed and realistic picture.)
`The following sequence of instructions adds the variables:
`add a , b , c # The sum of b and c is pl ac ed
`in a .
`add a, a , d # The sum of b , c , and d is now i n a .
`add a , a , e # The sum of b . c , d , and e is no1v
`in a .
`Thus it takes three instructions to take the sum of four variables.
`The words to the right of the sharp symbol (ii ) on each line above cire t'o111 -
`111ents for the human reader, and they are ignored by the computer. Note th,1t
`unlike other programming languages, each line of this language can contain at
`most one instruction. Another difference is that comments alwc1ys termi nate ,1t
`the end of a line.
`
`INTEL - 1012
`
`

`

`108
`
`Chapter 3
`
`Instructions: Language of the Machine
`
`3.3 Operands of the Computer Hardware
`
`109
`
`The natural number of operands for an operation like addition is three: the
`two numbers being added together and a place to put the sum. Requiring ev(cid:173)
`ery instruction to have exactly three operands, no more and no less, conforms
`to the philosophy of keeping the hardware simple: hardware for a variable
`number of operands is more complicated than hardware for a fixed number.
`This situation illustrates the first of four underlying principles of hardware
`design:
`Design Principle 1: Simplicity favors regularity.
`We can now show, in the two examples that follow, the relationship of pro(cid:173)
`grams written in higher-level programming languages to programs in this
`more primitive notation. Figure 3.1 summarizes the portions of MIPS assembly
`language described in this section.
`
`Example
`
`Compiling Two C Assignment Statements into MIPS
`
`This segment of a C program contains the five variables a, b, c, d, and e:
`a
`b + c ;
`d = a - e ;
`
`The translation from C to MIPS assembly language instructions is per(cid:173)
`formed by the compiler. Show the MIPS code produced by a C compiler.
`
`Answer
`
`I
`
`A MIPS instruction operates on two source operands and places the result
`in one destination operand. Hence the two simple C statements above
`compile directly into these two MIPS assembly language instructions:
`
`add a , b, c
`subd,a , e
`
`MIPS assembly language
`
`i@@ii·i:INifi::HFM:Jifi:ii:iW
`
`Category
`
`Arithmetic
`
`add
`subtract
`
`add a • b . c
`sub a • b . c
`
`b + c
`a
`a = b - c
`
`Comments
`
`Always three operands
`Always three operands
`
`FIGURE 3.1 MIPS architecture revealed in section 3.2. The real machine operands will be
`un veiled in the next section. Highlighted portions in such summaries show MIPS assembly
`language structures introduced in this section; for this first figure, all is new.
`
`Compiling a Complex C Assignment into MIPS
`
`Example
`
`A somewhat complex C statement contains the five variables f, g, h, i , and
`j :
`
`f = (g + h) -
`
`(i + j);
`
`What would a C compiler produce?
`
`Answer
`
`The compiler must break this C statement into several assembly instruc(cid:173)
`tions since only one operation is performed per MIPS instruction. The first
`MIPS instruction calculates the sum of g and h. We must place the result
`somewhere, so the compiler creates a temporary variable, called tO :
`add tO , g,h # temporary variab le tO contains g + h
`
`Although the next C operation is subtract, we need to calculate the sum of
`i and j before we can subtract. Thus the second instruction places the sum
`i and j in another temporary variable created by the compiler, called tl:
`add tl.i , j # temporary variable tl contains i + j
`
`Finally, the subtract instruction subtracts the second sum from the first and
`places the result in the variable f, completing the compiled code:
`sub f,tO,tl # f get s to - tl . which is (g + h)-(i + j)
`
`These instructions are symbolic representations of what the MIPS processor
`actually understands. In the next few sections we will evolve this symbolic
`representation into the real language of MIPS, with each step making the sym(cid:173)
`bolic representation more concrete.
`
`Operands of the Computer Hardware
`
`Unlike programs in high-level languages, the opera nd s of ari thmetic instruc(cid:173)
`tions cannot be any variables; they must be from a limited number of specia l
`locations called registers. Registers are the bricks of computer construction, for
`registers are primitives used in hardware d esign that are also visible to the
`programmer when the computer is completed . The size of a register in the
`MIPS architecture is 32 bits; groups of 32 bits occur so frequently that they are
`given the name word in the MIPS architecture.
`One major difference between the variables of a programming language
`and registers is the limited number of registers, typically 32 on current com(cid:173)
`puters. MIPS has 32 registers. (See section 3.15 for the history of the number of
`
`(cid:127)
`
`INTEL - 1012
`
`

`

`110
`
`Chapter 3
`
`Instructions: Language of the Machine
`
`3.3 Operands of the Computer Hardware
`
`111
`
`registers.) Thus, continuing in our stepwise evolution of the symbolic
`representation of the MIPS language, in this section we have added the restric(cid:173)
`tion that the three operands of MIPS arithmetic instructions must each be cho(cid:173)
`sen from one of the 32 32-bit registers.
`The reason for the limit to 32 registers may be found in the second of our
`four underlying design principles of hardware technology:
`Design Principle 2: Smaller is faster.
`A very large number of registers would increase the clock cycle time simply
`because it takes electronic signals longer when they must travel farther.
`Guidelines such as "smaller is faster" are not absolutes; 31 registers may not
`be faster than 32. Yet the truth behind such observations causes computer de(cid:173)
`signers to take them seriously. In this case, the designer must balance the crav(cid:173)
`ing of programs for more registers with the designer's desire to keep the clock
`cycle fast.
`Chapters 5 and 6 show the central role that registers play in hardware con(cid:173)
`struction; as we shall see in this chapter, effective use of registers is key to pro(cid:173)
`gram performance.
`Although we could simply write instructions using numbers for registers,
`from Oto 31, the MIPS convention is to use two character names following a
`dollar sign to represent a register. Section 3.6 will explain the reasons behind
`these names. For now we will use $s0, $sl, ... for registers that correspond
`to variables in C programs and HO, Hl, ... for temporary registers needed
`to compile the program into MIPS instructions.
`
`Compiling a C Assignment Using Registers
`
`Example
`
`It is the compiler's job to associate program variables with registers. Take,
`for instance, the C assignment statement from our earlier example:
`
`f= (g+h) -
`
`(i +j);
`
`The variables f, g, h, i, and j can be assigned to the registers $ s O, $ s 1, $ s 2,
`$ s 3, and $ s 4, respectively. What is the compiled MIPS assembly code?
`
`Answer
`
`The compiled program is very similar to the prior example, except we re(cid:173)
`place the variables with the registers mentioned above plus two tempo(cid:173)
`rary registers, HO and Hl, which correspond to the temporary variables
`above:
`
`add HO,$sl,$s2
`add Hl , $s3 , $s4
`sub $s0 . HO ,$ tl
`
`# register $t0 conta i ns g + h
`# register $tl contains i + j
`fl f gets HO - Hl, which is (g + h)-(i + j)
`
`Programming languages have simple variables that contain single data ele(cid:173)
`ments as in these examples, but they also have more complex data structures
`such as arrays. These complex data structures can contain many more data
`elements than there are registers in a machine. How can a computer represent
`and access such large structures?
`Recall the five components of a computer introduced in Chapter 1 and de(cid:173)
`picted on page 105. The processor can keep only a small amount of data in reg(cid:173)
`isters, but computer memory contains millions of data elements. Hence data
`structures, such as arrays, are kept in memory.
`As explained above, arithmetic operations occur only on registers in MIPS
`instructions; thus MIPS must include instructions that transfer data between
`memory and registers. Such instructions are called data transfer instructions. To
`access a word in memory, the instruction must supply the memory address.
`Memory is just a large, single-dimensional array, with the address acting as the
`index to that array, starting at 0. For example, in Figure 3.2, the address of the
`third data element is 2, and the value of Memory[2] is 10.
`The data transfer instruction that moves data from memory to a register is
`traditionally called load. The format of the load instruction is the name of the
`operation followed by the register to be loaded, then a constant and register
`used to access memory. The memory address is formed by the sum of the con(cid:173)
`stant portion of the instruction and the contents of the second register. The
`actual MIPS name for this instruction is l w, standing for load word.
`
`3
`
`2
`
`1
`
`0
`
`100
`
`10
`
`101
`
`1
`
`Address
`
`Data
`
`Processor
`
`Memory
`
`FIGURE 3 .2 Memory addresses and contents of memory at t hose locations. This is a sim(cid:173)
`plification of the MIPS addressing; Figure 3.3 shows MIPS addressing for sequential words in
`memory.
`
`INTEL - 1012
`
`

`

`112
`
`Chapter 3
`
`Instructions: Language of the Machine
`
`3.3 Operands of the Computer Hardware
`
`113
`
`Example
`
`Answer
`
`Compiling an Assignment When an Operand Is in Memory
`
`Let's assume that A is an array of 100 words and that the compiler has
`associated the variables g and h with the registers $ s 1 and $ s 2 as before.
`Let's also assume that the starting address, or base address, of the array is in
`$s3. Translate this C assignment statement:
`g = h + A[8] ;
`
`Although there is a single operation in this C assignment statement, one of
`the operands is in memory, so we must first transfer A [ 8] to a register. The
`address of this array element is the sum of the base of the array A, found
`in register $ s 3, plus the number to select element 8. The data should be
`placed in a temporary register for use in the next instruction. Based on
`Figure 3.2, the first compiled instruction is
`$t0,8($s 3) H Tem porary reg $t0 gets A[8]
`
`lw
`
`(On the next page we'll make a slight adjustment to this instruction, but
`we'll use this simplified version for now.) The follow ing instruction can
`operate on the value in $ tO (which equals A [ 8 ]) since it is in a register. The
`instruction must add h (contained in $s2) to A[8] (H O) and put the sum
`in the register corresponding to g (associated with $ s 1):
`add $sl,$s2,$t0 # g = h + A[8J
`
`The constant in a data transfer instruction is called the offset, and the reg(cid:173)
`ister added to form the address is called the base register.
`
`Hardware
`Software
`Interface
`
`In addition to associating variables with registers, the com(cid:173)
`piler allocates data structures like arrays and structures to
`locations in memory. The compiler can then place the
`proper starting address into the data transfer instructions.
`Since 8-bit bytes are useful in many programs, most ar(cid:173)
`chitectures address individual bytes. Therefore the address
`of a word matches the address of one of the 4 bytes within
`the word. Hence, addresses of sequential words differ by 4. For example,
`Figure 3.3 shows the actual MIPS addresses for Figure 3.2; the byte address of
`the third word is 8.
`Words must always start at addresses that are multiples of 4 in MIPS. This
`requirement is called an alignment restriction, and many architectures have it.
`(Chapter 5 suggests why alignment leads to faster data transfers.)
`
`12
`
`8
`
`4
`
`0
`
`100
`
`10
`
`101
`
`1
`
`Address
`
`Data
`
`Processor
`
`Memory
`
`FIGURE 3 .3 Actual MIPS memory addresses and contents of memory for those words.
`The changed addresses are highlighted to contrast with Figure 3.2. Since MIPS addresse;, each
`byte, word addresses are multiples of four (there are four bytes in a word).
`
`Machines with byte addresses are split into those that use the address of
`the leftmost or "big end" byte as the word address versus those that use the
`rightmost or "little end" byte. MIPS is in the Big Endinn camp. (Appendix A,
`page A-48, shows the two options to number bytes in a word.)
`Byte addressing also affects the array index. To get the proper byte address
`in the code above, the offset to be added to the base register $s3 must be
`4 x 8, or 32, so that the load address will select A [ 8 J and not A [ 8 / 4 J.
`
`The instruction complementary to load is traditionally called store; it trans(cid:173)
`fers data from a register to memory. The format of a store is similar to that of a
`load: the name of the operation, followed by the register to be stored, then off(cid:173)
`set to select the array element, and finally the base register. Once again, the
`MIPS address is specified in part by a constant and in part by the contents of a
`register. The actual MIPS name is sw, standing for store word.
`
`Compiling Using Load and Store
`
`Example
`
`Assume variable his associated with register $s2 and the base address of
`the array A is in $s3. What is the MIPS assembly code for the C assignment
`statement below?
`A[12] = h + A[8];
`
`INTEL - 1012
`
`

`

`114
`
`Chapter 3
`
`Instructions: Language of the Machine
`
`3.3 Operands of the Computer Hardware
`
`115
`
`Although there is a single operation in the C statement, now two of the op(cid:173)
`erands are in memory, so we need even more MIPS instructions. The first
`two instructions are the same as the prior example, except this time we use
`the proper offset for byte addressing in the load word instruction to select
`A[8] , and the add instruction places the sum in $t0:
`# Temporary reg St0 gets A[8J
`# Temporary reg St0 gets h + A[8J
`
`$t 0 , 32( $s3 )
`lw
`add St 0 , Ss2 , $t0
`
`The final instruction stores the sum into A [ 12 J, using 48 as the offset
`and register $ s 3 as the base register.
`# Stores h + A[8J back into A[12J
`sw
`St0,48($s3 )
`
`Arrays are often accessed with variables instead of constants, so that the ar(cid:173)
`ray element being selected can change while the program is running.
`
`Compiling Using a Variab.le Array Index
`
`Example
`
`Here is an example of an array with a variable index:
`
`g=h+A[i] ;
`
`Answer
`
`I
`
`Assume A is an array of 100 elements whose base is in register $ s3 and that
`the compiler associates the variables g, h, and i with the registers $ s 1, $ s 2,
`and $s4. What is the MIPS assembly code corresponding to this C
`segment?
`
`Before we can load A [ i J into a temporary register, we need to have its ad(cid:173)
`dress. Before we can add i to the base of array A to form the address, we
`must multiply the index i by 4 due to the byte addressing problem. We
`will see a multiply instruction in the next chapter; for now we will get the
`effect of multiplying i by 4 by first adding i to itself ( i + i = 2 i ) and then
`adding that sum to itself (2i + 2 i = 4 i ):
`# Temp reg Stl = 2 * i
`add Stl,$s4,Ss4
`# Temp reg Stl = 4 * i
`add Stl,$tl,$tl
`To get the address of A[ i ], we need to add $ tl and the base of A in $ s 3:
`# Stl = address of A[i] (4 * i + Ss 3)
`
`add Stl , $tl , $s3
`
`Now we can use that address to load A [ i J into a temporary register:
`$t0 , 0($tl) # Temporary reg HO= A[i]
`
`lw
`
`The final instruction adds A [ i J and h, and places the sum in g:
`add Ssl , $s2,$t0 # g = h + A[i]
`
`Hardware
`Software
`Interface
`
`Many programs have more variables than machines have
`registers. Consequently, the compiler tries to keep the most
`frequently used variables in registers and places the rest in
`memory, using loads and stores to move variables between
`registers and memory. The process of putting less com-
`monly used variables (or those needed later) into memory is
`called spilling registers.
`The hardware principle relating size and speed suggests that memory must
`be slower than registers since registers are smaller. This is indeed the case;
`data accesses are faster if data is kept in registers instead of memory.
`Moreover, data is more useful when in a register. A MIPS arithmetic
`instruction can read two registers, operate on them, and write the result. A
`MIPS data transfer instruction only reads one operand or writes one operand,
`without operating on it.
`Thus MIPS registers take both less time to access and have higher through(cid:173)
`put than memory-a rare combination-making data in registers both faster
`to access and simpler to use. To achieve highest performance, MIPS compilers
`must use registers efficiently.
`
`Figure 3.4 summarizes the portions of the symbolic representation of the
`MIPS instruction set described in this section. Load word and store word are
`the instructions that transfer words between memory and registers in the MIPS
`architecture. Other brands of computers use instructions in addition to load
`and store to transfer data. An architecture with such alternatives is the Intel
`80x86, described in section 3.12.
`
`Elaboration: The offset plus base register addressing is an excellent match to struc(cid:173)
`tures as well, since the register can point to the beginning of the structure and the off(cid:173)
`set can select the desired element. We'll see such an example in section 3.10.
`The register in the data transfer instructions was originally invented to hold an index
`of an array with the offset used for the starting address of an array. Thus the base reg(cid:173)
`ister is also called the index register. Today's memories are much larger and the soft(cid:173)
`ware model of data allocation is more sophisticated, so the base address of the array
`is normally passed in a register since it won 't fit in the offset, as we shall see .
`
`INTEL - 1012
`
`

`

`116
`
`Chapter 3
`
`Instructions: Language of the Machine
`
`3.4 Representing Instructions in the Computer
`
`117
`
`F
`
`Example
`
`W:ti .. l&
`$s0 , $51.
`HO . $tl.
`Memory[O].
`Memory[4] .. . . .
`Memory[4294967292]
`
`32 registers
`
`230 memory
`words
`
`MIPS operands
`
`Comments
`
`Fast locations for data. In MIPS, data must be in registers to perform arithmetic.
`
`Accessed only by data transfer instructions in MIPS. MIPS uses byte addresses, so
`sequential words differ by 4. Memory holds data structures, such as arrays, and spilled
`registers.
`
`MIPS assembly language
`
`Arithmetic
`
`!MUMCJHfOM!!ll.LL
`-
`add
`subtract
`load word
`store word
`
`Data transfer
`
`Example
`
`Meaning
`$sl = $s2 + $ s3
`add $sl, $s2 ,$ s3
`three operands; data in registers
`$sl = $s2 - $s3
`three operands; data in registers
`sub $sl , $s2 . $s3
`$s1 = Memory[$ s2 + 100] Data from memory to register
`l w $s1 , 100($s2)
`$ s1. 100( $s2) Memory[$ s2 + 100] = $s1 Data from register to memory
`SW
`
`Comments
`
`FIGURE 3.4 MIPS architecture revealed through section 3.3. Highlighted portions show MIPS assembly language
`structures introduced in section 3.3.
`
`II Representing Instructions in the Computer
`
`We are now ready to explain the difference between the way humans instruct
`machines and the way machines see instructions. But first, let's quickly
`review how a machine represents numbers.
`Humans are taught to think in base 10, but numbers may be represented in
`any base. For example, 123 base 10 = 1111011 base 2.
`Numbers are kept in computer hardware as a series of high and low elec(cid:173)
`tronic signals, and so they are considered base 2 numbers. (Just as base 10 num(cid:173)
`bers are called decimal numbers, base 2 numbers are called binary numbers.) A
`single digit of a binary number is thus the "atom" of computing, since all in(cid:173)
`formation is composed of binary digits or bits. This fundamental building
`block can be one of two values, which can be thought of as several alternatives:
`high or low, on or off, true or false, or 1 or 0.
`Instructions are also kept in the computer as a series of high and low elec(cid:173)
`tronic signals and may be represented as numbers. In fact, each piece of an in(cid:173)
`struction can be considered as an individual number, and placing these
`numbers side by side forms the instruction.
`Since registers are part of almost all instructions, there must be a convention
`to map register names into numbers. In MIPS assembly language, registers $ s 0
`to $ s 7 map onto registers 16 to 23, and registers HO to H 7 map onto registers
`8 to 15. Hence $ s O means register 16, $ s 1 means register 17, $ s 2 means regis(cid:173)
`ter 18, .. . , $ t O means reg