## LSU EE 3755 -- Spring 2002 -- Computer Organization
#
## Note Set 10 -- Control-Transfer Instructions
# Time-stamp: <10 April 2002, 12:26:08 CDT, koppel@sol>
## Contents
#
# Types of Control-Transfer Instructions
# A Simple Jump Instruction
# A Branch Instruction
# More Branch Instructions
# More Jump Instructions
# Procedure Call Example
# Typical CTI Uses
## References
#
# :PH: Patterson & Hennessy, "Computer Organization & Design"
# :Mv1: MIPS Technologies, "MIPS32 Architecture for Programmers Vol I: Intro"
# :Mv2: MIPS Technologies, "MIPS32 Architecture for Programmers Vol II: Instr"
################################################################################
## 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
#
# All of the CTIs covered here are delayed.
# (Traps are not delayed.)
#
# 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
################################################################################
## A Simple Jump Instruction
# :PH: 3.5
# :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
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.
################################################################################
## A Branch Instruction
# :PH: 3.5
# :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
bne $9, $10, LINE
addi $8, $8, 1 # Offset computed from this instruction.
addi $8, $8, 2
LINE:
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
################################################################################
## More Branch Instructions
# :PH: 3.5
# :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: 3.5
# :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 # Jump and link register.
# $31 <- 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: 3.6
# :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.
.globl __start
__start:
addi $a0, $0, 12 # Set value to triple.
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, 2001 # 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: 3.5
# 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 ) { d = d >> 1; e++; } else { d = d << 1; e--; }
# i++;
#
# Reg Usage: a, $8; b, $9; c, $10; d, $11; e, $12; i, $13
add $16, $8, $9 # $16 = a + b
slt $17, $10, $16 # $17 = c < a + b
beq $17, $0, ELSEPART
nop
sra $11, $11, 1 # d = d >> 1
addi $12, $12, 1 # e++;
j LINEX
nop
ELSEPART:
sll $11, $11, 1 # d = d << 1
addi $12, $12, -1 # e--
LINEX:
addi $13, $13, 1 # i++
# :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