Inlining of a recursive function

Question

When I try to compile this code:

#include <iostream>
#include <limits.h>

// End recursive template-expansion of function select below.
template <typename Type>
static inline constexpr Type select(unsigned index)
{ return Type(); }

// Select one of the items passed to it.
// e.g. select(0, a, b, c) = a; select(1, a, b, c) = b; etc.
template <typename Type, typename... Params>
[[gnu::always_inline]]
static inline constexpr Type select(unsigned index, Type value, Params... values)
{ return index == 0 ? value : select<Type>(index - 1, values...); }

template <typename Type>
[[gnu::always_inline]]
static inline constexpr Type reflect_mask_helper_1(Type mask, Type shift, Type value)
{ return ((value & mask) >> shift) | ((value << shift) & mask); }

template <typename Type>
[[gnu::always_inline]]
static inline constexpr Type reflect_mask_helper_0(unsigned i, Type value)
{
  return i == 0
    ? value
    : reflect_mask_helper_0(
        i - 1,
        reflect_mask_helper_1<Type>(
          select(i - 1, 0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0,
                        0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000),
          1 << (i - 1),
          value));
}

template <typename Type>
[[gnu::flatten]]
static inline constexpr Type reflect_mask(Type value)
{ return reflect_mask_helper_0(__builtin_ctz(sizeof(Type) * CHAR_BIT), value); }

int main(void) {
  for (int i = 0; i < 65536; i++) {
    std::cout << reflect_mask<uint16_t>(i) << std::endl;
  }
}

gcc gives me an error saying the function reflect_mask_helper_0 cannot be inlined because it is recursive. However, the function select is also recursive, but gcc inlines it without complaining. What am I missing here?

(I need it to be recursive, since constexpr functions cannot contain loops under C++11.)

Error message:

% g++ test.cpp -O3 -march=native -c
test.cpp: In function ‘constexpr Type reflect_mask_helper_0(unsigned int, Type) [with Type = short unsigned int]’:
test.cpp:23:30: error: inlining failed in call to always_inline ‘constexpr Type reflect_mask_helper_0(unsigned int, Type) [with Type = short unsigned int]’: recursive inlining
   23 | static inline constexpr Type reflect_mask_helper_0(unsigned i, Type value)
      |                              ^~~~~~~~~~~~~~~~~~~~~
test.cpp:27:28: note: called from here
   27 |     : reflect_mask_helper_0(
      |       ~~~~~~~~~~~~~~~~~~~~~^
   28 |         i - 1,
      |         ~~~~~~              
   29 |         reflect_mask_helper_1<Type>(
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   30 |           select(i - 1, 0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0,
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   31 |                         0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000),
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   32 |           1 << (i - 1),
      |           ~~~~~~~~~~~~~     
   33 |           value));
      |           ~~~~~~~           
test.cpp: In function ‘int main()’:
test.cpp:23:30: error: inlining failed in call to always_inline ‘constexpr Type reflect_mask_helper_0(unsigned int, Type) [with Type = short unsigned int]’: recursive inlining
   23 | static inline constexpr Type reflect_mask_helper_0(unsigned i, Type value)
      |                              ^~~~~~~~~~~~~~~~~~~~~
test.cpp:27:28: note: called from here
   27 |     : reflect_mask_helper_0(
      |       ~~~~~~~~~~~~~~~~~~~~~^
   28 |         i - 1,
      |         ~~~~~~              
   29 |         reflect_mask_helper_1<Type>(
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   30 |           select(i - 1, 0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0,
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   31 |                         0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000),
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   32 |           1 << (i - 1),
      |           ~~~~~~~~~~~~~     
   33 |           value));
      |           ~~~~~~~

Answer 1

select doesn't actually calls itself. It pops the front of the type list it received and then calls another specialization of select<Type, ...>. The trailing parameter pack is different. Since that "recursion" is essentially a finite set of nested function calls (different functions), GCC can see right through it, regardless of the run-time parameter.

But reflect_mask_helper_0 does call itself, with the same template arguments, indefinitely. GCC has no way to tell how deep this run-time recursion will go at run-time. Recall that a constexpr function is still a regular function that must be invocable at run-time.

Answer 2

If you check out the resulting assembly code, if you remove the always_inline and flatten attributes, you can see that gcc actually inlines everything correctly.

So, this issue is a QoI thing. Maybe, at that point, when always_inline handled, it cannot be inlined (hence the error message), but gcc decides to inline it afterwards anyways.

Btw., you can finetune gcc, and with a little modification to your code, gcc can compile it:

• pass --param max-early-inliner-iterations=3 to gcc
• remove the flatten attribute (no idea, why it matters...)

(So, actually, this issue has nothing to do with recursive calls - from the compiler standpoint, it doesn't matter whether the function is recursive, or not, it just follows the flow of the code - to a certain extent, of course. Here, recursive depth is just 4, it is not too hard to follow for a compiler)