[C++] avoid tail call based on different compiler

// BLOCK_TAIL_CALL_OPTIMIZATION
//
// Instructs the compiler to avoid optimizing tail-call recursion. This macro is
// useful when you wish to preserve the existing function order within a stack
// trace for logging, debugging, or profiling purposes.
//
// Example:
//
//   int f() {
//     int result = g();
//     BLOCK_TAIL_CALL_OPTIMIZATION();
//     return result;
//   }
#if defined(__pnacl__)
#define BLOCK_TAIL_CALL_OPTIMIZATION() if (volatile int x = 0) { (void)x; }
#elif defined(__clang__)
// Clang will not tail call given inline volatile assembly.
#define BLOCK_TAIL_CALL_OPTIMIZATION() __asm__ __volatile__("")
#elif defined(__GNUC__)
// GCC will not tail call given inline volatile assembly.
#define BLOCK_TAIL_CALL_OPTIMIZATION() __asm__ __volatile__("")
#elif defined(_MSC_VER)
#include 
// The __nop() intrinsic blocks the optimisation.
#define ABSL_BLOCK_TAIL_CALL_OPTIMIZATION() __nop()
#else
#define ABSL_BLOCK_TAIL_CALL_OPTIMIZATION() \
  if (volatile int x = 0) {                 \
    (void)x;                                \
  }
#endif

[Go][Java]&[Clang] tail call optimization status in 2019

Go:
Not going to happen in Go2 as well.
https://github.com/golang/go/issues/22624

Java:
JVM doesn’t support Tail Call Optimization.
https://softwareengineering.stackexchange.com/a/272086
https://www.youtube.com/watch?v=2y5Pv4yN0b0&t=1h02m18s

Clang:
Tail call optimization, callee reusing the stack of the caller, is currently supported on x86/x86-64, PowerPC, and WebAssembly.
It is performed on x86/x86-64 and PowerPC if:

• Caller and callee have the calling convention fastcc, cc 10 (GHC calling convention) or cc 11 (HiPE calling convention). 
• The call is a tail call - in tail position (ret immediately follows call and ret uses value of call or is void). 
• Option -tailcallopt is enabled. 
• Platform-specific constraints are met. 

x86/x86-64 constraints: 

• No variable argument lists are used. 
• On x86-64 when generating GOT/PIC code only module-local calls (visibility = hidden or protected) are supported.

[C++][clang][gcc] tail call optimization

code:
https://godbolt.org/g/axwo2h

#include <iostream>
using namespace std;

int voidret(int i)
{
    if (i < 0) {
        i++;
    }
    else {
        i--;
    }
    return voidret(i);
}


int main()
{
    auto i = voidret(10);
}

clang++ -O3 result:

2030951640

g++ -O3 result:

indifinite

clang++ -O3 assembly:

voidret(int):                            # @voidret(int)
        ret
main:                                   # @main
        xor     eax, eax
        ret
_GLOBAL__sub_I_example.cpp:             # @_GLOBAL__sub_I_example.cpp
        push    rax
        mov     edi, offset std::__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edi, offset std::ios_base::Init::~Init() [complete object destructor]
        mov     esi, offset std::__ioinit
        mov     edx, offset __dso_handle
        pop     rax
        jmp     __cxa_atexit            # TAILCALL

g++ -O3 assembly:

voidret(int):
.L2:
        jmp     .L2
main:
        mov     edi, 10
        call    voidret(int)
_GLOBAL__sub_I_voidret(int):
        sub     rsp, 8
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        add     rsp, 8
        jmp     __cxa_atexit

Reasoning:
https://stackoverflow.com/questions/18478078/clang-infinite-tail-recursion-optimization

quote:
While both g++ and clang++ are able to compile C++98 and C++11 code, clang++ was designed from the start as a C++11 compiler and has some C++11 behaviors embedded in its DNA.

With C++11 the C++ standard became thread aware, and that means that now there are some specific thread behavior. In particular 6.8.2.2 states:
The implementation may assume that any thread will eventually do one of the following:

• terminate,
• make a call to a library I/O function,
• perform an access through a volatile glvalue, or
• perform a synchronization operation or an atomic operation.

[ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. — end note ]

And that is precisely what clang++ is doing when optimizing. It sees that the function has no side effects and removes it even if it does not terminate.

[C++] Using Surrogate Call Function for speed up member function name resolution.

Reference:
https://mpark.github.io/programming/2017/08/08/using-killed-the-FUN-on-GCC-5/

[C++] Value vs. Reference type conversion overload ranking tie breaker rule.

Surrogate Call Function:
http://en.cppreference.com/w/cpp/language/overload_resolution#Call_to_a_class_object

sample code:

template <typename Head, typename... Tail>
struct FUN;

// Base case.
template <typename Head>
struct FUN<Head> {
  using F = Head (*)(Head);
  operator F() const;
};

// Recursive case.
template <typename Head, typename... Tail>
struct FUN : FUN<Tail...> {
  using F = Head (*)(Head);
  operator F() const;
};

or just:

template <typename T>
struct FUN_leaf {
  using F = T (*)(T);
  operator F() const;
};

template <typename... Ts>
struct FUN : FUN_leaf<Ts>... {};

Originally(SLOW) using inheritance introduce function name overloading for avoiding hidden ancestor type's function name:

template <typename Head, typename... Tail>
struct FUN;

// Base case.
template <typename Head>
struct FUN<Head> {
  Head operator()(Head) const;
};

// Recursive case.
template <typename Head, typename... Tail>
struct FUN : FUN<Tail...> {
  using FUN<Tail...>::operator();
  Head operator()(Head) const;
};

Surrogate function example:

int f1(int);
int f2(float);

typedef int (*fp1)(int);
typedef int (*fp2)(float);

struct A {
  operator fp1() { return f1; }
  operator fp2() { return f2; }
} a;

int i = a(1);  // calls f1 via pointer returned from conversion function

[C++] Tail Call op Articles

LLVM Tail call optimization
stackoverflow : LLVM tail call optimization
http://en.wikipedia.org/wiki/Tail_call

Tail call optimization, callee reusing the stack of the caller, is currently supported on x86/x86-64 and PowerPC, and AArch64.

It is performed if:

• Caller and callee have the calling convention fastcc, cc 10 (GHC calling convention) or cc 11 (HiPE calling convention). 
• The call is a tail call - in tail position (ret immediately follows call and ret uses value of call or is void). 
• Option -tailcallopt is enabled. 
• Platform-specific constraints are met. 
• x86/x86-64 constraints: 
• No variable argument lists are used. 
• On x86-64 when generating GOT/PIC code only module-local calls (visibility = hidden or protected) are supported.
• AArch64 constraints: 
• No variable argument lists are used.

[C++] tail call

Reference:
Tackling C++ Tail Calls

Tail Call Optimization (TCO), dependency, broken debug builds in C and C++ — and gcc 4.8

http://en.wikipedia.org/wiki/Tail_call

[C/C++][NOTE] Tail recursive call

Reference:
Tail Call
Tail recursion in C++
Tail Recursion in C++ with multiple recursive function calls
Does C++11 does optimise away tail recursive calls in lambdas?
Tackling C++ Tail Calls

https://llvm.org/docs/CodeGenerator.html#tail-call-optimization

#include <iostream>                                                                       
                                                                                          
template<typename T, int MeaningOfLife>                                                   
struct Fun                                                                                
{                                                                                         
   Fun()                                                                                  
   {                                                                                      
      std::move(*this).how(MeaningOfLife);                                                
   }                                                                                      
                                                                                          
   T how(int i)&&                                                                         
   {                                                                                      
      using namespace std;                                                                
      cout << "how ";                                                                     
      return std::move(*this).areyou(i);                                                  
   }                                                                                      
                                                                                          
   T areyou(int i)&&                                                                      
   {                                                                                      
      using namespace std;                                                                
      cout << "are you?" << endl;                                                         
      return std::move(*this).how(i);                                                     
   }                                                                                      
};                                                                                        
                                                                                          
                                                                                          
int main()                                                                                
{                                                                                         
   Fun<void, 42>();                                                                       
} 

Tail recursive Use with -O3 and without optimize to see how compiler optimizing the Tail recursive call. No more stack-overflow for -O3

* Expand in the callee, not the caller.
* Tail call could be translated to a local loop structure