Dept. Electronics Engineering, DEE 1050 Computer .

Dept. Electronics Engineering, National Chiao Tung UniversityDEE 1050 Computer OrganizationLecture 3 Instructions: Language of theComputerDr. Tian-Sheuan Changtschang@twins.ee.nctu.edu.twDept. Electronics EngineeringNational Chiao-Tung University

OutlineInstitute of Electronics, National Chiao Tung University Part I. Introduction Part II. Case study with MIPS instructions Part III. Tool chainDEE 1050 Lecture 2: Instructions1

OutlineInstitute of Electronics, National Chiao Tung University OperationsOperandsControl flowMIPS addressing modeDEE 1050 Lecture 2: Instructions2

IntroductionInstitute of Electronics, National Chiao Tung University Computer language– Words: instructions– Vocabulary: instruction set– Similar for all, like regional dialect ? Design goal of computer language– To find a language that makes it easy to build thehardware and the compiler while maximizingperformance and minimizing cost Reading list– COD3E: ch. 2DEE 1050 Lecture 2: Instructions3

Instructions: Difference with HLL Language of the MachineInstitute of Electronics, National Chiao Tung University– More primitive than higher level languagese.g., no sophisticated control flow– Very restrictivee.g., MIPS Arithmetic Instructions We’ll be working with the MIPS instruction set architecture– similar to other architectures developed since the 1980's– Almost 100 million MIPS processors manufactured in 2002– used by NEC, Nintendo, Cisco, Silicon Graphics, Sony, 14001300120011001000900800OtherSPARCHitachi SHPowerPCMotorola 68KMIPSIA-32ARM700600500400300200100DEE 1050 Lecture 2: Instructions019981999200020012002

How to Design the Instructions? OperationsInstitute of Electronics, National Chiao Tung University– Arithmetic– Logical– Datapath Operands– Datapath Control flow– Decision control– Procedures calls– ControlDEE 1050 Lecture 2: Instructionsint add5 (int a){int tmp a 5;return tmp;}void main (){int a 7;int c;if (a 7)c add5(a);}5

Operations: MIPS arithmeticInstitute of Electronics, National Chiao Tung University Each arithmetic instructions performs only one operationand have 3 operands Operand order is fixed (destination first)add a, b, c# a b ccommentsOne operationExact threeoperands“The natural number of operands for an operation likeaddition is three requiring every instruction to haveexactly three operands, no more and no less, conformsto the philosophy of keeping the hardware simple”DEE 1050 Lecture 2: Instructions6

MIPS arithmeticInstitute of Electronics, National Chiao Tung University Design Principle 1: simplicity favors regularity. Of course this complicates some things.C code:a b c d;MIPS code:add a, b, cadd a, a, dQ. Will variable no. of operands be faster?how about four or more operands in one instructionsDEE 1050 Lecture 2: Instructions

MIPS Logical Operations (Section 2.5) Why logical operationsInstitute of Electronics, National Chiao Tung University– Useful to operate on fields of bit or individual bits Q. Can some multiply by 2i ? Divide by 2i ? Invert?Q. Why “NOT” maps to “nor”?– A NOR 0 NOT (A OR 0) NOT (A) Q. Why not “nori” (nor immediate)?– Constant are rare for for NORoperationsc operatorsmipsshift leftshift rightbit-by-bit andbit-by-bit orbit-by-bit not & sllsrland, andior, orinorDEE 1050 Lecture 2: Instructions8

Institute of Electronics, National Chiao Tung University Intended to be blank9DEE 1050 Lecture 2: Instructions

Operands of the Computer Hardware (Section2.3)Institute of Electronics, National Chiao Tung University Difference with HLL like C– Limited number, why ?– Operands are restricted to hardware-built registers– Registers are primitive and visible to programmer MIPS operands– Operands must be registers, only 32 registersprovided– Each register contains 32 bits– Why 32? Design Principle 2: smaller is faster.DEE 1050 Lecture 2: Instructions10

Operand TypeInstitute of Electronics, National Chiao Tung University 3 Types– Register operands All arithmetic operations are in the register operands– Memory operands Array or structure Only load/store can access memory– Constant or immediate operands Small value will be in the instruction Large value will be stored separatelyDEE 1050 Lecture 2: Instructions11

Register Operand ExampleInstitute of Electronics, National Chiao Tung University Register representation– **, in MIPS s0, s1. Registers corresponding to the variables of C programs t0, t1 temporary registers need to compile the program– (this might be different in other assembly language)Translate the following C program into MIPSf (g h) – ( i j);Assume f, g, h, i, j uses s0, . s4Add t0, s1, s2Add t1, s3, s4Sub s0, t0 - t1DEE 1050 Lecture 2: Instructions12

HW/SW IF: How Compiler Use RegistersInstitute of Electronics, National Chiao Tung University Problem: more variables than available registers Solution– Keep the most frequently used variables in registers– Place the rest in memory (called spilling registers), useload and store to move variables between registers andmemory– Why? Register is faster but its size is small Compiler must use register efficientlyDEE 1050 Lecture 2: Instructions13

Memory Operands: Array and StructuresInstitute of Electronics, National Chiao Tung University Data are stored in memory “data transfer instructions”– Transfer data between memory and registers– Load lw: move data from memory to a register– Store st: move data from a register to memoryDEE 1050 Lecture 2: Instructions14

Array ExampleInstitute of Electronics, National Chiao Tung University Load format– lw register names, const offset(base register)g h a[8]offsetassume g, h s1, s2base address s3lw t0, 8( s3) #lw: load wordadd s1, 2, t0BaseaddressIf a[12] h a[8]Add one more instructionssw 12[ s3], s1DEE 1050 Lecture 2: Instructions15

Memory and Data SizesInstitute of Electronics, National Chiao Tung UniversitySo far, we’ve only talked about uniform data sizes. Actualdata come in many different sizes: Single bits: (“boolean” values, true or false) Bytes (8 bits): Characters (ASCII), very small integers Halfwords (16 bits): Characters (Unicode), short integers Words (32 bits): Long integers, floating-point (FP)numbers Double-words (64 bits): Very long integers, doubleprecision FP Quad-words (128 bits): Quad-precision floating-pointnumbersDEE 1050 Lecture 2: Instructions16

Different Data SizesInstitute of Electronics, National Chiao Tung UniversityHow do we handle different data sizes? Pick one size to be the unit stored in a single address Store larger datum in a set of contiguous memorylocations Store smaller datum in one location; use shift & mask opsToday, almost all machines (including MIPS) are “byteaddressable” – each addressable location in memoryholds 8 bits.DEE 1050 Lecture 2: Instructions17

Memory Organization – Byte AddressingInstitute of Electronics, National Chiao Tung University Viewed as a large, single-dimension array, withan address. A memory address is an index into the array "Byte addressing" means that the index pointsto a byte of memory.0123456.DEE 1050 Lecture 2: Instructions8 bits of data8 bits of data8 bits of data8 bits of data8 bits of data8 bits of data8 bits of data

Memory OrganizationInstitute of Electronics, National Chiao Tung University Bytes are nice, but most data items use larger "words" For MIPS, a word is 32 bits or 4 bytes.04812.32 bits of data32 bits of data32 bits of dataRegisters hold 32 bits of data32 bits of data 232 bytes with byte addresses from 0 to 232-1 230 words with byte addresses 0, 4, 8, . 232-4 Words are alignedi.e., what are the least 2 significant bits of a wordaddress? To select the byte Alignment restriction in MIPS– Words must start at addresses that are multiples of 4DEE 1050 Lecture 2: Instructions

Array Example for Real MIPS Memory AddressInstitute of Electronics, National Chiao Tung University Code for byte addressable memoryOriginala[12] h a[8]Updateda[12] h a[8]assume g, h s1, s2base address s3assume g, h s1, s2base address s3, word datalw t0, 8( s3)add s1, 2, t0sw 12( s3), s1lw t0, 32( s3)add s1, 2, t0sw 48( s3), s1Remember arithmetic operands are registers, not memory!Can’t write: add 48( s3), s2, 32( s3)DEE 1050 Lecture 2: Instructions20

Byte-Order (“Endianness”)Institute of Electronics, National Chiao Tung UniversityFor a multi-byte datum, which part goes in which byte? If 1 contains 1,000,000 (F4240H) and we store it intoaddress 80: On a “big-endian” machine, the “big” end goes intoaddress 80 7900800F814282408384 On a “little-endian” machine, it’s the other way around DEE 1050 Lecture 2: Instructions7940420F008081828384 21

Big-Endian vs. Little-EndianInstitute of Electronics, National Chiao Tung University Big-endian machines: MIPS, Sparc, 68000 Little-endian machines: most Intel processors,Alpha, VAX– No real reason one is better than the other – Compatibility problems transferring multi-byte databetween big-endian and little-endian machines –CAREFUL! Bi-endian machines: ARM, User’s choiceDEE 1050 Lecture 2: Instructions22

Registers Operands vs. Memory OperandsInstitute of Electronics, National Chiao Tung University Arithmetic instructions operands must beregisters,– only 32 registers provided– Compiler associates variables with registers What about programs with lots of variables ? Likearray and structures– Data structures are kept in memory– Data transfer instructions Load: lw copy data from memory to registers Store: sw copy data from registers to memory How: instruction supplies the memory addressDEE 1050 Lecture 2: Instructions

Constant or Immediate Operands Institute of Electronics, National Chiao Tung University Small constants are used quite frequently ( 50% of operands inSPEC2000 benchmark)e.g.,A A 5;B B 1;C C - 18;Solutions? Why not?– put 'constants' in memory and load them.– create hard-wired registers (like zero) for constants like one. MIPS Instructions:addi s1, s1, 5slti s2, s1, 10andi s1, s1, 6ori s1, s1, 4 Design Principle 3: Make the common case fast.Q: why only “addi” and no “subi”– Negative constantsDEE 1050 Lecture 2: Instructions

How about larger constants?Institute of Electronics, National Chiao Tung University We'd like to be able to load a 32 bit constant into a register Must use two instructions, new "load upper immediate"instructionlui t0, 1010101010101010filled with zeros10101010101010100000000000000000 Then must get the lower order bits right, i.e.,ori t0, t0, 010101010101010DEE 1050 Lecture 2: Instructions

So farMIPS operandsInstitute of Electronics, National Chiao Tung UniversityName32 registers230ExampleComments s0- s7, t0- t9,Fast locations for data. In MIPS, data must be in registers to perform zero, a0- a3, v0- arithmetic. MIPS register zero always equals 0. gp (28) is the global v1, gp, fp, sp, ra pointer, sp(29) is the stack pointer, fp (30) is the frame pointer, and ra(31) is the return address.Memory [0],Accessed only by data transfer instructions. MIPS uses byte addresses, somemory words Memory [4], ,sequential words differ by 4. Memory holds data structures, such as arrays,Memory[42949672920 and spilled register, such as those saved on procedure calls.MIPS assembly languageCategoryArithmeticData transferConditional branchUnconditional jumpInstructionaddsubtractload wordstore wordbranch on equalbranch on notequalset on less thanExampleadd s1, s2, s3sub s1, s2, s3lw s1,100 ( s2)sw s1,100 ( s2)beq s1, s2, Lbne s1, s2, LMeaning s1 s2 s3 s1 s2 - s3&s1 Memory [ s2 100]Memory [ s2 100] s1if ( s1 s2) go to Lif ( s1 ! s2) go to LCommentsThree operands; data in registersThree operands; data in registersData from memory to registerData from register to memoryEqual test and branchNot equal test and branchslt s1, s2, s3Compare less than: for beq, bnejumpjump registerjump and linkjjrjalif ( s2 s3) s1 1; else s1 0go to 10000go to ra ra PC 4; go to 1000DEE 1050 Lecture 2: Instructions2500 ra2500jump to target addressFor switch, procedure returnFor procedure call26