¿Puedo insinuar el optimizador dando el rango de un entero?

Estoy usando un inttipo para almacenar un valor. Según la semántica del programa, el valor siempre varía en un rango muy pequeño (0 - 36), y int(no a char) se usa solo debido a la eficiencia de la CPU.

Parece que se pueden realizar muchas optimizaciones aritméticas especiales en un rango tan pequeño de enteros. Muchas llamadas de función en esos enteros pueden optimizarse en un pequeño conjunto de operaciones "mágicas", y algunas funciones pueden incluso optimizarse en búsquedas de tablas.

Entonces, ¿es posible decirle al compilador que esto intsiempre está en ese rango pequeño, y es posible que el compilador haga esas optimizaciones?

Sí, es posible. Por ejemplo, gccpuede usar __builtin_unreachablepara decirle al compilador acerca de condiciones imposibles, así:

if (value < 0 || value > 36) __builtin_unreachable();

Podemos envolver la condición anterior en una macro:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

Y úsalo así:

assume(x >= 0 && x <= 10);

Como puede ver , gccrealiza optimizaciones basadas en esta información:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Produce:

func(int):
    mov     eax, 17
    ret

Sin embargo, una desventaja es que si su código alguna vez rompe tales suposiciones, obtendrá un comportamiento indefinido .

No le avisa cuando esto sucede, incluso en las versiones de depuración. Para depurar / probar / atrapar errores con suposiciones más fácilmente, puede usar una macro híbrida asumir / afirmar (créditos a @David Z), como esta:

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

En las compilaciones de depuración ( NDEBUG sin definir), funciona como un assertmensaje de error de impresión ordinario y un abortprograma 'ing', y en las compilaciones de lanzamiento utiliza una suposición, produciendo código optimizado.

Sin embargo, tenga en cuenta que no es un sustituto de la versión regular assert: condpermanece en las versiones de lanzamiento, por lo que no debe hacer algo así assume(VeryExpensiveComputation()).

Hay soporte estándar para esto. Lo que debe hacer es incluir stdint.h( cstdint) y luego usar el tipo uint_fast8_t.

Esto le dice al compilador que solo está usando números entre 0 y 255, pero que es libre de usar un tipo más grande si eso proporciona un código más rápido. Del mismo modo, el compilador puede suponer que la variable nunca tendrá un valor superior a 255 y luego realizar optimizaciones en consecuencia.

La respuesta actual es buena para el caso cuando sabe con certeza cuál es el rango, pero si aún desea un comportamiento correcto cuando el valor está fuera del rango esperado, entonces no funcionará.

Para ese caso, descubrí que esta técnica puede funcionar:

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

La idea es una compensación de datos de código: está moviendo 1 bit de datos (ya sea x == c) a la lógica de control .
Esto sugiere al optimizador que, xde hecho, es una constante conocida c, lo que lo alienta a alinear y optimizar la primera invocación por fooseparado del resto, posiblemente en gran medida.

Sin fooembargo, asegúrese de factorizar el código en una sola subrutina , no duplique el código.

Ejemplo:

Para que esta técnica funcione, debe ser un poco afortunado: hay casos en los que el compilador decide no evaluar las cosas estáticamente, y son algo arbitrarios. Pero cuando funciona, funciona bien:

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x\n", r);
}

Simplemente use -O3y observe las constantes previamente evaluadas 0x20y 0x30een la salida del ensamblador .

Solo estoy diciendo que si quieres una solución que sea más estándar en C ++, puedes usar el [[noreturn]]atributo para escribir el tuyo unreachable.

Así que volveré a utilizar el excelente ejemplo de Deniss para demostrar:

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Lo que, como puede ver , da como resultado un código casi idéntico:

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

La desventaja es, por supuesto, que recibe una advertencia de que una [[noreturn]]función, de hecho, regresa.