5

Is there any way to indicate to the compiler that you know the value of a particular variable must be within a particular range at a certain point in the code, to assist the compiler with optimizing? I'm writing a library that makes it possible to know the range of some variables at compile time, and it would be nifty if it could somehow communicate this information to the compiler so that the compiler could use it for optimization. I'd like to add support for any compilers where it would work even if it couldn't be made to work for all of them (it sounds like the sort of thing that some compilers could have as an extension, but I haven't found any). I know I could write something like this:

if(x < COMPILE_TIME_MIN or x > COMPILE_TIME_MAX)
    return;
// compiler will assume for code below that x is in range COMPILE_TIME_MIN..COMPILE_TIME_MAX

But that's a runtime check. Maybe there's some trick to get the compiler to make an assumption about the range without such a check?

Joseph Garvin
  • 20,727
  • 18
  • 94
  • 165
  • 2
    Do you have any thoughts on what type of optimisation this would help with? – Oliver Charlesworth Dec 12 '11 at 22:57
  • If you use templates, you can actually do compile time checking if all your information is known at compile time. – Mike Bailey Dec 12 '11 at 22:57
  • You are using the phrase "the compiler", but you never tell us which one. Presumably you mean some version of g++ or Visual C++, but that isn't clear. Optimization in general is not addressed by the Standard, so anything you could possibly do here is implementation-specific. – David Thornley Dec 12 '11 at 22:59
  • @OliCharlesworth: The Visual C++ documentation, referenced below, contains one example involving a switch with an unreachable default case. – James McNellis Dec 12 '11 at 23:01
  • @JosephGarvin, do you mean the values are never outside this range or you want to make sure they stay outside the range? In the first case, you don't really need an `if`, since you are sure (for example by proof) that the values are always in that range. I'm saying because at least one of the answers assumes you mean the first case (the answer with `assert`) – Shahbaz Dec 13 '11 at 00:19
  • @Shahbaz: I mean that the values are never outside the range, so yes for example if I had a proof. assert out of the box doesn't do the trick, because it gets disabled when NDEBUG is defined. – Joseph Garvin Dec 13 '11 at 02:18
  • @OliCharlesworth: Generally the information can help the compiler remove dead code e.g. determining the default case of a switch can't be reached, or eliminating bounds checking, etc. – Joseph Garvin Dec 13 '11 at 02:20
  • @JosephGarvin, so if by proof you know that the values **never** go outside of the range, why do you need an `if`? For example, if you have a 32bit unsigned int and you divide it by `1,000,000,000`, then checking to make sure it is in the range `[0,4]` is absolutely unnecessary. – Shahbaz Dec 13 '11 at 13:54
  • @Shahbaz: I'd be using this trick inside functions that are likely to be inlined, where at the call site there may be ifs after calls to my function. Also the call sites are inside templated functions where the ifs may or may not be necessary depending on template parameters. – Joseph Garvin Dec 18 '11 at 02:06

3 Answers3

6

Any such "hint" would be compiler-specific.

As an example, Visual C++ allows you to provide such a hint using the __assume intrinsic.

(Other compilers may also provide such intrinsics, but I am not familiar enough with other compilers to provide any further information. Consult your compiler's documentation if you are interested.)

James McNellis
  • 348,265
  • 75
  • 913
  • 977
  • 3
    From my own googling, gcc 4.5 and above can pass this info along too with the same syntax using `#define __assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)` – Drew Dormann Dec 12 '11 at 23:09
  • @DrewDormann Interesting. I think it would be better to define a single macro `#define ASSUME_THIS_THING(x) ...` that expands to `__assume(x)` on Visual C++ and your snippet on gcc. It's best not to define your own macro with a compiler-reserved name (like `__assume`). – James McNellis Dec 12 '11 at 23:18
  • Wow, that's awesome. James, care to merge Drew's info into your answer? Then I'll mark as accepted. – Joseph Garvin Dec 12 '11 at 23:19
  • Also I think the do/while part is only needed in C. In C++ can just surround the if with braces. – Joseph Garvin Dec 13 '11 at 00:31
  • @Joseph Garvin with only braces, your C++ compiler may make noise when the macro is followed by a semicolon. – Drew Dormann Dec 15 '11 at 16:55
  • @Shahbaz: I'd be using this trick inside functions that are likely to be inlined, where at the call site there may be ifs after calls to my function. Also those call sites are inside template functions where the ifs are sometimes and sometimes not necessary depending on the types passed as template parameters. – Joseph Garvin Dec 18 '11 at 02:02
3

It's not standard, but with gcc, there comes a command called __builtin_expect, with macros defined as likely and unlikely that serve your purpose. See here for example which talks about using them in kernel-space, but __builtin_expect is a gcc extension and could be used in user-space also (see this question), even if likely and unlikely are not defined.

Community
  • 1
  • 1
Shahbaz
  • 46,337
  • 19
  • 116
  • 182
  • There's a typo in the above comment: it should be `__builtin_expect`. GCC only uses the expectation as a hint: it won't avoid cases where the expectation is not met. – Matt Godbolt Sep 12 '12 at 16:54
  • @MattG, yeah I don't know how I had written `buildtin`! – Shahbaz Sep 12 '12 at 22:51
0

I don't know of any C++ compilation techniques that take advantage of this information, but I do know of various static analysis techniques that do; the common way to "tell" something to those tools would be via asserts, for instance:

assert(x > COMPILE_TIME_MIN);
assert(x < COMPILE_TIME_MAX);

But usually those tools would also be able to analyze things such as "if conditions" by themselves, so there's no special need to do so.

Additionally, if the range is really small, you can also represent it in a smaller-sized variable - e.g. using a short or char - and adding COMPILE_TIME_MIN. That can help such tools, though I don't know about the compilation itself.

And finally, as in all optimization approaches, I'd recommend first profiling your code to see if this could really be a bottleneck. Additionally, keep in mind that compilers are designed for optimizing "normal" code - hand-optimization could certainly help, just do it carefully.

Oak
  • 26,231
  • 8
  • 93
  • 152