Basis Dua ke Basis Sepuluh

Ingat lagi bahwa X^-n artinya 1/Xⁿ. Maka 2^-2 = 1/4 dan 2-3 = 1/8.

Untuk mengkonversi dari basis dua ke basis sepuluh, lakukan saja perhitungan seperti di atas. Berikut adalah 100,001 biner yang dikonvert ke desimal.

1	0	0	,	1	0	1
1×22	0×21	0×20	,	1×2-1	0×2-2	1×2-3
1×4 +	0×2 +	0×1+	,	1×0.5 +	0×0.25 +	1×0.125
4 +	0 +	0 +	,	0.5 +	0 +	0.125
		4	,	625

Selama kamu mengitung, tetap jaga posisi dari bilang bulat dan posisi dari bilangan pecahan. Pada gambar di atas, baris atas adalah basis dua dan baris bawah adalah hasil konversinya ke basis sepuluh, sementara baris yang di tengah disebut polinomial.

Quest 5: terjemahkan 0,11₂ menjadi basis 10

Jawab: 0,11₂ = 0×1 + 1×(0,5) + 1×(0,25) = 0,75

Notasi Posisi untuk Basis Dua

Notasi posisi juga bisa dipakai menggunakan selain basis sepuluh. Berikut adalah contoh menggunakan basis dua:

1	0	0	,	1	0	1
1×22	0×21	0×20	,	1×2-1	0×2-2	1×2-3

Saat sebuah basis tertentu tidak dicantumkan di dalam angka, maka digit ke 0 digunakan sebagai penanda pecahan. Tanda koma "," di tempat tersebut disebut binary point.

Secara umum, sebenarnya tanda koma tersebut digunakan untuk memisahkan pecahan dengan bilangan bulat yang disebut radix point. Di Amerika pemisahan tanda pecahan ini biasanya menggunakan tanda titik "."

Quest 4: Cepat 1×2^-1 ? Jawab menggunakan desimal

Jawab:  1×2-1 = 1/(21) = 1/2 = 0,5

Notasi Posisi

Ini hanyalah notasi posisi dari angka desimal, yang tentu sudah kamu tahu sebelumnya. Koma desimal diletakkan di antara nilai kelipatan 10⁰ dan 10^-1.

3	5	7	,	2	8	4
3×102	5×101	7×100	,	2×10-1	8×10-2	4×10-3

Notasi 357,284 artinya 3 kali 100 + 5 kali 10 + 7 kali 1 + 2 kali 0,1 + 8 kali 0,01 + 4 kali 0,001.

Quest 3: Cepat 3/10 + 1/100 menggunakan notasi koma
Jawab: 0,31

BAB 29 — Pecahan dalam Biner

Sejauh ini kita telah melakukan perhitungan matematika dalam bentuk integer, baik yang two complement maupun yang unsigned integer. Bab ini akan mulai membahas tentang matematika floating point bisa dilakukan di MIPS.

Topik:

• Notasi posisional dengan pecahan
• Konversi pecahan antara basis dua dengan basis sepuluh
• Representasi fixed point (koma tetap)
• Presisi yang terbatas dari pecahan biner (fixed point dan floating point)
• Bagaimana "seper sepuluh" tidak bisa diekspresikan menggunakan biner
• Program loop yang berbahaya

Quest 2: Di dalam angka desimal 12,6, berapakah faktor 10 dari tiap angka:

digit 1?

digit 2?

digit 6?

Jawab: digit 1 = 10¹

digit 2 = 10⁰

digit 6 = 10^-1

Komplit fact()

Berikut adalah code fact() yang telah lengkap:

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # 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,0        #   4. $fp = $sp - space_for_variables (==0)
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         b       epilog    

recurse:                          # else
                                  #  return n*fact(n-1)
         sub     $a0,$s1,1        #     n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine

         mul     $v0,$v0,$s1      # n*fact(n-1)
                            
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         add     $sp,$fp,0        #   2. $sp = $fp + space_for_variables (==0)
         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 

Quest 28: Adakah perbedaan konvensi linkage subroutine yang mengalir rekursif dengan yang tidak?
Jawab: Tidak ada, keduanya sama-sama berjalan dengan cara yang sama, yang spesial dari rekursif adalah dia memanggil dirinya sendiri.

Memanggil Recursive

         . . . . . .

recurse:                          # else
                                  #   return n*fact(n-1);
         sub     $a0,$s1,1        #     argument0 = n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine

         mul     $v0,$v0,$s1      # n*fact(n-1)

epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Rekursi telah diimplementasikan di sini menggunakan: (1) operasi mesin standar yang menggunakan eksekusi, testing dan percabangan. dan (2) runtime stack.

Ini adalah contoh abstraksi tingkat baru yang berada di atas tingkat dasar. Apakah menurut kamu ini adalah ide penting dalam ilmu komputer?

Quest 27: Bahasa pemrograman FORTRAN IV tidak mendukung rekursi. Apakah mungkin untuk membuat program rekursi menggunakan FORTRAN IV?
Jawab: Bisa, FORTRAN memiliki eksekusi yang berurutan, testing dan percabangan, seperti halnya semua bahasa. Untuk menulis sebuah program rekursif maka programmer harus mengalokasikan dan mengelola run-time stack, seperti dalam bahasa assembly. Bahasa modern tingkat tinggi melakukan hal ini secara otomatis.

Selanjutnya dari fact()

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         . . . . . .
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         b       epilog  

recurse:                          # else
                                  #   return n*fact(n-1);
         sub     $a0,$s1,1        #     argument0 = n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine
                                  #
                                  #   value is returned in $v0

         mul      ,  ,    # n*fact(n-1)

epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Percabangan dari if jika $s1 tidak sama dengan 1 atau kurang dari 1, adalah melompat ke symbolic address recurse yang melakukan pekerjaan n*fact(n-1). Dia pertama kali mengerjakan n-1 yang disimpan ke $a0 kemudian baru mengalikan.

Setelah itu dia memanggil fact(), tidak perlu kuatir untuk memanggil ulang karena setiap aktiuvasi akan menggunakan stacknya sendiri-sendiri.

Setelah memanggil fact(), register $v0 memegang return value (nilai hasil) dan register $s1 memegang nilai n.

Body dari fact()

Berikut adalah bagian dari isi subroutine fact().

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         . . . . . .
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         
         b        

recurse:                          # else
                                  #   return n*fact(n-1);
         . . . . . . 
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Argumen yang berada di $a0 diamankan ke register $s1 karena kemungkinan nantinya register $a0 akan berubah. Secara subroutine ini menggunakan $s1 maka $s1 diamankan ke dalam stack saat prolog.

Operasi if di sini bekerja untuk mengecek apakah isi dari argumen $a0 yang sudah dipindah ke $s1 bernilai 1 atau kurang. Jika iya maka dia akan meletakkan nilai 1 ke register $v0 yang nantinya register ini akan digunakan sebagai accumulator. Jika tidak maka cabang lain akan diberlakukan.

Entry Point (Titik Masuk)

Sekarang ke dalam subroutine. Alamat pertama dari subroutine ini disimbolkan dengn nama fact. Tentu saja nama fact hanyalah simbol yang dipakai oleh assembler, kenyataannya symbol ini akan diterjemahkan oleh assembler menjadi suatu letak atau alamat yang  berada di main storage runtime. Alamat ini ditentukan oleh assembler, linker dan loader.

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # 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,0        #   4. $fp = $sp - space_for_variables (==0)
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine
        . . . . . .
                            
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         add     $sp,$fp,0        #   2. $sp = $fp + space_for_variables (==0)
         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 

Simbol fact adalah simbol global (juga disebut simbol eksternal) sehingga assembler, linker dan loader bisa menggunakan simbol tersebut untuk menunjuk tempat yang sama di main memory.

Sebuah lokasi samacam fact ini yang mejadi target sebuah pemanggilan subroutine, disebut entry point. Kadang kala sebuah subroutine mempunyai beberap entri point, tiap-tiapnya berkaitan dengan fungsi yang berbeda-beda.

Quest 24: Apakah simbol global selalu meunjuk ke sebuah entry point?
Jawab: Tidak, bisa juga simbol global menunjuk ke suatu data yang diperlukan untuk operasi.

Komplit main()

Kembali ke contoh program yang kita buat.

#  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

                                  # 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
                        
                                  # subroutine call
                                  #   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 )
        
                                  # write("factorial is:")
         li     $v0,4             #   print string service
         la     $a0,prompt2       #   address of prompt
         syscall
                                  # print( b )
         lw     $a0,4($fp)        # load a 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
                                  # 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
prompt1: .asciiz "enter an int:"
prompt2: .asciiz "factorial is:"
lf:      .asciiz "\n"

Quest 23: Subroutine apa yang dipanggil oleh main()?

Kelas Storage

Ada 3 tempat di dalam memory yang bisa kita letakkan data: di data section (dideklarasikan dengan .data dalam bahasa assembly), di runtime-stack, dan di heap.

Subroutine boleh memiliki data yang tersimpan di section .data. Di bahasa pemrograman tingkat tinggi, seperti C, type penyimpanan ini disebut static.

Variabel yang disimpan dengan cara mengalokasikan run-time stack, biasanya disebut dengan variabel otomatis. Ini karena mereka secara otomatis di push dan di pop ketika subroutine masuk dan keluar. Biasanya kalau orang bilang "variabel" bisa mengacu ke "variabel otomatis".

Variabel yang tempat penyimpanannya ada di heap biasa disebut variabel dinamik. Bab 33 dari kuliah ini akan membahas tentang heap. Heap adalah tempat memory bagi object (menggunakan instruksi new kalau di Java atau C++). Di bahasa C memory dinamik dialokasikan menggunakan operasi malloc (atau sejenisnya).

Heap ada di atas data segment. Kalau variabel dinamik dialokasikan maka data segment akan tumbuh ke atas ke arah stack.

Quest 22: (mengulang) apa yang akan terjadi jika stack dan heap semakin membesar dan membesar?

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

Diagram

Aturan ini adalah rumit. Secara garis besar cara kerjanya sama dengan bab sebelumnya tentang konvensi linkage berbasis stack. Tapi sekarang, prolog subroutine menumpuk sejumlah ruangan di dalam stack untuk digunakan sebagai variabel lokal, dan di epilog mereka menge pop out.

Inilah gambarannya. Gambar menunjukkan bagian dari subroutine linkage, tugas-tugas dasarnya adalah sebagai berikut:

Memanggil subroutine: Tumpuk register T yang memegang nilai yang perlu diamankan. Letakkan argumen di register A. jal ke subroutine

Prolog: Tumpuk $ra dan $fp milik caller, tumpuk register S. Inisialisasi $fp dan $sp milik diri sendiri

Body: Normal code, kecuali jika dia memanggil subroutine lainnya maka aturan akan berlaku. Register T dan register A boleh digunakan secara bebas sebagaimana S yang telah diamankan sebelumnya. Akses ke variabel lokal menggunakan distance($fp).

Epilog: Letakkan nilai hasil ke dalam register V. Reset $sp melewati ruangan variable. Pop register S, pop $fp milik caller dan $ra. Kembali ke caller dengan jr $ra

Mendapatkan kontrol kembali: Pop out register T yang telah diamankan

Konvensi Linkage berbasis Frame

Konvensi linkage asli memperbolehkan berbagai jenis type object untuk ditumpuk ke dalam frame stack. Aturan di bawah ini menganggap bahwa stack hanya menyimpan nilai 32bit. Ada fitur dari konvensi linkage asli yang tidak dimiliki konvensi linkage yang sedang kita pelajari berikut ini.

Memanggil subroutine (dilakukan oleh caller):

1. Tumpuk register $t0 - $t9 yang memegang nilai yang sebaiknya disimpan. Tumpuk dengan urutan numerik
2. Letakkan nilai argumen ke $a0 - $a3
3. Panggil subroutine dengan jal

Prolog subroutine (dilakukan oleh subroutine):

1. Tumpuk $ra (selalu)
2. Tumpuk $fp milik caller
3. Tumpuk $s0 - $s7 yang mungkin diubah oleh subroutine
4. Inisialisasi untuk $fp milik sendiri dengan cara $sp - alokasi untuk variabel (misal variabel di sini adalah sepanjang 4 address atau 32bit)
5. Inisialisasi stack pointer untuk sejajar dengan frame pointer ($sp = $fp)

Subroutine body:

1. Pada titik ini stack akan kelihatan seperti gambar di atas
2. Subroutine boleh memakai register T, V, A dan S yang sebelumnya sudah diamankan di prolog
3. Subroutine memanggil variabel lokal dengan cara distance($fp)
4. Subroutine mungkin menge push dan menge pop nilai yang ada di stack menggunakan $sp
5. Jika subroutine memanggil subroutine yang lain maka aturan akan dilakukan dengan cara yang sama

Subroutine Epilog (dilakukan di akhir subroutine):

1. Letakan nilai hasil ke $v0 - $v1
2. $sp = $fp + kuota address untuk variabel
3. Pop $s0 - $s7
4. Pop $fp milik caller menggunakan $sp
5. Pop $ra (selalu)
6. Kembali ke caller dengan jr $ra

Mendapatkan kontrol kembali dari subroutine (dilakukan oleh caller):

1. Pop register $t0 - $t9 yang diamankan sebelumnya oleh caller

Contoh Code

Misalkan kita mempunyai rumus berikut ini
a = b + i + j;

variabel a, b, i dan j masing masing sudah tersimpan di dalam stack seperti pada gambar

Seperti ini lah kemungkinan bagamana compiler menerjemahkan rumus di atas:

lw    $t0,8($fp)     # get b

lw    $t1,4($fp)     # get i

lw    $t2,0($fp)     # get j

addu  $t3,$t0,$t1    # b + i

addu  $t3,$t3,$t2    # b + i + j

sw    $t3,12($fp)    # a =    

Register tertentu yang pemnyimpan nilai sementara ini adalah bebas.

Quest 5: Bermain kompiler, coba terjemahkan soal berikut ini menjadi bahasa assembly

a = a + 1;

Jawab:

lw      $t0,12($fp)    # get a

addiu   $t0,$t0,1      # a + 1

sw      $t0,12($fp)    # a = 

Frame Pointer

Register $30 telah dipersiapkan secara konvensi software untuk digunakan sebagai frame pointer. Di dalam assembler extended dia dinamai dengan $fp. Saat sebuah subroutine start pertama kali, frame pointer dan stack pointer memiliki address yang sama.

Ketika subroutine aktiv, frame pointer menunjuk ke tumpukan teratas stack. Tapi stack maupun stack pointer akan berubah-ubah seiring pengerjaan aritmatika, sehingga kalau frame pointer ikut berubah maka akan menyulitkan bagi programmer utk mendapatkan nilai yang tetap dari suatu alamat variabel.

Untuk membuat hal ini mudah bagi compiler maupun programmer assembly maka frame pointer di tetapkan untuk tidak bergerak saat subroutine aktiv. Sehingga variable yang tersimpan di stack selalu mempunyai jarak yang sama terhadap frame pointer yang tidak bergerak.

Di dalam prolog subroutine, frame pointer milik caller beserta stack pointer dan register S, ditumpuk ke stack. Sehingga subroutine bebas membuat ruang untuk variabelnya sendiri di dalam stack dan meletakkan frame pointer ke tumpukan paling atas.

Variabel

Bahasa pemrograman mempunyai variabel global. Juga, sebuah program blok yang ruwet boleh juga menggunakan variabel yang berasal dari luar blok. Mari lewati saja hal ini dan langsung ke implementasi variabel lokal. Ditail mungkin bisa diperdalam di kuliah kompiler atau bahasa pemrograman.

Gambar di bawah ini menunjukkan stack frame dari sebuah subroutine yang aktiv. Seperti biasa (untuk kuliah ini) tiap item di dalam stack ini adalah sepanjang 4 byte yang mengisi 4 address panjang.

Seperti sebelumnya, caller menumpuk register T yang nantinya akan direstore setelah kontrol kembali. Calee menumpuk register S yang mungkin akan berubah.

Pada contoh di bawah, ruang yang disediakan dari stack untuk mengimplementasikan variabel lokal a, b, i dan j. Tiap-tiap variabel ini akan menempati 32bit panjang. Biasanya variabel akan kita devinisikan sebagai integer.

Sebuah variabel adalah lokasi di dalam run-time stack yang digunakan untuk menyimpan data. Nilai dari variabel ini mungkin akan berubah sebagaimana program dieksekusi.

Variabel a ada di dalam tumpukan stack, tidak ada bentuk lain dalam mengimplementasikan variabel. Di dalam program, memanipulasi variabel adalah dilakukan dengan menggunakan register untuk meload dan menyetore nilai yang adal di dalam ruang stack. Bagaimanapun, variable adalah yang di stack bukan register.

Quest 3: Saat stack frame di pop out, apa yang terjadi dengan variable?
Jawab: Secara konsep, variabel sudah tidak ada lagi di dalam stack saat mereka sudah di pop out.

Implementasi Variabel Lokal

Di dalam bahasa tingkat tinggi, variabel lokal diimplementasikan sebagai sebuah lokasi yang ada di run-time stack. Tiap kali subroutine aktiv, lokasi baru untuk variabel ditumpuk ke stack. Bagian stack yang menyimpan nilai ini biasa disebut frame stack atau pencatat aktivasi. Sebuah frame pointer berfungsi memegang alamat dari stack fram untuk subroutine.

Saat subroutine kembali ke caller, stack frame pop out dari stack. Dengan begitu, variabel lokal hanya eksis sebagai lokasi memori saat subroutine aktiv. Subroutine disebut aktiv apabila subroutine tersebut sedang dikerjakan, atau sedang dipanggil.

Format dari stack frame yang digunakan oleh bahasa MIPS processor adalah rumit. Ada banyak situasi yang musti diatasi dan banyak optimasi di dalamnya. Ini membutuhkan compiler untuk membuatnya benar. Tulisan ini hanya akan menggambarkan stack frame yang sederhana.

Bagian terpenting dari memahami ini adalah mengetahui apa itu variabel lokal, yang secara umum: adalah sebuah lokasi di dalam run-time stack. Ini adalah gagasan penting di dalama komputer sains, salah satu yang akan kamu ulang berkali-kali saat kamu mempelajari ilmu-ilmu lanjutan.

BAB 28 — Konvensi Linkage berbasis Frame, Variabel dan Rekursi

Bab ini mengembangkan lebih jauh terhadap konvensi linkage berbasis stack untuk membuat konvensi linkage berbasis frame. Sebuah stack frame adalah bagian dari run-time stack yang berfungsi menyimpan data-data yang diperlukan untuk subroutine.

Topik:

• Stack frame dan frame pointer
• Variabel lokal
• Konvensi linkage berbasis frame sederhana
• Optimasi compiler
• Rekursi
• Class penyimpanan; statik, automatik, dinamik
• Entry point

Quest 1: Apa yang dimaksud variabel lokal dalam bahasa tingkat tinggi?

Jawab: Variabel lokal adalah nilai yang hanya aktif saat subroutine diaktifkan. Sebagai contoh variabel lokal yang ada di bahasa C: b dan c adalah variabel lokal.

int mysub( int arg )

{

  int b, c;  

  

  b = arg*2;

  c = b + 7;

  return c;  

}

(Bahasa pemrograman yang lain mempunyai prinsip yang sama, implementasinya dilakukan dengan syntax yang berbeda)

Sejarah Bahasa Pemrograman

Sebenarnya.. ini bukanlah hal yang gampang. Buktinya, lihat saja pada sejarah komputer. Diperlukan beberapa dekade sebelum bahasa pemrograman modern stabil. Yang pertama bisa dikatakan penting adalah Algol diciptakan pada tahun 1960. Algol stabil dalam subroutine linkage berbasis stack. Tapi tidak pernah cukup memuaskan.

Pascal (diciptakan pada tahun 1974) adalah sebuah momen penting. Dia menjadi begitu terkenal dan menggunakan ide subroutine berbasis stack ini (yang mana disebut procedure dan function). Bahasa pemrograman bisa diklasifikasikan sebagai "Sebelum Pascal" dan "Sesudah Pascal".

Tapi mari kita kembali ke MIPS processor (yang diciptakan 10 tahun setelah pascal).

Quest 10: apakah MIPS instruksi optimal untuk pemanggilan dan pengembalian subroutine?

Jawab: Yes

Rantai Aktivasi Linear (lurus)

Sebuah subroutine tertentu (katakanlah A) dapat memanggil subroutine lain dalam suksesi (misal B, kemudian X, kemudian Y, dan Z). Tapi dalam satu saat dia hanya bisa menautkan satu subroutine di bawahnya. Hampir di semua bahasa pemrograman modern pemanggilan subroutine adalah menggikuti konvensi berbasis stack ini. Subroutine yang sedang berjalan aktiv adalah berada di akhir sebuah rantai dari rantai aktivasi yang kembali ke operating sistem.

Run-time stack mempunyai bentuk yang sama dengan rantai aktivasi. Tumpukan stack teratas adalah untuk subroutine yang berjalan aktiv. Saat subroutine selesai maka data di stack pop out.

Stack adalah terakhi ditumpuk pertama dicabut

Subroutine adalah terakhir dipanggil pertama diselesaikan

Ketika subroutine mencapai akhir pekerjaannya, dia kembali ke caller, dan rantai pun memendek. Caller tadi mungkin memanggil lagi subroutine yang lain, dan rantai pun memanjang lagi.

Selama program memiliki banyak subroutine dieksekusi, rantai aktivasi ini akan memanjang dan memendek seperti yo-yo. Akhirnya rantai ini benar-benar habis, setelah program mengembalikan kontrol ke operating system.

Quest 9: apakah kamu merasa kalau otak kamu seperti yo-yo?

Sekumpulan Pemanggilan Subroutine

Diagram di bawah menunjukkan main routine terhubung ke subroutine A, yang mana dia terhubung ke subroutine B yang juga terhubung ke subroutine C. Subroutine-subroutine ini terhubung seperti kancing-kancing yang terhubung dengan 2 benang. Kontrol dilewatkan melalui call ke prolog, dan melalui epolog kembali ke caller. Semua subroutine yang tertaut seperti rantai mempunyai 5 bagian yang sama (call, prolog, body, epilog, gain kontrol) kecuali subroutine terakhir yang hanya menggunakan prolog dan epilog saja.

Tiap kali subroutine ditambahkan ke rantai, maka semakin banyak data yang ditumpuk ke dalam stack. Jika dilihat dari proses terpanjang, di akhir rantai stack menyimpan banyak data yang merupakan data dari tiap-tiap subroutine termasuk main. Subroutine yang sedang aktif adalah subroutine yang datanya berada di tumpukan ter atas dari stack (dalam kasus ini adalah subroutine C).

Setiap kali subroutine kembali ke caller maka setiap itu pula data di-pop out dari stack.

Setiap subroutine sama sekali tidak mengetahui apapun tentang stack selain stack nya sendiri. Dia bekerja menge-push data ke stack (yang merupakan data pendahulunya) kemudian meng-popnya kembali (agar bisa digunakan lagi oleh pendahulunya). Dia tidak bekerja menggunakan stack milik orang subroutine lain begitu juga dia tidak tahu berapa dalam level stack yang sedang terjadi sekarang.

Kadang kala orang menyebut "memanggil subroutine" dengan panggilan "mengaktivkan subroutine" Setiap-kancing-kancing yang ada di gambar dan tiap-tiap bagian dari stack adalah bersesuaian dengan sebuah pengaktivan subroutine.

Diagram

Aturan ini kelihatan rumit. Di bawah ini adalah gambar yang meunjukkan empat buah bagian subroutine linkage. Rangkuman tiap-tiap bagiannya adalah sebagai berikut:

Pemanggilan subroutine: Mengepush semua register T yang mungkin akan dipakai setelah memanggil subroutine. Letakkan argumen ke register A yang akan dipakai nilainya bersama-sama tetapi tidak berubah. Panggil subroutine dengan jal.

Prolog: Jika subroutine ini memanggil subroutine yang lain, tumpuk $ra. Tumpuk semua register S yang mungkin akan berubah di subroutine ini.

Body: normal code, kecuali dia harus mengikuti aturan konvensi jika dia memanggil subroutine yang lain. register T dan register A boleh digunakan secara bebas seperti halnya register S karena telah disimpan sebelumnya di saat prolog.

Epilog: Letakan nilai hasil ke register V. Pop register S. Pop $ra, kembali ke caller jr $ra

Kembalikan kontrol: Pop register T yang di awal telah di Push.

Quest 7: apakah ada batasan mengenai seberapa dalam level dari pemanggilan subroutine ini?
Jawab: No

Konvensi Linkage Berbasis Stack

Konvensi linkage sederhana bisa dirombak menjadi konvensi linkage berbasis stack. Ini bukanlah konvensi resmi. Bagaimanapun kamu bisa menggunakan konvensi ini untuk project kecil berbahasa assembly, karena cara ini belum begitu rumit dan hampir sudah cukup. Jika kamu ingin menautkan routine bahasa assembly ke program berbahasa C atau menggunakan routine sebagai library, maka kamu perlu menggunakan konvensi yang full resmi. (namun kamu belum bisa melakukan hal ini di SPIM). Berikut adalah aturan sederhananya:

Pemanggilan subroutine (dilakukan oleh caller):

1. Push ke dalam stack register $t0 - $t9 yang berisi nilai yang perlu disimpan. Takutnya subroutine mungkin akan mengubah nilai ini.
2. Letakkan nilai argument / nilai yang boleh dishare ke dalam $a0 - $a3
3. Penggil subroutine dengan intruksi jal

Subroutine prolog (dilakukan di awal-awal subroutine):

1. Jika subroutine mungkin memanggil subroutine yang lain, push $ra ke stack
2. Push ke dalam stack register yang ada di $s0 - $s7 ke dalam stack yang mungkin subroutine akan mengubahnya

Bagian tengah subroutine:

1. Subroutine boleh mengubah register T, register A atau register S.
2. Jika subroutine memanggil subroutine lainnya maka penyimpanan register ke stack akan dilakukan dengan cara yang sama

Subroutine epilog (dilakukan sesaat sebelum subroutine kembali ke callernya):

1. Letakkan nilai hasil ke $v0-$v1
2. Pop dari dalam stack dengan urutan kebalik register $s0 - $s7 yang sebelumnya di-push di prolog
3. Pop return address dari stack ke $ra
4. Kembali ke caller dengan instruksi jr $ra

Mengembalikan kontrol (dari subroutine, dilakukan oleh caller):

1. Pop dari stack (dalam urutan kebalik) register $t0 - $t9 yang sebelumnya telah di-push.

Untuk optimasi kecepatan, Beberapa subroutine ada yang menggunakan sedikit register untuk menyimpan nilai sementara. Mereka boleh menggunakan register T tanpa harus repot menyimpan dan merestore. Sebuah subroutine yang membutuhkan banyak sumber daya register atau memerlukan nilai itu di lewatkan ke subroutine lainnya mungkin akan menggunakan register S tapi mereka harus membayar kerepotan dalam menyimpan dan merestore ke dalam stack.

Menge-Push dan Menge-Pop Register

Berikut adalah aturannya: Jika sebuah subroutine diduga akan mengubah isi dari register S, dia pertama-tama harus menge-push nilai register ke stack. Sebelum kembali ke caller dia harus sudah menge-pop nilainya dari stack menuju ke asal registernya.

Berikut adalah contoh penggalan program. Subrotine subB memanggil subC yang mana menggunakan dua register S.

subB:
         sub    $sp,$sp,4    # push $ra
         sw     $ra,($sp)

         . . . .

         jal    subC         # call subC
         nop

         . . . .
         
         lw     $ra,($sp)    # pop return address
         add    $sp,$sp,4
         jr     $ra          # return to caller
         nop

# subC expects to use $s0 and $s1         
# subC does not call another subroutine
#       
subC:             
         sub    $sp,$sp,4    # push $s0
         sw     $s0,($sp)
         sub    $sp,$sp,4    # push $s1
         sw     $s1,($sp)

         . . . .             # statements using $s0 and $s1

         lw     $s1,($sp)    # pop s1
         add    $sp,$sp,4
         lw     $s0,($sp)    # pop s0
         add    $sp,$sp,4

         jr     $ra          # return to subB 
         nop       

The registers are popped in the opposite order that they were pushed.

Masalah Register

Pada konvensi linkage sederhana sebelumnya, register $s0 - $s7 tidak boleh diubah oleh subroutine. Tapi keterbatasan seperti ini akan menimbulkan masalah jika subroutine memanggil subroutine yang lain.

Misal main memanggil subA dan subA memanggil subB. subA tidak boleh menyimpan nilai ke $s0 -$s7, tapi nilai yang ada di $t0 - $t9 mungkin bercampur dengan subB secara subA dan subB sama-sama subroutine. Efeknya membuat subroutine tidak bisa saling berbagi register, dan ini tidak baik.

Solusinya adalah subA boleh menggunakan $s0 - $s7 tetapi dia musti menumpuk dulu nilai sebelumnya ke dalam stack, nanti setelah subA kembali ke callernya dia mengembalikan lagi nilai yang telah ditumpuk di stack kembali ke register.

Quest 4: Apakah tidak apa-apa menumpuk $s0 - $s7 dan $ra ke dalam stack?
Jawab: Yes, hanya saja pastikan urutan menge-push dan menge-pop nilai untuk kembali ke tempatnya dengan benar.

Rantai Subroutine

Sekarang mari kita lihat pada contoh mengenai subroutine yang memanggil subroutine yang lain. Sebuah subroutine yang memanggil subroutine yang lain harus menumpuk return address ke dalam stack. Saat dia akan kembali ke callernya maka dia menge-pop return address tersebut dari stack.

Di gambar, main dipanggil oleh OS. Selama main memakai kontrol dia menumpuk $ra ke dalam stack (step 1). Main bekerja sebentar dan kemudian memanggi subA. subA langsung menumpuk $ra ke dalam stack (step 2). Sekarang return address yang digunakan subA untuk kembali ke main sedang ditumpuk ke stack.

Selanjutnya subA memanggil subB yang mana langsung saja subB menumpuk $ra ke dalam stack (step 3). Return address buat subB untuk kembali sekarang ada di tumpukan stack.

Sekarang subB memanggil subC, subC tidak memanggil lagi subroutine sehingga $ra tidak perlu ditumpuk lagi. subC bekerja sebentar dan akhirnya kembali ke caller dengan intruksi jr $ra (step 5).

Sekarang subB  mendapat kontrol lagi. subB kembali ke callernya dengan cara mengepop return address dan mengeksekusi jr $ra (step 6).

Sekarang subA dapat kontrol lagi, return address yang dia perlukan ada di atas stack. subA kembali ke caller dengan cara mengepop stack ke $ra dan melakukan jr $ra (step 7).

Akhirnya main mendapat kontrol kembali, setelah melakukan tugasnya dia mengembalikan kontrol ke OS dengan menge-pop stack ke $ra dan menggunakan instruksi jr $ra (step 8).

Menge-Push Return Address

Untuk kembali ke caller, subroutine harus memiliki return address yang benar di dalam $ra saat intruksi jr dilaksanakan. Tetapi alamat ini tidak harus terus menerus menetap di dalam $ra selama subroutine berjalan. Lebih baik menyimpan nilai ini ke suatu tempat dan sewaktu-waktu bisa dikembalikan lagi.

Di dalam gambar, operating system memanggil main. Return address untuk kembali ke operating system ada di $ra. Selama dia mendapatkan kontrol, main menge-push return address ke dalam stack (step 1). Return addres yang akan digunakan main untk kembali ke operating system kini sedang ditumpuk ke dalam stack.

Push dan pop yang berada di gambar adalah secara konsep. Code yang sebenarnya di dalam melaksanakan hal ini adalah dengan cara biasa.

Setelah menge-push return address, main melakukan komputasi beberapa dan kemudian memanggil subC menggunakan intruksi jal (step2). dan akhirnya mengubah isi dari $ra menjadi return address untuk subC kembali ke main, beruntungnya return address untuk main kembali ke operating system telah disimpan dengan aman di dalam stack.

subC kemudian mendapat kontrol untuk mengerjakan bagiannya. Karena dia tidak memanggil subroutine yang lain, subC tidak melakukan tindakan untuh mengubah $ra, dan tidak perlu menumpuknya ke dalam stack. Saat subC ingin kembali ke main maka dia hanya perlu menggunakan intruksi jr $ra (step 3).

Setelah kontrol kembali ke main, kemudian dia bekerja sebentar dan akhirnya dia harus mengembalikan kontrol ke OS dengan cara menge-pop return addres dari stack baru kemudian melakukan instruksi jr $ra (step 4).

Exception handler adalah salah satu cara untuk mengembalikan kontrol ke OS, tapi untuk sekarang kita tidak menggunakan itu dlu.

BAB 27 — Konvensi Linkage berbasis Stack

Konvensi linkage sederhana di bab sebelumnya tidak memiliki beberapa fitur bahasa tingkat tinggi. Bab ini akan menambahi beberapa fitur dalam konvensi linkage baru yang berbasis stack.

Topik:

• Menyimpan register ke dalam stack
• Konvensi linkage berbasi stack
• Prolog dan epilog tentang pemanggilan subroutine
• Pemanggilan dan kembali ke pemanggil
• Pemanggilan subroutine yang digabungkan dan rantai aktivasi
• Sejarah linkage konvension
• Contoh program, mengubah inputan user menjadi kapital.

Program Komplit

Berikut adalah program yang telah selesai. Simbol global telah dibuat. Pelajari bagaimana setiap module menggunakan direktive .text dan .data untuk mendeskripsikan bagiannya.

# addthree.asm --- read in three integers and print their sum
#
# This program uses simple linkage.  
#
# Settings: Load delays  ON;  Branch delays ON
#           Trap file    ON;  Pseudoinstructions ON   
#

         .text
         .globl  main
main:
         jal     pread            # read first integer
         nop                      #  
         move    $s0,$v0          # save it in $s0

         jal     pread            # read second integer
         nop                      #  
         move    $s1,$v0          # save it in $s1

         jal     pread            # read third integer
         nop                      #  
         move    $s2,$v0          # save it in $s2
         
         addu    $s0,$s0,$s1      # compute the sum
         addu    $a0,$s0,$s2
         
         li      $v0,1            # print the sum
         syscall
         
         li      $v0,10           # exit
         syscall


# pread -- prompt for and read an integer
#
# on entry:
#    $ra -- return address
#
# on exit:
#    $v0 -- the integer

         .text
         .globl  pread
pread:   
         la    $a0,prompt        # print string
         li    $v0,4             # service 4
         syscall
        
         li    $v0,5             # read int into $v0
         syscall                 # service 5
        
         jr    $ra               # return
         nop                     #  
        
         .data
prompt:
         .asciiz "Enter an integer: "

Berikut adalah tampilan jendela konsol setelah program dijalankan.

Quest 15: Bisakan alamat .phread digunakan oleh program yang lain?
Jawab: boleh asalkan diikuti dengan konvensi linkage sederhana

Simbol Global

Ingat lagi bahwa subroutine dan main routine tidak boleh menggunakan nama yang sama untuk memory dengan alamat yang berbeda, ini artinya penamaan memori untuk keduanya tidak boleh sama, karena hal ini bisa merusak gagasan tentang modularitas.

Tapi kadang alamat yang sama juga digunakan oleh kedua subroutine maupun main routine.

Simbol atau nama yang sama digunakan oleh kedua modul ini disebut simbol global. Simbol global biasanya adalah entry point, simbol yang tidak global disebut local simbol. Di bahasa assembly MIPS alamat-alamat yang diperuntukkan untuk global biasanya ditaruh di tempat yang mengikuti direktiv .global. Beberapa bahasa ada yang menyebutnya sebagai variabel gobal.

Di dalam bahasa C, alamat yang tersedia untuk modul yang lain disebut simbol eksternal.

Source code SPIM berada di dalam sebuah file, yang mencakup semua sobroutine-subroutine. Bagaimanapun, di dalam pengembangan software profesional tiap-tiap subroutine bisa saja diletakkan ke dalam file-file yang berbeda. Tiap-tiap file ini akan menempati address symboliknya masing-masing, alamat ini adalah global dan boleh direferensi oleh software-software yang lain.

Main Program (main routine)

Setelah subroutine dibuat, kamu sekarang bisa menggunakannya untuk dipanggil dari main routine. Berikut adalah main programnya:

         .text
         .globl  main

main:
         jal     pread            # read first integer
         nop                      #  
         move    $s0,$v0          # save it in $s0
         jal     pread            # read second integer
         nop                      # 
         move    $s1,$v0          # save it in $s1
         jal     pread            # read third integer
         nop                      #  
         move    $s2,$v0          # save it in $s2
         
         addu    $s0,$s0,$s1      # compute the sum
         addu    $a0,$s0,$s2      # result in $a0
         
         li      $v0,1            # print the sum in $a0
         syscall
         
         li      $v0,10           # exit
         syscall

Perintah untuk memasukkan integer

Subroutine memerintahkan user untuk menginputkan interger. integer ini disimpan ke dalam register $v0. Berikut adalah awal subroutinenya:

# pread -- prompt for and read an integer
#
# on entry:
#    $ra -- return address
#
# on exit:
#    $v0 -- the integer

pread:   
         la    $a0,prompt        # print string
         li    $v0,4             # service 4
         syscall
        
         li    $v0,5             # read int into $v0
         syscall                 # service 5
        
         jr    $ra               # return
         nop                     # branch delay slot
        
         .data
prompt:
         .asciiz "Enter an integer: "

Contoh Program

Mari kita membuat sebuah program yang menggunakan konvensi linkage sederhana. Programnya adalah membaca tiga buah input yang diinputkan oleh user dan mengkomputasikannya. Rencananya adalah:

                # baca integer pertama
                # baca integer kedua
                # baca integer ketiga
                # hitung jumlahnya
                # tulis hasilnya

Quest 11: lihat pada rencana, manakah yang cocok untuk dijadikan sebagai subroutine?
Jawab: baca integer

Gambaran Ringkas

Gambar di bawah ini menunjukkan main memanggil mysub. Dua argumen yang dilewatkan ke subroutine berada di dalam register $a0 dan $a1.

Di dalam gambar, argumen tersebut diload menggunakan intruksi move dan li, instruksi yang lain juga boleh digunakan.

Konvensi linkage sederhana sangat terbatas untuk beberapa permasalahan. Konvensi linkage yang lebih maju akan di bahas di bab berikutnya.

CALLER melewatkan argumen-argumen ke sebuah subroutine dengan cara menyimpannya ke dalam register. Ini adalah satu-satunya cara bagaimana sebuah data bisa dilewatkan ke dalam subroutine. Subroutine juga mengembalikan nilai dari hasil pekerjaannya dia dalam bentuk register. Ini adalah satu-satunya cara bagaimana sebuah subroutine menimbalbalikkan nilai kepada CALLER. Subroutine tidak boleh menggunakan memory yang dipakai oleh CALLER. dan CALLER juga tidak boleh menggunakan memory yang digunaka oleh subroutine.

Konvensi Linkage Sederhana

Berikut adalah contoh dari calling convention. Konvensi ini sederhana dan tidak cocok untuk program yang lebih rumit. Tapi ini mengilustrasikan ide yang bisa digunakan untuk program yang kompleks selanjutnya. Mari kita sebut saja sebagai konvensi linkage sederhana. Aturannya adalah:

1. Sebuah subroutine dipanggil dengan intruksi jal
2. Sebuah subroutine tidak boleh memanggil subroutine yang lain
3. Subroutine kemmbali ke CALLER dengan cra jr $ra
4. Register yang digunakan adalah sebagai berikut:
• $t0 - $t9 — Subroutine bebas menggunakan register ini
• $s0 - $s7 — Subroutine tidak boleh mengubah isi dari register ini
• $a0 - $a3 — Register ini berisi argumen tentang subroutine. Subroutine boleh mengubahnya
• $v0 - $v1 — Register ini berisi nilai yang dihasilkan oleh subroutine
5. Main routine mengembalikan kontrol ke user menggunakan exception handler

Secara subroutine tidak boleh memanggil subroutine yang lain maka program yang kita buat akan menggunakan main routine yang memanggil beberapa subroutine dan setiap subroutine harus kembali ke main routine.

Quest 9: Pertimbangkan ini, kenapa sebuah subroutine tidak boleh memanggil subroutine yang lain?

Jawab: karena register yang digunakan untuk menyimpan return address hanya satu sehingga kalau subroutine memanggil subroutine maka address untuk kembali ke main routine bisa hilang.

Penggunaan Register

Salah satu tujuan dari penulisan subroutine adalah, untuk membuat modul yang mandiri dengan sumberdaya yang masih bebas / tersisa.

Isu yang lain adalah bagaimana data dilewatkan dan dikeluarkan dari subroutine. Sementara main routine atau routine-routine lainnya mungkin juga sedang membutuhkan tempat data itu (register).

Dengan menggunakan konvensi software, register dinamai dengan berbagai maksud dan tujuan.

• $t0 - $t9 — Subroutine bebas menggunakan register ini
• $s0 - $s7 — Subroutine tidak boleh mengubah isi dari register ini
• $a0 - $a3 — Register ini berisi argumen tentang subroutine. Subroutine boleh mengubahnya
• $v0 - $v1 — Register ini berisi nilai yang dihasilkan oleh subroutine