c++ - programas - Forro de una función recursiva.

recursividad en programacion

Question

Cuando intento compilar este código:

#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 me da un error diciendo que la función reflect_mask_helper_0 no se puede insertar porque es recursiva. Sin embargo, la función de select también es recursiva, pero gcc la alinea sin quejarse. ¿Que me estoy perdiendo aqui?

(Necesito que sea recursivo, ya que constexpr funciones constexpr no pueden contener bucles en C ++ 11).

Mensaje de error:

% 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

Aquí está la solución que he encontrado, gracias al comentario de grek40 y a la respuesta de StoryTeller .

(En cuanto a mi problema anterior con la instancia de plantilla de función no utilizada que quedó en el binario compilado, lo resolví compilando el código original, sin los gnu::always_inline y gnu::flatten - con los argumentos -ffunction-sections -fdata-sections -Wl,--gc-sections .)

Ahora reflect_mask_helper_0 está dentro de una struct (porque C ++ no permite la especialización parcial de las plantillas de función), y el parámetro i de la función se convirtió en el parámetro Index de la plantilla de struct .

#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;
  }
}

Answer 2

Si revisa el código de ensamblaje resultante, si elimina los always_inline y flatten , puede ver que gcc realmente alinea todo correctamente.

Entonces, este problema es una cuestión de QoI. Tal vez, en ese punto, cuando se maneja always_inline , no puede estar en línea (de ahí el mensaje de error), pero de todos modos gcc decide en línea.

Por cierto, puede ajustar gcc, y con una pequeña modificación a su código, gcc puede compilarlo:

• pasar --param max-early-inliner-iterations=3 a gcc
• eliminar el atributo de flatten (ni idea, por qué es importante ...)

(Entonces, en realidad, este problema no tiene nada que ver con llamadas recursivas; desde el punto de vista del compilador, no importa si la función es recursiva o no, solo sigue el flujo del código, en cierta medida, por supuesto Aquí, la profundidad recursiva es solo 4, no es demasiado difícil de seguir para un compilador)

Answer 3

select realidad no se llama a sí mismo . Aparece al frente de la lista de tipos que recibió y luego llama a otra especialización de select<Type, ...> . El paquete de parámetros finales es diferente . Dado que esa "recursión" es esencialmente un conjunto finito de llamadas de función anidadas (diferentes funciones), GCC puede ver a través de ella, independientemente del parámetro de tiempo de ejecución.

Pero reflect_mask_helper_0 se llama a sí mismo , con los mismos argumentos de plantilla, indefinidamente. GCC no tiene forma de decir cuán profunda será esta recursión en tiempo de ejecución en tiempo de ejecución. Recuerde que una función constexpr sigue siendo una función regular que debe ser invocable en tiempo de ejecución.