CS61C L 7 MIPS Decisions (1 ) Beamer, Summer 2 007 © UCBScott Beamer, Instructorinst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture #7 – MIPS Decisions2007-7-5takes onwww.sfgate.comwithCS61C L 7 MIPS Decisions (2 ) Beamer, Summer 2 007 © UCBReview• In MIPS Assembly Language:• Registers replace C variables• One Instruction (simple operation) per line• Simpler is better, smaller is faster• Memory is byte-addressable, but lw and sw accessone word at a time.• A pointer (used by lw and sw) is just a memoryaddress, so we can add to it or subtract from it (usingoffset).• New Instructions:add, addi, sub, lw, sw• New Registers:C Variables: $s0 - $s7Temporary Variables: $t0 - $t9Zero: $zeroCS61C L 7 MIPS Decisions (3 ) Beamer, Summer 2 007 © UCBSo Far...• All instructions so far only manipulatedata…we’ve built a calculator.• In order to build a computer, we needability to make decisions…• C (and MIPS) provide labels to support“goto” jumps to places in code.• C: Horrible style; MIPS: Necessary!• Heads up: pull out some papers andpens, you’ll do an in-class exercise!CS61C L 7 MIPS Decisions (4 ) Beamer, Summer 2 007 © UCBC Decisions: if Statements• 2 kinds of if statements in C•if (condition) clause•if (condition) clause1 else clause2• Rearrange 2nd if into following: if (condition) goto L1; clause2; goto L2;L1: clause1; L2:• Not as elegant as if-else, but samemeaningCS61C L 7 MIPS Decisions (5 ) Beamer, Summer 2 007 © UCBMIPS Decision Instructions• Decision instruction in MIPS:•beq register1, register2, L1•beq is “Branch if (registers are) equal”Same meaning as (using C): if (register1==register2) goto L1• Complementary MIPS decision instruction•bne register1, register2, L1•bne is “Branch if (registers are) not equal” Same meaning as (using C): if (register1!=register2) goto L1• Called conditional branchesCS61C L 7 MIPS Decisions (6 ) Beamer, Summer 2 007 © UCBMIPS Goto Instruction• In addition to conditional branches,MIPS has an unconditional branch:j label• Called a Jump Instruction: jump (orbranch) directly to the given labelwithout needing to satisfy any condition• Same meaning as (using C): goto label• Technically, it’s the same as:beq $0,$0,labelsince it always satisfies the condition.CS61C L 7 MIPS Decisions (7 ) Beamer, Summer 2 007 © UCBCompiling 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: $s4Exiti == j?f=g+h f=g-h(false) i != j(true) i == jCS61C L 7 MIPS Decisions (9 ) Beamer, Summer 2 007 © UCBOverflow in Arithmetic (1/2)• Reminder: Overflow occurs whenthere is a mistake in arithmetic due tothe limited precision in computers.• Example (4-bit unsigned numbers):+15 1111 +3 0011+18 10010• But we don’t have room for 5-bit solution,so the solution would be 0010, which is+2, and wrong.CS61C L 7 MIPS Decisions (10) Beamer, Summer 2 007 © UCBOverflow in Arithmetic (2/2)• Some languages detect overflow (Ada),some don’t (C)• MIPS solution has 2 kinds of arithmeticinstructions to recognize 2 choices:• add (add), add immediate (addi) andsubtract (sub) cause overflow to be detected• add unsigned (addu), add immediateunsigned (addiu) and subtract unsigned(subu) do not cause overflow detection• Compiler selects appropriate arithmetic• MIPS C compilers produceaddu, addiu, subuCS61C L 7 MIPS Decisions (11) Beamer, Summer 2 007 © UCBTwo Logic Instructions• 2 lectures ago we saw add, addi, sub• Here are 2 more new instructions• Shift Left: sll $s1,$s2,2 #s1=s2<<2• Store in $s1 the value from $s2 shifted 2bits to the left, inserting 0’s on right; << in C• Before: 0000 0002hex0000 0000 0000 0000 0000 0000 0000 0010two• After: 0000 0008hex0000 0000 0000 0000 0000 0000 0000 1000two• What arithmetic effect does shift left have?• Shift Right: srl is opposite shift; >>CS61C L 7 MIPS Decisions (12) Beamer, Summer 2 007 © UCBLoops in C/Assembly (1/3)• Simple loop in C; A[] is an array of intsdo {g = g + A[i];i = i + j;} while (i != h);• Rewrite this as:Loop: g = g + A[i];i = i + j;if (i != h) goto Loop;• Use this mapping: g, h, i, j, base of A$s1, $s2, $s3, $s4, $s5CS61C L 7 MIPS Decisions (13) Beamer, Summer 2 007 © UCBLoops in C/Assembly (2/3)• Final compiled MIPS code:Loop: sll $t1,$s3,2 #$t1= 4*i add $t1,$t1,$s5 #$t1=addr A lw $t1,0($t1) #$t1=A[i] add $s1,$s1,$t1 #g=g+A[i] add $s3,$s3,$s4 #i=i+j bne $s3,$s2,Loop# goto Loop # if i!=h• Original code:Loop: g = g + A[i];i = i + j;if (i != h) goto Loop;CS61C L 7 MIPS Decisions (14) Beamer, Summer 2 007 © UCBLoops in C/Assembly (3/3)• There are three types of loops in C:•while•do… while•for• Each can be rewritten as either of theother two, so the method used in theprevious example can be applied towhile and for loops as well.• Key Concept: Though there are multipleways of writing a loop in MIPS, the keyto decision making is conditional branchCS61C L 7 MIPS Decisions (15) Beamer, Summer 2 007 © UCBPeer InstructionWe want to translate *x = *y into MIPS(x, y ptrs stored in: $s0 $s1)A: add $s0, $s1, zeroB: add $s1, $s0, zeroC: lw $s0, 0($s1)D: lw $s1, 0($s0)E: lw $t0, 0($s1)F: sw $t0, 0($s0)G: lw $s0, 0($t0)H: sw $s1, 0($t0)1: A2: B3: C4: D5: E→F6: E→G7: F→E8: F→H9: H→G0: G→HCS61C L 7 MIPS Decisions (16) Beamer, Summer 2 007 © UCBAdministrivia• Assignments• HW2 due tonight @ 11:59pm• HW3 due 7/8 @ 11:59pm• Proj1 due 7/12 @ 11:59pm (going up today)• Third Section• Is going to happen, CS dept has approvedfunding, room, TA, etc….• But Summer Sessions office in Wheelerslow to move• Don’t unplug stuff in lab!CS61C L 7 MIPS Decisions (17) Beamer, Summer 2 007 © UCBInequalities in MIPS (1/3)• Until now, we’ve only tested equalities(== and != in C). General programs needto test < and > as well.• Create a MIPS Inequality Instruction:• “Set on Less Than”• Syntax: slt reg1,reg2,reg3• Meaning:if (reg2 < reg3)reg1 = 1;else reg1 = 0;• In computereeze, “set” means “set to 1”,“reset” means “set to 0”.reg1 = (reg2 < reg3);Same thing…CS61C L 7 MIPS Decisions (18) Beamer, Summer 2 007 © UCBInequalities in MIPS (2/3)• How do we use this? Compile by hand:if (g < h) goto Less; #g:$s0, h:$s1• Answer: compiled MIPS code…slt $t0,$s0,$s1 # $t0 = 1 if g<hbne $t0,$0,Less # goto Less # if $t0!=0 # (if (g<h))
View Full Document
Unlocking...