DOC PREVIEW
Berkeley COMPSCI 61C - Lecture Notes

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS61C L7 MIPS Decisions (1)Beamer, Summer 2007 © UCBScott Beamer, Instructorinst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture #7 – MIPS Decisions2007-7-5takes onwww.sfgate.comwithCS61C L7 MIPS Decisions (2)Beamer, Summer 2007 © 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 L7 MIPS Decisions (3)Beamer, Summer 2007 © 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 L7 MIPS Decisions (4)Beamer, Summer 2007 © 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 L7 MIPS Decisions (5)Beamer, Summer 2007 © 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 L7 MIPS Decisions (6)Beamer, Summer 2007 © 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 L7 MIPS Decisions (7)Beamer, Summer 2007 © 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 L7 MIPS Decisions (8)Beamer, Summer 2007 © UCBCompiling 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 # goto FinTrue: add $s0,$s1,$s2 # f=g+h (true)Fin:Note: Compiler automatically creates labels tohandle decisions (branches).Generally not found in HLL code.Exiti == j?f=g+h f=g-h(false) i != j(true) i == j• Compile by handif (i == j) f=g+h;else f=g-h;CS61C L7 MIPS Decisions (9)Beamer, Summer 2007 © 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 L7 MIPS Decisions (10)Beamer, Summer 2007 © 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 L7 MIPS Decisions (11)Beamer, Summer 2007 © 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 L7 MIPS Decisions (12)Beamer, Summer 2007 © 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 L7 MIPS Decisions (13)Beamer, Summer 2007 © 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 L7 MIPS Decisions (14)Beamer, Summer 2007 © 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 L7 MIPS Decisions (15)Beamer, Summer 2007 © 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 L7 MIPS Decisions (16)Beamer, Summer 2007 © 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 L7 MIPS Decisions (17)Beamer, Summer 2007 © 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


View Full Document

Berkeley COMPSCI 61C - Lecture Notes

Documents in this Course
SIMD II

SIMD II

8 pages

Midterm

Midterm

7 pages

Lecture 7

Lecture 7

31 pages

Caches

Caches

7 pages

Lecture 9

Lecture 9

24 pages

Lecture 1

Lecture 1

28 pages

Lecture 2

Lecture 2

25 pages

VM II

VM II

4 pages

Midterm

Midterm

10 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?