## LSU EE 4720 -- Spring 2017 -- Computer Architecture
#
## MIPS Control Flow Examples

# Time-stamp: <20 January 2017, 9:22:19 CST, koppel@cyc.ece.lsu.edu>

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


## Objectives
#
# Understand the relationship between high-level looping constructs
# and other control flow constructs and assembly language code.



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


 ## CTIs for if/else Statement
#
#  - Use branch and jump.
#  - Distances small.
#  - Very frequent.

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

        la $t5, DTABLE
        sll $t6, $t1, 2
        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