## LSU EE 3755 -- Fall 2013 -- Computer Organization # ## Note Set 10 -- Control-Transfer Instructions # Time-stamp: <25 October 2013, 9:09:12 CDT, koppel@dmk-laptop> ## Contents # # A Simple Jump Instruction # A Branch Instruction # Types of Control-Transfer Instructions # More Branch Instructions # More Jump Instructions # Procedure Call Example # Typical CTI Uses ## References # # :PH: Patterson & Hennessy, "Computer Organization & Design", 4th Edition # :Mv1: MIPS Technologies, "MIPS32 Architecture for Programmers Vol I: Intro" # :Mv2: MIPS Technologies, "MIPS32 Architecture for Programmers Vol II: Instr" ################################################################################ ## A Simple Jump Instruction # :PH: 2.7 # :Mv2: # Simple jump (j) covered here, others (jr,jal,jalr) covered in a # later selection. # Assembler :Syntax: J target # Coding :Syntax: J ii # After next instruction go to { PC[31:28], ii, 2'b0 }, # where ii is bits 27:2 of target. # # In assembly language "target" is the line label for the target. # In machine language "target", the ii field, is bits 27:2 of the # target address. # Bits 31:28 of the target address must match bits 31:28 of the jump # instruction's address. (If not, use the jr instruction.) # :Example: # # Code used to illustrate how target is determined. FIRSTLINE: # Address of add: 0x400000 add $8, $0, $0 j FORJOY # 0x00400004 addi $8, $8, 1 addi $8, $8, 2 FORJOY: # Address of addi: 0x400014 addi $8, $8, 4 addi $8, $8, 8 # In the code above: # # FORJOY is a line label, part of the assembly language. # Suppose the assembler [really the linker] sets FORJOY = 0x400014. # :Example: # # Code used to illustrate a j instruction that can't be assembled. FIRSTLINE: # Address of add: 0x400000 add $8, $0, $0 j FORJOY # Assembler error, target too far away. addi $8, $8, 1 addi $8, $8, 2 # lots of code FORJOY: # Address of addi: 0x10400014 addi $8, $8, 4 addi $8, $8, 8 ################################################################################ ## A Branch Instruction # :PH: 2.7 # :Mv2: # One branch instruction covered here (bne), others (beq, bltz, etc.) # covered in a later section. # Assembler :Syntax: BNE rs, rt, target # Branch Not Equal # Coding :Syntax: BNE rs, rt, offset # if rs != rt after next instruction # go to PC + 4 + 4 * sign_extend(offset) # # "target" is the line label to continue at. # "offset" is the number of instructions to skip, starting at # the instruction after the branch. # :Example: # # Code to illustrate the offset. FIRSTLINE: add $9, $0, $0 addi $10, $9, 1 0x1000: bne $9, $10, LINE 0x1004: addi $8, $8, 1 # Offset computed from this instruction. 0x1008: addi $8, $8, 2 // Targ = 0x1004 + 4 * 2 = 0x100c LINE: // LINE == 0x100c 0x100c: addi $8, $8, 4 # The branch target, offset = 2 instructions. addi $8, $8, 8 # :Example: # # Use of a branch in a loop. add $8, $0, $0 # $8 -> 0 addi $9, $0, 10 # $9 -> 10 add $10, $0, $0 # $10 -> 0 (i) LOOP: add $8, $8, $10 # $8 = $8 + i addi $9, $9, -1 bne $9, $0, LOOP addi $10, $10, 1 # i = i + 1 ################################################################################ ## Types of Control-Transfer Instructions # :PH: Material covered in a different order. # :Mv1: 4.1.3 (Brief overview.) ## Types of Control Transfers # # Branch # Used for loops, ifs, etc. Most commonly used CTI. # Instruction specifies a condition and an address, the target. # If condition is true continue execution at target. # # Branch-and-Link # Used for procedure calls. # Instruction specifies a condition and an address, the target. # If condition is true save PC in $31 and continue execution at target. # # Jump # Used for returns and other purposes. # Instruction specifies a target # Continue execution at target. # # Jump-and-Link # Used for procedure calls and returns and other purposes. # Instruction specifies a target # Save PC in $31 and continue execution at target. # # Trap (Not covered in detail.) # If condition true continue at specified entry in OS-prepared trap table. # # ## Conditions and Targets # # The methods used to specify conditions and targets vary by instruction. # See descriptions in following sections ## Delayed CTI <- PAY ATTENTION TO THIS. # # All of the CTIs covered here are delayed (except traps). # # The instruction after an ordinary delayed CTI IS ALWAYS EXECUTED. # add $8, $0, $0 j FORJOY addi $8, $8, 1 addi $8, $8, 2 FORJOY: addi $8, $8, 4 addi $8, $8, 8 ################################################################################ ## More Branch Instructions # :PH: 2.7 # :Mv2: # Assembler :Syntax: BEQ rs, rt, target # Branch Equal # Coding :Syntax: BEQ rs, rt, offset # if rs == rt after next instruction # go to PC + 4 + 4 * sign_extend(offset) # # Assembler :Syntax: BGEZ rs, target # Branch >= Zero # Coding :Syntax: BGEZ rs, offset # if rs >= 0 after next instruction # go to PC + 4 + 4 * sign_extend(offset) # # Assembler :Syntax: BGTZ rs, target # Branch > Zero # Coding :Syntax: BGTZ rs, offset # if rs > 0 after next instruction # go to PC + 4 + 4 * sign_extend(offset) # # Assembler :Syntax: BLEZ rs, target # Branch <= Zero # Coding :Syntax: BLEZ rs, offset # if rs <= 0 after next instruction # go to PC + 4 + 4 * sign_extend(offset) # # Assembler :Syntax: BLTZ rs, target # Branch < Zero # Coding :Syntax: BLTZ rs, offset # if rs < 0 after next instruction # go to PC + 4 + 4 * sign_extend(offset) ################################################################################ ## More Jump Instructions # :PH: 2.8 # :Mv2: # Assembler :Syntax: JAL target # Jump and link. # Coding :Syntax: JAL ii # $31 <- PC + 8 # After next instruction go to { PC[31:28], ii, 2'b0 }, # where ii is bits 27:2 of target. # Note: $31 a.k.a. $ra # # :Syntax: JR rs # Jump register. # After next instruction go to address in rs. # # :Syntax: JALR rs, rt # Jump and link register. # rt <- PC + 8 # After next instruction go to address in rs # Note: $31 a.k.a. $ra # # :Example: # # Use of j instruction. # Jump to LINEX j LINEX nop nop LINEX: addi $t2, $t2, 1 # :Example: # # Use of jal instruction. LINEA: # LINEA = 0x12345678 # Instruction below is stored at (PC=) 0x12345678 # Set $ra -> PC + 8 = 0x12345680 and jump to LINEX jal LINEX nop nop LINEX: addi $t2, $t2, 1 # :Example: # # Use of jr instruction. # Load the address of a line into $to. la $t0, LINEX # Jump to the line. jr $t0 nop nop LINEX: addi $t2, $t2, 1 # :Example: # # Use of jalr instruction. LINEA: # LINEA = 0x12345678 la $t0, LINEX # Note: this resolves to two instructions. # Instruction below is stored at (PC=) 0x12345680 # Set $ra -> PC + 8 = 0x12345688 and jump to LINEX jalr $t0 nop nop LINEX: addi $t2, $t2, 1 ################################################################################ ## Procedure Call Example # :PH: 2.8 # :Example: # # Use of jal, jr, and jalr instructions to call and return from # a procedure. # # The called procedure, times_three, puts 3 times $a0 in $v0. # # The procedure is called correctly three times, after which the code # goes into an infinite loop. # # For clarity CTI delay slots are filled with nops. In many examples # and in assignments they should be filled, where possible, with # useful instructions. .globl __start __start: addi $a0, $0, 12 # Set value to be tripled. jal times_three # Jump and save PC + 8 in $ra ($31) nop addi $a0, $0, 3755 # Returns here after jal above. jal times_three # Call times_three again. nop nop # Returns here after jal above. la $s1, times_three # Store address of times_three in $s1 addi $a0, $0, 2002 # Value to triple. jalr $s1 # Call times_three again, this time using jalr. nop addi $a0, $0, 22 # jr $s1 # THE WRONG WAY TO CALL A PROCEDURE!! nop addi $a0, $0, 0 # Never reached. times_three: sll $v0, $a0, 1 # Start of times_three. add $v0, $v0, $a0 jr $ra # Jump using return address. nop ################################################################################ ## Typical CTI Uses # :PH: 2.7, 2.8 # Branches (bne, beq, bltz, etc.) # if/else # Loops # # Regular Jump (j) # if/else, loops (along with branches) # # Jump and Link: (jal, jalr) # Procedure calls. # # Jump Register # Procedure returns. # switch statements. # :Example: # Typical if/else statement. # # if ( a + b > c ) # Condition # { # d = d >> 1; e++; # If Part # } # else # { # d = d << 1; e--; # Else Part # } # # i++; # # Reg Usage: a, $8; b, $9; c, $10; d, $11; e, $12; i, $13 ## Condition # # Compute condition. # add $16, $8, $9 # $16 = a + b slt $17, $10, $16 # $17 = c < a + b # # Branch based on condition. # beq $17, $0, ELSEPART nop ## If Part # sra $11, $11, 1 # d = d >> 1 j LINEX addi $12, $12, 1 # e++; ## Else Part # ELSEPART: sll $11, $11, 1 # d = d << 1 addi $12, $12, -1 # e-- # Done with the if/else LINEX: addi $13, $13, 1 # i++ ## CTIs for Loop # # - Branch and jump. # - Distances small to medium # - Frequently encountered. # :Example: # # Typical for loop. # # for ( i = a - 5; i < b + c; i = i + d ) x = x ^ ( x >> 1 ); ## Initialization Test Increment Body # # Reg Usage: a, $8; b, $9; c, $10; d, $11; x, $12; i, $13 ## Initialization # addi $13, $8, -5 # i = a - 5 j TEST nop LOOP: ## Body # sra $16, $12, 1 # $16 = x >> 1 xor $12, $12, $16 # x = x ^ $16 ## Increment # add $13, $13, $11 # i = i + d ## Test TEST: add $16, $9, $10 # $16 = b + c Note: Can be moved out of loop. slt $17, $13, $16 # i < $16 bne $17, $0, LOOP nop ## CTIs for Switch # # - Direct and Indirect Jump. # - Distances small to medium. # - Occasionally encountered. # :Example: # # Switch statement # # Indirect jump, jr used to jump to correct case. # # If cases are dense (consecutive or almost consecutive) compiler will # create a dispatch table of case statement addresses. In this example # the cases, 1, 2, 3, are dense. # # switch ( t1 ) { # case 1: t0++; break; # case 2: t0--; break; # case 3: t0=>1; break; # } # s2 = t0 & s3; .data ## Dispatch table, holding address of case statements. DTABLE: .word CASE0 .word CASE1 .word CASE2 .word CASE3 .text ## Suppose we want to go to case 2 (t1 = 2) la $t5, DTABLE sll $t6, $t1, 2 ## t6 = 8 add $t6, $t6, $t5 # Compute dispatch table address. lw $t7, 0($t6) # Load address of case statement. jr $t7 # Use jr to jump to case statement. nop CASE1: j ENDCASE addi $t0, $t0, 1 CASE2: j ENDCASE addi $t0, $t0, -1 CASE3: j ENDCASE srl $t0, $t0, 1 ENDCASE: and $s2, $t0, $s3