View on GitHub

JST

By Janelle Blankenburg, Shubham Gogna, and Terence Henriod
UNR CS 660: Compiler Construction

Running
Tests
Files
Source
Download this project as a .zip file Download this project as a tar.gz file

Constant Folding

Input

const int C = 4 + 4;

int main() {
    // expect to find a li with 14 in the assembly instructions
    // since we have constant folding working correctly
    int n = C - 2 + 4 * 2;

    // expect to see the 14 printed to show its loaded into n correctly
    print_int(n);

    return 0;
}

MIPS


  .macro SAVE_T_REGISTERS
  # brace yourself for a long, unrolled loop...
  sw           $t0,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t1,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t2,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t3,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t4,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t5,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t6,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t7,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t8,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $t9,    ($sp)
  subiu        $sp,      $sp,        4
  .end_macro

  .macro RESTORE_T_REGISTERS
  # brace yourself for a long, unrolled loop...
  addiu        $sp,      $sp,        4
  lw           $t9,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t8,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t7,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t6,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t5,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t4,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t3,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t2,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t1,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $t0,    ($sp)
  .end_macro

  .macro SAVE_SPILL_MEM
  # brace yourself for a long, unrolled loop...
  lw           $a3, SPILL_MEMORY
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 4
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 8
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 12
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 16
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 20
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 24
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 28
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 32
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 36
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 40
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 44
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 48
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 52
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 56
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  lw           $a3, SPILL_MEMORY + 60
  sw           $a3,    ($sp)
  subiu        $sp,      $sp,        4
  .end_macro

  .macro RESTORE_SPILL_MEM
  # brace yourself for a long, unrolled loop...
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 60
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 56
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 52
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 48
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 44
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 40
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 36
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 32
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 28
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 24
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 20
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 16
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 12
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 8
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY + 4
  addiu        $sp,      $sp,        4
  lw           $a3,    ($sp)
  sw           $a3, SPILL_MEMORY
  .end_macro

  .macro CALLEE_FUNCTION_PROLOGUE (%variable_size)
  # set $fp to the proper spot by recovering the value from $a0
  add          $fp,      $a0,    $zero
  # allocate stack space for variables ($sp = $sp - space for variables)
  li           $a0,        4
  mulu         $a1,      $a0, %variable_size
  sub          $sp,      $sp,      $a1
  .end_macro

  .macro CALLEE_FUNCTION_EPILOGUE
  # de-allocate the memory used for local variables and parameters
  add          $sp,      $fp,    $zero
  # jump back to the caller
  jr           $ra
  .end_macro

  .macro CALLER_FUNCTION_PROLOGUE
  # caller should save it's own $ra, $fp, and registers
  sw           $ra,    ($sp)
  subiu        $sp,      $sp,        4
  sw           $fp,    ($sp)
  subiu        $sp,      $sp,        4
  # caller pushes registers and spill memory onto the stack as well
  SAVE_T_REGISTERS()
  SAVE_SPILL_MEM()
  # save the value of $sp here into $a0 as temporary storage until the arguments are moved
  # $fp needs to stay where it's at while the arguments are copied after this macro
  add          $a0,      $sp,    $zero
  .end_macro

  .macro CALLER_FUNCTION_EPILOGUE
  # recover the spill memory and the stored registers
  RESTORE_SPILL_MEM()
  RESTORE_T_REGISTERS()
  # recover the caller's $fp and $ra
  addiu        $sp,      $sp,        4
  lw           $fp,    ($sp)
  addiu        $sp,      $sp,        4
  lw           $ra,    ($sp)
  .end_macro

  .macro __LAND (%lhs, %rhs)
  beqz        %lhs, __LAND_FALSE
  beqz        %rhs, __LAND_FALSE
  li           $a2,        1
  j       __LAND_END

  __LAND_FALSE:
  li           $a2,        0

  __LAND_END:
  .end_macro

  .macro __LOR (%lhs, %rhs)
  beqz        %lhs, __LOR_TRUE
  beqz        %rhs, __LOR_TRUE
  li           $a2,        0
  j       __LOR_END

  __LOR_TRUE:
  li           $a2,        1

  __LOR_END:
  .end_macro


  .data
  SPILL_MEMORY: .space 64
  C: .word 8

  .text
  add          $fp,      $sp,    $zero
  add          $a0,      $fp,    $zero
  jal         main
  j       PROG_END

  main:
  CALLEE_FUNCTION_PROLOGUE(1)
  la           $t0,    ($fp)
  li           $t1,       14
  sw           $t1,    ($t0)
  CALLER_FUNCTION_PROLOGUE()
  lw           $t0,    ($fp)
  sw           $t0,    ($sp)
  sub          $sp,      $sp,        4
  jal     print_int
  CALLER_FUNCTION_EPILOGUE()
  add          $t0,      $v0,    $zero
  li           $t0,        0
  add          $v0,      $t0,    $zero
  CALLEE_FUNCTION_EPILOGUE()
  CALLEE_FUNCTION_EPILOGUE()

  print_char:
  CALLEE_FUNCTION_PROLOGUE(0)
  # load $v0 with the value for the print char syscall
  li           $v0,       11
  # the first (and only) argument is the value to print
  lw           $a0,    ($fp)
  syscall
  CALLEE_FUNCTION_EPILOGUE()

  print_int:
  CALLEE_FUNCTION_PROLOGUE(0)
  # load $v0 with the value for the print int syscall
  li           $v0,        1
  # the first (and only) argument is the value to print
  lw           $a0,    ($fp)
  syscall
  CALLEE_FUNCTION_EPILOGUE()

  print_string:
  CALLEE_FUNCTION_PROLOGUE(0)
  # load $v0 with the value for the print string syscall
  li           $v0,        4
  # the first (and only) argument is the base address of the null terminated ascii string
  la           $a0,    ($fp)
  syscall
  CALLEE_FUNCTION_EPILOGUE()

  print_float:
  CALLEE_FUNCTION_PROLOGUE(0)
  # load $v0 with the value for the print float syscall
  li           $v0,        2
  # the first (and only) argument is the base address of the null terminated ascii string
  lwc1        $f12,    ($fp)
  syscall
  CALLEE_FUNCTION_EPILOGUE()

  PROG_END:
  add          $a0,      $v0,    $zero
  li           $v0,       17
  syscall

Output

14

3AC (Three-Address Code)


  .data
  GLOBLDECL      , C              , .word          , 8
  .text
  JAL            , main           , -              , -
  BR             , PROG_END       , -              , -
  main:
  PROCENTRY      , 4              , -              , -
  LA             , ireg_00000     , ($FP)          , -
  LI             , ireg_00001     , 14             , -
  STORE          , ireg_00001     , (ireg_00000)   , 4
  KICK           , ireg_00001     , -              , -
  KICK           , ireg_00000     , -              , -
  CALL_PROC      , print_int      , 0              , -
  LOAD           , ireg_00003     , ($FP)          , 4
  STORE          , ireg_00003     , ($SP)          , 4
  SUB            , $SP            , $SP            , 4
  KICK           , ireg_00003     , -              , -
  JAL            , print_int      , -              , -
  END_PROC       , 0              , -              , -
  ADD            , ireg_00002     , $RV            , $ZERO
  KICK           , ireg_00002     , -              , -
  LI             , ireg_00004     , 0              , -
  RETURN         , ireg_00004     , -              , -
  ENDPROC        , -              , -              , -
  PROG_END: