[Clang Interpreter] Initial patch for the constexpr interpreter

[nand]

Summary

This patch introduces the skeleton of the constexpr interpreter,
capable of evaluating a simple constexpr functions consisting of
if statements. The interpreter is described in more detail in the
RFC. Further patches will add more features.

[rsmith]

clang/lib/AST/ExprVM/InterpFrame.h

89–90 ↗

(On Diff #208520)

Separate allocation for each frame seems wasteful. Have you considered using a slab-allocated stack or similar? (Eg, allocate a large block up front and allocate the locals from that, and allocate more blocks if the first one is exhausted; you can cache the blocks on the vm::Context for reuse with no extra round-trips to the heap.)

clang/lib/AST/ExprVM/Opcodes.inc

1 ↗

(On Diff #208520)

This file is hardcoding too much of its #includers' implementation details. Please find a way to improve that. Generally we prefer

enum Opcode : uint32_t {
#define OPCODE(Name) EO_ ## Name,
#include "Opcodes.inc"
};

with this in Opcodes.inc:

OPCODE(Jmp)
OPCODE(JT)
OPCODE(JN)
// ...
#undef OPCODE

over the style you're using here, as it makes the point of use much more readable, and allows reuse of the same set of macros rather than having a distinct one for each use.

1 ↗

(On Diff #208520)

This file also needs a *lot* more documentation strings than it currently has. We need to document what all the opcodes are, what effects they have on the interpreter state, and so on.

344–392 ↗

(On Diff #208520)

Opcode names should be formatted following our normal coding conventions: use UpperCamelCase here rather than ALL_CAPS.

clang/lib/AST/ExprVM/Pointer.h

30 ↗

(On Diff #208520)

How is this going to work for subobjects? We can't generate the full space of all possible descriptors, as that would be unmanageable for large arrays of complicated types.

36–39 ↗

(On Diff #208520)

Please use a distinct type for representing size-in-the-interpreter, to avoid confusion and bugs when dealing with code that must manage both compile-time sizes and runtime sizes. And please use CharUnits for representing sizes-at-runtime.

40–49 ↗

(On Diff #208520)

Consider packing these 5 members into 4 bytes.

clang/lib/AST/ExprVM/Program.h

37 ↗

(On Diff #208520)

Consider adding a type-safe wrapper for this.

105 ↗

(On Diff #208520)

If CodePtr is a plain pointer, using a single flat vector here seems dangerous; you'll have invalidation issues if you ever trigger creation of a Function while evaluating, which seems like something that will happen in practice, eg:

constexpr int f();
constexpr int g() { return f(); }
constexpr int f() { return 0; } // or imported from a module at this point
constexpr int k = g(); // evaluation of this call triggers generation of code for f

106–107 ↗

(On Diff #208520)

Using a (presumably very large) std::map for this would presumably be very time- and space-inefficient. Do you expect this to be dense? (Would a flat array of SourceInfo work better?)

clang/lib/AST/ExprVM/Type.h

24–34 ↗

(On Diff #208520)

As previously, please follow coding guidelines wrt naming here.

51–53 ↗

(On Diff #208520)

What do you expect to use this for? If you need to encode a pointer, would it make sense to have a distinct primitive type for that?

64–75 ↗

(On Diff #208520)

Injecting T into this seems too implicit to me. Consider instead accepting the name of a function-like macro and invoking it on the type. Eg:

#define RETURN_SIZEOF(T) return sizeof(T);
TYPE_SWITCH(Type, RETURN_SIZEOF);

Also please wrap the expansion in do { ... } while (0) to require the user of the macro to provide a semicolon afterwards.

[nand]

How do you intend to represent pointers cast to integer types? Allocating 64 bits of state for a 64-bit integer is insufficient to model that case.

Is this ever going to be allowed in constexpr? If that is the case, we'll add a separate type for all integers which are large enough to hold a pointer, a tagged union indicating whether the value is a number or a pointer. This would add significant overhead, but I don't see any other way which can correctly diagnose UB when casting a random integer to a pointer.

[jfb]

In D64146#1604717, @nand wrote:

How do you intend to represent pointers cast to integer types? Allocating 64 bits of state for a 64-bit integer is insufficient to model that case.

Is this ever going to be allowed in constexpr? If that is the case, we'll add a separate type for all integers which are large enough to hold a pointer, a tagged union indicating whether the value is a number or a pointer. This would add significant overhead, but I don't see any other way which can correctly diagnose UB when casting a random integer to a pointer.

Most integers won't be in that category, you can therefore speculate that fact when emitting bytecode, and throw away byte code when the assumption turns out to be wrong (and re-generate the more expensive byte code).

[rsmith]

In D64146#1604717, @nand wrote:

How do you intend to represent pointers cast to integer types? Allocating 64 bits of state for a 64-bit integer is insufficient to model that case.

Is this ever going to be allowed in constexpr?

It's not sufficient for this to handle only the things that are allowed in constant expressions; you also need to allow the things that are allowed by Clang's current constant evaluator, which includes this case. There are also constructs that allow arbitrary constant folding within the context of constant expression evaluation (such as a __builtin_constant_p conditional). So yes, you need to deal with this.

If that is the case, we'll add a separate type for all integers which are large enough to hold a pointer, a tagged union indicating whether the value is a number or a pointer. This would add significant overhead, but I don't see any other way which can correctly diagnose UB when casting a random integer to a pointer.

These cases are likely to be rare enough that separately-allocated storage for this case could work. You'll need at least one bit somewhere to track whether you're in the "pointer cast to integer" case, though.

(You also need to be able to distinguish between an integer value and an uninitialized integer and an out-of-lifetime integer, so you'll presumably need some side-table to track the state of subobjects anyway.)

[nand]

We can add a separate integer type which tracks all the additional information required by __builtin_constant_p and compile all integers to it in this context. A later patch added an APInt fallback to the interpreter if an integral cannot be mapped to a type supported by the VM - this mechanism could be used to implement the fallback for contexts which cast pointers to integers.

clang/lib/AST/ExprVM/Compiler.h

125 ↗

(On Diff #208520)

I've removed the size field since it's not going to be used, but left the structure since it will gain other fields in future patches.

[nand]

I have applied most of the changes you suggested to my HEAD which had significantly more functionality, including a replacement of Opcodes.in with TableGen.
Quite a few of your concerns are answered by the features I have added between submitting the patch and now. The interpreter now stands at ~6k LOC.

Should I update the diff with an interpreter trimmed down to the functionality of the current diff (~3k LOC) or post the full interpreter now? What would be easier to review?

clang/lib/AST/ExprVM/Compiler.cpp

88 ↗

(On Diff #208520)

Overflow happens here if a function takes more than a few million arguments. I think clang would die before it gets here.

488–503 ↗

(On Diff #208520)

I'd like to do this in a future diff, once we add support for more constructs which discard their results.

clang/lib/AST/ExprVM/InterpFrame.h

89–90 ↗

(On Diff #208520)

Yes, I considered allocating this on the stack - I just don't want to add that complexity to the interpreter yet. I like to avoid changing this until it becomes a noticeable performance problem.

clang/lib/AST/ExprVM/Pointer.h

30 ↗

(On Diff #208520)

Subobjects will have pointers to descriptors embedded into their data - a pointer inside a block can follow that chain of descriptors up to the root.

36–39 ↗

(On Diff #208520)

I've added an alias to be used for the sizes of object as determined by the interpreter - CharUnits will be used when interfacing with APValue.

40–49 ↗

(On Diff #208520)

I'd like to avoid packing stuff for now, makes it harder to change things later and it's not a performance problem yet.

clang/lib/AST/ExprVM/Program.h

105 ↗

(On Diff #208520)

This wouldn't have been a problem, but the compilation of default constructors caused issues. Now the compiler can recursively invoke itself.

106–107 ↗

(On Diff #208520)

Replaced this with a dense array + binary search.

clang/lib/AST/ExprVM/Type.h

51–53 ↗

(On Diff #208520)

Removed this type.

64–75 ↗

(On Diff #208520)

I'd rather have a documented implicit than use nested macros...

[nand]

Implemented suggestions from @rsmith.

Since I had ~30 patches on top of the code in the diff, I applied the changes on those
and removed some functionality to produce this updated diff. This update uses the
byte code generator parameterised by a template emitter: the LinkEmitter emits and
links bytecode, while the EvalEmitter directly evaluates opcodes. The interpreter,
evaluator and most opcode-related code is now generated from Opcodes.td through
TableGen. Since the feedback included several references to pointers, I have included
some pointer functionality as well.

I hope the size of this diff is manageable - if really required, I could further trim
it down. Since this is a new subproject which does not introduce intrusive changes and
there are a significant number of other commits depending on this patch, I would like
to avoid that.

[rsmith]

I would like to better understand the big picture for descriptors, pointers, and so on. I'm not yet seeing how the pieces are going to fit together and not frequently require expensive operations. For example, pointer arithmetic requires determining the array bound of the pointee; pointer subtraction requires determining whether two pointers point into the same array; pointer comparisons require determining the divergence point in the access paths between two pointers. These path-based operations were easy in the old representation, and seem to be difficult in the new representation, so I want to make sure that they've been properly considered. It's also not clear to me how you'll model pointers that have lost their designator (through constant folding), where you have a runtime offset but no compile-time offset, or pointers that point to objects whose values are not part of the evaluation (for example, extern globals), or pointers that have a designator but no base (for __builtin_object_size handling).

This choice of representation also seems to make it really easy for a minor bug in the interpreter to turn into undefined behavior during compilation. Have you given any thought to how that might be avoided or mitigated?

clang/include/clang/Basic/LangOptions.def

291–294

"Clang" is redundant here (what else could it be?). If we're calling the new thing "interp" internally, then I guess "EnableInterp" and "ForceInterp" seem OK, but given that this is just scaffolding until the new interpreter is done, maybe "EnableNewInterp" and "ForceNewInterp" would be better. Suggestion:

BENIGN_LANGOPT(EnableNewInterp, 1, 0,
               "enable the experimental new constexpr interpreter")
BENIGN_LANGOPT(ForceNewInterp, 1, 0,
               "force the use of the experimental new constexpr interpreter")

clang/include/clang/Driver/Options.td

836–839

On reflection, let's put "new-" in here too, to match -fexperimental-new-pass-manager (so -fexperimental-new-constexpr-interpreter). (As above, this flag name should not contain the string "clang".)

clang/lib/AST/CMakeLists.txt

85–87

Please keep these in alphabetical order.

clang/lib/AST/ExprConstant.cpp

55–56

Please keep these in alphabetical order.

5039–5040

Missing a check for ForceClangInterp here.

12135–12136

Missing a check for ForceClangInterp here.

12362–12364

Isn't this in the wrong place? If interp succeeds, I think we always want to stop; it's only if interp fails / bails that ForceClangInterp should matter. Or did I misunderstand what that flag is for?

clang/lib/AST/ExprVM/Pointer.h

30 ↗

(On Diff #208520)

I don't think I understand what you're suggesting here. If I have, for example:

struct X { char c; };
X x[1000000];

... are you saying you would embed 1000000 descriptors into the representation of x? That seems extremely wasteful to me. Presumably the goal should be to get as close to allocating 1000000 bytes of storage for x as possible. I think we can probably get down to 1000000 bytes for the c members plus perhaps 1 bit for each X object (to track whether it's within its lifetime) and 2 bits for each char object (to track whether it's within its lifetime and whether it's initialized), for a 1.375x storage overhead in this case. But I don't see how you get there from this representation.

clang/lib/AST/Interp/ByteCodeGen.cpp

54

I think emitDestruction would probably be a better name, since this needs to encompass things that are not destructors (such as invalidating pointers/references that point into the destroyed objects).

99

Doc comment please. "Block" means two different things in Clang (compound statements and the Apple Blocks extension) and a reader needs to know which one.

119

I don't know what this means. Declarators don't typically introduce a scope (for lifetime purposes).

Do you mean "for the initializer of a top-level variable declaration" or something like that?

145–153

No else after return, please:

if (auto *Exp = dyn_cast<Expr>(S)) {
  if (Exp->getType()->isVoidType())
    return this->Visit(Exp);
  return discard(Exp);
}
return this->bail(S);

161

No auto here, and please don't shadow clang::Stmt with a local variable.

186

No auto here, please.

206

No auto here, please.

217

No auto here, please.

221

No auto here, please.

229–230

Especially no auto here. Even someone familiar with the rest of the clang codebase won't be able to guess these types. In particular, as a reader, I'm wondering if this is some type provided by Emitter or whether it's some type provided by ByteCodeGen, and what the contract is between this class and its template argument with regard to this type. Spelling this as typename Emitter::Label would help substantially.

I'm not going to point out any more uses, but generally if you only use auto when the type is obvious from the spelling of the initializer (eg, when the initializer is dyn_cast<T>(...)), that would be fine.

256

(This uses of auto like this are also fine; it's obvious this is an iterator and we don't need to know more than that.)

352–381

Have you considered how you will support Clang's current constant folding of && and || expressions where the left-hand side is non-constant but the right hand side is a false or true constant (respectively)?

536

We can, but should we?

I would think the only time we can reach this case is when we're constant-evaluating an expression within a function and that expression names a function parameter, and in that case, the expression should be treated as non-constant. We should have a more direct way to represent "if you get here, the evaluation is non-constant, with this reason" in the bytecode.

546

The above ParmVarDecl case can fall through into here, because a ParmVarDecl is a VarDecl. Is that what you intended?

Do you actually need to treat locals and parameters separately? This would seem simpler if you could model them as being the same thing.

600–601

Using an && here rather than a nested if would help readability a little.

605–611

Please try to find some way to refactor this so that there's not so many nested scopes; it makes it hard to follow the control flow within the function.

647–662

I'd like to see this generated from a .def file, rather than enumerating the various currently-supported integer types in many different places. The goal should be that adding support for a new integer type / size (say we start supporting a target with 48 bit integers) should require making changes in only one place. Case in point: you're currently missing support for 128-bit integers, which Clang does support across many targets.

718–720

These {} arguments are completely opaque here. Please add some kind of a clue as to what you're passing in here. (Can you use SourceInfo()?)

clang/lib/AST/Interp/ByteCodeGen.h

40

Does Emitter need to be a base class rather than a member?

111–113

Is there any reason these need to be virtual? It looks like you would never call these from a context where the concrete type is unknown. (These are the only implementations of the pure virtual functions they override.)

clang/lib/AST/Interp/Descriptor.h

29–31

Parameter names here would help explain what these functions are supposed to do -- particularly for BlockMoveFn (which char* is which?), but also for the bool parameter of BlockCtorFn.

62

scoped -> scope

clang/lib/AST/Interp/EvalEmitter.cpp

71–75

It seems like a problem that an unsupported construct in a !isActive() context causes us to fail evaluation.

105–111

Can this happen? I would expect not: if we can't cope with backwards jumps here, I wouldn't expect us to be able to cope with function calls / returns.

If this can happen, we need to skip anything that happens after the return rather than keeping on evaluating it.

clang/lib/AST/Interp/EvalEmitter.h

69

I can't find any calls to this, and I'm not sure what it's for. Is it necessary?

112–114

I'm curious how much this approach costs us, compared to allowing the emitter to tell ByteCodeGen whether to emit both arms of a ?: (or if not, telling it which one to follow) and similarly for && / ||. There's the constant overhead of checking isActive() on each action, plus the cost of the calls into EvalEmitter while "evaluating" the unselected operand. (Eg, false ? some-very-large-expression : 0 would be evaluated much faster if we could tell ByteCodeGen not to bother with the unselected operand.)

(This approach doesn't support statement-expressions, because there can be backwards jumps in those, so I think ?:/&&/|| are pretty much the only things this supports, right?)

clang/lib/AST/Interp/Interp.h

213–222

This is missing lots of necessary checks; I think your chosen model for pointers makes these checks quite hard to implement. The validity of pointer comparisons in constant evaluation depends on the point of divergence of the two access paths. For example:

struct A { int n; };
struct B : A { int m; } b;
B ba[10];
constexpr bool x = ba[0].n < &ba[0].m; // error, not constant, divergence point is base class
constexpr bool y = ba[0].n < &ba[1].m; // ok, divergence point is array indexing

Also, access control must be taken into account:

struct A {
  int x;
private:
  int y;
  constexpr bool q(A a) { return &a.x < &a.y; } // not constant, x and y have different access
};

218–219

On what basis do you assume that the orders of the offsets in the compile-time representation has any relation to the correct order for a pointer comparison? Do you intend to guarantee this when doing struct layout for the interpreter? If so, please include a comment here explaining that.

clang/lib/AST/Interp/InterpFrame.cpp

25–36

It seems wasteful to me to do this initialization work when entering the frame rather than when reaching the declaration of the variable in question. Do we need to do it early like this?

How does this deal with loops? I would have expected that we'd re-initialize a loop scope each time we enter the loop body, so that we don't confuse variables from one iteration with variables from another.

clang/lib/AST/Interp/LinkEmitter.h

32

Should this be called ByteCodeEmitter if it emits byte code?

clang/lib/AST/Interp/Opcodes.td

1

This still needs to be expanded to actually describe what the opcodes do (that is, their effects on the stack and any side-effects they cause). Something simple like:

// [RetVal] -> [], returns RetVal
def Ret : Opcode {

// [A, B] -> [B - A]
def Sub : AluRealOpcode;

would be enough.

clang/lib/AST/Interp/Pointer.h

69–78

If we're allocating one of these for every storage allocation in the evaluation, packing these bools into the spare bits in the pointers seems worthwhile.

245–249

What is this for? I think we need a design document here describing the intended model for pointers, references, descriptors, and so on -- preferably something that can be included in the internals manual.

251–261

You will also need to track at least:

• Whether this is a one-past-the-end pointer
• (Information equivalent to) which union members were accessed on the path to this point

I think everything else can be reconstructed from the type and offset.

[nand]

Implemented @zygoloid's suggestions

[nand]

updated diff, implemented requested changes

clang/include/clang/Basic/LangOptions.def

291–294

The goal is to evaluate everything that is constant - I would like to avoid using constexpr specifically in the name.

clang/lib/AST/ExprConstant.cpp

5039–5040

This is intended - if the interpreter bails and ForceInterp is set, we emit a diagnostic in Context, promoting the error to a failure.

clang/lib/AST/Interp/ByteCodeGen.cpp

352–381

Same as with statement expressions in the evaluating emitter - some sort of closure which compiles and executes when triggered.

536

We absolutely need this to emit the warning:

constexpr int callee_ptr(int *beg, int *end) {
  const int x = 2147483647;
  *beg = x + x; // expected-warning {{overflow in expression; result is -2 with type 'int'}}\
                // expected-note 3{{value 4294967294 is outside the range of representable values of type 'int'}}
  return *beg;
}

546

Refactored + fixed this by moving stuff to separate functions.

clang/lib/AST/Interp/EvalEmitter.cpp

71–75

Currently the interpreter cannot work side-by-side with the interpreter since reading from APValue is not supported at all... Since I am unsure whether I ever want to implement an APValue -> Interpreter mapping, I do not mind this, as long as diagnostic pinpoint the next feature to be implemented.

105–111

Theoretically not, but it helped me catch a few bugs in the past, so I would like to keep it conditional.

clang/lib/AST/Interp/EvalEmitter.h

69

The conditional operator will require it to handle the fallthrough from the false branch to the following expression.

112–114

I'd like to revisit this at a later point in time - for now I think predication is the simplest option and I would like to stick with the simple options until the interpreter is feature-complete.

Statement expressions would not be predicated, the current plan is to generate a closure-like method for them.
Another idea would be to revert to bytecode generation whenever the landing pad of a potentially backwards jump is encountered - these spots are quite well defined.

clang/lib/AST/Interp/Interp.h

213–222

I don't think there's a zero-cost way around this. We'll need to track more metadata to check whether fields are public/private and traverse the pointer chain to find divergence points. The InlineDescriptors might have a few spare bits could be used to cache "tags" which classify pointers into comparable classes? At this point, it is quite hard to decide what case to make fast at what cost.

218–219

Yes, the layout of fields in the interpreter is supposed to match the target's record layout.

clang/lib/AST/Interp/InterpFrame.cpp

25–36

We can optimise this later, avoiding the need to create blocks for local primitives which never have pointers taken. If a local does not have a pointer generated to it using GetLocalPtr, the block is not needed at all and zero-initialisation using memset should do the job.

clang/lib/AST/Interp/Opcodes.td

1

I was a bit afraid of documenting everything and then changing everything, but things seem to be quite stable now, so I will add some documentation.

clang/lib/AST/Interp/Pointer.h

69–78

It's definitely on the TODO list - I would like to avoid such optimisations for now, until enough features are available to run sizeable benchmarks.

251–261

It's on the TODO list - I am aiming for C++11 conformance ASAP and this will be required.

[nand]

clang/lib/AST/Interp/ByteCodeGen.cpp

647–662

This is the only case where such a switch occurs - there is another for zero initialisation, but it's quite different. A def which would capture the little common functionality would be quite ugly, so I would like to avoid it.

As for other integers, there won't be support for any. There are two more branches for the fixed-point catch-all fallback.

clang/lib/AST/Interp/ByteCodeGen.h

40

The entry point is through the emitter which needs to call into the code generator, things don't really work if the emitter is a field.

clang/lib/AST/Interp/Pointer.h

245–249

I haven't written things up yet since I changed quite a few things over the past few weeks. I am wrapping up support for unions and will produce a more detailed document afterwards. In the meantime, I have documented this field.

[nand]

The old path-based approach is slow for most operations, while the new pointer-based approach is fast for the most common ones.
For read/write/update operations, it is enough to check the pointer and at most a single descriptor to ensure whether the operation
can be performed. For some operations, such as some pointer comparisons, in the worst case the old-style path can be reproduced by
following the pointers produced through the getBase method, allowing us to implement everything.

Extern objects are handled by allocating memory for them, allowing pointers to those regions to exist, but marking the actual storage
as extern/uninitialized and preventing reads/writes to that storage.

Some details of corner cases are not clear at this point, but the fact that we can reproduce full paths and have space to store any special
bits gives me the confidence that we can converge to a full implementation.

I want to stress again the fact that C++ has an insane number of features and I am focusing on implementing as many of them, leaving a
path towards future optimisations open. I do not want to clobber initial patches with optimisations that would increase complexity - the
few things we do with direct local reads/writes and improved loops already yield significant speedupds.

[rsmith]

I think we're past the point of large-scale structural comments that are better addressed before the first commit, and it'd be much better to make incremental improvements from here.

Please go ahead and commit this, and we can iterate in-tree from now on. Thanks!

clang/include/clang/Basic/OptionalDiagnostic.h

41–75

I think these three all belong in PartialDiagnostic rather than in OptionalDiagnostic. (It doesn't make sense that an OptionalDiagnostic can format an APSInt but a PartialDiagnostic cannot.)

clang/include/clang/Driver/Options.td

839

const -> constant

clang/lib/AST/Interp/ByteCodeGen.cpp

26

using llvm::Expected;

536

As noted, the evaluation should be treated as non-constant in this case. This is "evaluate for overflow" mode, in which we want to keep evaluating past non-constant operations (and merely skip sub-evaluations that we can't process because they have non-constant values). We will need a bytecode representation for "non-constant evaluation". We should use that here.

clang/lib/AST/Interp/ByteCodeGen.h

40

I think the fact that the entry point to ByteCodeGen is in the Emitter base class is the cause of this design complexity (the inheritance, virtual functions, and layering cycle between the code generator and the emitter). For example, looking at ByteCodeEmitter, we have:

• ByteCodeEmitter::compileFunc is the entry point, and is the only function that calls compile
• ByteCodeEmitter::compile is a virtual function that calls into ByteCodeGen
• otherwise, ByteCodeGen only calls into ByteCodeEmitter and ByteCodeEmitter never calls into ByteCodeGen

(And the same thing happens in EvalEmitter.) That to me suggests an opportunity to improve the layering:

• move ByteCodeEmitter::compileFunc out of ByteCodeEmitter into a standalone function that creates a ByteCodeGen<ByteCodeEmitter> and calls compile on it
• remove the virtual functions and store the Emitter as a member of ByteCodeGen

No need to do this right away.

86

Please can you pick a different name for this, that's more different from the AccessKinds enum? AccessOp or something like that maybe?

clang/lib/AST/Interp/Opcodes.td

179–222

Please document what the Args mean.

[nand]

refactoring + implemented changes

[nand]

deactivated tests

[nand]

replaced llvm::make_unique with std::make_unique

[teemperor]

Seems like this patch introduced a cyclic dependency between Basic and AST when building with LLVM_ENABLE_MODULES=On:

While building module 'Clang_AST' imported from llvm/lldb/include/lldb/Symbol/ClangUtil.h:14:
While building module 'Clang_Basic' imported from llvm/llvm/../clang/include/clang/AST/Stmt.h:18:
In file included from <module-includes>:73:
clang/include/clang/Basic/OptionalDiagnostic.h:17:10: fatal error: cyclic dependency in module 'Clang_AST': Clang_AST -> Clang_Basic -> Clang_AST
#include "clang/AST/APValue.h"

[gchatelet]

This patch broke my build as well (discovered by runnin git bisect), command line

cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_C_COMPILER=/usr/local/bin/clang -DCMAKE_ASM_COMPILER=/usr/local/bin/clang -DCMAKE_CXX_COMPILER=/usr/local/bin/clang++ -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DBUILD_SHARED_LIBS=ON -DLLVM_USE_SPLIT_DWARF=ON -DLLVM_OPTIMIZED_TABLEGEN=ON -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD=ARC -DLLVM_ENABLE_PROJECTS=clang -DLLVM_BUILD_TESTS=ON -DLLVM_BUILD_DOCS=ON -DLLVM_ENABLE_WERROR=ON -H/redacted/git/llvm-project/llvm -B/tmp/llvm-project_dbg_compiled-with-clang -GNinja
ninja -C /tmp/llvm-project_dbg_compiled-with-clang

Error:

/usr/bin/ld: tools/clang/lib/AST/Interp/CMakeFiles/obj.clangInterp.dir/Block.cpp.o:(.data+0x0): undefined reference to `llvm::EnableABIBreakingChecks'
/usr/bin/ld: tools/clang/lib/AST/Interp/CMakeFiles/obj.clangInterp.dir/ByteCodeEmitter.cpp.o: in function `clang::interp::ByteCodeEmitter::emitAdd(clang::interp::PrimType, clang::interp::SourceInfo const&)':
/usr/bin/ld: tools/clang/lib/AST/Interp/CMakeFiles/obj.clangInterp.dir/ByteCodeEmitter.cpp.o: in function `clang::interp::ByteCodeEmitter::emitAddOffset(clang::interp::PrimType, clang::interp::SourceInfo const&)':

...

[svenvh]

Shared library builds seem to be broken indeed. I tried fixing by adding Support and clangAST as dependencies for clangInterp, but that creates a cyclic dependency between clangAST <-> clangInterp. Which makes me wonder whether clangInterp should be a separate library or be part of clangAST?

[lebedev.ri]

In D64146#1657117, @svenvh wrote:

Shared library builds seem to be broken indeed. I tried fixing by adding Support and clangAST as dependencies for clangInterp, but that creates a cyclic dependency between clangAST <-> clangInterp. Which makes me wonder whether clangInterp should be a separate library or be part of clangAST?

Arrived at same conclusions, reverted in rL370874.

[lebedev.ri]

In D64146#1657146, @lebedev.ri wrote:

In D64146#1657117, @svenvh wrote:

Shared library builds seem to be broken indeed. I tried fixing by adding Support and clangAST as dependencies for clangInterp, but that creates a cyclic dependency between clangAST <-> clangInterp. Which makes me wonder whether clangInterp should be a separate library or be part of clangAST?

Arrived at same conclusions, reverted in rL370874.

And that was even pointed out several days ago before the patch got relanded last two times:

In D64146#1653221, @teemperor wrote:

Seems like this patch introduced a cyclic dependency between Basic and AST when building with LLVM_ENABLE_MODULES=On:

While building module 'Clang_AST' imported from llvm/lldb/include/lldb/Symbol/ClangUtil.h:14:
While building module 'Clang_Basic' imported from llvm/llvm/../clang/include/clang/AST/Stmt.h:18:
In file included from <module-includes>:73:
clang/include/clang/Basic/OptionalDiagnostic.h:17:10: fatal error: cyclic dependency in module 'Clang_AST': Clang_AST -> Clang_Basic -> Clang_AST
#include "clang/AST/APValue.h"

@nand Please don't reland this patch until these concerns are addressed.

[nand]

Thanks for identifying these issues - I fixed the cycle detected by modules since then, however I wasn't aware of the issue with shared libs until now.

[RKSimon]

MSVC builds are seeing template instantiation issues with this patch: http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/27972/steps/build/logs/warnings%20%2824%29

[nand]

Merged clangInterp and clangAST into a single library while keeping Interp in a separate folder.
This is required since clangInterp needs access to the AST, but the intry points to the interpreter
are also in AST.

[nand]

Does anyone have any suggestions on how to fix the MSVC problems? I am trying to get access to a Windows machine, but it's not guaranteed.

[lebedev.ri]

In D64146#1657473, @nand wrote:

Merged clangInterp and clangAST into a single library while keeping Interp in a separate folder.
This is required since clangInterp needs access to the AST, but the intry points to the interpreter
are also in AST.

I don't have an actionable alternative suggestion but this seems like counter-correct layering, trying to paper over the issue instead of fixing it.

[nand]

The existing evaluator is not a separate library to start with. Given the tangling between ExprConstants.cpp and the AST nodes, I don't really see any elegant way of dealing with this problem.

An example of the problem is FieldDecl::getBitWidthValue.

[nand]

@jfb suggested I add @rnk: I was wondering if you have any suggestions on how to fix the msvc warnings/errors? I'd be grateful if I had some feedback on what features of C++ I should avoid using and what I should replace them with.

[RKSimon]

@nand The MSVC warnings are self explanatory - you've declared a number of methods (visitIndirectMember, emitConv and getPtrConstFn) but not provided definitions, as they're on template classes MSVC complains, a lot.

[nand]

I am providing definitions in the C++ file - the problem is that they are not available in the header before the extern declaration. The methods are available at the site of the extern definition.
gcc and clang accept this, so does Visual Studio 2019. This feels like an incorrect implementation of extern templates in Visual Studio?

I see two ways to proceed: move everything into a header (would like to avoid this) or silence the warning on VC++ (not great either).
Is there a better way? Which option is less bad from these two?

[RKSimon]

In D64146#1663867, @nand wrote:

I am providing definitions in the C++ file - the problem is that they are not available in the header before the extern declaration. The methods are available at the site of the extern definition.
gcc and clang accept this, so does Visual Studio 2019. This feels like an incorrect implementation of extern templates in Visual Studio?

I see two ways to proceed: move everything into a header (would like to avoid this) or silence the warning on VC++ (not great either).
Is there a better way? Which option is less bad from these two?

I think I'm missing something - for instance when I search the patch for "visitIndirectMember", all I get is this in ByteCodeExprGen.h:

bool visitIndirectMember(const BinaryOperator *E);

I don't see it in ByteCodeExprGen.cpp

[nand]

Totally missed that - thanks for noticing. I must have forgotten to remove stuff from the header since clang/gcc don't warn about it.
I'll get hold of a Windows machine soon-ish and I'll make sure to fix this problem.
Thanks!

[RKSimon]

In D64146#1665003, @nand wrote:

Totally missed that - thanks for noticing. I must have forgotten to remove stuff from the header since clang/gcc don't warn about it.
I'll get hold of a Windows machine soon-ish and I'll make sure to fix this problem.
Thanks!

If you remove those 3 declarations from the headers and update the patch I can test it on my windows machines for you.

[nand]

removed declarations with no definitions

[RKSimon]

rebase?

[nand]

rebase

[nand]

reset accidentally changed tests

[RKSimon]

Thanks - this builds cleanly on MSVC now

[nand]

Thanks for looking into the problem - sorry for the delay!

[RKSimon]

In D64146#1667567, @nand wrote:

Thanks for looking into the problem - sorry for the delay!

No problem, you still need a specialist to approve the patch though

[nand]

Added a FIXME to reflect the intention to move the interpreter to its own library

[jfb]

Sounds like this is ready to land again! Thanks for fixing everything.

[RKSimon]

Accepting this to remove the block

[jrtc27]

So I'm running into issues with this patch, specifically the line annotated below. I'm trying to compile our CHERI-LLVM fork as a native pure-capability CHERI[1] binary (which eventually will mean compiling the Morello-LLVM fork of our CHERI-LLVM to run as a native pure-capability CHERI binary on Arm's prototype Morello[2] board when it ships late this year/early next year), and I have LLVM (other than Orc JIT which is a whole beast and can't work without in-tree backend support) and LLD working (albeit only very lightly tested), and if I stub out that single function I am able to get Clang itself compiling and working (at least, well enough to compile a hello world C program all the way down to an executable), so this is the only technical blocker that I know of, which is rather frustrating.

CHERI capabilities can be used to implement C language pointers, providing strict fine-grained spatial safety and pointer provenance guarantees (i.e. it's not just that pointers have bounds, you also can't go and synthesise a pointer with the bounds you want if you don't already have one for that region), plus heap temporal safety on an experimental branch. This is done using tagged memory, where every capability-sized word in memory has a single tag bit indicating whether it has a valid capability or not. This means that, although you can memcpy capabilities around, they must remain aligned, otherwise their tags will become cleared and no longer be dereferenceable.

So, for us, that line _has_ to be able to be written as auto Punned = *(uintptr_t *)Ptr; (although it can be written in equivalent ways), as byte swapping uintptr_t is not something we can ever support (though with endianness::native you could at least make the templated version specialised to not call swapByteOrder, though the one taking a function argument can't be, but why bother going through all that indirection), nor is storing pointers to unaligned addresses if you want to be able to use them as pointers later.

I know nothing about this recently(ish)-added Clang constexpr interpreter, but it seems like this should be a solvable problem with some changes to the design to be less lax about alignment. Is there any documentation you could provide on how CodePtr is meant to work? "Pointer into the code segment." isn't exactly helpful, especially given it's actually storing pointers, which is not what you normally find in code segments when talking instead about compiled code. Do you have ideas for how this problem can be avoided?

[1] http://cheri-cpu.org/
[2] https://developer.arm.com/architectures/cpu-architecture/a-profile/morello

cfe/trunk/lib/AST/Interp/Source.h

69 ↗

(On Diff #220064)

^^^ this line ^^^

[nand]

CodePtr points into the bytecode emitted by the byte code compiler. In some instances, pointers to auxiliary data structures are embedded into the byte code, such as functions or AST nodes which contain information relevant to the execution of the instruction.

Would it help if instead of encoding pointers, the byte code encoded some integers mapped to the original objects?

[jrtc27]

In D64146#2567710, @nand wrote:

CodePtr points into the bytecode emitted by the byte code compiler. In some instances, pointers to auxiliary data structures are embedded into the byte code, such as functions or AST nodes which contain information relevant to the execution of the instruction.

Would it help if instead of encoding pointers, the byte code encoded some integers mapped to the original objects?

I've read through the code and have slightly more understanding now. It seems there are several options:

1. Keep the pointers somewhere on the side and put an integer in the byte code, like you suggest

2. Pad values in the byte code to their natural alignment in general (and ensure the underlying std::vector<char> gets its storage allocated at an aligned boundary / use a different container), though this can get a little weird as the amount of padding between consecutive arguments varies depending on where you are (unless you force realignment to the max alignment at the start of a new opcode)

3. Make the byte code be an array of uintptr_t instead of packing it like is done currently, with care needed on ILP32; that can either just use uint64_t instead and we declare CHERI unsupported for 32-bit architectures (which is unlikely to be a problem as you probably want a 64-bit virtual address space if the doubling pointer size, with 64-bit CHERI capabilities on 32-bit VA systems being only for embedded use) or you can split 64-bit integers into two 32-bit integers and treat them as two arguments

1 works but feels ugly. 2 or 3 would be my preference, and mirror how "normal" interpreters work, though those might split the code and data so they can keep the opcodes as, say, 32-bit integers, but the stack full of native word/pointer slots; my inclination is that 3 is the best option as it looks like the simplest. How do you feel about each of those? Is memory overhead from not packing values a concern?

[jrtc27]

In D64146#2591732, @jrtc27 wrote:

In D64146#2567710, @nand wrote:

CodePtr points into the bytecode emitted by the byte code compiler. In some instances, pointers to auxiliary data structures are embedded into the byte code, such as functions or AST nodes which contain information relevant to the execution of the instruction.

Would it help if instead of encoding pointers, the byte code encoded some integers mapped to the original objects?

I've read through the code and have slightly more understanding now. It seems there are several options:

1. Keep the pointers somewhere on the side and put an integer in the byte code, like you suggest

2. Pad values in the byte code to their natural alignment in general (and ensure the underlying std::vector<char> gets its storage allocated at an aligned boundary / use a different container), though this can get a little weird as the amount of padding between consecutive arguments varies depending on where you are (unless you force realignment to the max alignment at the start of a new opcode)

3. Make the byte code be an array of uintptr_t instead of packing it like is done currently, with care needed on ILP32; that can either just use uint64_t instead and we declare CHERI unsupported for 32-bit architectures (which is unlikely to be a problem as you probably want a 64-bit virtual address space if the doubling pointer size, with 64-bit CHERI capabilities on 32-bit VA systems being only for embedded use) or you can split 64-bit integers into two 32-bit integers and treat them as two arguments

1 works but feels ugly. 2 or 3 would be my preference, and mirror how "normal" interpreters work, though those might split the code and data so they can keep the opcodes as, say, 32-bit integers, but the stack full of native word/pointer slots; my inclination is that 3 is the best option as it looks like the simplest. How do you feel about each of those? Is memory overhead from not packing values a concern?

Hm, though I see the "store an ID" pattern is common for dynamic things and this should be quite rare, so maybe that is indeed the right approach, mirroring something like getOrCreateGlobal?

[jrtc27]

In D64146#2591830, @jrtc27 wrote:

In D64146#2591732, @jrtc27 wrote:

In D64146#2567710, @nand wrote:

CodePtr points into the bytecode emitted by the byte code compiler. In some instances, pointers to auxiliary data structures are embedded into the byte code, such as functions or AST nodes which contain information relevant to the execution of the instruction.

Would it help if instead of encoding pointers, the byte code encoded some integers mapped to the original objects?

I've read through the code and have slightly more understanding now. It seems there are several options:

1. Keep the pointers somewhere on the side and put an integer in the byte code, like you suggest

2. Pad values in the byte code to their natural alignment in general (and ensure the underlying std::vector<char> gets its storage allocated at an aligned boundary / use a different container), though this can get a little weird as the amount of padding between consecutive arguments varies depending on where you are (unless you force realignment to the max alignment at the start of a new opcode)

3. Make the byte code be an array of uintptr_t instead of packing it like is done currently, with care needed on ILP32; that can either just use uint64_t instead and we declare CHERI unsupported for 32-bit architectures (which is unlikely to be a problem as you probably want a 64-bit virtual address space if the doubling pointer size, with 64-bit CHERI capabilities on 32-bit VA systems being only for embedded use) or you can split 64-bit integers into two 32-bit integers and treat them as two arguments

1 works but feels ugly. 2 or 3 would be my preference, and mirror how "normal" interpreters work, though those might split the code and data so they can keep the opcodes as, say, 32-bit integers, but the stack full of native word/pointer slots; my inclination is that 3 is the best option as it looks like the simplest. How do you feel about each of those? Is memory overhead from not packing values a concern?

Hm, though I see the "store an ID" pattern is common for dynamic things and this should be quite rare, so maybe that is indeed the right approach, mirroring something like getOrCreateGlobal?

https://reviews.llvm.org/D97606 implements this.

clang/include/clang/AST/ASTContext.h

 enum BuiltinTemplateKind : int;
 
 namespace comments {
 
 class FullComment;
 
 } // namespace comments
 
+namespace interp {
+
+class Context;
+
+} // namespace interp
+
 struct TypeInfo {
   uint64_t Width = 0;
   unsigned Align = 0;
   bool AlignIsRequired : 1;
 
   TypeInfo() : AlignIsRequired(false) {}
   TypeInfo(uint64_t Width, unsigned Align, bool AlignIsRequired)
       : Width(Width), Align(Align), AlignIsRequired(AlignIsRequired) {}
private:
 
   /// Address space map mangling must be used with language specific
   /// address spaces (e.g. OpenCL/CUDA)
   bool AddrSpaceMapMangling;
 
   const TargetInfo *Target = nullptr;
   const TargetInfo *AuxTarget = nullptr;
   clang::PrintingPolicy PrintingPolicy;
+  std::unique_ptr<interp::Context> InterpContext;
 
 public:
   IdentifierTable &Idents;
   SelectorTable &Selectors;
   Builtin::Context &BuiltinInfo;
   mutable DeclarationNameTable DeclarationNames;
   IntrusiveRefCntPtr<ExternalASTSource> ExternalSource;
   ASTMutationListener *Listener = nullptr;
 
+  /// Returns the clang bytecode interpreter context.
+  interp::Context &getInterpContext();
+
   /// Container for either a single DynTypedNode or for an ArrayRef to
   /// DynTypedNode. For use with ParentMap.
   class DynTypedNodeList {
     using DynTypedNode = ast_type_traits::DynTypedNode;
 
     llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode,
                                 ArrayRef<DynTypedNode>> Storage;
     bool IsSingleNode;

clang/include/clang/Basic/DiagnosticASTKinds.td

def note_constexpr_bit_cast_invalid_type : Note<
   "bit_cast %select{from|to}0 a %select{|type with a }1"
   "%select{union|pointer|member pointer|volatile|reference}2 "
   "%select{type|member}1 is not allowed in a constant expression">;
 def note_constexpr_bit_cast_invalid_subtype : Note<
   "invalid type %0 is a %select{member|base}1 of %2">;
 def note_constexpr_bit_cast_indet_dest : Note<
   "indeterminate value can only initialize an object of type 'unsigned char'"
   "%select{, 'char',|}1 or 'std::byte'; %0 is invalid">;
+def err_experimental_clang_interp_failed : Error<
+  "the experimental clang interpreter failed to evaluate an expression">;
 
 def warn_integer_constant_overflow : Warning<
   "overflow in expression; result is %0 with type %1">,
   InGroup<DiagGroup<"integer-overflow">>;
 
 // This is a temporary diagnostic, and shall be removed once our
 // implementation is complete, and like the preceding constexpr notes belongs
 // in Sema.
 def note_unimplemented_constexpr_lambda_feature_ast : Note<
     "unimplemented constexpr lambda feature: %0 (coming soon!)">;

clang/include/clang/Basic/LangOptions.def

 BENIGN_LANGOPT(ArrowDepth, 32, 256,
                "maximum number of operator->s to follow")
 BENIGN_LANGOPT(InstantiationDepth, 32, 1024,
                "maximum template instantiation depth")
 BENIGN_LANGOPT(ConstexprCallDepth, 32, 512,
                "maximum constexpr call depth")
 BENIGN_LANGOPT(ConstexprStepLimit, 32, 1048576,
                "maximum constexpr evaluation steps")
+BENIGN_LANGOPT(EnableClangInterp, 1, 0,
+               "enable the experimental clang interpreter")
+BENIGN_LANGOPT(ForceClangInterp, 1, 0,
+               "force the use of the experimental constexpr interpreter")
 BENIGN_LANGOPT(BracketDepth, 32, 256,
                "maximum bracket nesting depth")
 BENIGN_LANGOPT(NumLargeByValueCopy, 32, 0,
         "if non-zero, warn about parameter or return Warn if parameter/return value is larger in bytes than this setting. 0 is no check.")
 VALUE_LANGOPT(MSCompatibilityVersion, 32, 0, "Microsoft Visual C/C++ Version")
 VALUE_LANGOPT(VtorDispMode, 2, 1, "How many vtordisps to insert")
 
 LANGOPT(ApplePragmaPack, 1, 0, "Apple gcc-compatible #pragma pack handling")

clang/include/clang/Basic/OptionalDiagnostic.h

+//===- OptionalDiagnostic.h - An optional diagnostic ------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// Implements a partial diagnostic which may not be emitted.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_BASIC_OPTIONALDIAGNOSTIC_H
+#define LLVM_CLANG_BASIC_OPTIONALDIAGNOSTIC_H
+
+#include "clang/AST/APValue.h"
+#include "clang/Basic/PartialDiagnostic.h"
+#include "llvm/ADT/APFloat.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+
+/// A partial diagnostic which we might know in advance that we are not going
+/// to emit.
+class OptionalDiagnostic {
+  PartialDiagnostic *Diag;
+
+public:
+  explicit OptionalDiagnostic(PartialDiagnostic *Diag = nullptr) : Diag(Diag) {}
+
+  template <typename T> OptionalDiagnostic &operator<<(const T &v) {
+    if (Diag)
+      *Diag << v;
+    return *this;
+  }
+
+  OptionalDiagnostic &operator<<(const llvm::APSInt &I) {
+    if (Diag) {
+      SmallVector<char, 32> Buffer;
+      I.toString(Buffer);
+      *Diag << StringRef(Buffer.data(), Buffer.size());
+    }
+    return *this;
+  }
+
+  OptionalDiagnostic &operator<<(const llvm::APFloat &F) {
+    if (Diag) {
+      // FIXME: Force the precision of the source value down so we don't
+      // print digits which are usually useless (we don't really care here if
+      // we truncate a digit by accident in edge cases).  Ideally,
+      // APFloat::toString would automatically print the shortest
+      // representation which rounds to the correct value, but it's a bit
+      // tricky to implement. Could use std::to_chars.
+      unsigned precision = llvm::APFloat::semanticsPrecision(F.getSemantics());
+      precision = (precision * 59 + 195) / 196;
+      SmallVector<char, 32> Buffer;
+      F.toString(Buffer, precision);
+      *Diag << StringRef(Buffer.data(), Buffer.size());
+    }
+    return *this;
+  }
+
+  OptionalDiagnostic &operator<<(const APFixedPoint &FX) {
+    if (Diag) {
+      SmallVector<char, 32> Buffer;
+      FX.toString(Buffer);
+      *Diag << StringRef(Buffer.data(), Buffer.size());
+    }
+    return *this;
+  }
+};
+
+} // namespace clang
+
+#endif

clang/include/clang/Driver/Options.td

def fno_complete_member_pointers : Flag<["-"], "fno-complete-member-pointers">, Group<f_clang_Group>,
    Flags<[CoreOption]>,
    HelpText<"Do not require member pointer base types to be complete if they would be significant under the Microsoft ABI">;
 def fcf_runtime_abi_EQ : Joined<["-"], "fcf-runtime-abi=">, Group<f_Group>,
     Flags<[CC1Option]>;
 def fconstant_cfstrings : Flag<["-"], "fconstant-cfstrings">, Group<f_Group>;
 def fconstant_string_class_EQ : Joined<["-"], "fconstant-string-class=">, Group<f_Group>;
 def fconstexpr_depth_EQ : Joined<["-"], "fconstexpr-depth=">, Group<f_Group>;
 def fconstexpr_steps_EQ : Joined<["-"], "fconstexpr-steps=">, Group<f_Group>;
+def fexperimental_clang_interpreter : Flag<["-"], "fexperimental-clang-interpreter">, Group<f_Group>,
+  HelpText<"Enable the experimental clang interpreter">, Flags<[CC1Option]>;
+def fforce_experimental_clang_interpreter : Flag<["-"], "fforce-experimental-clang-interpreter">, Group<f_Group>,
+  HelpText<"Force the use of the experimental clang interpreter, failing on missing features">, Flags<[CC1Option]>;
 def fconstexpr_backtrace_limit_EQ : Joined<["-"], "fconstexpr-backtrace-limit=">,
                                     Group<f_Group>;
 def fno_crash_diagnostics : Flag<["-"], "fno-crash-diagnostics">, Group<f_clang_Group>, Flags<[NoArgumentUnused, CoreOption]>,
   HelpText<"Disable auto-generation of preprocessed source files and a script for reproduction during a clang crash">;
 def fcrash_diagnostics_dir : Joined<["-"], "fcrash-diagnostics-dir=">, Group<f_clang_Group>, Flags<[NoArgumentUnused, CoreOption]>;
 def fcreate_profile : Flag<["-"], "fcreate-profile">, Group<f_Group>;
 def fcxx_exceptions: Flag<["-"], "fcxx-exceptions">, Group<f_Group>,
   HelpText<"Enable C++ exceptions">, Flags<[CC1Option]>;

clang/lib/AST/ASTContext.cpp

 //===- ASTContext.cpp - Context to hold long-lived AST nodes --------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file implements the ASTContext interface.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTContext.h"
 #include "CXXABI.h"
+#include "Interp/Context.h"
 #include "clang/AST/APValue.h"
 #include "clang/AST/ASTMutationListener.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/AttrIterator.h"
 #include "clang/AST/CharUnits.h"
 #include "clang/AST/Comment.h"
 #include "clang/AST/Decl.h"
CXXABI *ASTContext::createCXXABI(const TargetInfo &T) {
   case TargetCXXABI::WebAssembly:
     return CreateItaniumCXXABI(*this);
   case TargetCXXABI::Microsoft:
     return CreateMicrosoftCXXABI(*this);
   }
   llvm_unreachable("Invalid CXXABI type!");
 }
 
+interp::Context &ASTContext::getInterpContext() {
+  if (!InterpContext) {
+    InterpContext.reset(new interp::Context(*this));
+  }
+  return *InterpContext.get();
+}
+
 static const LangASMap *getAddressSpaceMap(const TargetInfo &T,
                                            const LangOptions &LOpts) {
   if (LOpts.FakeAddressSpaceMap) {
     // The fake address space map must have a distinct entry for each
     // language-specific address space.
     static const unsigned FakeAddrSpaceMap[] = {
       0, // Default
       1, // opencl_global

clang/lib/AST/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   BinaryFormat
   Core
   Support
   )
 
+add_subdirectory(Interp)
+
 add_clang_library(clangAST
   APValue.cpp
   ASTConsumer.cpp
   ASTContext.cpp
   ASTDiagnostic.cpp
   ASTDumper.cpp
   ASTImporter.cpp
   ASTImporterLookupTable.cpp
add_clang_library(clangAST
   TextNodeDumper.cpp
   Type.cpp
   TypeLoc.cpp
   TypePrinter.cpp
   VTableBuilder.cpp
   VTTBuilder.cpp
 
   LINK_LIBS
+  clangInterp
   clangBasic
   clangLex
   )

clang/lib/AST/ExprConstant.cpp

 //
 // If we are checking for a potential constant expression, failure to constant
 // fold a potential constant sub-expression will be indicated by a 'false'
 // return value (the expression could not be folded) and no diagnostic (the
 // expression is not necessarily non-constant).
 //
 //===----------------------------------------------------------------------===//
 
+#include "Interp/Context.h"
+#include "Interp/Frame.h"
+#include "Interp/State.h"
 #include "clang/AST/APValue.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/ASTLambda.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/CharUnits.h"
 #include "clang/AST/CurrentSourceLocExprScope.h"
-#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/OSLog.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/FixedPoint.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallBitVector.h"
+#include "clang/Basic/OptionalDiagnostic.h"
+#include "clang/Basic/TargetInfo.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstring>
 #include <functional>
 
 #define DEBUG_TYPE "exprconstant"
 
 using namespace clang;
 using llvm::APInt;
 using llvm::APSInt;
 using llvm::APFloat;
 using llvm::Optional;
 
 static bool IsGlobalLValue(APValue::LValueBase B);
 
 namespace {
   struct LValue;
-  struct CallStackFrame;
-  struct EvalInfo;
+  class CallStackFrame;
+  class EvalInfo;
 
   using SourceLocExprScopeGuard =
       CurrentSourceLocExprScope::SourceLocExprScopeGuard;
 
   static QualType getType(APValue::LValueBase B) {
     if (!B) return QualType();
     if (const ValueDecl *D = B.dyn_cast<const ValueDecl*>()) {
       // FIXME: It's unclear where we're supposed to take the type from, and
for (unsigned I = 0, N = Path.size(); I != N; ++I) {
         // Path[I] describes a base class.
         ArraySize = 0;
         IsArray = false;
       }
     }
     return MostDerivedLength;
   }
 
-  // The order of this enum is important for diagnostics.
-  enum CheckSubobjectKind {
-    CSK_Base, CSK_Derived, CSK_Field, CSK_ArrayToPointer, CSK_ArrayIndex,
-    CSK_Real, CSK_Imag
-  };
-
   /// A path from a glvalue to a subobject of that glvalue.
   struct SubobjectDesignator {
     /// True if the subobject was named in a manner not supported by C++11. Such
     /// lvalues can still be folded, but they are not core constant expressions
     /// and we cannot perform lvalue-to-rvalue conversions on them.
     unsigned Invalid : 1;
 
     /// Is this a pointer one past the end of an object?
void adjustIndex(EvalInfo &Info, const Expr *E, APSInt N) {
       if (IsArray)
         Entries.back() = PathEntry::ArrayIndex(ArrayIndex);
       else
         IsOnePastTheEnd = (ArrayIndex != 0);
     }
   };
 
   /// A stack frame in the constexpr call stack.
-  struct CallStackFrame {
+  class CallStackFrame : public interp::Frame {
+  public:
     EvalInfo &Info;
 
     /// Parent - The caller of this stack frame.
     CallStackFrame *Caller;
 
     /// Callee - The function which was called.
     const FunctionDecl *Callee;
 
public:
     unsigned getCurrentTemporaryVersion(const void *Key) const {
       auto UB = Temporaries.upper_bound(MapKeyTy(Key, UINT_MAX));
       if (UB != Temporaries.begin() && std::prev(UB)->first.first == Key)
         return std::prev(UB)->first.second;
       return 0;
     }
 
     APValue &createTemporary(const void *Key, bool IsLifetimeExtended);
+
+    void describe(llvm::raw_ostream &OS) override;
+
+    Frame *getCaller() const override { return Caller; }
+    SourceLocation getCallLocation() const override { return CallLoc; }
+    const FunctionDecl *getCallee() const override { return Callee; }
   };
 
   /// Temporarily override 'this'.
   class ThisOverrideRAII {
   public:
     ThisOverrideRAII(CallStackFrame &Frame, const LValue *NewThis, bool Enable)
         : Frame(Frame), OldThis(Frame.This) {
       if (Enable)
         Frame.This = NewThis;
     }
     ~ThisOverrideRAII() {
       Frame.This = OldThis;
     }
   private:
     CallStackFrame &Frame;
     const LValue *OldThis;
   };
 
-  /// A partial diagnostic which we might know in advance that we are not going
-  /// to emit.
-  class OptionalDiagnostic {
-    PartialDiagnostic *Diag;
-
-  public:
-    explicit OptionalDiagnostic(PartialDiagnostic *Diag = nullptr)
-      : Diag(Diag) {}
-
-    template<typename T>
-    OptionalDiagnostic &operator<<(const T &v) {
-      if (Diag)
-        *Diag << v;
-      return *this;
-    }
-
-    OptionalDiagnostic &operator<<(const APSInt &I) {
-      if (Diag) {
-        SmallVector<char, 32> Buffer;
-        I.toString(Buffer);
-        *Diag << StringRef(Buffer.data(), Buffer.size());
-      }
-      return *this;
-    }
-
-    OptionalDiagnostic &operator<<(const APFloat &F) {
-      if (Diag) {
-        // FIXME: Force the precision of the source value down so we don't
-        // print digits which are usually useless (we don't really care here if
-        // we truncate a digit by accident in edge cases).  Ideally,
-        // APFloat::toString would automatically print the shortest
-        // representation which rounds to the correct value, but it's a bit
-        // tricky to implement.
-        unsigned precision =
-            llvm::APFloat::semanticsPrecision(F.getSemantics());
-        precision = (precision * 59 + 195) / 196;
-        SmallVector<char, 32> Buffer;
-        F.toString(Buffer, precision);
-        *Diag << StringRef(Buffer.data(), Buffer.size());
-      }
-      return *this;
-    }
-
-    OptionalDiagnostic &operator<<(const APFixedPoint &FX) {
-      if (Diag) {
-        SmallVector<char, 32> Buffer;
-        FX.toString(Buffer);
-        *Diag << StringRef(Buffer.data(), Buffer.size());
-      }
-      return *this;
-    }
-  };
-
   /// A cleanup, and a flag indicating whether it is lifetime-extended.
   class Cleanup {
     llvm::PointerIntPair<APValue*, 1, bool> Value;
 
   public:
     Cleanup(APValue *Val, bool IsLifetimeExtended)
         : Value(Val, IsLifetimeExtended) {}
 
namespace {
   /// "integer constant expression" or constant expression.  If not, this struct
   /// captures information about how and why not.
   ///
   /// One bit of information passed *into* the request for constant folding
   /// indicates whether the subexpression is "evaluated" or not according to C
   /// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
   /// evaluate the expression regardless of what the RHS is, but C only allows
   /// certain things in certain situations.
-  struct EvalInfo {
+  class EvalInfo : public interp::State {
+  public:
     ASTContext &Ctx;
 
     /// EvalStatus - Contains information about the evaluation.
     Expr::EvalStatus &EvalStatus;
 
     /// CurrentCall - The top of the constexpr call stack.
     CallStackFrame *CurrentCall;
 
     /// CallStackDepth - The number of calls in the call stack right now.
     unsigned CallStackDepth;
 
     /// NextCallIndex - The next call index to assign.
     unsigned NextCallIndex;
 
     /// StepsLeft - The remaining number of evaluation steps we're permitted
     /// to perform. This is essentially a limit for the number of statements
     /// we will evaluate.
     unsigned StepsLeft;
 
+    /// Force the use of the constexpr interpreter, bailing out with an error
+    /// if a feature is unsupported.
+    bool ForceClangInterp;
+
+    /// Enable the experimental clang interpreter.
+    bool EnableClangInterp;
+
     /// BottomFrame - The frame in which evaluation started. This must be
     /// initialized after CurrentCall and CallStackDepth.
     CallStackFrame BottomFrame;
 
     /// A stack of values whose lifetimes end at the end of some surrounding
     /// evaluation frame.
     llvm::SmallVector<Cleanup, 16> CleanupStack;
 
enum EvaluationMode {
       /// optimizer if we don't constant fold them here, but in an unevaluated
       /// context we try to fold them immediately since the optimizer never
       /// gets a chance to look at it.
       EM_PotentialConstantExpressionUnevaluated,
     } EvalMode;
 
     /// Are we checking whether the expression is a potential constant
     /// expression?
-    bool checkingPotentialConstantExpression() const {
+    bool checkingPotentialConstantExpression() const override {
       return EvalMode == EM_PotentialConstantExpression ||
              EvalMode == EM_PotentialConstantExpressionUnevaluated;
     }
 
     /// Are we checking an expression for overflow?
     // FIXME: We should check for any kind of undefined or suspicious behavior
     // in such constructs, not just overflow.
-    bool checkingForOverflow() { return EvalMode == EM_EvaluateForOverflow; }
+    bool checkingForOverflow() const override {
+      return EvalMode == EM_EvaluateForOverflow;
+    }
 
     EvalInfo(const ASTContext &C, Expr::EvalStatus &S, EvaluationMode Mode)
       : Ctx(const_cast<ASTContext &>(C)), EvalStatus(S), CurrentCall(nullptr),
         CallStackDepth(0), NextCallIndex(1),
         StepsLeft(getLangOpts().ConstexprStepLimit),
+        ForceClangInterp(getLangOpts().ForceClangInterp),
+        EnableClangInterp(ForceClangInterp || getLangOpts().EnableClangInterp),
         BottomFrame(*this, SourceLocation(), nullptr, nullptr, nullptr),
         EvaluatingDecl((const ValueDecl *)nullptr),
         EvaluatingDeclValue(nullptr), HasActiveDiagnostic(false),
         HasFoldFailureDiagnostic(false),
         InConstantContext(false), EvalMode(Mode) {}
 
     void setEvaluatingDecl(APValue::LValueBase Base, APValue &Value) {
       EvaluatingDecl = Base;
       EvaluatingDeclValue = &Value;
     }
 
-    const LangOptions &getLangOpts() const { return Ctx.getLangOpts(); }
-
     bool CheckCallLimit(SourceLocation Loc) {
       // Don't perform any constexpr calls (other than the call we're checking)
       // when checking a potential constant expression.
       if (checkingPotentialConstantExpression() && CallStackDepth > 1)
         return false;
       if (NextCallIndex == 0) {
         // NextCallIndex has wrapped around.
         FFDiag(Loc, diag::note_constexpr_call_limit_exceeded);
bool nextStep(const Stmt *S) {
         FFDiag(S->getBeginLoc(), diag::note_constexpr_step_limit_exceeded);
         return false;
       }
       --StepsLeft;
       return true;
     }
 
   private:
-    /// Add a diagnostic to the diagnostics list.
-    PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId) {
-      PartialDiagnostic PD(DiagId, Ctx.getDiagAllocator());
-      EvalStatus.Diag->push_back(std::make_pair(Loc, PD));
-      return EvalStatus.Diag->back().second;
+    interp::Frame *getCurrentFrame() override { return CurrentCall; }
+    const interp::Frame *getBottomFrame() const override { return &BottomFrame; }
+
+    bool hasActiveDiagnostic() override { return HasActiveDiagnostic; }
+    void setActiveDiagnostic(bool Flag) override { HasActiveDiagnostic = Flag; }
+
+    void setFoldFailureDiagnostic(bool Flag) override {
+      HasFoldFailureDiagnostic = Flag;
     }
 
-    /// Add notes containing a call stack to the current point of evaluation.
-    void addCallStack(unsigned Limit);
+    Expr::EvalStatus &getEvalStatus() const override { return EvalStatus; }
 
-  private:
-    OptionalDiagnostic Diag(SourceLocation Loc, diag::kind DiagId,
-                            unsigned ExtraNotes, bool IsCCEDiag) {
+    ASTContext &getCtx() const override { return Ctx; }
 
-      if (EvalStatus.Diag) {
-        // If we have a prior diagnostic, it will be noting that the expression
-        // isn't a constant expression. This diagnostic is more important,
-        // unless we require this evaluation to produce a constant expression.
-        //
-        // FIXME: We might want to show both diagnostics to the user in
-        // EM_ConstantFold mode.
-        if (!EvalStatus.Diag->empty()) {
-          switch (EvalMode) {
-          case EM_ConstantFold:
-          case EM_IgnoreSideEffects:
-          case EM_EvaluateForOverflow:
-            if (!HasFoldFailureDiagnostic)
-              break;
-            // We've already failed to fold something. Keep that diagnostic.
-            LLVM_FALLTHROUGH;
-          case EM_ConstantExpression:
-          case EM_PotentialConstantExpression:
-          case EM_ConstantExpressionUnevaluated:
-          case EM_PotentialConstantExpressionUnevaluated:
-            HasActiveDiagnostic = false;
-            return OptionalDiagnostic();
-          }
-        }
-
-        unsigned CallStackNotes = CallStackDepth - 1;
-        unsigned Limit = Ctx.getDiagnostics().getConstexprBacktraceLimit();
-        if (Limit)
-          CallStackNotes = std::min(CallStackNotes, Limit + 1);
-        if (checkingPotentialConstantExpression())
-          CallStackNotes = 0;
-
-        HasActiveDiagnostic = true;
-        HasFoldFailureDiagnostic = !IsCCEDiag;
-        EvalStatus.Diag->clear();
-        EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes);
-        addDiag(Loc, DiagId);
-        if (!checkingPotentialConstantExpression())
-          addCallStack(Limit);
-        return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second);
+    bool hasPriorDiagnostic() override {
+          setActiveDiagnostic(false);
+          return true;
         }
-      HasActiveDiagnostic = false;
-      return OptionalDiagnostic();
       }
-  public:
-    // Diagnose that the evaluation could not be folded (FF => FoldFailure)
-    OptionalDiagnostic
-    FFDiag(SourceLocation Loc,
-          diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
-          unsigned ExtraNotes = 0) {
-      return Diag(Loc, DiagId, ExtraNotes, false);
-    }
-
-    OptionalDiagnostic FFDiag(const Expr *E, diag::kind DiagId
-                              = diag::note_invalid_subexpr_in_const_expr,
-                            unsigned ExtraNotes = 0) {
-      if (EvalStatus.Diag)
-        return Diag(E->getExprLoc(), DiagId, ExtraNotes, /*IsCCEDiag*/false);
-      HasActiveDiagnostic = false;
-      return OptionalDiagnostic();
+      return false;
     }
 
-    /// Diagnose that the evaluation does not produce a C++11 core constant
-    /// expression.
-    ///
-    /// FIXME: Stop evaluating if we're in EM_ConstantExpression or
-    /// EM_PotentialConstantExpression mode and we produce one of these.
-    OptionalDiagnostic CCEDiag(SourceLocation Loc, diag::kind DiagId
-                                 = diag::note_invalid_subexpr_in_const_expr,
-                               unsigned ExtraNotes = 0) {
-      // Don't override a previous diagnostic. Don't bother collecting
-      // diagnostics if we're evaluating for overflow.
-      if (!EvalStatus.Diag || !EvalStatus.Diag->empty()) {
-        HasActiveDiagnostic = false;
-        return OptionalDiagnostic();
-      }
-      return Diag(Loc, DiagId, ExtraNotes, true);
-    }
-    OptionalDiagnostic CCEDiag(const Expr *E, diag::kind DiagId
-                                 = diag::note_invalid_subexpr_in_const_expr,
-                               unsigned ExtraNotes = 0) {
-      return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes);
-    }
-    /// Add a note to a prior diagnostic.
-    OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId) {
-      if (!HasActiveDiagnostic)
-        return OptionalDiagnostic();
-      return OptionalDiagnostic(&addDiag(Loc, DiagId));
-    }
-
-    /// Add a stack of notes to a prior diagnostic.
-    void addNotes(ArrayRef<PartialDiagnosticAt> Diags) {
-      if (HasActiveDiagnostic) {
-        EvalStatus.Diag->insert(EvalStatus.Diag->end(),
-                                Diags.begin(), Diags.end());
-      }
+    unsigned getCallStackDepth() override {
+      return CallStackDepth;
     }
 
+  public:
     /// Should we continue evaluation after encountering a side-effect that we
     /// couldn't model?
     bool keepEvaluatingAfterSideEffect() {
       switch (EvalMode) {
       case EM_PotentialConstantExpression:
       case EM_PotentialConstantExpressionUnevaluated:
       case EM_EvaluateForOverflow:
       case EM_IgnoreSideEffects:
bool keepEvaluatingAfterUndefinedBehavior() {
         return false;
       }
       llvm_unreachable("Missed EvalMode case");
     }
 
     /// Note that we hit something that was technically undefined behavior, but
     /// that we can evaluate past it (such as signed overflow or floating-point
     /// division by zero.)
-    bool noteUndefinedBehavior() {
+    bool noteUndefinedBehavior() override {
       EvalStatus.HasUndefinedBehavior = true;
       return keepEvaluatingAfterUndefinedBehavior();
     }
 
     /// Should we continue evaluation as much as possible after encountering a
     /// construct which can't be reduced to a value?
     bool keepEvaluatingAfterFailure() {
       if (!StepsLeft)
APValue &CallStackFrame::createTemporary(const void *Key,
                                          bool IsLifetimeExtended) {
   unsigned Version = Info.CurrentCall->getTempVersion();
   APValue &Result = Temporaries[MapKeyTy(Key, Version)];
   assert(Result.isAbsent() && "temporary created multiple times");
   Info.CleanupStack.push_back(Cleanup(&Result, IsLifetimeExtended));
   return Result;
 }
 
-static void describeCall(CallStackFrame *Frame, raw_ostream &Out);
-
-void EvalInfo::addCallStack(unsigned Limit) {
-  // Determine which calls to skip, if any.
-  unsigned ActiveCalls = CallStackDepth - 1;
-  unsigned SkipStart = ActiveCalls, SkipEnd = SkipStart;
-  if (Limit && Limit < ActiveCalls) {
-    SkipStart = Limit / 2 + Limit % 2;
-    SkipEnd = ActiveCalls - Limit / 2;
-  }
-
-  // Walk the call stack and add the diagnostics.
-  unsigned CallIdx = 0;
-  for (CallStackFrame *Frame = CurrentCall; Frame != &BottomFrame;
-       Frame = Frame->Caller, ++CallIdx) {
-    // Skip this call?
-    if (CallIdx >= SkipStart && CallIdx < SkipEnd) {
-      if (CallIdx == SkipStart) {
-        // Note that we're skipping calls.
-        addDiag(Frame->CallLoc, diag::note_constexpr_calls_suppressed)
-          << unsigned(ActiveCalls - Limit);
-      }
-      continue;
-    }
-
-    // Use a different note for an inheriting constructor, because from the
-    // user's perspective it's not really a function at all.
-    if (auto *CD = dyn_cast_or_null<CXXConstructorDecl>(Frame->Callee)) {
-      if (CD->isInheritingConstructor()) {
-        addDiag(Frame->CallLoc, diag::note_constexpr_inherited_ctor_call_here)
-          << CD->getParent();
-        continue;
-      }
-    }
-
-    SmallVector<char, 128> Buffer;
-    llvm::raw_svector_ostream Out(Buffer);
-    describeCall(Frame, Out);
-    addDiag(Frame->CallLoc, diag::note_constexpr_call_here) << Out.str();
-  }
-}
-
-/// Kinds of access we can perform on an object, for diagnostics. Note that
-/// we consider a member function call to be a kind of access, even though
-/// it is not formally an access of the object, because it has (largely) the
-/// same set of semantic restrictions.
-enum AccessKinds {
-  AK_Read,
-  AK_Assign,
-  AK_Increment,
-  AK_Decrement,
-  AK_MemberCall,
-  AK_DynamicCast,
-  AK_TypeId,
-};
-
 static bool isModification(AccessKinds AK) {
   switch (AK) {
   case AK_Read:
   case AK_MemberCall:
   case AK_DynamicCast:
   case AK_TypeId:
     return false;
   case AK_Assign:
static void negateAsSigned(APSInt &Int) {
   if (Int.isUnsigned() || Int.isMinSignedValue()) {
     Int = Int.extend(Int.getBitWidth() + 1);
     Int.setIsSigned(true);
   }
   Int = -Int;
 }
 
 /// Produce a string describing the given constexpr call.
-static void describeCall(CallStackFrame *Frame, raw_ostream &Out) {
+void CallStackFrame::describe(raw_ostream &Out) {
   unsigned ArgIndex = 0;
-  bool IsMemberCall = isa<CXXMethodDecl>(Frame->Callee) &&
-                      !isa<CXXConstructorDecl>(Frame->Callee) &&
-                      cast<CXXMethodDecl>(Frame->Callee)->isInstance();
+  bool IsMemberCall = isa<CXXMethodDecl>(Callee) &&
+                      !isa<CXXConstructorDecl>(Callee) &&
+                      cast<CXXMethodDecl>(Callee)->isInstance();
 
   if (!IsMemberCall)
-    Out << *Frame->Callee << '(';
+    Out << *Callee << '(';
 
-  if (Frame->This && IsMemberCall) {
+  if (This && IsMemberCall) {
     APValue Val;
-    Frame->This->moveInto(Val);
-    Val.printPretty(Out, Frame->Info.Ctx,
-                    Frame->This->Designator.MostDerivedType);
+    This->moveInto(Val);
+    Val.printPretty(Out, Info.Ctx,
+                    This->Designator.MostDerivedType);
     // FIXME: Add parens around Val if needed.
-    Out << "->" << *Frame->Callee << '(';
+    Out << "->" << *Callee << '(';
     IsMemberCall = false;
   }
 
-  for (FunctionDecl::param_const_iterator I = Frame->Callee->param_begin(),
-       E = Frame->Callee->param_end(); I != E; ++I, ++ArgIndex) {
+  for (FunctionDecl::param_const_iterator I = Callee->param_begin(),
+       E = Callee->param_end(); I != E; ++I, ++ArgIndex) {
     if (ArgIndex > (unsigned)IsMemberCall)
       Out << ", ";
 
     const ParmVarDecl *Param = *I;
-    const APValue &Arg = Frame->Arguments[ArgIndex];
-    Arg.printPretty(Out, Frame->Info.Ctx, Param->getType());
+    const APValue &Arg = Arguments[ArgIndex];
+    Arg.printPretty(Out, Info.Ctx, Param->getType());
 
     if (ArgIndex == 0 && IsMemberCall)
-      Out << "->" << *Frame->Callee << '(';
+      Out << "->" << *Callee << '(';
   }
 
   Out << ')';
 }
 
 /// Evaluate an expression to see if it had side-effects, and discard its
 /// result.
 /// \return \c true if the caller should keep evaluating.
if (MD && MD->isDefaulted() &&
     // we're inferring constexpr-ness), so we don't have access to them in this
     // case. But since we don't need the captures to constexpr check, we can
     // just ignore them.
     if (!Info.checkingPotentialConstantExpression())
       MD->getParent()->getCaptureFields(Frame.LambdaCaptureFields,
                                         Frame.LambdaThisCaptureField);
   }
 
+  // Try to evaluate the function call in the bytecode VM.
+  if (Info.EnableClangInterp) {
+    auto &InterpCtx = Info.Ctx.getInterpContext();
+    switch (InterpCtx.handleFunctionCall(Info, Callee, ArgValues, Result)) {
+    case interp::InterpResult::Success:
+      return true;
+    case interp::InterpResult::Fail:
+      return false;
+    case interp::InterpResult::Bail:
+      break;
+    }
+  }
+
   StmtResult Ret = {Result, ResultSlot};
   EvalStmtResult ESR = EvaluateStmt(Ret, Info, Body);
   if (ESR == ESR_Succeeded) {
     if (Callee->getReturnType()->isVoidType())
       return true;
     Info.FFDiag(Callee->getEndLoc(), diag::note_constexpr_no_return);
   }
   return ESR == ESR_Returned;
static bool EvaluateInPlace(APValue &Result, EvalInfo &Info, const LValue &This,
 
   // For any other type, in-place evaluation is unimportant.
   return Evaluate(Result, Info, E);
 }
 
 /// EvaluateAsRValue - Try to evaluate this expression, performing an implicit
 /// lvalue-to-rvalue cast if it is an lvalue.
 static bool EvaluateAsRValue(EvalInfo &Info, const Expr *E, APValue &Result) {
+   if (Info.EnableClangInterp) {
+    auto &InterpCtx = Info.Ctx.getInterpContext();
+    switch (InterpCtx.evaluateAsRValue(Info, E, Result)) {
+    case interp::InterpResult::Success:
+      return true;
+    case interp::InterpResult::Fail:
+      return false;
+    case interp::InterpResult::Bail:
+      break;
+    }
+  }
+
   if (E->getType().isNull())
     return false;
 
   if (!CheckLiteralType(Info, E))
     return false;
 
   if (!::Evaluate(Result, Info, E))
     return false;
bool Expr::EvaluateAsInitializer(APValue &Value, const ASTContext &Ctx,
   // performance problems. Only do so in C++11 for now.
   if (isRValue() && (getType()->isArrayType() || getType()->isRecordType()) &&
       !Ctx.getLangOpts().CPlusPlus11)
     return false;
 
   Expr::EvalStatus EStatus;
   EStatus.Diag = &Notes;
 
-  EvalInfo InitInfo(Ctx, EStatus, VD->isConstexpr()
+  EvalInfo Info(Ctx, EStatus, VD->isConstexpr()
                                       ? EvalInfo::EM_ConstantExpression
                                       : EvalInfo::EM_ConstantFold);
-  InitInfo.setEvaluatingDecl(VD, Value);
-  InitInfo.InConstantContext = true;
+  Info.setEvaluatingDecl(VD, Value);
+  Info.InConstantContext = true;
+
+  if (Info.EnableClangInterp) {
+    auto &InterpCtx = const_cast<ASTContext &>(Ctx).getInterpContext();
+    switch (InterpCtx.evaluateAsInitializer(Info, VD, Value)) {
+    case interp::InterpResult::Fail:
+      // Bail out if an error was encountered.
+      return false;
+    case interp::InterpResult::Success:
+      // If the interpreter is forced, do not compute any other value.
+      if (Info.ForceClangInterp)
+        return true;
+      break;
+    case interp::InterpResult::Bail:
+      // Evaluate the value again for the tree evaluator to use.
+      break;
+    }
+  }
 
   LValue LVal;
   LVal.set(VD);
 
   // C++11 [basic.start.init]p2:
   //  Variables with static storage duration or thread storage duration shall be
   //  zero-initialized before any other initialization takes place.
   // This behavior is not present in C.
   if (Ctx.getLangOpts().CPlusPlus && !VD->hasLocalStorage() &&
       !VD->getType()->isReferenceType()) {
     ImplicitValueInitExpr VIE(VD->getType());
-    if (!EvaluateInPlace(Value, InitInfo, LVal, &VIE,
+    if (!EvaluateInPlace(Value, Info, LVal, &VIE,
                          /*AllowNonLiteralTypes=*/true))
       return false;
   }
 
-  if (!EvaluateInPlace(Value, InitInfo, LVal, this,
+  if (!EvaluateInPlace(Value, Info, LVal, this,
                        /*AllowNonLiteralTypes=*/true) ||
       EStatus.HasSideEffects)
     return false;
 
-  return CheckConstantExpression(InitInfo, VD->getLocation(), VD->getType(),
-                                 Value);
+  return CheckConstantExpression(Info, VD->getLocation(), VD->getType(), Value);
 }
 
 /// isEvaluatable - Call EvaluateAsRValue to see if this expression can be
 /// constant folded, but discard the result.
 bool Expr::isEvaluatable(const ASTContext &Ctx, SideEffectsKind SEK) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
bool Expr::isPotentialConstantExpr(const FunctionDecl *FD,
 
   Expr::EvalStatus Status;
   Status.Diag = &Diags;
 
   EvalInfo Info(FD->getASTContext(), Status,
                 EvalInfo::EM_PotentialConstantExpression);
   Info.InConstantContext = true;
 
+  // The constexpr VM attempts to compile all methods to bytecode here.
+  if (Info.EnableClangInterp) {
+    auto &InterpCtx = Info.Ctx.getInterpContext();
+    switch (InterpCtx.isPotentialConstantExpr(Info, FD)) {
+    case interp::InterpResult::Success:
+    case interp::InterpResult::Fail:
+      return Diags.empty();
+    case interp::InterpResult::Bail:
+      break;
+    }
+  }
+
   const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(FD);
   const CXXRecordDecl *RD = MD ? MD->getParent()->getCanonicalDecl() : nullptr;
 
   // Fabricate an arbitrary expression on the stack and pretend that it
   // is a temporary being used as the 'this' pointer.
   LValue This;
   ImplicitValueInitExpr VIE(RD ? Info.Ctx.getRecordType(RD) : Info.Ctx.IntTy);
   This.set({&VIE, Info.CurrentCall->Index});

clang/lib/AST/Interp/ByteCodeGen.h

+//===--- ByteCodeGen.h - Code Generator for the constexpr VM -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the constexpr bytecode compiler.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_BYTECODEGEN_H
+#define LLVM_CLANG_AST_INTERP_BYTECODEGEN_H
+
+#include "EvalEmitter.h"
+#include "LinkEmitter.h"
+#include "Pointer.h"
+#include "Type.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/StmtVisitor.h"
+#include "llvm/ADT/Optional.h"
+
+namespace clang {
+class QualType;
+
+namespace interp {
+class Function;
+class State;
+
+template <class Emitter> class LocalScope;
+template <class Emitter> class LoopScope;
+template <class Emitter> class SwitchScope;
+template <class Emitter> class RecordScope;
+template <class Emitter> class CompilerScope;
+
+/// Compilation context for a constexpr function.
+template <class Emitter>
+class ByteCodeGen : public ConstStmtVisitor<ByteCodeGen<Emitter>, bool>,
+                 public Emitter {
+  using NullaryFn = bool (ByteCodeGen::*)(const SourceInfo &);
+  using UnaryFn = bool (ByteCodeGen::*)(PrimType, const SourceInfo &);
+  using BinaryFn = bool (ByteCodeGen::*)(PrimType, PrimType, const SourceInfo &);
+
+  using LabelTy = typename Emitter::LabelTy;
+  using OptLabelTy = llvm::Optional<LabelTy>;
+  using CaseMap = llvm::DenseMap<const SwitchCase *, LabelTy>;
+
+  using AddrTy = typename Emitter::AddrTy;
+
+  /// Current compilation context.
+  Context &Ctx;
+  /// Evaluation state.
+  State &S;
+  /// Program to link to.
+  Program &P;
+
+public:
+  /// Initializes the compiler and the backend emitter.
+  template <typename... Tys>
+  ByteCodeGen(Context &Ctx, State &S, Program &P, Tys &&... Args)
+      : Emitter(Ctx, S, P, Args...), Ctx(Ctx), S(S), P(P) {}
+
+  // Expression visitors - result returned on stack.
+  bool VisitDeclRefExpr(const DeclRefExpr *E);
+  bool VisitCastExpr(const CastExpr *CE);
+  bool VisitIntegerLiteral(const IntegerLiteral *E);
+  bool VisitParenExpr(const ParenExpr *PE);
+  bool VisitBinaryOperator(const BinaryOperator *BO);
+
+  // If an unsupported construct is encountered, no code is generated.
+  bool VisitExpr(const Expr *E) { return this->bail(E); }
+  bool VisitStmt(const Stmt *S) { llvm_unreachable("not compiled"); }
+
+private:
+  // Statement visitors.
+  bool visit(const Stmt *S);
+  bool visitCompoundStmt(const CompoundStmt *S);
+  bool visitDeclStmt(const DeclStmt *DS);
+  bool visitReturnStmt(const ReturnStmt *RS);
+  bool visitIfStmt(const IfStmt *IS);
+
+  /// Evaluates an expr for side effects and discards the result.
+  bool discard(const Expr *E);
+  bool discardBinaryOperator(const BinaryOperator *BO);
+
+  enum class AccessKind {
+    /// Value is read and pushed to stack.
+    Read,
+    /// Direct method generates a value which is written. Returns pointer.
+    Write,
+    /// Direct method generates a value which is written.
+    WriteVoid,
+    /// Direct method receives the value, pushes mutated value. Returns pointer.
+    ReadWrite,
+    /// Direct method receives the value, pushes mutated copy.
+    ReadWriteVoid
+  };
+
+  /// Method to directly load a value. If the value can be fetched directly,
+  /// the direct handler is called. Otherwise, a pointer is left on the stack
+  /// and the indirect handler is expected to operate on that.
+  bool dereference(const Expr *LValue, AccessKind AK,
+                   llvm::function_ref<bool(PrimType)> Direct,
+                   llvm::function_ref<bool(PrimType)> Indirect);
+
+  /// Compiles a variable declaration.
+  bool visitVarDecl(const VarDecl *VD);
+
+protected:
+  virtual bool compile(const FunctionDecl *F) override;
+  virtual bool compile(const Expr *E) override;
+  virtual bool compile(const VarDecl *VD) override;
+
+private:
+  friend class CompilerScope<Emitter>;
+  friend class LocalScope<Emitter>;
+  friend class RecordScope<Emitter>;
+  friend class LoopScope<Emitter>;
+  friend class SwitchScope<Emitter>;
+
+  /// Returns the size int bits of an integer.
+  unsigned getIntWidth(QualType Ty) {
+    auto &ASTContext = Ctx.getASTContext();
+    return ASTContext.getIntWidth(Ty);
+  }
+
+  /// Emits an APInt constant.
+  bool emitConst(PrimType T, unsigned NumBits, const llvm::APInt &Value,
+                 const Expr *E);
+
+  /// Emits an integer constant.
+  template<typename T>
+  bool emitConst(const Expr *E, T Value) {
+    QualType Ty = E->getType();
+    unsigned NumBits = getIntWidth(Ty);
+    APInt WrappedValue(NumBits, Value, std::is_signed<T>::value);
+    return emitConst(*Ctx.classify(Ty), NumBits, WrappedValue, E);
+  }
+
+  /// Creates a local primitive value.
+  unsigned allocateLocalPrimitive(DeclTy &&Decl, PrimType Ty, bool IsMutable,
+                                  bool IsExtended = false);
+
+  /// Compiles an argument.
+  bool visitArgument(const Expr *E);
+
+  /// Returns or compiles a function.
+  Function *getFunction(const FunctionDecl *FD);
+
+  /// Variable to storage mapping.
+  llvm::DenseMap<const ValueDecl *, Scope::Local> Locals;
+
+  /// Current scope.
+  CompilerScope<Emitter> *Top = nullptr;
+};
+
+extern template class ByteCodeGen<LinkEmitter>;
+extern template class ByteCodeGen<EvalEmitter>;
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/ByteCodeGen.cpp

+//===--- ByteCodeGen.cpp - Code Generator for the constexpr VM -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ByteCodeGen.h"
+#include "ByteCodeGenError.h"
+#include "Context.h"
+#include "EvalEmitter.h"
+#include "Function.h"
+#include "LinkEmitter.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "State.h"
+#include "Type.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+using APSInt = llvm::APSInt;
+using Error = llvm::Error;
+
+namespace clang {
+namespace interp {
+
+/// Scope chain managing the compiler state.
+///
+/// Classes deriving from this override certain parts of the compiler
+/// state to deal with block scopes, break/continue labels and cases.
+template <class Emitter> class CompilerScope {
+public:
+  virtual ~CompilerScope() { Ctx->Top = this->Parent; }
+
+  void add(const Scope::Local &Local, bool IsExtended) {
+    if (IsExtended)
+      this->addExtended(Local);
+    else
+      this->addLocal(Local);
+  }
+
+  virtual void addLocal(const Scope::Local &Local) {
+    if (this->Parent)
+      this->Parent->addLocal(Local);
+  }
+
+  virtual void addExtended(const Scope::Local &Local) {
+    if (this->Parent)
+      this->Parent->addExtended(Local);
+  }
+
+  virtual void emitDestructor() {}
+
+  CompilerScope *getParent() { return Parent; }
+
+protected:
+  CompilerScope(ByteCodeGen<Emitter> *Ctx) : Ctx(Ctx), Parent(Ctx->Top) {
+    Ctx->Top = this;
+  }
+
+  /// ByteCodeGen instance.
+  ByteCodeGen<Emitter> *Ctx;
+  /// Link to the parent scope.
+  CompilerScope *Parent;
+};
+
+/// Scope for local variables.
+///
+/// When the scope is destroyed, instructions are emitted to tear down
+/// all variables declared in this scope.
+template <class Emitter> class LocalScope : public CompilerScope<Emitter> {
+public:
+  LocalScope(ByteCodeGen<Emitter> *Ctx) : CompilerScope<Emitter>(Ctx) {}
+
+  ~LocalScope() override { this->emitDestructor(); }
+
+  void addLocal(const Scope::Local &Local) override {
+    if (!Idx.hasValue()) {
+      Idx = this->Ctx->Descriptors.size();
+      this->Ctx->Descriptors.emplace_back();
+    }
+
+    this->Ctx->Descriptors[*Idx].emplace_back(Local);
+  }
+
+  void emitDestructor() override {
+    if (!Idx.hasValue())
+      return;
+    this->Ctx->emitDestroy(*Idx, {});
+  }
+
+protected:
+  /// Index of the scope in the chain.
+  llvm::Optional<unsigned> Idx;
+};
+
+template <class Emitter> class BlockScope final : public LocalScope<Emitter> {
+public:
+  BlockScope(ByteCodeGen<Emitter> *Ctx) : LocalScope<Emitter>(Ctx) {}
+
+  void addExtended(const Scope::Local &Local) override {
+    llvm_unreachable("Cannot create temporaries in full scopes");
+  }
+};
+
+/// Expression scope which tracks potentially lifetime extended
+/// temporaries which are hoisted to the parent scope on exit.
+template <class Emitter> class ExprScope final : public LocalScope<Emitter> {
+public:
+  ExprScope(ByteCodeGen<Emitter> *Ctx) : LocalScope<Emitter>(Ctx) {}
+
+  void addExtended(const Scope::Local &Local) override {
+    this->Parent->addLocal(Local);
+  }
+};
+
+/// Scope used for toplevel declarators.
+template <class Emitter> class DeclScope final : public LocalScope<Emitter> {
+public:
+  DeclScope(ByteCodeGen<Emitter> *Ctx) : LocalScope<Emitter>(Ctx) {}
+
+  void addExtended(const Scope::Local &Local) override {
+    return this->addLocal(Local);
+  }
+};
+
+} // namespace interp
+} // namespace clang
+
+template <class Emitter> bool ByteCodeGen<Emitter>::visit(const Stmt *S) {
+  switch (S->getStmtClass()) {
+  case Stmt::CompoundStmtClass:
+    return visitCompoundStmt(cast<CompoundStmt>(S));
+  case Stmt::DeclStmtClass:
+    return visitDeclStmt(cast<DeclStmt>(S));
+  case Stmt::ReturnStmtClass:
+    return visitReturnStmt(cast<ReturnStmt>(S));
+  case Stmt::IfStmtClass:
+    return visitIfStmt(cast<IfStmt>(S));
+  case Stmt::NullStmtClass:
+    return true;
+  default: {
+    if (auto *Exp = dyn_cast<Expr>(S)) {
+      if (Exp->getType()->isVoidType()) {
+        return this->Visit(Exp);
+      } else {
+        return discard(Exp);
+      }
+    } else {
+      return this->bail(S);
+    }
+  }
+  }
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::visitCompoundStmt(const CompoundStmt *S) {
+  BlockScope<Emitter> Scope(this);
+  for (auto *Stmt : S->body())
+    if (!visit(Stmt))
+      return false;
+  return true;
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::visitDeclStmt(const DeclStmt *DS) {
+  for (auto *D : DS->decls()) {
+    // Variable declarator.
+    if (auto *VD = dyn_cast<VarDecl>(D)) {
+      if (!visitVarDecl(VD))
+        return false;
+      continue;
+    }
+
+    // TODO: implement other declarations.
+    return this->bail(DS);
+  }
+
+  return true;
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::visitReturnStmt(const ReturnStmt *RS) {
+  if (auto *RetExpr = RS->getRetValue()) {
+    ExprScope<Emitter> RetScope(this);
+    QualType RT = RetExpr->getType();
+    if (Ctx.isComposite(RT)) {
+      // RVO - construct the value in the return location.
+      return this->bail(RS);
+    } else {
+      // Primitive types are simply returned.
+      if (auto T = Ctx.classify(RetExpr)) {
+        if (!this->Visit(RetExpr))
+          return false;
+        for (auto *C = Top; C; C = C->getParent())
+          C->emitDestructor();
+        if (!this->emitRet(*T, RS))
+          return false;
+        return true;
+      }
+    }
+    return this->bail(RS);
+  } else {
+    for (auto *C = Top; C; C = C->getParent())
+      C->emitDestructor();
+    if (!this->emitRetVoid(RS))
+      return false;
+    return true;
+  }
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::visitIfStmt(const IfStmt *IS) {
+  BlockScope<Emitter> IfScope(this);
+  if (auto *CondInit = IS->getInit())
+    if (!visit(IS->getInit()))
+      return false;
+
+  if (auto *CondDecl = IS->getConditionVariableDeclStmt())
+    if (!visitDeclStmt(CondDecl))
+      return false;
+
+  if (!this->Visit(IS->getCond()))
+    return false;
+
+  if (auto *Else = IS->getElse()) {
+    auto LabelElse = this->getLabel();
+    auto LabelEnd = this->getLabel();
+    if (!this->jumpFalse(LabelElse))
+      return false;
+    if (!visit(IS->getThen()))
+      return false;
+    if (!this->jump(LabelEnd))
+      return false;
+    this->emitLabel(LabelElse);
+    if (!visit(Else))
+      return false;
+    this->emitLabel(LabelEnd);
+  } else {
+    auto LabelEnd = this->getLabel();
+    if (!this->jumpFalse(LabelEnd))
+      return false;
+    if (!visit(IS->getThen()))
+      return false;
+    this->emitLabel(LabelEnd);
+  }
+
+  return true;
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::VisitDeclRefExpr(const DeclRefExpr *DE) {
+  if (auto *PD = dyn_cast<ParmVarDecl>(DE->getDecl())) {
+    auto It = this->Params.find(PD);
+    if (It == this->Params.end()) {
+      return this->emitUndef(DE);
+    } else {
+      QualType Ty = PD->getType();
+      if (Ty->isReferenceType() || Ctx.isComposite(Ty))
+        return this->emitGetParamPtr(It->second, DE);
+      else
+        return this->emitGetPtrParam(It->second, DE);
+    }
+  }
+  if (auto *VD = dyn_cast<VarDecl>(DE->getDecl())) {
+    if (!VD->hasLocalStorage()) {
+      return this->bail(DE);
+    }
+
+    auto It = Locals.find(VD);
+    if (It == Locals.end()) {
+      return this->emitUndef(DE);
+    } else {
+      if (VD->getType()->isReferenceType())
+        return this->emitGetLocal(PT_Ptr, It->second.Offset, DE);
+      else
+        return this->emitGetPtrLocal(It->second.Offset, DE);
+    }
+  }
+  if (auto *ED = dyn_cast<EnumConstantDecl>(DE->getDecl())) {
+    QualType Ty = ED->getType();
+    if (auto T = Ctx.classify(Ty))
+      return this->emitConst(*T, getIntWidth(Ty), ED->getInitVal(), DE);
+    return this->bail(DE);
+  }
+  // TODO: compile other decls.
+  return this->bail(DE);
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::VisitCastExpr(const CastExpr *CE) {
+  auto *SubExpr = CE->getSubExpr();
+  switch (CE->getCastKind()) {
+
+  case CK_LValueToRValue: {
+    return dereference(
+        CE->getSubExpr(), AccessKind::Read,
+        [](PrimType) {
+          // Value loaded - nothing to do here.
+          return true;
+        },
+        [this, CE](PrimType T) {
+          // Pointer on stack - dereference it.
+          return this->emitLoadPop(T, CE);
+        });
+  }
+
+  case CK_NoOp: {
+    return this->Visit(SubExpr);
+  }
+
+  default: {
+    // TODO: implement other casts.
+    return this->bail(CE);
+  }
+  }
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::VisitIntegerLiteral(const IntegerLiteral *LE) {
+  auto Val = LE->getValue();
+
+  QualType LitTy = LE->getType();
+  if (auto T = Ctx.classify(LitTy))
+    return emitConst(*T, getIntWidth(LitTy), LE->getValue(), LE);
+  return this->bail(LE);
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::VisitParenExpr(const ParenExpr *PE) {
+  return this->Visit(PE->getSubExpr());
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::VisitBinaryOperator(const BinaryOperator *BO) {
+  // Typecheck the args.
+  auto *LHS = BO->getLHS();
+  auto TypeLHS = Ctx.classify(LHS->getType());
+  if (!TypeLHS) {
+    return this->bail(BO);
+  }
+  auto *RHS = BO->getRHS();
+  auto TypeRHS = Ctx.classify(RHS->getType());
+  if (!TypeRHS) {
+    return this->bail(BO);
+  }
+
+  if (auto T = Ctx.classify(BO->getType())) {
+    switch (BO->getOpcode()) {
+    case BO_LAnd: {
+      if (!this->Visit(LHS))
+        return false;
+      auto Short = this->getLabel();
+      if (!this->emitDup(*TypeLHS, BO))
+        return false;
+      if (!this->jumpFalse(Short))
+        return false;
+      if (!this->emitPop(*TypeLHS, BO))
+        return false;
+      if (!this->Visit(RHS))
+        return false;
+      this->emitLabel(Short);
+      return true;
+    }
+    case BO_LOr: {
+      if (!this->Visit(LHS))
+        return false;
+      auto Short = this->getLabel();
+      if (!this->emitDup(*TypeLHS, BO))
+        return false;
+      if (!this->jumpTrue(Short))
+        return false;
+      if (!this->emitPop(*TypeLHS, BO))
+        return false;
+      if (!this->Visit(RHS))
+        return false;
+      this->emitLabel(Short);
+      return true;
+    }
+
+    case BO_Comma: {
+      if (!discard(LHS))
+        return false;
+      if (!this->Visit(RHS))
+        return false;
+      return true;
+    }
+
+    default:
+      break;
+    }
+
+    if (!this->Visit(LHS))
+      return false;
+    if (!this->Visit(RHS))
+      return false;
+
+    switch (BO->getOpcode()) {
+    case BO_EQ:
+      return this->emitEQ(*TypeLHS, BO);
+    case BO_NE:
+      return this->emitNE(*TypeLHS, BO);
+    case BO_LT:
+      return this->emitLT(*TypeLHS, BO);
+    case BO_LE:
+      return this->emitLE(*TypeLHS, BO);
+    case BO_GT:
+      return this->emitGT(*TypeLHS, BO);
+    case BO_GE:
+      return this->emitGE(*TypeLHS, BO);
+    case BO_Rem:
+      return this->emitRem(*T, BO);
+    case BO_Div:
+      return this->emitDiv(*T, BO);
+    case BO_Sub:
+      return this->emitSub(*T, BO);
+    case BO_Add:
+      return this->emitAdd(*T, BO);
+    case BO_Mul:
+      return this->emitMul(*T, BO);
+    default:
+      return this->bail(BO);
+    }
+  }
+
+  return this->bail(BO);
+}
+
+template <class Emitter> bool ByteCodeGen<Emitter>::discard(const Expr *DE) {
+  switch (DE->getStmtClass()) {
+  case Stmt::BinaryOperatorClass:
+    return discardBinaryOperator(static_cast<const BinaryOperator *>(DE));
+  default:
+    if (!this->Visit(DE))
+      return false;
+    if (auto T = Ctx.classify(DE))
+      return this->emitPop(*T, DE);
+    break;
+  }
+
+  return this->bail(DE);
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::discardBinaryOperator(const BinaryOperator *BO) {
+  // Typecheck the args.
+  auto *LHS = BO->getLHS();
+  auto TypeLHS = Ctx.classify(LHS->getType());
+  if (!TypeLHS) {
+    return this->bail(BO);
+  }
+  auto *RHS = BO->getRHS();
+  auto TypeRHS = Ctx.classify(RHS->getType());
+  if (!TypeRHS) {
+    return this->bail(BO);
+  }
+
+  // Peephole optimisations.
+  if (auto T = Ctx.classify(BO->getType())) {
+    // Handle operations with mixed types.
+    switch (BO->getOpcode()) {
+    case BO_Comma:
+      if (!discard(LHS))
+        return false;
+      if (!discard(RHS))
+        return false;
+      return true;
+    default:
+      break;
+    }
+
+    if (!this->Visit(BO))
+      return false;
+    return this->emitPop(*T, BO);
+  } else {
+    return this->bail(BO);
+  }
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::dereference(
+    const Expr *LV, AccessKind AK, llvm::function_ref<bool(PrimType)> Direct,
+    llvm::function_ref<bool(PrimType)> Indirect) {
+  auto T = Ctx.classify(LV->getType());
+  if (!T)
+    return this->bail(LV);
+
+  if (auto *DE = dyn_cast<DeclRefExpr>(LV)) {
+    if (!DE->getDecl()->getType()->isReferenceType()) {
+      if (auto *PD = dyn_cast<ParmVarDecl>(DE->getDecl())) {
+        auto It = this->Params.find(PD);
+        if (It != this->Params.end()) {
+          unsigned Idx = It->second;
+          switch (AK) {
+          case AccessKind::Read:
+            if (!this->emitGetParam(*T, Idx, LV))
+              return false;
+            break;
+          case AccessKind::Write:
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetParam(*T, Idx, LV))
+              return false;
+            if (!this->emitGetPtrParam(Idx, LV))
+              return false;
+            break;
+          case AccessKind::WriteVoid:
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetParam(*T, Idx, LV))
+              return false;
+            break;
+          case AccessKind::ReadWrite:
+            if (!this->emitGetParam(*T, Idx, LV))
+              return false;
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetParam(*T, Idx, LV))
+              return false;
+            if (!this->emitGetPtrParam(Idx, LV))
+              return false;
+            break;
+          case AccessKind::ReadWriteVoid:
+            if (!this->emitGetParam(*T, Idx, LV))
+              return false;
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetParam(*T, Idx, LV))
+              return false;
+            break;
+          }
+          return true;
+        } else {
+          // If the param is a pointer, we can dereference a dummy value.
+          if (PD->getType()->hasPointerRepresentation()) {
+            if (AK == AccessKind::Read) {
+              if (!this->emitUndef(LV))
+                return false;
+              return Direct(*T);
+            }
+          }
+        }
+      }
+      if (auto *VD = dyn_cast<VarDecl>(DE->getDecl())) {
+        auto It = Locals.find(VD);
+        if (It != Locals.end()) {
+          const auto &L = It->second;
+          switch (AK) {
+          case AccessKind::Read: {
+            if (!this->emitGetLocal(*T, L.Offset, LV))
+              return false;
+            break;
+          }
+          case AccessKind::Write: {
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetLocal(*T, L.Offset, LV))
+              return false;
+            if (!this->emitGetPtrLocal(L.Offset, LV))
+              return false;
+            break;
+          }
+          case AccessKind::WriteVoid: {
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetLocal(*T, L.Offset, LV))
+              return false;
+            break;
+          }
+          case AccessKind::ReadWrite: {
+            if (!this->emitGetLocal(*T, L.Offset, LV))
+              return false;
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetLocal(*T, L.Offset, LV))
+              return false;
+            if (!this->emitGetPtrLocal(L.Offset, LV))
+              return false;
+            break;
+          }
+          case AccessKind::ReadWriteVoid: {
+            if (!this->emitGetLocal(*T, L.Offset, LV))
+              return false;
+            if (!Direct(*T))
+              return false;
+            if (!this->emitSetLocal(*T, L.Offset, LV))
+              return false;
+            break;
+          }
+          }
+          return true;
+        } else {
+          // If the declaration is a constant value, emit it here even
+          // though the declaration was not evaluated in the current scope.
+          // The access mode can only be read in this case.
+          if (VD->hasLocalStorage()) {
+            auto VT = VD->getType();
+            if (VT.isConstQualified() && VT->isFundamentalType()) {
+              if (AK == AccessKind::Read) {
+                if (!this->Visit(VD->getInit()))
+                  return false;
+                return Direct(*T);
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+
+  if (!this->Visit(LV))
+    return false;
+  return Indirect(*T);
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::visitVarDecl(const VarDecl *VD) {
+  auto DT = VD->getType();
+
+  if (!VD->hasLocalStorage()) {
+    // No code generation required.
+    return true;
+  }
+
+  // Integers, pointers, primitives.
+  if (auto T = Ctx.classify(DT)) {
+    auto Off = allocateLocalPrimitive(VD, *T, !DT.isConstQualified());
+    // Compile the initialiser in its own scope.
+    {
+      ExprScope<Emitter> Scope(this);
+      if (!this->Visit(VD->getInit()))
+        return false;
+    }
+    // Set the value.
+    return this->emitSetLocal(*T, Off, VD);
+  } else {
+    return this->bail(VD);
+  }
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::emitConst(PrimType T, unsigned NumBits,
+                                     const APInt &Value, const Expr *E) {
+  switch (T) {
+  case PT_Sint8:
+    return this->emitConstSint8(Value.getSExtValue(), E);
+  case PT_Uint8:
+    return this->emitConstUint8(Value.getZExtValue(), E);
+  case PT_Sint16:
+    return this->emitConstSint16(Value.getSExtValue(), E);
+  case PT_Uint16:
+    return this->emitConstUint16(Value.getZExtValue(), E);
+  case PT_Sint32:
+    return this->emitConstSint32(Value.getSExtValue(), E);
+  case PT_Uint32:
+    return this->emitConstUint32(Value.getZExtValue(), E);
+  case PT_Sint64:
+    return this->emitConstSint64(Value.getSExtValue(), E);
+  case PT_Uint64:
+    return this->emitConstUint64(Value.getZExtValue(), E);
+  case PT_Bool:
+    return this->emitConstBool(Value.getBoolValue(), E);
+  case PT_Ptr:
+    llvm_unreachable("Invalid integral type");
+    break;
+  }
+}
+
+template <class Emitter>
+unsigned
+ByteCodeGen<Emitter>::allocateLocalPrimitive(DeclTy &&Decl, PrimType Ty,
+                                             bool IsMutable, bool IsExtended) {
+  Descriptor *D = P.createDescriptor(std::move(Decl), Ty, IsMutable,
+                                     Decl.is<const Expr *>());
+  Scope::Local Local = this->createLocal(D);
+  if (auto *VD = Decl.dyn_cast<const ValueDecl *>())
+    Locals.insert({VD, Local});
+  Top->add(Local, IsExtended);
+  return Local.Offset;
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::visitArgument(const Expr *E) {
+  // Primitive or pointer argument - leave it on the stack.
+  if (auto T = Ctx.classify(E))
+    return this->Visit(E);
+
+  // Composite argument - copy construct and push pointer.
+  return this->bail(E);
+}
+
+template <class Emitter> bool ByteCodeGen<Emitter>::compile(const Expr *Exp) {
+  ExprScope<Emitter> RootScope(this);
+  if (!this->ConstStmtVisitor<ByteCodeGen<Emitter>, bool>::Visit(Exp))
+    return false;
+
+  if (auto T = Ctx.classify(Exp))
+    return this->emitRet(*T, Exp);
+
+  return false;
+}
+
+template <class Emitter>
+bool ByteCodeGen<Emitter>::compile(const FunctionDecl *F) {
+  // Set up fields and context if a constructor.
+  if (auto *MD = dyn_cast<CXXMethodDecl>(F)) {
+    return this->bail(MD);
+  }
+
+  if (auto *Body = F->getBody())
+    if (!visit(Body))
+      return false;
+
+  // Emit a guard return to protect against a code path missing one.
+  if (F->getReturnType()->isVoidType())
+    return this->emitRetVoid({});
+  else
+    return this->emitNoRet({});
+}
+
+template <class Emitter> bool ByteCodeGen<Emitter>::compile(const VarDecl *VD) {
+  auto VT = VD->getType();
+  auto Init = VD->getInit();
+
+  DeclScope<Emitter> LocalScope(this);
+
+  if (auto T = Ctx.classify(VT)) {
+    // Primitive declarations - compute the value and set a global.
+    if (!this->ConstStmtVisitor<ByteCodeGen<Emitter>, bool>::Visit(Init))
+      return false;
+    if (VD->hasLocalStorage())
+      return this->emitPop(*T, VD);
+    return this->bail(VD);
+  } else {
+    // Composite declarations - allocate storage and initialize it.
+    return this->bail(VD);
+  }
+}
+
+namespace clang {
+namespace interp {
+
+template class ByteCodeGen<LinkEmitter>;
+template class ByteCodeGen<EvalEmitter>;
+
+} // namespace interp
+} // namespace clang

clang/lib/AST/Interp/ByteCodeGenError.h

+//===--- ByteCodeGenError.h - Byte code generation error ----------*- C -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_BYTECODEGENERROR_H
+#define LLVM_CLANG_AST_INTERP_BYTECODEGENERROR_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/Support/Error.h"
+
+namespace clang {
+namespace interp {
+
+/// Error thrown by the compiler.
+struct ByteCodeGenError : public llvm::ErrorInfo<ByteCodeGenError> {
+public:
+  ByteCodeGenError(SourceLocation Loc) : Loc(Loc) {}
+  ByteCodeGenError(const Stmt *S) : ByteCodeGenError(S->getBeginLoc()) {}
+  ByteCodeGenError(const Decl *D) : ByteCodeGenError(D->getBeginLoc()) {}
+
+  void log(raw_ostream &OS) const override { OS << "unimplemented feature"; }
+
+  const SourceLocation &getLoc() const { return Loc; }
+
+  static char ID;
+
+private:
+  // Start of the item where the error occurred.
+  SourceLocation Loc;
+
+  // Users are not expected to use error_code.
+  std::error_code convertToErrorCode() const override {
+    return llvm::inconvertibleErrorCode();
+  }
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/ByteCodeGenError.cpp

+//===--- ByteCodeGenError.h - Byte code generation error --------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ByteCodeGenError.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+char ByteCodeGenError::ID;

clang/lib/AST/Interp/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  )
+
+clang_tablegen(Opcodes.inc
+  -gen-clang-opcodes
+  SOURCE Opcodes.td
+  TARGET Opcodes)
+
+add_clang_library(clangInterp
+  ByteCodeGen.cpp
+  ByteCodeGenError.cpp
+  Context.cpp
+  Descriptor.cpp
+  Disasm.cpp
+  EvalEmitter.cpp
+  Frame.cpp
+  Function.cpp
+  Interp.cpp
+  InterpFrame.cpp
+  InterpStack.cpp
+  InterpState.cpp
+  LinkEmitter.cpp
+  Pointer.cpp
+  Program.cpp
+  Source.cpp
+  State.cpp
+  Type.cpp
+
+  DEPENDS
+  Opcodes
+  )

clang/lib/AST/Interp/Context.h

+//===--- Context.h - Context for the constexpr VM ---------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the constexpr execution context.
+//
+// The execution context manages cached bytecode and the global context.
+// It invokes the compiler and interpreter, propagating errors.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_CONTEXT_H
+#define LLVM_CLANG_AST_INTERP_CONTEXT_H
+
+#include "Context.h"
+#include "InterpStack.h"
+#include "clang/AST/APValue.h"
+#include "llvm/ADT/PointerIntPair.h"
+
+namespace clang {
+class ASTContext;
+class LangOptions;
+class Stmt;
+class FunctionDecl;
+class VarDecl;
+
+namespace interp {
+class Function;
+class Program;
+class State;
+enum PrimType : unsigned;
+
+/// Wrapper around interpreter termination results.
+enum class InterpResult {
+  /// Interpreter successfully computed a value.
+  Success,
+  /// Interpreter encountered an error and quit.
+  Fail,
+  /// Interpreter encountered an unimplemented feature, AST fallback.
+  Bail,
+};
+
+/// Holds all information required to evaluate constexpr code in a module.
+class Context {
+public:
+  /// Initialises the constexpr VM.
+  Context(ASTContext &Ctx);
+
+  /// Cleans up the constexpr VM.
+  ~Context();
+
+  /// Compiles and runs a function with a given set of arguments.
+  InterpResult handleFunctionCall(State &Parent, const FunctionDecl *FnDecl,
+                                  llvm::ArrayRef<APValue> Args,
+                                  APValue &Result);
+
+  /// Checks if a function is a potential constant expression.
+  InterpResult isPotentialConstantExpr(State &Parent,
+                                       const FunctionDecl *FnDecl);
+
+  /// Evaluates a toplevel expression as an rvalue.
+  InterpResult evaluateAsRValue(State &Parent, const Expr *E, APValue &Result);
+
+  /// Evaluates a toplevel initializer.
+  InterpResult evaluateAsInitializer(State &Parent, const VarDecl *VD,
+                                     APValue &Result);
+
+  /// Returns the AST context.
+  ASTContext &getASTContext() const { return Ctx; }
+  /// Returns the language options.
+  const LangOptions &getLangOpts() const;
+
+  /// Classifies an expression.
+  llvm::Optional<PrimType> classify(QualType T);
+  /// Classifies a type.
+  llvm::Optional<PrimType> classify(const Expr *E);
+  /// Checks if a type cannot be mapped to a VM type.
+  bool isComposite(QualType T) const;
+
+private:
+  /// Runs a function.
+  InterpResult Run(State &Parent, Function *Func, APValue &Result);
+
+  /// Checks a result fromt the interpreter.
+  InterpResult Check(State &Parent, llvm::Expected<bool> &&R);
+
+private:
+  /// Current compilation context.
+  ASTContext &Ctx;
+  /// Flag to indicate if the use of the interpreter is mandatory.
+  bool ForceInterp;
+  /// Interpreter stack, shared across invocations.
+  InterpStack Stk;
+  /// Constexpr program.
+  std::unique_ptr<Program> P;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Context.cpp

+//===--- Context.cpp - Context for the constexpr VM -------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Context.h"
+#include "ByteCodeGen.h"
+#include "EvalEmitter.h"
+#include "Interp.h"
+#include "InterpFrame.h"
+#include "InterpStack.h"
+#include "LinkEmitter.h"
+#include "Program.h"
+#include "Type.h"
+#include "clang/AST/Expr.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+Context::Context(ASTContext &Ctx)
+    : Ctx(Ctx), ForceInterp(getLangOpts().ForceClangInterp),
+      P(new Program(*this)) {}
+
+Context::~Context() {}
+
+InterpResult Context::handleFunctionCall(State &Parent,
+                                         const FunctionDecl *FnDecl,
+                                         llvm::ArrayRef<APValue> Args,
+                                         APValue &Result) {
+  assert(Stk.size() == 0 && "Empty stack expected on execution start");
+
+  // Compile the function.
+  Function *Func = P->getFunction(FnDecl);
+  if (!Func) {
+    if (auto R =
+            ByteCodeGen<LinkEmitter>(*this, Parent, *P).compileFunc(FnDecl)) {
+      Func = *R;
+    } else if (ForceInterp) {
+      handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) {
+        Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed);
+      });
+      return InterpResult::Fail;
+    } else {
+      consumeError(R.takeError());
+      return InterpResult::Bail;
+    }
+  }
+
+  // Convert the arguments and store them on the stack.
+  if (!Parent.checkingPotentialConstantExpression()) {
+    assert(Args.size() == FnDecl->getNumParams() && "Missing arguments");
+
+    for (unsigned I = 0, N = FnDecl->getNumParams(); I < N; ++I) {
+      auto *ParamDecl = FnDecl->getParamDecl(I);
+      auto &Value = Args[I];
+
+      switch (*classify(ParamDecl->getType())) {
+      case PT_Sint8:
+        Stk.push<PrimConv<PT_Sint8>::T>(Value.getInt());
+        break;
+      case PT_Uint8:
+        Stk.push<PrimConv<PT_Uint8>::T>(Value.getInt());
+        break;
+      case PT_Sint16:
+        Stk.push<PrimConv<PT_Sint16>::T>(Value.getInt());
+        break;
+      case PT_Uint16:
+        Stk.push<PrimConv<PT_Uint16>::T>(Value.getInt());
+        break;
+      case PT_Sint32:
+        Stk.push<PrimConv<PT_Sint32>::T>(Value.getInt());
+        break;
+      case PT_Uint32:
+        Stk.push<PrimConv<PT_Uint32>::T>(Value.getInt());
+        break;
+      case PT_Sint64:
+        Stk.push<PrimConv<PT_Sint64>::T>(Value.getInt());
+        break;
+      case PT_Uint64:
+        Stk.push<PrimConv<PT_Uint64>::T>(Value.getInt());
+        break;
+      case PT_Bool:
+        Stk.push<PrimConv<PT_Bool>::T>(Value.getInt());
+        break;
+      case PT_Ptr:
+        if (ForceInterp) {
+          const auto &Loc = Func->getLoc();
+          Parent.FFDiag(Loc, diag::err_experimental_clang_interp_failed);
+          return InterpResult::Fail;
+        } else {
+          return InterpResult::Bail;
+        }
+      }
+    }
+  }
+
+  return Run(Parent, Func, Result);
+}
+
+InterpResult Context::isPotentialConstantExpr(State &Parent,
+                                              const FunctionDecl *FD) {
+  Function *Func = P->getFunction(FD);
+  if (!Func) {
+    if (auto R = ByteCodeGen<LinkEmitter>(*this, Parent, *P).compileFunc(FD)) {
+      Func = *R;
+    } else if (ForceInterp) {
+      handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) {
+        Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed);
+      });
+      return InterpResult::Fail;
+    } else {
+      consumeError(R.takeError());
+      return InterpResult::Bail;
+    }
+  }
+
+  APValue Dummy;
+  return Run(Parent, Func, Dummy);
+}
+
+InterpResult Context::evaluateAsRValue(State &Parent, const Expr *E,
+                                       APValue &Result) {
+  ByteCodeGen<EvalEmitter> C(*this, Parent, *P, Stk, Result);
+  return Check(Parent, C.interpretExpr(E));
+}
+
+InterpResult Context::evaluateAsInitializer(State &Parent, const VarDecl *VD,
+                                            APValue &Result) {
+  ByteCodeGen<EvalEmitter> C(*this, Parent, *P, Stk, Result);
+  return Check(Parent, C.interpretDecl(VD));
+}
+
+const LangOptions &Context::getLangOpts() const { return Ctx.getLangOpts(); }
+
+llvm::Optional<PrimType> Context::classify(QualType T) {
+  if (T->isBooleanType()) {
+    return PT_Bool;
+  }
+
+  if (T->isSignedIntegerOrEnumerationType()) {
+    switch (Ctx.getIntWidth(T)) {
+    case 64:
+      return PT_Sint64;
+    case 32:
+      return PT_Sint32;
+    case 16:
+      return PT_Sint16;
+    case 8:
+      return PT_Sint8;
+    default:
+      return {};
+    }
+  }
+
+  if (T->isUnsignedIntegerOrEnumerationType()) {
+    switch (Ctx.getIntWidth(T)) {
+    case 64:
+      return PT_Uint64;
+    case 32:
+      return PT_Uint32;
+    case 16:
+      return PT_Uint16;
+    case 8:
+      return PT_Uint8;
+    default:
+      return {};
+    }
+  }
+
+  if (T->isNullPtrType() || T->isReferenceType() || T->isPointerType())
+    return PT_Ptr;
+
+  return {};
+}
+
+llvm::Optional<PrimType> Context::classify(const Expr *E) {
+  if (E->isGLValue())
+    return PT_Ptr;
+  return classify(E->getType());
+}
+
+bool Context::isComposite(QualType T) const {
+  return !T->isFundamentalType() && !T->isEnumeralType() &&
+         !T->hasPointerRepresentation();
+}
+
+InterpResult Context::Run(State &Parent, Function *Func, APValue &Result) {
+  InterpState State(Parent, *P, Stk, *this);
+  State.Current = new InterpFrame(State, Func, nullptr, {}, {});
+  if (Interpret(State, Result)) {
+    return InterpResult::Success;
+  } else {
+    Stk.clear();
+    return InterpResult::Fail;
+  }
+}
+
+InterpResult Context::Check(State &Parent, llvm::Expected<bool> &&R) {
+  if (R) {
+    return *R ? InterpResult::Success : InterpResult::Fail;
+  } else if (ForceInterp) {
+    handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) {
+      Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed);
+    });
+    return InterpResult::Fail;
+  } else {
+    consumeError(R.takeError());
+    return InterpResult::Bail;
+  }
+}

clang/lib/AST/Interp/Descriptor.h

+//===--- Descriptor.h - Types for the constexpr VM --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines descriptors which characterise allocations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_DESCRIPTOR_H
+#define LLVM_CLANG_AST_INTERP_DESCRIPTOR_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+
+namespace clang {
+namespace interp {
+class Block;
+class Record;
+struct Descriptor;
+enum PrimType : unsigned;
+
+using DeclTy = llvm::PointerUnion<const ValueDecl *, const Expr *>;
+
+/// Handlers managing object lifetimes.
+using BlockCtorFn = void (*)(Block *B, char *, bool, Descriptor *);
+using BlockDtorFn = void (*)(Block *B, char *, Descriptor *);
+using BlockMoveFn = void (*)(Block *B, char *, char *, Descriptor *);
+
+/// Object size as used by the interpreter.
+using InterpSize = unsigned;
+
+/// Describes a memory block created by an allocation site.
+struct Descriptor {
+  /// Original declaration, used to emit the error message.
+  const DeclTy Source;
+  /// Size of an element.
+  const InterpSize ElemSize;
+  /// Size of the allocation, in bytes.
+  const InterpSize Size;
+  /// Pointer to the record, if block contains records.
+  Record *const ElemRecord = nullptr;
+  /// Descriptor of the array element.
+  Descriptor *const ElemDesc = nullptr;
+  /// Flag indicating if the block is mutable.
+  const bool IsMutable = false;
+  /// Flag indicating if the block is a temporary.
+  const bool IsTemporary = false;
+  /// Flag indicating if the block is an array.
+  const bool IsArray = false;
+
+  /// Invoked whenever a block is created. The constructor method fills in the
+  /// inline descriptors of all fields and array elements. It also initializes
+  /// all the fields which contain non-trivial types.
+  const BlockCtorFn CtorFn = nullptr;
+  /// Invoked when a block is destroyed. Invokes the destructors of all
+  /// non-trivial nested fields of arrays and records.
+  const BlockDtorFn DtorFn = nullptr;
+  /// Invoked when a block with pointers referencing it goes out of scoped. Such
+  /// blocks are persisted: the move function copies all inline descriptors and
+  /// non-trivial fields, as existing pointers might need to reference those
+  /// descriptors. Data is not copied since it cannot be legally read.
+  const BlockMoveFn MoveFn = nullptr;
+
+  QualType getType() const;
+  SourceLocation getLocation() const;
+
+  /// Allocates a descriptor for a primitive.
+  Descriptor(const DeclTy &D, PrimType Type, bool IsMutable, bool IsTemporary);
+};
+
+/// Inline descriptor embedded in structures and arrays.
+struct InlineDescriptor {
+  /// Offset from the start of the record or array.
+  unsigned Offset;
+  /// Flag indicating whether storage is mutable.
+  bool IsMutable;
+  /// Flag indicating whether a record field was initialised.
+  bool IsInitialized;
+  /// Pointer to the array element or field descriptor.
+  Descriptor *Desc;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Descriptor.cpp

+//===--- Descriptor.cpp - Types for the constexpr VM ------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Descriptor.h"
+#include "Pointer.h"
+#include "Type.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+template<typename T>
+static void ctorTy(Block *, char *Ptr, bool, Descriptor *) {
+  new (Ptr) T();
+}
+
+template<typename T>
+static void dtorTy(Block *, char *Ptr, Descriptor *) {
+  reinterpret_cast<T *>(Ptr)->~T();
+}
+
+template<typename T>
+static void moveTy(Block *, char *Src, char *Dst, Descriptor *) {
+  auto *SrcPtr = reinterpret_cast<T *>(Src);
+  auto *DstPtr = reinterpret_cast<T *>(Dst);
+  new (DstPtr) T(std::move(*SrcPtr));
+}
+
+static BlockCtorFn getCtorPrim(PrimType Type) {
+  switch (Type) {
+  case PT_Ptr:    return ctorTy<PrimConv<PT_Ptr>::T>;
+  default:        return nullptr;
+  }
+}
+
+static BlockDtorFn getDtorPrim(PrimType Type) {
+  switch (Type) {
+  case PT_Ptr:    return dtorTy<PrimConv<PT_Ptr>::T>;
+  default:        return nullptr;
+  }
+}
+
+static BlockMoveFn getMovePrim(PrimType Type) {
+  switch (Type) {
+  case PT_Ptr:    return moveTy<PrimConv<PT_Ptr>::T>;
+  default:        return nullptr;
+  }
+}
+
+Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsMutable,
+                       bool IsTemporary)
+    : Source(D), ElemSize(primSize(Type)), Size(ElemSize), IsMutable(IsMutable),
+      IsTemporary(IsTemporary), CtorFn(getCtorPrim(Type)),
+      DtorFn(getDtorPrim(Type)), MoveFn(getMovePrim(Type)) {}
+
+QualType Descriptor::getType() const {
+  if (auto *D = Source.dyn_cast<const ValueDecl *>())
+    return D->getType();
+  if (auto *E = Source.dyn_cast<const Expr *>())
+    return E->getType();
+  llvm_unreachable("Invalid descriptor type");
+}
+
+SourceLocation Descriptor::getLocation() const {
+  if (auto *D = Source.dyn_cast<const ValueDecl *>())
+    return D->getLocation();
+  if (auto *E = Source.dyn_cast<const Expr *>())
+    return E->getExprLoc();
+  llvm_unreachable("Invalid descriptor type");
+}

clang/lib/AST/Interp/Disasm.cpp

+//===--- Disasm.cpp - Disassembler for bytecode functions -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Dump method for Function which disassembles the bytecode.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Function.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "Type.h"
+#include "clang/AST/DeclCXX.h"
+#include "llvm/Support/Compiler.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+LLVM_DUMP_METHOD void Function::dump() const { dump(llvm::errs()); }
+
+LLVM_DUMP_METHOD void Function::dump(llvm::raw_ostream &OS) const {
+  if (F) {
+    if (auto *Cons = dyn_cast<CXXConstructorDecl>(F)) {
+      auto Name = Cons->getParent()->getName();
+      OS << Name << "::" << Name << ":\n";
+    } else {
+      OS << F->getName() << ":\n";
+    }
+  } else {
+    OS << "<<expr>>\n";
+  }
+
+  auto PrintName = [&OS](const char *Name) {
+    OS << Name;
+    for (long I = 0, N = strlen(Name); I < 30 - N; ++I) {
+      OS << ' ';
+    }
+  };
+
+  for (auto Start = getCodeBegin(), PC = Start; PC != getCodeEnd();) {
+    size_t Addr = PC - Start;
+    auto Op = PC.read<Opcode>();
+    OS << llvm::format("%8d", Addr) << " ";
+    switch (Op) {
+#define GET_DISASM
+#include "Opcodes.inc"
+#undef GET_DISASM
+    }
+  }
+}
+
+LLVM_DUMP_METHOD void Program::dump() const { dump(llvm::errs()); }
+
+LLVM_DUMP_METHOD void Program::dump(llvm::raw_ostream &OS) const {
+  for (auto &Func : Funcs) {
+    Func.second->dump();
+  }
+  for (auto &Anon : AnonFuncs) {
+    Anon->dump();
+  }
+}

clang/lib/AST/Interp/EvalEmitter.h

+//===--- EvalEmitter.h - Instruction emitter for the VM ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the instruction emitters.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_EVALEMITTER_H
+#define LLVM_CLANG_AST_INTERP_EVALEMITTER_H
+
+#include "ByteCodeGenError.h"
+#include "Context.h"
+#include "InterpStack.h"
+#include "InterpState.h"
+#include "Program.h"
+#include "Source.h"
+#include "Type.h"
+#include "llvm/Support/Error.h"
+
+namespace clang {
+class FunctionDecl;
+namespace interp {
+class Context;
+class Function;
+class InterpState;
+class Program;
+class SourceInfo;
+enum Opcode : uint32_t;
+
+/// An emitter which evaluates opcodes as they are emitted.
+class EvalEmitter : public SourceMapper {
+public:
+  using LabelTy = uint32_t;
+  using AddrTy = uintptr_t;
+  using Local = Scope::Local;
+
+  llvm::Expected<bool> interpretExpr(const Expr *E);
+  llvm::Expected<bool> interpretDecl(const VarDecl *VD);
+
+protected:
+  EvalEmitter(Context &Ctx, State &Parent, Program &P, InterpStack &Stk,
+              APValue &Result);
+
+  virtual ~EvalEmitter() {}
+
+  /// Define a label.
+  void emitLabel(LabelTy Label);
+  /// Create a label.
+  LabelTy getLabel();
+
+  /// Methods implemented by the compiler.
+  virtual bool compile(const FunctionDecl *E) = 0;
+  virtual bool compile(const Expr *E) = 0;
+  virtual bool compile(const VarDecl *VD) = 0;
+
+  bool bail(const Stmt *S) { return bail(S->getBeginLoc()); }
+  bool bail(const Decl *D) { return bail(D->getBeginLoc()); }
+  bool bail(const SourceLocation &Loc);
+
+  /// Emits jumps.
+  bool jumpTrue(const LabelTy &Label);
+  bool jumpFalse(const LabelTy &Label);
+  bool jump(const LabelTy &Label);
+  bool fallthrough(const LabelTy &Label);
+
+  /// Callback for registering a local.
+  Local createLocal(Descriptor *D);
+
+  /// Returns the source location of the current opcode.
+  SourceInfo getSource(Function *F, CodePtr PC) const override {
+    return F ? F->getSource(PC) : CurrentSource;
+  }
+
+  /// Parameter indices.
+  llvm::DenseMap<const ParmVarDecl *, unsigned> Params;
+  /// Local descriptors.
+  llvm::SmallVector<SmallVector<Local, 8>, 2> Descriptors;
+
+private:
+  /// Current compilation context.
+  Context &Ctx;
+  /// Current program.
+  Program &P;
+  /// Callee evaluation state.
+  InterpState S;
+  /// Location to write the result to.
+  APValue &Result;
+
+  /// Temporaries which require storage.
+  llvm::DenseMap<unsigned, std::unique_ptr<char[]>> Locals;
+
+  // The emitter always tracks the current instruction and sets OpPC to a token
+  // value which is mapped to the location of the opcode being evaluated.
+  CodePtr OpPC;
+  /// Location of a failure.
+  llvm::Optional<SourceLocation> BailLocation;
+  /// Location of the current instruction.
+  SourceInfo CurrentSource;
+
+  /// Next label ID to generate - first label is 1.
+  LabelTy NextLabel = 1;
+  /// Label being executed - 0 is the entry label.
+  LabelTy CurrentLabel = 0;
+  /// Active block which should be executed.
+  LabelTy ActiveLabel = 0;
+
+  /// Since expressions can only jump forward, predicated execution is
+  /// used to deal with if-else statements.
+  bool isActive() { return CurrentLabel == ActiveLabel; }
+
+protected:
+#define GET_EVAL_PROTO
+#include "Opcodes.inc"
+#undef GET_EVAL_PROTO
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/EvalEmitter.cpp

+//===--- EvalEmitter.cpp - Instruction emitter for the VM -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "EvalEmitter.h"
+#include "Context.h"
+#include "Interp.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "clang/AST/DeclCXX.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+using APSInt = llvm::APSInt;
+using Error = llvm::Error;
+
+EvalEmitter::EvalEmitter(Context &Ctx, State &Parent, Program &P,
+                         InterpStack &Stk, APValue &Result)
+    : Ctx(Ctx), P(P), S(Parent, P, Stk, Ctx, this), Result(Result) {
+  // Create a dummy frame for the interpreter which does not have locals.
+  S.Current = new InterpFrame(S, nullptr, nullptr, {}, {});
+}
+
+llvm::Expected<bool> EvalEmitter::interpretExpr(const Expr *E) {
+  assert(S.Stk.size() == 0 && "empty stack expected by evaluator");
+
+  bool Success = this->compile(E);
+  S.Stk.clear();
+  if (!Success && BailLocation)
+    return llvm::make_error<ByteCodeGenError>(*BailLocation);
+
+  return Success;
+}
+
+llvm::Expected<bool> EvalEmitter::interpretDecl(const VarDecl *VD) {
+  assert(S.Stk.size() == 0 && "empty stack expected by evaluator");
+
+  bool Success = this->compile(VD);
+  S.Stk.clear();
+  if (!Success && BailLocation)
+    return llvm::make_error<ByteCodeGenError>(*BailLocation);
+
+  return Success;
+}
+
+void EvalEmitter::emitLabel(LabelTy Label) {
+  CurrentLabel = Label;
+}
+
+EvalEmitter::LabelTy EvalEmitter::getLabel() { return NextLabel++; }
+
+Scope::Local EvalEmitter::createLocal(Descriptor *D) {
+  // Allocate memory for a local.
+  auto Memory = llvm::make_unique<char[]>(sizeof(Block) + D->Size);
+  auto *B = new (Memory.get()) Block(D, /*isStatic=*/false);
+
+  if (D->CtorFn)
+    D->CtorFn(B, B->data(), D->IsMutable, D);
+
+  // Register the local.
+  unsigned Off = Locals.size();
+  Locals.insert({Off, std::move(Memory)});
+  return {Off, D};
+}
+
+bool EvalEmitter::bail(const SourceLocation &Loc) {
+  if (!BailLocation)
+    BailLocation = Loc;
+  return false;
+}
+
+bool EvalEmitter::jumpTrue(const LabelTy &Label) {
+  if (isActive()) {
+    if (S.Stk.pop<bool>())
+      ActiveLabel = Label;
+  }
+  return true;
+}
+
+bool EvalEmitter::jumpFalse(const LabelTy &Label) {
+  if (isActive()) {
+    if (!S.Stk.pop<bool>())
+      ActiveLabel = Label;
+  }
+  return true;
+}
+
+bool EvalEmitter::jump(const LabelTy &Label) {
+  if (isActive())
+    CurrentLabel = ActiveLabel = Label;
+  return true;
+}
+
+bool EvalEmitter::fallthrough(const LabelTy &Label) {
+  if (isActive())
+    ActiveLabel = Label;
+  return true;
+}
+
+template <PrimType OpType> bool EvalEmitter::emitRet(const SourceInfo &Info) {
+  if (!isActive()) {
+    return true;
+  }
+  using T = typename PrimConv<OpType>::T;
+  return ReturnValue<T>(S.Stk.pop<T>(), Result);
+}
+
+bool EvalEmitter::emitRetVoid(const SourceInfo &Info) { return true; }
+
+bool EvalEmitter::emitGetPtrLocal(const uint32_t &I, const SourceInfo &Info) {
+  if (!isActive())
+    return true;
+
+  auto It = Locals.find(I);
+  assert(It != Locals.end() && "Missing local variable");
+  S.Stk.push<Pointer>(reinterpret_cast<Block *>(It->second.get()));
+  return true;
+}
+
+template <PrimType OpType>
+bool EvalEmitter::emitGetLocal(const uint32_t &I, const SourceInfo &Info) {
+  if (!isActive())
+    return true;
+
+  using T = typename PrimConv<OpType>::T;
+
+  auto It = Locals.find(I);
+  assert(It != Locals.end() && "Missing local variable");
+  auto *B = reinterpret_cast<Block *>(It->second.get());
+  S.Stk.push<T>(*reinterpret_cast<T *>(B + 1));
+  return true;
+}
+
+template <PrimType OpType>
+bool EvalEmitter::emitSetLocal(const uint32_t &I, const SourceInfo &Info) {
+  if (!isActive())
+    return true;
+
+  using T = typename PrimConv<OpType>::T;
+
+  auto It = Locals.find(I);
+  assert(It != Locals.end() && "Missing local variable");
+  auto *B = reinterpret_cast<Block *>(It->second.get());
+  *reinterpret_cast<T *>(B + 1) = S.Stk.pop<T>();
+  return true;
+}
+
+bool EvalEmitter::emitDestroy(const uint32_t &I, const SourceInfo &Info) {
+  if (!isActive())
+    return true;
+
+  for (auto &Local : Descriptors[I]) {
+    auto It = Locals.find(Local.Offset);
+    assert(It != Locals.end() && "Missing local variable");
+    S.deallocate(reinterpret_cast<Block *>(It->second.get()));
+  }
+
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Opcode evaluators
+//===----------------------------------------------------------------------===//
+
+#define GET_EVAL_IMPL
+#include "Opcodes.inc"
+#undef GET_EVAL_IMPL

clang/lib/AST/Interp/Frame.h

+//===--- Frame.h - Call frame for the VM and AST Walker ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the base class of interpreter and evaluator stack frames.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_FRAME_H
+#define LLVM_CLANG_AST_INTERP_FRAME_H
+
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+class FunctionDecl;
+
+namespace interp {
+
+/// Base class for stack frames, shared between VM and walker.
+class Frame {
+public:
+  virtual ~Frame();
+
+  /// Generates a human-readable description of the call site.
+  virtual void describe(llvm::raw_ostream &OS) = 0;
+
+  /// Returns a pointer to the caller frame.
+  virtual Frame *getCaller() const = 0;
+
+  /// Returns the location of the call site.
+  virtual SourceLocation getCallLocation() const = 0;
+
+  /// Returns the called function's declaration.
+  virtual const FunctionDecl *getCallee() const = 0;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Frame.cpp

+//===--- Frame.cpp - Call frame for the VM and AST Walker -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Frame.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+Frame::~Frame() {}

clang/lib/AST/Interp/Function.h

+//===--- Function.h - Bytecode function for the VM --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the Function class which holds all bytecode function-specific data.
+//
+// The scope class which describes local variables is also defined here.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_FUNCTION_H
+#define LLVM_CLANG_AST_INTERP_FUNCTION_H
+
+#include "Pointer.h"
+#include "Source.h"
+#include "clang/AST/Decl.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace interp {
+class Program;
+enum PrimType : uint32_t;
+
+/// Describes a scope block.
+///
+/// The block gathers all the descriptors of the locals defined in this block.
+class Scope {
+public:
+  /// Information about a local's storage.
+  struct Local {
+    /// Offset of the local in frame.
+    unsigned Offset;
+    /// Descriptor of the local.
+    Descriptor *Desc;
+  };
+
+  using LocalVectorTy = llvm::SmallVector<Local, 8>;
+
+  Scope(LocalVectorTy &&Descriptors) : Descriptors(std::move(Descriptors)) {}
+
+  llvm::iterator_range<LocalVectorTy::iterator> locals() {
+    return llvm::make_range(Descriptors.begin(), Descriptors.end());
+  }
+
+private:
+  /// Object descriptors in this block.
+  LocalVectorTy Descriptors;
+};
+
+/// Bytecode function.
+///
+/// Contains links to the bytecode of the function, as well as metadata
+/// describing all arguments and stack-local variables.
+class Function {
+public:
+  using ParamDescriptor = std::pair<PrimType, Descriptor *>;
+
+  /// Returns the size of the function's local stack.
+  unsigned getFrameSize() const { return FrameSize; }
+  /// Returns the size of the argument stackx
+  unsigned getArgSize() const { return ArgSize; }
+
+  /// Returns a pointer to the start of the code.
+  CodePtr getCodeBegin() const;
+  /// Returns a pointer to the end of the code.
+  CodePtr getCodeEnd() const;
+
+  /// Returns the original FunctionDecl.
+  const FunctionDecl *getDecl() const { return F; }
+
+  /// Returns the lcoation.
+  SourceLocation getLoc() const { return Loc; }
+
+  /// Returns a parameter descriptor.
+  ParamDescriptor getParamDescriptor(unsigned Offset) const;
+
+  /// Range over the scope blocks.
+  llvm::iterator_range<llvm::SmallVector<Scope, 2>::iterator> scopes() {
+    return llvm::make_range(Scopes.begin(), Scopes.end());
+  }
+
+  /// Range over argument types.
+  using arg_reverse_iterator = SmallVectorImpl<PrimType>::reverse_iterator;
+  llvm::iterator_range<arg_reverse_iterator> args_reverse() {
+    return llvm::make_range(ParamTypes.rbegin(), ParamTypes.rend());
+  }
+
+  /// Returns a specific scope.
+  Scope &getScope(unsigned Idx) { return Scopes[Idx]; }
+
+  /// Returns the source information at a given PC.
+  SourceInfo getSource(CodePtr PC) const;
+
+private:
+  /// Construct a function representing an actual function.
+  Function(Program &P, const FunctionDecl *F, unsigned FrameSize,
+           unsigned ArgSize, std::vector<char> &&Code, SourceMap &&SrcMap,
+           llvm::SmallVector<Scope, 2> &&Scopes,
+           llvm::SmallVector<PrimType, 8> &&ParamTypes,
+           llvm::DenseMap<unsigned, ParamDescriptor> &&Params);
+
+private:
+  friend class Program;
+
+  /// Program reference.
+  Program &P;
+  /// Location of the executed code.
+  SourceLocation Loc;
+  /// Declaration this function was compiled from.
+  const FunctionDecl *F;
+  /// Local area size: storage + metadata.
+  unsigned FrameSize;
+  /// Size of the argument stack.
+  unsigned ArgSize;
+  /// Program code.
+  std::vector<char> Code;
+  /// Opcode-to-expression mapping.
+  SourceMap SrcMap;
+  /// List of block descriptors.
+  llvm::SmallVector<Scope, 2> Scopes;
+  /// List of argument types.
+  llvm::SmallVector<PrimType, 8> ParamTypes;
+  /// Map from byte offset to parameter descriptor.
+  llvm::DenseMap<unsigned, ParamDescriptor> Params;
+
+public:
+  /// Dumps the disassembled bytecode to \c llvm::errs().
+  void dump() const;
+  void dump(llvm::raw_ostream &OS) const;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Function.cpp

+//===--- Function.h - Bytecode function for the VM --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Function.h"
+#include "Program.h"
+#include "Opcode.h"
+#include "clang/AST/Decl.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+Function::Function(Program &P, const FunctionDecl *F, unsigned FrameSize,
+                   unsigned ArgSize, std::vector<char> &&Code,
+                   SourceMap &&SrcMap, llvm::SmallVector<Scope, 2> &&Scopes,
+                   llvm::SmallVector<PrimType, 8> &&ParamTypes,
+                   llvm::DenseMap<unsigned, ParamDescriptor> &&Params)
+    : P(P), Loc(F->getBeginLoc()), F(F), FrameSize(FrameSize), ArgSize(ArgSize),
+      Code(std::move(Code)), SrcMap(std::move(SrcMap)),
+      Scopes(std::move(Scopes)), ParamTypes(std::move(ParamTypes)),
+      Params(std::move(Params)) {}
+
+CodePtr Function::getCodeBegin() const { return Code.data(); }
+
+CodePtr Function::getCodeEnd() const { return Code.data() + Code.size(); }
+
+Function::ParamDescriptor Function::getParamDescriptor(unsigned Offset) const {
+  auto It = Params.find(Offset);
+  assert(It != Params.end() && "Invalid parameter offset");
+  return It->second;
+}
+
+SourceInfo Function::getSource(CodePtr PC) const {
+  unsigned Offset = PC - getCodeBegin();
+  using Elem = std::pair<unsigned, SourceInfo>;
+  auto It = std::lower_bound(SrcMap.begin(), SrcMap.end(), Elem{Offset, {}},
+                             [](Elem A, Elem B) { return A.first < B.first; });
+  if (It == SrcMap.end() || It->first != Offset)
+    llvm::report_fatal_error("missing source location");
+  return It->second;
+}

clang/lib/AST/Interp/Integral.h

+//===--- Integral.h - Wrapper for numeric types for the VM ------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the VM types and helpers operating on types.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_NUMBER_H
+#define LLVM_CLANG_AST_INTERP_NUMBER_H
+
+#include "clang/AST/ComparisonCategories.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cstddef>
+#include <cstdint>
+
+namespace clang {
+namespace interp {
+
+using APInt = llvm::APInt;
+using APSInt = llvm::APSInt;
+
+/// Helper to compare two comparable types.
+template <typename T>
+ComparisonCategoryResult Compare(const T &X, const T &Y) {
+  if (X < Y)
+    return ComparisonCategoryResult::Less;
+  if (X > Y)
+    return ComparisonCategoryResult::Greater;
+  return ComparisonCategoryResult::Equal;
+}
+
+/// Wrapper around numeric types.
+///
+/// These wrappers are required to shared an interface between APSint and
+/// builtin primitive numeral types, allowing opcodes operating on fixed
+/// precision integers and fast integers to share an implementation.
+template <unsigned Bits, bool Signed> class Integral {
+private:
+  template <unsigned OtherBits, bool OtherSigned> friend class Integral;
+
+  // Helper structure to select the representation.
+  template <unsigned B, bool S> struct Repr;
+  template <> struct Repr<1, false> { using Type = bool; };
+  template <> struct Repr<8, false> { using Type = uint8_t; };
+  template <> struct Repr<16, false> { using Type = uint16_t; };
+  template <> struct Repr<32, false> { using Type = uint32_t; };
+  template <> struct Repr<64, false> { using Type = uint64_t; };
+  template <> struct Repr<8, true> { using Type = int8_t; };
+  template <> struct Repr<16, true> { using Type = int16_t; };
+  template <> struct Repr<32, true> { using Type = int32_t; };
+  template <> struct Repr<64, true> { using Type = int64_t; };
+
+  /// Helper structure to select the min value.
+  template <unsigned B, bool S> struct Min {
+    using Type = typename Repr<Bits, Signed>::Type;
+    static const auto Value = std::numeric_limits<Type>::min();
+  };
+  template <> struct Min<1, false> { static const bool Value = false; };
+
+  // The primitive representing the integral.
+  using T = typename Repr<Bits, Signed>::Type;
+  T V;
+
+  /// Construct an integral from anything that is convertible to storage.
+  template <typename T> explicit Integral(T V) : V(V) {}
+
+public:
+  /// Zero-initializes an integral.
+  Integral() : V(0) {}
+
+  /// Constructs an integral from another integral.
+  template <unsigned SrcBits, bool SrcSign>
+  explicit Integral(Integral<SrcBits, SrcSign> V) : V(V.V) {}
+
+  /// Construct an integral from a value based on signedness.
+  explicit Integral(const APSInt &V)
+      : V(V.isSigned() ? V.getSExtValue() : V.getZExtValue()) {}
+
+  bool operator<(Integral RHS) const { return V < RHS.V; }
+  bool operator>(Integral RHS) const { return V > RHS.V; }
+  bool operator<=(Integral RHS) const { return V <= RHS.V; }
+  bool operator>=(Integral RHS) const { return V >= RHS.V; }
+  bool operator==(Integral RHS) const { return V == RHS.V; }
+  bool operator!=(Integral RHS) const { return V != RHS.V; }
+
+  Integral operator+(Integral RHS) const { return Integral(V + RHS.V); }
+  Integral operator-(Integral RHS) const { return Integral(V - RHS.V); }
+  Integral operator*(Integral RHS) const { return Integral(V * RHS.V); }
+  Integral operator/(Integral RHS) const { return Integral(V / RHS.V); }
+  Integral operator%(Integral RHS) const { return Integral(V % RHS.V); }
+  Integral operator&(Integral RHS) const { return Integral(V & RHS.V); }
+  Integral operator|(Integral RHS) const { return Integral(V | RHS.V); }
+  Integral operator^(Integral RHS) const { return Integral(V ^ RHS.V); }
+
+  Integral operator-() const { return Integral(-V); }
+  Integral operator~() const { return Integral(~V); }
+
+  Integral operator>>(unsigned RHS) const { return Integral(V >> RHS); }
+  Integral operator<<(unsigned RHS) const { return Integral(V << RHS); }
+
+  template <unsigned DstBits, bool DstSign>
+  explicit operator Integral<DstBits, DstSign>() const {
+    return Integral<DstBits, DstSign>(V);
+  }
+
+  explicit operator off_t() const { return V; }
+  explicit operator unsigned() const { return V; }
+  explicit operator uint64_t() const { return V; }
+
+  APSInt toAPSInt() const { return APSInt(APInt(Bits, V, Signed), !Signed); }
+  APSInt toAPSInt(unsigned NumBits) const {
+    return APSInt(APInt(NumBits, V, Signed), !Signed);
+  }
+
+  Integral<Bits, false> toUnsigned() const {
+    return Integral<Bits, false>(*this);
+  }
+
+  unsigned bitWidth() const { return Bits; }
+
+  bool isZero() const { return !V; }
+
+  bool isMin() const { return *this == min(bitWidth()); }
+
+  bool isMinusOne() const { return Signed && V == T(-1); }
+
+  bool isSigned() const { return Signed; }
+
+  bool isNegative() const { return V < T(0); }
+
+  ComparisonCategoryResult compare(const Integral &RHS) const {
+    return Compare(V, RHS.V);
+  }
+
+  unsigned countLeadingZeros() const {
+    unsigned LeadingZeros = __builtin_clzll(V);
+    constexpr auto FullBits = std::numeric_limits<unsigned long long>::digits;
+    return LeadingZeros - (FullBits - bitWidth());
+  }
+
+  void print(llvm::raw_ostream &OS) const { OS << V; }
+
+  static Integral min(unsigned NumBits) {
+    return Integral(Min<Bits, Signed>::Value);
+  }
+
+  template <typename T>
+  static typename std::enable_if<std::is_integral<T>::value, Integral>::type
+  from(T Value) {
+    return Integral(Value);
+  }
+
+  template <unsigned SrcBits, bool SrcSign>
+  static typename std::enable_if<SrcBits != 0, Integral>::type
+  from(Integral<SrcBits, SrcSign> Value) {
+    return Integral(Value.V);
+  }
+
+  template <bool SrcSign> static Integral from(Integral<0, SrcSign> Value) {
+    if (SrcSign)
+      return Integral(Value.V.getSExtValue());
+    else
+      return Integral(Value.V.getZExtValue());
+  }
+
+  static Integral zero() { return from(0); }
+
+  template <typename T> static Integral from(T Value, unsigned NumBits) {
+    return Integral(Value);
+  }
+
+  static bool increment(Integral A, Integral *R) {
+    return add(A, Integral(T(1)), A.bitWidth(), R);
+  }
+
+  static bool decrement(Integral A, Integral *R) {
+    return sub(A, Integral(T(1)), A.bitWidth(), R);
+  }
+
+  static bool add(Integral A, Integral B, unsigned OpBits, Integral *R) {
+    return CheckAddUB(A.V, B.V, R->V);
+  }
+
+  static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) {
+    return CheckSubUB(A.V, B.V, R->V);
+  }
+
+  static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) {
+    return CheckMulUB(A.V, B.V, R->V);
+  }
+
+private:
+  template <typename T>
+  static typename std::enable_if<std::is_signed<T>::value, bool>::type
+  CheckAddUB(T A, T B, T &R) {
+    return llvm::AddOverflow<T>(A, B, R);
+  }
+
+  template <typename T>
+  static typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+  CheckAddUB(T A, T B, T &R) {
+    R = A + B;
+    return false;
+  }
+
+  template <typename T>
+  static typename std::enable_if<std::is_signed<T>::value, bool>::type
+  CheckSubUB(T A, T B, T &R) {
+    return llvm::SubOverflow<T>(A, B, R);
+  }
+
+  template <typename T>
+  static typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+  CheckSubUB(T A, T B, T &R) {
+    R = A - B;
+    return false;
+  }
+
+  template <typename T>
+  static typename std::enable_if<std::is_signed<T>::value, bool>::type
+  CheckMulUB(T A, T B, T &R) {
+    return llvm::MulOverflow<T>(A, B, R);
+  }
+
+  template <typename T>
+  static typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+  CheckMulUB(T A, T B, T &R) {
+    R = A * B;
+    return false;
+  }
+};
+
+template <unsigned Bits, bool Signed>
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Integral<Bits, Signed> I) {
+  I.print(OS);
+  return OS;
+}
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Interp.h

+//===--- Interp.h - Interpreter for the constexpr VM ------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Definition of the interpreter state and entry point.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_INTERP_H
+#define LLVM_CLANG_AST_INTERP_INTERP_H
+
+#include "Function.h"
+#include "InterpFrame.h"
+#include "InterpStack.h"
+#include "InterpState.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "State.h"
+#include "Type.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTDiagnostic.h"
+#include "clang/AST/CXXInheritance.h"
+#include "clang/AST/Expr.h"
+#include "llvm/ADT/APFloat.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/Support/Endian.h"
+#include <limits>
+#include <vector>
+
+namespace clang {
+namespace interp {
+
+using APInt = llvm::APInt;
+using APSInt = llvm::APSInt;
+
+/// Convers a value to an APValue.
+template <typename T> bool ReturnValue(const T &V, APValue &R) {
+  R = APValue(V.toAPSInt());
+  return true;
+}
+
+
+template <> inline bool ReturnValue<Pointer>(const Pointer &Ptr, APValue &R) {
+  if (const auto &Value = Ptr.toAPValue()) {
+    R = *Value;
+    return true;
+  }
+  return false;
+}
+
+/// Checks if a pointer is live and accesible.
+bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+               AccessKinds AK);
+
+/// Checks if a pointer is null.
+bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+               CheckSubobjectKind CSK);
+
+/// Checks if a pointer is in range.
+bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+                AccessKinds AK);
+
+/// Checks if a pointer points to a mutable location.
+bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
+
+// Checks a pointer offset.
+bool CheckOffset(int64_t NewOffset, const Pointer &Ptr, InterpState &S,
+                 CodePtr OpPC);
+
+/// Checks if a value can be loaded from a block.
+bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
+
+/// Checks if a value can be stored in a block.
+bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
+
+/// Checks if a value can be initialized.
+bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr);
+
+template <typename T> inline bool IsTrue(const T &V) { return !V.isZero(); }
+template <> inline bool IsTrue(const Pointer &V) { return !V.isNull(); }
+
+//===----------------------------------------------------------------------===//
+// Add, Sub, Mul
+//===----------------------------------------------------------------------===//
+
+template <typename T, bool (*OpFW)(T, T, unsigned, T *),
+          template <typename U> class OpAP>
+bool AddSubMulHelper(InterpState &S, CodePtr OpPC, unsigned Bits, const T &LHS,
+                     const T &RHS) {
+  // Fast path - add the numbers with fixed width.
+  T Result;
+  if (!OpFW(LHS, RHS, Bits, &Result)) {
+    S.Stk.push<T>(Result);
+    return true;
+  }
+
+  // If for some reason evaluation continues, use the truncated results.
+  S.Stk.push<T>(Result);
+
+  // Slow path - compute the result using another bit of precision.
+  APSInt Value = OpAP<APSInt>()(LHS.toAPSInt(Bits), RHS.toAPSInt(Bits));
+
+  // Report undefined behaviour, stopping if required.
+  const Expr *E = S.Current->getExpr(OpPC);
+  QualType Type = E->getType();
+  if (S.checkingForOverflow()) {
+    auto Trunc = Value.trunc(Result.bitWidth()).toString(10);
+    auto Loc = E->getExprLoc();
+    S.report(Loc, diag::warn_integer_constant_overflow) << Trunc << Type;
+    return true;
+  } else {
+    S.CCEDiag(E, diag::note_constexpr_overflow) << Value << Type;
+    return S.noteUndefinedBehavior();
+  }
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Add(InterpState &S, CodePtr OpPC) {
+  const T &RHS = S.Stk.pop<T>();
+  const T &LHS = S.Stk.pop<T>();
+  const unsigned Bits = RHS.bitWidth() + 1;
+  return AddSubMulHelper<T, T::add, std::plus>(S, OpPC, Bits, LHS, RHS);
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Sub(InterpState &S, CodePtr OpPC) {
+  const T &RHS = S.Stk.pop<T>();
+  const T &LHS = S.Stk.pop<T>();
+  const unsigned Bits = RHS.bitWidth() + 1;
+  return AddSubMulHelper<T, T::sub, std::minus>(S, OpPC, Bits, LHS, RHS);
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Mul(InterpState &S, CodePtr OpPC) {
+  const T &RHS = S.Stk.pop<T>();
+  const T &LHS = S.Stk.pop<T>();
+  const unsigned Bits = RHS.bitWidth() * 2;
+  return AddSubMulHelper<T, T::mul, std::multiplies>(S, OpPC, Bits, LHS, RHS);
+}
+
+//===----------------------------------------------------------------------===//
+// Div, Rem
+//===----------------------------------------------------------------------===//
+
+template <typename T, T (*OpFW)(T, T), typename OpAP>
+bool DivRemHelper(InterpState &S, CodePtr OpPC) {
+  const T RHS = S.Stk.pop<T>();
+  const T LHS = S.Stk.pop<T>();
+
+  // Bail on division by zero.
+  if (RHS.isZero()) {
+    S.FFDiag(S.Current->getSource(OpPC), diag::note_expr_divide_by_zero);
+    return false;
+  }
+
+  if (RHS.isSigned()) {
+    // (-MAX - 1) / -1 = MAX + 1 overflows.
+    if (LHS.isMin() && RHS.isMinusOne()) {
+      // Push the truncated value in case the interpreter continues.
+      S.Stk.push<T>(T::min(RHS.bitWidth()));
+
+      // Compute the actual value for the diagnostic.
+      const size_t Bits = RHS.bitWidth() + 1;
+      APSInt Value = OpAP()(LHS.toAPSInt(Bits), RHS.toAPSInt(Bits));
+      return S.reportOverflow(S.Current->getExpr(OpPC), Value);
+    }
+  }
+
+  // Safe to execute division here.
+  S.Stk.push<T>(OpFW(LHS, RHS));
+  return true;
+}
+
+template <typename T> T DivFn(T a, T b) { return a / b; }
+
+template <typename T> T RemFn(T a, T b) { return a % b; }
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Div(InterpState &S, CodePtr OpPC) {
+  return DivRemHelper<T, DivFn<T>, std::divides<APSInt>>(S, OpPC);
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Rem(InterpState &S, CodePtr OpPC) {
+  return DivRemHelper<T, RemFn<T>, std::modulus<APSInt>>(S, OpPC);
+}
+
+//===----------------------------------------------------------------------===//
+// EQ, NE, GT, GE, LT, LE
+//===----------------------------------------------------------------------===//
+
+using CompareFn = llvm::function_ref<bool(ComparisonCategoryResult)>;
+
+template <typename T>
+bool CmpHelper(InterpState &S, CodePtr OpPC, CompareFn Fn) {
+  using BoolT = PrimConv<PT_Bool>::T;
+  const T &RHS = S.Stk.pop<T>();
+  const T &LHS = S.Stk.pop<T>();
+  S.Stk.push<BoolT>(BoolT::from(Fn(LHS.compare(RHS))));
+  return true;
+}
+
+template <>
+inline bool CmpHelper<Pointer>(InterpState &S, CodePtr OpPC, CompareFn Fn) {
+  using BoolT = PrimConv<PT_Bool>::T;
+  const Pointer &RHS = S.Stk.pop<Pointer>();
+  const Pointer &LHS = S.Stk.pop<Pointer>();
+
+  if (!Pointer::isComparable(LHS, RHS)) {
+    const auto &Loc = S.Current->getSource(OpPC);
+    S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr);
+    return false;
+  } else {
+    auto VL = LHS.getOffset();
+    auto VR = RHS.getOffset();
+    S.Stk.push<BoolT>(BoolT::from(Fn(Compare(VL, VR))));
+    return true;
+  }
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool EQ(InterpState &S, CodePtr OpPC) {
+  return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
+    return R == ComparisonCategoryResult::Equal;
+  });
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool NE(InterpState &S, CodePtr OpPC) {
+  return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
+    return R != ComparisonCategoryResult::Equal;
+  });
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool LT(InterpState &S, CodePtr OpPC) {
+  return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
+    return R == ComparisonCategoryResult::Less;
+  });
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool LE(InterpState &S, CodePtr OpPC) {
+  return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
+    return R == ComparisonCategoryResult::Less ||
+           R == ComparisonCategoryResult::Equal;
+  });
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool GT(InterpState &S, CodePtr OpPC) {
+  return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
+    return R == ComparisonCategoryResult::Greater;
+  });
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool GE(InterpState &S, CodePtr OpPC) {
+  return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) {
+    return R == ComparisonCategoryResult::Greater ||
+           R == ComparisonCategoryResult::Equal;
+  });
+}
+
+//===----------------------------------------------------------------------===//
+// Dup, Pop
+//===----------------------------------------------------------------------===//
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Dup(InterpState &S, CodePtr OpPC) {
+  S.Stk.push<T>(S.Stk.peek<T>());
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Pop(InterpState &S, CodePtr OpPC) {
+  S.Stk.pop<T>();
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Test
+//===----------------------------------------------------------------------===//
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Test(InterpState &S, CodePtr OpPC) {
+  S.Stk.push<bool>(IsTrue<T>(S.Stk.pop<T>()));
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Const, ConstFP
+//===----------------------------------------------------------------------===//
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Const(InterpState &S, CodePtr OpPC, const T &Arg) {
+  S.Stk.push<T>(Arg);
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Get/Set Local/Param/Global/This
+//===----------------------------------------------------------------------===//
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool GetLocal(InterpState &S, CodePtr OpPC, uint32_t I) {
+  S.Stk.push<T>(S.Current->getLocal<T>(I));
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool SetLocal(InterpState &S, CodePtr OpPC, uint32_t I) {
+  S.Current->setLocal<T>(I, S.Stk.pop<T>());
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool GetParam(InterpState &S, CodePtr OpPC, uint32_t I) {
+  if (S.checkingPotentialConstantExpression()) {
+    return false;
+  }
+  S.Stk.push<T>(S.Current->getParam<T>(I));
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool SetParam(InterpState &S, CodePtr OpPC, uint32_t I) {
+  S.Current->setParam<T>(I, S.Stk.pop<T>());
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// GetPtr Local/Param/Global/Field/This
+//===----------------------------------------------------------------------===//
+
+inline bool GetPtrLocal(InterpState &S, CodePtr OpPC, uint32_t I) {
+  S.Stk.push<Pointer>(S.Current->getLocalPointer(I));
+  return true;
+}
+
+inline bool GetPtrParam(InterpState &S, CodePtr OpPC, uint32_t I) {
+  if (S.checkingPotentialConstantExpression()) {
+    return false;
+  }
+  S.Stk.push<Pointer>(S.Current->getParamPointer(I));
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Load, Store, Init
+//===----------------------------------------------------------------------===//
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Load(InterpState &S, CodePtr OpPC) {
+  const Pointer &Ptr = S.Stk.peek<Pointer>();
+  if (!CheckLoad(S, OpPC, Ptr))
+    return false;
+  S.Stk.push<T>(Ptr.deref<T>());
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool LoadPop(InterpState &S, CodePtr OpPC) {
+  const Pointer &Ptr = S.Stk.pop<Pointer>();
+  if (!CheckLoad(S, OpPC, Ptr))
+    return false;
+  S.Stk.push<T>(Ptr.deref<T>());
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Store(InterpState &S, CodePtr OpPC) {
+  const T &Value = S.Stk.pop<T>();
+  const Pointer &Ptr = S.Stk.peek<Pointer>();
+  if (!CheckStore(S, OpPC, Ptr))
+    return false;
+  Ptr.deref<T>() = Value;
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool StorePop(InterpState &S, CodePtr OpPC) {
+  const T &Value = S.Stk.pop<T>();
+  const Pointer &Ptr = S.Stk.pop<Pointer>();
+  if (!CheckStore(S, OpPC, Ptr))
+    return false;
+  Ptr.deref<T>() = Value;
+  return true;
+}
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Init(InterpState &S, CodePtr OpPC) {
+  const T &Value = S.Stk.pop<T>();
+  const Pointer &Ptr = S.Stk.peek<Pointer>();
+  if (!CheckInit(S, OpPC, Ptr)) {
+    return false;
+  }
+  Ptr.deref<T>() = Value;
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Destroy
+//===----------------------------------------------------------------------===//
+
+inline bool Destroy(InterpState &S, CodePtr OpPC, uint32_t I) {
+  S.Current->destroy(I);
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Zero, Nullptr
+//===----------------------------------------------------------------------===//
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Zero(InterpState &S, CodePtr OpPC) {
+  S.Stk.push<T>(T::zero());
+  return true;
+}
+
+inline bool NullPtr(InterpState &S, CodePtr OpPC) {
+  S.Stk.push<Pointer>();
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Undef
+//===----------------------------------------------------------------------===//
+
+inline bool Undef(InterpState &S, CodePtr OpPC) {
+  // this should generate a dummy pointer, but nullptr works.
+  S.Stk.push<Pointer>();
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// NoRet
+//===----------------------------------------------------------------------===//
+
+inline bool NoRet(InterpState &S, CodePtr OpPC) {
+  SourceLocation EndLoc = S.Current->getCallee()->getEndLoc();
+  S.FFDiag(EndLoc, diag::note_constexpr_no_return);
+  return false;
+}
+
+/// Interpreter entry point.
+bool Interpret(InterpState &S, APValue &Result);
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Interp.cpp

+//===--- InterpState.cpp - Interpreter for the constexpr VM -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Interp.h"
+#include "Function.h"
+#include "InterpFrame.h"
+#include "InterpStack.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "State.h"
+#include "Type.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTDiagnostic.h"
+#include "clang/AST/CXXInheritance.h"
+#include "clang/AST/Expr.h"
+#include "llvm/ADT/APSInt.h"
+#include <limits>
+#include <vector>
+
+using namespace clang;
+using namespace clang::interp;
+
+//===----------------------------------------------------------------------===//
+// Ret
+//===----------------------------------------------------------------------===//
+
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+static bool Ret(InterpState &S, CodePtr &PC, APValue &Result) {
+  S.CallStackDepth--;
+  const T &Ret = S.Stk.pop<T>();
+
+  assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame");
+  if (!S.checkingPotentialConstantExpression())
+    S.Current->popArgs();
+
+  if (InterpFrame *Caller = S.Current->Caller) {
+    PC = S.Current->getRetPC();
+    delete S.Current;
+    S.Current = Caller;
+    S.Stk.push<T>(Ret);
+  } else {
+    delete S.Current;
+    S.Current = nullptr;
+    if (!ReturnValue<T>(Ret, Result))
+      return false;
+  }
+  return true;
+}
+
+static bool RetVoid(InterpState &S, CodePtr &PC, APValue &Result) {
+  S.CallStackDepth--;
+
+  assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame");
+  if (!S.checkingPotentialConstantExpression())
+    S.Current->popArgs();
+
+  if (InterpFrame *Caller = S.Current->Caller) {
+    PC = S.Current->getRetPC();
+    delete S.Current;
+    S.Current = Caller;
+  } else {
+    delete S.Current;
+    S.Current = nullptr;
+  }
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Jmp, Jt, Jf
+//===----------------------------------------------------------------------===//
+
+static bool Jmp(InterpState &S, CodePtr &PC, int32_t Offset) {
+  PC += Offset;
+  return true;
+}
+
+static bool Jt(InterpState &S, CodePtr &PC, int32_t Offset) {
+  if (S.Stk.pop<bool>()) {
+    PC += Offset;
+  }
+  return true;
+}
+
+static bool Jf(InterpState &S, CodePtr &PC, int32_t Offset) {
+  if (!S.Stk.pop<bool>()) {
+    PC += Offset;
+  }
+  return true;
+}
+
+namespace clang {
+namespace interp {
+
+bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+               AccessKinds AK) {
+  const auto &Src = S.Current->getSource(OpPC);
+  if (Ptr.isNull()) {
+
+    if (Ptr.isField())
+      S.FFDiag(Src, diag::note_constexpr_null_subobject) << CSK_Field;
+    else
+      S.FFDiag(Src, diag::note_constexpr_access_null) << AK;
+
+    return false;
+  }
+
+  if (!Ptr.isLive()) {
+    bool IsTemp = Ptr.isTemporary();
+
+    S.FFDiag(Src, diag::note_constexpr_lifetime_ended, 1) << AK << !IsTemp;
+
+    if (IsTemp)
+      S.Note(Ptr.getDeclLoc(), diag::note_constexpr_temporary_here);
+    else
+      S.Note(Ptr.getDeclLoc(), diag::note_declared_at);
+
+    return false;
+  }
+
+  return true;
+}
+
+bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+               CheckSubobjectKind CSK) {
+  if (!Ptr.isNull())
+    return true;
+  const auto &Loc = S.Current->getSource(OpPC);
+  S.FFDiag(Loc, diag::note_constexpr_null_subobject) << CSK;
+  return false;
+}
+
+bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+                AccessKinds AK) {
+  if (Ptr.inBounds())
+    return true;
+  const auto &Loc = S.Current->getSource(OpPC);
+  S.FFDiag(Loc, diag::note_constexpr_access_past_end) << AK;
+  return false;
+}
+
+bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr) {
+  assert(Ptr.isLive() && "Pointer is not live");
+  if (Ptr.isMutable()) {
+    return true;
+  }
+
+  const QualType Ty = Ptr.getType();
+  const auto &Loc = S.Current->getSource(OpPC);
+  S.FFDiag(Loc, diag::note_constexpr_modify_const_type) << Ty;
+  return false;
+}
+
+bool CheckOffset(int64_t NewOffset, const Pointer &Ptr, InterpState &S,
+                 CodePtr OpPC) {
+  int64_t Index = NewOffset / static_cast<int64_t>(Ptr.elemSize());
+  size_t NumElems = Ptr.size() / Ptr.elemSize();
+
+  if (Index < 0 || static_cast<size_t>(Index) > NumElems) {
+    S.CCEDiag(S.Current->getSource(OpPC), diag::note_constexpr_array_index)
+        << Integral<64, true>::from(Index).toAPSInt()
+        << /*array*/ static_cast<int>(!Ptr.isArray())
+        << static_cast<unsigned>(NumElems);
+    return false;
+  }
+  return true;
+}
+
+static bool CheckExtern(InterpState &S, CodePtr OpPC, const Pointer &Ptr) {
+  if (!Ptr.isExtern())
+    return true;
+
+  auto *VD = Ptr.getDeclDesc()->Source.dyn_cast<const ValueDecl *>();
+  const auto &Loc = S.Current->getSource(OpPC);
+  S.FFDiag(Loc, diag::note_constexpr_ltor_non_constexpr, 1) << VD;
+  S.Note(VD->getLocation(), diag::note_declared_at);
+  return false;
+}
+
+static bool CheckInitialized(InterpState &S, CodePtr OpPC, const Pointer &Ptr,
+                             AccessKinds AK) {
+  if (Ptr.isInitialized())
+    return true;
+  const auto &Loc = S.Current->getSource(OpPC);
+  S.FFDiag(Loc, diag::note_constexpr_access_uninit) << AK << false;
+  return false;
+}
+
+bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr) {
+  if (!CheckLive(S, OpPC, Ptr, AK_Read))
+    return false;
+  if (!CheckExtern(S, OpPC, Ptr))
+    return false;
+  if (!CheckRange(S, OpPC, Ptr, AK_Read))
+    return false;
+  if (!CheckInitialized(S, OpPC, Ptr, AK_Read))
+    return false;
+  return true;
+}
+
+bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr) {
+  if (!CheckLive(S, OpPC, Ptr, AK_Assign))
+    return false;
+  if (!CheckRange(S, OpPC, Ptr, AK_Assign))
+    return false;
+  if (!CheckMutable(S, OpPC, Ptr))
+    return false;
+  return true;
+}
+
+bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr) {
+  if (!CheckLive(S, OpPC, Ptr, AK_Assign))
+    return false;
+  if (!CheckRange(S, OpPC, Ptr, AK_Assign))
+    return false;
+  return true;
+}
+
+bool Interpret(InterpState &S, APValue &Result) {
+  CodePtr PC = S.Current->getPC();
+
+  for (;;) {
+    auto Op = PC.read<Opcode>();
+    CodePtr OpPC = PC;
+
+    switch (Op) {
+#define GET_INTERP
+#include "Opcodes.inc"
+#undef GET_INTERP
+    }
+  }
+}
+
+} // namespace interp
+} // namespace clang

clang/lib/AST/Interp/InterpFrame.h

+//===--- InterpFrame.h - Call Frame implementation for the VM ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the class storing information about stack frames in the interpreter.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_INTERPFRAME_H
+#define LLVM_CLANG_AST_INTERP_INTERPFRAME_H
+
+#include "Frame.h"
+#include "Pointer.h"
+#include "Program.h"
+#include "State.h"
+#include <cstdint>
+#include <vector>
+
+namespace clang {
+namespace interp {
+class Function;
+class InterpState;
+
+/// Frame storing local variables.
+class InterpFrame final : public Frame {
+public:
+  /// The frame of the previous function.
+  InterpFrame *Caller;
+
+  /// Creates a new frame for a method call.
+  InterpFrame(InterpState &S, Function *Func, InterpFrame *Caller,
+              CodePtr RetPC, const Pointer &This);
+
+  /// Destroys the frame, killing all live pointers to stack slots.
+  ~InterpFrame();
+
+  /// Invokes the destructors for a scope.
+  void destroy(unsigned Idx);
+
+  /// Pops the arguments off the stack.
+  void popArgs();
+
+  /// Describes the frame with arguments for diagnostic purposes.
+  void describe(llvm::raw_ostream &OS);
+
+  /// Returns the parent frame object.
+  Frame *getCaller() const;
+
+  /// Returns the location of the call to the frame.
+  SourceLocation getCallLocation() const;
+
+  /// Returns the caller.
+  const FunctionDecl *getCallee() const;
+
+  /// Returns the current function.
+  Function *getFunction() const { return Func; }
+
+  /// Returns the offset on the stack at which the frame starts.
+  size_t getFrameOffset() const { return FrameOffset; }
+
+  /// Returns the value of a local variable.
+  template <typename T> const T &getLocal(unsigned Offset) {
+    return localRef<T>(Offset);
+  }
+
+  /// Mutates a local variable.
+  template <typename T> void setLocal(unsigned Offset, const T &Value) {
+    localRef<T>(Offset) = Value;
+  }
+
+  /// Returns a pointer to a local variables.
+  Pointer getLocalPointer(unsigned Offset);
+
+  /// Returns the value of an argument.
+  template <typename T> const T &getParam(unsigned Offset) {
+    auto Pt = Params.find(Offset);
+    if (Pt == Params.end()) {
+      return stackRef<T>(Offset);
+    } else {
+      return Pointer(reinterpret_cast<Block *>(Pt->second.get())).deref<T>();
+    }
+  }
+
+  /// Mutates a local copy of a parameter.
+  template <typename T> void setParam(unsigned Offset, const T &Value) {
+     getParamPointer(Offset).deref<T>() = Value;
+  }
+
+  /// Returns a pointer to an argument - lazily creates a block.
+  Pointer getParamPointer(unsigned Offset);
+
+  /// Returns the 'this' pointer.
+  const Pointer &getThis() const { return This; }
+
+  /// Checks if the frame is a root frame - return should quit the interpreter.
+  bool isRoot() const { return !Func; }
+
+  /// Returns the PC of the frame's code start.
+  CodePtr getPC() const { return Func->getCodeBegin(); }
+
+  /// Returns the return address of the frame.
+  CodePtr getRetPC() const { return RetPC; }
+
+  /// Map a location to a source.
+  virtual SourceInfo getSource(CodePtr PC) const;
+  const Expr *getExpr(CodePtr PC) const;
+  SourceLocation getLocation(CodePtr PC) const;
+
+private:
+  /// Returns an original argument from the stack.
+  template <typename T> const T &stackRef(unsigned Offset) {
+    return *reinterpret_cast<const T *>(Args - ArgSize + Offset);
+  }
+
+  /// Returns an offset to a local.
+  template <typename T> T &localRef(unsigned Offset) {
+    return *reinterpret_cast<T *>(Locals.get() + Offset);
+  }
+
+  /// Returns a pointer to a local's block.
+  void *localBlock(unsigned Offset) {
+    return Locals.get() + Offset - sizeof(Block);
+  }
+
+private:
+  /// Reference to the interpreter state.
+  InterpState &S;
+  /// Reference to the function being executed.
+  Function *Func;
+  /// Current object pointer for methods.
+  Pointer This;
+  /// Return address.
+  CodePtr RetPC;
+  /// The size of all the arguments.
+  const unsigned ArgSize;
+  /// Pointer to the arguments in the callee's frame.
+  char *Args = nullptr;
+  /// Fixed, initial storage for known local variables.
+  std::unique_ptr<char[]> Locals;
+  /// Offset on the stack at entry.
+  const size_t FrameOffset;
+  /// Mapping from arg offsets to their argument blocks.
+  llvm::DenseMap<unsigned, std::unique_ptr<char[]>> Params;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/InterpFrame.cpp

+//===--- InterpFrame.cpp - Call Frame implementation for the VM -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "InterpFrame.h"
+#include "Function.h"
+#include "Interp.h"
+#include "InterpStack.h"
+#include "Program.h"
+#include "Type.h"
+#include "clang/AST/DeclCXX.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+InterpFrame::InterpFrame(InterpState &S, Function *Func, InterpFrame *Caller,
+                         CodePtr RetPC, const Pointer &This)
+    : Caller(Caller), S(S), Func(Func), This(This), RetPC(RetPC),
+      ArgSize(Func ? Func->getArgSize() : 0),
+      Args(static_cast<char *>(S.Stk.top())), FrameOffset(S.Stk.size()) {
+  if (Func) {
+    if (auto FrameSize = Func->getFrameSize()) {
+      Locals = llvm::make_unique<char[]>(FrameSize);
+      for (auto &Scope : Func->scopes()) {
+        for (auto &Local : Scope.locals()) {
+          Block *B = new (localBlock(Local.Offset)) Block(Local.Desc);
+          if (Local.Desc->CtorFn)
+            Local.Desc->CtorFn(B, B->data(), Local.Desc->IsMutable, Local.Desc);
+        }
+      }
+    }
+  }
+}
+
+InterpFrame::~InterpFrame() {
+  for (auto &Param : Params) {
+    S.deallocate(reinterpret_cast<Block *>(Param.second.get()));
+  }
+}
+
+void InterpFrame::destroy(unsigned Idx) {
+  for (auto &Local : Func->getScope(Idx).locals()) {
+    S.deallocate(reinterpret_cast<Block *>(localBlock(Local.Offset)));
+  }
+}
+
+void InterpFrame::popArgs() {
+  for (PrimType Ty : Func->args_reverse())
+    TYPE_SWITCH(Ty, S.Stk.discard<T>());
+}
+
+template <typename T>
+static void print(llvm::raw_ostream &OS, const T &V, ASTContext &, bool) {
+  OS << V;
+}
+
+template <>
+void print(llvm::raw_ostream &OS, const Pointer &P, ASTContext &Ctx,
+           bool IsReference) {
+  if (P.isNull()) {
+    OS << "nullptr";
+    return;
+  }
+
+  auto printDesc = [&OS, &Ctx](Descriptor *Desc) {
+    if (auto *D = Desc->Source.dyn_cast<const ValueDecl *>()) {
+      OS << *D;
+      return;
+    }
+    if (auto *E = Desc->Source.dyn_cast<const Expr *>()) {
+      E->printPretty(OS, nullptr, Ctx.getPrintingPolicy());
+      return;
+    }
+    llvm_unreachable("Invalid descriptor type");
+  };
+
+  if (!IsReference)
+    OS << "&";
+  llvm::SmallVector<Pointer, 2> Levels;
+  for (Pointer F = P; F.isField(); F = F.getBase())
+    Levels.push_back(F);
+
+  printDesc(P.getDeclDesc());
+  for (auto It = Levels.rbegin(); It != Levels.rend(); ++It) {
+    OS << ".";
+    printDesc(It->getFieldDesc());
+  }
+
+  if (auto Index = P.getIndex())
+    OS << " + " << Index;
+}
+
+void InterpFrame::describe(llvm::raw_ostream &OS) {
+  auto *F = getCallee();
+  auto *M = dyn_cast<CXXMethodDecl>(F);
+  if (M && M->isInstance() && !isa<CXXConstructorDecl>(F)) {
+    print(OS, This, S.getCtx(), /*isReference*/false);
+    OS << "->";
+  }
+  OS << *F << "(";
+  unsigned Off = 0;
+  for (unsigned I = 0, N = F->getNumParams(); I < N; ++I) {
+    QualType Ty = F->getParamDecl(I)->getType();
+    const bool IsReference = Ty->isReferenceType();
+
+    PrimType PrimTy;
+    if (auto T = S.Ctx.classify(Ty)) {
+      PrimTy = *T;
+    } else {
+      PrimTy = PT_Ptr;
+    }
+
+    TYPE_SWITCH(PrimTy, print(OS, stackRef<T>(Off), S.getCtx(), IsReference));
+    Off += align(primSize(PrimTy));
+    if (I + 1 != N)
+      OS << ", ";
+  }
+  OS << ")";
+}
+
+Frame *InterpFrame::getCaller() const {
+  if (Caller->Caller)
+    return Caller;
+  return S.getSplitFrame();
+}
+
+SourceLocation InterpFrame::getCallLocation() const {
+  if (!Caller->Func)
+    return S.getLocation(nullptr, {});
+  return S.getLocation(Caller->Func, RetPC - sizeof(uintptr_t));
+}
+
+const FunctionDecl *InterpFrame::getCallee() const {
+  return Func->getDecl();
+}
+
+Pointer InterpFrame::getLocalPointer(unsigned Offset) {
+  assert(Offset < Func->getFrameSize() && "Invalid local offset.");
+  return Pointer(
+      reinterpret_cast<Block *>(Locals.get() + Offset - sizeof(Block)));
+}
+
+Pointer InterpFrame::getParamPointer(unsigned Off) {
+  // Return the block if it was created previously.
+  auto Pt = Params.find(Off);
+  if (Pt != Params.end()) {
+    return Pointer(reinterpret_cast<Block *>(Pt->second.get()));
+  }
+
+  // Allocate memory to store the parameter and the block metadata.
+  const auto &Desc = Func->getParamDescriptor(Off);
+  auto Memory = llvm::make_unique<char[]>(sizeof(Block) + Desc.second->Size);
+  auto *B = new (Memory.get()) Block(Desc.second);
+
+  // Copy the initial value.
+  TYPE_SWITCH(Desc.first, new (B->data()) T(stackRef<T>(Off)));
+
+  // Record the param.
+  Params.insert({Off, std::move(Memory)});
+  return Pointer(B);
+}
+
+SourceInfo InterpFrame::getSource(CodePtr PC) const {
+  return S.getSource(Func, PC);
+}
+
+const Expr *InterpFrame::getExpr(CodePtr PC) const {
+  return S.getExpr(Func, PC);
+}
+
+SourceLocation InterpFrame::getLocation(CodePtr PC) const {
+  return S.getLocation(Func, PC);
+}
+

clang/lib/AST/Interp/InterpStack.h

+//===--- InterpStack.h - Stack implementation for the VM --------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the upwards-growing stack used by the interpreter.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H
+#define LLVM_CLANG_AST_INTERP_INTERPSTACK_H
+
+#include <memory>
+
+namespace clang {
+namespace interp {
+
+/// Stack frame storing temporaries and parameters.
+class InterpStack final {
+public:
+  InterpStack() {}
+
+  /// Destroys the stack, freeing up storage.
+  ~InterpStack();
+
+  /// Constructs a value in place on the top of the stack.
+  template <typename T, typename... Tys> void push(Tys &&... Args) {
+    new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...);
+  }
+
+  /// Returns the value from the top of the stack and removes it.
+  template <typename T> T pop() {
+    auto *Ptr = &peek<T>();
+    auto Value = std::move(*Ptr);
+    Ptr->~T();
+    shrink(aligned_size<T>());
+    return Value;
+  }
+
+  /// Discards the top value from the stack.
+  template <typename T> void discard() {
+    auto *Ptr = &peek<T>();
+    Ptr->~T();
+    shrink(aligned_size<T>());
+  }
+
+  /// Returns a reference to the value on the top of the stack.
+  template <typename T> T &peek() {
+    return *reinterpret_cast<T *>(peek(aligned_size<T>()));
+  }
+
+  /// Returns a pointer to the top object.
+  void *top() { return Chunk ? peek(0) : nullptr; }
+
+  /// Returns the size of the stack in bytes.
+  size_t size() const { return StackSize; }
+
+  /// Clears the stack without calling any destructors.
+  void clear();
+
+private:
+  /// All stack slots are aligned to the native pointer alignment for storage.
+  template <typename T> constexpr size_t aligned_size() const {
+    static_assert(alignof(void *) % alignof(T) == 0, "invalid alignment");
+    return ((sizeof(T) + alignof(void *) - 1) / alignof(void *)) *
+           alignof(void *);
+  }
+
+  /// Grows the stack to accomodate a value and returns a pointer to it.
+  void *grow(size_t Size);
+  /// Returns a pointer from the top of the stack.
+  void *peek(size_t Size);
+  /// Shrinks the stack.
+  void shrink(size_t Size);
+
+  /// Allocate stack space in 1Mb chunks.
+  static constexpr size_t ChunkSize = 1024 * 1024;
+
+  /// Metadata for each stack chunk.
+  ///
+  /// The stack is composed of a linked list of chunks. Whenever an allocation
+  /// is out of bounds, a new chunk is linked. When a chunk becomes empty,
+  /// it is not immediately freed: a chunk is deallocated only when the
+  /// predecessor becomes empty.
+  struct StackChunk {
+    StackChunk *Next;
+    StackChunk *Prev;
+    char *End;
+
+    StackChunk(StackChunk *Prev = nullptr)
+        : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {}
+
+    /// Returns the size of the chunk, minus the header.
+    size_t size() { return End - start(); }
+
+    /// Returns a pointer to the start of the data region.
+    char *start() { return reinterpret_cast<char *>(this + 1); }
+  };
+  static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size");
+
+  /// First chunk on the stack.
+  StackChunk *Chunk = nullptr;
+  /// Total size of the stack.
+  size_t StackSize = 0;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/InterpStack.cpp

+//===--- InterpStack.cpp - Stack implementation for the VM ------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "InterpStack.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+InterpStack::~InterpStack() {
+  clear();
+}
+
+void InterpStack::clear() {
+  if (Chunk && Chunk->Next)
+    free(Chunk->Next);
+  if (Chunk)
+    free(Chunk);
+  Chunk = nullptr;
+  StackSize = 0;
+}
+
+void *InterpStack::grow(size_t Size) {
+  assert(Size < ChunkSize - sizeof(StackChunk) && "Object too large");
+
+  if (!Chunk || sizeof(StackChunk) + Chunk->size() + Size > ChunkSize) {
+    if (Chunk && Chunk->Next) {
+      Chunk = Chunk->Next;
+    } else {
+      StackChunk *Next = new (malloc(ChunkSize)) StackChunk(Chunk);
+      if (Chunk)
+        Chunk->Next = Next;
+      Chunk = Next;
+    }
+  }
+
+  auto Object = Chunk->End;
+  Chunk->End += Size;
+  StackSize += Size;
+  return reinterpret_cast<void *>(Object);
+}
+
+void *InterpStack::peek(size_t Size) {
+  assert(Chunk && "Stack is empty!");
+
+  StackChunk *Ptr = Chunk;
+  while (Size > Ptr->size()) {
+    Size -= Ptr->size();
+    Ptr = Ptr->Prev;
+    assert(Ptr && "Offset too large");
+  }
+
+  return reinterpret_cast<void *>(Ptr->End - Size);
+}
+
+void InterpStack::shrink(size_t Size) {
+  assert(Chunk && "Chunk is empty!");
+
+  while (Size > Chunk->size()) {
+    Size -= Chunk->size();
+    if (Chunk->Next) {
+      free(Chunk->Next);
+      Chunk->Next = nullptr;
+    }
+    Chunk->End = Chunk->start();
+    Chunk = Chunk->Prev;
+    assert(Chunk && "Offset too large");
+  }
+
+  Chunk->End -= Size;
+  StackSize -= Size;
+}

clang/lib/AST/Interp/InterpState.h

+//===--- InterpState.h - Interpreter state for the constexpr VM -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Definition of the interpreter state and entry point.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_INTERPSTATE_H
+#define LLVM_CLANG_AST_INTERP_INTERPSTATE_H
+
+#include "Context.h"
+#include "Function.h"
+#include "InterpStack.h"
+#include "State.h"
+#include "clang/AST/APValue.h"
+#include "clang/AST/ASTDiagnostic.h"
+#include "clang/AST/Expr.h"
+#include "clang/Basic/OptionalDiagnostic.h"
+
+namespace clang {
+namespace interp {
+class Context;
+class Function;
+class InterpStack;
+class InterpFrame;
+class SourceMapper;
+
+/// Interpreter context.
+class InterpState final : public State, public SourceMapper {
+public:
+  InterpState(State &Parent, Program &P, InterpStack &Stk, Context &Ctx,
+              SourceMapper *M = nullptr);
+
+  ~InterpState();
+
+  // Stack frame accessors.
+  Frame *getSplitFrame() { return Parent.getCurrentFrame(); }
+  Frame *getCurrentFrame() override;
+  unsigned getCallStackDepth() override { return CallStackDepth; }
+  const Frame *getBottomFrame() const override {
+    return Parent.getBottomFrame();
+  }
+
+  // Acces objects from the walker context.
+  Expr::EvalStatus &getEvalStatus() const override {
+    return Parent.getEvalStatus();
+  }
+  ASTContext &getCtx() const override { return Parent.getCtx(); }
+
+  // Forward status checks and updates to the walker.
+  bool checkingForOverflow() const override {
+    return Parent.checkingForOverflow();
+  }
+  bool checkingPotentialConstantExpression() const override {
+    return Parent.checkingPotentialConstantExpression();
+  }
+  bool noteUndefinedBehavior() override {
+    return Parent.noteUndefinedBehavior();
+  }
+  bool hasActiveDiagnostic() override { return Parent.hasActiveDiagnostic(); }
+  void setActiveDiagnostic(bool Flag) override {
+    Parent.setActiveDiagnostic(Flag);
+  }
+  void setFoldFailureDiagnostic(bool Flag) override {
+    Parent.setFoldFailureDiagnostic(Flag);
+  }
+  bool hasPriorDiagnostic() override { return Parent.hasPriorDiagnostic(); }
+
+  /// Reports overflow and return true if evaluation should continue.
+  bool reportOverflow(const Expr *E, const llvm::APSInt &Value);
+
+  /// Deallocates a pointer.
+  void deallocate(Block *B);
+
+  /// Delegates source mapping to the mapper.
+  SourceInfo getSource(Function *F, CodePtr PC) const override {
+    return M ? M->getSource(F, PC) : F->getSource(PC);
+  }
+
+private:
+  /// AST Walker state.
+  State &Parent;
+  /// Dead block chain.
+  DeadBlock *DeadBlocks = nullptr;
+  /// Reference to the offset-source mapping.
+  SourceMapper *M;
+
+public:
+  /// Reference to the module containing all bytecode.
+  Program &P;
+  /// Temporary stack.
+  InterpStack &Stk;
+  /// Interpreter Context.
+  Context &Ctx;
+  /// The current frame.
+  InterpFrame *Current = nullptr;
+  /// Call stack depth.
+  unsigned CallStackDepth;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/InterpState.cpp

+//===--- InterpState.cpp - Interpreter for the constexpr VM -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "InterpState.h"
+#include "Function.h"
+#include "InterpFrame.h"
+#include "InterpStack.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "State.h"
+#include "Type.h"
+#include <limits>
+
+using namespace clang;
+using namespace clang::interp;
+
+using APSInt = llvm::APSInt;
+
+InterpState::InterpState(State &Parent, Program &P, InterpStack &Stk,
+                         Context &Ctx, SourceMapper *M)
+    : Parent(Parent), M(M), P(P), Stk(Stk), Ctx(Ctx), Current(nullptr),
+      CallStackDepth(Parent.getCallStackDepth() + 1) {}
+
+InterpState::~InterpState() {
+  while (Current) {
+    InterpFrame *Next = Current->Caller;
+    delete Current;
+    Current = Next;
+  }
+
+  while (DeadBlocks) {
+    DeadBlock *Next = DeadBlocks->Next;
+    free(DeadBlocks);
+    DeadBlocks = Next;
+  }
+}
+
+Frame *InterpState::getCurrentFrame() {
+  if (Current && Current->Caller) {
+    return Current;
+  } else {
+    return Parent.getCurrentFrame();
+  }
+}
+
+bool InterpState::reportOverflow(const Expr *E, const llvm::APSInt &Value) {
+  QualType Type = E->getType();
+  CCEDiag(E, diag::note_constexpr_overflow) << Value << Type;
+  return noteUndefinedBehavior();
+}
+
+void InterpState::deallocate(Block *B) {
+  Descriptor *Desc = B->getDescriptor();
+  if (B->hasPointers()) {
+    size_t Size = B->getSize();
+
+    // Allocate a new block, transferring over pointers.
+    char *Memory = reinterpret_cast<char *>(malloc(sizeof(DeadBlock) + Size));
+    auto *D = new (Memory) DeadBlock(DeadBlocks, B);
+
+    // Move data from one block to another.
+    if (Desc->MoveFn)
+      Desc->MoveFn(B, B->data(), D->data(), Desc);
+  } else {
+    // Free storage, if necessary.
+    if (Desc->DtorFn)
+      Desc->DtorFn(B, B->data(), Desc);
+  }
+}

clang/lib/AST/Interp/LinkEmitter.h

+//===--- LinkEmitter.h - Instruction emitter for the VM ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the instruction emitters.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_LINKEMITTER_H
+#define LLVM_CLANG_AST_INTERP_LINKEMITTER_H
+
+#include "ByteCodeGenError.h"
+#include "Context.h"
+#include "InterpStack.h"
+#include "InterpState.h"
+#include "Program.h"
+#include "Source.h"
+#include "Type.h"
+#include "llvm/Support/Error.h"
+
+namespace clang {
+namespace interp {
+class Context;
+class SourceInfo;
+enum Opcode : uint32_t;
+
+/// An emitter which links the program to bytecode for later use.
+class LinkEmitter {
+protected:
+  using LabelTy = uint32_t;
+  using AddrTy = uintptr_t;
+  using Local = Scope::Local;
+
+public:
+  /// Compiles the function into the module.
+  llvm::Expected<Function *> compileFunc(const FunctionDecl *F);
+
+protected:
+  LinkEmitter(Context &Ctx, State &S, Program &P) : Ctx(Ctx), P(P) {}
+
+  virtual ~LinkEmitter() {}
+
+  /// Define a label.
+  void emitLabel(LabelTy Label);
+  /// Create a label.
+  LabelTy getLabel() { return ++NextLabel; }
+
+  /// Methods implemented by the compiler.
+  virtual bool compile(const FunctionDecl *E) = 0;
+  virtual bool compile(const Expr *E) = 0;
+  virtual bool compile(const VarDecl *E) = 0;
+
+  /// Bails out if a given node cannot be compiled.
+  bool bail(const Stmt *S) { return bail(S->getBeginLoc()); }
+  bool bail(const Decl *D) { return bail(D->getBeginLoc()); }
+  bool bail(const SourceLocation &Loc);
+
+  /// Emits jumps.
+  bool jumpTrue(const LabelTy &Label);
+  bool jumpFalse(const LabelTy &Label);
+  bool jump(const LabelTy &Label);
+  bool fallthrough(const LabelTy &Label) { return true; }
+
+  /// Callback for local registration.
+  Local createLocal(Descriptor *D);
+
+  /// Parameter indices.
+  llvm::DenseMap<const ParmVarDecl *, unsigned> Params;
+  /// Local descriptors.
+  llvm::SmallVector<SmallVector<Local, 8>, 2> Descriptors;
+
+private:
+  /// Current compilation context.
+  Context &Ctx;
+  /// Program to link to.
+  Program &P;
+  /// Index of the next available label.
+  LabelTy NextLabel = 0;
+  /// Offset of the next local variable.
+  unsigned NextLocalOffset = 0;
+  /// Location of a failure.
+  llvm::Optional<SourceLocation> BailLocation;
+  /// Label information for linker.
+  llvm::DenseMap<LabelTy, unsigned> LabelOffsets;
+  /// Location of label relocations.
+  llvm::DenseMap<LabelTy, llvm::SmallVector<unsigned, 5>> LabelRelocs;
+  /// Program code.
+  std::vector<char> Code;
+  /// Opcode to expression mapping.
+  SourceMap SrcMap;
+
+  /// Returns the offset for a jump or records a relocation.
+  int32_t getOffset(LabelTy Label);
+
+  /// Emits an opcode.
+  template <typename... Tys>
+  bool emitOp(Opcode Op, const Tys &... Args, const SourceInfo &L);
+
+protected:
+#define GET_LINK_PROTO
+#include "Opcodes.inc"
+#undef GET_LINK_PROTO
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/LinkEmitter.cpp

+//===--- LinkEmitter.cpp - Instruction emitter for the VM -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "LinkEmitter.h"
+#include "Context.h"
+#include "Opcode.h"
+#include "Program.h"
+#include "clang/AST/DeclCXX.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+using APSInt = llvm::APSInt;
+using Error = llvm::Error;
+
+Expected<Function *> LinkEmitter::compileFunc(const FunctionDecl *F) {
+  // Set up argument indices.
+  unsigned ParamOffset = 0;
+  SmallVector<PrimType, 8> ParamTypes;
+  llvm::DenseMap<unsigned, Function::ParamDescriptor> ParamDescriptors;
+
+  // If the return is not a primitive, a pointer to the storage where the value
+  // is initialized in is passed as the first argument.
+  if (Ctx.isComposite(F->getReturnType())) {
+    ParamTypes.push_back(PT_Ptr);
+    ParamOffset += align(primSize(PT_Ptr));
+  }
+
+  // Assign descriptors to all parameters.
+  // Composite objects are lowered to pointers.
+  for (auto *PD : F->parameters()) {
+    PrimType Ty;
+    if (auto T = Ctx.classify(PD->getType())) {
+      Ty = *T;
+    } else {
+      Ty = PT_Ptr;
+    }
+
+    auto *Desc = P.createDescriptor(PD, Ty);
+    ParamDescriptors.insert({ParamOffset, {Ty, Desc}});
+    Params.insert({PD, ParamOffset});
+    ParamOffset += align(primSize(Ty));
+    ParamTypes.push_back(Ty);
+  }
+
+  // Compile the function body.
+  if (!compile(F))
+    return llvm::make_error<ByteCodeGenError>(*BailLocation);
+
+  // Create scopes from descriptors.
+  llvm::SmallVector<Scope, 2> Scopes;
+  for (auto &DS : Descriptors) {
+    Scopes.emplace_back(std::move(DS));
+  }
+
+  // Create a handle over the emitted code.
+  return P.createFunction(F, NextLocalOffset, ParamOffset, std::move(Code),
+                          std::move(SrcMap), std::move(Scopes),
+                          std::move(ParamTypes), std::move(ParamDescriptors));
+}
+
+Scope::Local LinkEmitter::createLocal(Descriptor *D) {
+  NextLocalOffset += sizeof(Block);
+  unsigned Location = NextLocalOffset;
+  NextLocalOffset += align(D->Size);
+  return {Location, D};
+}
+
+void LinkEmitter::emitLabel(LabelTy Label) {
+  const size_t Target = Code.size();
+  LabelOffsets.insert({Label, Target});
+  auto It = LabelRelocs.find(Label);
+  if (It != LabelRelocs.end()) {
+    for (unsigned Reloc : It->second) {
+      using namespace llvm::support;
+
+      /// Rewrite the operand of all jumps to this label.
+      void *Location = Code.data() + Reloc - sizeof(int32_t);
+      const int32_t Offset = Target - static_cast<int64_t>(Reloc);
+      endian::write<int32_t, endianness::native, 1>(Location, Offset);
+    }
+    LabelRelocs.erase(It);
+  }
+}
+
+int32_t LinkEmitter::getOffset(LabelTy Label) {
+  // Compute the PC offset which the jump is relative to.
+  const int64_t Position = Code.size() + sizeof(Opcode) + sizeof(int32_t);
+
+  // If target is known, compute jump offset.
+  auto It = LabelOffsets.find(Label);
+  if (It != LabelOffsets.end()) {
+    return It->second - Position;
+  }
+
+  // Otherwise, record relocation and return dummy offset.
+  LabelRelocs[Label].push_back(Position);
+  return 0ull;
+}
+
+bool LinkEmitter::bail(const SourceLocation &Loc) {
+  if (!BailLocation)
+    BailLocation = Loc;
+  return false;
+}
+
+template <typename... Tys>
+bool LinkEmitter::emitOp(Opcode Op, const Tys &... Args, const SourceInfo &SI) {
+  bool Success = true;
+
+  /// Helper to write bytecode and bail out if 32-bit offsets become invalid.
+  auto emit = [this, &Success](const char *Data, size_t Size) {
+    if (Code.size() + Size > std::numeric_limits<unsigned>::max()) {
+      Success = false;
+      return;
+    }
+    Code.insert(Code.end(), Data, Data + Size);
+  };
+
+  /// The opcode is followed by arguments. The source info is
+  /// attached to the address after the opcode.
+  emit(reinterpret_cast<const char *>(&Op), sizeof(Opcode));
+  if (SI)
+    SrcMap.emplace_back(Code.size(), SI);
+
+  /// The initializer list forces the expression to be evaluated
+  /// for each argument in the variadic template, in order.
+  (void)std::initializer_list<int>{
+      (emit(reinterpret_cast<const char *>(&Args), sizeof(Args)), 0)...};
+
+  return Success;
+}
+
+bool LinkEmitter::jumpTrue(const LabelTy &Label) {
+  return emitJt(getOffset(Label), {});
+}
+
+bool LinkEmitter::jumpFalse(const LabelTy &Label) {
+  return emitJf(getOffset(Label), {});
+}
+
+bool LinkEmitter::jump(const LabelTy &Label) {
+  return emitJmp(getOffset(Label), {});
+}
+
+//===----------------------------------------------------------------------===//
+// Opcode emitters
+//===----------------------------------------------------------------------===//
+
+#define GET_LINK_IMPL
+#include "Opcodes.inc"
+#undef GET_LINK_IMPL

clang/lib/AST/Interp/Opcode.h

+//===--- Opcode.h - Opcodes for the constexpr VM ----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines all opcodes executed by the VM and emitted by the compiler.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_OPCODE_H
+#define LLVM_CLANG_AST_INTERP_OPCODE_H
+
+#include <cstdint>
+
+namespace clang {
+namespace interp {
+
+enum Opcode : uint32_t {
+#define GET_OPCODE_NAMES
+#include "Opcodes.inc"
+#undef GET_OPCODE_NAMES
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Opcodes.td

+//===--- Opcodes.td - Opcode defitions for the constexpr VM -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Helper file used to generate opcodes, the interpreter and the disassembler.
+//
+//===----------------------------------------------------------------------===//
+
+
+//===----------------------------------------------------------------------===//
+// Types evaluated by the interpreter.
+//===----------------------------------------------------------------------===//
+
+class Type;
+def Bool : Type;
+def Sint8 : Type;
+def Uint8 : Type;
+def Sint16 : Type;
+def Uint16 : Type;
+def Sint32 : Type;
+def Uint32 : Type;
+def Sint64 : Type;
+def Uint64 : Type;
+def Ptr : Type;
+
+//===----------------------------------------------------------------------===//
+// Types transferred to the interpreter.
+//===----------------------------------------------------------------------===//
+
+class ArgType { string Name = ?; }
+def ArgSint8 : ArgType { let Name = "int8_t"; }
+def ArgUint8 : ArgType { let Name = "uint8_t"; }
+def ArgSint16 : ArgType { let Name = "int16_t"; }
+def ArgUint16 : ArgType { let Name = "uint16_t"; }
+def ArgSint32 : ArgType { let Name = "int32_t"; }
+def ArgUint32 : ArgType { let Name = "uint32_t"; }
+def ArgSint64 : ArgType { let Name = "int64_t"; }
+def ArgUint64 : ArgType { let Name = "uint64_t"; }
+def ArgBool : ArgType { let Name = "bool"; }
+def ArgPtr : ArgType { let Name = "uintptr_t"; }
+
+//===----------------------------------------------------------------------===//
+// Classes of types intructions operate on.
+//===----------------------------------------------------------------------===//
+
+class TypeClass {
+  list<Type> Types;
+}
+
+def AluTypeClass : TypeClass {
+  let Types = [Sint8, Uint8, Sint16, Uint16, Sint32,
+               Uint32, Sint64, Uint64, Bool];
+}
+
+def AllTypeClass : TypeClass {
+  let Types = !listconcat(AluTypeClass.Types, [Ptr]);
+}
+
+class SingletonTypeClass<Type Ty> : TypeClass {
+  let Types = [Ty];
+}
+
+//===----------------------------------------------------------------------===//
+// Record describing all opcodes.
+//===----------------------------------------------------------------------===//
+
+class Opcode {
+  list<TypeClass> Types = [];
+  list<ArgType> Args = [];
+  string Name = "";
+  bit CanReturn = 0;
+  bit ChangesPC = 0;
+  bit HasCustomLink = 0;
+  bit HasCustomEval = 0;
+  bit HasGroup = 0;
+}
+
+class AluOpcode : Opcode {
+  let Types = [AluTypeClass];
+  let HasGroup = 1;
+}
+
+class AluRealOpcode : Opcode {
+  let Types = [AluTypeClass];
+  let HasGroup = 1;
+}
+
+//===----------------------------------------------------------------------===//
+// Jump opcodes
+//===----------------------------------------------------------------------===//
+
+class JumpOpcode : Opcode {
+  let Args = [ArgSint32];
+  let ChangesPC = 1;
+  let HasCustomEval = 1;
+}
+
+def Jmp : JumpOpcode;
+def Jt : JumpOpcode;
+def Jf : JumpOpcode;
+
+//===----------------------------------------------------------------------===//
+// Returns
+//===----------------------------------------------------------------------===//
+
+def Ret : Opcode {
+  let Types = [AllTypeClass];
+  let ChangesPC = 1;
+  let CanReturn = 1;
+  let HasGroup = 1;
+  let HasCustomEval = 1;
+}
+def RetVoid : Opcode {
+  let CanReturn = 1;
+  let ChangesPC = 1;
+  let HasCustomEval = 1;
+}
+def NoRet : Opcode {}
+
+//===----------------------------------------------------------------------===//
+// Frame management
+//===----------------------------------------------------------------------===//
+
+def Destroy : Opcode {
+  let Args = [ArgUint32];
+  let HasCustomEval = 1;
+}
+
+//===----------------------------------------------------------------------===//
+// Constants
+//===----------------------------------------------------------------------===//
+
+class ConstOpcode<Type Ty, ArgType ArgTy> : Opcode {
+  let Types = [SingletonTypeClass<Ty>];
+  let Args = [ArgTy];
+  let Name = "Const";
+}
+
+def ConstSint8 : ConstOpcode<Sint8, ArgSint8>;
+def ConstUint8 : ConstOpcode<Uint8, ArgUint8>;
+def ConstSint16 : ConstOpcode<Sint16, ArgSint16>;
+def ConstUint16 : ConstOpcode<Uint16, ArgUint16>;
+def ConstSint32 : ConstOpcode<Sint32, ArgSint32>;
+def ConstUint32 : ConstOpcode<Uint32, ArgUint32>;
+def ConstSint64 : ConstOpcode<Sint64, ArgSint64>;
+def ConstUint64 : ConstOpcode<Uint64, ArgUint64>;
+def ConstBool : ConstOpcode<Bool, ArgBool>;
+
+def Zero : Opcode {
+  let Types = [AluTypeClass];
+}
+
+def NullPtr : Opcode;
+
+//===----------------------------------------------------------------------===//
+// Pointer generation
+//===----------------------------------------------------------------------===//
+
+def GetPtrLocal : Opcode {
+  let Args = [ArgUint32];
+  bit HasCustomEval = 1;
+}
+def GetPtrParam : Opcode {
+  let Args = [ArgUint32];
+}
+
+def Undef : Opcode;
+
+//===----------------------------------------------------------------------===//
+// Direct field accessors
+//===----------------------------------------------------------------------===//
+
+class AccessOpcode : Opcode {
+  let Types = [AllTypeClass];
+  let Args = [ArgUint32];
+  let HasGroup = 1;
+}
+
+def GetLocal : AccessOpcode { let HasCustomEval = 1; }
+def SetLocal : AccessOpcode { let HasCustomEval = 1; }
+
+def GetParam : AccessOpcode;
+def SetParam : AccessOpcode;
+
+//===----------------------------------------------------------------------===//
+// Pointer access
+//===----------------------------------------------------------------------===//
+
+class LoadOpcode : Opcode {
+  let Types = [AllTypeClass];
+  let HasGroup = 1;
+}
+
+def Load : LoadOpcode {}
+def LoadPop : LoadOpcode {}
+
+class StoreOpcode : Opcode {
+  let Types = [AllTypeClass];
+  let HasGroup = 1;
+}
+
+def Store : StoreOpcode {}
+def StorePop : StoreOpcode {}
+
+def Init : StoreOpcode {}
+
+//===----------------------------------------------------------------------===//
+// Binary operators.
+//===----------------------------------------------------------------------===//
+
+def Sub : AluRealOpcode;
+def Add : AluRealOpcode;
+def Mul : AluRealOpcode;
+def Div : AluRealOpcode;
+def Rem : AluOpcode;
+
+//===----------------------------------------------------------------------===//
+// Comparison opcodes.
+//===----------------------------------------------------------------------===//
+
+class ComparisonOpcode : Opcode {
+  let Types = [AllTypeClass];
+  let HasGroup = 1;
+}
+
+def EQ : ComparisonOpcode;
+def NE : ComparisonOpcode;
+def LT : ComparisonOpcode;
+def LE : ComparisonOpcode;
+def GT : ComparisonOpcode;
+def GE : ComparisonOpcode;
+
+//===----------------------------------------------------------------------===//
+// Stack management.
+//===----------------------------------------------------------------------===//
+
+def Pop : Opcode {
+  let Types = [AllTypeClass];
+  let HasGroup = 1;
+}
+
+def Dup : Opcode {
+  let Types = [AllTypeClass];
+  let HasGroup = 1;
+}

clang/lib/AST/Interp/Pointer.h

+//===--- Pointer.h - Types for the constexpr VM -----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the classes responsible for pointer tracking.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_POINTER_H
+#define LLVM_CLANG_AST_INTERP_POINTER_H
+
+#include "Descriptor.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+#include "llvm/ADT/PointerUnion.h"
+
+namespace clang {
+namespace interp {
+class Block;
+class DeadBlock;
+class Context;
+class InterpState;
+class Pointer;
+enum PrimType : unsigned;
+
+/// A memory block, either on the stack or in the heap.
+///
+/// The storage described by the block immediately follows it in memory.
+class Block {
+public:
+  // Creates a new block.
+  Block(Descriptor *Desc, bool IsStatic = false, bool IsExtern = false)
+      : IsStatic(IsStatic), IsExtern(IsExtern), Desc(Desc) {}
+
+  /// Returns the block's descriptor.
+  Descriptor *getDescriptor() const { return Desc; }
+  /// Checks if the block has any live pointers.
+  bool hasPointers() const { return Pointers; }
+  /// Checks if the block is extern.
+  bool isExtern() const { return IsExtern; }
+  /// Checks if the block has static storage duration.
+  bool isStatic() const { return IsStatic; }
+  /// Returns the size of the block.
+  InterpSize getSize() const { return Desc->Size; }
+
+  /// Returns a pointer to the stored data.
+  char *data() { return reinterpret_cast<char *>(this + 1); }
+
+protected:
+  friend class Pointer;
+  friend class DeadBlock;
+  friend class InterpState;
+
+  Block(Descriptor *Desc, bool IsExtern, bool IsStatic, bool IsDead)
+    : IsStatic(IsStatic), IsExtern(IsExtern), IsDead(true), Desc(Desc) {}
+
+  // Deletes a dead block at the end of its lifetime.
+  void cleanup();
+
+  // Pointer chain management.
+  void addPointer(Pointer *P);
+  void removePointer(Pointer *P);
+  void movePointer(Pointer *From, Pointer *To);
+
+  /// Start of the chain of pointers.
+  Pointer *Pointers = nullptr;
+  /// Flag indicating if the block has static storage duration.
+  bool IsStatic = false;
+  /// Flag indicating if the block is an extern.
+  bool IsExtern = false;
+  /// Flag indicating if the pointer is dead.
+  bool IsDead = false;
+  /// Pointer to the stack slot descriptor.
+  Descriptor *Desc;
+};
+
+/// Descriptor for a dead block.
+///
+/// Dead blocks are chained in a double-linked list to deallocate them
+/// whenever pointers become dead.
+class DeadBlock {
+public:
+  /// Copies the block.
+  DeadBlock(DeadBlock *&Root, Block *Blk);
+
+  /// Returns a pointer to the stored data.
+  char *data() { return B.data(); }
+
+private:
+  friend class Block;
+  friend class InterpState;
+
+  void free();
+
+  /// Root pointer of the list.
+  DeadBlock *&Root;
+  /// Previous block in the list.
+  DeadBlock *Prev;
+  /// Next block in the list.
+  DeadBlock *Next;
+
+  /// Actual block storing data and tracking pointers.
+  Block B;
+};
+
+/// A pointer to a memory block, live or dead.
+///
+/// This object can be allocated into interpreter stack frames. If pointing to
+/// a live block, it is a link in the chain of pointers pointing to the block.
+class Pointer {
+public:
+  Pointer() {}
+  Pointer(Block *B);
+  Pointer(const Pointer &P);
+  Pointer(Pointer &&P);
+  ~Pointer();
+
+  void operator=(const Pointer &P);
+  void operator=(Pointer &&P);
+
+  /// Converts the pointer to an APValue.
+  llvm::Optional<APValue> toAPValue() const;
+
+  /// Offsets a pointer inside an array.
+  Pointer atOffset(unsigned Off) const {
+    if (getFieldDesc()->ElemDesc)
+      Off += sizeof(InlineDescriptor);
+    return Pointer(Pointee, Base, Base + Off);
+  }
+
+  /// Creates a pointer to a field.
+  Pointer atField(unsigned Off) const {
+    unsigned Field = Offset + Off;
+    return Pointer(Pointee, Field, Field);
+  }
+
+  /// Narrows a pointer to a field.
+  Pointer narrow() const {
+    return Pointer(Pointee, Offset, Offset);
+  }
+
+  /// Expands a pointer to the container.
+  Pointer expand() const {
+    if (Base == 0)
+      return *this;
+    return getBase();
+  }
+
+  /// Checks if the pointer is null.
+  bool isNull() const { return Pointee == nullptr; }
+  /// Checks if the pointer is live.
+  bool isLive() const { return Pointee && !Pointee->IsDead; }
+  /// Checks if the pointer is in bounds.
+  bool inBounds() const { return Offset < Base + size(); }
+  /// Checks if the item is a field in an object.
+  bool isField() const { return Base != 0; }
+
+  /// Accessor for information about the declaration site.
+  Descriptor *getDeclDesc() const { return Pointee->Desc; }
+  SourceLocation getDeclLoc() const { return getDeclDesc()->getLocation(); }
+
+  /// Returns a pointer to the object of which this pointer is a field.
+  Pointer getBase() const {
+    assert(Base != 0 && "Not a nested pointer");
+    unsigned NewBase = Base - getInlineDescriptor()->Offset;
+    Descriptor *Desc;
+    if (NewBase == 0) {
+      Desc = Pointee->Desc;
+    } else {
+      auto *I = reinterpret_cast<InlineDescriptor *>(Pointee->data() + NewBase);
+      Desc = (I - 1)->Desc;
+    }
+    unsigned Start = Desc->ElemDesc ? sizeof(InlineDescriptor) : 0;
+    return Pointer(Pointee, NewBase, NewBase + Start);
+  }
+
+  /// Accessors for information about the innermost field.
+  Descriptor *getFieldDesc() const {
+    if (Base == 0)
+      return getDeclDesc();
+    return getInlineDescriptor()->Desc;
+  }
+
+  /// Returns the type of the innermost field.
+  QualType getType() const { return getFieldDesc()->getType(); }
+  /// Returns the element size of the innermost field.
+  size_t elemSize() const { return getFieldDesc()->ElemSize; }
+  /// Returns the total size of the innermost field.
+  size_t size() const { return getFieldDesc()->Size; }
+  /// Checks if the innermost field is an array.
+  bool isArray() const { return getFieldDesc()->IsArray; }
+  /// Checks if the storage is extern.
+  bool isExtern() const { return Pointee->isExtern(); }
+
+  /// Checks if an object or a subfield is mutable.
+  bool isMutable() const {
+    if (Base == 0)
+      return getDeclDesc()->IsMutable;
+    return getInlineDescriptor()->IsMutable;
+  }
+
+  /// Checks if an object was initialized.
+  bool isInitialized() const {
+    if (Base == 0)
+      return true;
+    return getInlineDescriptor()->IsInitialized;
+  }
+
+  /// Returns the offset into an array.
+  unsigned getOffset() const {
+    if (Offset > Base && getFieldDesc()->ElemDesc)
+      return Offset - Base - sizeof(InlineDescriptor);
+    return Offset - Base;
+  }
+  /// Returns the index into an array.
+  int64_t getIndex() const { return getOffset() / elemSize(); }
+  /// Checks if the declaration is a temporary.
+  bool isTemporary() const { return getDeclDesc()->IsTemporary; }
+
+  /// Dereferences the pointer, if it's live.
+  template <typename T> T &deref() const {
+    assert(isLive() && "Invalid pointer");
+    return *reinterpret_cast<T *>(Pointee->data() + Offset);
+  }
+
+  /// Initializes a field.
+  void initialize() const {
+    assert(Base != 0 && "Only fields can be initialised");
+    getInlineDescriptor()->IsInitialized = true;
+  }
+
+  /// Checks if two pointers are comparable.
+  static bool isComparable(const Pointer &A, const Pointer &B);
+
+private:
+  friend class Block;
+  friend class DeadBlock;
+
+  Pointer(Block *Pointee, unsigned Base, unsigned Offset);
+
+  /// Returns the embedded descriptor preceding a field.
+  InlineDescriptor *getInlineDescriptor() const {
+    assert(Base != 0 && "Not a nested pointer");
+    return reinterpret_cast<InlineDescriptor *>(Pointee->data() + Base) - 1;
+  }
+
+  /// The block the pointer is pointing to.
+  Block *Pointee = nullptr;
+  /// Start of the current subfield.
+  unsigned Base = 0;
+  /// Offset into the block.
+  unsigned Offset = 0;
+
+  /// Previous link in the pointer chain.
+  Pointer *Prev = nullptr;
+  /// Next link in the pointer chain.
+  Pointer *Next = nullptr;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Pointer.cpp

+//===--- Pointer.cpp - Types for the constexpr VM ---------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Pointer.h"
+#include "Type.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+void Block::addPointer(Pointer *P) {
+  if (IsStatic)
+    return;
+  if (Pointers) {
+    Pointers->Prev = P;
+  }
+  P->Next = Pointers;
+  P->Prev = nullptr;
+  Pointers = P;
+}
+
+void Block::removePointer(Pointer *P) {
+  if (IsStatic)
+    return;
+  if (Pointers == P)
+    Pointers = P->Next;
+  if (P->Prev)
+    P->Prev->Next = P->Next;
+  if (P->Next)
+    P->Next->Prev = P->Prev;
+}
+
+void Block::cleanup() {
+  if (Pointers == nullptr && IsDead)
+    (reinterpret_cast<DeadBlock *>(this + 1) - 1)->free();
+}
+
+void Block::movePointer(Pointer *From, Pointer *To) {
+  if (IsStatic)
+    return;
+  To->Prev = From->Prev;
+  if (To->Prev)
+    To->Prev->Next = To;
+  To->Next = From->Next;
+  if (To->Next)
+    To->Next->Prev = To;
+  if (Pointers == From)
+    Pointers = To;
+
+  From->Prev = nullptr;
+  From->Next = nullptr;
+}
+
+DeadBlock::DeadBlock(DeadBlock *&Root, Block *Blk)
+    : Root(Root), B(Blk->Desc, Blk->IsStatic, Blk->IsExtern, /*isDead=*/true) {
+  // Add the block to the chain of dead blocks.
+  if (Root)
+    Root->Prev = this;
+
+  Next = Root;
+  Prev = nullptr;
+  Root = this;
+
+  // Transfer pointers.
+  B.Pointers = Blk->Pointers;
+  for (Pointer *P = Blk->Pointers; P; P = P->Next)
+    P->Pointee = &B;
+}
+
+void DeadBlock::free() {
+  if (Prev)
+    Prev->Next = Next;
+  if (Next)
+    Next->Prev = Prev;
+  if (Root == this)
+    Root = Next;
+  ::free(this);
+}
+
+Pointer::Pointer(Block *Pointee) : Pointer(Pointee, 0, 0) {}
+
+Pointer::Pointer(const Pointer &P) : Pointer(P.Pointee, P.Base, P.Offset) {}
+
+Pointer::Pointer(Pointer &&P)
+    : Pointee(P.Pointee), Base(P.Base), Offset(P.Offset) {
+  if (Pointee)
+    Pointee->movePointer(&P, this);
+}
+
+Pointer::Pointer(Block *Pointee, unsigned Base, unsigned Offset)
+    : Pointee(Pointee), Base(Base), Offset(Offset) {
+  assert(Base % alignof(void *) == 0 && "Invalid alignment");
+  if (Pointee)
+    Pointee->addPointer(this);
+}
+
+Pointer::~Pointer() {
+  if (Pointee) {
+    Pointee->removePointer(this);
+    Pointee->cleanup();
+  }
+}
+
+void Pointer::operator=(const Pointer &P) {
+  Block *Old = Pointee;
+
+  if (Pointee)
+    Pointee->removePointer(this);
+
+  Offset = P.Offset;
+  Base = P.Base;
+
+  Pointee = P.Pointee;
+  if (Pointee)
+    Pointee->addPointer(this);
+
+  if (Old)
+    Old->cleanup();
+}
+
+void Pointer::operator=(Pointer &&P) {
+  Block *Old = Pointee;
+
+  if (Pointee)
+    Pointee->removePointer(this);
+
+  Offset = P.Offset;
+  Base = P.Base;
+
+  Pointee = P.Pointee;
+  if (Pointee)
+    Pointee->movePointer(&P, this);
+
+  if (Old)
+    Old->cleanup();
+}
+
+llvm::Optional<APValue> Pointer::toAPValue() const {
+  if (isNull())
+    return {};
+
+  // Build the lvalue base from the block.
+  Descriptor *Desc = getDeclDesc();
+  APValue::LValueBase Base;
+  if (auto *VD = Desc->Source.dyn_cast<const ValueDecl *>())
+    Base = VD;
+  else if (auto *E = Desc->Source.dyn_cast<const Expr *>())
+    Base = E;
+  else
+    llvm_unreachable("Invalid descriptor type");
+
+  // TODO: compute the offset into the object.
+  CharUnits Offset = CharUnits::Zero();
+
+  if (!isField()) {
+    return APValue(Base, Offset, APValue::NoLValuePath());
+  }
+
+  // TODO: return subobject paths.
+  return {};
+}
+
+bool Pointer::isComparable(const Pointer &A, const Pointer &B) {
+  return A.Pointee == B.Pointee;
+}

clang/lib/AST/Interp/Program.h

+//===--- Program.h - Bytecode for the constexpr VM --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a program which organises and links multiple bytecode functions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_PROGRAM_H
+#define LLVM_CLANG_AST_INTERP_PROGRAM_H
+
+#include "Function.h"
+#include "Pointer.h"
+#include "Source.h"
+#include "Type.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
+#include <map>
+#include <vector>
+
+namespace clang {
+class RecordDecl;
+class Expr;
+class FunctionDecl;
+class Stmt;
+class StringLiteral;
+class VarDecl;
+
+namespace interp {
+class Context;
+class Scope;
+
+/// The program contains and links the bytecode for all functions.
+class Program {
+public:
+  Program(Context &Ctx) : Ctx(Ctx) {}
+
+  /// Creates a new function from a code range.
+  template <typename... Ts>
+  Function *createFunction(const FunctionDecl *Def, Ts &&... Args) {
+    auto *Func = new Function(*this, Def, std::forward<Ts>(Args)...);
+    Funcs.insert({Def, std::unique_ptr<Function>(Func)});
+    return Func;
+  }
+
+  /// Creates an anonymous function.
+  template <typename... Ts>
+  Function *createFunction(Ts &&... Args) {
+    auto *Func = new Function(*this, std::forward<Ts>(Args)...);
+    AnonFuncs.emplace_back(Func);
+    return Func;
+  }
+
+  /// Returns a function.
+  Function *getFunction(const FunctionDecl *F);
+
+  /// Creates a descriptor for a primitive type.
+  Descriptor *createDescriptor(const DeclTy &D, PrimType Type,
+                               bool IsMutable = true,
+                               bool IsTemporary = false) {
+    return allocateDescriptor(std::move(D), Type, IsMutable, IsTemporary);
+  }
+
+private:
+  /// Reference to the VM context.
+  Context &Ctx;
+  /// Mapping from decls to cached bytecode functions.
+  llvm::DenseMap<const FunctionDecl *, std::unique_ptr<Function>> Funcs;
+  /// List of anonymous functions.
+  std::vector<std::unique_ptr<Function>> AnonFuncs;
+
+  /// Custom allocator for global storage.
+  using PoolAllocTy = llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator>;
+
+  /// Allocator for globals and descriptors.
+  PoolAllocTy Allocator;
+
+    /// Creates a new descriptor.
+  template <typename... Ts>
+  Descriptor *allocateDescriptor(Ts &&... Args) {
+    return new (Allocator) Descriptor(std::forward<Ts>(Args)...);
+  }
+
+public:
+  /// Dumps the disassembled bytecode to \c llvm::errs().
+  void dump() const;
+  void dump(llvm::raw_ostream &OS) const;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Program.cpp

+//===--- Program.cpp - Bytecode for the constexpr VM ------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Program.h"
+#include "Context.h"
+#include "Function.h"
+#include "Opcode.h"
+#include "Type.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+Function *Program::getFunction(const FunctionDecl *F) {
+  F = F->getDefinition();
+  auto It = Funcs.find(F);
+  return It == Funcs.end() ? nullptr : It->second.get();
+}

clang/lib/AST/Interp/Source.h

+//===--- Source.h - Source location provider for the VM  --------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a program which organises and links multiple bytecode functions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_SOURCE_H
+#define LLVM_CLANG_AST_INTERP_SOURCE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+#include "llvm/Support/Endian.h"
+
+namespace clang {
+namespace interp {
+class Function;
+
+/// Pointer into the code segment.
+class CodePtr {
+public:
+  CodePtr() : Ptr(nullptr) {}
+
+  CodePtr &operator+=(int32_t Offset) {
+    Ptr += Offset;
+    return *this;
+  }
+
+  int32_t operator-(const CodePtr &RHS) const {
+    assert(Ptr != nullptr && RHS.Ptr != nullptr && "Invalid code pointer");
+    return Ptr - RHS.Ptr;
+  }
+
+  CodePtr operator-(size_t RHS) const {
+    assert(Ptr != nullptr && "Invalid code pointer");
+    return CodePtr(Ptr - RHS);
+  }
+
+  bool operator!=(const CodePtr &RHS) const { return Ptr != RHS.Ptr; }
+
+  /// Reads data and advances the pointer.
+  template <typename T> T read() {
+    using namespace llvm::support;
+    T Value = endian::read<T, endianness::native, 1>(Ptr);
+    Ptr += sizeof(T);
+    return Value;
+  }
+
+private:
+  /// Constructor used by Function to generate pointers.
+  CodePtr(const char *Ptr) : Ptr(Ptr) {}
+
+private:
+  friend class Function;
+
+  /// Pointer into the code owned by a function.
+  const char *Ptr;
+};
+
+/// Describes the statement/declaration an opcode was generated from.
+class SourceInfo {
+public:
+  SourceInfo() {}
+  SourceInfo(const Stmt *E) : Source(E) {}
+  SourceInfo(const VarDecl *D) : Source(D) {}
+
+  SourceLocation getLoc() const;
+
+  const Stmt *asStmt() const { return Source.dyn_cast<const Stmt *>(); }
+  const VarDecl *asDecl() const { return Source.dyn_cast<const VarDecl *>(); }
+  const Expr *asExpr() const;
+
+  operator bool() const { return !Source.isNull(); }
+
+private:
+  llvm::PointerUnion<const VarDecl *, const Stmt *> Source;
+};
+
+using SourceMap = std::vector<std::pair<unsigned, SourceInfo>>;
+
+/// Interface for classes which map locations to sources.
+class SourceMapper {
+public:
+  virtual ~SourceMapper() {}
+
+  /// Returns source information for a given PC in a function.
+  virtual SourceInfo getSource(Function *F, CodePtr PC) const = 0;
+
+  /// Returns the expression if an opcode belongs to one, null otherwise.
+  const Expr *getExpr(Function *F, CodePtr PC) const;
+  /// Returns the location from which an opcode originates.
+  SourceLocation getLocation(Function *F, CodePtr PC) const;
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/Source.cpp

+//===--- Source.cpp - Source expression tracking ----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Source.h"
+#include "clang/AST/Expr.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+SourceLocation SourceInfo::getLoc() const {
+  if (auto *E = asExpr())
+    return E->getExprLoc();
+  if (auto *S = asStmt())
+    return S->getBeginLoc();
+  if (auto *D = asDecl())
+    return D->getBeginLoc();
+  return SourceLocation();
+}
+
+const Expr *SourceInfo::asExpr() const {
+  if (auto *S = Source.dyn_cast<const Stmt *>())
+    return dyn_cast<Expr>(S);
+  return nullptr;
+}
+
+const Expr *SourceMapper::getExpr(Function *F, CodePtr PC) const {
+  if (auto *E = getSource(F, PC).asExpr())
+    return E;
+  llvm::report_fatal_error("missing source expression");
+}
+
+SourceLocation SourceMapper::getLocation(Function *F, CodePtr PC) const {
+  return getSource(F, PC).getLoc();
+}

clang/lib/AST/Interp/State.h

+//===--- State.h - State chain for the VM and AST Walker --------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the base class of the interpreter and evaluator state.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_STATE_H
+#define LLVM_CLANG_AST_INTERP_STATE_H
+
+#include "clang/AST/ASTDiagnostic.h"
+#include "clang/AST/Expr.h"
+#include "clang/Basic/OptionalDiagnostic.h"
+
+namespace clang {
+
+/// Kinds of access we can perform on an object, for diagnostics. Note that
+/// we consider a member function call to be a kind of access, even though
+/// it is not formally an access of the object, because it has (largely) the
+/// same set of semantic restrictions.
+enum AccessKinds {
+  AK_Read,
+  AK_Assign,
+  AK_Increment,
+  AK_Decrement,
+  AK_MemberCall,
+  AK_DynamicCast,
+  AK_TypeId,
+};
+
+// The order of this enum is important for diagnostics.
+enum CheckSubobjectKind {
+  CSK_Base,
+  CSK_Derived,
+  CSK_Field,
+  CSK_ArrayToPointer,
+  CSK_ArrayIndex,
+  CSK_Real,
+  CSK_Imag
+};
+
+namespace interp {
+class Frame;
+class SourceInfo;
+
+/// Interface for the VM to interact with the AST walker's context.
+class State {
+public:
+  virtual ~State();
+
+  virtual bool checkingForOverflow() const = 0;
+  virtual bool checkingPotentialConstantExpression() const = 0;
+  virtual bool noteUndefinedBehavior() = 0;
+  virtual Frame *getCurrentFrame() = 0;
+  virtual const Frame *getBottomFrame() const = 0;
+  virtual bool hasActiveDiagnostic() = 0;
+  virtual void setActiveDiagnostic(bool Flag) = 0;
+  virtual void setFoldFailureDiagnostic(bool Flag) = 0;
+  virtual Expr::EvalStatus &getEvalStatus() const = 0;
+  virtual ASTContext &getCtx() const = 0;
+  virtual bool hasPriorDiagnostic() = 0;
+  virtual unsigned getCallStackDepth() = 0;
+
+public:
+  // Diagnose that the evaluation could not be folded (FF => FoldFailure)
+  OptionalDiagnostic
+  FFDiag(SourceLocation Loc,
+         diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
+         unsigned ExtraNotes = 0);
+
+  OptionalDiagnostic
+  FFDiag(const Expr *E,
+         diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
+         unsigned ExtraNotes = 0);
+
+  OptionalDiagnostic
+  FFDiag(const SourceInfo &SI,
+         diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
+         unsigned ExtraNotes = 0);
+
+  /// Diagnose that the evaluation does not produce a C++11 core constant
+  /// expression.
+  ///
+  /// FIXME: Stop evaluating if we're in EM_ConstantExpression or
+  /// EM_PotentialConstantExpression mode and we produce one of these.
+  OptionalDiagnostic
+  CCEDiag(SourceLocation Loc,
+          diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
+          unsigned ExtraNotes = 0);
+
+  OptionalDiagnostic
+  CCEDiag(const Expr *E,
+          diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
+          unsigned ExtraNotes = 0);
+
+  OptionalDiagnostic
+  CCEDiag(const SourceInfo &SI,
+          diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
+          unsigned ExtraNotes = 0);
+
+  /// Add a note to a prior diagnostic.
+  OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId);
+
+  /// Add a stack of notes to a prior diagnostic.
+  void addNotes(ArrayRef<PartialDiagnosticAt> Diags);
+
+  /// Directly reports a diagnostic message.
+  DiagnosticBuilder report(SourceLocation Loc, diag::kind DiagId);
+
+  const LangOptions &getLangOpts() const;
+
+private:
+  void addCallStack(unsigned Limit);
+
+  PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId);
+
+  OptionalDiagnostic diag(SourceLocation Loc, diag::kind DiagId,
+                          unsigned ExtraNotes, bool IsCCEDiag);
+};
+
+} // namespace interp
+} // namespace clang
+
+#endif

clang/lib/AST/Interp/State.cpp

+//===--- State.cpp - State chain for the VM and AST Walker ------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "State.h"
+#include "Frame.h"
+#include "Program.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/CXXInheritance.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+State::~State() {}
+
+OptionalDiagnostic State::FFDiag(SourceLocation Loc, diag::kind DiagId,
+                                 unsigned ExtraNotes) {
+  return diag(Loc, DiagId, ExtraNotes, false);
+}
+
+OptionalDiagnostic State::FFDiag(const Expr *E, diag::kind DiagId,
+                                 unsigned ExtraNotes) {
+  if (getEvalStatus().Diag)
+    return diag(E->getExprLoc(), DiagId, ExtraNotes, false);
+  setActiveDiagnostic(false);
+  return OptionalDiagnostic();
+}
+
+OptionalDiagnostic State::FFDiag(const SourceInfo &SI, diag::kind DiagId,
+                                 unsigned ExtraNotes) {
+  if (getEvalStatus().Diag)
+    return diag(SI.getLoc(), DiagId, ExtraNotes, false);
+  setActiveDiagnostic(false);
+  return OptionalDiagnostic();
+}
+
+OptionalDiagnostic State::CCEDiag(SourceLocation Loc, diag::kind DiagId,
+                                  unsigned ExtraNotes) {
+  // Don't override a previous diagnostic. Don't bother collecting
+  // diagnostics if we're evaluating for overflow.
+  if (!getEvalStatus().Diag || !getEvalStatus().Diag->empty()) {
+    setActiveDiagnostic(false);
+    return OptionalDiagnostic();
+  }
+  return diag(Loc, DiagId, ExtraNotes, true);
+}
+
+OptionalDiagnostic State::CCEDiag(const Expr *E, diag::kind DiagId,
+                                  unsigned ExtraNotes) {
+  return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes);
+}
+
+OptionalDiagnostic State::CCEDiag(const SourceInfo &SI, diag::kind DiagId,
+                                  unsigned ExtraNotes) {
+  return CCEDiag(SI.getLoc(), DiagId, ExtraNotes);
+}
+
+OptionalDiagnostic State::Note(SourceLocation Loc, diag::kind DiagId) {
+  if (!hasActiveDiagnostic())
+    return OptionalDiagnostic();
+  return OptionalDiagnostic(&addDiag(Loc, DiagId));
+}
+
+void State::addNotes(ArrayRef<PartialDiagnosticAt> Diags) {
+  if (hasActiveDiagnostic()) {
+    getEvalStatus().Diag->insert(getEvalStatus().Diag->end(), Diags.begin(),
+                                 Diags.end());
+  }
+}
+
+DiagnosticBuilder State::report(SourceLocation Loc, diag::kind DiagId) {
+  return getCtx().getDiagnostics().Report(Loc, DiagId);
+}
+
+/// Add a diagnostic to the diagnostics list.
+PartialDiagnostic &State::addDiag(SourceLocation Loc, diag::kind DiagId) {
+  PartialDiagnostic PD(DiagId, getCtx().getDiagAllocator());
+  getEvalStatus().Diag->push_back(std::make_pair(Loc, PD));
+  return getEvalStatus().Diag->back().second;
+}
+
+OptionalDiagnostic State::diag(SourceLocation Loc, diag::kind DiagId,
+                               unsigned ExtraNotes, bool IsCCEDiag) {
+  auto &EvalStatus = getEvalStatus();
+  if (EvalStatus.Diag) {
+    if (hasPriorDiagnostic()) {
+      return OptionalDiagnostic();
+    }
+
+    unsigned CallStackNotes = getCallStackDepth() - 1;
+    unsigned Limit = getCtx().getDiagnostics().getConstexprBacktraceLimit();
+    if (Limit)
+      CallStackNotes = std::min(CallStackNotes, Limit + 1);
+    if (checkingPotentialConstantExpression())
+      CallStackNotes = 0;
+
+    setActiveDiagnostic(true);
+    setFoldFailureDiagnostic(!IsCCEDiag);
+    EvalStatus.Diag->clear();
+    EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes);
+    addDiag(Loc, DiagId);
+    if (!checkingPotentialConstantExpression()) {
+      addCallStack(Limit);
+    }
+    return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second);
+  }
+  setActiveDiagnostic(false);
+  return OptionalDiagnostic();
+}
+
+const LangOptions &State::getLangOpts() const { return getCtx().getLangOpts(); }
+
+void State::addCallStack(unsigned Limit) {
+  // Determine which calls to skip, if any.
+  unsigned ActiveCalls = getCallStackDepth() - 1;
+  unsigned SkipStart = ActiveCalls, SkipEnd = SkipStart;
+  if (Limit && Limit < ActiveCalls) {
+    SkipStart = Limit / 2 + Limit % 2;
+    SkipEnd = ActiveCalls - Limit / 2;
+  }
+
+  // Walk the call stack and add the diagnostics.
+  unsigned CallIdx = 0;
+  auto *CurrentCall = getCurrentFrame();
+  auto *BottomFrame = getBottomFrame();
+  for (auto *F = CurrentCall; F != BottomFrame; F = F->getCaller(), ++CallIdx) {
+    auto CallLocation = F->getCallLocation();
+
+    // Skip this call?
+    if (CallIdx >= SkipStart && CallIdx < SkipEnd) {
+      if (CallIdx == SkipStart) {
+        // Note that we're skipping calls.
+        addDiag(CallLocation, diag::note_constexpr_calls_suppressed)
+            << unsigned(ActiveCalls - Limit);
+      }
+      continue;
+    }
+
+    // Use a different note for an inheriting constructor, because from the
+    // user's perspective it's not really a function at all.
+    if (auto *CD = dyn_cast_or_null<CXXConstructorDecl>(F->getCallee())) {
+      if (CD->isInheritingConstructor()) {
+        addDiag(CallLocation, diag::note_constexpr_inherited_ctor_call_here)
+            << CD->getParent();
+        continue;
+      }
+    }
+
+    SmallVector<char, 128> Buffer;
+    llvm::raw_svector_ostream Out(Buffer);
+    F->describe(Out);
+    addDiag(CallLocation, diag::note_constexpr_call_here) << Out.str();
+  }
+}

clang/lib/AST/Interp/Type.h

+//===--- Type.h - Types for the constexpr VM --------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the VM types and helpers operating on types.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_INTERP_TYPE_H
+#define LLVM_CLANG_AST_INTERP_TYPE_H
+
+#include "Integral.h"
+#include "Pointer.h"
+#include <cstddef>
+#include <cstdint>
+#include <climits>
+
+namespace clang {
+namespace interp {
+
+/// Enumeration of the primitive types of the VM.
+enum PrimType : unsigned {
+  PT_Sint8,
+  PT_Uint8,
+  PT_Sint16,
+  PT_Uint16,
+  PT_Sint32,
+  PT_Uint32,
+  PT_Sint64,
+  PT_Uint64,
+  PT_Ptr,
+  PT_Bool,
+};
+
+/// Mapping from primitive types to their representation.
+template <PrimType T> struct PrimConv;
+template <> struct PrimConv<PT_Sint8> { using T = Integral<8, true>; };
+template <> struct PrimConv<PT_Uint8> { using T = Integral<8, false>; };
+template <> struct PrimConv<PT_Sint16> { using T = Integral<16, true>; };
+template <> struct PrimConv<PT_Uint16> { using T = Integral<16, false>; };
+template <> struct PrimConv<PT_Sint32> { using T = Integral<32, true>; };
+template <> struct PrimConv<PT_Uint32> { using T = Integral<32, false>; };
+template <> struct PrimConv<PT_Sint64> { using T = Integral<64, true>; };
+template <> struct PrimConv<PT_Uint64> { using T = Integral<64, false>; };
+template <> struct PrimConv<PT_Bool> { using T = Integral<1, false>; };
+template <> struct PrimConv<PT_Ptr> { using T = Pointer; };
+
+/// Returns the size of a primitive type in bytes.
+size_t primSize(PrimType Type);
+
+/// Aligns a size to the pointer alignment.
+constexpr size_t align(size_t Size) {
+  return ((Size + alignof(void *) - 1) / alignof(void *)) * alignof(void *);
+}
+
+} // namespace interp
+} // namespace clang
+
+/// Helper macro to simplify type switches.
+/// The macro implicitly exposes a type T in the scope of the inner block.
+#define TYPE_SWITCH(Expr, B)                                                   \
+  switch (Expr) {                                                              \
+  case PT_Sint8:  {using T = PrimConv<PT_Sint8>::T;  do{B;}while(0); break; }  \
+  case PT_Uint8:  {using T = PrimConv<PT_Uint8>::T;  do{B;}while(0); break; }  \
+  case PT_Sint16: {using T = PrimConv<PT_Sint16>::T; do{B;}while(0); break; }  \
+  case PT_Uint16: {using T = PrimConv<PT_Uint16>::T; do{B;}while(0); break; }  \
+  case PT_Sint32: {using T = PrimConv<PT_Sint32>::T; do{B;}while(0); break; }  \
+  case PT_Uint32: {using T = PrimConv<PT_Uint32>::T; do{B;}while(0); break; }  \
+  case PT_Sint64: {using T = PrimConv<PT_Sint64>::T; do{B;}while(0); break; }  \
+  case PT_Uint64: {using T = PrimConv<PT_Uint64>::T; do{B;}while(0); break; }  \
+  case PT_Bool:   {using T = PrimConv<PT_Bool>::T;   do{B;}while(0); break; }  \
+  case PT_Ptr:    {using T = PrimConv<PT_Ptr>::T;    do{B;}while(0); break; }  \
+  }
+#endif

clang/lib/AST/Interp/Type.cpp

+//===--- Type.cpp - Types for the constexpr VM ------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Type.h"
+
+using namespace clang;
+using namespace clang::interp;
+
+namespace clang {
+namespace interp {
+
+size_t primSize(PrimType Type) {
+  TYPE_SWITCH(Type, return sizeof(T));
+}
+
+} // namespace interp
+} // namespace clang

clang/lib/Driver/ToolChains/Clang.cpp

if (Arg *A = Args.getLastArg(options::OPT_fconstexpr_depth_EQ)) {
     CmdArgs.push_back(A->getValue());
   }
 
   if (Arg *A = Args.getLastArg(options::OPT_fconstexpr_steps_EQ)) {
     CmdArgs.push_back("-fconstexpr-steps");
     CmdArgs.push_back(A->getValue());
   }
 
+  if (Args.hasArg(options::OPT_fexperimental_clang_interpreter))
+    CmdArgs.push_back("-fexperimental-clang-interpreter");
+
+  if (Args.hasArg(options::OPT_fforce_experimental_clang_interpreter))
+    CmdArgs.push_back("-fforce-experimental-clang-interpreter");
+
   if (Arg *A = Args.getLastArg(options::OPT_fbracket_depth_EQ)) {
     CmdArgs.push_back("-fbracket-depth");
     CmdArgs.push_back(A->getValue());
   }
 
   if (Arg *A = Args.getLastArg(options::OPT_Wlarge_by_value_copy_EQ,
                                options::OPT_Wlarge_by_value_copy_def)) {
     if (A->getNumValues()) {

clang/lib/Frontend/CompilerInvocation.cpp

#include "clang/Frontend/LangStandards.def"
   Opts.InstantiationDepth =
       getLastArgIntValue(Args, OPT_ftemplate_depth, 1024, Diags);
   Opts.ArrowDepth =
       getLastArgIntValue(Args, OPT_foperator_arrow_depth, 256, Diags);
   Opts.ConstexprCallDepth =
       getLastArgIntValue(Args, OPT_fconstexpr_depth, 512, Diags);
   Opts.ConstexprStepLimit =
       getLastArgIntValue(Args, OPT_fconstexpr_steps, 1048576, Diags);
+  Opts.EnableClangInterp =
+      Args.hasArg(OPT_fexperimental_clang_interpreter);
+  Opts.ForceClangInterp =
+      Args.hasArg(OPT_fforce_experimental_clang_interpreter);
   Opts.BracketDepth = getLastArgIntValue(Args, OPT_fbracket_depth, 256, Diags);
   Opts.DelayedTemplateParsing = Args.hasArg(OPT_fdelayed_template_parsing);
   Opts.NumLargeByValueCopy =
       getLastArgIntValue(Args, OPT_Wlarge_by_value_copy_EQ, 0, Diags);
   Opts.MSBitfields = Args.hasArg(OPT_mms_bitfields);
   Opts.ObjCConstantStringClass =
     Args.getLastArgValue(OPT_fconstant_string_class);
   Opts.ObjCDefaultSynthProperties =

clang/test/AST/Interp/cond.cpp

+// RUN: %clang_cc1 -std=c++17 -fsyntax-only -fforce-experimental-clang-interpreter %s -verify
+// RUN: %clang_cc1 -std=c++17 -fsyntax-only %s -verify
+// expected-no-diagnostics
+
+constexpr int cond_then_else(int a, int b) {
+  if (a < b) {
+    return b - a;
+  } else {
+    return a - b;
+  }
+}

clang/utils/TableGen/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_tablegen(clang-tblgen CLANG
   ClangASTNodesEmitter.cpp
   ClangAttrEmitter.cpp
   ClangCommentCommandInfoEmitter.cpp
   ClangCommentHTMLNamedCharacterReferenceEmitter.cpp
   ClangCommentHTMLTagsEmitter.cpp
   ClangDataCollectorsEmitter.cpp
   ClangDiagnosticsEmitter.cpp
+  ClangOpcodesEmitter.cpp
   ClangOpenCLBuiltinEmitter.cpp
   ClangOptionDocEmitter.cpp
   ClangSACheckersEmitter.cpp
   NeonEmitter.cpp
   TableGen.cpp
   )
 set_target_properties(clang-tblgen PROPERTIES FOLDER "Clang tablegenning")

clang/utils/TableGen/ClangOpcodesEmitter.cpp

+//=== ClangOpcodesEmitter.cpp - constexpr interpreter opcodes ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// These tablegen backends emit Clang AST node tables
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/StringMatcher.h"
+#include "llvm/TableGen/TableGenBackend.h"
+
+using namespace llvm;
+
+namespace {
+class ClangOpcodesEmitter {
+  RecordKeeper &Records;
+  Record Root;
+  unsigned NumTypes;
+
+public:
+  ClangOpcodesEmitter(RecordKeeper &R)
+    : Records(R), Root("Opcode", SMLoc(), R),
+      NumTypes(Records.getAllDerivedDefinitions("Type").size()) {}
+
+  void run(raw_ostream &OS);
+
+private:
+  /// Emits the opcode name for the opcode enum.
+  /// The name is obtained by concatenating the name with the list of types.
+  void EmitEnum(raw_ostream &OS, StringRef N, Record *R);
+
+  /// Emits the switch case and the invocation in the interpreter.
+  void EmitInterp(raw_ostream &OS, StringRef N, Record *R);
+
+  /// Emits the disassembler.
+  void EmitDisasm(raw_ostream &OS, StringRef N, Record *R);
+
+  /// Emits the LinkEmitter method.
+  void EmitLink(raw_ostream &OS, StringRef N, Record *R);
+
+  /// Emits the prototype.
+  void EmitProto(raw_ostream &OS, StringRef N, Record *R);
+
+  /// Emits the prototype to dispatch from a type.
+  void EmitGroup(raw_ostream &OS, StringRef N, Record *R);
+
+  /// Emits the evaluator method.
+  void EmitEval(raw_ostream &OS, StringRef N, Record *R);
+
+  void PrintTypes(raw_ostream &OS, ArrayRef<Record *> Types);
+};
+
+void Enumerate(const Record *R,
+               StringRef N,
+               std::function<void(ArrayRef<Record *>, Twine)> &&F) {
+  llvm::SmallVector<Record *, 2> TypePath;
+  auto *Types = R->getValueAsListInit("Types");
+
+  std::function<void(size_t, const Twine &)> Rec;
+  Rec = [&TypePath, Types, &Rec, &F](size_t I, const Twine &ID) {
+    if (I >= Types->size()) {
+      F(TypePath, ID);
+      return;
+    }
+
+    if (auto *TypeClass = dyn_cast<DefInit>(Types->getElement(I))) {
+      for (auto *Type : TypeClass->getDef()->getValueAsListOfDefs("Types")) {
+        TypePath.push_back(Type);
+        Rec(I + 1, ID + Type->getName());
+        TypePath.pop_back();
+      }
+    } else {
+      PrintFatalError("Expected a type class");
+    }
+  };
+  Rec(0, N);
+}
+
+} // namespace
+
+void ClangOpcodesEmitter::run(raw_ostream &OS) {
+  for (auto *Opcode : Records.getAllDerivedDefinitions(Root.getName())) {
+    // The name is the record name, unless overriden.
+    StringRef N = Opcode->getValueAsString("Name");
+    if (N.empty())
+      N = Opcode->getName();
+
+    EmitEnum(OS, N, Opcode);
+    EmitInterp(OS, N, Opcode);
+    EmitDisasm(OS, N, Opcode);
+    EmitProto(OS, N, Opcode);
+    EmitGroup(OS, N, Opcode);
+    EmitLink(OS, N, Opcode);
+    EmitEval(OS, N, Opcode);
+  }
+}
+
+void ClangOpcodesEmitter::EmitEnum(raw_ostream &OS, StringRef N, Record *R) {
+  OS << "#ifdef GET_OPCODE_NAMES\n";
+  Enumerate(R, N, [&OS](ArrayRef<Record *>, const Twine &ID) {
+    OS << "OP_" << ID << ",\n";
+  });
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::EmitInterp(raw_ostream &OS, StringRef N, Record *R) {
+  OS << "#ifdef GET_INTERP\n";
+
+  Enumerate(R, N, [this, R, &OS, &N](ArrayRef<Record *> TS, const Twine &ID) {
+    bool CanReturn = R->getValueAsBit("CanReturn");
+    bool ChangesPC = R->getValueAsBit("ChangesPC");
+    auto Args = R->getValueAsListOfDefs("Args");
+
+    OS << "case OP_" << ID << ": {\n";
+
+    // Emit calls to read arguments.
+    for (size_t I = 0, N = Args.size(); I < N; ++I) {
+      OS << "\tauto V" << I;
+      OS << " = ";
+      OS << "PC.read<" << Args[I]->getValueAsString("Name") << ">();\n";
+    }
+
+    // Emit a call to the template method and pass arguments.
+    OS << "\tif (!" << N;
+    PrintTypes(OS, TS);
+    OS << "(S";
+    if (ChangesPC)
+      OS << ", PC";
+    else
+      OS << ", OpPC";
+    if (CanReturn)
+      OS << ", Result";
+    for (size_t I = 0, N = Args.size(); I < N; ++I)
+      OS << ", V" << I;
+    OS << "))\n";
+    OS << "\t\treturn false;\n";
+
+    // Bail out if interpreter returned.
+    if (CanReturn) {
+      OS << "\tif (!S.Current || S.Current->isRoot())\n";
+      OS << "\t\treturn true;\n";
+    }
+
+    OS << "\tcontinue;\n";
+    OS << "}\n";
+  });
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::EmitDisasm(raw_ostream &OS, StringRef N, Record *R) {
+  OS << "#ifdef GET_DISASM\n";
+  Enumerate(R, N, [R, &OS](ArrayRef<Record *>, const Twine &ID) {
+    OS << "case OP_" << ID << ":\n";
+    OS << "\tPrintName(\"" << ID << "\");\n";
+    OS << "\tOS << \"\\t\"";
+
+    for (auto *Arg : R->getValueAsListOfDefs("Args"))
+      OS << " << PC.read<" << Arg->getValueAsString("Name") << ">() << \" \"";
+
+    OS << "<< \"\\n\";\n";
+    OS << "\tcontinue;\n";
+  });
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::EmitLink(raw_ostream &OS, StringRef N, Record *R) {
+  if (R->getValueAsBit("HasCustomLink"))
+    return;
+
+  OS << "#ifdef GET_LINK_IMPL\n";
+  Enumerate(R, N, [R, &OS](ArrayRef<Record *>, const Twine &ID) {
+    auto Args = R->getValueAsListOfDefs("Args");
+
+    // Emit the list of arguments.
+    OS << "bool LinkEmitter::emit" << ID << "(";
+    for (size_t I = 0, N = Args.size(); I < N; ++I)
+      OS << "const " << Args[I]->getValueAsString("Name") << " &A" << I << ",";
+    OS << "const SourceInfo &L) {\n";
+
+    // Emit a call to write the opcodes.
+    OS << "\treturn emitOp<";
+    for (size_t I = 0, N = Args.size(); I < N; ++I) {
+      if (I != 0)
+        OS << ", ";
+      OS << Args[I]->getValueAsString("Name");
+    }
+    OS << ">(OP_" << ID;
+    for (size_t I = 0, N = Args.size(); I < N; ++I)
+      OS << ", A" << I;
+    OS << ", L);\n";
+    OS << "}\n";
+  });
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::EmitProto(raw_ostream &OS, StringRef N, Record *R) {
+  OS << "#if defined(GET_EVAL_PROTO) || defined(GET_LINK_PROTO)\n";
+  auto Args = R->getValueAsListOfDefs("Args");
+  Enumerate(R, N, [&OS, &Args](ArrayRef<Record *> TS, const Twine &ID) {
+    OS << "bool emit" << ID << "(";
+    for (auto *Arg : Args)
+      OS << "const " << Arg->getValueAsString("Name") << " &, ";
+    OS << "const SourceInfo &);\n";
+  });
+
+  // Emit a template method for custom emitters to have less to implement.
+  auto TypeCount = R->getValueAsListInit("Types")->size();
+  if (R->getValueAsBit("HasCustomEval") && TypeCount) {
+    OS << "#if defined(GET_EVAL_PROTO)\n";
+    OS << "template<";
+    for (size_t I = 0; I < TypeCount; ++I) {
+      if (I != 0)
+        OS << ", ";
+      OS << "PrimType";
+    }
+    OS << ">\n";
+    OS << "bool emit" << N << "(";
+    for (auto *Arg : Args)
+      OS << "const " << Arg->getValueAsString("Name") << " &,";
+    OS << "const SourceInfo &);\n";
+    OS << "#endif\n";
+  }
+
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::EmitGroup(raw_ostream &OS, StringRef N, Record *R) {
+  if (!R->getValueAsBit("HasGroup"))
+    return;
+
+  auto *Types = R->getValueAsListInit("Types");
+  auto Args = R->getValueAsListOfDefs("Args");
+
+  // Emit the prototype of the group emitter in the header.
+  OS << "#if defined(GET_EVAL_PROTO) || defined(GET_LINK_PROTO)\n";
+  OS << "bool emit" << N << "(";
+  for (size_t I = 0, N = Types->size(); I < N; ++I)
+    OS << "PrimType, ";
+  for (auto *Arg : Args)
+    OS << "const " << Arg->getValueAsString("Name") << " &, ";
+  OS << "const SourceInfo &I);\n";
+  OS << "#endif\n";
+
+  // Emit the dispatch implementation in the source.
+  OS << "#if defined(GET_EVAL_IMPL) || defined(GET_LINK_IMPL)\n";
+  OS << "bool \n";
+  OS << "#if defined(GET_EVAL_IMPL)\nEvalEmitter\n#else\nLinkEmitter\n#endif\n";
+  OS << "::emit" << N << "(";
+  for (size_t I = 0, N = Types->size(); I < N; ++I)
+    OS << "PrimType T" << I << ", ";
+  for (size_t I = 0, N = Args.size(); I < N; ++I)
+    OS << "const " << Args[I]->getValueAsString("Name") << " &A" << I << ", ";
+  OS << "const SourceInfo &I) {\n";
+
+  std::function<void(size_t, const Twine &)> Rec;
+  llvm::SmallVector<Record *, 2> TS;
+  Rec = [this, &Rec, &OS, Types, &Args, R, &TS, N](size_t I, const Twine &ID) {
+    if (I >= Types->size()) {
+      // Print a call to the emitter method.
+      // Custom evaluator methods dispatch to template methods.
+      if (R->getValueAsBit("HasCustomEval")) {
+        OS << "#ifdef GET_LINK_IMPL\n";
+        OS << "return emit" << ID << "\n";
+        OS << "#else\n";
+        OS << "return emit" << N;
+        PrintTypes(OS, TS);
+        OS << "\n#endif\n";
+      } else {
+        OS << "return emit" << ID;
+      }
+
+      OS << "(";
+      for (size_t I = 0; I < Args.size(); ++I) {
+        OS << "A" << I << ", ";
+      }
+      OS << "I);\n";
+      return;
+    }
+
+    // Print a switch statement selecting T.
+    if (auto *TypeClass = dyn_cast<DefInit>(Types->getElement(I))) {
+      OS << "switch (T" << I << "){\n";
+      auto Cases = TypeClass->getDef()->getValueAsListOfDefs("Types");
+      for (auto *Case : Cases) {
+        OS << "case PT_" << Case->getName() << ":\n";
+        TS.push_back(Case);
+        Rec(I + 1, ID + Case->getName());
+        TS.pop_back();
+      }
+      // Emit a default case if not all types are present.
+      if (Cases.size() < NumTypes) {
+        OS << "default: llvm_unreachable(\"invalid\");\n";
+      }
+      OS << "}\n";
+    } else {
+      PrintFatalError("Expected a type class");
+    }
+  };
+  Rec(0, N);
+
+  OS << "}\n";
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::EmitEval(raw_ostream &OS, StringRef N, Record *R) {
+  if (R->getValueAsBit("HasCustomEval"))
+    return;
+
+  OS << "#ifdef GET_EVAL_IMPL\n";
+  Enumerate(R, N, [this, R, &N, &OS](ArrayRef<Record *> TS, const Twine &ID) {
+    auto Args = R->getValueAsListOfDefs("Args");
+
+    OS << "bool EvalEmitter::emit" << ID << "(";
+    for (size_t I = 0, N = Args.size(); I < N; ++I)
+      OS << "const " << Args[I]->getValueAsString("Name") << " &A" << I << ",";
+    OS << "const SourceInfo &L) {\n";
+    OS << "if (!isActive()) return true;\n";
+    OS << "CurrentSource = L;\n";
+
+    OS << "return " << N;
+    PrintTypes(OS, TS);
+    OS << "(S, OpPC";
+    for (size_t I = 0, N = Args.size(); I < N; ++I)
+      OS << ", A" << I;
+    OS << ");\n";
+    OS << "}\n";
+  });
+
+  OS << "#endif\n";
+}
+
+void ClangOpcodesEmitter::PrintTypes(raw_ostream &OS, ArrayRef<Record *> Types) {
+  if (Types.empty())
+    return;
+  OS << "<";
+  for (size_t I = 0, N = Types.size(); I < N; ++I) {
+    if (I != 0)
+      OS << ", ";
+    OS << "PT_" << Types[I]->getName();
+  }
+  OS << ">";
+}
+
+namespace clang {
+
+void EmitClangOpcodes(RecordKeeper &Records, raw_ostream &OS) {
+  ClangOpcodesEmitter(Records).run(OS);
+}
+
+} // end namespace clang

clang/utils/TableGen/TableGen.cpp

enum ActionType {
   GenClangAttrTextNodeDump,
   GenClangAttrNodeTraverse,
   GenClangDiagsDefs,
   GenClangDiagGroups,
   GenClangDiagsIndexName,
   GenClangCommentNodes,
   GenClangDeclNodes,
   GenClangStmtNodes,
+  GenClangOpcodes,
   GenClangSACheckers,
   GenClangCommentHTMLTags,
   GenClangCommentHTMLTagsProperties,
   GenClangCommentHTMLNamedCharacterReferences,
   GenClangCommentCommandInfo,
   GenClangCommentCommandList,
   GenClangOpenCLBuiltins,
   GenArmNeon,
cl::values(
         clEnumValN(GenClangDiagsIndexName, "gen-clang-diags-index-name",
                    "Generate Clang diagnostic name index"),
         clEnumValN(GenClangCommentNodes, "gen-clang-comment-nodes",
                    "Generate Clang AST comment nodes"),
         clEnumValN(GenClangDeclNodes, "gen-clang-decl-nodes",
                    "Generate Clang AST declaration nodes"),
         clEnumValN(GenClangStmtNodes, "gen-clang-stmt-nodes",
                    "Generate Clang AST statement nodes"),
+        clEnumValN(GenClangOpcodes, "gen-clang-opcodes",
+                   "Generate Clang constexpr interpreter opcodes"),
         clEnumValN(GenClangSACheckers, "gen-clang-sa-checkers",
                    "Generate Clang Static Analyzer checkers"),
         clEnumValN(GenClangCommentHTMLTags, "gen-clang-comment-html-tags",
                    "Generate efficient matchers for HTML tag "
                    "names that are used in documentation comments"),
         clEnumValN(GenClangCommentHTMLTagsProperties,
                    "gen-clang-comment-html-tags-properties",
                    "Generate efficient matchers for HTML tag "
case GenClangCommentNodes:
     break;
   case GenClangDeclNodes:
     EmitClangASTNodes(Records, OS, "Decl", "Decl");
     EmitClangDeclContext(Records, OS);
     break;
   case GenClangStmtNodes:
     EmitClangASTNodes(Records, OS, "Stmt", "");
     break;
+  case GenClangOpcodes:
+    EmitClangOpcodes(Records, OS);
+    break;
   case GenClangSACheckers:
     EmitClangSACheckers(Records, OS);
     break;
   case GenClangCommentHTMLTags:
     EmitClangCommentHTMLTags(Records, OS);
     break;
   case GenClangCommentHTMLTagsProperties:
     EmitClangCommentHTMLTagsProperties(Records, OS);

clang/utils/TableGen/TableGenBackends.h

void EmitClangCommentHTMLTagsProperties(llvm::RecordKeeper &Records,
                                         llvm::raw_ostream &OS);
 void EmitClangCommentHTMLNamedCharacterReferences(llvm::RecordKeeper &Records,
                                                   llvm::raw_ostream &OS);
 
 void EmitClangCommentCommandInfo(llvm::RecordKeeper &Records,
                                  llvm::raw_ostream &OS);
 void EmitClangCommentCommandList(llvm::RecordKeeper &Records,
                                  llvm::raw_ostream &OS);
+void EmitClangOpcodes(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 
 void EmitNeon(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitFP16(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonSema(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonTest(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeon2(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonSema2(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonTest2(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);