CS 61C: Great Ideas in Computer Architecture (Machine Structures)

CS 61C: Great Ideas in Computer Architecture (Machine Structures)

CS 61C: Great Ideas in Computer Architecture More MIPS, MIPS Functions Instructor: Justin Hsia 7/02/2013 Summer 2013 -- Lecture #6 1 Review of Last Lecture (1/2) RISC Design Principles Smaller is faster: 32 registers, fewer instructions Keep it simple: rigid syntax, fixed word length MIPS Registers: $s0-$s7, $t0-$t9, $0 Only operands used by instructions No variable types, just raw bits Memory is byte-addressed Watch endianness when dealing with bytes

7/02/2013 Summer 2013 -- Lecture #6 2 Review of Last Lecture (2/2) MIPS Instructions Arithmetic: add, sub, addi,mult,div addu,subu,addiu Data Transfer: lw, sw, lb, sb, lbu Branching: beq, bne, j Bitwise: and,andi,or,ori, nor,xor,xori Shifting: sll,sllv,srl,srlv, sra,srav 7/02/2013

Summer 2013 -- Lecture #6 3 Great Idea #1: Levels of Representation/ Interpretation temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; Higher-Level Language Program (e.g. C) Compiler lw lw sw sw Assembly Language Program (e.g. MIPS) Assembler Machine Language

Program (MIPS) $t0, 0($2) $t1, 4($2) $t1, 0($2) $t0, 4($2) We are here_ 0000 1001 1100 0110 1010 1111 0101 1000 1010 1111 0101 1000 0000 1001 1100 0110 1100 0110 1010 1111 0101 1000 0000 1001 0101 1000 0000 1001 1100 0110 1010 1111 Machine Interpretation Hardware Architecture Description (e.g. block diagrams) Architecture Implementation Logic Circuit Description (Circuit Schematic Diagrams) 7/02/2013

Summer 2013 -- Lecture #6 5 Agenda Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers Bonus: Memory Address Convention Bonus: Register Convention Analogy

7/02/2013 Summer 2013 -- Lecture #6 6 Inequalities in MIPS Inequality tests: <, <=, >, and >= RISC: implement all with 1 additional instruction Set on Less Than (slt) slt dst,src1,src2 Stores 1 in dst if value in src1 < value in src2 and stores 0 in dst otherwise Combine with bne, beq, and $0 7/02/2013 Summer 2013 -- Lecture #6 7

Inequalities in MIPS C Code: MIPS Code: if (a < b) { ... /* then */ } (let a$s0, b$s1) slt $t0,$s0,$s1 # $t0=1 if a=b bne $t0, $0,then # go to then # if $t00 7/02/2013 Summer 2013 -- Lecture #6 8

Inequalities in MIPS C Code: MIPS Code: if (a >= b) { ... /* then */ } (let a$s0, b$s1) slt $t0,$s0,$s1 # $t0=1 if a=b beq $t0, $0,then # go to then # if $t0=0 Try to work out the other two on your own: Swap src1 and src2 Switch beq and bne 7/02/2013

Summer 2013 -- Lecture #6 9 Immediates in Inequalities Three variants of slt: sltu slti dst,src1,src2: unsigned comparison dst,src,imm: compare against constant sltiu dst,src,imm: unsigned comparison against constant Example: addi $s0,$0,-1 slti $t0,$s0,1 sltiu $t1,$s0,1 7/02/2013

# # # # # Summer 2013 -- Lecture #6 $s0=0xFFFFFFFF $t0=1 $t0=1 $t1=0 $t1=0 10 Aside: MIPS Signed vs. Unsigned MIPS terms signed and unsigned appear in 3 different contexts: Signed vs. unsigned bit extension lb lbu Detect vs. dont detect overflow

add, addi, sub, mult, div addu, addiu, subu, multu, divu Signed vs. unsigned comparison 7/02/2013 slt, slti sltu, sltiu Summer 2013 -- Lecture #6 11 Question: What C code properly fills in the following blank? do {i--;} while(_________); Loop: addi $s0,$s0,-1 slti $t0,$s1,2 beq $t0,$0 ,Loop slt $t0,$s1,$s0 bne $t0,$0 ,Loop (A) j 2 || j

(B) j 2 && j (C) j < 2 || j (D) j < 2 && j # # # # # # < < i$s0, j$s1 i = i - 1 $t0 = (j < 2) goto Loop if $t0==0 $t0 = (j < i) goto Loop if $t0!=0

i i i i 12 Agenda Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers

Bonus: Memory Address Convention Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 13 Assembler Pseudo-Instructions Certain C statements are implemented unintuitively in MIPS e.g. assignment (a=b) via addition with 0 MIPS has a set of pseudo-instructions to make programming easier More intuitive to read, but get translated into actual instructions later Example: move dst,src translated into addi dst,src,0 7/02/2013

Summer 2013 -- Lecture #6 14 Assembler Pseudo-Instructions List of pseudo-instructions: http://en.wikipedia.org/wiki/MIPS_architecture#Pseudo_instructions List also includes instruction translation Load Address (la) la dst,label Loads address of specified label into dst Load Immediate (li) li dst,imm Loads 32-bit immediate into dst MARS has more pseudo-instructions (see Help) Dont go overboard: avoid confusing yourself! 7/02/2013

Summer 2013 -- Lecture #6 15 Assembler Register Problem: When breaking up a pseudo-instruction, the assembler may need to use an extra register If it uses a regular register, itll overwrite whatever the program has put into it Solution: Reserve a register ($1 or $at for assembler temporary) that assembler will use to break up pseudo-instructions Since the assembler may use this at any time, its not safe to code with it 7/02/2013 Summer 2013 -- Lecture #6

16 MAL vs. TAL True Assembly Language (TAL) The instructions a computer understands and executes MIPS Assembly Language (MAL) Instructions the assembly programmer can use (includes pseudo-instructions) Each MAL instruction becomes 1 or more TAL instruction TAL MAL 7/02/2013 Summer 2013 -- Lecture #6 17 Agenda

Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 18 Administrivia HW2 due Fri 7/5

HW3 due Sun 7/7 Project 1 posted by Friday, due 7/14 No homework next week (still labs) Special OH this week 7/02/2013 Summer 2013 -- Lecture #6 19 Agenda Inequalities

Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers Bonus: Memory Address Convention Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 20 Six Steps of Calling a Function 1. Put arguments in a place where the function can access them 2. Transfer control to the function 3. The function will acquire any (local) storage resources it needs 4. The function performs its desired task 5. The function puts return value in an accessible place and cleans up

6. Control is returned to you 7/02/2013 Summer 2013 -- Lecture #6 21 MIPS Registers for Function Calls Registers way faster than memory, so use them whenever possible $a0$a3: four argument registers to pass parameters $v0$v1: two value registers to return values $ra: return address register that saves where a function is called from 7/02/2013 Summer 2013 -- Lecture #6 22 MIPS Instructions for Function Calls

Jump and Link (jal) jal label Saves the location of following instruction in register $ra and then jumps to label (function address) Used to invoke a function Jump Register (jr) jr src Unconditional jump to the address specified in src (almost always used with $ra) Used to return from a function 7/02/2013 Summer 2013 -- Lecture #6 23 Instruction Addresses jal puts the address of an instruction in $ra Instructions are stored as data in memory! Recall: Code section More on this next lecture

In MIPS, all instructions are 4 bytes long so each instruction differs in address by 4 Recall: Memory is byte-addressed Labels get converted to instruction addresses 7/02/2013 Summer 2013 -- Lecture #6 24 Program Counter The program counter (PC) is a special register that holds the address of the current instruction being executed This register is inaccessible to the programmer, but accessible to jal jal stores PC+4 into $ra What would happen if we stored PC instead? All branches and jumps (beq, bne, j, jal, jr)

work by storing an address into PC 7/02/2013 Summer 2013 -- Lecture #6 25 Function Call Example ... sum(a,b); ... address (decimal) int sum(int x, int y) { return x+y; } /* a$s0,b$s1 */ C MIPS 1000 addi $a0,$s0,0 # x = a

1004 addi $a1,$s1,0 # y = b 1008 addi $ra,$zero,1016 # $ra=1016 1012 j sum # jump to sum Would we know this before compiling? 1016 ... Otherwise we dont know where we 2000 sum: add came from jr $ra $v0,$a0,$a1 7/02/2013 Summer 2013 -- Lecture 26 2004 jr $ra # #6return Function Call Example

... sum(a,b); ... /* a$s0,b$s1 */ address (decimal) int sum(int x, int y) { return x+y; } 1000 1004 1008 1012 ... addi $a0,$s0,0 addi $a1,$s1,0 jal sum 2000 7/02/2013 2004

sum: add $v0,$a0,$a1 Summer 2013 -- Lecture jr $ra # #6return C MIPS # x = a # y = b # $ra=1012, goto sum 27 Six Steps of Calling a Function 1. Put arguments in a place where the function $a0-$a3 can access them jal 2. Transfer control to the function 3. The function will acquire any (local) storage resources it needs

4. The function performs its desired task 5. The function puts return value in an accessible $v0-$v1 place and cleans up jr 6. Control is returned to you 7/02/2013 Summer 2013 -- Lecture #6 28 Saving and Restoring Registers Why might we need to save registers? Limited number of registers for everyone to use What happens if a function calls another function? ($ra would get overwritten!) Where should we save registers? The Stack $sp (stack pointer) register contains pointer to current bottom (last used space) of stack 7/02/2013

Summer 2013 -- Lecture #6 29 Recall: Memory Layout Address $sp stack Space for saved procedure information heap Dynamically allocated space static data 0 7/02/2013

code Global variables, string literals Program instructions Summer 2013 -- Lecture #6 30 Example: sumSquare int sumSquare(int x, int y) { return mult(x,x)+ y; } What do we need to save? Call to mult will overwrite $ra, so save it Reusing $a1 to pass 2nd argument to mult, but need current value (y) later, so save $a1 To save something to the Stack, move $sp down the required amount and fill the created space 7/02/2013 Summer 2013 -- Lecture #6

31 Example: sumSquare int sumSquare(int x, int y) { return mult(x,x)+ y; } sumSquare: addi $sp,$sp,-8 push sw $ra, 4($sp) sw $a1, 0($sp) add $a1,$a0,$zero jal mult lw $a1, 0($sp) pop add $v0,$v0,$a1 lw $ra, 4($sp) addi $sp,$sp,8 jr $ra mult: ... 7/02/2013 # #

# # # # # # # make space on stack save ret addr save y set 2nd mult arg call mult restore y ret val = mult(x,x)+y get ret addr restore stack Summer 2013 -- Lecture #6 32 Basic Structure of a Function

Prologue func_label: addi $sp,$sp, -framesize sw $ra, ($sp) save other regs if need be Body ra (call other functions) ... Epilogue restore other regs if need be lw $ra, ($sp) addi $sp,$sp, framesize jr $ra 7/02/2013 Summer 2013 -- Lecture #6

stack 33 Local Variables and Arrays Any local variables the compiler cannot assign to registers will be allocated as part of the stack frame (Recall: spilling to memory) Locally declared arrays and structs are also allocated as part of the stack frame Stack manipulation is same as before Move $sp down an extra amount and use the space it created as storage 7/02/2013 Summer 2013 -- Lecture #6 34 Stack Before, During, After Call 7/02/2013

Summer 2013 -- Lecture #6 35 Get To Know Your Staff Category: Games 7/02/2013 Summer 2013 -- Lecture #6 36 Agenda

Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers Bonus: Memory Address Convention Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 37 Register Conventions CalleR: the calling function CalleE: the function being called Register Conventions: A set of generally accepted rules as to which registers will be unchanged after a procedure call (jal) and which may have changed

7/02/2013 Summer 2013 -- Lecture #6 38 Saved Registers These registers are expected to be the same before and after a function call If calleE uses them, it must restore values before returning This means save the old values, use the registers, then reload the old values back into the registers $s0-$s7 (saved registers) $sp (stack pointer) If not in same place, the caller wont be able to properly restore values from the stack $ra (return address) 7/02/2013 Summer 2013 -- Lecture #6

39 Volatile Registers These registers can be freely changed by the calleE If calleR needs them, it must save those values before making a procedure call $t0-$t9 (temporary registers) $v0-$v1 (return values) These will contain the new returned values $a0-$a3 (return address and arguments) These will change if calleE invokes another function (nested function means calleE is also a calleR) 7/02/2013 Summer 2013 -- Lecture #6 40 Register Conventions Summary One more time for luck:

CalleR must save any volatile registers it is using onto the stack before making a procedure call CalleE must save any saved registers it intends to use before garbling up their values Notes: CalleR and calleE only need to save the appropriate registers they are using (not all!) Dont forget to restore the values later 7/02/2013 Summer 2013 -- Lecture #6 41 Example: Using Saved Registers myFunc: # Uses $s0 and $s1 addiu $sp,$sp,-12 # This is the # This is Prologue the Prologue sw

$ra,8($sp) # Save saved registers sw $s0,4($sp) sw $s1,0($sp) ... # Do stuff with $s0 and $s1 jal func1 # $s0 and $s1 unchanged by ... # function calls, so can keep jal func2 # using them normally ... # Do stuff with $s0 and $s1 lw $s1,0($sp) # This is the # This

is Epilogue the Epilogue lw $s0,4($sp) # Restore saved registers lw $ra,8($sp) addiu $sp,$sp,12 jr $ra # return 7/02/2013 Summer 2013 -- Lecture #6 42 Example: Using Volatile Registers myFunc: # Uses $t0 addiu $sp,$sp,-4 sw $ra,0($sp) ... addiu $sp,$sp,-4

sw $t0,0($sp) jal func1 lw $t0,0($sp) addiu $sp,$sp,4 ... lw $ra,0($sp) addiu $sp,$sp,4 jr $ra 7/02/2013 # # # # # # #

# This is the Prologue Save saved registers Do stuff with $t0 Save volatile registers before calling a function # Function may change $t0 Restore volatile registers before you use them again Do stuff with $t0 # This is the Epilogue # Restore saved registers # return Summer 2013 -- Lecture #6 43 Choosing Your Registers Minimize register footprint Optimize to reduce number of registers you need to save by choosing which registers to use in a function

Only save when you absolutely have to Function does NOT call another function Use only $t0-$t9 and there is nothing to save! Function calls other function(s) Values you need throughout go in $s0-$s7, others go in $t0-$t9 At each function call, check number arguments and return values for whether you or not you need to save 7/02/2013 Summer 2013 -- Lecture #6 44 Question: Which statement below is FALSE? (A) MIPS uses jal to invoke a function and jr to return from a function (B) jal saves PC+1 in $ra

(C) The callee can use temporary registers ($ti) without saving and restoring them (D) The caller can rely on save registers ($si) without fear of callee changing them 45 Summary (1/2) Inequalities done using slt and allow us to implement the rest of control flow Pseudo-instructions make code more readable Count as MAL, later translated into TAL MIPS function implementation: Jump and link (jal) invokes, jump register (jr $ra) returns Registers $a0-$a3 for arguments, $v0-$v1 for return values 7/02/2013 Summer 2013 -- Lecture #6 46

Summary (2/2) Register conventions preserves values of registers between function calls Different responsibilities for calleR and calleE Registers classified as saved and volatile Use the Stack for spilling registers, saving return address, and local variables 7/02/2013 Summer 2013 -- Lecture #6 47 BONUS SLIDES You are responsible for the material contained on the following slides, though we may not have enough time to get to them in lecture. They have been prepared in a way that should be easily readable and the material will be touched upon in the following lecture.

7/02/2013 Summer 2013 -- Lecture #6 48 Agenda Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers

Bonus: Memory Address Convention Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 49 MIPS Registers

The constant 0 Reserved for Assembler Return Values Arguments Temporary Saved More Temporary Used by Kernel Global Pointer Stack Pointer Frame Pointer Return Address 7/02/2013 Summer 2013 -- Lecture #6 $0 $1 $2-$3 $4-$7 $8-$15 $16-$23

$24-$25 $26-27 $28 $29 $30 $31 $zero $at $v0-$v1 $a0-$a3 $t0-$t7 $s0-$s7 $t8-$t9 $k0-$k1 $gp $sp $fp $ra 50 The Remaining Registers $at (assembler)

Used for intermediate calculations by the assembler (pseudo-code); unsafe to use $k0-$k1 (kernal) May be used by the OS at any time; unsafe to use $gp (global pointer) Points to global variables in Static Data; rarely used $fp (frame pointer) Points to top of current frame in Stack; rarely used 7/02/2013 Summer 2013 -- Lecture #6 51 Agenda

Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions Bonus: Remaining Registers Bonus: Memory Address Convention Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 52 Memory Address Convention (Heap)

(Code) 7/02/2013 Summer 2013 -- Lecture #6 53 Agenda Inequalities Pseudo-Instructions Administrivia Implementing Functions in MIPS Function Calling Conventions

Bonus: Remaining Registers Bonus: Memory Address Convention Bonus: Register Convention Analogy 7/02/2013 Summer 2013 -- Lecture #6 54 Register Convention Analogy (1/5) Parents (calleR) leave for the weekend and give the keys to the house to their kid (calleE) Before leaving, they lay down a set of rules (calling conventions): You can trash the temporary rooms like the den and basement if you want; we dont care about them (volatile registers) BUT youd better leave the rooms for guests (living, dining, bed, etc.) untouched (saved registers): These rooms better look the same when we return! 7/02/2013

Summer 2013 -- Lecture #6 55 Register Convention Analogy (2/5) Kid now owns all of the rooms (registers) Kid is going to throw a wild, wild party (computation) and wants to use the guest rooms (saved registers) So what does the kid (calleE) do? Takes stuff from guest rooms and moves it to the shed in the backyard (memory) Throws the party and everything in the house gets trashed (shed is outside, so it survives) Restores guest rooms by replacing the items from the backyard shed 7/02/2013 Summer 2013 -- Lecture #6 56

Register Convention Analogy (3/5) Same scenario, except that during the party, the kid needs to run to the store for supplies Kid (calleE) has left valuable stuff (data) all over the house The party will continue, meaning the valuable stuff might get destroyed Kid leaves friend (2nd calleE) in charge, instructing him/her on the rules of the house (conventions) Here the kid has become the heavy (calleR) 7/02/2013 Summer 2013 -- Lecture #6 57 Register Convention Analogy (4/5) If kid has valuable stuff (data) in the temporary rooms (volatile registers) that are going to be trashed, there are three options: 1) Move stuff to the backyard shed (memory)

2) Move stuff to guest rooms (saved registers) whose contents have already been moved to the shed 3) Optimize lifestyle (code) so that the amount youve got to schlep back and forth from shed is minimized. Mantra: Minimize register footprint Otherwise: Dude, wheres my data?! 7/02/2013 Summer 2013 -- Lecture #6 58 Register Convention Analogy (5/5) Same as kid! Friend now owns all of the rooms (registers) Friend decides to allow the wild, wild party (computation) to use the guest rooms (saved registers) What does the friend (2nd calleE) do? Takes stuff from guest rooms and moves it to the shed in

the backyard (memory) Throws the party and everything in the house gets trashed (shed is outside, so it survives) Restores guest rooms by replacing the items from the backyard shed 7/02/2013 Summer 2013 -- Lecture #6 59

Recently Viewed Presentations

  • kahoot - vlc.nccommunitycolleges.edu

    kahoot - vlc.nccommunitycolleges.edu

    Kahoot enables users to ask questions in an easy-to-use, inclusive, and engaging way. Its potential benefits include increased student participation, promoting healthy motivation in students, and student-driven learning. Though assessment, review, and quizzes are Kahoot's primary functions ...
  • Slide 1

    Slide 1

    Independent Enquirer. Creative Thinker. Say what we do in different weather conditions. with opinions - Lv3. with reasons - Lv4. Team Worker. Effective Participator. Creative Thinker. Write out these sentences. Each letter stands for a word, e.g. Q i f...
  • SC-ITE Digitalisation in Engineering Program Proposal

    SC-ITE Digitalisation in Engineering Program Proposal

    GuidingPrinciplesfrom a Bosch Perspective. Requirements and Objectives for holistic PLM . Benefit for BU users in a short timeframe should prioritize project topics. Seamless toolchains are as important as functional tool excellence. Tools follows process is not in every situation...
  • Title

    Title

    A "fruit machine" is a British term for a slot machine. The one-armed bandit is another popular nickname. Evolution of Bingo. Traditional Bingo. Evolution of Online Gambling. 2012 . ... hockey, etc. Gambling on sports is banned in the USA...
  • Burrage v. United States [Needs full Supreme Court cite ...

    Burrage v. United States [Needs full Supreme Court cite ...

    Blessing v. Sirius XM Radio Inc., 507 Fed. Appx. 1 (2d Cir. 2012) Alito, J., Concurring: "It seems quite farfetched to argue that class counsel cannot fairly and adequately represent a class unless the race and gender of counsel mirror...
  • PHTLS Slides - OU Medicine

    PHTLS Slides - OU Medicine

    Kinematics of Trauma Kimberly Ann Holmes Kenney RN, CNS-Rx, MS(N), MS CCRN, CEN, CFRN, NREMT-P Types of Impact: Frontal/Ejection How many impacts did this collision involve?
  • CU Project Management Mentoring Introduction

    CU Project Management Mentoring Introduction

    The Work Breakdown Structure (WBS) The WBS = your "Nouns" WBS = The work being delivered Hierarchical representation of work elements needing completion—deliverables themselves or deliverable components Single most important tool in scope definition, scope control, and communications What about...
  • GD&amp;T

    GD&T

    FIT. Fit is generally term used to signify the range of tightness or looseness which may result from the application of a specific combination of allowance and tolerance in the design of mating part features. Fits are of generally three...