Use
r0 for the argument and result. With 32-bit integers and pointers, the three fields have byte offsets 0, 4 and 8. Assume an acyclic finite binary tree, no concurrent mutation, a valid aligned call stack, and no signed integer overflow in any evaluated sum. These are representation and arithmetic assumptions, rather than properties of arbitrary C programming language implementations..syntax unified
.cpu cortex-m0
.thumb
.global sum_rec
.thumb_func
sum_rec:
cmp r0, #0
beq .Lempty
push {r4, r5, r6, lr} @ 16-byte frame; r6 is alignment padding
movs r4, r0 @ retain this invocation's node
ldr r5, [r4, #0] @ running value begins with its label
ldr r0, [r4, #4]
bl sum_rec @ r0 = left subtree sum
adds r5, r5, r0
ldr r0, [r4, #8]
bl sum_rec @ r0 = right subtree sum
adds r0, r0, r5
pop {r4, r5, r6, pc} @ restore caller state and return
.Lempty:
movs r0, #0
bx lrThe node and partial sum are held in callee-saved registers
r4,r5. Each recursive invocation saves its caller's values before replacing them, so a child returns with the parent's values intact. Saving lr preserves the return address across the two bl instructions. Caller-saved registers may be overwritten by a child; no parent value is left live only in them. Pushing four words maintains eight-byte stack alignment at recursive calls.[ref]Procedure Call Standard for the Arm Architecture by ARM Limited. AAPCS32, base standard: core-register roles, stack constraints and result return
Correctness follows by structural induction. An empty subtree returns zero. For a nonempty subtree, assume both recursive calls return their respective label sums. The final addition then combines the node's label with exactly those two sums, so
r0 returns the sum of all labels. The instruction forms and field offsets fit the short load and arithmetic encodings.[ref]Thumb 16-bit instruction set quick reference by Arm. Move, Add, Load, Push/Pop and Branch tables
Use an explicit-stack depth-first tree traversal. Descend the left branch immediately and put each nonempty right subtree on a stack for later. For the same node declarations as in the paper, an original C programming language implementation is:
int sum_iter(tree t)
{
tree pending[32];
unsigned top = 0;
int total = 0;
while (t != NULL || top != 0) {
if (t == NULL) {
t = pending[--top];
} else {
total += t->data;
if (t->right != NULL)
pending[top++] = t->right;
t = t->left;
}
}
return total;
}The loop invariant says that the accumulated labels plus the sums of the current subtree and all pending subtrees equal the original tree sum, with the unvisited subtrees disjoint. Visiting a node adds its label and replaces its subtree by its two children. Popping merely changes which pending subtree is current. When both current and pending subtrees are absent, the invariant proves the result.
At most one unvisited right sibling is pending at each level of the current ancestor path. If depth means the number of nonempty nodes on a longest root-to-leaf path, depth at most 32 requires at most 31 pending right siblings. A 32-word array is therefore sufficient; it also covers the convention that depth counts at most 32 edges. The depth promise makes unchecked pushes valid here. For arbitrary input, a production implementation should check capacity rather than overwrite its frame.
A corresponding Thumb instruction set implementation keeps the total in
r4, the array base in r5, and its next-free address in r6:.global sum_iter_asm
.thumb_func
sum_iter_asm:
push {r4, r5, r6, lr}
sub sp, sp, #128 @ 32 pending pointers
mov r5, sp @ base of pending array
mov r6, sp @ empty stack: next-free equals base
movs r4, #0
.Lvisit:
cmp r0, #0
beq .Ltake_pending
ldr r1, [r0, #0]
adds r4, r4, r1 @ consume this node's label
ldr r1, [r0, #8]
cmp r1, #0
beq .Lleft
str r1, [r6, #0] @ defer the nonempty right subtree
adds r6, r6, #4
.Lleft:
ldr r0, [r0, #4] @ continue down the left branch
b .Lvisit
.Ltake_pending:
cmp r6, r5
beq .Ldone
subs r6, r6, #4
ldr r0, [r6, #0]
b .Lvisit
.Ldone:
movs r0, r4
add sp, sp, #128
pop {r4, r5, r6, pc}The stack pointer stays fixed while the array is used;
r6 is a separate cursor inside that array. All callee-saved registers touched by the function are restored. Each nonempty node contributes its label exactly once. As in part (a), require that every partial total fits the signed result type; a representable final answer alone does not prevent overflow in a different summation order.Let be the number of nonempty nodes and the maximum number on a root-to-leaf path. Both listings take time on a unit-cost machine: each node is visited once and its three fields are read once. The recursive listing executes two child calls per nonempty node, including calls on empty children; there are invocations in total. It saves and restores four words for every nonempty invocation. The iterative listing has one function frame, no recursive calls, and one push/pop pair per deferred nonempty right subtree. Thus it removes repeated call/return and frame-transfer overhead, although its extra loop tests also cost instructions. Exact cycle comparisons need a specified processor, memory timing and compiler; an optimizing compiler may alter either implementation.
For these particular assembly language listings, the recursive call stack uses bytes above the caller's frame; empty calls allocate no additional frame. The iterative listing uses a fixed bytes, even for a shallow or empty tree. With , the recursive maximum is 512 bytes, versus 144 bytes for this fixed-array iteration. If the promised depth of 32 instead counts edges, the recursive bound is bytes; the same 32-word pending array still suffices. Conversely, for recursion uses at most 128 bytes and is smaller than the fixed array. When sized dynamically to depth, both approaches use auxiliary storage, but their stored information differs: full suspended invocation state versus pending subtree roots. Therefore recursion is not intrinsically always slower or larger; the claim depends on generated code, tree shape and the choice to reserve a maximum-size explicit array.
Articles by others on the same topic
There are currently no matching articles.