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()).