1==================== 2Constant Interpreter 3==================== 4 5.. contents:: 6 :local: 7 8Introduction 9============ 10 11The constexpr interpreter aims to replace the existing tree evaluator in 12clang, improving performance on constructs which are executed inefficiently 13by 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 17 18Bytecode Compilation 19==================== 20 21Bytecode compilation is handled in ``ByteCodeStmtGen.h`` for statements 22and ``ByteCodeExprGen.h`` for expressions. The compiler has two different 23backends: one to generate bytecode for functions (``ByteCodeEmitter``) and 24one to directly evaluate expressions as they are compiled, without 25generating bytecode (``EvalEmitter``). All functions are compiled to 26bytecode, while toplevel expressions used in constant contexts are directly 27evaluated since the bytecode would never be reused. This mechanism aims to 28pave the way towards replacing the evaluator, improving its performance on 29functions and loops, while being just as fast on single-use toplevel 30expressions. 31 32The interpreter relies on stack-based, strongly-typed opcodes. The glue 33logic between the code generator, along with the enumeration and 34description of opcodes, can be found in ``Opcodes.td``. The opcodes are 35implemented as generic template methods in ``Interp.h`` and instantiated 36with the relevant primitive types by the interpreter loop or by the 37evaluating emitter. 38 39Primitive Types 40--------------- 41 42* ``PT_{U|S}int{8|16|32|64}`` 43 44 Signed or unsigned integers of a specific bit width, implemented using 45 the ```Integral``` type. 46 47* ``PT_{U|S}intFP`` 48 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. 54 55* ``PT_Bool`` 56 57 Representation for boolean types, essentially a 1-bit unsigned 58 ``Integral``. 59 60* ``PT_RealFP`` 61 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. 65 66* ``PT_Ptr`` 67 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``). 71 72* ``PT_FnPtr`` 73 74 Function pointer type, can also be a null function pointer. Defined 75 in ``"FnPointer.h"``. 76 77* ``PT_MemPtr`` 78 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"``. 91 92Composite types 93--------------- 94 95The interpreter distinguishes two kinds of composite types: arrays and 96records (structs and classes). Unions are represented as records, except 97at most a single field can be marked as active. The contents of inactive 98fields are kept until they are reactivated and overwritten. 99Complex numbers (``_Complex``) and vectors 100(``__attribute((vector_size(16)))``) are treated as arrays. 101 102 103Bytecode Execution 104================== 105 106Bytecode is executed using a stack-based interpreter. The execution 107context consists of an ``InterpStack``, along with a chain of 108``InterpFrame`` objects storing the call frames. Frames are built by 109call instructions and destroyed by return instructions. They perform 110one allocation to reserve space for all locals in a single block. 111These objects store all the required information to emit stack traces 112whenever evaluation fails. 113 114Memory Organisation 115=================== 116 117Memory management in the interpreter relies on 3 data structures: ``Block`` 118objects which store the data and associated inline metadata, ``Pointer`` 119objects which refer to or into blocks, and ``Descriptor`` structures which 120describe blocks and subobjects nested inside blocks. 121 122Blocks 123------ 124 125Blocks contain data interleaved with metadata. They are allocated either 126statically in the code generator (globals, static members, dummy parameter 127values etc.) or dynamically in the interpreter, when creating the frame 128containing the local variables of a function. Blocks are associated with a 129descriptor that characterises the entire allocation, along with a few 130additional attributes: 131 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. 138 139Static blocks are never deallocated, but local ones might be deallocated 140even when there are live pointers to them. Pointers are only valid as 141long as the blocks they point to are valid, so a block with pointers to 142it whose lifetime ends is kept alive until all pointers to it go out of 143scope. Since the frame is destroyed on function exit, such blocks are 144turned into a ``DeadBlock`` and copied to storage managed by the 145interpreter itself, not the frame. Reads and writes to these blocks are 146illegal and cause an appropriate diagnostic to be emitted. When the last 147pointer goes out of scope, dead blocks are also deallocated. 148 149The lifetime of blocks is managed through 3 methods stored in the 150descriptor 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 156* **DtorFn**: invokes the destructors of non-trivial objects. 157 158* **MoveFn**: moves a block to dead storage. 159 160Non-static blocks track all the pointers into them through an intrusive 161doubly-linked list, required to adjust and invalidate all pointers when 162transforming a block into a dead block. If the lifetime of an object ends, 163all pointers to it are invalidated, emitting the appropriate diagnostics when 164dereferenced. 165 166The 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 205Inline descriptors are filled in by the `CtorFn` of blocks, which leaves storage 206in an uninitialised, but valid state. 207 208Descriptors 209----------- 210 211Descriptors are generated at bytecode compilation time and contain information 212required to determine if a particular memory access is allowed in constexpr. 213They also carry all the information required to emit a diagnostic involving 214a memory access, such as the declaration which originates the block. 215Currently there is a single kind of descriptor encoding information for all 216block types. 217 218Pointers 219-------- 220 221Pointers, implemented in ``Pointer.h`` are represented as a tagged union. 222Some 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 239Besides the previously mentioned union, a number of other pointer-like types 240have 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 246Void pointers, which can be built by casting any of the aforementioned 247pointers, are implemented as a union of all pointer types. The ``BitCast`` 248opcode is responsible for performing all legal conversions between these 249types and primitive integers. 250 251BlockPointer 252~~~~~~~~~~~~ 253 254Block pointers track a ``Pointee``, the block to which they point, along 255with a ``Base`` and an ``Offset``. The base identifies the innermost field, 256while the offset points to an array element relative to the base (including 257one-past-end pointers). The offset identifies the array element or field 258which is referenced, while the base points to the outer object or array which 259contains the field. These two fields allow all pointers to be uniquely 260identified, disambiguated and characterised. 261 262As 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 279On 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 281distinguished since the are all allowed to address distinct range of 282memory. 283 284In the interpreter, the object would require 240 bytes of storage and 285would have its field interleaved with metadata. The pointers which can 286be derived to the object are illustrated in the following diagram: 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 299The ``Base`` offset of all pointers points to the start of a field or 300an array and is preceded by an inline descriptor (unless ``Base`` is 301zero, pointing to the root). All the relevant attributes can be read 302from either the inline descriptor or the descriptor of the block. 303 304 305Array elements are identified by the ``Offset`` field of pointers, 306pointing to past the inline descriptors for composites and before 307the actual data in the case of primitive arrays. The ``Offset`` 308points 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 310of ``a.c``, but its offset would point to ``&a.c[1]``. The 311array-to-pointer decay operation adjusts a pointer to an array (where 312the offset is equal to the base) to a pointer to the first element. 313 314ExternPointer 315~~~~~~~~~~~~~ 316 317Extern pointers can be derived, pointing into symbols which are not 318readable from constexpr. An external pointer consists of a base 319declaration, along with a path designating a subobject, similar to 320the ``LValuePath`` of an APValue. Extern pointers can be converted 321to block pointers if the underlying variable is defined after the 322pointer 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 331TargetPointer 332~~~~~~~~~~~~~ 333 334While null pointer arithmetic or integer-to-pointer conversion is 335banned in constexpr, some expressions on target offsets must be folded, 336replicating the behaviour of the ``offsetof`` builtin. Target pointers 337are characterised by 3 offsets: a field offset, an array offset and a 338base offset, along with a descriptor specifying the type the pointer is 339supposed to refer to. Array indexing adjusts the array offset, while the 340field offset is adjusted when a pointer to a member is created. Casting 341an integer to a pointer sets the value of the base offset. As a special 342case, null pointers are target pointers with all offsets set to 0. 343 344TypeInfoPointer 345~~~~~~~~~~~~~~~ 346 347``TypeInfoPointer`` tracks two types: the type assigned to 348``std::type_info`` and the type which was passed to ``typeinfo``. 349 350InvalidPointer 351~~~~~~~~~~~~~~ 352 353Such pointers are built by operations which cannot generate valid 354pointers, allowing the interpreter to continue execution after emitting 355a warning. Inspecting such a pointer stops execution. 356 357TODO 358==== 359 360Missing Language Features 361------------------------- 362 363* Changing the active field of unions 364* ``volatile`` 365* ``__builtin_constant_p`` 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 378 379Known Bugs 380---------- 381 382* If execution fails, memory storing APInts and APFloats is leaked when the 383 stack is cleared 384