Functions in Computing
Fundamentals of functions in computing, covering topics such as return types, function calls, nested function calls, and more. Learn about the rules and best practices for utilizing functions effectively in programming. See examples and explanations regarding returning values, function expressions, and nested calls.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 2 Instructions: Language of the Computer
Instruction Set The repertoire of instructions of a computer Different computers have different instruction sets But with many aspects in common Early computers had very simple instruction sets Simplified implementation Many modern computers also have simple instruction sets Chapter 2 Instructions: Language of the Computer 2
Instruction Set Architecture Instruction Set Architecture: 1. abtraction that hides the low-level details of a processor from the user 2. the interface between the hardware and software 3. everything you need to know to use the processor: instruction set instruction representations addressing modes etc Families of processors are defined by their ISA: Sun Sparc Intel IA-32 MIPS IBM 360 Motorola/IBM PowerPC CSCE 212 3
Instruction Set Architecture CSCE 212 4
RISC vs. CISC Design philosophies for ISAs: RISC vs. CISC CISC = Complex Instruction Set Computer RISC = Reduced Instruction Set Computer Tradeoff: Execution time = instructions per program x cycles per instruction x seconds per cycle RISC: Small instruction set Easier for compilers Limit each instruction to (at most): three register accesses, one memory access, one ALU operation => facilitates parallel instruction execution (ILP) Load-store machine: minimize off-chip access CSCE 212 5
The MIPS Instruction Set Used as the example throughout the book Stanford MIPS commercialized by MIPS Technologies (www.mips.com) Large share of embedded core market Applications in consumer electronics, network/storage equipment, cameras, printers, Typical of many modern ISAs See MIPS Reference Data tear-out card, and Appendixes B and E Chapter 2 Instructions: Language of the Computer 6
MIPS ISA 100 million MIPS processors manufactured in 2002 MIPS processors used in: SGI workstations Series2 TiVo Windows CE devices Cisco/Linksys routers Nintendo 64 Sony Playstation 1, PS2 (Emotion), PSP Cable boxes John L. Hennessy (Stanford, 1981) 1984: MIPS Computer Systems R2000 (1985), R3000 (1988), R4000 (64-bit, 1991) MIPS Technologies aquired by SGI and later by Imagination Technology Transition to licensed IP: MIPS32 and MIPS64 (1999) Heavyweight embedded processor CSCE 212 7
Arithmetic Operations Add and subtract, three operands Two sources and one destination add a, b, c # a gets b + c All arithmetic operations have this form Design Principle 1: Simplicity favours regularity Regularity makes implementation simpler Simplicity enables higher performance at lower cost Chapter 2 Instructions: Language of the Computer 8
Arithmetic Example C code: f = (g + h) - (i + j); Compiled MIPS code: add t0, g, h # temp t0 = g + h add t1, i, j # temp t1 = i + j sub f, t0, t1 # f = t0 - t1 Chapter 2 Instructions: Language of the Computer 9
Register Operands Arithmetic instructions use register operands MIPS has a 32 32-bit register file Use for frequently accessed data Numbered 0 to 31 32-bit data called a word Assembler names $t0, $t1, , $t9 for temporary values $s0, $s1, , $s7 for saved variables Design Principle 2: Smaller is faster c.f. main memory: millions of locations Chapter 2 Instructions: Language of the Computer 10
MIPS Registers 32 x 32-bit general purpose integer registers Some have special purposes These are the only registers the programmer can directly use $0 => constant 0 $1 => $at (reserved for assembler) $2,$3 => $v0,$v1 (expression evaluation and results of a function) $4-$7 => $a0-$a3 (arguments 1-4) $8-$15 => $t0-$t7 (temporary values) Used when evaluating expressions that contain more than two operands (partial solutions) Not preserved across function calls $16-$23 => $s0->$s7 (for local variables, preserved across function calls) $24, $25 => $t8, $t9 (more temps) $26,$27 => $k0, $k1 (reserved for OS kernel) $28 => $gp (pointer to global area) $29 => $sp (stack pointer) $30 => $fp (frame pointer) $31 => $ra (return address, for branch-and-links) Program counter (PC) contains address of next instruction to be executed CSCE 212 11
Register Operand Example C code: f = (g + h) - (i + j); f, , j in $s0, , $s4 Compiled MIPS code: add $t0, $s1, $s2 add $t1, $s3, $s4 sub $s0, $t0, $t1 Chapter 2 Instructions: Language of the Computer 12
Memory Operands Main memory used for composite data Arrays, structures, dynamic data To apply arithmetic operations Load values from memory into registers Store result from register to memory Memory is byte addressed Each address identifies an 8-bit byte Words are aligned in memory Address must be a multiple of 4 MIPS is Little Endian Least-significant byte at least address of a word c.f. Big Endian: most-significant byte at least address Chapter 2 Instructions: Language of the Computer 13
Memory Operand Example 1 C code: g = h + A[8]; g in $s1, h in $s2, base address of A in $s3 Compiled MIPS code: Index 8 requires offset of 32 4 bytes per word lw $t0, 32($s3) # load word add $s1, $s2, $t0 offset base register Chapter 2 Instructions: Language of the Computer 14
Memory Operand Example 2 C code: A[12] = h + A[8]; h in $s2, base address of A in $s3 Compiled MIPS code: Index 8 requires offset of 32 lw $t0, 32($s3) # load word add $t0, $s2, $t0 sw $t0, 48($s3) # store word Chapter 2 Instructions: Language of the Computer 15
Registers vs. Memory Registers are faster to access than memory Operating on memory data requires loads and stores More instructions to be executed Compiler must use registers for variables as much as possible Only spill to memory for less frequently used variables Register optimization is important! Chapter 2 Instructions: Language of the Computer 16
Immediate Operands Constant data specified in an instruction addi $s3, $s3, 4 No subtract immediate instruction Just use a negative constant addi $s2, $s1, -1 Design Principle 3: Make the common case fast Small constants are common Immediate operand avoids a load instruction Chapter 2 Instructions: Language of the Computer 17
The Constant Zero MIPS register 0 ($zero) is the constant 0 Cannot be overwritten Useful for common operations E.g., move between registers add $t2, $s1, $zero Chapter 2 Instructions: Language of the Computer 18
Representing Instructions Instructions are encoded in binary Called machine code MIPS instructions Encoded as 32-bit instruction words Small number of formats encoding operation code (opcode), register numbers, Regularity! Register numbers $t0 $t7 are reg s 8 15 $t8 $t9 are reg s 24 25 $s0 $s7 are reg s 16 23 Chapter 2 Instructions: Language of the Computer 19
MIPS R-format Instructions op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits Instruction fields op: operation code (opcode) rs: first source register number rt: second source register number rd: destination register number shamt: shift amount (00000 for now) funct: function code (extends opcode) Chapter 2 Instructions: Language of the Computer 20
R-format Example op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits add $t0, $s1, $s2 special $s1 $s2 $t0 0 add 0 17 18 8 0 32 000000 10001 10010 01000 00000 100000 000000100011001001000000001000002 = 0232402016 Chapter 2 Instructions: Language of the Computer 21
Hexadecimal Base 16 Compact representation of bit strings 4 bits per hex digit 0 1 2 3 0000 0001 0010 0011 4 5 6 7 0100 0101 0110 0111 8 9 a b 1000 1001 1010 1011 c d e f 1100 1101 1110 1111 Example: eca8 6420 1110 1100 1010 1000 0110 0100 0010 0000 Chapter 2 Instructions: Language of the Computer 22
MIPS I-format Instructions op rs rt constant or address 6 bits 5 bits 5 bits 16 bits Immediate arithmetic and load/store instructions rt: destination or source register number Constant: 215 to +215 1 Address: offset added to base address in rs Design Principle 4: Good design demands good compromises Different formats complicate decoding, but allow 32-bit instructions uniformly Keep formats as similar as possible Chapter 2 Instructions: Language of the Computer 23
Logical Operations Instructions for bitwise manipulation Operation Shift left Shift right Bitwise AND Bitwise OR Bitwise NOT C << >> & | ~ Java << >>> & | ~ MIPS sll srl and, andi or, ori nor Useful for extracting and inserting groups of bits in a word Chapter 2 Instructions: Language of the Computer 24
Shift Operations op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits shamt: how many positions to shift Shift left logical Shift left and fill with 0 bits sll by i bits multiplies by 2i Shift right logical Shift right and fill with 0 bits srl by i bits divides by 2i (unsigned only) Chapter 2 Instructions: Language of the Computer 25
AND Operations Useful to mask bits in a word Select some bits, clear others to 0 and $t0, $t1, $t2 $t2 0000 0000 0000 0000 0000 1101 1100 0000 $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 0000 0000 0000 0000 0000 1100 0000 0000 Chapter 2 Instructions: Language of the Computer 26
OR Operations Useful to include bits in a word Set some bits to 1, leave others unchanged or $t0, $t1, $t2 $t2 0000 0000 0000 0000 0000 1101 1100 0000 $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 0000 0000 0000 0000 0011 1101 1100 0000 Chapter 2 Instructions: Language of the Computer 27
NOT Operations Useful to invert bits in a word Change 0 to 1, and 1 to 0 MIPS has NOR 3-operand instruction a NOR b == NOT ( a OR b ) nor $t0, $t1, $zero Register 0: always read as zero $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 1111 1111 1111 1111 1100 0011 1111 1111 Chapter 2 Instructions: Language of the Computer 28
Conditional Operations Branch to a labeled instruction if a condition is true Otherwise, continue sequentially beq rs, rt, L1 if (rs == rt) branch to instruction labeled L1; bne rs, rt, L1 if (rs != rt) branch to instruction labeled L1; j L1 unconditional jump to instruction labeled L1 Chapter 2 Instructions: Language of the Computer 29
Compiling If Statements C code: if (i==j) f = g+h; else f = g-h; f, g, in $s0, $s1, Compiled MIPS code: bne $s3, $s4, Else add $s0, $s1, $s2 j Exit Else: sub $s0, $s1, $s2 Exit: Assembler calculates addresses Chapter 2 Instructions: Language of the Computer 30
Compiling Loop Statements C code: while (save[i] == k) i += 1; i in $s3, k in $s5, address of save in $s6 Compiled MIPS code: Loop: sll $t1, $s3, 2 add $t1, $t1, $s6 lw $t0, 0($t1) bne $t0, $s5, Exit addi $s3, $s3, 1 j Loop Exit: Chapter 2 Instructions: Language of the Computer 31
Integer Multiply and Divide mult $2, $3 result in hi (32 bits) and lo (32 bits) mul $2, $3, $4 is psuedo (low 32 bits) madd $2, $3 multiply and accumulate in hi and lo div $2, $3 quotient in lo and reminder in hi div $2, $3, $4 is psuedo (quotient) CSCE 212 32
Complex Arithmetic Example z=(a*b)+(c/d)-(e+f*g); lw $s0,a lw $s1,b mult $s0,$s1 mflo $t0 lw $s0,c lw $s1,d div $s0,$s1 mflo $t1 add $t0,$t0,$t1 lw $s0,e lw $s1,f lw $s2,g mult $s1,$s2 mflo $t1 add $t1,$s0,$t1 sub $t0,$t0,$t1 sw $t0,z CSCE 212 33
If-Statement if ((a>b)&&(c==d)) e=0; else e=f; lw $s0,a lw $s1,b bgt $s0,$s1,next0 b nope next0: lw $s0,c lw $s1,d beq $s0,$s1,yup nope: lw $s0,f sw $s0,e b out yup: xor $s0,$s0,$s0 sw $s0,e out: CSCE 212 34
For Loop for (i=0;i<a;i++) b[i]=i; loop0: loop1: out: lw $s0,a li $s1,0 blt $s1,$s0,loop1 j out sll $s2,$s1,2 sw $s1,b($s2) addi $s1,$s1,1 j loop0 CSCE 212 35
Pre-Test While Loop while (a<b) { a++; } loop0: loop1: out: lw $s0,a lw $s1,b blt $s0,$s1,loop1 b out addi $s0,Ss0,1 sw $s0,a b loop0 CSCE 212 36
Post-Test While Loop do { a++; } while (a<b); loop0: lw $s0,a lw $s1,b addi $s0,$s0,1 sw $s0,a blt $s0,$s1,loop0 CSCE 212 37
Complex Loop for (i=0;i<n;i++) a[i]=b[i]+10; loop: add $6,$5,$2 lw $7,0($6) addi $7,$7,10 # compute b[i]=b[i]+10 add $6,$4,$2 sw $7,0($6) addi $2,$2,4 test: blt $2,$3,loop # loop if test succeeds li $2,$0 lw $3,n sll $3,$3,2 la $4,a la $5,b j test # zero out index register (i) # load iteration limit # multiply by 4 (words) # get address of a (assume < 216) # get address of b (assume < 216) # compute address of b[i] # load b[i] # compute address of a[i] # store into a[i] # increment i CSCE 212 38
Branch Addressing Branch instructions specify Opcode, two registers, target address Most branch targets are near branch Forward or backward op rs rt constant or address 6 bits 5 bits 5 bits 16 bits PC-relative addressing Target address = PC + offset 4 PC already incremented by 4 by this time Chapter 2 Instructions: Language of the Computer 39
Jump Addressing Jump (j and jal) targets could be anywhere in text segment Encode full address in instruction op address 26 bits 6 bits (Pseudo) Direct jump addressing Target address = PC31 28 : (address 4) Chapter 2 Instructions: Language of the Computer 40
Target Addressing Example Loop code from earlier example Assume Loop at location 80000 80000 0 0 19 9 4 0 Loop: sll $t1, $s3, 2 80004 0 9 22 9 0 32 add $t1, $t1, $s6 80008 35 9 8 0 lw $t0, 0($t1) 80012 5 8 21 2 bne $t0, $s5, Exit 80016 8 19 19 1 addi $s3, $s3, 1 80020 2 20000 j Loop 80024 Exit: Chapter 2 Instructions: Language of the Computer 41
Branching Far Away If branch target is too far to encode with 16-bit offset, assembler rewrites the code Example beq $s0,$s1, L1 bne $s0,$s1, L2 j L1 L2: Chapter 2 Instructions: Language of the Computer 42
Addressing Mode Summary Chapter 2 Instructions: Language of the Computer 43
More Conditional Operations Set result to 1 if a condition is true Otherwise, set to 0 slt rd, rs, rt if (rs < rt) rd = 1; else rd = 0; slti rt, rs, constant if (rs < constant) rt = 1; else rt = 0; Use in combination with beq, bne slt $t0, $s1, $s2 # if ($s1 < $s2) bne $t0, $zero, L # branch to L Chapter 2 Instructions: Language of the Computer 44
Branch Instruction Design Why not blt, bge, etc? Hardware for <, , slower than =, Combining with branch involves more work per instruction, requiring a slower clock All instructions penalized! beq and bne are the common case This is a good design compromise Chapter 2 Instructions: Language of the Computer 45
Assembler Pseudoinstructions Most assembler instructions represent machine instructions one-to-one Pseudoinstructions: figments of the assembler s imagination move $t0, $t1 blt $t0, $t1, L slt $at, $t0, $t1 $at (register 1): assembler temporary add $t0, $zero, $t1 bne $at, $zero, L Chapter 2 Instructions: Language of the Computer 46
Pseudoinstructions Some MIPS instructions don t have direct hardware implementations Ex: abs $2, $3 Resolved to: bgez $3, pos sub $2, $0, $3 j out pos: add $2, $0, $3 out: Ex: rol $2, $3, $4 Resolved to: addi $1, $0, 32 sub $1, $1, $4 srlv $1, $3, $1 sllv $2, $3, $4 or $2, $2, $1 CSCE 212 47
I/O I/O is performed with reserved instructions / memory space Performed by the operating system on behalf of user code Use syscall instruction Call code in $v0 and argument in $a0 Return value in $v0 (or $f0) Services: CSCE 212 48
Example .data .asciiz str: the answer = .text li la syscall li la syscall $v0,4 $a0, str $v0,1 $a0,5 CSCE 212 49
Signed vs. Unsigned Signed comparison: slt, slti Unsigned comparison: sltu, sltui Example $s0 = 1111 1111 1111 1111 1111 1111 1111 1111 $s1 = 0000 0000 0000 0000 0000 0000 0000 0001 slt $t0, $s0, $s1 # signed 1 < +1 $t0 = 1 sltu $t0, $s0, $s1 # unsigned +4,294,967,295 > +1 $t0 = 0 Chapter 2 Instructions: Language of the Computer 50
