[Bug c/111786] New: No tail recursion for simple program

[Bug c/111786] New: No tail recursion for simple program

[lukas.graetz@tu-darmstadt.de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111786

            Bug ID: 111786
           Summary: No tail recursion for simple program
           Product: gcc
           Version: 13.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: lukas.graetz@tu-darmstadt.de
  Target Milestone: ---

Created attachment 56096
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56096&action=edit
C code of expr_main

Follow up with nearly the same source file as 111643, only without the flatten
attribute. Sorry for taking so long for that. I learned the optimized compiler
should output a tail recursion. But this seams not to be the case: With "sub"
and "call", 16 bytes on the stack are used.

The file attached file contains:

---
int expr_main(int argc, char **argv)
{
    return expr_main_original(argc, argv);
}
---

And after cc1 -O3 on amd64, the output contains:

-- gcc 13.2.0 --
expr_main:
        subq    $8, %rsp
        call    expr_main_original
---

-- gcc 9.4.0 shipped with ubuntu 20.04 ---
expr_main:
        endbr64
        pushq   %rax
        popq    %rax
        pushq   %rax
        call    expr_main_original
---

-- Expected --
expr_main:
        jmp     expr_main_original
---

If I compile the above snippet only, I get the expected result. But not when
compiling the whole C file which also includes the body of
expr_main_original(). I also suspect there are some other factors I don't know,
since many other functions I tested yield the expected result.

In my case, the overhead seams to be negligible. However, I think it should be
possible to construct similar recursive programs where the overhead compared to
tail recursion is not negligible.

[Bug c/111786] No tail recursion for simple program

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111786

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
We completely intentionally don't emit tail calls to noreturn functions, so
that e.g. in case of abort one doesn't need to virtually reconstruct backtrace.
In your case, the interprocedural optimizations determine expr_main_original is
noreturn and so calls it normally (and optimizes away anything after that
call).

[Bug c/111786] No tail recursion for simple program

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111786

Xi Ruoyao <xry111 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|INVALID                     |DUPLICATE

--- Comment #2 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---


*** This bug has been marked as a duplicate of bug 10837 ***

[Bug c/111786] No tail recursion for simple program

[lukas.graetz@tu-darmstadt.de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111786

--- Comment #3 from Lukas Grätz <lukas.graetz@tu-darmstadt.de> ---
(In reply to Jakub Jelinek from comment #1)
> We completely intentionally don't emit tail calls to noreturn functions, so
> that e.g. in case of abort one doesn't need to virtually reconstruct
> backtrace.
> In your case, the interprocedural optimizations determine expr_main_original
> is noreturn and so calls it normally (and optimizes away anything after that
> call).

Thank you very much indeed! (Ah yes, this also explains why there is not
"ret".) And sorry for not realizing that this is duplicate. So the "call" is
intentionally emitted by gcc for a better debugging experience. I agree, this
makes perfectly sense in many cases.

However, the price of better debugging seems to be the danger of a stack
overflow. After I understood your "complete" intention, it took me about 20 min
to construct an example with bears a stack overflow following that intention.

---
void foo(int n) {
    if (n == 0)
        exit(0);
    int x[200];
    for (int i = 0; i < 200; i++)
        extern_function(x[i], x[200-i]);
    return foo(n-1);
}
---

After adding __attribute__((noreturn)), compiling with -O3 and passing 10000 to
foo(), I get a segmentation fault. There is still a warning "function declared
‘noreturn’ has a ‘return’ statement". But in our case, the noreturn attribute
is not wrong, because none of the recursive calls actually do return. This
might be something that interprocedure optimizations detect in the future. So
even without attribute noreturn, gcc could decide to produce no tail recursion
(because it is a noreturn function, regardless of the noreturn attribute).

Last remark, then I remain silent. I just learned that clang actually has the
attribute musttail which would help for my reported C file as well as in the
foo() example above to prevent the stack overflow. But I guess it is not
planned to add musttail to gcc?