Can I hint the optimizer by giving the range of an integer?

Question

I am using an int type to store a value. By the semantics of the program, the value always varies in a very small range (0 - 36), and int (not a char) is used only because of the CPU efficiency.

It seems like many special arithmetical optimizations can be performed on such a small range of integers. Many function calls on those integers might be optimized into a small set of "magical" operations, and some functions may even be optimized into table look-ups.

So, is it possible to tell the compiler that this int is always in that small range, and is it possible for the compiler to do those optimizations?

Answer 1

Yes, it is possible. For example, for gcc you can use __builtin_unreachable to tell the compiler about impossible conditions, like so:

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

We can wrap the condition above in a macro:

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

And use it like so:

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

As you can see, gcc performs optimizations based on this information:

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

Produces:

func(int):
    mov     eax, 17
    ret

One downside, however, that if your code ever breaks such assumptions, you get undefined behavior.

It doesn't notify you when this happens, even in debug builds. To debug/test/catch bugs with assumptions more easily, you can use a hybrid assume/assert macro (credits to @David Z), like this one:

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

In debug builds (with NDEBUG not defined), it works like an ordinary assert, printing error message and abort'ing program, and in release builds it makes use of an assumption, producing optimized code.

Note, however, that it is not a substitute for regular assert - cond remains in release builds, so you should not do something like assume(VeryExpensiveComputation()).

Answer 2

There is standard support for this. What you should do is to include stdint.h (cstdint) and then use the type uint_fast8_t.

This tells the compiler that you are only using numbers between 0 - 255, but that it is free to use a larger type if that gives faster code. Similarly, the compiler can assume that the variable will never have a value above 255 and then do optimizations accordingly.

Answer 3

The current answer is good for the case when you know for sure what the range is, but if you still want correct behavior when the value is out of the expected range, then it won't work.

For that case, I found this technique can work:

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

The idea is a code-data tradeoff: you're moving 1 bit of data (whether x == c) into control logic.
This hints to the optimizer that x is in fact a known constant c, encouraging it to inline and optimize the first invocation of foo separately from the rest, possibly quite heavily.

Make sure to actually factor the code into a single subroutine foo, though -- don't duplicate the code.

Example:

For this technique to work you need to be a little lucky -- there are cases where the compiler decides not to evaluate things statically, and they're kind of arbitrary. But when it works, it works well:

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

Just use -O3 and notice the pre-evaluated constants 0x20 and 0x30e in the assembler output.

Answer 4

I am just pitching in to say that if you may want a solution that is more standard C++, you can use the [[noreturn]] attribute to write your own unreachable.

So I'll re-purpose deniss' excellent example to demonstrate:

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

Which as you can see, results in nearly identical code:

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

The downside is of course, that you get a warning that a [[noreturn]] function does, indeed, return.