[std-proposals] A call to discuss asm in constexpr and constexpr <algorithm>

[Antony Polukhin]

Hello,

The Problem

The Standard Library provides a great collection of algorithms, many of which currently lack constexpr support. Consider the simple example:

#include <array>
#include <algorithm>
 
int main() {
    // OK
    constexpr std::array<char, 6> a { 'H', 'e', 'l', 'l', 'o' };
    // Note: std::array::begin(), std::array::end() are constexpr in P0031R0
    // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0031r0.html

    // Failures:
    // * std::find is not constexpr
    constexpr auto it = std::find(a.begin(), a.end(), 'H');
}

Main problem with functions from <algorithm> is that they could be optimized using assembly. Currently constexpr can not deal with inline assembly.

Let's discuss and share ideas on how to improve the situation.



Ideas
Here are the ideas I've been investigating. Impatient ones could jump right to the 'Refinement' to see the idea I've stopped on.
-----------------------------------------------
IDEA #1
Create a trait that signals usage of function inside constexpr context: `__is_constexpr_context` that returns true_type or false_type

EXAMPLE in pseudocode:

template <class It, class Value>
constexpr It find_impl(It begin, It end, const Value& v, true_type /*constexpr*/);

template <class It, class Value>
It find_impl(It begin, It end, const Value& v, false_type /*constexpr*/);

template <class It, class Value>
constexpr It find(It begin, It end, const Value& v) {
    return find_impl(begin, end, v, __is_constexpr_context{});
}

DRAWBACKS:
* Breaks ODR (This is probably one of the worst ideas ever)
* Potentially forces user to write two different implementations of function

-----------------------------------------------
IDEA #2
Allow overloads by constexpr.

EXAMPLE in pseudocode:

template <class It, class Value>
It find(It begin, It end, const Value& v);

template <class It, class Value>
constexpr It find(It begin, It end, const Value& v);

DRAWBACKS:
* forces user to write two different implementations of function
* C++ already has a lot of overload rules, adding new ones does not seem to be a good idea. For example which overload to choose is not obvious in following case:
template <class T> constexpr void foo(const T& );
void foo(int );

-----------------------------------------------
IDEA #3
Relax restrictions on constexpr, allow usage of assembly and goto in constexpr functions.

DRAWBACKS:
* Providing such ability for cross-compilaton would be a huge amount of work for the compiler developers. Compiler developers would be forced to know how to evaluate assembly for a foreign platform. For example cross compiling on x86 for ARM will require the compiler to evaluate ARM assembly on x86.

-----------------------------------------------
IDEA #4
Mark the required function with constexpr and force the Standard Library developers and compiler developers to implement more compiler intrinsics.

EXAMPLE in pseudocode:

template <class It, class Value>
constexpr It find(It begin, It end, const Value& v) {
    return __builtin_find(begin, end, v);
}

DRAWBACKS:
* This will make the Standard Libraries less portable across compilers (every compiler vendor has it's own naming schemes for intrinsics).
* This solution is also not usable by user (user would not be able to create it's own assembly optimized constexpr function, because he has no access to the compiler internals).

-----------------------------------------------
IDEA #5
Add an additional keyword, signaling that in a constexpr context only this overload must be used.

EXAMPLE in pseudocode:

template <class T>
constexpr_only // <---- new keyword
    int foo(const T& ); // overlaod #1

int foo(int );  // overlaod #2
constexpr int foo(float );  // overlaod #3

int main() {
    constexpr int i0 = foo(1); // will call overlaod #1
    constexpr int i1 = foo(1.0); // will call overlaod #1
    constexpr int i2 = foo(1.0f); // will call overlaod #3

    int i3 = foo(1LL); // will call overlaod #2
    int i4 = foo(1.0f); // will call overlaod #3
}

DRAWBACKS:
* New keyword is not good.
* This idea also affects the overload rules and make them even more confusing.
* Potentially forces user to write two different implementations of function
-----------------------------------------------


Refinement
I've stopped on idea #3. In attempt to simplify the compiler developers work, I've applied additional restrictions to inline assembly.
I took additional care to not mention the asm in [expr.const], because asm definition is implementation-defined (see [dcl.asm]).

The impact on the C++ Standard is following:

In [dcl.constexpr] remove the following requirements on constexpr function body:
    — an asm-definition,
    — a goto statement,

In [expr.const] add the following to the list of the "would evaluate one of the following expressions:"

— a call to priviledged instruction, long jump instruction, software interruption or any other instruction that
 produces results depending not only on input arguments [ Example: x86 instructions CPUID, RDRAND, RDSEED — end example ].

-----------------------------------------------

Any suggestions or improvements are welcomed!


--

Best regards,
Antony Polukhin

[Andrew Tomazos]

I was working on this earlier in the year.  Current design is:

    constexpr R f(P1, P2, P3) {

       ... constexpr version ...

    } else {

       ... non-constexpr version ...

    }

Enjoy,

Andrew.

--

---
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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Richard Smith]

This seems like the best approach. Note that the intrinsics need not be as broad and complex as the one you specify below. Instead, I imagine this would look more like:

template <class It, class Value>
constexpr It find(It begin, It end, const Value& v) {
    return __builtin_find(begin, end, v);
}

constexpr char *find(char *begin, char *end, const char& v) {

    void *p = memchr(begin, v, end - begin);
    return p ? begin + __builtin_ptrdiff(p, begin) : end;
}

--

[rhalb...@gmail.com]

Clang currently allows bit-twiddling intrinsics (__builtin_popcount and friends) in constant experssions. Is this a non-standard extension, or don't these intrinsics use bit-twiddling asm under the hood?

[Richard Smith]

On Wed, Nov 18, 2015 at 2:34 PM, <rhalb...@gmail.com> wrote:

Clang currently allows bit-twiddling intrinsics (__builtin_popcount and friends) in constant experssions. Is this a non-standard extension, or don't these intrinsics use bit-twiddling asm under the hood?

I don't understand the question. This is obviously a non-standard extension; the standard has no __builtin_* functions. Under the hood, there are usually two completely separate implementations of these for the case when they're encountered during constant expression evaluation and the case when code is generated for them.

[Antony Polukhin]

2015-11-18 23:39 GMT+03:00 Andrew Tomazos <andrew...@gmail.com>:

I was working on this earlier in the year.  Current design is:

    constexpr R f(P1, P2, P3) {

       ... constexpr version ...

    } else {

       ... non-constexpr version ...

    }

I think that approach was carefully avoided by the Standard Committee in previous years, because it leads to reimplementation of the same function in different ways which potentially leads to creation of hard detectable errors.

[Antony Polukhin]

2015-11-19 1:28 GMT+03:00 Richard Smith <ric...@metafoo.co.uk>:

This seems like the best approach. Note that the intrinsics need not be as broad and complex as the one you specify below. Instead, I imagine this would look more like:

template <class It, class Value>
constexpr It find(It begin, It end, const Value& v) {
    return __builtin_find(begin, end, v);
}

constexpr char *find(char *begin, char *end, const char& v) {

    void *p = memchr(begin, v, end - begin);
    return p ? begin + __builtin_ptrdiff(p, begin) : end;
} 

This actually gave me an idea to split proposal into two parts:
* algorithm only related proposal, that could be implemented by vendors using intrinsics (if required)
* proposal to allow asm in constexpr. This would untie hands for algorithms implementation without intrinsics

For the curious, here's some draft version of the first proposal: http://apolukhin.github.io/constexpr_algorithms/

[inkwizyt...@gmail.com]

I think that is impossible to support asm in constexpr. Consider this, I have x86 machine compiling for Arm. What CPU should be supported in constexpr function in that case?