Пример loRecursion в сборке ARM

Вам нужно использовать стек, инструкции STMDB и LDMIA. На реальных ARM-инструментах с «унифицированной» нотацией тоже есть мнемоники PUSH и POP.

Фибоначи и факториал не являются хорошими примерами, поскольку им не нужна рекурсия. Но давайте представим, что они это делают. Я выберу Фибоначчи, так как у вас нет инструкции MUL!? Вы хотите сделать что-то вроде этого:

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}         ;  }

Он должен заканчиваться R0, содержащим fib(6) == 8. Конечно, этот код очень неэффективен, так как он неоднократно вызывает FIB для одних и тех же значений.

STM необходим, чтобы вы могли использовать регистры r4, r5, потому что другой вызов функции может изменить r0-r3 и LR. Толкать LR и выталкивать PC — это как B LR. Если вы вызывали код C, вы должны поместить четное число регистров, чтобы поддерживать 64-битное выравнивание SP (здесь нам не нужно этого делать; игнорируйте R6).

какая-то другая рекурсивная функция:

unsigned int so ( unsigned int x )
{
    static unsigned int z=0;
    z+=x;
    if(x==0) return(z);
    so(x-1);
    return(z);
}

строить/разбирать

arm-none-eabi-gcc -O2 -c Desktop/so.c -o so.o
arm-none-eabi-objdump -D so.o


00000000 <so>:
   0:   e92d4010    push    {r4, lr}
   4:   e59f4034    ldr r4, [pc, #52]   ; 40 <so+0x40>
   8:   e5943000    ldr r3, [r4]
   c:   e3500000    cmp r0, #0
  10:   e0803003    add r3, r0, r3
  14:   e5843000    str r3, [r4]
  18:   1a000002    bne 28 <so+0x28>
  1c:   e1a00003    mov r0, r3
  20:   e8bd4010    pop {r4, lr}
  24:   e12fff1e    bx  lr
  28:   e2400001    sub r0, r0, #1
  2c:   ebfffffe    bl  0 <so>
  30:   e5943000    ldr r3, [r4]
  34:   e8bd4010    pop {r4, lr}
  38:   e1a00003    mov r0, r3
  3c:   e12fff1e    bx  lr
  40:   00000000    

Если вы этого не понимаете, то оно того стоит. Является ли обманом позволить инструменту сделать это за вас?

push — это псевдоинструкция для stm, pop — псевдоинструкция для ldm, так что вы можете их использовать.

Я использовал статический локальный, который я называю локальным глобальным, он попадает в .data, а не в стек (ну, в данном случае .bss, поскольку я сделал его нулевым)

Disassembly of section .bss:

00000000 <z.4099>:
   0:   00000000    

первая загрузка загружает это значение в r3.

соглашение о вызовах гласит, что r0 будет содержать первый параметр при входе в функцию (есть исключения, но в данном случае это правда).

поэтому мы идем и получаем z из памяти, r0 уже имеет параметр x, поэтому мы добавляем x к z и сохраняем его в памяти

компилятор сделал сравнение не по порядку, кто знает причины производительности, add и str, как написано, не изменяют флаги, так что все в порядке,

если x не равен нулю, он переходит к 28, что делает вызов so(x-1) считывающим r3 обратно из памяти (соглашение о вызовах говорит, что r0-r3 являются изменчивыми функциями, которые вы можете изменить по своему желанию и не должны сохранить их, чтобы наша версия z в r3 могла быть уничтожена, но r4 сохраняется любым вызываемым пользователем, поэтому мы считываем z обратно в r3, извлекаем r4 и адрес возврата из стека, подготавливаем регистр возврата r0 с z и делаем Возврат.

если x был равен нулю (bne на 18 не удалось, мы запускаем 1c, затем 20, затем 24), затем мы копируем z (версия r3) в r0, который является регистром, используемым для возврата из этой функции в соответствии с соглашением о вызовах, используемым этим компилятором ( рекомендации по оружию). и возвращается.

компоновщик заполнит адрес z по смещению 0x40, это объект, а не окончательный двоичный файл...

arm-none-eabi-ld -Ttext=0x1000 -Tbss=0x2000 so.o -o so.elf
arm-none-eabi-ld: warning: cannot find entry symbol _start; defaulting to 0000000000001000
arm-none-eabi-objdump -D so.elf

so.elf:     file format elf32-littlearm


Disassembly of section .text:

00001000 <so>:
    1000:   e92d4010    push    {r4, lr}
    1004:   e59f4034    ldr r4, [pc, #52]   ; 1040 <so+0x40>
    1008:   e5943000    ldr r3, [r4]
    100c:   e3500000    cmp r0, #0
    1010:   e0803003    add r3, r0, r3
    1014:   e5843000    str r3, [r4]
    1018:   1a000002    bne 1028 <so+0x28>
    101c:   e1a00003    mov r0, r3
    1020:   e8bd4010    pop {r4, lr}
    1024:   e12fff1e    bx  lr
    1028:   e2400001    sub r0, r0, #1
    102c:   ebfffff3    bl  1000 <so>
    1030:   e5943000    ldr r3, [r4]
    1034:   e8bd4010    pop {r4, lr}
    1038:   e1a00003    mov r0, r3
    103c:   e12fff1e    bx  lr
    1040:   00002000    

Disassembly of section .bss:

00002000 <z.4099>:
    2000:   00000000    

дело здесь не в том, чтобы обманывать и использовать компилятор, дело в том, что в рекурсивной функции нет ничего волшебного, конечно, если вы следуете соглашению о вызовах или какому-то вашему любимому термину.

Например

если у вас есть параметры r0 первый, r1 второй, до r3 (если они подходят, сделайте свой код таким, чтобы он соответствовал, и у вас есть четыре или меньше параметров) возвращаемое значение находится в r0, если он подходит вам нужно нажать lr на стек, поскольку вы будете вызывать другую функцию r4 для сохранения, если вам нужно их изменить, если вы хотите, чтобы какое-то локальное хранилище использовало стек, соответствующим образом изменив указатель стека (или выполнив push/stms). вы можете видеть, что gcc вместо этого сохраняет то, что было в регистре, в стек, а затем использует регистр во время функции, по крайней мере, до нескольких локальных переменных, помимо этого, ему нужно будет много стучать по стеку, sp относительно. когда вы выполняете рекурсивный вызов, вы делаете это так же, как и любую другую обычную функцию в соответствии с соглашением о вызовах, если вам нужно сохранить r0-r3 перед вызовом, сделайте это либо в регистре r4 или выше, либо в стеке, восстановите после функция возвращает. вы можете видеть, что проще просто поместить значения, которые вы хотите сохранить, до и после вызова функции в регистре r4 или выше. компилятор мог бы выполнить сравнение r0 непосредственно перед веткой, так легче читается. Точно так же можно было бы сделать mov to r0 возвращаемого значения до pop

Я не указал параметры, поэтому моя сборка gcc здесь выглядит как armv4t, если я попрошу что-то немного новее

arm-none-eabi-gcc -O2 -c -mcpu=mpcore Desktop/so.c -o so.o
arm-none-eabi-objdump -D so.o

so.o:     file format elf32-littlearm


Disassembly of section .text:

00000000 <so>:
   0:   e92d4010    push    {r4, lr}
   4:   e59f402c    ldr r4, [pc, #44]   ; 38 <so+0x38>
   8:   e3500000    cmp r0, #0
   c:   e5943000    ldr r3, [r4]
  10:   e0803003    add r3, r0, r3
  14:   e5843000    str r3, [r4]
  18:   1a000001    bne 24 <so+0x24>
  1c:   e1a00003    mov r0, r3
  20:   e8bd8010    pop {r4, pc}
  24:   e2400001    sub r0, r0, #1
  28:   ebfffffe    bl  0 <so>
  2c:   e5943000    ldr r3, [r4]
  30:   e1a00003    mov r0, r3
  34:   e8bd8010    pop {r4, pc}
  38:   00000000 

Вы можете видеть, что возвраты читаются немного легче

хотя оптимизация была пропущена, он мог бы выполнить ldr r0,[r4] и сохранить инструкцию. или оставить этот хвост как есть, и bne мог быть beq до 30 (mov r0,r3; pop{r4,pc} и разделил выход.

немного более читабельно

so:
    push    {r4, lr}
    @ z += x
    ldr r4, zptr
    ldr r3, [r4]
    add r3, r0, r3
    str r3, [r4]
    @ if x==0 return z
    cmp r0, #0
    beq l30
    @ so(x - 1)
    sub r0, r0, #1
    bl so
    ldr r3, [r4]
l30:
    @ return z
    mov r0, r3
    pop {r4, pc}
zptr: .word z

.section .bss
z: .word 0

arm-none-eabi-as so.s -o so.o
arm-none-eabi-objdump -D so.o

so.o:     file format elf32-littlearm


Disassembly of section .text:

00000000 <so>:
   0:   e92d4010    push    {r4, lr}  (stmdb)
   4:   e59f4024    ldr r4, [pc, #36]   ; 30 <zptr>
   8:   e5943000    ldr r3, [r4]
   c:   e0803003    add r3, r0, r3
  10:   e5843000    str r3, [r4]
  14:   e3500000    cmp r0, #0
  18:   0a000002    beq 28 <l30>
  1c:   e2400001    sub r0, r0, #1
  20:   ebfffff6    bl  0 <so>
  24:   e5943000    ldr r3, [r4]

00000028 <l30>:
  28:   e1a00003    mov r0, r3
  2c:   e8bd8010    pop {r4, pc}  (ldmia)

00000030 <zptr>:
  30:   00000000    

Disassembly of section .bss:

00000000 <z>:
   0:   00000000    

РЕДАКТИРОВАТЬ

Итак, давайте пройдемся по этому последнему.

push {r4,lr}  which is a pseudo instruction for stmdb sp!,{r4,lr}

Lr is the r14 which is the return address look at the bl instruction
branch and link, so we branch to some address but lr (link register) is 
set to the return address, the instruction after the bl.  So when main or some other function calls so(4);  lets assume so is at address 0x1000 so the program counter, r15, pc gets 0x1000, lr will get the value of the instruction after the caller so lets say that is 0x708.  Lets also assume the stack pointer during this first call to so() from main is at 0x8000, and lets say that .bss is at 0x2000 so z lives at address 0x2000 (which also means the value at 0x1030, zptr is 0x2000.

We enter the function for the first time with r0 (x) = 4.

When you read the arm docs for stmdb sp!,{r4,lr} it decrements before (db)  so sp on entry this time is 0x8000 so it decrements for the two items to 0x7FF8, the first item in the list is written there so

0x7FF8 = r4 from main
0x7FFC = 9x 0x708 return address to main

the ! means sp stays modified so sp-0x7ff8

then ldr r4,zptr  r4 = 0x2000
ldr r3,[r4] this is an indirect load so what is at address r4 is read to 
put in r3 so r3 = [0x2000] = 0x0000 at this point  the z variable.

z+=x;  add r3,r0,r3  r3 = r0 + r3 = 4 + 0 = 4
str r3,[r4]  [r4] = r3, [0x2000] = r3 write 4 to 0x2000

cmp r0,#0   4 != 0

beq to 28 nope, not equal so no branch

sub r0,r0,#1   r0 = 4 - 1 = 3

bl so  so this is so(3); pc = 0x1000 lr = 0x1024

so now we enter so for the second time with r0 = 3

stmdb sp!,{r4,lr}

0x7FF0 = r4 (saving from so(4) call but we dont care its value even though we know it)
0x7FF4 = lr from so(4) = 0x1024
sp=0x7FF0
ldr r4,zptr r4 = 0x2000
ldr r3,[r4] r3 = [0x2000] = 4
add r3,r0,r3  r3 = 3 + 4 = 7
str r3,[r4]  write 7 to 0x2000
cmp r0,#0 3 != 0
beq 0x1028 not equal so dont branch
sub r0,r0,#1   r0 = 3-1 = 2
bl so  pc=0x1000 lr=0x1024

so(2)

stmdb sp!,{r4,lr}
0x7FE8 = r4 from caller, just save it
0x7FEC = lr from caller, 0x1024
sp=0x7FE8
ldr r4,zprt  r4=0x2000
ldr r3,[r4]  r3 = read 7 from 0x2000
add r3,r0,r3  r3 = 2 + 7 = 9
str r3,[r4]  write 9 to 0x2000
cmp r0,#0  2 != 0
beq 0x1028  not equal so dont branch
sub r0,r0,#1  r0 = 2 - 1 = 1
bl 0x1000 pc=0x1000 lr=0x1024

so(1)

stmdb sp!,{r4,lr}
0x7FE0 = save r4
0x7FE4 = lr = 0x1024
sp=0x7FE0
ldr r4,zptr r4=0x2000
ldr r3,[r4]  r3 = read 9 from 0x2000
add r3,r0,r3  r3 = 1 + 9 = 10
str r3,[r4]  write 10 to 0x2000
cmp r0,#0  1 != 0
beq 0x1028  not equal so dont branch
sub r0,r0,#1  r0 = 1 - 1 = 0
bl 0x1000  pc=0x1000 lr=0x1024

so(0)

stmdb sp!,{r4,lr}
0x7FD8 = r4
0x7FDC = lr = 0x1024
sp = 0x7FD8
ldr r4,zptr  r4 = 0x2000
ldr r3,[r4]  r3 = read 10 from 0x2000
add r3,r0,r3  r3 = 0 + 10 = 10
str r0,[r4]  write 10 to 0x2000
cmp r0,#0  0 = 0  so it matches
beq 0x1028 it is equal so we finally take this branch
mov r0,r3  r0 = 10
ldmia sp!,{r4,pc}
increment after
r4 = [sp+0] = [0x7FD8] restore r4 from caller
pc = [sp+4] = [0x7FDC] = 0x1024
sp += 8 = 0x7FE0
(branch to 0x1024)(return from so(0) to so(1))
ldr r3,[r4]  read 10 from 0x2000
mov r0,r3  r0 = 10
ldmia sp!,{r4,pc}
r4 = [sp+0] = [0x7FE0] restore r4 from caller
pc = [sp+4] = [0x7FE4] = 0x1024
sp += 8 = 0x7FE8
(branch to 0x1024)(return from so(1) to so(2))
ldr r3,[r4]  read 10 from 0x2000
mov r0,r3  r0 = 10
ldmia sp!,{r4,pc}
r4 = [sp+0] = [0x7FE8] restore r4 from caller
pc = [sp+4] = [0x7FEC] = 0x1024
sp += 8 = 0x7FF0
(branch to 0x1024)(return from so(2) to so(3))
ldr r3,[r4]  read 10 from 0x2000
mov r0,r3  r0 = 10
ldmia sp!,{r4,pc}
r4 = [sp+0] = [0x7FF0] restore r4 from caller
pc = [sp+4] = [0x7FF4] = 0x1024
sp += 8 = 0x7FF8
(branch to 0x1024)(return from so(3) to so(4))
ldr r3,[r4]  read 10 from 0x2000
mov r0,r3  r0 = 10
ldmia sp!,{r4,pc}
r4 = [sp+0] = [0x7FF8] restore r4 from caller (main()'s r4)
pc = [sp+4] = [0x7FFC] = 0x708
sp += 8 = 0x8000
(branch to 0x708)(return from so(4) to main())

and we are done.

Стек похож на подстаканник дикси, который может появиться раньше вашего времени. Подстаканник, в который вы опускаете чашку, а следующая и остальные чашки остаются в держателе, ну, вы можете засунуть туда одну обратно.

Таким образом, стек является временным хранилищем для функции, запишите один элемент данных на чашку, затем засуньте его в держатель (сохраните r4 от вызывающей стороны), напишите другой элемент и засуньте его в держатель (lr, обратный адрес от вызывающей стороны). здесь мы использовали только два элемента для каждой функции, поэтому для каждой функции я могу вставить две чашки в держатель, при каждом вызове функции я получаю два НОВЫХ И УНИКАЛЬНЫХ места хранения для хранения этой локальной информации. Когда я выхожу из функции, я вытаскиваю две чашки из держателя и использую их значения (и выбрасываю их). Это в некоторой степени ключ к рекурсии, стек дает вам новое локальное хранилище для каждого вызова, отдельное от предыдущих вызовов той же функции, если вам больше ничего не нужно, адрес возврата (хотя сделал еще более простой пример рекурсии, которого не было, когда оптимизированный был достаточно умен, чтобы сделать из него петлю).

ldr rd,[rn] Думайте о брекетах как о произнесении элемента по этому адресу, поэтому считывайте память по адресу в rn и сохраняйте это значение в rd.

str rd,[rn] одна запутанная инструкция руки, в то время как остальные первый параметр является левой частью равенства (добавить r1,r2,r3 r1 = r2 + r3, ldr r1,[r4] r1 = [r4]) это обратное [rn] = rd сохранить значение в rd в ячейку памяти, описанную адресом r4, один уровень косвенности.

stmdb sp!, означает уменьшение указателя стека перед выполнением каких-либо действий на 4 байта, умноженное на количество регистров в списке, затем записать первый регистр с наименьшим номером в [sp+0], затем следующий в [sp+4] и так далее. последний будет на четыре меньше начального значения sp. ! означает, что функция завершается с sp, являющимся этим уменьшенным значением. Вы можете использовать ldm/stm для вещей, отличных от push и pops стека. Вроде memcpy, но это уже другая история...

Все это есть в документации по arm с сайта infocenter.arm.com, которая у вас уже должна быть (справочное руководство по архитектуре arm, если вы его еще не читали, предпочтительнее armv5).