## LSU EE 4720 -- Spring 2025 -- Computer Architecture
#
## Implementation of C Control Flow Constructs


## Contents
#
#

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



################################################################################
## Implementation of C Control Flow Constructs

# :PH: 3.5
# C/C++ Programming Review: https://en.cppreference.com/w/

 ## Some C Control Flow Constructs
#
# :Syntax:   if ( COND ) then IFPART; else ELSEPART;
# :Example:  if ( a < b ) c++; else d++;
#
# :Syntax:   for ( INIT;  TEST;  INCR )  BODY;
# :Example:  for ( int i=0;  i<10;  i++ ) printf(" i = %d\n", i );
#
# :Syntax:   switch ( COND ) { case C1: PART1;  case C2: PART2; .. }
# :Example:  switch ( c ) { case 65: chose_A(); break;  case 66: ch_B(); .. }



################################################################################
## Assembler for if/else Statement
#
# :Syntax:   if ( COND ) then IFPART; else ELSEPART;
# :Example:  if ( a < b ) c++; else d++;
#
#  - Use branch and jump.
#  - Distances small.
#  - Very frequent.

# :Example:
#
#   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
        addi $12, $12, 1    # e++;
        j LINEX
        nop

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


################################################################################
## Assembler for for Loops
#
# :Syntax:   for ( INIT;  TEST;  INCR )  BODY;
# :Example:  for ( int i=0;  i<10;  i++ ) printf(" i = %d\n", i );
#
# - Branch and jump.
# - Distances small to medium
# - Frequently encountered.
#
# :Example:
#
# 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


################################################################################
## Assembler for Switch Statements
#
# :Syntax:
#   switch ( CONDITION ) {
#    case CONSTANT_1: STATEMENT_1;
#    case CONSTANT_2: STATEMENT_2;
#    ...
#    default: STATEMENT_D;
#   }
#
# :Example:
#   switch ( t1 ) {  // Case constants are *sparse*. Bad.
#    case 1: t0++; break;
#    case 20: t0--; break;
#    case 300: t0 = t0 >> 1; break;
#    default: assert( false );
#   }
#
#
#

#
# If cases are sparse (case constants have large gaps), then compiler
# will use a series of if statements.
#
# If cases are dense (consecutive or almost consecutive) compiler will
# create a dispatch table of case statement addresses.


 ## Switch with Sparse case Constants
# :Syntax: switch statement, sparse cases.
#
# switch ( t1 ) {  // Case constants are *sparse*. Bad.
#  case 1: t0++; break;
#  case 20: t0--; break;
#  case 300: t0 = t0 >> 1; break;
#  default: assert( false );
# }

# Suppose t1 is in register $t1
        addi $t9, $0, 1
        beq $t1, $t9, case_1
        addi $t9, $0, 20
        beq $t1, $t9, case_20
        addi $t9, $0, 300
        beq $t1, $t9, case_300
        nop
        j case_default
        nop


case_1: 
        addi $t0, $t0, 1;
        j ENDCASE
        nop
        
case_20:
        addi $t0, $t0, -1;
        j ENDCASE
        nop
case_300:
        sra $t0, $t0, 1
        j ENDCASE
        nop
case_default:
        addi $a0, $0, 0
        jal assert
        nop
        j ENDCASE
        nop


# :Example: switch statement, dense cases.
#
# switch ( t1 ) {  // Case constants are *dense*. Good.
#  case 1: t0++; break;
#  case 2: t0--; break;
#  case 3: t0 = t0 >> 1; break;
#  case 5: t0 = t0 << 1; t2++; break;
# }
# s2 = t0 & s3;

        .data
 ## Dispatch table, holding address of case statements.
DTABLE:
        .word CASE0_IF_THERE_WAS_ONE_BUT_THERE_ISNT
        .word CASE1
        .word CASE2
        .word CASE3
        .space 4
        .word CASE5
        .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
CASE5:
        sll $t0, $t0, 1
        j ENDCASE
        addi $t2, $t2, 1

ENDCASE:
        and $s2, $t0, $s3