#10072 - funkeejeffou - Tue Aug 26, 2003 2:54 pm
I'm having some problems implementing a recursive functiun. Basically my code does this :
dummy
cmp r0, #0
;do stuff
....
stmfd sp!, {r0, lr} ;r0 is a variable needed
bl dummy
ldmfd sp!, {r0}
cmp r0, #0
;do stuff
bl dummy
ldmfd sp!, {lr}
bx lr
;functiun end
;this is where we call the functiun the first time
mov r0, #0
bl dummy
Well it doesn't work. The only parameter I need here is r0, so I push it when I'll need it after a functiun return. lr is pushed once at the beginning so we will exit properly at the end of the functiun.
Does someone know what is wrong here?
If you know a good explanation of how implementing a recursive functiun in ASM, I'd appreciate the help.
Thanks
#10074 - Lupin - Tue Aug 26, 2003 3:35 pm
stmfd sp!, {r0, lr} ;r0 is a variable needed
you said lr is only pushed once, I dunno if lr has to be there...
The best way of implementing recursive functions is to use an simple loop instead ^^, actually an recursive function does exactly the same as an loop...
#10077 - torne - Tue Aug 26, 2003 3:48 pm
Is your function intended to be tail-recursive or not? If you don't know, tail recursion is when the last line of the function (if you consider something like C) is 'return resultOfCallingMyself()' or something similar - i.e. you only execute code on the way *down* the recursion.
A tail recursive function in assembler should look like this:
| Code: |
FunctionEntryPoint:
Push registers that you need to save, including lr if you need to call other functions
RecursiveReentryPoint:
Do the work that you need to do in each recursion
Test some termination condition; if not terminating, b RecursiveEntryPoint (not bl, you do not need to save the return address when using tail recursion)
Do final calculation if any, and leave the return value in the right place
Pop registers you saved, including lr
bx lr |
If you are intending to return straight to the function that called you (which is what tail-recursion normally does, and what I believe you are intending to call) then you must only push/pop lr once, not on every time around: you will be making further calls many times, but only returning once, so the pushes and pops won't balance out.
If your code is not intended to be tail-recursive, that is, you will be doing 'work' on the way back up:
| Code: |
FunctionEntryPoint:
Push registers you need to save between recursions, this ALWAYS includes lr
Do work for this iteration before the recursive call
Test if you need to recurse; if so, bl FunctionEntryPoint
Do work for this iteration after the recursive call
Pop registers
bx lr (will return up one level, or to the caller if no more recursions are on the stack)
|
You always do best to use tail recursion when possible (it is not always; see tree traversal for an example) as it uses a constant amount of stack space and requires less memory accesses per iteration.
If that's not clear enough, try posting your literal code rather than a dummy version; it frequently makes it easier to undersand what people are trying to do.
Torne
#10089 - sajiimori - Tue Aug 26, 2003 6:51 pm
Torne pretty much covered it, but as an aside, try writing some basic (or even emtpy) functions in C and see how your compiler handles recursion. In gcc, you would do "gcc -S -O0 sourcefile.c".
#10094 - funkeejeffou - Tue Aug 26, 2003 8:57 pm
My recursive functiun is in fact a binary tree traversal. You stop recursing when you find a leaf. Pretty easy in C, but not in ASM. In fact my functiun works cause the error wasn't from the code but from the compiler. Apparently goldroad doesn't appreciate these two things(why?):
cmp r1, #0
ldrnesh r2, [r3]
ldreqsh r2, [r3, #2]
and
tst r0, 0x80000000 ;0x80000000 = 1<<31 so it should work
my functiun does this in C :
var is a global variable wich is constant for a frame.
render_node(index)
{
if (var > node[index].value)
{
if (node[index].front is a node)
render_node(node[index].front)
else
render_leaf(node[index].front)
if (node[index].back is a node)
render_node(node[index].back)
else
render_leaf(node[index].back)
}
else
{
if (node[index].back is a node)
render_node(node[index].back)
else
render_leaf(node[index].back)
if (node[index].front is a node)
render_node(node[index].front)
else
render_leaf(node[index].front)
}
}
Here is my pseudo code in ASM :
render_node
;r4 = first node or leaf to recurse r5 =second node or leaf
;when calling render_node, r1 has the index of the node
;when calling render_leaf, r0 has the index of the leaf
;node[index].front >= 0 if node else it is a leaf and we inverse the bits
stmfd sp!, {r4, r5, lr}
cmp r4, #0
mvnlt r0, r4
bllt render_leaf
ldmfd sp!, {r4}
cmp r4, #0 ;on teste le bit 32
movge r1, r4
blge render_node
ldmfd sp, {r5}
cmp r5, #0 ;on teste le bit 32
mvnlt r0, r5 ;si bit32, alors on inverse
bllt render_leaf
ldmfd sp!, {r5}
cmp r5, #0 ;on teste le bit 32
movge r1, r5
blge render_node
ldmfd sp!, {lr}
bx lr
Can this be done better?
Is it tail recursive?
Is it code recursivity or a recursive functiun (I'm not sure anymore)?
Thanks for helping.
#10095 - torne - Tue Aug 26, 2003 9:44 pm
| funkeejeffou wrote: |
My recursive functiun is in fact a binary tree traversal. You stop recursing when you find a leaf. Pretty easy in C, but not in ASM. In fact my functiun works cause the error wasn't from the code but from the compiler. Apparently goldroad doesn't appreciate these two things(why?):
cmp r1, #0
ldrnesh r2, [r3]
ldreqsh r2, [r3, #2]
and
tst r0, 0x80000000 ;0x80000000 = 1<<31 so it should work |
The former should be valid. If Goldroad does not accept it then either it is buggy, or it wants a slightly different instruction syntax. For the former, try putting the conditional execution suffixes at the end (ldrsheq and ldrshne). The latter needs a #: tst r0, #0x80000000.
| funkeejeffou wrote: |
| ldmfd sp!, {r4} |
Reloading the values of r4 and r5 should not be neccecary. Functions which conform to the ARM procedure call standard are not permitted to overwrite the values of r4-r11.
I wouldn't write it that way, let's say. I would write a function which takes one argument, the address of a node, then processes each of its children separately.. but the way you have it should be fine. It's not tail recursive because a full tree traversal (where you visit every node, as opposed to a traversal where you only follow one branch at each level, such as when searching) cannot be made tail recursive. =)
Your program is using code recursion. Code recursion and recursive functions are the same thing. The other way is called data recursion, and for a tree traversal would involve putting the 'right' leaf of each node into a list/queue/stack, then processing the left node, until you run out of left nodes, at which point you get one node from the list/queue/stack and do it again. You wouldn't actually do data recursion for a tree traversal like this, it is very hard to manage.
Most tail recursive procedures are using data recursion; if you are searching a tree you can at each stage just update a register which contains the current node, then loop back to the top of your function. This gives you a recursive traversal (the same code is executed for each node) but without requiring any stack pushes/function calls.
#10097 - funkeejeffou - Tue Aug 26, 2003 11:48 pm
I don't get something about functiuns in ASM :
When I call a functiun by using bl, if this functiun uses all registers from r0 to r12, when it finishes (bx lr), the values previously contained (ie before the call of the functiun) by r0-r12 would have been overwritten, no?
I've seen that registers r0 to r4 are different from the registers r5 to r12 : why?
All the code I've written is using this organisation :
I push the registers that a functiun will overwrite, so that when it finishes and when we return to our original functiun I pop them back.
All the registers can be used to send parameters :
if r0 to r12 are functiun parameters, I can bl functiun and that functiun will have the correct r0-r12.
Please tell me if I'm wrong somewhere. What and when must I push when calling procedures?
Thanks
#10098 - torne - Wed Aug 27, 2003 12:49 am
This is very wrong. Follow the ARM/Thumb Procedure Call Standard, and you will be happy (as this is what GCC and ADS use, so you will be able to call to/from C/ASM without problems): http://www.arm.com/support/566FQ9/$File/ATPCS.pdf?OpenElement
Also, read this thread with some posts by me trying to explain what the ATPCS implies on the GBA: http://forum.gbadev.org/viewtopic.php?t=1119
In summary:
1) Functions may not change the values of registers r4-r11 or r13-r14. If an assembler function changes any of these registers, it must push and pop them itself (in the called function). If you call any functions with bl, you must push/pop r14 at the beginning and end of your function (not before/after the bl call, that's unneeded). If you don't call any functions you can skip popping r14. Maintaining r13 just requires your pushes and pops to be balanced. =)
2) Functions may always destroy the values of registers r0-r3 and r12. If you call a function and require a value that is in one of those to be preserved, you must push it yourself in the function doing the calling.
3) The first four parameters to a function are passed in r0-r3. If a function needs more than four parameters, the fifth and further parameters are pushed onto the stack in order. (see ATPCS for how to find them).
4) Functions must always return values in r0 (or r0 and r1, to return a 64-bit result, or r0-r3 to return a 128-bit result).
You must always return using bx lr if you are going to use interworking (mixing thumb/arm code), as the version of the ARM core in the GBA does NOT restore the instruction set state on a pop (later versions of the ARM do). This is particularly a pain in Thumb, whose pop instruction can't specify lr as a destination.
If you never intend to call ANY code written by other people, or generated from a compiler, you can ignore all these rules. However, all libraries, most code examples, and all compiled C code, follow the ATPCS. If you don't, then you will find that things break unpredictably and unamusingly. =)
tepples, could we get an FAQ entry about this? I'm starting to get bored of repeating myself. I should really write a 'What Every GBA Developer Needs To Know About The ATPCS' tutorial. =)
#10099 - funkeejeffou - Wed Aug 27, 2003 1:13 am
Hummm....
Am I wrong, or are you presuming that my functiuns calls can be made from GCC C code?
Because ALL my code is written in ASM(goldroad), so when I'm talking about calling a functiun, it is just branching and linking to a label by using bl.
What was strange was when you said that I do not need to push/pop r4-r5 when returning from a functiun, but in the ARM7tdmi doc, nothing is said about that.
Offtopic :
I've tryed every syntax to make ldreqsh work, but nothing does it with goldroad 1.6/1.7. ldreqh works, but it must be ldrheq.
Really sad to figure this two weeks before the compo...
#10108 - momo - Wed Aug 27, 2003 8:28 am
At the first Funktion , I think the bx lr is wrong, if it is in a recursion and
the function ends, the program start after the last bl and if you have no other break condition you are in a other CPU_Mode (Arm/Thumb) and the program fails. Use a mov pc,lr.
The Syntax for ldrsh is
ldr<cond>sh rd,[ <adresse> ]
Its should work with goldroad.
#10109 - torne - Wed Aug 27, 2003 9:13 am
| funkeejeffou wrote: |
Hummm....
Am I wrong, or are you presuming that my functiuns calls can be made from GCC C code?
Because ALL my code is written in ASM(goldroad), so when I'm talking about calling a functiun, it is just branching and linking to a label by using bl.
What was strange was when you said that I do not need to push/pop r4-r5 when returning from a functiun, but in the ARM7tdmi doc, nothing is said about that. |
I said that if all your code is asm and yours, there is no need to follow any rules at all. It's still probably not good practise, unless you are desperate to save some memory accesses. When I say you do not need to push/pop r4-r5, I don't mean the CPU will magically save them for you; I mean that any ATPCS-conforming function which changes them will push/pop them. BTW, if you are depending on the ARM7 document for details of the GBA, you'll be out of luck; that only covers specific issues for that chip, not the general details of the ARMv4 architecture. You also need to read the ATPCS and the ARM ARM (Architectural Reference Manual). The latter is not on ARM's website as you are supposed to buy it in book form, but I have a PDF that I got from altera's website.. the link seems to be gone, try googling.
| funkeejeffou wrote: |
Offtopic :
I've tryed every syntax to make ldreqsh work, but nothing does it with goldroad 1.6/1.7. ldreqh works, but it must be ldrheq.
Really sad to figure this two weeks before the compo... |
If Goldroad can't assemble that instruction, it's broken. =) Try using GAS, or if you're really desperate, put in some other instruction then hex-edit in the right assembled code.
#10110 - torne - Wed Aug 27, 2003 9:15 am
| momo wrote: |
At the first Funktion , I think the bx lr is wrong, if it is in a recursion and
the function ends, the program start after the last bl and if you have no other break condition you are in a other CPU_Mode (Arm/Thumb) and the program fails. Use a mov pc,lr. |
Uhm, no. Interworking-capable code should never execute mov pc,lr to return from functions. bx lr is equivalent in all cases to doing a direct mov, except it guarentees to restore the CPU mode correctly.
#10111 - momo - Wed Aug 27, 2003 9:48 am
@torne
But if I call my function self, its wrong to change the mode at the return or break condition. Because if my function is written in thumb and I call this function recusive its wrong to break with a bx. There is no problem to use a mov pc,lr because if I dont need to switch the mode, there is no reason to use bx.
Any Compilers would define a Standard which not realy exists. If it need a bx, the programmer have to capsule a rekursive function.
#10114 - torne - Wed Aug 27, 2003 1:13 pm
| momo wrote: |
| But if I call my function self, its wrong to change the mode at the return or break condition. Because if my function is written in thumb and I call this function recusive its wrong to break with a bx. There is no problem to use a mov pc,lr because if I dont need to switch the mode, there is no reason to use bx. |
Uhm.. no, it won't break. bx does not change the mode to the opposite of what it is now. bx changes the mode to the RIGHT one for the caller. If lr points to Thumb code, bx will set the processor mode to Thumb, regardless of what it is at present. If lr points to ARM code, bx will set the processor mode to ARM, regardless of what it is at present. Read the instruction set documentation. Also, on the ARM7, mov pc, lr and bx lr take exactly the same amount of time to execute, so you *never* lose anything by using bx, and gain interworking return support.
| momo wrote: |
| Any Compilers would define a Standard which not realy exists. If it need a bx, the programmer have to capsule a rekursive function. |
I assure you that the standard does really exist. Every version of GCC and every version of the ARM ADS compiler has conformed to some version of the ARM procedure call standard. It is written by ARM.. you can't get any more authoritative than that.
#10115 - momo - Wed Aug 27, 2003 1:43 pm
| torne wrote: |
| momo wrote: | | But if I call my function self, its wrong to change the mode at the return or break condition. Because if my function is written in thumb and I call this function recusive its wrong to break with a bx. There is no problem to use a mov pc,lr because if I dont need to switch the mode, there is no reason to use bx. |
Uhm.. no, it won't break. bx does not change the mode to the opposite of what it is now. bx changes the mode to the RIGHT one for the caller. If lr points to Thumb code, bx will set the processor mode to Thumb, regardless of what it is at present. If lr points to ARM code, bx will set the processor mode to ARM, regardless of what it is at present. Read the instruction set documentation. Also, on the ARM7, mov pc, lr and bx lr take exactly the same amount of time to execute, so you *never* lose anything by using bx, and gain interworking return support.
|
Thats right, Iam was totaly wrong :)
I have written so much lines in ARM Asm and then this :(
| torne wrote: |
| momo wrote: | | Any Compilers would define a Standard which not realy exists. If it need a bx, the programmer have to capsule a rekursive function. |
I assure you that the standard does really exist. Every version of GCC and every version of the ARM ADS compiler has conformed to some version of the ARM procedure call standard. It is written by ARM.. you can't get any more authoritative than that |
I know that there is a standard if I used the "normal" way of programming,
like scratch registers,stackframes,...
But if you use goldroad, you have no contact with objects. Because its in any ways not very optimal to use this "normal" guideline. But that's a matter of opinion.