Selanjutnya dari main()

main() selanjutnya melakukan beberapa pekerjaan yaitu mencetak integer dan mencetak faktorialnya.

                          # print( b )
         lw     $a0,4($fp)        # load b into $a0
         li     $v0,1             # print integer service
         syscall                                  
                                  # end the print line
         li     $v0,4             #   print string service
         la     $a0,lf            #   address of line feed
         syscall

Akhirnya main() mengakhiri dengan epilog

                
                                  # epilog
                                  #   1. No return value         
         add     $sp,$fp,8        #   2. $sp = $fp + space_for_variables       
                                  #   3. No S registers to pop      
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #                                    
         jr      $ra              # return to OS 

Data yang ada di "prompt" tidak disimpan ke dalam stack.

                       
         .data
prompt1: .asciiz "enter an int:"
prompt2: .asciiz "factorial is:"
lf:      .asciiz "\n"

Quest 21: Kenapa data variabel a dan b berbeda dengan data yang ada di prompt1 dan prompt2 ?
Jawab: a dan b adalah data yang hanya aktif saat subroutine dipanggil dan tidak aktif setelah kembali ke caller dengan begitu a dan b disimpan ke dalam stack
prompt1 dan prompt2 adalah data yang aktiv saat program berada di main memory, karenanya penyimpanannya ada di memory bagian penyimpanan data.

Isi dari main()

Bagian selanjutnya dari main(). Service SPIM untuk angka 4 dan 5 adalah untuk menampilkan string dan untuk membaca integer. Integer yang dimasukkan oleh user secara konvensi masuk ke dalam register $v0, kemudian disimpan sebagai variabel a yang ada di stack.

                         # write("enter an int:")
         li     $v0,4             #   print string service
         la     $a0,prompt1       #   address of prompt
         syscall
                                  # read( a )
         li     $v0,5             #   read integer service
         syscall                  #   $v0 gets the integer
         sw     $v0,0($fp)        #   save in variable a

Kode selanjutnya mengerjakan b = fact(a). Hal ini dikerjakan dengan cara mengikuti protokol pemanggilan subroutine, dan menyimpan nilai hasil ke dalam b.

                           # subroutine call: b = fact( a )
                                  #   1. No T registers to push
         lw      $a0,0($fp)       #   2. Put argument into $a0
         jal     fact             #   3. Jump and link to subroutine
         
                                  # return from subroutine 
                                  #   1. No T registers to restore
                                  
         sw     $v0,4($fp)        # b = fact( a )

Prolog main()

Berikut adalah main routine dari pseudo code dan prolog. Perhatikan bahwa di sini kita menggunakan 2 variabel.

#  main()
#  {
#    int a, b;                      // a: 0($fp),  b: 4($fp)
#    write("enter an int:")
#    read( a );
#    b = fact( a );
#    write("factorial is:")
#    print( b );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
                                  #   3. No S registers to push
         sub     $fp,$sp,8        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp

Rantai Aktifasi

Jika subroutine fact() dipanggil dengan argumen yang nilainya lebih besar dari 1 maka dia akan memanggil dirinya sendiri dengan argumen baru. Ini adalah aktifasi baru dengan code yang sama. Ini bukanlah masalah karena data untuk aktifasi pertama dari fact() telah di-push ke dalam stack. Aktifasi baru kini menggunakan stack baru dari frame stack data.

Jika aktifasi yang pertama mendapat kontrol kembali, maka dia akan menggunakan data yang sudah berada di tumpukan stack paling atas. Proses ini diilustrasikan seperti gambar di bawah. Tiap-tiap aktivasi direpresentasikan dengan lingkaran hjau. Tiap-tiap aktivasi ini bekerja dengan menggunakan datanya masing-masing yang berada di tumpukan frame stack. Tiap-tiap aktivasi ini tidak saling mengganggu satu sama lain.

#  int fact( int n )
#  {
#    if ( n <= 1 )
#      return 1;
#    else
#      return n*fact(n-1);
#  }

Setiap lingkaran dari rantai aktivasi ini merepresentasikan aktivasi dari subroutine. Angka yang mendampingi panah ke bawah adalah argumen yang diberikan dan angka yang mendampingi panah ke atas adalah nilai yang dikembalikan.

Tiap-tiap satu lingkaran dalam rantai ini bersesuaian dengan satu frame stack yang ada di sampingnya. Saat pekerjaan ini selesai maka frame stack akan kembali memendek ke main dan rantai program pun juga memendek.

Contoh Program: Faktorial(N)

Contoh program kita selanjutnya adalah menyuruh user memasukkan interger, kemudian membaca integer tersebut dan mencetak faktorial dari interger tersebut. Berikut adalah gambaran output yang dihasilkan oleh program berikut pseudo-code nya.

#  main()
#  {
#    int a, b;  // a: 0($fp),  b: 4($fp)
#    write("enter an int:")
#    read( a );
#    b = fact( a );
#    write("factorial is:")
#    print( b );
#  }

#  int fact( int n )
#  {
#    if ( n <= 1 )
#      return 1;
#    else
#      return n*fact(n-1);
#  }

Quest 17: Bagaimana cara menghitung faktorial?
Jawab: misal faktorial 5

fact(5) == 5*fact(4)
        == 5*( 4*fact(3) )
        == 5*( 4*( 3*fact(2)) )
        == 5*( 4*( 3*(2*fact(1))) )
        == 5*( 4*( 3*(2*1)) )
        == 5*4*3*2*1
        == 120

Kembali ke main()

Di contoh ini, main() tidak menyimpan register T manapun. Tidak ada yang perlu dilakukan saat dia mendapatkan kembali kontrol selain menggunakan nilai yang di letakkan ke $v0 sebagai hasil dari subroutine mysub().

#  main()
#  {
#    int a;                      // a: 0($fp)
#    a = mysub( 6 );
#    print( a );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
                                  #   3. No S registers to push
         sub     $fp,$sp,4        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp

                                  # subroutine call
                                  #   1. No T registers to push
         li      $a0,6            #   2. Put argument into $a0
         jal     mysub            #   3. Jump and link to subroutine
         
                                  # return from subroutine 
                                  #   1. No T registers to restore
                                  
         sw     $v0,0($fp)        # a = mysub( 6 )
        
                                  # print a
         lw     $a0,0($fp)        # load a into $a0
         li     $v0,1             # print integer service
         syscall                                  
                                  # epilog
                                  #   1. No return value         
         add     $sp,$fp,4        #   2. $sp = $fp + space_for_variables       
                                  #   3. No S registers to pop      
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #                                    
         jr      $ra              # return to OS 

Perhatikan kode di bawah, nilai yang tersimpan di $v0 dicopy ke variabel a yang berada di stack

Pada kalimat selanjutnya code akan bekerja menyalin nilai a di stack yang sudah memegang nilai $v0, ke dalam $a0 untuk kemudian dilakukan pencetakan nilai ini menggunakan service dari SPIM. Sekali lagi sebenarnya melakukan hal ini tidak perlu melibatkan stack, tetapi lagi-lagi kompiler yang tidak optimal mungkin melakukan hal semacam ini.

Kompiler yang optimal mungkin memproduksi code yang lebih efisien daripada code di atas.

Kompiler optimal mungkin akan memerikasa source kode dan menulis ulang source tersebut menjadi sebuah kalimat yang lebih efisien. Misalnya mengubah source code main() menjadi tanpa variabel a

main()
 {
   print(  mysub( 6 ) );
 }

Subroutine Epilog

Epilog dari sebuah subroutine akan menyiapkan nilai yang akan dikembalikan ke caller. Dia kemudian mengembalikan register dan stack ke tempatnya milik caller agar nanti bisa dipakai lagi oleh caller. Akhirnya kontrol kembali ke caller.

#  int mysub( int arg )
#  {
#    int b,c;                     // b: 0($fp)
#                                 // c: 4($fp)
#    b = arg*2;
#    c = b + 7;
#    
#    return c;  
#  }
         .text
         .globl  mysub
mysub:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
         sub     $sp,$sp,4        #   3. Push register $s1
         sw      $s1,($sp)
         sub     $fp,$sp,8        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine     
         mul     $s1,$a0,2        #     arg*2
         sw      $s1,0($fp)       # b = "   "
         
         lw      $t0,0($fp)       # get b
         add     $t0,$t0,7        #     b+7
         sw      $t0,4($fp)       # c = "  "
         
                                  # epilog
         lw      $v0,4($fp)       #   1. Put return value in $v0        
         add     $sp,$fp,8        #   2. $sp = $fp + space_for_variables
         lw      $s1,($sp)        #   3. Pop register $s1
         add     $sp,$sp,4        #          
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #            
         jr      $ra              #   6. return to caller 

Perhatikan bahwa code yang diperlukan untuk body sebuah subroutine di sini hanya sepanjang 5 kalimat, sementara total dari seluruh code menjadi 22 kalimat gara-gara konvensi linkage. Subroutine linkage membuatnya menjadi boros.

Quest 14: apa yang musti dilakukan oleh caller setelah mendapatkan kontrolnya kembali?
Jawab: dia musti merestore register T yang di awal-awal telah dia simpan sendiri

Menggunakan Variabel

Subroutine ini menggunakan dua variabel, jadi dialokasikan ruang sepanjang 8byte untuk mereka.

#  int mysub( int arg )
#  {
#    int b,c;                     // b: 0($fp)
#                                 // c: 4($fp)
#    b = arg*2;
#    c = b + 7;
#    
#    return c;  
#  }
         .text
         .globl  mysub
mysub:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)

         sub     $sp,$sp,4        #   3. Push register $s1
         sw      $s1,($sp)

         sub     $fp,$sp,8        #   4. $fp = $sp - space_for_variables

         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine    
                                   
         mul     $s1,$a0,2        # arg*2
         
         sw      $s1, ( )     # b = "   "
         
         lw      $t0, ( )     # get b
         
         add     $t0,$t0,           # b+7
         
         sw      $t0, ( )     # c = "  "
         
         . . . . .

         jr      $ra              # return to caller 

Program ini menjadi tidak efisien. Sebenarnya tidak perlu menyetore b kemudian meloadnya. Sebuah kompiler yang tidak optimal melakukan hal seperti ini, bagaimanapun juga.

Quest 12: Fill in the blank. Anggap bahwa variabel b terletak sejauh 0 dari $fp dan variabel c terletak sejauh 4 dari $fp

Prolog untuk mysub()

Tentu saja mysub() harus diawali dengan prolog. Ada dua variabel, jadi alokasi akan dilakukan ke dalam stack.

#  int mysub( int arg )
#  {
#    int b,c;                     // b: 0($fp)
#                                 // c: 4($fp)
#    b = arg*2;
#    c = b + 7;
#    
#    return c;  
#  }
         .text
         .globl   
 :
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)

              , ,       #   3. Push register $s1
         
              , 

         sub    $fp,$sp,    #   4. $fp = $sp - space_for_variables

         move   $sp,$fp           #   5. $sp = $fp
         
         . . . .     

         jr      $ra              # return to caller 

Subroutine ini seharusnya ditulis tanpa melibatkan $s1. Perhatikan code di atas

Memanggil Subroutine

Pada titik ini kita telah "mengkompilasi" tiga baris pertama dari program bahasa "C" ke dalam bahasa assembly. Selanjutnya program akan memanggil subroutine mysub(), silahkan lihat kode selanjutnya di bawah ini:

#  main()
#  {
#    int a;
#    a = mysub( 6 );
#    print( a );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)

                                  #   3. No S registers to push

         addiu   $fp,$sp,4        #   4. $fp = $sp + space_for_variables

         move    $sp,$fp          #   5. $sp = $fp

                                  # subroutine call
                                  #   1. No T registers to push
         li      $a0,6            #   2. Put argument into $a0
         jal     mysub            #   3. Jump and link to subroutine
         
                                  # return from subroutine   
         
         . . . .     
         
                                  # epilog
         jr      $ra              # return to OS 

main()

Di bawah ini adalah code untuk main(), dengan beberapa kotak kosong. Aturan untuk prolog subroutine disalin dari atas.

#  main()
#  {
#    int a;
#    a = mysub( 6 );
#    print( a );
#  }

         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
                                  #   3. No S registers to push
                                  
         sub      , ,     #   4. $fp = $sp - space_for_variables
         

            $sp,$fp         #   5. $sp = $fp
         

                                  # subroutine call

         . . . .
         
                                  # return from subroutine   
         
         . . . .     
         
                                  # epilog
         jr      $ra              # return to OS 

Quest 9: Fill in the blank seperti yang dimaksud oleh koment

Contoh Program

Jumlah register yang dimiliki MIPS (atau processor yang lain) tidak membatasi banyaknya variabel yang dimiliki oleh subroutine. Sebanyak variabel yang kamu inginkan selama bisa dialokasikan ke dalam stack. Berikut adalah contoh program yang ditulis dalam bahasa C:

main()
{
  int a;
  a = mysub( 6 );
  print( a );
}

int mysub( int arg )
{
  int b,c;
  
  b = arg*2;
  c = b + 7;
  
  return c;  
}

Bagi operating system, main() adalah subroutine. Jika main() mendapat kontrol maka dia harus mengikuti aturan di bawah "subroutine prolog".

Quest 8: berapa banyak ruangan yang musti diberikan stack untuk menyimpan variabel-variabel yang ada di main() ?
Jawab: 4byte untuk sebuah variabel a