14:332:331 Computer Architecture and Assembly Language Spring 06 Week 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 InstructionsSlide 17Compiling 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 ProcedureSlide 33Slide 34331 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 OrganizationProcessorMemory32 bits230wordsread/write addrread datawrite dataword address(binary)0…00000…01000…10000…11001…1100Register Filesrc1 addrsrc2 addrdst addrwrite data32 bitssrc1datasrc2data32registers($zero - $ra)323232323232555 ALU323232 0 1 2 37654byte address(big Endian)Arithmetic instructions – to/from the register fileLoad/store word and byte instructions – from/to memoryFetchDecodeExec331 Week 3. 3 Spring 2006Review: MIPS Instructions, so farCategory Instr Op Code Example MeaningArithmetic(R format)add 0 and 32 add $s1, $s2, $s3 $s1 = $s2 + $s3subtract 0 and 34 sub $s1, $s2, $s3 $s1 = $s2 - $s3Datatransfer(I format)load word 35 lw $s1, 100($s2) $s1 = Memory($s2+100)store word 43 sw $s1, 100($s2) Memory($s2+100) = $s1load byte 32 lb $s1, 101($s2) $s1 = Memory($s2+101)store byte 40 sb $s1, 101($s2) Memory($s2+101) = $s1331 Week 3. 4 Spring 2006Decision making instructionsalter the control flow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 offset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:PClimits the offset to -215 to +215-1 from the (instruction after the) branch instruction, but-most branches are local anyway (principle of locality)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 -217 to +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 byconcatenating two low-order zeros to create an 18 bit number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 code bne $s0, $s1, Lab1add $s3, $s0, $s1Lab1: ...Machine Format of bne:Assembling Branches Exampleop rs rt 16 bit offsetI format5 16 17RememberAfter the bne instruction is fetched, the PC is updated to address the add instruction (PC = PC + 4).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/write addrread datawrite dataword address(binary)0…00000…01000…10000…11001…1100Register Filesrc1 addrsrc2 addrdst addrwrite data32 bitssrc1datasrc2data32registers($zero - $ra)323232323232555 PCALU32 323232320 1 2 37654byte 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?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 beq instruction is 0x00400020 (hex address)beq $s0, $s1, Lab1add $s3, $s0, $s1j Lab2Lab1: 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 $s2 while (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 format:2More Instructions for Making Decisionsop rs rt rd funct 0 16 17 8 0 42 = 0x2a331 Week