Mercurial > hg > CbC > CbC_llvm

comparison clang/docs/ConstantInterpreter.rst @ 173:0572611fdcc8 llvm10 llvm12

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
reorgnization done
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 25 May 2020 11:55:54 +0900
parents 1d019706d866
children 1f2b6ac9f198
comparison
equal deleted inserted replaced
172:9fbae9c8bf63 173:0572611fdcc8
6 :local: 6 :local:
7 7
8 Introduction 8 Introduction
9 ============ 9 ============
10 10
11 The constexpr interpreter aims to replace the existing tree evaluator in clang, improving performance on constructs which are executed inefficiently by the evaluator. The interpreter is activated using the following flags: 11 The constexpr interpreter aims to replace the existing tree evaluator in
12 12 clang, improving performance on constructs which are executed inefficiently
13 * ``-fexperimental-new-constant-interpreter`` enables the interpreter, emitting an error if an unsupported feature is encountered 13 by the evaluator. The interpreter is activated using the following flags:
14
15 * ``-fexperimental-new-constant-interpreter`` enables the interpreter,
16 emitting an error if an unsupported feature is encountered
14 17
15 Bytecode Compilation 18 Bytecode Compilation
16 ==================== 19 ====================
17 20
18 Bytecode compilation is handled in ``ByteCodeStmtGen.h`` for statements and ``ByteCodeExprGen.h`` for expressions. The compiler has two different backends: one to generate bytecode for functions (``ByteCodeEmitter``) and one to directly evaluate expressions as they are compiled, without generating bytecode (``EvalEmitter``). All functions are compiled to bytecode, while toplevel expressions used in constant contexts are directly evaluated since the bytecode would never be reused. This mechanism aims to pave the way towards replacing the evaluator, improving its performance on functions and loops, while being just as fast on single-use toplevel expressions. 21 Bytecode compilation is handled in ``ByteCodeStmtGen.h`` for statements
19 22 and ``ByteCodeExprGen.h`` for expressions. The compiler has two different
20 The interpreter relies on stack-based, strongly-typed opcodes. The glue logic between the code generator, along with the enumeration and description of opcodes, can be found in ``Opcodes.td``. The opcodes are implemented as generic template methods in ``Interp.h`` and instantiated with the relevant primitive types by the interpreter loop or by the evaluating emitter. 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.
31
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.
21 38
22 Primitive Types 39 Primitive Types
23 --------------- 40 ---------------
24 41
25 * ``PT_{U|S}int{8|16|32|64}`` 42 * ``PT_{U|S}int{8|16|32|64}``
26 43
27 Signed or unsigned integers of a specific bit width, implemented using the ```Integral``` type. 44 Signed or unsigned integers of a specific bit width, implemented using
45 the ```Integral``` type.
28 46
29 * ``PT_{U|S}intFP`` 47 * ``PT_{U|S}intFP``
30 48
31 Signed or unsigned integers of an arbitrary, but fixed width used to implement 49 Signed or unsigned integers of an arbitrary, but fixed width used to
32 integral types which are required by the target, but are not supported by the host. 50 implement integral types which are required by the target, but are not
33 Under the hood, they rely on APValue. The ``Integral`` specialisation for these 51 supported by the host. Under the hood, they rely on APValue. The
34 types is required by opcodes to share an implementation with fixed integrals. 52 ``Integral`` specialisation for these types is required by opcodes to
53 share an implementation with fixed integrals.
35 54
36 * ``PT_Bool`` 55 * ``PT_Bool``
37 56
38 Representation for boolean types, essentially a 1-bit unsigned ``Integral``. 57 Representation for boolean types, essentially a 1-bit unsigned
58 ``Integral``.
39 59
40 * ``PT_RealFP`` 60 * ``PT_RealFP``
41 61
42 Arbitrary, but fixed precision floating point numbers. Could be specialised in 62 Arbitrary, but fixed precision floating point numbers. Could be
43 the future similarly to integers in order to improve floating point performance. 63 specialised in the future similarly to integers in order to improve
64 floating point performance.
44 65
45 * ``PT_Ptr`` 66 * ``PT_Ptr``
46 67
47 Pointer type, defined in ``"Pointer.h"``. 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``).
48 71
49 * ``PT_FnPtr`` 72 * ``PT_FnPtr``
50 73
51 Function pointer type, can also be a null function pointer. Defined in ``"Pointer.h"``. 74 Function pointer type, can also be a null function pointer. Defined
75 in ``"FnPointer.h"``.
52 76
53 * ``PT_MemPtr`` 77 * ``PT_MemPtr``
54 78
55 Member pointer type, can also be a null member pointer. Defined in ``"Pointer.h"`` 79 Member pointer type, can also be a null member pointer. Defined
80 in ``"MemberPointer.h"``
81
82 * ``PT_VoidPtr``
83
84 Void pointer type, can be used for rount-trip casts. Represented as
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"``.
56 91
57 Composite types 92 Composite types
58 --------------- 93 ---------------
59 94
60 The interpreter distinguishes two kinds of composite types: arrays and records. Unions are represented as records, except a single field can be marked as active. The contents of inactive fields are kept until they 95 The interpreter distinguishes two kinds of composite types: arrays and
61 are reactivated and overwritten. 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.
62 101
63 102
64 Bytecode Execution 103 Bytecode Execution
65 ================== 104 ==================
66 105
67 Bytecode is executed using a stack-based interpreter. The execution context consists of an ``InterpStack``, along with a chain of ``InterpFrame`` objects storing the call frames. Frames are built by call instructions and destroyed by return instructions. They perform one allocation to reserve space for all locals in a single block. These objects store all the required information to emit stack traces whenever evaluation fails. 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.
68 113
69 Memory Organisation 114 Memory Organisation
70 =================== 115 ===================
71 116
72 Memory management in the interpreter relies on 3 data structures: ``Block`` 117 Memory management in the interpreter relies on 3 data structures: ``Block``
73 object which store the data and associated inline metadata, ``Pointer`` objects 118 objects which store the data and associated inline metadata, ``Pointer``
74 which refer to or into blocks, and ``Descriptor`` structures which describe 119 objects which refer to or into blocks, and ``Descriptor`` structures which
75 blocks and subobjects nested inside blocks. 120 describe blocks and subobjects nested inside blocks.
76 121
77 Blocks 122 Blocks
78 ------ 123 ------
79 124
80 Blocks contain data interleaved with metadata. They are allocated either statically 125 Blocks contain data interleaved with metadata. They are allocated either
81 in the code generator (globals, static members, dummy parameter values etc.) or 126 statically in the code generator (globals, static members, dummy parameter
82 dynamically in the interpreter, when creating the frame containing the local variables 127 values etc.) or dynamically in the interpreter, when creating the frame
83 of a function. Blocks are associated with a descriptor that characterises the entire 128 containing the local variables of a function. Blocks are associated with a
84 allocation, along with a few additional attributes: 129 descriptor that characterises the entire allocation, along with a few
85 130 additional attributes:
86 * ``IsStatic`` indicates whether the block has static duration in the interpreter, i.e. it is not a local in a frame. 131
87 132 * ``IsStatic`` indicates whether the block has static duration in the
88 * ``IsExtern`` indicates that the block was created for an extern and the storage cannot be read or written. 133 interpreter, i.e. it is not a local in a frame.
89 134
90 * ``DeclID`` identifies each global declaration (it is set to an invalid and irrelevant value for locals) in order to prevent illegal writes and reads involving globals and temporaries with static storage duration. 135 * ``DeclID`` identifies each global declaration (it is set to an invalid
91 136 and irrelevant value for locals) in order to prevent illegal writes and
92 Static blocks are never deallocated, but local ones might be deallocated even when there are live pointers to them. Pointers are only valid as long as the blocks they point to are valid, so a block with pointers to it whose lifetime ends is kept alive until all pointers to it go out of scope. Since the frame is destroyed on function exit, such blocks are turned into a ``DeadBlock`` and copied to storage managed by the interpreter itself, not the frame. Reads and writes to these blocks are illegal and cause an appropriate diagnostic to be emitted. When the last pointer goes out of scope, dead blocks are also deallocated. 137 reads involving globals and temporaries with static storage duration.
93 138
94 The lifetime of blocks is managed through 3 methods stored in the descriptor of the block: 139 Static blocks are never deallocated, but local ones might be deallocated
95 140 even when there are live pointers to them. Pointers are only valid as
96 * **CtorFn**: initializes the metadata which is store in the block, alongside actual data. Invokes the default constructors of objects which are not trivial (``Pointer``, ``RealFP``, etc.) 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.
148
149 The lifetime of blocks is managed through 3 methods stored in the
150 descriptor of the block:
151
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.)
155
97 * **DtorFn**: invokes the destructors of non-trivial objects. 156 * **DtorFn**: invokes the destructors of non-trivial objects.
157
98 * **MoveFn**: moves a block to dead storage. 158 * **MoveFn**: moves a block to dead storage.
99 159
100 Non-static blocks track all the pointers into them through an intrusive doubly-linked list, this is required in order to adjust all pointers when transforming a block into a dead block. 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.
101 207
102 Descriptors 208 Descriptors
103 ----------- 209 -----------
104 210
105 Descriptor are generated at bytecode compilation time and contain information required to determine if a particular memory access is allowed in constexpr. Even though there is a single descriptor object, it encodes information for several kinds of objects: 211 Descriptors are generated at bytecode compilation time and contain information
106 212 required to determine if a particular memory access is allowed in constexpr.
107 * **Primitives** 213 They also carry all the information required to emit a diagnostic involving
108 214 a memory access, such as the declaration which originates the block.
109 A block containing a primitive reserved storage only for the primitive. 215 Currently there is a single kind of descriptor encoding information for all
110 216 block types.
111 * **Arrays of primitives**
112
113 An array of primitives contains a pointer to an ``InitMap`` storage as its first field: the initialisation map is a bit map indicating all elements of the array which were initialised. If the pointer is null, no elements were initialised, while a value of ``(InitMap)-1`` indicates that the object was fully initialised. when all fields are initialised, the map is deallocated and replaced with that token.
114
115 Array elements are stored sequentially, without padding, after the pointer to the map.
116
117 * **Arrays of composites and records**
118
119 Each element in an array of composites is preceded by an ``InlineDescriptor``. Descriptors and elements are stored sequentially in the block. Records are laid out identically to arrays of composites: each field and base class is preceded by an inline descriptor. The ``InlineDescriptor`` has the following field:
120
121 * **Offset**: byte offset into the array or record, used to step back to the parent array or record.
122 * **IsConst**: flag indicating if the field is const-qualified.
123 * **IsInitialized**: flag indicating whether the field or element was initialized. For non-primitive fields, this is only relevant for base classes.
124 * **IsBase**: flag indicating whether the record is a base class. In that case, the offset can be used to identify the derived class.
125 * **IsActive**: indicates if the field is the active field of a union.
126 * **IsMutable**: indicates if the field is marked as mutable.
127
128 Inline descriptors are filled in by the `CtorFn` of blocks, which leaves storage in an uninitialised, but valid state.
129 217
130 Pointers 218 Pointers
131 -------- 219 --------
132 220
133 Pointers track a ``Pointee``, the block to which they point or ``nullptr`` for null pointers, along with a ``Base`` and an ``Offset``. The base identifies the innermost field, while the offset points to an array element relative to the base (including one-past-end pointers). Most subobject the pointer points to in block, while the offset identifies the array element the pointer points to. These two fields allow all pointers to be uniquely identified and disambiguated. 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.
134 261
135 As an example, consider the following structure: 262 As an example, consider the following structure:
136 263
137 .. code-block:: c 264 .. code-block:: c
138 265
147 } c[2]; 274 } c[2];
148 int z; 275 int z;
149 }; 276 };
150 constexpr A a; 277 constexpr A a;
151 278
152 On the target, ``&a`` and ``&a.b.x`` are equal. So are ``&a.c[0]`` and ``&a.c[0].a``. In the interpreter, all these pointers must be distinguished since the are all allowed to address distinct range of memory. 279 On the target, ``&a`` and ``&a.b.x`` are equal. So are ``&a.c[0]`` and
153 280 ``&a.c[0].a``. In the interpreter, all these pointers must be
154 In the interpreter, the object would require 240 bytes of storage and would have its field interleaved with metadata. The pointers which can be derived to the object are illustrated in the following diagram: 281 distinguished since the are all allowed to address distinct range of
282 memory.
283
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:
155 287
156 :: 288 ::
157 289
158 0 16 32 40 56 64 80 96 112 120 136 144 160 176 184 200 208 224 240 290 0 16 32 40 56 64 80 96 112 120 136 144 160 176 184 200 208 224 240
159 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 291 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
162 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 294 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
163 | | | | | | | &a.c[0].b | | &a.c[1].b | 295 | | | | | | | &a.c[0].b | | &a.c[1].b |
164 a |&a.b.x &a.y &a.c |&a.c[0].a |&a.c[1].a | 296 a |&a.b.x &a.y &a.c |&a.c[0].a |&a.c[1].a |
165 &a.b &a.c[0] &a.c[1] &a.z 297 &a.b &a.c[0] &a.c[1] &a.z
166 298
167 The ``Base`` offset of all pointers points to the start of a field or an array and is preceded by an inline descriptor (unless ``Base == 0``, pointing to the root). All the relevant attributes can be read from either the inline descriptor or the descriptor of the block. 299 The ``Base`` offset of all pointers points to the start of a field or
168 300 an array and is preceded by an inline descriptor (unless ``Base`` is
169 Array elements are identified by the ``Offset`` field of pointers, pointing to past the inline descriptors for composites and before the actual data in the case of primitive arrays. The ``Offset`` points to the offset where primitives can be read from. As an example, ``a.c + 1`` would have the same base as ``a.c`` since it is an element of ``a.c``, but its offset would point to ``&a.c[1]``. The ``*`` operation narrows the scope of the pointer, adjusting the base to ``&a.c[1]``. The reverse operator, ``&``, expands the scope of ``&a.c[1]``, turning it into ``a.c + 1``. When a one-past-end pointer is narrowed, its offset is set to ``-1`` to indicate that it is an invalid value (expanding returns the past-the-end pointer). As a special case, narrowing ``&a.c`` results in ``&a.c[0]``. The `narrow` and `expand` methods can be used to follow the chain of equivalent pointers. 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
325
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.
170 356
171 TODO 357 TODO
172 ==== 358 ====
173 359
174 Missing Language Features 360 Missing Language Features
175 ------------------------- 361 -------------------------
176 362
177 * Definition of externs must override previous declaration
178 * Changing the active field of unions 363 * Changing the active field of unions
179 * Union copy constructors
180 * ``typeid``
181 * ``volatile`` 364 * ``volatile``
182 * ``__builtin_constant_p`` 365 * ``__builtin_constant_p``
183 * ``std::initializer_list``
184 * lambdas
185 * range-based for loops
186 * ``vector_size``
187 * ``dynamic_cast`` 366 * ``dynamic_cast``
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
188 378
189 Known Bugs 379 Known Bugs
190 ---------- 380 ----------
191 381
192 * Pointer comparison for equality needs to narrow/expand pointers 382 * If execution fails, memory storing APInts and APFloats is leaked when the
193 * If execution fails, memory storing APInts and APFloats is leaked when the stack is cleared 383 stack is cleared