1、1,Chapter 2. Instruction: Language of the Computer,2,Five Basic Components,Memory,Processor,Input,Output,Since 1946 all computers have had 5 components!,3,A Translation Hierarchy,High Level Language (HLL) programs first compiled (possibly into assembly), then linked and finally loaded into main memo
2、ry.,4,Machine Language v.s. Assembly Language,In C, we can havea = b+c+d; The MIPS assembly code will look like this:add a, b, cadd a, a, dwhere a, b, c and d are registers The MIPS machine language will look like:000000 00010 00011 00001 00000 100000000000 00001 00100 00001 00000 100000 Comparison
3、The high level language is most efficient and readable The assembly language is less efficient yet readable The machine language directly corresponds to the assembly language, but not readable,5,High Level Language Operators/Operands,Consider C or C+Operators: +, -, *, /, % (mod); (7/4 equals 1, 7%4
4、 equals 3)Operands: Variables: fahr, celsius Constants: 0, 1000, -17, 15.4In most High Level Languages, variables declared and given a type int fahr, celsius; int a, b, c, d, e;,6,Assembly Operators/Instructions,MIPS Assembly Syntax is rigid: for arithmetic operations, 3 variables Why? Directly corr
5、esponds to the machine language and makes hardware simple via regularity Consider the following C statement: a = b + c + d - e; It will be executed as multiple instructions add a, b, c # a = sum of b & c add a, a, d # a = sum of b,c,d sub a, a, e # a = b+c+d-e The right of # is a comment terminated
6、by end of the line. Applies only to current line.,7,Compilation,How to turn the notation that programmers prefer into notation computer understands? Program to translate C statements into Assembly Language instructions; called a compiler Example: compile by hand this C code: a = b + c; d = a - e; Ea
7、sy:add a, b, c sub d, a, e Compile an entire program of 10,000 lines of C code by hand? Big Idea: compiler translates notation from one level of computing abstraction to lower level,8,Compilation 2,Example: compile by hand this C code: f = (g + h) - (i + j); First sum of g and h. Where to put result
8、? add f, g, h # f contains g+h Now sum of i and j. Where to put result? Compiler creates temporary variable to hold sum: t1 add t1, i, j # t1 contains i+j Finally produce difference sub f, f, t1 # f = (g+h)-(i+j),9,Compilation - Summary,C statement (5 operands, 3 operators): f = (g + h) - (i + j); B
9、ecomes 3 assembly instructions (6 unique operands, 3 operators): add f,g,h # f contains g+h add t1,i,j # t1 contains i+j sub f,f,t1 # f=(g+h)-(i+j) In general, each line of C produces many assembly instructions Why people program in C vs. Assembly?,10,Assembly Design: Key Concepts,Assembly language
10、is essentially directly supported in hardware, therefore . It is kept very simple! Limit on the type of operands Limit on the set operations that can be done to absolute minimum. if an operation can be decomposed into a simpler operation, dont include it.,11,MIPS R3000 Instruction Set Architecture (
11、Summary),Instruction Categories Load/Store Computational Jump and Branch Floating Point (coprocessor),3 Instruction Formats: all 32 bits wide,I:,R:,J:,Different Instruction Sets,Compute C = A + B under different instruction sets:,Stack,Accumulator,Push A,Load A,lw R1,A,Push B,Add B,lw R2,B,Add,Store
12、 C,add R3,R1,R2,Pop C,sw C,R3,MIPS,13,Assembly Variables: Registers (1/4),Unlike HLL, assembly cannot use variables Why not? Keep Hardware Simple Assembly Operands are registers limited number of special locations built directly into the hardware operations can only be performed on these! Benefit: S
13、ince registers are directly in hardware, they are very fast Registers are not what we normally call “memory”,14,Assembly Variables: Registers (2/4),32 registers in MIPS Why 32? Smaller is faster Each register can be referred to by number or name Number references: $0, $1, $2, $30, $31 Each MIPS regi
14、ster is 32 bits wide Groups of 32 bits called a word in MIPS Drawback: Since registers are in hardware, there are a predetermined number of them Solution: MIPS code must be very carefully put together to efficiently use registers,15,Assembly Variables: Registers (3/4),By convention, each register al
15、so has a name to make it easier to code For now: $16 - $23 $s0 - $s7 (correspond to C variables) $8 - $15 $t0 - $t7 (correspond to temporary variables) In general, use register names to make your code more readable,16,Comments in Assembly,Another way to make your code more readable: comments! Hash (
16、#) is used for MIPS comments anything from hash mark to end of line is a comment and will be ignored Note: Different from C. C comments have format /* comment */ , so they can span many lines,17,Addition and Subtraction (1/4),Syntax of Instructions: add a, b, c where: add: operation by name a: opera
17、nd getting result (destination) b: 1st operand for operation (source1) c: 2nd operand for operation (source2) Syntax is rigid: 1 operator, 3 operands Why? Keep Hardware simple via regularity,18,Addition and Subtraction (2/4),Addition in Assembly Example (in MIPS): add $s0, $s1, $s2 Equivalent to (in
18、 C): a = b + c where registers $s0, $s1, $s2 are associated with variables a, b, c Subtraction in Assembly Example (in MIPS): sub $s3, $s4, $s5 Equivalent to (in C): d = e - f where registers $s3, $s4, $s5 are associated with variables d, e, f,19,Addition and Subtraction (3/4),How to do the followin
19、g C statement? a = b + c + d - e; Break it into multiple instructions: add $s0, $s1, $s2 # a = b + c add $s0, $s0, $s3 # a = a + d sub $s0, $s0, $s4 # a = a - e,20,Immediates,Immediates are numerical constants. They appear often in code, so there are special instructions for them. Add Immediate: add
20、i $s0, $s1, 10 (in MIPS) f = g + 10 (in C) where registers $s0, $s1 are associated with variables f, g Syntax similar to add instruction, except that last argument is a number instead of a register.,21,Register Zero,One particular immediate, the number zero (0), appears very often in code. So we def
21、ine register zero ($0 or $zero) to always have the value 0. This is defined in hardware, so an instruction like addi $0, $0, 5will not do anything. Use this register, its very handy!,22,Assembly Operands: Memory,C variables map onto registers; what about large data structures like arrays? 1 of 5 com
22、ponents of a computer: memory contains such data structures But MIPS arithmetic instructions only operate on registers, never directly on memory. Data transfer instructions transfer data between registers and memory: Memory to register Register to memory,23,MIPS Addressing Formats (Summary),How memo
23、ry can be addressed in MIPS,24,Data Transfer: Memory to Reg (1/4),To transfer a word of data, we need to specify two things: Register: specify this by number (0 - 31) Memory address: more difficult Think of memory as a single one-dimensional array, so we can address it simply by supplying a pointer
24、to a memory address. Other times, we want to be able to offset from this pointer.,25,Data Transfer: Memory to Reg (2/4),To specify a memory address to copy from, specify two things: A register which contains a pointer to memory A numerical offset (in bytes) The desired memory address is the sum of t
25、hese two values. Example: 8($t0) specifies the memory address pointed to by the value in $t0, plus 8 bytes,26,Data Transfer: Memory to Reg (3/4),Load Instruction Syntax: lw a, 100(b) where lw operation (instruction) name a register that will receive value 100 numerical offset in bytes b register con
26、taining pointer to memory Instruction Name: lw (meaning Load Word, so 32 bits or one word are loaded at a time),27,Data Transfer: Memory to Reg (4/4),Example: lw $t0, 12($s0) This instruction will take the pointer in $s0, add 12 bytes to it, and then load the value from the memory pointed to by this
27、 calculated sum into register $t0 Notes: $s0 is called the base register 12 is called the offset offset is generally used in accessing elements of array or structure: base register points to beginning of array or structure,28,Data Transfer: Reg to Memory,Also want to store value from a register into
28、 memory Store instruction syntax is identical to Load instruction syntax Instruction Name: sw (meaning Store Word, so 32 bits or one word are loaded at a time),Example: sw $t0, 12($s0) This instruction will take the pointer in $s0, add 12 bytes to it, and then store the value from register $t0 into
29、the memory address pointed to by the calculated sum,29,Pointers vs. Values,Key Concept: A register can hold any 32-bit value. That value can be a (signed) int, an unsigned int, a pointer (memory address), etc. If you write lw $t2, 0($t0) then, $t0 better contain a pointer What is this for: add $t2,$
30、t1,$t0,30,Addressing: Byte vs. word,Every word in memory has an address, similar to an index in an array Early computers numbered words like C numbers elements of an array: Memory0, Memory1, Memory2, ,Computers needed to access 8-bit bytes as well as words (4 bytes/word) Today machines address memor
31、y as bytes, hence word addresses differ by 4 Memory0, Memory4, Memory8,31,Compilation with Memory,What offset in lw to select A8 in C?4x8=32 to select A8: byte vs. word Compile by hand using registers: g = h + A8;g: $s1, h: $s2, $s3: base address of A 1st transfer from memory to register:lw $t0, 32(
32、$s3) # $t0 gets A8 Add 32 to $s3 to select A8, put into $t0 Next add it to h and place in g add $s1, $s2, $t0 # $s1 = h + A8,32,Notes about Memory,Pitfall: Forgetting that sequential word addresses in machines with byte addressing do not differ by 1. Many an assembly language programmer has toiled o
33、ver errors made by assuming that the address of the next word can be found by incrementing the address in a register by 1 instead of by the word size in bytes. So remember that for both lw and sw, the sum of the base address and the offset must be a multiple of 4 (to be word aligned),33,More Notes a
34、bout Memory: Alignment,MIPS requires that all words start at addresses that are multiples of 4 bytes,Called Alignment: objects must fall on address that is multiple of their size.,34,Role of Registers vs. Memory,What if more variables than registers? Compiler tries to keep most frequently used varia
35、ble in registers Writing less frequently used to memory: spilling Why not keep all variables in memory? Smaller is faster: registers are faster than memory Registers more versatile: MIPS arithmetic instructions can read 2, operate on them, and write 1 per instruction MIPS data transfer only read or
36、write 1 operand per instruction, and no operation,35,So Far.,All instructions have allowed us to manipulate data. So weve built a calculator. To build a computer, we need ability to make decisions,36,C Decisions: if Statements,2 kinds of if statements in C if (condition) clause if (condition) clause
37、1 else clause2 Rearrange 2nd if into following: if (condition) goto L1; clause2; go to L2; L1: clause1;L2: Not as elegant as if - else, but same meaning,37,MIPS Decision Instructions,Decision instruction in MIPS: beq a, b, L beq is Branch if (registers are) equal Same meaning as (using C): if (a = b
38、) goto L Complementary MIPS decision instruction bne a, b, L bne is Branch if (registers are) not equal Same meaning as (using C): if (a!=b) goto L1 Called conditional branches,38,MIPS Goto Instruction,In addition to conditional branches, MIPS has an unconditional branch: j label Called a Jump Instr
39、uction: jump (or branch) directly to the given label without needing to satisfy any condition Same meaning as (using C): goto label Technically, its the same as: beq $0, $0, label since it always satisfies the condition. But j has a longer address field (26 bits) while beg has a shorter address fiel
40、d (16 bits),39,Compiling C if into MIPS (1/2),Compile by handif (i = j)f = g+h;else f = g-h;Use this mapping: f: $s0, g: $s1, h: $s2, i: $s3, j: $s4,40,Compiling C if into MIPS (2/2),Final compiled MIPS code:beq $s3, $s4, True # branch i=j sub $s0, $s1, $s2 # f=g-h(false) j Fin # go to Fin True:add
41、$s0,$s1,$s2 # f=g+h (true) Fin:Note: Compilers automatically create labels to handle decisions (branches) appropriately. Generally not found in HLL code.,41,Instruction Support for Functions,. sum(a,b);. /* a, b: $s0,$s1 */ int sum(int x, int y) return x+y; address 1000 add $a0,$s0,$zero # x = a 100
42、4 add $a1,$s1,$zero # y = b 1008 addi $ra,$zero,1016 #$ra=1016 1012 j sum #jump to sum 1016 .2000 sum: add $v0,$a0,$a1 2004 jr $ra # new instruction,C,M I P S,42,Instruction Support for Functions,Single instruction to jump and save return address: jump and link (jal) Before: 1008 addi $ra,$zero,1016
43、 #$ra=1016 1012 j sum #go to sum After: 1012 jal sum # $ra=1016,go to sum Why have a jal? Make the common case fast: functions are very common.,43,Instruction Support for Functions,Syntax for jr (jump register): jr register Instead of providing a label to jump to, the jr instruction provides a regis
44、ter which contains an address to jump to. Very useful for function calls: jal stores return address in register ($ra) jr jumps back to that address,44,Nested Procedures,int sumSquare(int x, int y) return mult(x,x)+ y; Routine called sumSquare; now sumSquare is calling mult. So theres a value in $ra
45、that sumSquare wants to jump back to, but this will be overwritten by the call to mult. Need to save sumSquare return address before call to mult.,45,Nested Procedures,In general, may need to save some other info in addition to $ra. When a C program is run, there are 3 important memory areas allocat
46、ed: Static: Variables declared once per program, cease to exist only after execution completes Heap: Variables declared dynamically Stack: Space to be used by procedure during execution; this is where we can save register values,46,C memory Allocation,0,Address,47,0,Run-Time Memory Allocation in Exe
47、cutable Programs,Program instructions,Variables allocated once per program (global, C static),Explicitly allocated space, (C malloc()library proc),global pointer $gp,0,Local data in functions, stack frames,48,Using the Stack,So we have a register $sp which always points to the last used space in the
48、 stack. To use stack, we decrement this pointer by the amount of space we need and then fill it with info. So, how do we compile this? int sumSquare(int x, int y) return mult(x,x)+ y;,49,Using the Stack (2/2),Compile by hand sumSquare:addi $sp, $sp, -8 #space on stacksw $ra, 4($sp) #save ret addrsw
49、$a1, 0($sp) # save y,add $a1, $a0, $zero # mult(x,x)jal mult # call mult,lw $a1, 0($sp) # restore yadd $v0, $v0, $a1 # mult()+ ylw $ra, 4($sp) # get ret addraddi $sp, $sp, 8 # restore stackjr $ra,50,Steps for Making a Procedure Call,1) Save necessary values onto stack. 2) Assign argument(s), if any.
50、 3) jal call 4) Restore values from stack.,51,Rules for Procedures,Called with a jal instruction, returns with a jr $ra Accepts up to 4 arguments in $a0, $a1, $a2 and $a3 Return value is always in $v0 (and if necessary in $v1) Must follow register conventions (even in functions that only you will call)! So what are they? Return address $ra Arguments $a0, $a1, $a2, $a3 Return value $v0, $v1 Local variables $s0, $s1, , $s7,
