CS 61C L14Introduction to MIPS: Instruction Representation II ( 1) Garcia, Fall 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture 14 – Introduction to MIPS Instruction Representation II 2004-10-01Shark Tale!!! ⇒ Dreamworks todayreleased their big fall movie.Pixar will release their movie“The Incredibles” soon.Compare & contrast the two!www.sharktale.comCS 61C L14Introduction to MIPS: Instruction Representation II ( 2) Garcia, Fall 2004 © UCBI-Format Problems (0/3)• Problem 0: Unsigned # sign-extended?•addiu, sltiu, sign-extends immediatesto 32 bits. Thus, # is a “signed” integer.• Rationale•addiu so that can add w/out overflow- See K&R pp. 230, 305•sltiu suffers so that we can have ez HW- Does this mean we’ll get wrong answers?- Nope, it means assembler has to handle anyunsigned immediate 215 ≤ n < 216 (I.e., with a1 in the 15th bit and 0s in the upper 2 bytes)as it does for numbers that are too large. ⇒CS 61C L14Introduction to MIPS: Instruction Representation II ( 3) Garcia, Fall 2004 © UCBI-Format Problems (1/3)• Problem 1:• Chances are that addi, lw, sw and sltiwill use immediates small enough to fit inthe immediate field.• …but what if it’s too big?• We need a way to deal with a 32-bitimmediate in any I-format instruction.CS 61C L14Introduction to MIPS: Instruction Representation II ( 4) Garcia, Fall 2004 © UCBI-Format Problems (2/3)• Solution to Problem 1:• Handle it in software + new instruction• Don’t change the current instructions:instead, add a new instruction to help out• New instruction:lui register, immediate• stands for Load Upper Immediate• takes 16-bit immediate and puts these bitsin the upper half (high order half) of thespecified register• sets lower half to 0sCS 61C L14Introduction to MIPS: Instruction Representation II ( 5) Garcia, Fall 2004 © UCBI-Format Problems (3/3)• Solution to Problem 1 (continued):• So how does lui help us?• Example:addi $t0,$t0, 0xABABCDCDbecomes:lui $at, 0xABABori $at, $at, 0xCDCDadd $t0,$t0,$at• Now each I-format instruction has only a 16-bit immediate.• Wouldn’t it be nice if the assembler wouldthis for us automatically? (later)CS 61C L14Introduction to MIPS: Instruction Representation II ( 6) Garcia, Fall 2004 © UCBBranches: PC-Relative Addressing (1/5)• Use I-Formatopcode rs rt immediate• opcode specifies beq v. bne• rs and rt specify registers to compare• What can immediate specify?•Immediate is only 16 bits• PC (Program Counter) has byte address ofcurrent instruction being executed;32-bit pointer to memory• So immediate cannot specify entireaddress to branch to.CS 61C L14Introduction to MIPS: Instruction Representation II ( 7) Garcia, Fall 2004 © UCBBranches: PC-Relative Addressing (2/5)• How do we usually use branches?• Answer: if-else, while, for• Loops are generally small: typically up to50 instructions• Function calls and unconditional jumps aredone using jump instructions (j and jal),not the branches.• Conclusion: may want to branch toanywhere in memory, but a branch oftenchanges PC by a small amountCS 61C L14Introduction to MIPS: Instruction Representation II ( 8) Garcia, Fall 2004 © UCBBranches: PC-Relative Addressing (3/5)• Solution to branches in a 32-bitinstruction: PC-Relative Addressing• Let the 16-bit immediate field be asigned two’s complement integer to beadded to the PC if we take the branch.• Now we can branch ± 215 bytes fromthe PC, which should be enough tocover almost any loop.• Any ideas to further optimize this?CS 61C L14Introduction to MIPS: Instruction Representation II ( 9) Garcia, Fall 2004 © UCBBranches: PC-Relative Addressing (4/5)• Note: Instructions are words, sothey’re word aligned (byte address isalways a multiple of 4, which means itends with 00 in binary).• So the number of bytes to add to the PCwill always be a multiple of 4.• So specify the immediate in words.• Now, we can branch ± 215 words fromthe PC (or ± 217 bytes), so we canhandle loops 4 times as large.CS 61C L14Introduction to MIPS: Instruction Representation II ( 10) Garcia, Fall 2004 © UCBBranches: PC-Relative Addressing (5/5)• Branch Calculation:• If we don’t take the branch:PC = PC + 4PC+4 = byte address of next instruction• If we do take the branch:PC = (PC + 4) + (immediate * 4)• Observations- Immediate field specifies the number ofwords to jump, which is simply the number ofinstructions to jump.- Immediate field can be positive or negative.- Due to hardware, add immediate to (PC+4),not to PC; will be clearer why later in courseCS 61C L14Introduction to MIPS: Instruction Representation II ( 11) Garcia, Fall 2004 © UCBBranch Example (1/3)• MIPS Code:Loop: beq $9,$0,Endadd $8,$8,$10addi $9,$9,-1j LoopEnd:• beq branch is I-Format:opcode = 4 (look up in table)rs = 9 (first operand)rt = 0 (second operand)immediate = ???CS 61C L14Introduction to MIPS: Instruction Representation II ( 12) Garcia, Fall 2004 © UCBBranch Example (2/3)• MIPS Code:Loop: beq $9,$0,Endaddi $8,$8,$10addi $9,$9,-1j LoopEnd:• Immediate Field:• Number of instructions to add to (orsubtract from) the PC, starting at theinstruction following the branch.• In beq case, immediate = 3CS 61C L14Introduction to MIPS: Instruction Representation II ( 13) Garcia, Fall 2004 © UCBBranch Example (3/3)• MIPS Code:Loop: beq $9,$0,Endaddi $8,$8,$10addi $9,$9,-1j LoopEnd:4 9 0 3decimal representation:binary representation:000100 01001 00000 0000000000000011CS 61C L14Introduction to MIPS: Instruction Representation II ( 14) Garcia, Fall 2004 © UCBQuestions on PC-addressing• Does the value in branch field changeif we move the code?• What do we do if destination is > 215instructions away from branch?• Since it’s limited to ± 215 instructions,doesn’t this generate lots of extraMIPS instructions?• Why do we need all these addressingmodes? Why not just one?CS 61C L14Introduction to MIPS: Instruction Representation II ( 19) Garcia, Fall 2004 © UCBJ-Format Instructions (1/5)• For branches, we assumed that wewon’t want to branch too far, so wecan specify change in PC.• For general jumps (j and jal), we mayjump to anywhere in memory.• Ideally, we could specify a 32-bitmemory address to jump to.• Unfortunately, we can’t fit both a 6-bitopcode and a 32-bit address into
View Full Document
Unlocking...