Crystal: tail recursion and LLVM

[Fusion]

Since you are answering questions :)

Disclaimer: I am not familiar with LLVM so this is a naive question!

I was playing with Crystal's code generation and checked that by invoking LLVMSetTailCall I could ask llvm/builder.cr to generate a 'tail' call. OK, I understand that, using the C calling convention, we are effectively working with sibling calls.

I wrote a small test case but when attempting to recurse 50M times I quickly ran afoul of the stack guard. OK, I realize that is remains active unless compiling in 'release' mode.

In release mode I was able to successfully run my test program.

A that point, I thought I had a good handle on what llvm does. Except that, after removing the 'tail' call (verified in .ll file) I am still able to run my program in release mode.

Does this mean that llvm will automatically detect sibling calls, even when not specified?

Cheers,
-Chris.

[Fusion]

...and bonus question: does this mean that I can count on sibling call optimization when using Crystal?

[asterite]

Hi,

I don't understand: how and where did you use LLVMSetTailCall?

In release mode LLVM optimizations are performed and (I guess) LLVM can detect tail/sibling calls (LLVM will add those annotations), but that's something that should be asked in the LLVM forums.

[Fusion]

I guess I should have been more clear that I was playing with Crystal's source code itself, specifically llvm/builder.cr.

As you point out, these are LLVM questions so I will simply focus on the Crystal-relevant one: will Crystal, as a black box, perform sibling call optimization? Or did I draw the wrong conclusion from my observations?

[asterite]

When you compile with --release that optimizes the generated LLVM. Wiithout --release the compiler will generate very simple/dumb LLVM, that's not inefficient but could be better. No tail/sibling call annotations are added without passing that --release flag. I don't know if that answers your question.

In any case, that doesn't mean in the future the compiler will add these annotations even if you don't pass the --release flag.

[asterite]

I forgot to say: it's by running those LLVM optimizations that the tail/sibiling annotations are added. Crystal doesn't add those by itself.

[jhass]

Question answered? Does somebody want to open a separate proposal for explicitly marking a method or function as tail recursive or having the compiler detect tail recursive cases which LLVM won't detect?

[asterite]

I wouldn't add specific language constructs to enable tail call optimizations. Ideally, the compiler should figure it out for itself. LLVM detects some cases of this. Right now there's no real pressure to improve this because performance is pretty good even without it used in some cases, so I'm closing this for now.