Helping the optimizer along (__assume)

:slight_smile: Touche.

Doesn't llvm-gcc support GCC's builtin_expect?
Or does it transform it into nothing?

Cédric Venet wrote:

Technically, yes, but we can reword future standards to have the latitude to give compilation errors for conditions that can be proved to be false, then the implementation is conforming. We could always have a flag to control the behavior if people want/need it, though, I can't hardly see why they'd want it to compile if they assert something that is false.
    
you never seen assert(0 && "Not yet implemented"); ?
You may want to compile a program like this :slight_smile:
  

As I see it, under the proposed extension a compile-time false constant would error "if the code commits to executing it".

Heuristically, something like

void foo(int x)
{
    switch(x)
    {
    case 1: return;
    case 2: return;
    default: assert(0 && "not yet implemented")
    }
}

should itself compile, but then ideally

foo(3)

causes a compiler error as it commits to executing the assert.

Kenneth

Kenneth Boyd a écrit :

Cédric Venet wrote:

you never seen assert(0 && "Not yet implemented"); ?
You may want to compile a program like this :slight_smile:
  

As I see it, under the proposed extension a compile-time false constant
would error "if the code commits to executing it".

Heuristically, something like

void foo(int x)
{
    switch(x)
    {
    case 1: return;
    case 2: return;
    default: assert(0 && "not yet implemented")
    }
}

should itself compile, but then ideally

foo(3)

causes a compiler error as it commits to executing the assert.

Kenneth

Then not only the condition of the assert must be proved false, but the
assert must be proved to be actually reached in all possible code path
(not only be reachable, think about virtual function). I don't really
know the State of art of C++ code proofer but this seems pretty hard to
prove in most real word case. And then think about:

int main(int argc, const char* argv[]) {
  if(argc<2) return -1; // error in command line, exit early
  ...
  assert(0); // false assert
  ...
  return 0;
}

you will never be able to demonstrate that the assert is reached since
it is not reached in all code path, after all how can the compiler know
that the good code path is when argc>=2 and not the contrary ?

Clearly this functionnality is interesting, but there is lot of work to
do on the semantic to make it useful, and potentially need the
adjonction of additionnal user information like: error_code_path or
always_reached.

Regards,

Cédric

I've been playing around with something similar to this except the
never block actually can be reached but calls a new intrinsic
@llvm.abort() followed by an unreachable.

In my case, I'm converting branches into asserts and moving the branch
for the assert around to create bigger basic blocks. If I make sure to
use the same "never" block with the abort() call, -simplifycfg will
combine the assert conditions by ANDing them together. A later pass to
-instcombine can get rid of redundant checks.

Additionally because I've got plain branches in the IR, -predsimplify
automatically handles code simplification without modifications.

So in regards to a generic assert/assume instruction, I would imagine
something like |assert i1 %cond, label %notTrue|. So assume would
provide a "never" block that is unreachable as the label where I could
provide "abort" block as the label. (The reason why it wouldn't be an
intrinsic is that intrinsics can't take labels.)

Ed

Hi Danny,

Doesn't llvm-gcc support GCC's builtin_expect?
Or does it transform it into nothing?

This isnt the same as GCC's builtin-expect, to my knowledge.
Builtin_expect will leave branch prediction hints, but won't remove
the branch. This would remove the branch. There was a discussion of
adding this to GCC a long time ago
(http://gcc.gnu.org/ml/gcc/2003-11/msg00324.html), but it looks like
nothing came of it, though you probably know better than me.

Paul

Cédric Venet wrote:

Kenneth Boyd a écrit :
  

Cédric Venet wrote:
    

you never seen assert(0 && "Not yet implemented"); ?
You may want to compile a program like this :slight_smile:
  

As I see it, under the proposed extension a compile-time false constant would error "if the code commits to executing it".

Heuristically, something like

void foo(int x)
{
    switch(x)
    {
    case 1: return;
    case 2: return;
    default: assert(0 && "not yet implemented")
    }
}

should itself compile, but then ideally

foo(3)

causes a compiler error as it commits to executing the assert.
    
Then not only the condition of the assert must be proved false, but the
assert must be proved to be actually reached in all possible code path
(not only be reachable, think about virtual function).

I'm thinking a bit more locally than that; as I'd rather not mess with the halting problem.

In the example I gave, I want foo(3) to error even if it is unreachable. But I don't want an extended assert of the compile-time false constant, wrapped in the switch statement, to error.

[I'm visualizing this as having two extension intrinsics __precondition and __postcondition, and using the algebra of theses intrinsics to implement the automated proof. The compiler gets to inject these at AST creation "wherever reasonable". In particular, each block of the switch statement gets an implicit __postcondition at the very beginning, before any user code in the block.

The __postcondition(1!=x && 2!=x), implicitly injected at the start of the default: block, prevents the __precondition(0 && "not yet implemented"), injected by the assert, from immediately erroring. The idea is that is that

__postcondition(1!=x && 2!=x) __precondition(0 && "not yet implemented")

isn't "in normal form", we should first reduce to

__postcondition(1!=x && 2!=x) __precondition(0)

and then commutate:

__precondition(1!=x && 2!=x) __postcondition(1!=x && 2!=x) ]

... And then think about:

int main(int argc, const char* argv[]) {
  if(argc<2) return -1; // error in command line, exit early
  ...
  assert(0); // false assert
  ...
  return 0;
}

you will never be able to demonstrate that the assert is reached since
it is not reached in all code path,

That's fine. Then the assert goes off at runtime only in debug-mode, just like before.

....
  Clearly this functionnality is interesting, but there is lot of work to
do on the semantic to make it useful, and potentially need the
adjonction of additionnal user information like: error_code_path or
always_reached.
  

Yes.

Kenneth

Doesn't llvm-gcc support GCC's builtin_expect?

Yes, it supports it.

Or does it transform it into nothing?

Yep, that's how. :slight_smile: As Paul said, this is related but different than builtin_expect though.

-Chris

Sounds like the "bug" is in simplifycfg then. The IR is already fully capable of expressing this without a new builtin. Note that these annotations would have to be removed *sometime* in the optimizer pipeline, the policy decision is picking a place.

-Chris

This isnt the same as GCC's builtin-expect, to my knowledge.
Builtin_expect will leave branch prediction hints, but won't remove
the branch. This would remove the branch. There was a discussion of
adding this to GCC a long time ago
(http://gcc.gnu.org/ml/gcc/2003-11/msg00324.html), but it looks like
nothing came of it, though you probably know better than me.

The gcc VRP pass uses ASSERT_EXPR, which is the kind of thing being talked
about here, but ASSERT_EXPR didn't yet become something that front-ends can
generate: various parts of gcc still need to be taught about it.

Ciao,

Duncan.