Detecting compile-time evaluation

[Gonzalo BG]

AFAIK none of the major C++ compilers provide a way to detect whether a constexpr function is being evaluated at compile-time.

This is unfortunate. I have a constexpr function with bad run-time performance. Rewriting it to use SSE4.2 intrinsics improves its performance by 3.5x. Those intrinsics are not constexpr functions. I could imagine similar situations in which one would need to go down to inline assembly to deliver acceptable run-time performance in constexpr functions. Inline assembly cannot be neither standardized nor evaluated at compile-time. 

So I must choose: either constexpr (which my function already was) but horrible run-time performance, or run-time performance and breakage (because my function was already constexpr). This is an uncomfortable spot to be in. In particular, since constexpr functions are not limited to compile-time evaluation.

There are some unreliable hacks to workaround this. For example using GCC, if all arguments of a function are "__builtin_constant_p(arg) == true", chances are that the function is being evaluated at compile-time. Obviously, this hack is neither reliable nor portable. 

Some people have particularly argued for "constexpr overloading" and other complicated features in the past [0, 1]. The main argument against those was that the committee preferred to improve constexpr so that faster run-time algorithms can be implemented without hacks, than offering a escape hatch. I don't see how this could ever work for somebody wanting to use inline assembly for the run-time implementation of a constexpr function, and hence argue that we do need a escape hatch.

I think that a standard library function, "constexpr bool std::is_context_being_constant_evaluated();", would be a simple addition to the language that solves all the needs to differentiate between run-time and compile-time code in constexpr functions. It does not have any of the complications of a new constexpr overloading mechanism. 

There is also prior art in the D language, where the __ctfe intrinsic is provided [3], and quoting its documentation, defined as:
> The __ctfe boolean pseudo-variable, which evaluates to true at compile time, but false at run time, can be used to provide an alternative execution path to avoid operations which are forbidden at compile time. Every usage of __ctfe is evaluated before code generation and therefore has no run-time cost, even if no optimizer is used.

[0] https://drive.google.com/file/d/0B0-xyi_NILkZeUxCWjdudW52UjQ/view

[1] https://groups.google.com/a/isocpp.org/forum/?fromgroups#!searchin/std-proposals/constexpr$20overloading/std-proposals/1MxiNSeJAj8/s4BXtHnA_pwJ

[3] http://dlang.org/spec/function.html

[Gonzalo BG]

In [0] Chandler Carruth discusses a different approach using attributes that is nicer:

// constexpr implementation
constexpr int foo_constexpr_impl();

// run-time implementation with fallback

// to the constexpr implementation in 

// constant-evaluated contexts
[[constexpr_alias(foo_constexpr_impl)]]
int foo();

I wonder what happened to this proposal. Gabriel Dos Reis argues there that we should focus on making constexpr better, but Richard Smith argued:

Yes, I completely agree, but I don't think this solves the whole 
problem {{referring to improving constexpr}}. There are certain constructs which we are unlikely to *ever*
permit in constexpr functions, such as (as an extreme case) inline
assembly. Where possible, we should share an implementation between
compile time and runtime. This proposal is for the exceptional cases
(which, over time, should become fewer and fewer), and as a stopgap
measure while we work towards the right solution.

[0] http://clang-developers.42468.n3.nabble.com/C-11-new-builtin-to-allow-constexpr-to-be-applied-to-performance-critical-functions-td4027593.html

[Mathias Gaunard]

I'd personally prefer to add constexpr as a qualifier on the parameters and overload based on that, that would be much more generic.

Good luck extending C++ to make that work though.

[Gonzalo BG]

> I'd personally prefer to add constexpr as a qualifier on the parameters and overload based on that, that would be much more generic.

Are constexpr functions required to be evaluated at compile-time if all parameters are constant expressions? I thought that they are only required to be evaluated at compile-time in constant expression contexts and potentially also in unevaluated contexts. 

Anyhow your preference is appealing, and could be a backwards compatible (and very complex) addition to either of the things being proposed.

However, note that while it might make some programs easier to write, it does not allow writing new programs, since it can be worked around with if constexpr +  `std::is_const_evaluated(arg)`.

[Nicol Bolas]

On Thursday, February 9, 2017 at 8:19:27 AM UTC-5, Gonzalo BG wrote:

AFAIK none of the major C++ compilers provide a way to detect whether a constexpr function is being evaluated at compile-time.

This is unfortunate. I have a constexpr function with bad run-time performance. Rewriting it to use SSE4.2 intrinsics improves its performance by 3.5x. Those intrinsics are not constexpr functions. I could imagine similar situations in which one would need to go down to inline assembly to deliver acceptable run-time performance in constexpr functions. Inline assembly cannot be neither standardized nor evaluated at compile-time. 

So I must choose: either constexpr (which my function already was) but horrible run-time performance, or run-time performance and breakage (because my function was already constexpr). This is an uncomfortable spot to be in. In particular, since constexpr functions are not limited to compile-time evaluation.

There are some unreliable hacks to workaround this. For example using GCC, if all arguments of a function are "__builtin_constant_p(arg) == true", chances are that the function is being evaluated at compile-time. Obviously, this hack is neither reliable nor portable. 

Some people have particularly argued for "constexpr overloading" and other complicated features in the past [0, 1]. The main argument against those was that the committee preferred to improve constexpr so that faster run-time algorithms can be implemented without hacks, than offering a escape hatch. I don't see how this could ever work for somebody wanting to use inline assembly for the run-time implementation of a constexpr function, and hence argue that we do need a escape hatch.

I think that a standard library function, "constexpr bool std::is_context_being_constant_evaluated();", would be a simple addition to the language that solves all the needs to differentiate between run-time and compile-time code in constexpr functions. It does not have any of the complications of a new constexpr overloading mechanism.

I think there's a much easier way: `if constexpr`.

As it currently stands, `if constexpr()` is a compile error, since there is no expression to evaluate. What if we make it so that `if constexpr()` means "if I'm in a constant expression evaluation". And thus, the `else` clause would be "if I'm not in a constant expression evaluation".

After all, 90% of the time you're going to call `is_context_being_constant_evaluated`, you're going to use it in an `if constexpr` statement. So let's just skip the middleman.

[Faisal Vali]

IMHO, if you have a valid use case that improves the performance of
your code (and resonates with "enough" domain experts) - yet is very
challenging (if not impossible) to implement in current C++, we should
at the very least strongly consider providing it as an extension in
clang (which I believe should not be hard to implement - i.e. codegen
ignores the true-branch, and Richard's expression evaluator ignores
the false-branch).

Whether the standardization committee will ever embrace it (following
a paper), is quite another matter (and might depend on the quality and
reputation of the code-bases that emerge around it) ...

Faisal Vali

> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/86a47916-27c3-4e29-862f-9b4e1f105c1c%40isocpp.org.

[Thiago Macieira]

On quinta-feira, 9 de fevereiro de 2017 09:24:09 PST Faisal Vali wrote:
> IMHO, if you have a valid use case that improves the performance of
> your code (and resonates with "enough" domain experts) - yet is very
> challenging (if not impossible) to implement in current C++, we should
> at the very least strongly consider providing it as an extension in
> clang (which I believe should not be hard to implement - i.e. codegen
> ignores the true-branch, and Richard's expression evaluator ignores
> the false-branch).

He's not the first to bring it up. I believe I have more than once prior to
this and the examples are all the same: trying to do something that isn't
constexpr but is faster at runtime. In 90% of the cases, it's either due to
inline assembly or compiler intrinsics that aren't constexpr. I have yet to
see clever, non-constexpr hacky code that doesn't involve either, but it's
possible.

We used to have this problem with Clang: for example, qCountTrailingZeroBits
wasn't constexpr with Clang until 3.8, because we couldn't use __builtin_ctz
in a constexpr context.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Thiago Macieira]

On quinta-feira, 9 de fevereiro de 2017 10:12:30 PST Thiago Macieira wrote:
> He's not the first to bring it up. I believe I have more than once prior to
> this and the examples are all the same: trying to do something that isn't
> constexpr but is faster at runtime. In 90% of the cases, it's either due to
> inline assembly or compiler intrinsics that aren't constexpr. I have yet to
> see clever, non-constexpr hacky code that doesn't involve either, but it's
> possible.

Here's an idea: anything related to type punning via memcpy.

Given enough __builtin constexpr floating point functions, you can implement
conversion to __fp16 (a.k.a. ushort) in constexpr fashion. But if you know
that you're under IEEE 754 / IEC 559, you could simply memcpy the float to
uint32_t (or double to uint64_t) and extract the bits that you need.

uint64_t v;
memcpy(&v, &val, sizeof(v));
int sign = v >> 63 << 15;
int exp = (v >> 52) & 0x7ff;
int mant = v << 12 >> 12 >> (53-11); /* keep only the 11 most
significant bits of the mantissa */
exp -= 1023;
if (exp == 1024) {
/* infinity or NaN */
exp = 16;
mant >>= 1;
} else if (exp >= 16) {
/* overflow, as largest number */
exp = 15;
mant = 1023;
} else if (exp >= -14) {
/* regular normal */
} else if (exp >= -24) {
/* subnormal */
mant |= 1024;
mant >>= -(exp + 14);
exp = -15;
} else {
/* underflow, make zero */
return 0;
}

/* safe cast here as bit operations above guarantee not to overflow */
return (unsigned short)(sign | ((exp + 15) << 10) | mant);

[rhalb...@gmail.com]

On Thursday, February 9, 2017 at 7:12:40 PM UTC+1, Thiago Macieira wrote:

We used to have this problem with Clang: for example, qCountTrailingZeroBits
wasn't constexpr with Clang until 3.8, because we couldn't use __builtin_ctz
in a constexpr context.

That is inaccurate: builtin bit-twiddling in constexpr contexts has been supported since Clang 3.4. 

int main()

{

    static_assert(__builtin_ctz(0x8) == 3, "");

}

http://melpon.org/wandbox/permlink/atER2z2uVzSPxzjA 

[Thiago Macieira]

On quinta-feira, 9 de fevereiro de 2017 11:29:26 PST rhalb...@gmail.com
wrote:

> That is inaccurate: builtin bit-twiddling in constexpr contexts has been
> supported since Clang 3.4.
>
> int main()
> {
> static_assert(__builtin_ctz(0x8) == 3, "");
> }
>
> http://melpon.org/wandbox/permlink/atER2z2uVzSPxzjA

Well, experience proves you wrong. This used to fail with Clang that came with
Xcode 6.4, which says:

Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)

So unless Apple broke something, then 3.5 didn't work.

(Testing with gcc.godbolt.org shows that it's actually Apple's fault)

[Rein Halbersma]

On Thu, Feb 9, 2017 at 9:04 PM, Thiago Macieira <thi...@macieira.org> wrote:

On quinta-feira, 9 de fevereiro de 2017 11:29:26 PST rhalb...@gmail.com
wrote:
> That is inaccurate: builtin bit-twiddling in constexpr contexts has been
> supported since Clang 3.4.
>
> int main()
> {
>     static_assert(__builtin_ctz(0x8) == 3, "");
> }
>
> http://melpon.org/wandbox/permlink/atER2z2uVzSPxzjA

Well, experience proves you wrong. This used to fail with Clang that came with
Xcode 6.4, which says:

Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)

So unless Apple broke something, then 3.5 didn't work.

(Testing with gcc.godbolt.org shows that it's actually Apple's fault

On Linux, this has been working for at least 3 years now, too bad if XCode didn't work out for you. 

[Thiago Macieira]

On quinta-feira, 9 de fevereiro de 2017 21:10:18 PST Rein Halbersma wrote:
> On Linux, this has been working for at least 3 years now, too bad if XCode
> didn't work out for you.

Xcode's Clang is the overwhelming majority of Clang users for Qt. Something
like a 1000:1 ratio of usage and I am guessing low.

Anyway, Apple stopped trying to claim that they follow any release. Since
Xcode 7, they no longer even show which SVN branch they released from. So we
simply now track the Xcode version, not the Clang version. In turn, that means
we almost never enable Clang features based on the upstream version anymore,
until we get a report from someone on FreeBSD two years down the line.

[Gonzalo BG]

Whether some version of clang did or did not support one particular intrinsic inside constexpr functions is kind of irrelevant.

Do you know how many SSE vector intrinsics and vector types are supported by the constant expression evaluators of clang, gcc, and msvc? None, don't need to even mention AVX or anything more modern, just plain old 1999's SSE.  

Even if it was somehow possible to support all these intrinsics (which I don't think will ever happen in practice), it is still impossible to support inline assembly (+ cross-compiling).

As a consequence, constexpr will never be a zero cost abstraction, because there will always be a set of programs for which it incurs an extra run-time cost.

I am not arguing whether "if constepxr() {...}" or [[constexpr_alias(..)]] are the best or only ways to solve the problem, but rather that this is a real problem and these could be some solutions. They are probably not perfect, so I'd really appreciate if we could focus into proposing either new solutions, or finding flaws in the proposed ones.

One potential peril of [[constexpr_alias]] could be that it might introduce a new way to create ODR issues.

A peril of "if constexpr()"-like solutions is that the compiler might want to evaluate a block of a non constexpr function at compile-time, in which case it could make sense to make "if constexpr()" also work in non-constexpr functions, and to return true if the current context/scope/block is being evaluated at compile-time, independently of whether the outer function is or isn't being evaluated at compile-time. 

[Nicol Bolas]

On Friday, February 10, 2017 at 7:35:38 AM UTC-5, Gonzalo BG wrote:

A peril of "if constexpr()"-like solutions is that the compiler might want to evaluate a block of a non constexpr function at compile-time, in which case it could make sense to make "if constexpr()" also work in non-constexpr functions, and to return true if the current context/scope/block is being evaluated at compile-time, independently of whether the outer function is or isn't being evaluated at compile-time.

I'm not sure what would keep `if constexpr()` from working under those circumstances. You would simply define it to work if the compiler chooses to execute the function at compile time.

[Thiago Macieira]

Em sexta-feira, 10 de fevereiro de 2017, às 04:35:38 PST, Gonzalo BG escreveu:
> Do you know how many SSE vector intrinsics and vector types are supported
> by the constant expression evaluators of clang, gcc, and msvc? None, don't
> need to even mention AVX or anything more modern, just plain old 1999's
> SSE.

Of course.

But in our experience, any algorithm that can be complex enough to warrant
SIMD optimisation is too complex for a constexpr inline function. We don't
have any example of that in Qt code. All the ones that would need to be
constexpr and have a faster runtime have been so far solved by compiler
intrinsics.

The closest thing that would come to what you're saying is calculating a
string's hash. But we specifically *don't* want to have that inline so that we
can change the algorithm later (right now, I'm considering changing the one we
have based on CRC32 to one based on AES).

[Gonzalo BG]

@Thiago:

> We used to have this problem with Clang: for example, qCountTrailingZeroBits  wasn't constexpr with Clang until 3.8, because we couldn't use __builtin_ctz  in a constexpr context. 

Given that you have run into the issue, I cannot find the logic in the following statement:

> But in our experience, any algorithm that can be complex enough to warrant SIMD optimisation is too complex for a constexpr inline function.

You seem to be arguing that using __builtin_ctz in a constexpr function is reasonable, but using any other intrinsics while solving problems in any other domain is not. Care to elaborate on which experience makes you say so?

I am not a Qt user, but at least outside from Qt it is easy to find examples of algorithms that are useful in constexpr functions, but for which one always wants to use intrinsics/SIMD at run-time:

1) The post C++11 standard library. Before C++11 I rarely saw people reimplementing pow, log, exp, sin, ... After C++11 almost every single project had its own pow constexpr implementation because neither the math functions from the standard library nor the builtins provided by the compilers worked inside constant expressions for years after C++11. The run-time performance of these functions was, and still is, horrible. The fix for this was to make the math functions in the standard constexpr, but this did not solve the underlying issue (which is being discussed here).

2) Math/Linear algebra libraries like Eigen3, Blaze, ... which have used expression template hacks for compile-time computations for the last 20 years _cannot_ use constexpr anywhere in their API (and don't really use it almost anywhere) because somewhere down the pipeline they do use intrinsics (and pragmas and what not) for run-time performance reasons.

Do you consider using a log function (which is implemented using intrinsics in most standard libraries) or multiplying two 4x4 matrices "too complex" for constexpr functions?

@Nicol Bolas:

> I'm not sure what would keep `if constexpr()` from working under those circumstances. You would simply define it to work if the compiler chooses to execute the function at compile time

I am quoting Eric from this issue which mentions ODR violations as a potential issue: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79452

>There are definitely opportunities for ODR violations here, or at least

>something like them. Consider the following case:
>
>template <class T>
>constexpr bool foo(T) {
>  if constexpr(__ctfe__)
>    return true;
>  else
>    return false
>}
>
>static_assert(foo(0));
>auto runtime = foo(0);
>
>Both calls instantiate foo with the same template arguments, so they should
>seemingly both get the same instantiation with the w/e value of `__ctfe__` was
>when the implicit instantiations occurred. Therefore one of the two calls to
>foo() will return the wrong answer.
>
>This problem is made ever worse if `__builtin_constant_expression` allows you
>to generate non-dependent compile-time expressions based on the function
>arguments.
>
>One solution would be to consider the instantiation of `foo` to be value
>dependent on a "implicit template parameter" representing `__ctfe__`.

[Thiago Macieira]

On sábado, 11 de fevereiro de 2017 10:43:53 PST Gonzalo BG wrote:
> @Thiago:
> > We used to have this problem with Clang: for example,
> > qCountTrailingZeroBits wasn't constexpr with Clang until 3.8, because we
> > couldn't use __builtin_ctz in a constexpr context.
>
> Given that you have run into the issue, I cannot find the logic in the
>
> following statement:
> > But in our experience, any algorithm that can be complex enough to
> > warrant SIMD optimisation is too complex for a constexpr inline function.
>
> You seem to be arguing that using __builtin_ctz in a constexpr function is
> reasonable, but using any other intrinsics while solving problems in any
> other domain is not. Care to elaborate on which experience makes you say so?

It was a problem, but it's now fixed and we now can use the builtin that is
constexpr.

> 1) The post C++11 standard library. Before C++11 I rarely saw people
> reimplementing pow, log, exp, sin, ... After C++11 almost every single
> project had its own pow constexpr implementation because neither the math
> functions from the standard library nor the builtins provided by the
> compilers worked inside constant expressions for years after C++11. The
> run-time performance of these functions was, and still is, horrible. The
> fix for this was to make the math functions in the standard constexpr, but
> this did not solve the underlying issue (which is being discussed here).

That's an interesting example, but it doesn't match my experience. I haven't
seen a lot of people need exponentiation and logarithm in constexpr constexts.
In regular code, you simply rely on the optimiser propagating constants,
something compilers have done for a decade.

> 2) Math/Linear algebra libraries like Eigen3, Blaze, ... which have used
> expression template hacks for compile-time computations for the last 20
> years _cannot_ use constexpr anywhere in their API (and don't really use it
> almost anywhere) because somewhere down the pipeline they do use intrinsics
> (and pragmas and what not) for run-time performance reasons.

Same as above: I've never seen the need for those operations to appear in a
constexpr context in the first place. It is as I said: the majority of the
operations that benefit from non-constexpr'able code is too complex for
constexpr anyway.

> Do you consider using a log function (which is implemented using intrinsics
> in most standard libraries) or multiplying two 4x4 matrices "too complex"
> for constexpr functions?

Yes, in my experience.

Or, put another way, what use-case warrants storing the result of such an
operation in a constexpr variable? This is a real question, you probably know
more cases than I do.

[Joel Falcou]

Eigen and other expression tempaltes library don't perform computation at compile time, they build a lazy representation of computations at compile time so the actual computations are delayed.

I wrote a couple of such library and the only places where constexpr made sense was optimizing matrix size computation when all dimensions where constants.

log2 happens a bit in constexpr context becasue finding the closest power of 2 is a task some code may requires. I had myself solved a 2x2 linear system but not much more at compile time.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.

To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.

To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/18849693.bqFcfaDNcV%40tjmaciei-mobl1.

[inkwizyt...@gmail.com]

a) All function need have `inline` to be able use `constexpr`
b) At some point you know if you call in `constexpr` context or not.

Probably best solution for today is manual overloading:

int k = 6;

template<bool is_constexpr>
constexpr int bar(int i, int j)
{
  return 42 * j + i;
}

template<>
int bar<false>(int i, int j)
{
  return k * j + i;
}

template<bool is_constexpr>
constexpr int foo(int i, int j)
{
  return bar<is_constexpr>(i + j, j);
}

template<int i>
struct S
{
  int f() { return i; }
}

int main()
{
  int a = 5;
  S<foo<true>(1, 2)> b(4, 4);
  return foo<false>(a, b.f());
}

[Matthew Woehlke]

(No TOFU¹ please!!)

On 2017-02-09 10:24, Faisal Vali wrote:

> On Thu, Feb 9, 2017 at 7:19 AM, Gonzalo BG wrote:
>> AFAIK none of the major C++ compilers provide a way to detect whether a
>> constexpr function is being evaluated at compile-time.
>

> Whether the standardization committee will ever embrace it (following
> a paper), is quite another matter

Fortunately, it seems Daveed has already written that paper:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0595r0.html

(¹ https://en.wikipedia.org/wiki/Posting_style#Top-posting)

--
Matthew

[Faisal Vali]

On Thu, Feb 16, 2017 at 1:53 PM, Matthew Woehlke
<mwoehlk...@gmail.com> wrote:
> (No TOFU¹ please!!)

sorry (happens occasionally when i'm in a rush :( )

>
> On 2017-02-09 10:24, Faisal Vali wrote:
>> On Thu, Feb 9, 2017 at 7:19 AM, Gonzalo BG wrote:
>>> AFAIK none of the major C++ compilers provide a way to detect whether a
>>> constexpr function is being evaluated at compile-time.
>>
>> Whether the standardization committee will ever embrace it (following
>> a paper), is quite another matter
>
> Fortunately, it seems Daveed has already written that paper:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0595r0.html

That's awesome - and reason for much optimism!

>
> (¹ https://en.wikipedia.org/wiki/Posting_style#Top-posting)
>
> --
> Matthew
>

> --
> You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.

> To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/58A6032C.9020001%40gmail.com.