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

Here’s the solution I’ve found, thanks to grek40’s comment and to StoryTeller’s answer.

(As for my previous problem with the unused function template instance left in the compiled binary, I solved it by compiling the original code — without the gnu::always_inline and gnu::flatten attributes — with the arguments -ffunction-sections -fdata-sections -Wl,--gc-sections.)

Now reflect_mask_helper_0 is inside a struct (because C++ doesn’t allow partial specialization of function templates), and the i parameter of the function became the Index parameter of the struct template.

#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, unsigned Index>
struct reflect_mask_helper_0
{
  [[gnu::always_inline]]
  static inline constexpr Type invoke(Type value)
  {
    return reflect_mask_helper_0<Type, Index - 1>::call(
      reflect_mask_helper_1<Type>(
        static_cast<Type>(select(Index - 1,
          0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0,
          0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000)),
        1 << (Index - 1),
        value));
  }
};

template <typename Type>
struct reflect_mask_helper_0<Type, 0>
{
  [[gnu::always_inline]]
  static inline constexpr Type invoke(Type value) { return value; }
};

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

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