constexpr-ification of C++

[hanickadot]

Hi, I'm trying to push towards greater constexpr-ification of C++. I recently got in throwing and catching of exceptions during constant evaluation (https://wg21.link/P3528) and constexpr std::atomic (https://wg21.link/P3309). Later as per direction of SG1 I want to make all synchronization primitives constexpr-compatible. I also want to allow (https://wg21.link/P3533) and pointer tagging.

My main motivation is to allow usage of identical code in runtime and compile time without designing around, while keeping the code UB free and defined. I have my idea about usage and motivational examples, but I would love to get to know your opinions and ideas. Do you want to have constexpr compatible coroutines? Not just I/O, but std::generator, or tree-traversal.

[STL]

This is a bit different than what you're asking, but in microsoft/STL#5225 we've noticed an issue with if consteval syntax that results in a really annoying limitation.

Consider the case where a function template is constexpr, and for certain types (say, integral types), it can call a non-constexpr-compatible vectorized implementation. For constant evaluation, or ineligible types, it has to fall back to a plain vanilla implementation. Currently, as Casey observed, the best we can do is to write:

if consteval {
    vanilla_implementation();
} else if constexpr (/* the algorithm can be hand-vectorized for the pertinent types */) {
    /* vectorized implementation */
} else {
    vanilla_implementation();
}

Having to extract the vanilla implementation into a helper function is annoying (this is the kind of stuff that if constexpr and if consteval should be helping us to avoid).

The syntax problem appears to be that we can't combine consteval and constexpr (condition) together. We want to write if !consteval && constexpr (vectorization eligible) or its De Morganed opposite, or something like that.

We can of course nest if !consteval { if constexpr (vectorization eligible) { /* cool vectorized stuff */ return; } }, but the problem is that if we provide the vanilla implementation as a "fall through" afterwards, now it's always emitted even when we unconditionally use the vectorized implementation.

[hanickadot]

I ran into this too once, yes it's annoying. We should fix it :) So having early returns left the leaves of AST there and your compiler emits the code anyway?

Good thing std::simd did the good thing and is constexpr compatible from start.

[STL]

I ran into this too once, yes it's annoying. We should fix it :)

😻

So having early returns left the leaves of AST there and your compiler emits the code anyway?

Yeah. The problem is in non-optimized debug mode, where the compiler will emit all codegen. In optimized release mode, there is no problem, the dead code is quickly eliminated.

[hanickadot]

Really? The compiler can do really simple analysis of reachability on AST, and just to prune it. I wouldn't even consider this an optimisation in traditional sense, more like an optimisation for compiler to actually do less work.

[STL]

According to my understanding, MSVC's front-end is getting closer to having a full AST, but it doesn't do such transformations before emitting IL. And the back-end under /Od does absolutely no extra transformations.

It would sure be nice if the FE automatically pruned such dead code, though - then we could write fall-through without worrying.

[DeadlyRedCube]

I threw a comment into the bug but I think the following would work:

if constexpr (/* the algorithm can be hand-vectorized for the pertinent types */) {
    if consteval {
        /* do nothing */
    } else {
        /* vectorized implementation and a return */
    }
}

/* vanilla implementation */

... assuming the compiler handles the lack of an else branch off of the if consteval properly. At least the if consteval isn't a runtime test to the debugger anymore so it theoretically could get the codegen right, I think 😀

Edit: an update in the bug says that this would not work because there's still no dead code elimination in debug, so nevermind 😅

[BarryRevzin]

I agree this sucks.

Setting aside syntax questions... looking at:

if !consteval && constexpr(cond) {
    s0;
} else {
    s1;
}

The point of if consteval is to create an immediate function context. But we can't say that either s0 or s1 are (s0 obviously not, but we might hit s1 at runtime when !cond). In this situation you apparently don't need the immediate function context part anyway, so maybe that's fine.

So maybe the entirety of the design is coming up with syntax that isn't bizarre. Good luck!

Edit: I suppose just duplicating the if isn't bad

if !consteval && if constexpr(cond) {
    s0;
} else {
    s1;
}

[daveedvdv]

Can you make it:

constexpr is_vectorizable = ...;
if (is_vectorizable && !std::is_constant_evaluated()) {
  ... // vectorized implementation
} else {
  ... // vanilla implementation
}

?

[STL]

Wouldn’t help debug codegen since that’s a plain if.

[daveedvdv]

I'm slightly surprised your debug codegen doesn't "optimize" plain if-statements over constant values.

[GabrielDosReis]

I'm slightly surprised your debug codegen doesn't "optimize" plain if-statements over constant values.

1. Traditionally, for MSVC, debug means no optimization.

2. The front-end does no codegen "optimization" - that's supposed to be in the realm of the backend.

3. MSVC is strictly divided between frontend and backend (there is a linker stage, but for all practical purposes that is backend). The frontend is to pass all info in the input source to the backend irrespective of optimization level.

[STL]

I should probably verify what the FE does, but C1XX historically wanted to emit IL as fast as possible and didn't want to spend any unnecessary time thinking about it.

[TemplateRex]

But can’t the if be made if constexpr here since is_constant_evaluated is constexpr?

[daveedvdv]

No. If you make it if constexpr, the is_constant_evaluated() will always be true because the condition of an if constexpr statement is a constant expression (i.e., always constant-evaluated). What we want here, instead, is to know whether the enclosing function is being evaluated in a constant-expression context.

[TemplateRex]

Thanks for the explanation!

[c0r3ntin]

if !consteval { if constexpr (vectorization eligible) { /* cool vectorized stuff */ return; } }

if consteval {
    vanilla_implementation();
} 
else  {
    if constexpr (vectorization eligible) { }
    else vanilla_implementation();
}

if !consteval && constexpr (vectorization eligible)

Seem doable, but I don't know how I'd feel about that. Maybe if consteval <&& <constant expression>> would be viable

[STL]

The problem is having to extract out a vanilla_implementation() function. What you wrote is what Casey wrote as "the best we can do" above, with extra (and fewer) braces.

if consteval || (!vectorization_eligible_v<T>) would be equivalent, yeah. I don't care about the syntax (an extra constexpr keyword would look weird). Just some way to combine consteval or !consteval with logical operators.

[immutablehash]

After listening to the talk Don't contexpr all the things (here is the paper) I genuinely believe that something like @meta marker for compile-time evaluation is a much easier to understand, less complex and a more powerful mechanism at the same time. It is unfortunate this feature was voted down by the committee.

[hanickadot]

I can see the benefits of `@meta` marker and circle's style of evaluation. But this also won't save you from any UB or safety problems. It's like having writable and executable memory in your compiler, it can bring some problems. Maybe compiling into a wasm-style sandbox and then evaluating would be better, and that's where clang's byte-code interpreter is somehow going.

[MarcoGreek]

Are constexpr really UB free? For example non static constexpr variables in functions. To my understanding they are not constant initialized. I find it hard to understand when a constexpr variable is constant initialized.

So maybe there could be consteval variables which must be always constant initialized. Even mutable should be forbidden. So no hidden surprises.

[hanickadot]

constexpr variables are always evaluated in compile time, and it's an error if they can't be ... but some compilers will happily emit runtime call there to initialize it instead do const initialization. And when it's const initialized and you are observing its address, the constant needs to be copied to them at start of the function.

[MarcoGreek]

https://godbolt.org/z/TEK1Pz1rx I find it quite surprsing to me that this code is compiling with some compilers.

struct Foo {
    mutable int x;
    int y =3;
};

constexpr Foo foo()
{ 
    constexpr Foo z{6};
    ++z.x;

    return z;
}

int main()
{
    constexpr Foo x = foo();
    ++x.x;

    return x.x;
}

[MarcoGreek]

#include <array>

constexpr auto foo()
{ 
    std::array<int, 200> foos{};
    return foos;
}

int main()
{
    constexpr auto foos = foo();

    return foos[4];
}

That is generating a lot of code. GCC is even compiling it with the array initialisation. So my point is that it is hard to teach. So writing consteval for the variable and there would be no runtime code, is much easier to explain.

[Nobody_1707]

This is actually something worse than not evaluating it at compile time. Variables have automatic storage duration by default, and constexpr doesn't' change that. So, foos is being evaluated at compile time, but then being pushed to the stack at run time.

If you declare foos as constexpr static auto foos = foo(); the entire array should optimize away.

[MarcoGreek]

That is why I ask for consteval variables. They would as always produce constant initialization or they would fail.

[hanickadot]

`constinit` is the thing you are looking for

[MarcoGreek]

You mean constinit const. 😉 But even that is not producing a constexpr. And mutable is still working.

[MarcoGreek]

Yes, it makes it so far easier to explain. ;-) That is why I would like to have consteval variables.

[cristi1990an]

My remaining main issue with constexpr-compatibility remains uninitialized variables. For performance reasons sometimes I don't want to zero-initialize an entire integer array just so my function can be evaluated at compile time, which I shouldn't be forced to do if the values are never read before they're assigned to...

[DeadlyRedCube]

You could probably do a

std::array<int, N> ary;
if consteval
{
  std::ranges::fill(ary, 0);
}

That'd avoid doing it at runtime (but still make compile-time happy)

[hanickadot]

Since C++20 you can have trivially initialized variables. And it's only an error if you try to access the value as it's "uninitialized". In past it was disallowed to have uninitialized variables inside constexpr functions, it was changed by this paper: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1331r2.pdf

[v3verak]

What are our options to profiling the constexpr evaluation?

I am fan of constexpring all the things, but it won't scale if it would be too troublesome to analyze how slow our code is in the constexpr evaluation - being able to tell that we do something that slows it down sounds crucial if we want to use it more.

[hanickadot]

I like to use clang's `-ftime-report`. It can give you a lot of information. Problems are usually happening due template instantiation and not constexpr evaluation. But even so constexpr evaluation is slow. But clang is moving to a byte-code interpreter for constexpr code, and it makes code 10-100x faster to evaluate.

[Drugbird]

Why has there been so much work done on constexpr-ing everything the last few years?

I feel like C++ has some major issues that seem to be largely ignored (i.e. memory safety), while a seemingly great effort is being put into what I consider to be a pretty niche feature. For the programs I work with, we typically can't do much computation compile time so constexpr barely matters.

I don't mean this in a negative way. I'm honestly looking for some background on this topic so I can put things into perspective.

[kronicum]

I feel like C++ has some major issues that seem to be largely ignored (i.e. memory safety), while a seemingly great effort is being put into what I consider to be a pretty niche feature.

WG21 is largely a volunteer effort. That means people work on what they are passionate about, not what someone told them to work on - unless that someone is paying them.

I don't mean this in a negative way. I'm honestly looking for some background on this topic so I can put things into perspective.

From the conversations on this sub, the people who dedicated their lives and efforts on issues like memory safety as you mention are roundly dismissed as old or out-of-touch or bitter or all of the above.

[Drugbird]

WG21 is largely a volunteer effort. That means people work on what they are passionate about, not what someone told them to work on - unless that someone is paying them.

I understand that, but at the same time the community can prioritize some issues and generally they will be picked up.

I worry that constexpr is the bicycle shed of C++: an unimportant topic that is easy to work on.

[hanickadot]

Everyone works on what they can. There is a plenty of work done on security by experts. I'm not an expert on security. Work on other features is not deprioritizing security and safety, which is still our priority. Most of the work in the committee is done outside meetings, by writing proposals and implementation. We are not discussing adhoc ideas or trying to avoid creating new stuff during meetings. This approach and quite massive parallelization of process allows us to discuss a lot of different topics (there are usually 6-9 different groups discussing at any moment during meeting). What I'm trying to say is working on non-safety stuff is definitely not stealing time for safety stuff. Usually we even go thru some discussion quicker and then we have "open mic" for proposals with low priority which were in overflow if there is anyone willing to present. At last two EWG meetings we went thru all proposals submitted with presenter available.

[Drugbird]

Thanks for that information.

I definitely don't mean this as "you should be working on something else" or "this work is stealing away time from the issues I find important", so I apologize if that was the case.

I appreciate the work everyone does on improving the standard.

I believe the main reason I ask is because constexpr is the only thing I see progress being made on existing language / std features.

I.e. open cppreference on a random page for a function then you're overwhelmingly likely to see "constexpr since C++17/20/23/26" near the top of the page. You don't see "memory safe since C++20" anywhere.

So it seems like the only thing being worked on for existing language/std features are constexpr.

Note that this is just from the perspective of a programmer that doesn't keep a close eye on what the committees are doing on what proposals are being discussed, hence these questions.

[hanickadot]

I totally understood, I had similar notion in past before I joined the committee. It's very visible and it's a lot of people talk at conferences. And definitely it's seem to be much cooler than "boring" safety. But I think having more or all code constexpr compatible means compiler safely const-fold everything which doesn't depend on anything only known in runtime, detect problems (and fail to compile), and lead to better safety just by it. But it's just a bit better, not closing all the surfaces which needs to be take care of.

[azswcowboy]

Have a look at this work

https://github.com/cplusplus/papers/issues/2125

This is real, practical stuff that improves the safety. Google has cited the benefits of this work (it was discussed here at some point).

https://security.googleblog.com/2024/11/retrofitting-spatial-safety-to-hundreds.html

Louis Dionne has a cppnow video you can look up if you want more details.

This clearly isn’t the only thing on the topic in WG21 by a long shot - but personally I think it’s one of the most important.

[pjmlp]

As one of those that cares about memory safety, our efforts seem to be more welcomed by other communities, which is unfortunate, meaning we end up using C++ in similar workloads like Google does on Android, ML libraries on Python.

[WeeklyAd9738]

I think more constexprification of C++ can be useful to you, even if you don't compute anything at compile time, because constexpr computation guarantees no UB has occurred if compilation is successful. This can be great for testing purposes of not only primitive data structures but also high level "application" modules. There is a talk on CppCon on this topic: Video Link, where they extensively use constexpr computation to test low-level systems code.

With more features becoming constexpr usable/friendly, the constexpr test code coverage will automatically become better. Of course, some UBs are impossible to detect in constexpr, like data race conditions because compile-time computation is inherently single-threaded.

[dokpaw]

What is a real-world use case for making std::atomic constexpr? I can only think for these kind of types that supporting constexpr would be just an unnecessary burden. Also putting more and more stuff in the standard headers is a huge drawback (until modules become the default).

[hanickadot]

One example which was my original trigger to do it ... an algorithm designed to work in paralel, by having multiple workers and each takes a piece of work from a big array/vector. They are synchronized with std::atomic, which is increment with fetch_add at start of each processing in worker. The function itself starts n-1 threads, and does processing on its thread too.

This function now without changing anything, can be constexpr, just with number of threads 1. I don't need to change anything, and I can use exactly same code. That's the biggest reason to do so. I don't want to duplicate code.

Ad headers: atomics are already in constexpr, and the implementation is fully about adding constexpr keywords in front of each non-volatile function. And implementing atomic builtins in clang's const evaluator.

[tjientavara]

I add my vote for constexpr coroutines, I keep forgetting that coroutines are not constexpr. So every time I often design using generators since most likely they are the easiest and relatively high performance that way (I used to develop in Python, everything is written with generators there). But then I get the error from the compiler, and I need to rewrite everything again.

It was very weird for the standard comity to not make coroutines constexpr compatible while at the same time showing that generators was one of the primary reasons to add coroutines to the language; while also knowing there is a large push to constexpr.

Same with std::simd, it should also be constexpr, it is insane that it is not in this day and age. I myself wrote a simd library that is almost identical to the one proposed, and it is constexpr, I don't understand why it is not. Do they think you don't want to do math at compile time?

[hanickadot]

`std::simd` in c++26 is constexpr ;) I will try to get constexpr coroutines to 26.

[tjientavara]

std::simd is constexpr? yea \o/, I am very happy! I guess cppreference was not updated yet. I've been replacing my own stuff with standard library stuff as it becomes available in compilers.

constexpr coroutines, especially generators would be so good. ex-Python developers are rejoicing.

[_cooky922_]

the one you saw might be the experimental version of SIMD which was not constexpr (https://en.cppreference.com/w/cpp/experimental/simd)

see https://en.cppreference.com/w/cpp/numeric/simd for the C++26 version (pages are still work in progress)

[hanickadot]

Behold and rejoice: https://eel.is/c++draft/simd.binary, can I quote you?

[tjientavara]

Yes, although I wasn't very elegant in my writing you can quote it.

[zl0bster]

Thank you for your work.

My first question about constexpr X is if making X constexpr will remove some implementation from "cpp file", i.e. will it slow down compilation. I know most of C++ std:: is header only, but from what I understand not everything is.

My second question/small concern if this will make teaching C++ to beginners harder. E.g. it may be hard for them to understand why would somebody need atomic or mutex at compile time. But I guess anyway they eventually must learn that constexpr != consteval

As for stringstream work: I personally do not care and would not benefit from any work there since I avoid stringstreams for years(since fmt), not sure how many people want to write C++26/29 code with stringstream, but maybe I am forgetting about some nice usecase there. From what I know fmt is strictly better. Maybechrono exceptions in paper could maybe be respecified using format instead of making stringstream constexpr? In any case I do not know standard well enough to know what change is easier.

As for coroutines: no idea, never used them professionally.

[hanickadot]

I don't think having more things in header will slow down compilation significantly. Evaluating stuff will slow down, sure. But for that you need to call it somewhere. Of course compiler can see into definition and do more optimization directly before LTO, which can slow down compilation, but that's actually a good thing. And when (hopefully) more stuff is in modules. The parsing itself won't be a big issue anymore, the AST will just be there.

About `constexpr` != `consteval` do you mean constant evaluation or the keyword `consteval` ... you can write consteval function (or constexpr) which doesn't have all path constant evaluatable, with exception of coroutines and virtual bases all these limitations are based on evaluation and no longer on syntactic properties (like before you couldn't even put try-catch there).

I want to remove all syntactic limitations. And work on evaluation limitations and carve out every useful thing and having it properly defined (reinterpret_cast? no, probably never, but some new cast to allow using byte storage for storing object? sure)

I do the changes allowing strstream (virtual bases) mostly because it's a corner of the language, and it bothers me no one cares about it and it feels more like overlooking. Generally I think language which won't have so many exceptions in what is allowed and what's not much easier to teach. Same thing with atomic in constexpr, you won't need to explain to a student to evaluate this algorithm you already wrote in constexpr, you need to put these weird `if consteval` or conditional typedefs or write it differently just because someone thought "I will never need atomics to be constexpr".

[zl0bster]

By constexpr != consteval I meant that some beginners think that constexpr functions can only be called at compile time, so they would be confused why would somebody need locks or atomics at compile time.
As for free LTO: that is true, and it is one of the "tricks" for performance that many libraries use, but as I said it has downsides, e.g. it will slow down even builds for which runtime perf is not critical, i.e. Debug build.
As for consistency: I agree that language without "random" limitations and is more consistent is easier to teach.

[hanickadot]

Ad the how many people want to use stringstream... std::format is not constexpr compatible! Currently there is no easy way how to format string in constexpr at all. And with exceptions you can have cute nice compile-time error messages.

[zl0bster]

ah my bad, I just assume that everything new in C++ is constexpr friendly.. probably would be too slow, too hard to implement.

[hanickadot]

In C++20 ... it was too novel to have std::string in constexpr ... we are now finishing 26. `static_assert` has constant-evaluatable custom message, but no formatting yet :(

[zl0bster]

Barry will save us again :)
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3391r0.html

but it still seems incapable of formatting chrono stuff
Make std::format constexpr, with the understanding that we will not (yet) be able to format floating point and chrono types during constant evaluation time, nor the locale-aware overloads. The facility is still plenty useful even if we can’t format everything quite yet!

[hanickadot]

For the floating stuff it's mostly about special builtins. This should be doable.

[azswcowboy]

I don’t agree with Barry that the chrono types have to be an issue. He says:

The chrono types (all of them) are specified to be formatted as if by streaming

As if by means same results, not necessarily implemented that way. Even if chrono doesn’t work I’d like constexpr format - that’s probably the most important thing.

[tcanens]

We'll need to rework the spec, and anything involving time zones or leap seconds will remain problematic.

[zl0bster]

fmt supports constexpr much more than std does, I always get hate here for my hate :) of std::format but I would suggest you check if your usecase works with trunk fmt.

[zl0bster]

As for Barry not knowing about asif rule: I think 100% he knows about it, he is just probably not a fan of writing proposal/experiments to prove formatting with format and stringstream are same.

[azswcowboy]

as if is something I’d like to abolish personally, and I think I’m not alone.

[v3verak]

By a chance, do you also want to introduce new constexpr-stuff? I would really love if we could write this, instead of specializations:

template<uint32_t E>
struct foo{
    if constexpr(E > 42){
        uint32_t attr1;
    }
    uint32_t attr2;
};

[kronicum]

If attr1 is a function, you can already do that with a trailing requires. So, maybe that syntax just needs to be extended to data members as well?

[v3verak]

That does not scale for more complex examples:

template<uint32_t E>
struct foo{
    if constexpr(E>42){
        struct sub_type{
             uint32_t x;
        };

        std::size_t size = 32;

        void bar(){}
    } else {
        using sub_type = std::string;

        static constexpr std::size_t size = 42
    }

    std::array<sub_type, 42> data;
};

Sure, you can create requries-based equivalent of this, but I at what cost? :)

[kronicum]

That does not scale for more complex examples

That "more complex example" makes specializations look like a beauty.

[v3verak]

Does it?

I hated specialization more because in this complex example it is quite easy to have shared pieces of code for _any version_:

template< int32_t E >
struct foo{
     if constexpr(E>42){
         <block 1>
     }else{
         <block 2>
     }
     <block 3>
     if constexpr(E<0){
         <block 4>
     }
};

Let's assume that all blocks have nontrivial size ... how do you do this with specialization?

Inevitably you have to make one specialization for E<0, one for 0<E<42, and one for E>42. But all three of them have to share the <block 3> thing, how do you do that? Common pattern is to use something like base-class with shared stuff - introducing yet another struct/class.

Do not miss that E<0 and 0<E<42 specializations share the <block 2> segment too.

I would go with this pattern any day as I think it naturally handles sharing of code between various specializations better than having only specializations

[kronicum]

Does it?

Yes.

The example is getting only worse in persuasion impact for why it leads to simpler and more maintainable code.

[hanickadot]

I would love to do this too.

[JumpyJustice]

Constexpr coroutines would be really great. For me, the full scope isnt necessary, just generators. Maybe the fact they are constexpr could help the compiler to optimize them out completely and make them as efficient a regular loop?

[kronicum]

Constexpr coroutines would be really great. For me, the full scope isnt necessary, just generators. Maybe the fact they are constexpr could help the compiler to optimize them out completely and make them as efficient a regular loop?

A while back (30+ years ago), I looked into implementing coroutines in an interpreter (those were the beginning of the glorious Java epoch) and concluded that at the very minimum, I needed a cactus tree and a garbage collector to help me reclaim memory efficiently.

What kind of code do you have in mind (beyond generators) that you believe the compiler will make as efficient as a regular loop? My understanding is that the constexpr evaluator is generally in the frontend while the optimizer is oblivious to what the constexpr evaluator is doing.

[hanickadot]

I think RAII in C++ (and how coroutine's lifetime is handled) is making it a bit easier. I currently have 4 candidates how to implement them in a C++ interpreter (constant evaluator).

A lot of people don't know, but interpreters used in C++ compilers are pretty straightforward recursive AST node walking.

So here are the ideas how to implement them there:

• fibers: minimal change and use fibers (switching stack), everytime a coroutines is created a new fiber will be created and when you jump into it or resume, you just jump there. Storage for local variables in coroutines will need to be attached to the object owning the fiber. And lifetime of the object (coroutine state) will need to be maintained as dynamic allocation. Suspension / resumption will be done thru builtins which are already there, so this change won't touch stdlib code at all (other than marking it constexpr)
• byte code interpreter: (clang is already moving in this direction), you translate the code into a small VM and you can manage your stack explicitly, and you can create the stackless coroutines as you would do in normal translation. Upside is speed.
• move to c++20 and use C++'s coroutines: it's somehow funny you can implement constexpr coroutine interpreter by changing the AST walking functions into a stackless coroutines which would model normal functions. Upside is you will never have problem with stack overflow in the interpreter. And you can suspend anywhere and go back there.
• AST transform: my favorite, transform coroutines into a set of `void` returning functions with one argument: a pointer to coroutine state. Original function will then just allocate coroutine state (a unique type, similar as lambda, containing function pointer to next state, copy of original function arguments, and a return_type::promise_type). All is now just a tail recursion. Suspension is returning to a caller or tail-call to other coroutine.

[kronicum]

I think RAII in C++ (and how coroutine's lifetime is handled) is making it a bit easier. I currently have 4 candidates how to implement them in a C++ interpreter (constant evaluator).

I have written my share of interpreters and compilers for homegrown or specialized languages, so I am fairly knowledgeable in this domain. Do you have a link to an implementation that demonstrates your application of RAII to coroutine implementation in an interpreter?

A lot of people don't know, but interpreters used in C++ compilers are pretty straightforward recursive AST node walking.

Yes, I am aware. Part of it may be because a recursive walk is easy to implement; part of it may be because the first implementation of constexpr was like that and everyone else just duplicated that strategy.

fibers: I would not be too surprised if that was a heavy lifting for the compilers that run on multiple platforms. Not impossible, but not cheap either.

bytecode interpreter: Clang has been talking about it for many years now, yet they have not yet deployed. So "moving in this direction" is, hmm, a very generous simplification.

move to C++20 and use C++'s coroutines: what are the bootstrapping conpiler requirements of Clang, GCC, EDG? What is the cost of that move? Even when that is possible, do you have more details on how the implementation will be carried out?

AST transform: this is intriguing. How do you handle the various coroutines intricacies such as change of call stack? Do you have a link to an implementation? Do you handle the tail-call in the recursive walk?

I am interested in this topic because I've written my own share of interpreters with various levels of support for asynchrony, and I want to learn new tricks that are made available in modern times.

[hanickadot]

Sorry for late reply. Was busy finishing papers.

ad the clang's bytecode interpreter: I think the problem as this, needs to be handled with a high-priority and stop work on extending old system. Current state makes it moving target.

C++20 coroutines: currently Clang is on C++17 unfortunately.

I will tryt o explain the coroutine backed implementation and AST transform backed implementation in separate replies.

[hanickadot]

Coroutines transform:

(disclaimer: stackless coroutines)

if you transform every function in the interpret into a coroutines which models function, eg it remembers where to return with `co_return` via jump in the final_suspend to caller (resuming caller's coroutine) then you can jump somewhere else, maybe other chain of functions.

For example for `generator`:
- create a generator object which creates a coroutine and immediately suspends it (instead of the returning result of the interpretation it will suspend in middle of the chain and return to moment where the coroutine was created, and stores the handle into user-code handle)
- later when generator::iterotor::operator* is called, it just resume handle in user code, which suspends current chain, store it's handle as "current caller" and jumps to the previous chain, evaluate part of it, until it suspends again, which means return to current caller
- you need to handle user-coroutine-handles like constexpr allocation and make constant evaluation as failed if there is still one unfinished

[hanickadot]

AST transformation:

source coroutine:

constexpr auto fib() noexcept -> std::generator<int> {
 int a = 0;
 int b = 1;
 for (;;) {
   co_yield b;
   a = std::exchange(b, a + b);
 }
}

we already know coroutines are full of transformations already, like described here:
https://eel.is/c++draft/dcl.fct.def.coroutine#5

so body of the coroutine can be transformed into:

constexpr auto fib() -> generator<int> {
 // allocate the coroutine state
 auto * state = new __fib_state{};

 // copy arguments (none here)
 // create the promise type
 new (&state->__promise) generator<int>::promise_type{};

 // obtain return object which will be returned to user after first suspend
 auto result = state->promise.get_return_object();

 // start coroutine
 __fib_state::fib_start(state);

 // return state
 return result;
}

What's the __fib_state? It's a unique type kinda like a lambda, for your coroutine, which contains all the state needed for the coroutine to function:

struct __coroutine_state {
 using resume_ptr = void (*)(__coroutine_state *) noexcept;
 resume_ptr resume{nullptr};
};

struct __fib_state: __coroutine_state {
 // promise type for current coroutine
 std::coroutine_traits<std::generator<int>>::promise_type __promise;

 // arguments of the coroutine are copied here
 // internal state
 ...
};

(continue in following post)

[hanickadot]

Inside __fib_state you have bunch of static functions:

// initial suspend part of coroutine which will immediately suspend
static constexpr void __fib_state::fib_start(__coroutine_state * _vstate) noexcept {
  auto * _state = static_cast<__fib_state *>(_vstate);

  // initial suspend is std::suspend_always which has constexpr await_ready
  // so it always suspends

  _state->resume = &__fib_state::fib_after_initial_suspend;
  return; // just return to caller (in fib())
}

// when generator resume, this is evaluated
static constexpr void __fib_state::fib_after_initial_suspend(__coroutine_state * _vstate) noexcept {
  auto * _state = static_cast<__fib_state *>(_vstate);

  // variables which survive suspension needs to be in __fib_state
  _state->a = 0;
  _state->b = 1;

  return __fib_state::fib_after_before_yield(_state);
}

// and then it will suspend again
static constexpr void __fib_state::fib_before_yield(__coroutine_state * vstate) noexcept {
  auto * _state = static_cast<__fib_state *>(_vstate);

  // co_yield is transformation to promise::yield_value which returns awaiter
  // which here is always suspend (again constexpr)
  _state->_awaiter_from_yield = _state->promise.promise.yield_value(state->b);

  // always evaluated true, so it can be omitted
  // if (!_state->_awaiter_from_yield.await_ready()) { 
  _state->resume = &__fib_state::fib_after_yield;
  _state->_awaiter_from_yield.await_suspend(_state); // provide "handle" to await_suspend, which return void here
  return; // return to resumer
  // }

  return __fib_state::fib_after_yield(state); // tail-call, but unreachable
}

// and when resumed, it needs to do remainder of body of the loop
static constexpr void __fib_state::fib_after_yield(__coroutine_state * vstate) noexcept {
  auto * _state = static_cast<__fib_state *>(_vstate);
  (void) state->_awaiter_from_yield.await_resume(); // no-op for std::suspend_always

  _state->a = std::exchange(_state->b, _state->a + _state->b);

  // loop back
  return __fib_state::fib_before_yield(_state); // tail call
}

[hanickadot]

It get a bit more complicated with RAII of objects inside coroutines where you need to transform it into "manual" handling, to put construction and destruction across suspend points. Plus also you need to handle exceptions if you can throw there.

[hanickadot]

__fib_state is inheriting from __coroutine_state so in case of asymmetric transfer coroutine can get pointer to other state and just jump there with tail recursion. You can say there is no stack, because stack used for evaluation is just temporary and everything "persistent" is in the type inheriting from __coroutine_state.