#Program demonstrate the creation of the 
#AR in the context of the Fibonacci Sequence
	.data
N:	.word 8      		#Fib(N)	
	.text
	

	move $fp,$sp		#create the initial AR dummy frame
	addi $sp,$sp,-8		#won't save old fp because there isn't one
	
	lw $a0, N		#initialize n
	jal Fib_0		#call Fib(n)
	move $t1, $v0		#store result of function
	
	move $a0, $t1  		#Print result to show it works
	li $v0, 1
	syscall
	
	li $v0, 10
	syscall 			
			
Fib_0:
	sw $ra, ($fp)		#save ra in the AR
	sw $s1, ($sp)		#store the $s registers we are using.
	sw $s2, -4($sp)	
	addi $sp, $sp, -8	#adjust sp to TOP
	
	
	beq $a0,1, Fib_3    	#test if N is = 1,  base case
	beq $a0,0, Fib_2	#test if N is = 0,  base case
	
	#n-1 function call
	sw $a0, ($sp)		#save a0 onto stack
	addi $sp, $sp, -12	#create space for ra and old fp
	sw $fp, 4($sp)		#store previous fp
	move $fp,$sp   		#set fp to point to stored ra
	addi $fp,$fp,8
	
	subi $a0,$a0,1       	#setup parameter n-1
	jal Fib_0
	move $s1,$v0		#store return value
	
	lw $a0,4($fp) 		#restore a0
	move $sp,$fp		#set sp to fp
	lw $fp, -4($fp)		#restore old fp 
	addi $sp,$sp,4		#set sp to TOP of previous AR

									
	#n-2 function call																										
	sw $a0, ($sp)		#save a0 onto stack
	addi $sp, $sp, -12	#create space for ra and old fp
	sw $fp, 4($sp)		#store previous fp
	move $fp,$sp   		#set fp to point to stored ra
	addi $fp,$fp,8
	
	subi $a0,$a0,2		#set up parameter n-2																																					
	jal Fib_0																											
	move $s2,$v0
	
	lw $a0,4($fp) 		#restore a0
	move $sp,$fp		#set sp to fp
	lw $fp, -4($fp)		#restore old fp 
	addi $sp,$sp,4		#set sp to TOP of previous AR
		
	b Fib_4			#branch to non trivial return case

Fib_2:				#return 0
	li $v0,0		#base case
	b Fib_5
Fib_3:				#return	a 1
	li $v0,1		#base case
	b Fib_5
Fib_4:
	move $v0, $s1		#add fib(n-1) and fib(n-2)
	add $v0, $v0, $s2	#put in o/p register
																																																																																																																																																																																																																																																																																	
Fib_5:				#Start Procedure return																																																																																																																																																																																																																																																																																																																																																																													
	addi $sp,$sp,8		#restore s registers
	lw $s1,($sp)
	lw $s2, -4($sp)	
	lw $ra, ($fp)		#restore ra from AR
	jr $ra