Can someone give me an example of how recursion would be done in ARM Assembly with only the instructions listed here (for visUAL)?
I am trying to do a recursive fibonacci and factorial function for class. I know recursion is a function that calls a function, but I have no idea how to simulate that in ARM.
https://salmanarif.bitbucket.io/visual/supported_instructions.html
In case the link doesn't work, I am using visUAL and these are the only instructions I can use:
This doesn't load an older value for R4, so R4 just doubles every time the function calls itself.
;VisUAL initializess all registers to 0 except for R13/SP, which is -16777216
MOV R4, #0
MOV R5, #1
MOV r0, #4
MOV LR, #16 ;tells program to move to 4th instruction
FIB
STMDB SP!, {R4-R6, LR} ;Stores necessary values on stack (PUSH command)
LDR R4, [SP] ;Loads older value for R4 from memory
ADD R4, R4, R5 ;Adds R5 to R4
STR R4, [SP], #8 ;stores current value for R4 to memory
MOV R5, R4 ;Makes R5 = R4
CMP R4, #144 ;If R4 >= 144:
BGE POP ;Branch to POP
MOV PC, LR ;Moves to STMDB(PUSH) statement
POP
LDMIA SP!, {R4-R6, LR} ;Pops registers off stack
END ;ends program
You need to use the stack, STMDB and LDMIA instructions. On real ARM tools with "unified" notation, they also have mnemonics PUSH and POP.
Fibonnaci and factorial are not great examples as they don't "need" recursion. But let's pretend they do. I'll pick Fibonacci as you don't have a MUL instruction!? You want to do something like this:
START
MOV R0, #6
BL FIB
END ; pseudo-instruction to make your simulator terminate
FIB ; int fib(int i) {
STMDB SP!, {R4,R5,R6,LR} ; int n, tmp;
MOV R4, R0 ; n = i;
CMP R0, #2 ; if (i <= 2) {
MOV R0, #1 ; return 1;
BLE FIB_END ; }
SUB R0, R4, #2 ; i = n-2;
BL FIB ; i = fib(i);
MOV R5, R0 ; tmp = i;
SUB R0, R4, #1 ; i = n-1;
BL FIB ; i = fib(i);
ADD R0, R0, R5 ; i = i + tmp;
FIB_END ; return i;
LDMIA SP!, {R4,R5,R6,PC} ; }
It should terminate with R0 containing fib(6) == 8. Of course this code is very inefficient as it repeatedly calls FIB for the same values.
The STM is needed so you can use registers r4,r5 because another function call can change r0-r3 and LR. Pushing LR and popping PC is like B LR. If you were calling C code you should push an even number of registers to keep SP 64-bit aligned (we don't really need to do that here; ignore R6).