TL;DR: The constexpr evaluation historically revolves around the algorithm of constant folding (wikipedia) on the AST.
The problem is that constexpr becomes more omnipresent and it is gets harder and harder to support it. For example, there is no sign of such a thing as constexpr std::vector<T> that was supposed to be a thing, I believe, 4 years ago. Also it’s truly hard to fix constexpr bugs - they require plenty of time to dive into the code. In general, we have a peculiar limited C++ interpreter that works on the AST.
(People decided to start developing the ConstantInterpreter (more info) for Clang. They still make a Clang’s own C++ interpreter as well, because their main concern was the running time of the old AST interpreter (traversing the AST is slow)).
What if we outsource the constexpr evaluation to the LLVM IR?
When we have a LLVM IR module being built, we can request some computation on it.
It’s a known feature:
The lli tool can execute programs right from the LLVM IR bitcode.
I suggest to discuss this opportunity. Whenever we need to calculate a constant value, we can generate the corresponding LLVM IR (the dependant functions+variables) and request evaluation in it.
To optimize the evaluation (in case we have dozens of constexpr calls) we wouldn’t create a new LLVM IR module for every constexpr evaluation but rather keep the single LLVM IR module and put into it new data on the fly when meeting a new constexpr expression.
This is how it works now:
Clang is creating the AST.
Every constexpr expression is calculated by traversing the AST.
The fully built AST is converted into a LLVM IR module (via the CodeGen module)
This is how it could work (just an approach):
Clang is creating the AST, while keeping a dedicated LLVM IR module specifically for constexpr.
Every constexpr expression is calculated (interpreted) in the dedicated LLVM IR module.
The fully built AST is converted into a LLVM IR module (the new module has nothing to do with the dedicated module).
We see the constexpr expression, we put all its dependant classes/functions/etc. to the dedicated LLVM IR module (which hasn’t been put there yet) and then just evaluate the expression, and emplace the result into the AST being built.
lli is not an emulator. It will not execute IR of different architectures and it can only interpret (or JIT-compile) for the host architecture.
Given Clang is inherently a cross-to-everything compiler, and can even generate IR without the corresponding backend (which allows all tests to run no matter what backends are present), this seems like a non-starter.
Hi, I don’t quite understand the problem you mentioned.
Yes, LLVM IR is “interpreted” using the host architecture (in the lli and clang-repl tools too).
What exactly is the problem in “interpreting” constexpr expressions on the host architecture? Constexpr expressions evaluation is supposed to help building the AST.
The Clang’s AST itself is independent of any target architecture.
The Clang’s AST itself is independent of any target architecture.
While the AST data structure is independent of target architecture the AST will describe a target-specific program. Further, using Clang CodeGen to generate an IR module from that AST will generate a target-specific IR representation because Clang CodeGen does lots of target-specific things.
The other wrinkle to keep in mind is that lli and clang-repl also use LLVM’s JIT, not interpreter. I don’t know the current state of the interpreter, but historically it had some significant gaps in support. Making Clang JIT constexpr would add significant distribution challenges since some of the platforms that Clang runs on have security provisions locking down JITing.
I don’t necessarily think your proposal is bad, but there’s a lot of complication and it would not be as straight forward as you make it sound.
Using Clang CodeGen to generate IR for constexpr evaluation seems like a non-starter, due to complications with cross-compilation, and differing semantics between compile-time and runtime (particularly related to diagnostics). I think trying to share the code like this actually ends up increasing the complexity overall.
You could theoretically add an optional JIT to ConstantInterpreter. But there’s probably room to optimize without going that route, and I doubt the evaluation is actually a bottleneck in most cases.
Afaik, undefined behavior in constexpr functions is ruled out by the standard. Would that mean that clang’s undefined behavior sanitizer would need to be enhanced such that it is able to catch all undefined behavior which could potentially occur during evaluating constexpr?
Like others, I’m also not certain this is feasible due to cross compilation issues. Also, the constant expression interpreter is required to identify instances of undefined behavior so that they can be properly diagnosed in some contexts and it’s not clear to me how this approach would handle that.
The current efforts underway (largely being driven by @tbaeder) are moving us away from interpreting the AST directly and towards more of a JIT approach where we can easily memoize the resulting computations. We’ve been seeing some excellent performance gains from this approach. You might consider helping with those efforts, as this is a pretty extensive undertaking.
That would be an interesting experiment. Since clangir is basically a MLIR dialect, I wonder if we could do evaluations using a tailored version of SCCP.