การแปลงภาษา C สำหรับฟังก์ชั่น Recursive

การคำนวณ Factorial สามารถใช้งานฟังก์ชั่น Recursive ได้ดังต่อไปนี้

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

จงเขียนเป็นภาษาแอสแซมบลีของ MIPS

ให้ตัวแปรพารามิเตอร์ n อยู่ในอาร์กูเมนต์รีจีสเตอร์ $a0 เมื่อฟังก์ชั่นเริ่มทำงานก็เริ่มจากการเก็บค่า $ra สำหรับ Return Address และ $a0 ลงในสแตก:

fact:
   addi $sp, $sp, -8 #adjust stack for 2 items
   sw $ra, 4($sp) # save the return address
   sw $a0, 0($sp) # save the argument n

เมื่อฟังก์ชั่น fact ถูกเรียกเป็นครั้งแรก คำสั่ง sw จะเก็บตำแหน่งของโปรแกรมที่เรียกฟังก์ชั่นสแตก จากนั้นคำสั่งต่อมาเป็นการตรวจสอบว่า n น้อยกว่าหนึ่งหรือไม่

slti $t0, $a0, 1 # test for n < 1
beq $t0, $zero, L1 # if n >= 1, go to L1

ถ้า n น้อยกว่า 1 ฟังก์ชั่น fact จะคืนค่า 1 โดยกำหนดให้ค่าใน value register $v0 มีค่าเท่ากับ 1 โดยการบวกค่าหนึ่งและรีจีสเตอร์ zero เข้าด้วยกัน และ jump ไปยัง return address

addi $v0, $zero, 1 # return 1
addi $sp, $sp, 8 # pop 2 items off stack
jr $ra # return to after jal

ก่อนที่เราจะทำการ pop 2 words ออกจากสแตก เราควรโหลดค่ามาเก็บไว้ก่อน แต่ในกรณีที่ n < 1 นั้น ค่า $a0 และ $ra ไม่มีการเปลี่ยนแปลงค่า จึงไม่จำเป็นต้องดำเนินการใดๆ

ในกรณีที่ n มีค่าไม่น้อยกว่าหนึ่ง เราจะทำการลดค่า n และเรียกฟังก์ชั่น fact อีกครั้งหนึ่งด้วยค่าอาร์กูเมนต์ที่ลดลงหนึ่ง

L1: addi $a0, $a0, -1 # n >= 1: argument get (n - 1)
    jal fact  # call fact with (n-1)

คำสั่งต่อมาเป็นคำสั่งหลังจากฟังก์ชั่น fact คืนค่ากลับมา หรือ return

lw $a0, 0($sp) # return from jal: restore argument n
lw $ra, 4($sp) # restore the return address
addi $sp, $sp, 8 # adjust stack pointer to pop 2 items

จากนั้นทำการคำนวณผลลัพธ์ใส่ในรีจีสเตอร์ $v0

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

และกลับไปยัง caller โดยการเรียกคำสั่ง

jr $ra # return to caller

การเก็บค่าตัวแปรในภาษา C นั้นแบ่งออกเป็นสองส่วนได้แก่ automatic และ static ในการใช้งานตัวแปรต่างๆ ที่อยู่ในฟังก์ชั่น นั้นเป็นการกำหนดตัวแปรแบบ automatic ที่จะมีการใชังาน stack และรีจีสเตอร์ ตามหลักการที่กล่าวมา ในส่วนของตัวแปรที่อยู่นอกฟังก์ชั่น และสามารถเข้าถึงใช้งานได้จากทุกๆ ฟังก์ชั่นเรียกว่า static variable โดยในคอมพิวเตอร์ MIPS จะกำหนดรีจีสเตอร์ อีกตัวหนึ่งเรียกว่า global register $gp สำหรับชี้ไปยังขัอมูลแบบ static