A better __builtin_constant_p

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

A better __builtin_constant_p

Pip Cet
I'd like to introduce a new builtin, __builtin_constant_function_p,
with nicer semantics and better performance than __builtin_constant_p.


Background:

I want to define an assert_or_assume() macro that is equivalent to
assume() or assert(), whichever results in better compiled code.

I'd like to use __builtin_constant_p to decide whether
assert_or_assume evaluates this construct:

if (!(CONDITION))
  __builtin_unreachable ();

My current idea is to write:

if (__builtin_constant_p (!(CONDITION) != !(CONDITION)))
  if (!(CONDITION))
    __builtin_unreachable ();

This would check that evaluating CONDITION "twice" (in undefined
order) results in the same truth value; if CONDITION includes, for
example, external function calls, we won't be able to prove that, so
the expensive construct would be skipped.  However, for common
conditions such as read-only logical and arithmetic expressions,
!(CONDITION) != !(CONDITION) will be folded to 0, which
__builtin_constant_p can then recognize as a constant.


The Problem:

However, it seems that with trunk GCC, __builtin_constant_p always
returns false for expressions which contain calls to functions not
explicitly marked with attribute((const)), even when those functions
are both inlined and found to allow the const attribute by
-Wsuggest-attr=const.

This is in contrast to macros which work just fine in
__builtin_constant_p's argument.  So, in this case, an inline function
isn't as fast as a macro.

The problem is that __builtin_constant_p must fold its argument very
early, before gimplification, to avoid evaluation of the argument.


My proposed solution:

The idea I'm currently playing around with is to add a new
__builtin_constant_function_p builtin, which folds to 1 as soon if its
argument can be shown, at compile time, to be a pointer to a constant
function.  This can be used in conjunction with inner functions (C
only) to redefine constant_p as:

#define constant_p(EXPR) ({ int inner(void) { return EXPR; };
__builtin_constant_function_p (inner); })

As mentioned, this definition of constant_p would be superior to
__builtin_constant_p while also ensuring the expression itself is
never evaluated.


Patch:

In early test runs, the attached patch appears to work, but I'm
inexperienced when it comes to GCC internals, and I also find that
people often disagree with me for good reasons.


Limitations:

This currently works for C only (using lambdas to expand it to C++
looks like it ought to be possible to me).

Compilation time probably increases significantly, because an inner
function is generated and optimized only to be eventually
discarded. It's also possible this affects code generation in the rest
of the outer function.

This absolutely hasn't been tested enough. I'm attaching my main test
case.

We give up in the fold-builtins pass. It might be a better idea to
wait for the last such pass, if we could.

For very good reasons, this doesn't work as I naively expected it
would for functions marked with attribute((const)), because the
compiler cannot assume that those functions, if called, would return.

Questions:

Am I totally on the wrong track here?

Should we have __builtin_assume?

Should we instead fix our code so forgetting a "const" attribute won't
hurt performance, if it can be inferred?

Should there be a new function attribute to mark functions that may be
assumed by the compiler to return?

Should we fix after-the-fact assume()s to work better?

constant_function_p.c (608 bytes) Download Attachment
0001-Add-a-__builtin_constant_function_p-builtin.patch (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: A better __builtin_constant_p

Andrew Sutton
> Am I totally on the wrong track here?

That depends on what you want your assumptions to do. This definitely
doesn't solve the problems I'm having implementing C++ contracts,
especially axioms, which can involve declarations of undecidable
functions. For example, is_reachable(p, q) for a pair of pointers
can't be implemented for normal systems (maybe it could with one
sanitizer or another), but it could be used for static analyzers (or
optimizers maybe?) that understood the inherent meaning of a "call" to
that function.

Our problem is that we need to communicate an assumption syntactically
through to GIMPLE, but without the usual ODR requirements of C++.
Specifically, we need to allow assumptions on conditions that use
functions that are declared but not defined anywhere.

Now, I'm not an optimizer expert at all, so I could be way wrong, but
my sense is that depending on the constantness of a function will not
help you get better assumptions, because you aren't necessarily
interested in the value of the expression, only the facts introduced
by it (e.g., for some x, x == 5).

> Should we have __builtin_assume?

I'd like it. The "if (predicate) unreachable" pattern doesn't work for
C++ contracts. This works just fine for C++ contracts in LLVM.

There's another solution to the problem: define undefinable functions
as "= undecidable".

> Should we instead fix our code so forgetting a "const" attribute won't
> hurt performance if it can be inferred?

Probably? If you have an assertion that you want to promote to an
assumption vial __builtin_assume (using LLVM), you'll get a warning.
Throw in -werror, and your program doesn't compile. That seems
unfortunate.

This has come up in WG21 discussions around contracts. There's some
momentum to relax the requirement that asserted contracts don't have
side effects because it's sometimes useful to call predicates that log
something, throw, terminate, etc. If we allow "promotion" of
assertions to assumptions, then that requirement is simply going to
break a lot of code. Also, most functions aren't declared const, and
requiring that broadly would be a non-starter for adding contracts to
a program.