## LSU EE 3755 -- Fall 2001 -- Computer Organization
#
## Note Set 10 -- Control-Transfer Instructions

# Time-stamp: <7 November 2001, 17:44:26 CST, koppel@sol>

These notes are outdated. 
The lectures page contains links to the latest versions of these notes.

## 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