#199 Incorrect recursion call in MOS6502 and MOS65C02

[Andrzej]

I found the problem with recursion call in MOS6502, while the MCS51 and Z180 works correct.

I wrote the simple code to test the recursion:

#define uchar unsigned char
#define schar signed char

#define _uchar ((uchar volatile *)0)
#define _schar ((schar volatile *)0)

// Simple Fibonacci number computation
uchar FiboSimple(uchar N)
{
 if (N <= 1)
 {
  return N;
 }
 return FiboSimple(N - 1) + FiboSimple(N - 2);
}

void main(void)
{
 // Take 7 as parameter and save the result at the 0x9000 byte
 _uchar[0x9000] = FiboSimple(7);

 // Infinity loop at the end of the program
 while (1)
 {
 }
}

As you can see, the program computes the value of Fibonacci sequence directly from the recursive formula.
In my simulator, in the 65C02, the code computes incorrect sequences values. For instance, for 7 the code returns 4 instead of 13.

I wrote the assembler code of the FiboSimple function based on the LST file, so the code as the same as generated by SDCC:

LDA #7
    jsr _FiboSimple
EndLoop:
    jmp EndLoop

_FiboSimple:
    cmp #01
    beq x00103
    bcc x00103
    jmp x00102
    rts
x00102:
    pha
    sec
    sbc #01
    tax
    jsr _FiboSimple
    sta $05
    pla
    sec
    sbc #02
    jsr _FiboSimple
    clc
    adc $05
x00103:
    rts

I detected, that the function code takes the argument from A register and put the result into A register.

I run the code in the simulator: https://skilldrick.github.io/easy6502/

In the linked simulator I tested with several arguments and I get the same computation error.

Is this a bug in SDCC or how to solve the problem?

[Andrzej]

This problem exists in 6502 when the function recursively call themself more than once.

[Janko Stamenović]

I haven't used 6502 but I would first try to add __reentrant like this: uchar FiboSimple(uchar N) __reentrant.

[Andrzej]

The exactly compilation command is very simple:

wine sdcc -mmos6502 TestProg.c

I use 32-bit version 4.4.0 under Ubuntu Linux.

[Maarten Brock]

Ticket moved from /p/sdcc/bugs/3751/

Can't be converted:

• _category: MOS6502

[Maarten Brock]

Many of the targets supported by SDCC are poorly equipped for reentrancy. That is why by default SDCC does not support reentrancy for them. The mcs51 and 6502 are both in that category, z180 is not. The reason this simple function works for mcs51 is pure luck, because the mcs51 has more registers that get used for intermediate results and do get saved/restored around calls. A bigger recursively called function would fail the same way.

As Janko mentioned you can force SDCC to make functions reentrant, either by supplying the __reentrant keyword or by using the --stack-auto option.

There is no bug here, so I changed it to a Support Request.