[solved] 64 bit ABI and recursion ?

For other topics related to the FreeBASIC project or its community.
D.J.Peters
Posts: 8019
Joined: May 28, 2005 3:28
Contact:

[solved] 64 bit ABI and recursion ?

Postby D.J.Peters » Aug 01, 2015 18:46

I use some boxes with 32bit CPU's and have no practice in 64bit assembler.

If the 64 bit ABI used registers for the first four params (fastcall)
how a compiler handels recursion ?

On 32 bit the params are on the curent stackframe and not destroyed by recursion
but if a param exists in a register only it would be detroyed by recursion.

Does a 64bit compiler must detect recursion self and use the stack instead of registers ?

Joshy
Last edited by D.J.Peters on Aug 03, 2015 18:18, edited 1 time in total.
dkl
Site Admin
Posts: 3210
Joined: Jul 28, 2005 14:45
Location: Germany

Re: 64bit ABI and recursion ?

Postby dkl » Aug 01, 2015 19:01

I guess the parameters will be copied to stack or other (safe) registers. At least that must happen if the function contains any calls. It probably doesn't even matter if it's recursion or not.
SARG
Posts: 995
Joined: May 27, 2005 7:15
Location: FRANCE

Re: 64bit ABI and recursion ?

Postby SARG » Aug 01, 2015 22:14

Hi,

An area 32 bytes is also (always) reserved on the stack for the 4 first parameters (even if there is no parameter...).
So if needed they could be saved there.

With the small piece of code you can see that the paramater 'a' is saved on the stack (from ecx) and all is done from the stack.
Nota : No gcc's optimization is used (-Ox). I guess that in case of selected optimization it could be very different but debugging becomes impossible.

Code: Select all

sub test(a as long)
a+=15
print a
end sub


Code: Select all

TEST:
.LFB0:
   .file 1 "test_stringarray_64.bas"
   .loc 1 1 0
   .cfi_startproc
   push   rbp
.LCFI0:
   .cfi_def_cfa_offset 16
   .cfi_offset 6, -16
   mov   rbp, rsp
.LCFI1:
   .cfi_def_cfa_register 6
   sub   rsp, 32
   mov   DWORD PTR 16[rbp], ecx
.L2:
   .loc 1 2 0
   mov   eax, DWORD PTR 16[rbp]
   add   eax, 15
   mov   DWORD PTR 16[rbp], eax
   .loc 1 3 0
   mov   r8d, 1
   mov   edx, DWORD PTR 16[rbp]
   mov   ecx, 0
   call   fb_PrintInt
   .loc 1 4 0
   leave
.LCFI2:
   .cfi_restore 6
   .cfi_def_cfa 7, 8
   ret
marcov
Posts: 2839
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: 64bit ABI and recursion ?

Postby marcov » Aug 02, 2015 10:16

dkl wrote:I guess the parameters will be copied to stack or other (safe) registers. At least that must happen if the function contains any calls. It probably doesn't even matter if it's recursion or not.


.. and if it needs the values of the parameters after that call.
marcov
Posts: 2839
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: 64bit ABI and recursion ?

Postby marcov » Aug 02, 2015 10:39

SARG wrote:An area 32 bytes is also (always) reserved on the stack for the 4 first parameters (even if there is no parameter...).
So if needed they could be saved there.


The x86_64 ABI document only names register save area as part of va_* macros, IOW C style variant parameter functions.

Or has that changed meanwhile?
dkl
Site Admin
Posts: 3210
Joined: Jul 28, 2005 14:45
Location: Germany

Re: 64bit ABI and recursion ?

Postby dkl » Aug 02, 2015 11:10

The SysV ABI for x86_64 mentions a "red zone" allocated as part of the stack frame. The MinGW x64 Software convention wiki page says that Windows doesn't have it, though.
marcov
Posts: 2839
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: 64bit ABI and recursion ?

Postby marcov » Aug 02, 2015 12:20

dkl wrote:The SysV ABI for x86_64 mentions a "red zone" allocated as part of the stack frame. The MinGW x64 Software convention wiki page says that Windows doesn't have it, though.


The red zone is a general scratch zone, but afaik its internal layout isn't fixed like with register save areas, and thus (its layout is) not part of the ABI.

Since it stretches below the stackframe (-128(%rsp)), it can't be used to preserve values while you call a function since that function could overwrite it. Only interrupt/signal handlers must preserve it.
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: [solved] 64 bit ABI and recursion ?

Postby MichaelW » Sep 04, 2015 3:18

Code: Select all

function Factorial( n as longint ) as longint
    if n = 0 then
        return 1
    else
        return n * Factorial( n - 1 )
    end if   
end function

for i as longint = 0 to 10
    print Factorial(i)
next
sleep

Assembly code as compiled with Version 1.03.0 (07-01-2015), built for win64 (64bit):

Code: Select all

   .file   "factorial.c"
   .intel_syntax noprefix
   .text
   .globl   FACTORIAL
   .def   FACTORIAL;   .scl   2;   .type   32;   .endef
FACTORIAL:
   push   rbp
   mov   rbp, rsp
   sub   rsp, 48
   mov   QWORD PTR 16[rbp], rcx
   mov   QWORD PTR -16[rbp], 0
.L2:
   cmp   QWORD PTR 16[rbp], 0
   je   .L3
   nop
.L4:
   mov   rax, QWORD PTR 16[rbp]
   sub   rax, 1
   mov   rcx, rax
   call   FACTORIAL
   mov   QWORD PTR -8[rbp], rax
   mov   rax, QWORD PTR 16[rbp]
   imul   rax, QWORD PTR -8[rbp]
   mov   QWORD PTR -16[rbp], rax
   nop
   jmp   .L6
.L3:
   mov   QWORD PTR -16[rbp], 1
.L5:
   nop
.L6:
   mov   rax, QWORD PTR -16[rbp]
   leave
   ret
   .def   __main;   .scl   2;   .type   32;   .endef
   .globl   main
   .def   main;   .scl   2;   .type   32;   .endef
main:
   push   rbp
   mov   rbp, rsp
   sub   rsp, 64
   mov   DWORD PTR 16[rbp], ecx
   mov   QWORD PTR 24[rbp], rdx
   call   __main
   mov   DWORD PTR -20[rbp], 0
   mov   rax, QWORD PTR 24[rbp]
   mov   r8d, 0
   mov   rdx, rax
   mov   ecx, DWORD PTR 16[rbp]
   call   fb_Init
.L9:
   mov   QWORD PTR -8[rbp], 0
.L10:
   mov   rax, QWORD PTR -8[rbp]
   mov   rcx, rax
   call   FACTORIAL
   mov   QWORD PTR -16[rbp], rax
   mov   rax, QWORD PTR -16[rbp]
   mov   r8d, 1
   mov   rdx, rax
   mov   ecx, 0
   call   fb_PrintLongint
.L11:
   add   QWORD PTR -8[rbp], 1
.L12:
   cmp   QWORD PTR -8[rbp], 10
   jg   .L13
   jmp   .L10
.L13:
   mov   ecx, -1
   call   fb_Sleep
.L14:
   mov   ecx, 0
   call   fb_End
   mov   eax, DWORD PTR -20[rbp]
   leave
   ret
   .ident   "GCC: (x86_64-win32-sjlj-rev3, Built by MinGW-W64 project) 4.9.2"
   .def   fb_Init;   .scl   2;   .type   32;   .endef
   .def   fb_PrintLongint;   .scl   2;   .type   32;   .endef
   .def   fb_Sleep;   .scl   2;   .type   32;   .endef
   .def   fb_End;   .scl   2;   .type   32;   .endef

Output:

Code: Select all

 1
 1
 2
 6
 24
 120
 720
 5040
 40320
 362880
 3628800
marcov
Posts: 2839
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: [solved] 64 bit ABI and recursion ?

Postby marcov » Sep 13, 2015 11:03

Btw nice page on the topic (seems to indicate that win64 does not support Red Zone, but uses a proper register save area)

http://eli.thegreenplace.net/2011/09/06 ... on-x86-64/

with many links on the subject including MSDN

Return to “Community Discussion”

Who is online

Users browsing this forum: No registered users and 1 guest