|
150
|
1 ====================
|
|
|
2 Constant Interpreter
|
|
|
3 ====================
|
|
|
4
|
|
|
5 .. contents::
|
|
|
6 :local:
|
|
|
7
|
|
|
8 Introduction
|
|
|
9 ============
|
|
|
10
|
|
173
|
11 The constexpr interpreter aims to replace the existing tree evaluator in
|
|
|
12 clang, improving performance on constructs which are executed inefficiently
|
|
|
13 by the evaluator. The interpreter is activated using the following flags:
|
|
150
|
14
|
|
173
|
15 * ``-fexperimental-new-constant-interpreter`` enables the interpreter,
|
|
|
16 emitting an error if an unsupported feature is encountered
|
|
150
|
17
|
|
|
18 Bytecode Compilation
|
|
|
19 ====================
|
|
|
20
|
|
173
|
21 Bytecode compilation is handled in ``ByteCodeStmtGen.h`` for statements
|
|
|
22 and ``ByteCodeExprGen.h`` for expressions. The compiler has two different
|
|
|
23 backends: one to generate bytecode for functions (``ByteCodeEmitter``) and
|
|
|
24 one to directly evaluate expressions as they are compiled, without
|
|
|
25 generating bytecode (``EvalEmitter``). All functions are compiled to
|
|
|
26 bytecode, while toplevel expressions used in constant contexts are directly
|
|
|
27 evaluated since the bytecode would never be reused. This mechanism aims to
|
|
|
28 pave the way towards replacing the evaluator, improving its performance on
|
|
|
29 functions and loops, while being just as fast on single-use toplevel
|
|
|
30 expressions.
|
|
150
|
31
|
|
173
|
32 The interpreter relies on stack-based, strongly-typed opcodes. The glue
|
|
|
33 logic between the code generator, along with the enumeration and
|
|
|
34 description of opcodes, can be found in ``Opcodes.td``. The opcodes are
|
|
|
35 implemented as generic template methods in ``Interp.h`` and instantiated
|
|
|
36 with the relevant primitive types by the interpreter loop or by the
|
|
|
37 evaluating emitter.
|
|
150
|
38
|
|
|
39 Primitive Types
|
|
|
40 ---------------
|
|
|
41
|
|
|
42 * ``PT_{U|S}int{8|16|32|64}``
|
|
|
43
|
|
173
|
44 Signed or unsigned integers of a specific bit width, implemented using
|
|
|
45 the ```Integral``` type.
|
|
150
|
46
|
|
|
47 * ``PT_{U|S}intFP``
|
|
|
48
|
|
173
|
49 Signed or unsigned integers of an arbitrary, but fixed width used to
|
|
|
50 implement integral types which are required by the target, but are not
|
|
|
51 supported by the host. Under the hood, they rely on APValue. The
|
|
|
52 ``Integral`` specialisation for these types is required by opcodes to
|
|
|
53 share an implementation with fixed integrals.
|
|
150
|
54
|
|
|
55 * ``PT_Bool``
|
|
|
56
|
|
173
|
57 Representation for boolean types, essentially a 1-bit unsigned
|
|
|
58 ``Integral``.
|
|
150
|
59
|
|
|
60 * ``PT_RealFP``
|
|
|
61
|
|
173
|
62 Arbitrary, but fixed precision floating point numbers. Could be
|
|
|
63 specialised in the future similarly to integers in order to improve
|
|
|
64 floating point performance.
|
|
150
|
65
|
|
|
66 * ``PT_Ptr``
|
|
|
67
|
|
173
|
68 Pointer type, defined in ``"Pointer.h"``. A pointer can be either null,
|
|
|
69 reference interpreter-allocated memory (``BlockPointer``) or point to an
|
|
|
70 address which can be derived, but not accessed (``ExternPointer``).
|
|
150
|
71
|
|
|
72 * ``PT_FnPtr``
|
|
|
73
|
|
173
|
74 Function pointer type, can also be a null function pointer. Defined
|
|
|
75 in ``"FnPointer.h"``.
|
|
150
|
76
|
|
|
77 * ``PT_MemPtr``
|
|
|
78
|
|
173
|
79 Member pointer type, can also be a null member pointer. Defined
|
|
|
80 in ``"MemberPointer.h"``
|
|
|
81
|
|
|
82 * ``PT_VoidPtr``
|
|
|
83
|
|
252
|
84 Void pointer type, can be used for round-trip casts. Represented as
|
|
173
|
85 the union of all pointers which can be cast to void.
|
|
|
86 Defined in ``"VoidPointer.h"``.
|
|
|
87
|
|
|
88 * ``PT_ObjCBlockPtr``
|
|
|
89
|
|
|
90 Pointer type for ObjC blocks. Defined in ``"ObjCBlockPointer.h"``.
|
|
150
|
91
|
|
|
92 Composite types
|
|
|
93 ---------------
|
|
|
94
|
|
173
|
95 The interpreter distinguishes two kinds of composite types: arrays and
|
|
|
96 records (structs and classes). Unions are represented as records, except
|
|
|
97 at most a single field can be marked as active. The contents of inactive
|
|
|
98 fields are kept until they are reactivated and overwritten.
|
|
|
99 Complex numbers (``_Complex``) and vectors
|
|
|
100 (``__attribute((vector_size(16)))``) are treated as arrays.
|
|
150
|
101
|
|
|
102
|
|
|
103 Bytecode Execution
|
|
|
104 ==================
|
|
|
105
|
|
173
|
106 Bytecode is executed using a stack-based interpreter. The execution
|
|
|
107 context consists of an ``InterpStack``, along with a chain of
|
|
|
108 ``InterpFrame`` objects storing the call frames. Frames are built by
|
|
|
109 call instructions and destroyed by return instructions. They perform
|
|
|
110 one allocation to reserve space for all locals in a single block.
|
|
|
111 These objects store all the required information to emit stack traces
|
|
|
112 whenever evaluation fails.
|
|
150
|
113
|
|
|
114 Memory Organisation
|
|
|
115 ===================
|
|
|
116
|
|
|
117 Memory management in the interpreter relies on 3 data structures: ``Block``
|
|
173
|
118 objects which store the data and associated inline metadata, ``Pointer``
|
|
|
119 objects which refer to or into blocks, and ``Descriptor`` structures which
|
|
|
120 describe blocks and subobjects nested inside blocks.
|
|
150
|
121
|
|
|
122 Blocks
|
|
|
123 ------
|
|
|
124
|
|
173
|
125 Blocks contain data interleaved with metadata. They are allocated either
|
|
|
126 statically in the code generator (globals, static members, dummy parameter
|
|
|
127 values etc.) or dynamically in the interpreter, when creating the frame
|
|
|
128 containing the local variables of a function. Blocks are associated with a
|
|
|
129 descriptor that characterises the entire allocation, along with a few
|
|
|
130 additional attributes:
|
|
150
|
131
|
|
173
|
132 * ``IsStatic`` indicates whether the block has static duration in the
|
|
|
133 interpreter, i.e. it is not a local in a frame.
|
|
|
134
|
|
|
135 * ``DeclID`` identifies each global declaration (it is set to an invalid
|
|
|
136 and irrelevant value for locals) in order to prevent illegal writes and
|
|
|
137 reads involving globals and temporaries with static storage duration.
|
|
150
|
138
|
|
173
|
139 Static blocks are never deallocated, but local ones might be deallocated
|
|
|
140 even when there are live pointers to them. Pointers are only valid as
|
|
|
141 long as the blocks they point to are valid, so a block with pointers to
|
|
|
142 it whose lifetime ends is kept alive until all pointers to it go out of
|
|
|
143 scope. Since the frame is destroyed on function exit, such blocks are
|
|
|
144 turned into a ``DeadBlock`` and copied to storage managed by the
|
|
|
145 interpreter itself, not the frame. Reads and writes to these blocks are
|
|
|
146 illegal and cause an appropriate diagnostic to be emitted. When the last
|
|
|
147 pointer goes out of scope, dead blocks are also deallocated.
|
|
150
|
148
|
|
173
|
149 The lifetime of blocks is managed through 3 methods stored in the
|
|
|
150 descriptor of the block:
|
|
150
|
151
|
|
173
|
152 * **CtorFn**: initializes the metadata which is store in the block,
|
|
|
153 alongside actual data. Invokes the default constructors of objects
|
|
|
154 which are not trivial (``Pointer``, ``RealFP``, etc.)
|
|
150
|
155
|
|
|
156 * **DtorFn**: invokes the destructors of non-trivial objects.
|
|
173
|
157
|
|
150
|
158 * **MoveFn**: moves a block to dead storage.
|
|
|
159
|
|
173
|
160 Non-static blocks track all the pointers into them through an intrusive
|
|
|
161 doubly-linked list, required to adjust and invalidate all pointers when
|
|
|
162 transforming a block into a dead block. If the lifetime of an object ends,
|
|
|
163 all pointers to it are invalidated, emitting the appropriate diagnostics when
|
|
|
164 dereferenced.
|
|
|
165
|
|
|
166 The interpreter distinguishes 3 different kinds of blocks:
|
|
|
167
|
|
|
168 * **Primitives**
|
|
|
169
|
|
|
170 A block containing a single primitive with no additional metadata.
|
|
|
171
|
|
|
172 * **Arrays of primitives**
|
|
|
173
|
|
|
174 An array of primitives contains a pointer to an ``InitMap`` storage as its
|
|
|
175 first field: the initialisation map is a bit map indicating all elements of
|
|
|
176 the array which were initialised. If the pointer is null, no elements were
|
|
|
177 initialised, while a value of ``(InitMap*)-1`` indicates that the object was
|
|
|
178 fully initialised. When all fields are initialised, the map is deallocated
|
|
|
179 and replaced with that token.
|
|
|
180
|
|
|
181 Array elements are stored sequentially, without padding, after the pointer
|
|
|
182 to the map.
|
|
|
183
|
|
|
184 * **Arrays of composites and records**
|
|
|
185
|
|
|
186 Each element in an array of composites is preceded by an ``InlineDescriptor``
|
|
|
187 which stores the attributes specific to the field and not the whole
|
|
|
188 allocation site. Descriptors and elements are stored sequentially in the
|
|
|
189 block.
|
|
|
190 Records are laid out identically to arrays of composites: each field and base
|
|
|
191 class is preceded by an inline descriptor. The ``InlineDescriptor``
|
|
|
192 has the following fields:
|
|
|
193
|
|
|
194 * **Offset**: byte offset into the array or record, used to step back to the
|
|
|
195 parent array or record.
|
|
|
196 * **IsConst**: flag indicating if the field is const-qualified.
|
|
|
197 * **IsInitialized**: flag indicating whether the field or element was
|
|
|
198 initialized. For non-primitive fields, this is only relevant to determine
|
|
|
199 the dynamic type of objects during construction.
|
|
|
200 * **IsBase**: flag indicating whether the record is a base class. In that
|
|
|
201 case, the offset can be used to identify the derived class.
|
|
|
202 * **IsActive**: indicates if the field is the active field of a union.
|
|
|
203 * **IsMutable**: indicates if the field is marked as mutable.
|
|
|
204
|
|
|
205 Inline descriptors are filled in by the `CtorFn` of blocks, which leaves storage
|
|
|
206 in an uninitialised, but valid state.
|
|
150
|
207
|
|
|
208 Descriptors
|
|
|
209 -----------
|
|
|
210
|
|
173
|
211 Descriptors are generated at bytecode compilation time and contain information
|
|
|
212 required to determine if a particular memory access is allowed in constexpr.
|
|
|
213 They also carry all the information required to emit a diagnostic involving
|
|
|
214 a memory access, such as the declaration which originates the block.
|
|
|
215 Currently there is a single kind of descriptor encoding information for all
|
|
|
216 block types.
|
|
150
|
217
|
|
|
218 Pointers
|
|
|
219 --------
|
|
|
220
|
|
173
|
221 Pointers, implemented in ``Pointer.h`` are represented as a tagged union.
|
|
|
222 Some of these may not yet be available in upstream ``clang``.
|
|
|
223
|
|
|
224 * **BlockPointer**: used to reference memory allocated and managed by the
|
|
|
225 interpreter, being the only pointer kind which allows dereferencing in the
|
|
|
226 interpreter
|
|
|
227 * **ExternPointer**: points to memory which can be addressed, but not read by
|
|
|
228 the interpreter. It is equivalent to APValue, tracking a declaration and a path
|
|
|
229 of fields and indices into that allocation.
|
|
|
230 * **TargetPointer**: represents a target address derived from a base address
|
|
|
231 through pointer arithmetic, such as ``((int *)0x100)[20]``. Null pointers are
|
|
|
232 target pointers with a zero offset.
|
|
|
233 * **TypeInfoPointer**: tracks information for the opaque type returned by
|
|
|
234 ``typeid``
|
|
|
235 * **InvalidPointer**: is dummy pointer created by an invalid operation which
|
|
|
236 allows the interpreter to continue execution. Does not allow pointer
|
|
|
237 arithmetic or dereferencing.
|
|
|
238
|
|
|
239 Besides the previously mentioned union, a number of other pointer-like types
|
|
|
240 have their own type:
|
|
|
241
|
|
|
242 * **ObjCBlockPointer** tracks Objective-C blocks
|
|
|
243 * **FnPointer** tracks functions and lazily caches their compiled version
|
|
|
244 * **MemberPointer** tracks C++ object members
|
|
|
245
|
|
|
246 Void pointers, which can be built by casting any of the aforementioned
|
|
|
247 pointers, are implemented as a union of all pointer types. The ``BitCast``
|
|
|
248 opcode is responsible for performing all legal conversions between these
|
|
|
249 types and primitive integers.
|
|
|
250
|
|
|
251 BlockPointer
|
|
|
252 ~~~~~~~~~~~~
|
|
|
253
|
|
|
254 Block pointers track a ``Pointee``, the block to which they point, along
|
|
|
255 with a ``Base`` and an ``Offset``. The base identifies the innermost field,
|
|
|
256 while the offset points to an array element relative to the base (including
|
|
|
257 one-past-end pointers). The offset identifies the array element or field
|
|
|
258 which is referenced, while the base points to the outer object or array which
|
|
|
259 contains the field. These two fields allow all pointers to be uniquely
|
|
|
260 identified, disambiguated and characterised.
|
|
150
|
261
|
|
|
262 As an example, consider the following structure:
|
|
|
263
|
|
|
264 .. code-block:: c
|
|
|
265
|
|
|
266 struct A {
|
|
|
267 struct B {
|
|
|
268 int x;
|
|
|
269 int y;
|
|
|
270 } b;
|
|
|
271 struct C {
|
|
|
272 int a;
|
|
|
273 int b;
|
|
|
274 } c[2];
|
|
|
275 int z;
|
|
|
276 };
|
|
|
277 constexpr A a;
|
|
|
278
|
|
173
|
279 On the target, ``&a`` and ``&a.b.x`` are equal. So are ``&a.c[0]`` and
|
|
|
280 ``&a.c[0].a``. In the interpreter, all these pointers must be
|
|
|
281 distinguished since the are all allowed to address distinct range of
|
|
|
282 memory.
|
|
150
|
283
|
|
173
|
284 In the interpreter, the object would require 240 bytes of storage and
|
|
|
285 would have its field interleaved with metadata. The pointers which can
|
|
|
286 be derived to the object are illustrated in the following diagram:
|
|
150
|
287
|
|
|
288 ::
|
|
|
289
|
|
|
290 0 16 32 40 56 64 80 96 112 120 136 144 160 176 184 200 208 224 240
|
|
|
291 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|
|
|
292 + B | D | D | x | D | y | D | D | D | a | D | b | D | D | a | D | b | D | z |
|
|
|
293 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|
|
|
294 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
|
|
|
295 | | | | | | | &a.c[0].b | | &a.c[1].b |
|
|
|
296 a |&a.b.x &a.y &a.c |&a.c[0].a |&a.c[1].a |
|
|
|
297 &a.b &a.c[0] &a.c[1] &a.z
|
|
|
298
|
|
173
|
299 The ``Base`` offset of all pointers points to the start of a field or
|
|
|
300 an array and is preceded by an inline descriptor (unless ``Base`` is
|
|
|
301 zero, pointing to the root). All the relevant attributes can be read
|
|
|
302 from either the inline descriptor or the descriptor of the block.
|
|
|
303
|
|
|
304
|
|
|
305 Array elements are identified by the ``Offset`` field of pointers,
|
|
|
306 pointing to past the inline descriptors for composites and before
|
|
|
307 the actual data in the case of primitive arrays. The ``Offset``
|
|
|
308 points to the offset where primitives can be read from. As an example,
|
|
|
309 ``a.c + 1`` would have the same base as ``a.c`` since it is an element
|
|
|
310 of ``a.c``, but its offset would point to ``&a.c[1]``. The
|
|
|
311 array-to-pointer decay operation adjusts a pointer to an array (where
|
|
|
312 the offset is equal to the base) to a pointer to the first element.
|
|
|
313
|
|
|
314 ExternPointer
|
|
|
315 ~~~~~~~~~~~~~
|
|
|
316
|
|
|
317 Extern pointers can be derived, pointing into symbols which are not
|
|
|
318 readable from constexpr. An external pointer consists of a base
|
|
|
319 declaration, along with a path designating a subobject, similar to
|
|
|
320 the ``LValuePath`` of an APValue. Extern pointers can be converted
|
|
|
321 to block pointers if the underlying variable is defined after the
|
|
|
322 pointer is created, as is the case in the following example:
|
|
|
323
|
|
|
324 .. code-block:: c
|
|
150
|
325
|
|
173
|
326 extern const int a;
|
|
|
327 constexpr const int *p = &a;
|
|
|
328 const int a = 5;
|
|
|
329 static_assert(*p == 5, "x");
|
|
|
330
|
|
|
331 TargetPointer
|
|
|
332 ~~~~~~~~~~~~~
|
|
|
333
|
|
|
334 While null pointer arithmetic or integer-to-pointer conversion is
|
|
|
335 banned in constexpr, some expressions on target offsets must be folded,
|
|
|
336 replicating the behaviour of the ``offsetof`` builtin. Target pointers
|
|
|
337 are characterised by 3 offsets: a field offset, an array offset and a
|
|
|
338 base offset, along with a descriptor specifying the type the pointer is
|
|
|
339 supposed to refer to. Array indexing adjusts the array offset, while the
|
|
|
340 field offset is adjusted when a pointer to a member is created. Casting
|
|
|
341 an integer to a pointer sets the value of the base offset. As a special
|
|
|
342 case, null pointers are target pointers with all offsets set to 0.
|
|
|
343
|
|
|
344 TypeInfoPointer
|
|
|
345 ~~~~~~~~~~~~~~~
|
|
|
346
|
|
|
347 ``TypeInfoPointer`` tracks two types: the type assigned to
|
|
|
348 ``std::type_info`` and the type which was passed to ``typeinfo``.
|
|
|
349
|
|
|
350 InvalidPointer
|
|
|
351 ~~~~~~~~~~~~~~
|
|
|
352
|
|
|
353 Such pointers are built by operations which cannot generate valid
|
|
|
354 pointers, allowing the interpreter to continue execution after emitting
|
|
|
355 a warning. Inspecting such a pointer stops execution.
|
|
150
|
356
|
|
|
357 TODO
|
|
|
358 ====
|
|
|
359
|
|
|
360 Missing Language Features
|
|
|
361 -------------------------
|
|
|
362
|
|
|
363 * Changing the active field of unions
|
|
|
364 * ``volatile``
|
|
|
365 * ``__builtin_constant_p``
|
|
|
366 * ``dynamic_cast``
|
|
173
|
367 * ``new`` and ``delete``
|
|
|
368 * Fixed Point numbers and arithmetic on Complex numbers
|
|
|
369 * Several builtin methods, including string operations and
|
|
|
370 ``__builtin_bit_cast``
|
|
|
371 * Continue-after-failure: a form of exception handling at the bytecode
|
|
|
372 level should be implemented to allow execution to resume. As an example,
|
|
|
373 argument evaluation should resume after the computation of an argument fails.
|
|
|
374 * Pointer-to-Integer conversions
|
|
|
375 * Lazy descriptors: the interpreter creates a ``Record`` and ``Descriptor``
|
|
|
376 when it encounters a type: ones which are not yet defined should be lazily
|
|
|
377 created when required
|
|
150
|
378
|
|
|
379 Known Bugs
|
|
|
380 ----------
|
|
|
381
|
|
173
|
382 * If execution fails, memory storing APInts and APFloats is leaked when the
|
|
|
383 stack is cleared
|
