14:332:331Computer Architecture and Assembly LanguageSpring 06Week 3 : Braches and ProceduresReview: MIPS OrganizationReview: MIPS Instructions, so farInstructions for Making DecisionsAssembling BranchesSpecifying Branch DestinationsDisassembling Branch DestinationsAssembling Branches ExampleMIPS OrganizationAnother Instruction for Changing FlowAssembling JumpsDisassembling Jump DestinationsAssembling Branches and JumpsCompiling While LoopsMore Instructions for Making DecisionsOther Branch InstructionsAnother Instruction for Changing FlowCompiling a Case (Switch) StatementInstructions, so farLogic OperationsLogical Operations - ShiftsProceduresSix Steps in Execution of a ProcedureInstruction for Calling a ProcedureCompiling a ProcedureMIPS Register ConventionSpilling RegistersA Quick AsideNested ProceduresNested Procedures OutcomeSaving the Return AddressCompiling a Recursive ProcedureCompiling a Recursive ProcedureReview: MIPS Instructions, so far331 Week 3. 1 Spring 200614:332:331Computer Architecture and Assembly LanguageSpring 06Week 3 : Braches and Procedures[Adapted from Dave Patterson’s UCB CS152 slides andMary Jane Irwin’s PSU CSE331 slides]331 Week 3. 2 Spring 2006Review: MIPS Organization Arithmetic instructions – to/from the register file Load/store word and byte instructions – from/to memoryProcessorMemory32 bits230wordsread/writeaddrread datawrite dataword address(binary)0…00000…01000…10000…11001…1100Register Filesrc1 addrsrc2 addrdst addrwrite data32 bitssrc1datasrc2data32registers($zero - $ra)323232323232555ALU32323201237654byte address(big Endian)FetchDecodeExec331 Week 3. 3 Spring 2006Review: MIPS Instructions, so farCategory Instr Op Code Example Meaningadd 0 and 320 and 343543load byte 32 lb $s1, 101($s2) $s1 = Memory($s2+101)store byte 40 sb $s1, 101($s2) Memory($s2+101) = $s1add $s1, $s2, $s3 $s1 = $s2 + $s3subtract sub $s1, $s2, $s3 $s1 = $s2 - $s3load word lw $s1, 100($s2) $s1 = Memory($s2+100)store word sw $s1, 100($s2) Memory($s2+100) = $s1Arithmetic(R format)Datatransfer(I format)331 Week 3. 4 Spring 2006 Decision making instructionsz alter the control flowz i.e., change the "next" instruction to be executed Why do we need decision making instructions?if (i==j) h = i + j;MIPS conditional branch instructions:bne $s0, $s1, Label #go to Label if $s0≠$s1 beq $s0, $s1, Label #go to Label if $s0=$s1 Example: if (i==j) h = i + j;Instructions for Making Decisions331 Week 3. 5 Spring 2006 Instructions:bne $s0, $s1, Label #go to Label if $s0≠$s1 beq $s0, $s1, Label #go to Label if $s0=$s1 Machine Formats: How is the branch destination address specified?Assembling Branchesop rs rt 16 bit numberI format5 16 17 ????4 16 17 ????6 bits5 bits 5 bits331 Week 3. 6 Spring 2006Specifying Branch Destinations Could use a register (like lw and sw) and add to it the 16-bit offsetz which register?- Instruction Address Register (PC = program counter)- its use is automatically implied by instruction- PC gets updated (PC+4) during the fetch cycle so that it holds the address of the next instructionbne $s0,$s1,Lab1add $s3,$s0,$s1...Lab1+PC:PCz limits the offset to -215to +215-1 from the (instruction after the) branch instruction, but- most branches are local anyway (principle of locality)z One optimization- Each instruction is 4 bytes long, and only word address is necessary (multiple of 4)- We can right shift the offset by 2 bits (divided by 4), and store the value- Essentially, it can cover -217to +217-1 offset331 Week 3. 7 Spring 2006Disassembling Branch Destinations The contents of the updated PC (PC+4) is added to the low order 16 bits of the branch instruction which is converted into a 32 bit value byz concatenating two low-order zeros to create an 18 bit numberz sign-extending those 18 bits The result is written into the PC if the branch condition is true prior to the next Fetch cyclePCAdd3232323232offset163200sign-extendfrom the low order 16 bits of the branch instructionbranch dstaddress?Add432Why??331 Week 3. 8 Spring 2006 Assembly codebne $s0, $s1, Lab1add $s3, $s0, $s1Lab1: ... Machine Format of bne:Assembling Branches Exampleop rs rt 16 bit offsetI format5 16 17Rememberz After the bne instruction is fetched, the PC is updated to address the add instruction (PC = PC + 4).z Two low-order zeros are concatenated to the offset number and that value sign-extended is added to the (updated) PC331 Week 3. 9 Spring 2006MIPS OrganizationProcessorMemory32 bits230wordsread/writeaddrread datawrite dataword address(binary)0…00000…01000…10000…11001…1100Register Filesrc1 addrsrc2 addrdst addrwrite data32 bitssrc1datasrc2data32registers($zero - $ra)323232323232555PCALU32 3232323201237654byte address(big Endian)FetchPC = PC+4DecodeExecAdd32324Add3232br offset331 Week 3. 10 Spring 2006 MIPS also has an unconditional branch instruction or jump instruction:j label #go to label Example: if (i!=j) h=i+j;elseh=i-j;Another Instruction for Changing Flow331 Week 3. 11 Spring 2006 Instruction:j label #go to label Machine Format: How is the jump destination address specified?z As an absolute address formed by- concatenating the upper 4 bits of the current PC (now PC+4) to the 26-bit address and- concatenating 00 as the 2 low-order bitsAssembling Jumpsop 26-bit addressJ format2 ????331 Week 3. 12 Spring 2006Disassembling Jump Destinations to create a 32 bit instruction address that is placed into the PC prior to the next Fetch cyclePC3232263200from the low order 26 bits of the jump instruction331 Week 3. 13 Spring 2006 Assemble the MIPS machine code (in decimal is fine) for the following code sequence. Assume that the address of the beqinstruction is 0x00400020 (hex address)beq $s0, $s1, Lab1add $s3, $s0, $s1jLab2Lab1: sub $s3, $s0, $s1Lab2: ...Assembling Branches and Jumps331 Week 3. 14 Spring 2006Compiling While Loops Compile the assembly code for the C while loop where i is in $s0, j is in $s1, and k is in $s2while (i!=k) i=i+j;331 Week 3. 15 Spring 2006 We have beq, bne, but what about branch-if-less-than? New instruction:slt $t0, $s0, $s1 # if $s0 < $s1# then# $t0 = 1# else # $t0 = 0 Machine