3

Say I have an assert() something like assert( x < limit ); I took a look at the behaviour of the optimiser in GDC in release and debug builds with the following snippet of code:

uint cxx1( uint x )
    {
    assert( x < 10 );
    return x % 10;
    }

uint cxx1a( uint x )
in  { assert( x < 10 ); }
body
    {
    return x % 10;
    }

uint cxx2( uint x )
    {
    if ( !( x < 10 ))
       assert(0);
    return x % 10;
    }

Now when I build in debug mode, the asserts have the very pleasing effect of triggering huge optimisation. GDC gets rid of the horrid code to do the modulo operation entirely, because of its knowledge about the possible range of x due to the assert’s if-condition. But in release mode, the if-condition is discarded, so all of a sudden, the horrid code comes back, and there is no longer any optimisation in cxx1() nor even in cxx1a(). This is very ironic, that release mode generates far worse code than debug code. Of course, no-one wants executable code belonging to the if-tests to be present in release code as we must lose all that overhead.

Now ideally, I would want to express the condition in the sense of communicating information to the compiler, regardless of release / debug builds, about conditions that may always be assumed to be true, and so such assumptions can guide optimisation in very powerful ways.

I believe some C++ compilers have something called __assume() or some such, but memory fails me here. GCC has a __builtin_unreachable() special directive which might be useable to build an assume() feature. Basically if I could build my own assume() directive it would have the effect of asserting certain truths about known values or known ranges and exposing / publishing these to optimisation passes regardless of release / debug mode but without generating any actual code at all for the assume() condition in a release build, while in debug mode it would be exactly the same as assert().

I tried an experiment which you see in cxx2 which triggers optimisation always, so good job there, but it generates what is morally debug code for the assume()'s if-condition even in release mode with a test and a conditional jump to an undefined instruction in order to halt the process.

Does anyone have any ideas about whether this is solvable? Or do you think this is a useful D compiler fantasy wish-list item?

Cecil Ward
  • 597
  • 2
  • 13

2 Answers2

4

As far as I know __builtin_unreachable is the next best replacement for an assume like function in GCC. In some cases the if condition might still not get optimized out though: "Assume" clause in gcc

The GCC builtins are available in GDC by importing gcc.builtins. Here's an example how to wrap the __builtin_unreachable function:

import gcc.builtins;

void assume()(bool condition)
{
  if (!condition)
    __builtin_unreachable();
}

bool foo(int a)
{
  assume(a > 10);
  return a > 10;
}

There are two interesting details here:

  1. We don't need string mixins or similarily complicated stuff. As long as you compile with -O GDC will completely optimize the function call anyway.
  2. For this to work the assume function must get inlined. Unfortunately inlining normal functions is not completely supported when assume is in a different module as the calling function. As a workaround we use a template with 0 template arguments. This should make sure inlining can always work.

You can test and modify this example here: explore.dgnu.org

Now we (GDC developers) could easily rewrite assert(...) to if(...) __builtin_unreachable() in release mode. But this could break some code so dmd should implement this first.

Community
  • 1
  • 1
jpf
  • 527
  • 3
  • 7
  • I think rewriting assert in the way proposed would be a worthwhile change, producing better code, and agree dmd ought to do it first if anyone does. However assert/assume or whatever should not allow side effects in the condition - that may already be true for assert, I haven't checked. – Cecil Ward Feb 12 '17 at 22:25
  • I would probably add an `assert()` in at the start of jpf's `assume()` so that you get the correct behaviour in debug builds. – Cecil Ward Feb 13 '17 at 00:34
  • What I would really like is for the compiler to evaluate the condition at compile time if it can and then fail at compile time if the condition is false. I can't use `static if` just like that, and using traits to check if a `static if` compiles or not is no good because the compiler just throws out an error if the expression contains variables so a 'compiles' check won't help. There are plenty of cases where the compiler knows what the value of the expression actually is even if it contains runtime variables, and I would definitely like it to always fail at compile-time. – Cecil Ward Feb 13 '17 at 00:39
  • Using jpf's technology with the latest versions of GDC in Matt Godbolt's Compiler Explorer I can see case where the compiler emits no code because the `__builtin_unreachable()` tells it not to. When this happens in a case where the compiler knows that the value of the condition is false, that would definitely be a case where we want to make it fail at compile time, or if that's completely impossible, then an `assert(0)` (that is, a `ud2` instruction on x86) although that is far less desireable. – Cecil Ward Feb 13 '17 at 00:43
  • One really bad thing about using assume if we don't improve this is that an assume can make a subsequent test `if (some_other_cond) assert(0);` disappear altogether, so although this might be a release-build test we've silently disabled it, which is very bad. – Cecil Ward Feb 13 '17 at 00:49
  • I don't know what I am talking about here, but I assume someone will set me straight. Could we write a specialisation of the template for the case where the value of condition is 'known' to be false, so that we could have different code, rather than just ending up with a different inline expansion solely because of the optimiser? I ask because I'm trying to fix the known-bad-condition case so that it implements early fail or at least always-fail. – Cecil Ward Feb 13 '17 at 00:54
  • Is it possible to implement this using string mixins? Would this create a solution less dependent on accidental details of compiler behaviour - i.e. the fact that it happens to expand the template inline first _in the context of the calling function_ like a macro and then applies unreachable to the calling function, rather than generating an assume function first then calling it with a function call. If it works, I shouldn't knock it, but right now it has to be tested with every compiler, unless we treat it as a stop-gap until `assume()` can be promoted to a special function – Cecil Ward Feb 13 '17 at 01:05
  • .. or unless assert() is upgraded to take over its job making assume completely unnecessary. – Cecil Ward Feb 13 '17 at 01:06
  • 1
    Death bug? I tried `const uint x = 100; assume( x < 2 ); return x < 10;` compiling in release mode with -O3 causes garbage x86-64 code to be generated (no ret insn from the function) by GCC. So in this case, simply adding the line containing an assume() turns working code into garbage even when the subsequent parts of the _algorithm_ are not tuned to only work in a particular case. You can always make good code into bad code by including such directives if necessary code is deleted by the optimiser, for example assume alignment. But here adding an assume simply kills you for no reason. – Cecil Ward Feb 13 '17 at 02:20
  • A string mixin version is possible, although the calling syntax probably needs to be different then (i.e. pass the condition as a string). String mixins have other drawbacks though and are therefore usually considered to be a last resort option. Your bug example is an extreme case, but this is the reason why I've argued against rewriting `assert=>assume` in the past: If you add a wrong `assume` all bets are off. I guess GCC simply removes as many instructions as possible which in this case seems quite idiotic but similar things can happen in more complex examples where this difficult to detect – jpf Feb 13 '17 at 10:40
0

OK, I really dont know what you want? cxx2 is solution some more info

Kozzi11
  • 2,413
  • 12
  • 17
  • cxx2 contains generated code for the if-condition even in release mode. The aim is to _lose this code_ as happens with the code for the condition check in an assert. This is what I said earlier, but perhaps I didn't make it clear. – Cecil Ward Feb 10 '17 at 00:34
  • Actually, gaining access to GCC's builtin_unreachable might do it, but then that's only good for one compiler, but then after all, this is entirely about optimisation. – Cecil Ward Feb 10 '17 at 00:36
  • I forgot to ask how I might package the cxx2 solution up into something neat of the form `assume(cond)`, assuming we can do no better. I have no idea how to do this without a preprocessor, lack of experience with D. – Cecil Ward Feb 10 '17 at 00:39