Since my previous article, there have been roughly 640 new commits to the Clang bytecode interpreter. Apart from the usual bug fixes, performance improvements, and smaller refactoring, the work resulted in these changes:
- Support for virtual bases (both interpreters)
- Support for expansion statements in constant expressions (both interpreters)
- Proper support for
dynamic_cast
, including multiple bases, and more - Support for
evaluateWithSubstitution()
- Support for
evaluateDestruction()
- Using tail-calls when interpreting bytecode, similar to what Python has been doing
- More support for x86 SIMD intrinsics (both interpreters)
The updated status page of the remaining test failures can be found here.
Easier testing
One problem with testing the bytecode interpreter, particularly in a large existing code base, was the need to modify compiler flags used during the build.
You can now build clang with -DCLANG_USE_EXPERIMENTAL_CONST_INTERP=ON
to use the bytecode interpreter by default. The behavior can be changed by passing -fno-experimental-new-constant-interpreter
. If you build clang from source anyway, this is a nice way of changing the interpreter to test other code bases.
This is available since Clang 23.
Recap: Data and metadata
When the bytecode interpreter allocates data for a variable, it uses a char
array. This contains metadata about the variable as well as the actual data.
More specifically, a field (in a record or array) is preceded by something called InlineDescriptor
, which we can get metadata from like initialization state, mutability, volatility, and so on. The InlineDescriptor
is then followed by the actual data of the field.
In practice, this means that data and metadata are interleaved in the allocated memory. For an example, consider this struct
:
struct S {
int a;
char c;
};
The allocated data for S
looks something like this:
| InlineDescriptor | data for a | InlineDescriptor | data for c |
I won't bore you with actual sizes and offsets. This construct is called a Block
in the end, and a pointer pointing to it is called a "block pointer". Not all pointers are block pointers. For example, you can imagine that the construct above is unnecessary for a function pointer.
Managing the data like this is useful if we can actually ever use (read or write) the data at compile time.
Opaque pointers
In real-life code bases, it often happens that a constant expression refers to a variable that isn't constant, but the result of the expression is still evaluatable at compile time. As an example, take this simple static assertion:
extern int k;
static_assert(&k < &k + 1);
This "obviously" works, even though we don't know the value of k
at all. We don't even need to know its exact address at compile time.
Up until now, the bytecode interpreter would still allocate a Block
for k
, and mark it as inaccessible. This was called a "dummy pointer". For the example above, that's not a big deal, but consider a large array that's not accessible but used in a constant expression:
struct S {
int a;
};
S s[1'000];
static_assert(&s[0].a < &s[999].a);
Not only is the array pretty large, but don't forget we're also inserting metadata into it, which means the resulting allocation is even larger. To make matters worse, s
is a global variable, so it would not be deallocated until the compiler process ended (or the ASTContext
was freed).
Dummy pointers were always considered a stop-gap solution, and they did their job of getting things moving. However, this year I ran into a problem regarding the implementation of __builtin_object_size
that required a feature that dummy pointers simply didn't support. So I gritted my teeth and finally implemented opaque pointers.
An opaque pointer (not to be confused with the similar concept in LLVM) is exactly the type of pointer I talked about above: Something we can refer to in a constant expression, but never read from or write to.
Instead of allocating memory for an opaque pointer, we first only need a "base" (a declaration or an expression). For the simple cases, this is all that's needed.
Once we need to refer to more complex expressions like s.[0].a[1].b
, we do allocate a "pointer path", which specifies a "path" of field (or array or base, or similar) operations to apply to the base. If you're familiar with Clang's APValue
, this is likely familiar to you, because it's similar to an lvalue
APValue
.
The biggest part of the transition from dummy pointers to opaque pointers was implemented in PR #220917. The results are promising, both in terms of compile-time improvements, as well as memory usage.
String pointers
In a similar fashion, another new pointer type has been introduced: String pointers. A string pointer is a pointer to a string literal. The contents of the string literal are not allocated in the bytecode interpreter, but the pointer is simply backed by the AST node of the string literal.
Using a string pointer, we can model string literals without allocating memory for them. Previously, we used to create regular block pointers, allocate memory and copy the string literal contents into the allocated Block
. Meanwhile, the AST node was in memory anyway, so our own allocating was unnecessary.
Similar to opaque pointers, string pointers cannot be written to. But string pointers can be read from (of course). Apart from memory savings, there is another reason for the introduction of string pointers. In C++, pointers to string literals only compare equal if they refer to the same "instance" of a string literal. This works:
constexpr bool test() {
const char *p = "foo";
const char *p2 = p;
return p2 == p;
}
static_assert(test());
Both p
and p2
point to a string literal, but it's the same instance of the literal, so no problems.
This, however, does not work:
constexpr bool test() {
return "foo" == "foo";
}
static_assert(test());
Example output (you can try it yourself on Godbolt):
<source>:7:15: error: static assertion expression is not an integral constant expression
7 | static_assert(test());
| ^~~~~~
<source>:5:16: note: comparison of addresses of potentially overlapping literals has unspecified value
5 | return "foo" == "foo";
| ^
<source>:7:15: note: in call to 'test()'
7 | static_assert(test());
| ^~~~~~
The example above could be (and has been) handled without string pointers. It's possible because we have 2 distinct string literals, each with their own AST nodes. It's rather trivial to figure out that the 2 pointers don't point to the same instance of a string literal. Now consider this example:
constexpr bool test() {
const char *p[2];
for (unsigned i = 0; i != 2; ++i)
p[i] = "foo";
return p[0] == p[1];
}
static_assert(test());
The comparison between p[0]
and p[1]
needs to be rejected, but there is only 1 AST for the string literal. It's evaluated twice, but that information didn't used to be present in the bytecode interpreter. Adding this information to the previous way we referred to string literals would require adding it to all block pointers, even though it's unnecessary and unused in almost all cases.
In string pointers, we simply save an ID
field, which helps us disambiguate multiple evaluations of the same string literal, such as in the example above.
Larger integers
Now for a more unfortunate change. In C and C++, a pointer can be cast to an integer and, potentially, back. Here's an example in C:
typedef __UINTPTR_TYPE__ uintptr_t;
char *a = (void*)(uintptr_t)(void*)&a;
As you can see in the LLVM output, the frontend successfully folds the initializer of a into simply a pointer to a
.
Previously, an integer type in the bytecode interpreter was exactly the size required for the target. Usually that means an integer was 4 bytes, a short 2 bytes, and so on. Those sizes are target-dependent, but we took that into account and things were fine.
Now for the example above. After casting &a
to uintptr_t
, all we have left is a pointer-sized integer. No more information. We could even potentially inspect the value of this integer, which is invalid at compile time, because the pointer-to-integer cast does not yield a stable value.
For the cast back from uintptr_t
to a void*
, we need to know whether the integer we're casting is even a valid pointer. If not, we need to (potentially) reject the cast completely. The example above is fine, but to implement it, a uintptr_t
cannot just be 8 bytes (on 64 bit systems). We need more information. In this case, we need to know if the integer was once a pointer.
So, 1 bit of extra information it is. But that's not enough, because adding an offset to such an integer-converted-from-a-pointer should also work. For example:
typedef __UINTPTR_TYPE__ uintptr_t;
char *a = (void*)(((uintptr_t)(void*)&a) + 3);
So we need to know what "kind" of integer it is: An actual integer value and an offset. The worst case is this example:
void FoldableAddrLabelDiff() {
static long x = (long)&&a-(long)&&b;
a:b:return;
}
If you're confused about what that even is: Good. Don't ever write such code. This is an "address label difference", where x
refers to the difference of the addresses of 2 labels (a
and b
). This is folded in the frontend, so to properly represent this address label difference, the integer must hold 2 pointers as well as the integral kind.
In the end, to support all the use cases above, all integers greater than or equal to 16 bits now take up 24 bytes in the bytecode interpreter. That's highly unfortunate, but reality and its programming languages are complex.
Conclusion
While there were some larger features that landed in the last year (and others were implemented but didn't land), I see it mostly as a time of stabilization. There were few testing regressions, both in the clang and libc++ test suites. The remaining test failures in the clang test suite were almost halved.
The next big feature I will be working on is array fillers (I know I've said that before). This is quite complex, unfortunately, and will require a fairly large commit and repeated testing to get right.