### Doc/BuildingAndRunning --- id: building-and-running title: Building and Running --- This document describes how to build and run Hermes as a standalone compiler and VM. To use Hermes in the context of a React Native app, see the [React Native](https://reactnative.dev/docs/getting-started) documentation. ## Dependencies Hermes is a C++14 project. clang, gcc, and Visual C++ are supported. Hermes also requires cmake, git, ICU, Python, and zip. It builds with [CMake](https://cmake.org) and [ninja](https://ninja-build.org). The Hermes REPL will also use libreadline, if available. To install dependencies on Ubuntu: apt install cmake git ninja-build libicu-dev python3 zip libreadline-dev On Arch Linux: pacman -S cmake git ninja icu python zip readline On Mac via Homebrew: brew install cmake git ninja ## Building on Linux and macOS Hermes will place its build files in the current directory by default. You can also give explicit source and build directories, use `--help` on the build scripts to see how. Create a base directory to work in, e.g. `~/workspace`, and cd into it. (Tip: avoid naming it `hermes`, as `hermes` will be one of several subdirectories in the workspace). After `cd`ing, follow the steps below to generate the Hermes build system: git clone https://github.com/facebook/hermes.git cmake -S hermes -B build -G Ninja The build system has now been generated in the `build` directory. To perform the build: cmake --build ./build ## Release Build The above instructions create an unoptimized debug build. The `-DCMAKE_BUILD_TYPE=Release` flag will create a release build: cmake -S hermes -B build_release -G Ninja -DCMAKE_BUILD_TYPE=Release cmake --build ./build_release ## Building on Windows To build on Windows using Visual Studio with a checkout in the `hermes` directory: cmake -S hermes -B build -G 'Visual Studio 16 2019' cmake --build ./build ## Running Hermes The primary binary is the `hermes` tool, which will be found at `build/bin/hermes`. This tool compiles JavaScript to Hermes bytecode. It can also execute JavaScript, from source or bytecode or be used as a REPL. ### Executing JavaScript with Hermes hermes test.js ## Compiling and Executing JavaScript with Bytecode hermes -emit-binary -out test.hbc test.js hermes test.hbc ## Running Tests To run the Hermes test suite: cmake --build ./build --target check-hermes To run Hermes against the test262 suite, you need to have a Hermes binary built already and a clone of the [test262 repo](https://github.com/tc39/test262/): hermes/utils/testsuite/run_testsuite.py -b E.g. if we configured at `~/hermes_build` (i.e. `~/hermes_build/bin/hermes` is an executable) and cloned test262 at `~/test262`, then perform: hermes/utils/testsuite/run_testsuite.py -b ~/hermes_build ~/test262/test Note that you can also only test against part of a test suite, e.g. to run the Intl402 subset of the test262, you can specifiy a subdir: hermes/utils/testsuite/run_testsuite.py -b ~/hermes_build ~/test262/test/intl402 ## Formatting Code To automatically format all your changes, you will need `clang-format`, then simply run: hermes/utils/format.sh ## AddressSanitizer (ASan) Build The `-HERMES_ENABLE_ADDRESS_SANITIZER=ON` flag will create a ASan build: git clone https://github.com/facebook/hermes.git cmake -S hermes -B asan_build -G Ninja -D HERMES_ENABLE_ADDRESS_SANITIZER=ON cmake --build ./asan_build You can verify the build by looking for `asan` symbols in the `hermes` binary: nm asan_build/bin/hermes | grep asan ### Other Tools In addition to `hermes`, the following tools will be built: - `hdb`: JavaScript command line debugger - `hbcdump`: Hermes bytecode disassembler - `hermesc`: Standalone Hermes compiler. This can compile JavaScript to Hermes bytecode, but does not support executing it. - `hvm`: Standalone Hermes VM. This can execute Hermes bytecode, but does not support compiling it. --- ### Doc/CodingStandards --- id: coding-standards title: Coding Standards --- ## Hermes Coding Standards This document provides guidance for the kind of code that should go in to the Hermes project. The rules in this document will allow us to scale the project and ensure that the code base remains readable and maintainable. ### Code Quality Code quality standards in Hermes are very strict. While we welcome and support community contributions, expect scrutiny on changes that do not meet the following standards: - Contributions must be well understood and explained in PRs. We cannot accept and maintain contributions that we don't fully understand. - Contributions should not use shortcuts or hacks in the name of expediency. Hermes is a critical piece of infrastructure for many apps and systems, and such code creates ongoing work for maintainers. ### Language Features Hermes uses C++14. Exceptions or RTTI are prohibited, except where needed for interfacing with other software that requires them. GCC language extensions are discouraged for compatibility with MSVC, or they should be conditionally enabled. ### Code Style TODO: This should be sorted and expanded. - Every declaration must have a doc-comment. Naming - Member variables use a "\_" suffix unless they are public, where it is acceptable to omit the suffix. - Classes use pascal case (`MyClass`). - Functions and methods use camel case (`myFunc`). - Variables generally use camel case (`myVar`). We also allow "abbreviated case": "basic block" can be abbreviated as `BB`, "instruction" can be abbreviated as `I`, etc. - Constants use either capitalized snake case (`MY_CONST`) or camel case with "k" prefix (`kMyConst`). Misc - `struct` should be used only when it is a true POD - there are no constructors or destructors of any kind. For everything else use `class`. - Inlining: Only completely trivial (one line) methods can be defined in the class body. The rest should be declared as `inline` both at the declaration and the definition. ### Small incremental changes The project is developed using small incremental changes. These changes can be small bug fixes or minor tweaks. Other times, these changes are small steps along the path to reaching larger stated goals. Long-term development branches suffer from many problems, including the lack of visibility, difficulty of code review, lack of testing of the branch and merge difficulty. Commits that go into the project need to be reviewable. This means that commits need to be relatively small, well documented and self contained. ### Add tests Functional changes to the compiler need to include a testcase. Unit tests and regression tests are critical to the qualification of the compiler. Every bug fix needs to include a testcase. Reduce test cases as much as possible! It is unacceptable to commit big programs because they do not describe the essence of the failure, they are fragile, and they slow testing down. Tests need to be short and focused. ### Format your code clang-format is required to enforce code style and formatting. Commits that only change the formatting of code should go in independent of functional changes. ### Commit messages Here are some guidelines about the format of the commit message: Separate the commit message into a single-line title and a separate body that describes the change. Make the title short (80 chars) and readable. In changes that are restricted to a specific part of the code, include a [tag] at the start of the line in square brackets—for example, “[docs] ... ”. If the commit fixes an issue in the bug tracking system, include a link or a task number. When reverting a change make sure to add a short note that describes why the patch is being reverted. ### Code review The project relies heavily on code review to maintain the software quality. Review other people’s changes! Anybody is allowed to review code and comment on patches. All changes, by all developers, must be reviewed before they are committed to the repository. Smaller changes (if the developer is the de-facto owner of the code base) can be reviewed after being committed. --- ### Doc/CrossCompilation --- id: cross-compilation title: Cross Compilation --- This document describes how to build Hermes in a cross compilation setting, e.g. building for Android, WASM (with Emscripten), or any other platforms different than the host development machines. ## A Two-stage Build Hermes now requires a two stage build proecess because the VM now contains Hermes bytecode which needs to be compiled by Hermes ### Setting up the workspace We will use environment variable `$HERMES_WS_DIR` to indicate the root of your workspace where the `hermes` git checkout directory is a subdirectory. ### 1st Stage: Building the Host Hermes Compiler ``` cd "$HERMES_WS_DIR" # Generate the build system at $HERMES_WS_DIR/build cmake -S hermes -B ./build # Build the Hermes compiler cmake --build ./build --target hermesc ``` ### 2nd Stage: Building the target Hermes The key is that we need to pass a CMake flag `-DIMPORT_HOST_COMPILERS:PATH=$HERMES_WS_DIR/build_host_hermesc/ImportHostCompilers.cmake` during the cross compilation build of Hermes so it can access the host `hermesc` from the first stage to build the VM. This process is currently happened in different places for different platforms: 1. For Android, this happened in `hermes/android/build.gradle` 2. For Apple platforms, this happend in `hermes/utils/build-apple-framework.sh` 3. For Emscripten, you can find an example from the `test-emscripten` job from `hermes/.circleci/config.yml`. Also see more details at [Building with Emscripten](./Emscripten.md) --- ### Doc/Design --- id: design title: Design Overview --- This is the design document for the Hermes Engine. ## JSON estree parser ## JavaScript parser ## IRGen ## Hermes Bytecode Generator The Hermes bytecode generator is responsible for translating the Hermes high-level IR into Hermes bytecode. This section only describes the generation of the opcode stream, not the whole bundle file format that is described in a separate document. The bytecode is a register-based bytecode. The number of registers is infinite, but there are some restrictions on the registers. For example, registers that are allocated to call instructions must be consecutive, and most instructions only accept an 8-bit register index. The first phase of bytecode generation is lowering of some instructions to target-specific instructions. Next, the register allocator allocates registers for each instruction in the lowered IR. Notice that the Hermes IR has a single return value per instruction. We model multiple return values or in-out variables using alloc-stack instructions. One interesting design decision here is that register allocation happens on the IR prior to instruction selection. Performing register allocation prior to lowering is often done in JIT compilers where the lowering phase is trivial and close to a 1:1 translation between high-level IR and the low-level target IR. The lowered Hermes IR is very close to the bytecode format with a few exceptions: the handling of variables, the representation of constants and the representation of stack-allocated variables. Stack allocated registers are implemented as values that are pinned into a specific registers (at least during the lifetime of the stack allocation). Load/Store instructions from the stack allocation values are lowered into MOV instructions. The current register allocation implementation is a very simple linear scan. The allocation has four main steps. First, we number the instructions in the functions, and traverse the basic blocks in the function in reverse-post-order scan. Second, we calculate the liveness graph of the result of each instruction in the function. We propagate this information across the function with a simple data-flow scan. Third, we calculate the liveness interval of each instruction. Finally, we scan the instructions in the function one by one and assign registers. We maintain a list of currently live intervals that correspond to the register file. We represent the register file with a simple bit vector and prefer to allocate registers from the beginning of the file. When we run out of registers we simply allocate new registers. When we reach instructions that require target-specific handling we call the backend to fill in the details. For example, the Hermes backend handles call instructions in a special way. At the moment we do not coalesce values and our PHI nodes generate two MOVs. After register allocation we lower the Hermes IR into pseudo opcodes using a one-to-one or one-to-many translation. There are a few interesting optimizations during this translation. The first interesting optimization is the optimization that eliminates redundant constant jumps. It is possible to eliminate many branches by scheduling basic blocks in a way that maximizes the number of fall-through opportunities. The current algorithm uses a greedy approach where we emit basic blocks in some order (that starts with the entry block), and attempt to place the fall-through destination right after terminators that branch (conditional and unconditional branches) if the block has not been generated already. In the future we may need to investigate if this greedy algorithm is optimal. When we generate the opcode stream we need to encode jump targets. However, when we emit opcodes that refer to jump destinations that we have not yet emitted then we do not know the address of the destination. We solve this problem by emitting a dummy value and keeping a side-table that saves the location that we need to patch. When we finish emitting all of the opcodes we scan the side table and patch all of the locations that refer to previously unresolved addresses. ### Hermes Bytecode Instructions Hermes bytecode adopts variable-length instructions. Each operand to a bytecode instruction has a fixed-type and width, defined by the opcode. For instance, Jmp takes a 1-byte offset as the jump target, while JmpLong takes a 4-byte offset as the jump target. Fixed-type/width instructions allow us to decode them efficiently in the interpreter. However we are trading off with an increasing number of opcodes to handle different operand widths (e.g. two Jmp opcodes instead of one). We believe that we are able to avoid opcode explosion by generating the code smartly. A full list of Hermes bytecode opcodes can be found in BytecodeList.def. There are a few interesting design decisions worth mentioning here: - Registers: We discovered that in all of the Facebook mobile JS code as well as majority of external benchmarks, no function ever uses more than 256 registers. Hence we always use 1-byte to represent register index, which will be most efficient for the normal cases. Spilling is implemented via MovLong which supports 32 bit register indices. - Constants: we achieve constant loading fully through instructions. For fixed-value constants such as undefined, null, true and false, we introduce a corresponding load opcode for each of them into a register (e.g. LoadConstUndefined `dstReg`); For 32-bit integers, we introduce LoadConstInt opcode, which takes a 4-bytes immediate value and load it into a register; for doubles, we introduce LoadConstDouble, which takes a 8-bytes immediate value and load it into a register; finally for strings, we introduce LoadConstString, which takes an index to the string table from which to load into a register. Doing so can significantly reduce the size of the bytecode, however it does introduce a few more opcodes which could slow down the interpreter. - Non-local Variable Access: Local variables are translated to registers. Non-local variables are variables from different scopes/environments. Without a compiler, accessing non-local variables in JavaScript usually means a scope lookup (i.e. locating the closest scope in the scope chain that defines the variable), followed by a symbol lookup in that scope. However with a compiler, it is possible to statically determine the scope of every variable, and hence there is no need for a real scope lookup. In Hermes backend, for each non-local variable access, we simply calculate the delta between the defining scope and the current scope, and locate such scope using the delta (i.e. number of times the VM needs to follow the scope chain) directly. Furthermore, since we know exactly what and how many variables are defined in each scope (except the global scope), we skip the symbol lookup in the scope but instead using a direct index access to retrieve such variable in the located scope. We believe that skipping both scope lookups and symbol lookups can significantly improve the runtime performance. ### Bytecode File Format The bytecode file contains the bytecode as well as necessary metadata and auxiliary data sections for the VM to execute properly. The file format is defined in BytecodeFileFormat.h, and structures as following: - FILE HEADER: The file header contains the MAGIC, the current format version, and a list of global metadata, including the file size, offset of the function header table, offset of the string table, index of the global code and number of functions. - FUNCTION HEADER TABLE: This is a list of function headers. Each function header contains metadata of a function, such as the offset of the function bytecode in the file, number of parameters, size of the frame/environment, size of the bytecode and etc. This list also naturally assigns an index to each function in the file, which makes access to each function convenient in the VM. - STRING TABLE&STORAGE: All the strings used in all functions are uniqued and stored in the section to avoid redundant string storage. This section contains two parts: The string storage, which is a long sequence of raw characters; the string table, which is a list of pairs, each pair represents a string through the offset to the string storage and the length of the string. The string table also naturally assigns an index to each unique string, which makes it convenient to refer to the strings in the bytecode. - FUNCTION BYTECODES: This section is the core section of the bytecode file, containing a list of compiled function body. The function body contains its executable bytecode, along with a few tables that are used by the bytecode, including the exception handler table (tells where to jump to when exception happens), the array buffer (used to initialize constant arrays). Likely there will be a few more tables coming to support RegExp and debug information. ### Serialization / Deserialization Because the Hermes backend is in the same codebase as the VM, there are opportunities for us to share code between them. In particular, we want the serialization in the backend to be able to share the same target data structure as the deserialization in the VM. This introduces some interesting questions: - How can we share data/code without having to link too much code on each side? - How to avoid data copies during both serialization and deserialization? We introduce two design pieces to achieve code sharing efficiently: - Generator: During serialization, we often need many auxiliary data and functionality to aid the process, though many of that will not be needed in the end. To ensure the separation of the complexity and allow the deserialization to share data/code most efficiently, we use a BytecodeModuleGenerator and a list of BytecodeFunctionGenerator for the purpose of generating bytecode and serialization. After all the processing, they will eventually generate a BytecodeModule and a list of BytecodeFunction that contains minimum amount of data/functionality required to generate the bytecode file. Hence we can share this minimum data structure between the backend and the VM. - StreamVector: During serialization, we need to move/copy the part of the auxiliary data from the generator to the shared minimum data structure; during deserialization, we need to move/copy the content of the file into the shared minimum data structure. Both can be expensive if not managed properly. To minimize the copying overhead, we abstracted the complexity using a class named StreamVector. During serialization, StreamVector allows us to move the data out of the generator without copying (through std::vector::swap); during deserialization, StreamVector allows us to take in a raw data pointer to the memory buffer from the file directly, without having to copy them too. ### Interaction with the VM At runtime, the VM will deserialize the bytecode from the file and interpret it. A few components are involved: BytecodeModule: This is the in-memory representation of the whole bytecode file, containing all the bytecode functions. During both serialization and deserialization, this data structure is generated, as a static representation of the whole file. - BytecodeFunction: This is the in-memory representation of a function’s bytecode. - RuntimeModule: This is the dynamic version of the bytecode module, containing necessary runtime information for interpretation. - CodeBlock: This is the dynamic version of the bytecode function, containing necessary runtime information to execute a function. - Domain: A GC-managed proxy which references a set of RuntimeModules, acting as a bridge between the GC heap and the C++ heap. - JSFunction: This is the Function object in JavaScript. It is important (and tricky) to efficiently manage the memory and ownership of these objects properly at runtime. The following figure demonstrates it. Own means one manages the memory of the other through unique_ptr; Pointer means one has a raw pointer to the other, without any ownership. Indirectly Own is a special kind of ownership, which will be explained below. To summarize the ownership: - JSFunction is a JavaScript object, and hence managed by the heap/garbage collector directly. - JSFunction owns a GC-visible reference to a Domain, and a pointer to the corresponding CodeBlock to execute. - CodeBlock contains a pointer to both the RuntimeModule to access runtime information, as well as a pointer to the corresponding BytecodeFunction which contains the static function bytecode to execute. - BytecodeModule owns a list of BytecodeFunction. - RuntimeModule owns a list of CodeBlock, as well as the corresponding BytecodeModule. - Domain owns one or more RuntimeModule. This is the mechanism by which an extant JSFunction keeps the backing bytecode alive. ## Interpreter ## Garbage Collector --- ### Doc/Emscripten --- id: emscripten title: Building with Emscripten --- ## Setting up Emscripten To setup Emscripten for building Hermes, we recommend using `emsdk`, which is the same way Emscripten recommends for most circumstances. Follow the directions on the [Emscripten website for `emsdk`](https://emscripten.org/docs/getting_started/downloads.html) to download the SDK. ``` emsdk install latest emsdk activate latest source ./emsdk_env.sh ``` If you install `emsdk` at `~/emsdk` and activate `latest`, then you should use this shell variable for the rest of these instructions: ``` $EmscriptenRoot = ~/emsdk/upstream/emscripten ``` If you are using the old `fastcomp` instead, replace `upstream` in the above instruction with `fastcomp`. WARNING: The old `fastcomp` backend was [removed in emscripten `2.0.0` (August 2020)](https://emscripten.org/docs/compiling/WebAssembly.html?highlight=fastcomp#backends) ## Setting up Workspace and Host Hermesc Hermes now requires a two stage build process because the VM now contains Hermes bytecode which needs to be compiled by Hermes. Please follow the [Cross Compilation](./CrossCompilation.md) to set up a workplace and build a host hermesc at `$HERMES_WS_DIR/build_host_hermesc`. # Building Hermes With Emscripten and CMake cmake -S ${HermesSourcePath?} -B build \ -DCMAKE_TOOLCHAIN_FILE=${EmscriptenRoot?}/cmake/Modules/Platform/Emscripten.cmake \ -DCMAKE_BUILD_TYPE=MinSizeRel \ -DEMSCRIPTEN_FASTCOMP=1 \ -DCMAKE_EXE_LINKER_FLAGS="-s NODERAWFS=1 -s WASM=0 -s ALLOW_MEMORY_GROWTH=1" # Build Hermes cmake --build ./build --target hermes --parallel # Execute hermes node bin/hermes.js --help In the commands above, replace `${HermesSourcePath?}` with the path where you cloned Hermes, and `${EmscriptenRoot?}` with the path to your Emscripten install. Each option is explained below: * `CMAKE_BUILD_TYPE`: set it to one of CMake's build modes: `Debug`, `Release`, `MinSizeRel`, etc. * `EMSCRIPTEN_FASTCOMP`: set to `1` if using fastcomp, or `0` if using upstream (LLVM) * `WASM`: whether to use asm.js (`0`), WebAssembly (`1`), or both (`2`) * `NODERAWFS`: set to `1` if you will be running Hermes directly with Node. It enables direct access to the filesystem. * `ALLOW_MEMORY_GROWTH`: whether to pre-allocate all memory, or let it grow over time You can customize the build generator by passing the `-G` option to CMake, for example `-G Ninja`. --- ### Doc/Features --- id: language-features title: Language Features --- Hermes plans to target ECMAScript 2015 (ES6), with some carefully considered exceptions. ### Supported - All ES6 JS library functions - ES6 Array searching functions - ES6 String searching functions - Set/Map - WeakSet/WeakMap - Array spread - Arrow functions - BigInt - Destructuring assignment (with array and object "rest" properties) - ES6 Promise (with incompatibilities documented below) - `for..of` loops - Generators (`function*` and `yield`) - [`Intl`, or Internationalization APIs](IntlAPIs.md) - Iteration (with `[Symbol.iterator]`) - Object rest/spread - Optional chaining and nullish coalescing (`?.` and `??`) - Reflection (`Reflect` and `Proxy`) starting from [v0.7.0](https://github.com/facebook/hermes/releases/tag/v0.7.0) - Shorthand property and computed property on object literals - Symbols (including most well-known Symbols) - Template string literals - TypedArrays ### In Progress - Async function (`async` and `await`). - ES modules (`import` and `export`) - `Intl` API glue has been added to enable community contribution of a complete, spec-compliant implementation on multiple platforms - `Symbol.prototype.description` (it's not fully spec-conformant yet. `Symbol().description` should be `undefined` but it's currently `''`). - WeakRef ### Planned - Block scoped variables (`let` and `const`), with support for the temporal dead zone - Classes and method definitions - Expanded Intl functionality (e.g., DisplayNames, ListFormat, PluralRules, RelativeTimeFormat, and Locale) - RegExp match indices and named capture groups ### Excluded From Support - Local mode `eval()` (use and introduce local variables) - Other features added to ECMAScript after ES6 not listed under "Supported" - Realms - `Symbol.species` and its interactions with JS library functions - `Symbol.unscopables` (Hermes does not support `with`) - use of `constructor` property when creating new Arrays in Array.prototype methods - `with` statements ### Miscellaneous Incompatibilities - `arguments` changes in non-strict mode will not sync with named parameters - `Function.prototype.toString` cannot show source because Hermes executes from bytecode - `Promise` is implemented by pre-compiling [the JS polyfill from RN](https://github.com/facebook/hermes/blob/HEAD/utils/promise/index.js) as the [internal bytecode](https://github.com/facebook/hermes/blob/HEAD/lib/InternalBytecode/01-Promise.js) to preserve the current interoperation, hence its conformance to the spec is up to conformance of the polyfill. - In case you want to bring in your own Promise and opt-out Hermes', you can turn it off by passing `-Xes6-promise=0` in CLI or setting `withES6Promise(false)` in the runtime configs. --- ### Doc/GCSafeCoding # C++ Coding With GC Hermes is a JavaScript engine with a garbage collector (GC). Various entities like JS objects, hidden classes, property maps, and so on are allocated in the GC heap and their lifetime is managed by the garbage collector — they can be freed when the GC discovers that they are no longer referenced. Additionally, the GC can automatically move GC-managed entities for heap compaction or other reasons. Writing C++ code that uses GC-managed objects can be difficult because of this — objects that the C++ code is accessing can be freed or moved. This document explains the rules for writing correct and performant GC-safe code. ## The fundamental rule of GC-safe native code The GC can only determine that objects are unreachable or move objects at **GC safepoints**. Without that guarantee, it would be impossible to write GC-safe C++ code. So, the fundamental requirement for GC-safe code is that all "live" pointers to GC-managed entities used by the C++ code **must** be stored in locations known to the GC before a GC safepoint, and must be reloaded from those locations after the GC safepoint. Storing the pointers in a location known to the GC ensures that the GC will consider those objects reachable and will not free them. Reloading the pointers after the safe point guarantees that if the GC moved the objects, the native code will use the updated pointer value. This is all very abstract. In the next sections we will talk about more concrete patterns. ## GC safepoints In practice, a GC safepoint is either an allocation, or a function call that might transitively reach a GC safepoint. Not all C++ calls can reach a GC safepoint. In the Hermes code base, we use naming conventions, parameter types, and explicit doc-comments to communicate this. The rules are: - A function that takes a `Runtime &` or `PointerBase &` parameter (both of which provide access to the GC) is assumed to be able to reach GC safepoints, unless explicitly documented otherwise, or named with a suffix like `_noalloc` or `_nogc`. - A function with an **`_RJS`** suffix may invoke JavaScript code recursively ("Recursive JavaScript"), so it definitely reaches GC safepoints. For example: `JSObject::getNamed_RJS()`, `toString_RJS()`, `toNumber_RJS()`. - A function that does **not** take `Runtime &` or `PointerBase &`, and is not `_RJS`, is generally safe to call without protecting pointers. These rules must be followed absolutely by C++ code — all pointers to heap values must be stored before and reloaded after. (In practice, the values simply "live" in locations known to the GC and the C++ code loads them every time. The C++ compiler is smart enough to optimize out consecutive loads if the underlying value couldn't have changed.) ## GC roots vs heap values The GC needs a starting point to discover which objects are alive. That starting point is the set of **roots** — pointers to GC-managed objects that live *outside* the GC heap, in locations the GC is explicitly told about. Roots include: - The **register stack** — the VM's operand stack used by the bytecode interpreter. - **Locals** — stack-allocated `PinnedValue<>` fields registered via `LocalsRAII`. - **GCScope chains** — dynamically allocated `PinnedHermesValue` slots managed by `GCScope` (legacy). - **Runtime fields** — `PinnedHermesValue` fields inside the `Runtime` object itself, such as well-known prototypes (`arrayPrototype`, `objectPrototype`, etc.). None of these live in the GC heap. They live on the C++ stack or in fixed locations in the `Runtime`. The GC knows about each category and walks them all during collection (see `Runtime::markRoots()` in `Runtime.cpp`). Starting from these roots, the GC traces through every pointer it finds. An object in the GC heap is alive if and only if it is **transitively reachable** from at least one root. Any object not reachable from any root can be freed. If the GC moves an object (for compaction), it updates every pointer it knows about — both roots and pointers stored inside other GC heap objects. The key insight for C++ code: **if you hold a raw pointer to a GC object and that pointer is not stored in a root, the GC does not know about it.** The pointed-to object could be freed (use-after-free) or moved (dangling pointer). This is why all live pointers must be stored in roots before any GC safepoint. ## HermesValue `HermesValue` is the fundamental value type exposed to the GC — it is a NaN-boxed 64-bit value that can contain JS primitives (numbers, booleans, undefined, null, symbols) and, importantly, pointers to GC-managed objects. The GC works on `HermesValue`s, using the NaN-boxing tag bits to determine whether each value is a pointer or a primitive. When a value is a pointer, the GC traces through it, and updates it if the pointed-to object moves. ## PinnedHermesValue `PinnedHermesValue` is a subclass of `HermesValue`. The only purpose of the subclass is to indicate that this `HermesValue` instance is a **GC root** — it lives in memory that is not in the GC heap (and is not movable by the GC), and is known to the GC as a root. Note that declaring something as `PinnedHermesValue` does not *magically* register it as a root. The declaration is a semantic marker: if a value is stored outside the GC heap and is registered with the GC as a root (through `Locals`, `GCScope`, or `Runtime` fields), it should be typed as `PinnedHermesValue` to indicate its "root-ness". `PinnedHermesValue` is essential for writing GC-safe code. The "locations known to the GC" mentioned in the first section are all `PinnedHermesValue` roots. Conceptually, C++ code stores all pointers to GC objects it needs into `PinnedHermesValue` instances before a safepoint and reloads them after. In practice, there are convenient C++ abstractions built on top of `PinnedHermesValue`. ## Handle and MutableHandle A `Handle` is a wrapper around a pointer to an immutable `PinnedHermesValue` (`const PinnedHermesValue *`), where the `PinnedHermesValue` is known to contain a value of type `T` (a number, bool, `JSObject`, etc.). Most internal APIs accept `Handle`s instead of direct pointers. A `Handle<>` (i.e. `Handle`) is an untyped handle that can hold any `HermesValue`. A `MutableHandle` is similar to a `Handle`, but it points to a *mutable* `PinnedHermesValue` and allows updating the stored value. `Handle` is trivially copyable (it is just a pointer) and is designed to be passed by value. An important property: a `PinnedValue` implicitly converts to `Handle`. This means that when a function accepts `Handle`, you can pass a `PinnedValue` directly. ## PseudoHandle `PseudoHandle` holds a GC-managed value *without* protecting it via a root. It is a move-only type — once moved from, the original is invalidated (in debug mode, accessing an invalidated `PseudoHandle` asserts). `PseudoHandle` exists for performance: in many cases a function produces a value and the caller immediately stores it in a root. Wrapping the value in a `PseudoHandle` encodes in the type system that the value is *unrooted* and must be stored somewhere safe before any GC safepoint. Many internal APIs return `CallResult>` for this reason. Common patterns with `PseudoHandle`: ```cpp // Storing into a PinnedValue (moves and invalidates the PseudoHandle): lv.obj = std::move(*result); // Converting to a Handle (allocates in GCScope — legacy): auto handle = runtime.makeHandle(std::move(pseudoHandle)); ``` ## CallResult and error handling `CallResult` is the standard return type for operations that can throw a JS exception. It is either a value of type `T` or `ExecutionStatus::EXCEPTION`. The typical usage pattern is: ```cpp auto result = someOperation_RJS(runtime, args); if (LLVM_UNLIKELY(result == ExecutionStatus::EXCEPTION)) { return ExecutionStatus::EXCEPTION; } // Use *result or result.getValue() to get the value. lv.obj = std::move(*result); ``` Most functions that can trigger GC return `CallResult>` or `CallResult`. The caller must check for exceptions before using the value, and must store the value into a root before the next GC safepoint. ## GCScope (legacy) `GCScope` is a RAII-based variable-sized container of `PinnedHermesValue`. GCScopes are always instantiated in a stack-like manner. They keep themselves in a singly linked list — the root of this list is known to the GC. The GC crawls all GCScopes during garbage collection, making all `PinnedHermesValue` stored there roots. A GCScope is an efficient dynamic container — it dynamically allocates new `PinnedHermesValue` slots internally and returns instances of `Handle<>` or `MutableHandle<>`. However, to prevent unlimited growth, it is configured with a fixed limit (48 by default in debug builds). This limit can be changed per scope. The typical usage pattern is to declare a GCScope at function entry, allocate values inside it as needed (keeping the handles). The GCScope is destroyed automatically when the function exits. **IMPORTANT:** Values allocated in a GCScope must not be used after the scope is destroyed. This mistake is rare but it happens — typically by attempting to return a `Handle<>` that was allocated in a `GCScope` that is about to be destroyed. ### Implicit GCScope allocation `runtime.makeHandle()` and `runtime.makeMutableHandle()`, as well as the `Handle<>` and `MutableHandle<>` constructors, implicitly allocate a slot in the topmost (i.e. most recently created) `GCScope`. This means: - If a function creates `Handle<>` or `MutableHandle<>` values (and does not return them to the caller), it likely needs its own `GCScope`, or at the very least a `GCScopeMarkerRAII` to free the slots when they are no longer needed. A `GCScopeMarkerRAII` is preferred when only one or two handles are allocated. - If a function calls APIs that *return* a `Handle<>`, those handles are also allocated in the topmost `GCScope`, so the same logic applies. Note that this only applies to functions that take `Runtime &` or `PointerBase &` — those are the ones that can access the GCScope and allocate new slots. Functions like `vmcast<>` that do not take these parameters simply cast an existing handle without allocating a new one. Without a local `GCScope` or `GCScopeMarkerRAII`, handles accumulate in the caller's `GCScope`, which can cause it to exceed its slot limit. ## The problem with loops and GCScopeMarkerRAII (legacy) A common problem when using GCScope is allocating handles in a loop, causing potentially unbounded growth of rooted `PinnedHermesValue` slots. This is why GCScope has a limit on the maximum number of handles. One solution is to create a GCScope in the loop body. This works, but is heavyweight — a GCScope preallocates space for 16 handles and must register and deregister itself from the linked list every iteration. `GCScopeMarkerRAII` is a lightweight alternative. It saves the state of a GCScope on creation and frees all subsequently allocated handles on destruction. A typical pattern is to place it at the top of the loop body: ```cpp GCScope gcScope(runtime); // ... for (...) { GCScopeMarkerRAII marker(gcScope); // Handles allocated here are freed at end of each iteration. } ``` Or, more efficiently, create the marker outside the loop and call `flush()` explicitly: ```cpp GCScope gcScope(runtime); // ... auto marker = gcScope.createMarker(); for (...) { gcScope.flushToMarker(marker); // ... } ``` ## Locals and PinnedValue\ (preferred API) **All new code must use `Locals` + `PinnedValue` instead of `GCScope` + `makeHandle()` for rooting local GC values.** Do not introduce new `GCScope` instances or `makeHandle()` calls. Existing code is being migrated incrementally. `Locals` with `PinnedValue` is the preferred way to create rooted storage for local GC values. `Handle` remains the standard type for passing GC values between functions — `PinnedValue` implicitly converts to `Handle`, so the two work together naturally. ### How it works You declare an anonymous struct inheriting from `Locals`, with `PinnedValue` fields for each GC value you need to keep alive. Then create a `LocalsRAII` to register the struct with the runtime. `LocalsRAII` pushes the struct onto a linked list (`runtime.vmLocals`). During GC, `Runtime::markRoots()` walks this list and marks every `PinnedHermesValue` in every `Locals` struct as a root. ```cpp // Locals struct lives on the C++ stack. The PinnedValue fields are // PinnedHermesValues that the GC will mark as roots. struct : public Locals { PinnedValue obj; PinnedValue str; PinnedValue<> genericValue; // untyped — can hold any HermesValue } lv; LocalsRAII lraii(runtime, &lv); ``` ### Why Locals is better than GCScope | GCScope + Handle | Locals + PinnedValue | |---|---| | Dynamically allocates `PinnedHermesValue` slots | Fields are part of the struct — no dynamic allocation | | `Handle` is a pointer to a `PinnedHermesValue` — one level of indirection | `PinnedValue` *is* the `PinnedHermesValue` — direct access | | Easy to accidentally allocate handles in a loop, requiring `GCScopeMarkerRAII` | Fixed set of fields — loops cannot cause unbounded growth | | 48-handle limit per scope (debug assertion) | No limit — number of fields is determined at compile time | ### Assignment patterns ```cpp // From a PseudoHandle (the typical case after a CallResult): lv.obj = std::move(*callResult); // From a CallResult with a HermesValue that you know is a specific type: lv.obj.castAndSetHermesValue(callResult.getValue()); // From a raw pointer: lv.obj = someJSObjectPtr; // From a GCPointer: lv.obj = someGCPointer.get(runtime); // Clearing (so it doesn't keep an object alive unnecessarily): lv.obj = nullptr; ``` ### Passing PinnedValue where Handle is expected `PinnedValue` implicitly converts to `Handle`, so you can pass it directly to functions that accept handles: ```cpp struct : public Locals { PinnedValue O; } lv; LocalsRAII lraii(runtime, &lv); lv.O.castAndSetHermesValue(*objRes); // getPrototypeOf takes Handle, but PinnedValue converts: return getPrototypeOf(runtime, lv.O); ``` ### Reading from PinnedValue ```cpp // Get the underlying typed value: JSObject *rawPtr = lv.obj.get(); // or *lv.obj JSObject *rawPtr = *lv.obj; // Dereference to access members: lv.obj->someMethod(); // Get as HermesValue: HermesValue hv = lv.obj.getHermesValue(); ``` ### Template functions When calling `PinnedValue` member function templates like `castAndSetHermesValue` from a template context where the `PinnedValue` type is dependent, C++ requires the `template` keyword before the member name: ```cpp template void doSomething(Runtime &runtime, HermesValue value) { struct : public Locals { PinnedValue obj; } lv; LocalsRAII lraii(runtime, &lv); // "template" is required because PinnedValue is a dependent type: lv.obj.template castAndSetHermesValue(value); } ``` Without the `template` keyword, the compiler parses the `<` as a less-than operator instead of the start of a template argument list, causing a compile error. This applies to any template member function called on a `PinnedValue` with a dependent type parameter. ### Real-world example From `arrayConstructor` in `Array.cpp`: ```cpp CallResult arrayConstructor(void *, Runtime &runtime) { NativeArgs args = runtime.getCurrentFrame().getNativeArgs(); struct : public Locals { PinnedValue selfParent; PinnedValue self; } lv; LocalsRAII lraii(runtime, &lv); if (LLVM_LIKELY(!args.isConstructorCall() || ...)) { CallResult> selfRes = JSArray::create(runtime, runtime.arrayPrototype); if (LLVM_UNLIKELY(selfRes == ExecutionStatus::EXCEPTION)) return ExecutionStatus::EXCEPTION; lv.self = std::move(*selfRes); } else { CallResult> thisParentRes = NativeConstructor::parentForNewThis_RJS(runtime, ...); if (LLVM_UNLIKELY(thisParentRes == ExecutionStatus::EXCEPTION)) return ExecutionStatus::EXCEPTION; lv.selfParent = std::move(*thisParentRes); auto arrRes = JSArray::create(runtime, lv.selfParent); if (LLVM_UNLIKELY(arrRes == ExecutionStatus::EXCEPTION)) return ExecutionStatus::EXCEPTION; lv.self = std::move(*arrRes); } // ...use lv.self throughout the rest of the function... return lv.self.getHermesValue(); } ``` ### Locals and loops Locals solves the loop problem inherently — the `PinnedValue` fields are a fixed set, so you simply reuse them each iteration without needing `GCScopeMarkerRAII`. However, some existing code uses a `GCScope` + `GCScopeMarkerRAII` alongside `Locals` for functions that call APIs returning `Handle<>` (which require a `GCScope`). In such cases, the `Locals` hold the long-lived values, while the `GCScope` manages short-lived temporaries created by those API calls: ```cpp struct : Locals { PinnedValue O; PinnedValue<> elem; PinnedValue sep; } lv; LocalsRAII lraii(runtime, &lv); GCScope gcScope(runtime); // ... auto marker = gcScope.createMarker(); for (uint32_t i = 0; i < len; gcScope.flushToMarker(marker), ++i) { // Temporary handles created inside the loop are flushed each iteration. // Long-lived values stored in lv.* persist across iterations. auto strRes = toString_RJS(runtime, lv.elem); if (LLVM_UNLIKELY(strRes == ExecutionStatus::EXCEPTION)) return ExecutionStatus::EXCEPTION; lv.sep = std::move(*strRes); } ``` ## Common mistakes ### Holding raw pointers across GC safepoints ```cpp // WRONG — rawPtr may dangle after the allocation: JSObject *rawPtr = someHandle->getObject(); auto newObj = JSObject::create(runtime); // GC safepoint! rawPtr->doSomething(); // rawPtr may be invalid! // CORRECT — store in a PinnedValue, reload after: struct : public Locals { PinnedValue obj; } lv; LocalsRAII lraii(runtime, &lv); lv.obj = someHandle->getObject(); auto newObj = JSObject::create(runtime); // GC safepoint lv.obj->doSomething(); // Safe: PinnedValue is a root ``` ### Holding PseudoHandles across GC safepoints `PseudoHandle` is **not** a GC root — it holds an unrooted value just like a raw pointer. It is equally dangerous to use a `PseudoHandle` after a GC safepoint. This is easy to miss because `PseudoHandle` looks like a "safe" smart pointer type, but it is not rooted. Watch especially for **multi-step creation patterns** where two `::create()` calls are made in sequence: ```cpp // WRONG — ctor PseudoHandle is stale after the second create(): auto ctor = NativeConstructor::create(runtime, ...); auto proto = JSObject::create(runtime); // GC safepoint — ctor is stale! lv.ctor = std::move(ctor); // Too late — ctor is already stale! // CORRECT — root the PseudoHandle before the next allocation: lv.ctor = NativeConstructor::create(runtime, ...); // Root immediately. lv.proto = JSObject::create(runtime); // GC safepoint — lv.ctor is safe. ``` This bug often goes undetected because the stale value is still valid most of the time — the GC only moves objects during compaction, which is rare. Enable `HERMESVM_SANITIZE_HANDLES` (enabled by default in ASAN builds) to catch these bugs deterministically by moving the heap after every allocation. ### Returning a Handle from a destroyed GCScope or Locals ```cpp // WRONG — the Handle points into the destroyed GCScope: Handle createThing(Runtime &runtime) { GCScope gcScope(runtime); auto handle = runtime.makeHandle(JSObject::create(runtime)); return handle; // gcScope destroyed here — handle dangles! } // WRONG — returning a Handle from a PinnedValue that is about to be destroyed: Handle createThing(Runtime &runtime) { struct : public Locals { PinnedValue obj; } lv; LocalsRAII lraii(runtime, &lv); lv.obj = ...; return lv.obj; // lraii destroyed here — Handle dangles! } ``` Instead, return a `PseudoHandle` (which copies the value out, not a pointer to the root): ```cpp // CORRECT — return a PseudoHandle: CallResult> createThing(Runtime &runtime) { struct : public Locals { PinnedValue obj; } lv; LocalsRAII lraii(runtime, &lv); lv.obj = ...; return PseudoHandle::create(*lv.obj); } // CORRECT — write into a caller-provided MutableHandle: void createThing(Runtime &runtime, MutableHandle result) { // No local rooting needed — we write directly into the caller's root. auto res = JSObject::create(runtime); result = res.get(); } // CORRECT — return a HermesValue (caller roots it, so risky): CallResult createThing(Runtime &runtime) { struct : public Locals { PinnedValue obj; } lv; LocalsRAII lraii(runtime, &lv); lv.obj = ...; return lv.obj.getHermesValue(); } ``` ### Forgetting to check for exceptions ```cpp // WRONG — using the value without checking for exception: auto result = someOperation_RJS(runtime, args); lv.obj = std::move(*result); // May dereference an exception! // CORRECT: auto result = someOperation_RJS(runtime, args); if (LLVM_UNLIKELY(result == ExecutionStatus::EXCEPTION)) return ExecutionStatus::EXCEPTION; lv.obj = std::move(*result); ``` ### Null prototype handling When traversing prototype chains, always check for null: ```cpp auto protoRes = JSObject::getPrototypeOf(obj, runtime); if (LLVM_UNLIKELY(protoRes == ExecutionStatus::EXCEPTION)) return ExecutionStatus::EXCEPTION; if (!*protoRes) { lv.O = nullptr; // End of prototype chain } else { lv.O.castAndSetHermesValue(protoRes->getHermesValue()); } ``` --- ### Doc/GenGC --- id: gengc title: The GenGC Garbage Collector --- GenGC used to be the default garbage collector for Hermes, and aims to provide a generational garbage collector that returns memory to the OS aggressively and frequently. The newer GC is called [Hades](./Hades.md), and it has much lower pause times than GenGC. We recommend most users use Hades instead. Throughout this document, we will refer to the **heap**, which in this context means the memory space where JS objects reside. This is separate from the C and C++ `malloc` heap, and in general if this document says "heap" it means the space for JS objects. # Heap Segments The heap is made out of many fixed-size regions of memory known as **heap segments** (or more briefly as **segments**). Currently these segments are 4 MiB, but this can be changed with the CMake build configuration variable `-DHERMESVM_HEAP_SEGMENT_SIZE_KB=number`. Memory is acquired and released on a per-segment basis. Segments are allocated using `mmap` on POSIX systems and `VirtualAlloc` on Windows systems. These functions allow virtual memory to be requested for some space, and allows us to unmap subregions so that alignment can be guaranteed. This is done in separate regions because we found that a lot of devices have trouble allocating enough virtual memory upfront to have the entire heap be contiguous. By allowing it to grow virtual address space usage with the size of the heap (and shrink as well), it works on a broader set of devices. We chose 4 MiB as the size of segments because it was small enough to not exhaust virtual address space, while also being large enough to not have a lot of overhead in managing the segments. Each heap segment is aligned to begin on a pointer address that is a multiple of its size. For example, if segments are 4 MiB wide, then their start addresses are aligned on a 4 MiB boundary (the low 22 bits are all 0). This means for any pointer into the JS heap, you can get the segment start address with a simple bitwise-and operation. All metadata for the segment is stored at the front of the segment. At the beginning of a segment, there is a small amount of memory reserved for some metadata about the heap. Specifically, the following things are kept there: - Segment ID: explained in [Compressed Pointers](#compressed-pointers) - CardTable: explained in [Generations](#generations) - MarkBitArray: explained in [Mark Phase](#mark-phase) - Guard page: a page of memory that is protected from reads and writes to ensure bugs in the VM or GC don't accidentally overwrite metadata. The rest of the segment is free space available for JS values to be allocated into. See [`AlignedHeapSegment::Contents`](../include/hermes/VM/AlignedHeapSegment.h) for details about the layout of a heap segment. # Object Types In order to determine reachability, we need to be able to discover what objects point to. To do this for the variety of types in Hermes, we define a system of metadata for each object, associated to its type which is encoded as a `VTable`. Metadata is built once for the first Runtime created, and is then re-used for every subsequent runtime. The metadata describes at what offsets from the head of an object there are pointers. It also describes for any array type where the length of the array can be found, so a dynamic number of pointers can be found. This design allows pointers to be marked without performing any type checks, branches, or virtual dispatch. The `VTable *` is embedded in the header of everything allocated on the heap. This is represented by the C++ superclass of all heap objects, called `GCCell`. This way, given a pointer to something in the heap, its type (and pointer metadata) can be found. The type is stored as a `CellKind` enum. The `VTable` also includes function pointers for dynamic dispatch. This is used to implement type-based dispatch for things like property accesses and function calls. # Generations GenGC is so named because it is **generational**, meaning it manages groups of allocated objects based on their age. Age is determined by how many collections an object has survived. GenGC has two generations: the **Young Generation** (YG) and **Old Generation** (OG). Allocations go initially into YG, and if they survive the first YG collection cycle, they are promoted to OG. The OG is collected less frequently and over a larger number of objects. YG is collected frequently because it is assumed that there are a lot of objects that were allocated but became garbage quickly. This is known as the [Generational Hypothesis](https://www.memorymanagement.org/glossary/g.html#generational.hypothesis): young objects are more likely to die than old objects. The young generation of GenGC is a single segment, regardless of the size of the heap as a whole. Since YG is much smaller than OG, this is also a much shorter pause to collect YG. Since the YG is also a single segment, it's very fast to check if a pointer is a YG pointer: get the segment start address and compare to the YG start address. The allocation algorithm is as follows: - Attempt to allocate into the YG segment by bumping a pointer called the "level" of the segment up. If the level would go past the end of the segment, it fails - If the bump allocation succeeds, the allocation is complete and control returns to the VM - If the bump allocation fails, start a YG collection cycle. This will evacuate the YG into the OG, and leave some empty space. - Try bump allocation again after the YG collection cycle completes. If it succeeds, return. - Else, try to allocate directly into the OG. - If the OG is full, start a full collection cycle (collect garbage in both the YG and OG). Once that completes, try allocating directly into OG again. - If all that fails, that means there's not enough space for the allocation, raise an Out of Memory (OOM) error The old generation of GenGC is a list of segments, each of which is created after an allocation failed in the previous segment. The OG maintains an allocation context which remembers the most recent active segment, and this is where promoted YG objects are allocated into. Once the OG has reached its configured size limit, it will do a full collection, trying to free garbage inside the OG. There are more details on collection cycles in the [Collection Cycles](#collection-cycles) section. ## Allocate directly into the Old Geneneration (Pre-Tenuring) Sometimes there are applications where the generational hypothesis doesn't hold true, or in other words they allocate more objects that are long-lived than short-lived. This typically occurs during the initialization period of an application. If this rule applies to your application, you can request this behavior from Hermes by changing the `GCConfig` that's used at Runtime construction time: ```cpp hermes::vm::GCConfig::Builder gcConfigBuilder{}; gcConfigBuilder .withAllocInYoung(false) .withRevertToYGAtTTI(true); std::unique_ptr runtime = makeHermesRuntime( hermes::vm::RuntimeConfig::Builder() .withGCConfig(gcConfigBuilder.build()) ); ``` The `AllocInYoung` parameter defaults to `true`, and controls whether allocations go into YG by default or OG. The `RevertToYGAtTTI` parameter defaults to `false`, and is unused unless `AllocInYoung` is true. See the full documentation of [GCConfig](../public/hermes/Public/GCConfig.h) for more details and other configuration options. # Collection Cycles GenGC determines garbage that can be collected in a program based on what is reachable in the graph of objects. The graph has **roots** that define the entrypoint to the graph. These are typically things like variables on the JS call stack. From the roots, the entire graph of objects is traversed by following each property to another object. Think of it as similar to a traditional graph search algorithm, although we make many optimizations specific to the heap structure. GenGC has two different types of garbage collection cycles (abbreviated as "GC"). There is a Young Generation Collection or YG GC, and a Full Collection or full GC. A YG GC collects only objects present in the YG, and promotes objects that are reachable to the OG so they are collected less frequently. A full GC collects both the OG and YG simultaneously, and determines the reachability of every object in the heap. There are two common concepts across both types of collections: - Mark: Marking means setting some state related to an object to say that it was found to be reachable during the traversal of the heap. In GenGC's case, this is often referred to as a "mark bit" - Sweep: Sweeping means reclaiming unused space so that it can be re-used by the allocator. This can look very different depending on the generation ## Young Generation Collection When a YG collection is triggered, it first needs to mark the roots of the object graph. Because YG collections occur very frequently, we want the set of roots to be small. To achieve this we ignore any roots that are known to be only in the OG. When each pointer is discovered for the first time, an allocation is made in the OG for the same size, the YG object's contents are copied, and a forwarding pointer is left in the header of the YG object pointing to the new OG object. After that, if we see the same pointer again, we replace it with the value of the forwarding pointer. We also need to consider any OG objects that point into YG as part of the root set. That is handled by a separate mechanism during JS execution, detailed below in the section on [Write Barriers](#write-barriers). To find all the reachable objects, we take advantage of the linear nature of OG, and scan linearly from the original end of the allocated region, until there aren't any more promoted objects. Each promoted object is scanned for its own pointers. This is how all YG objects are discovered. It's similar to a semi-space algorithm where the second space is the OG. Once the objects are all moved, any weak references pointing to YG objects are updated if the object is still alive, and then any finalizers are run by iterating over a list of finalizers. ### Write Barriers As part of the root set, we also consider any OG objects that point into YG. To determine where these exist without iterating over the whole OG, we use a **write barrier** whenever a pointer value is written to during JS execution. If it would create an old -> young pointer, we want to mark the source object as part of the root set of YG. The way we do this is by classifying a small region of memory in the OG as a **card**, currently 512 bytes. We determine the card for a pointer using the same alignment trick to get the base address of the segment, then use division to figure out the card index. The **card table** is a list of bytes stored in the header of the segment, and when we find an object pointing into the YG, we "dirty" its card by setting the byte value to 1. We don't use a bitmap because the card table is only 8 KiB, and shrinking it further isn't worth it. During YG collection time, we can quickly scan each card table for the set of dirtied cards, then we mark all of the objects on that card. We use a separate **card object table** to find the first object for a card. That table contains another byte per card, except it is signed. If the sign is positive, it means "go back that many bytes to find the first object on this card". If the sign is negative, it means "go back that many cards and check the table at that index". This encoding scheme allows a low memory cost way to jump across very large objects. Note that the way cards are dirtied means there's a chance of promoting some YG objects that aren't actually live. This tradeoff is chosen so the cards take up less memory and can be scanned quickly. Smaller cards are more precise, but take up more memory and require more scanning. ## Full Collection A full collection is much larger than a YG collection, so it happens less frequently. It needs to determine the reachability of every object in the heap. A full collection is triggered when the OG doesn't have enough space to satisfy an allocation from a YG promotion or a direct-to-OG allocation. ### Mark Phase The collection begins with a call to `markRoots`, although this time additionally marking roots known to only point into the OG, such as the `IdentifierTable`. The first time an object is encountered, it sets a bit in the mark bit array, so future accesses know that it has already been found. Then we push the newly discovered object on top of a **mark stack**. The mark stack is drained by popping off the top object, scanning all of its pointers, and pushing objects it discovers onto the mark stack. There are two changes implemented to prevent the mark stack from growing without bound: - If a pointer to an object is discovered that is after the current address, it isn't pushed on the mark stack. Instead, we jump to the next marked bit when the mark stack is empty. If the pointer is before the current address, it has to be pushed on the stack because we won't go backwards in the heap normally - If the mark stack overflows a limit, we drop the whole stack and re-scan from the beginning of the heap. Since many objects have already been marked, this will go much faster than previous times. It's guaranteed to terminate because in the worst case eventually every object will be marked and there's nothing to collect. Once the marking is complete this way, full reachability is known, and sweeping can begin. ### Weak Map resolution However, one problem to be handled are **weak references**, which are pointers that do not keep what they point to alive. Now that we know reachability, we know which weak pointers to make null. But there's a special case of the JS type `WeakMap` that has to be handled: the keys are weak, and the values are strong, unless they keep the key itself alive. This means the values can't be marked until the key is determined reachable through some other means. We delay marking any WeakMap key/value pairs until the end of marking. Then for each WeakMap, and for each key that is reachable in the weak map, we then mark the value. If marking the value ends up making another WeakMap key reachable, we then need to mark that. We repeat this for every key that becomes reachable until there's nothing more to mark. At that point we can finally null out keys that were never found to be reachable. ### Sweep & Compact Phases Now that full reachability has been computed, we know which objects are garbage. We want to reclaim that memory so that it can be allocated again. To do so, we will **compact** all live memory down so that there's no space between them, overwriting the space that was used by dead objects. To do this, we iterate through every live object in the heap using the mark bits, and for each one we compute its new address. We place that new address as a forwarding pointer in the header of the object (displacing the `VTable *` to a temporary vector to avoid losing the type information). Once a forwarding pointer has been determined for everything in the heap, we do a second pass to fixup pointers within objects to use the forwarded value. Finally, we copy the memory from the previous location to the new location, overwriting whatever used to be there. The end result of this is that all live memory sits right next to each other in the heap segments, and all dead memory has now been reclaimed for the allocator. We use `madvise` on POSIX systems to tell the operating system that the leftover memory is now not needed by the program, and it's free to be paged out and zero filled if the OS needs to. At this point control returns to the JS engine, typically to finish the allocation that started the collection. --- ### Doc/Hades --- id: hades title: The Hades Garbage Collector --- Hades is a garbage collector for Hermes that aims to improve pause times by an order of magnitude over GenGC. The main principle Hades uses to achieve those low pause times is that most of the garbage collection work happens in a background thread concurrently with the interpreter running JavaScript code. This is distinct from GenGC, which only runs on a single thread which is shared with the interpreter. # Enabling Hades In local builds on the command line using CMake (which forwards to CMake), Hades is the default GC used, and currently the only GC supported for production use. The GC being used is controlled by the CMake variable `-DHERMESVM_GCKIND=value`. To use a pre-built package of Hermes with Hades enabled, check the [Releases page on Github](https://github.com/facebook/hermes/releases). As of right now, there aren't any available, but we'll be making one available with v0.8 and later. ## Check Which GC is Used If you want to know what GC is being used in your application, you can find out with some JS: ```js const gcName = HermesInternal.getRuntimeProperties().GC; // If you're running Hermes on the command line, use print. print(gcName); // If you're running Hermes in some kind of framework like React Native, // console.log should exist. console.log(gcName); ``` This will print one of: - `"hades (concurrent)"`: You're using Hades in concurrent mode - `"hades (incremental)"`: You're using Hades in [incremental mode](#incremental-mode) # Basics Most of the basic heap structure of Hades is similar to GenGC, so it is recommended to read the [GenGC Documentation](./GenGC.md) first, in particular the following sections: - [Heap Segments](./GenGC.md#heap-segments) - [Object Types](./GenGC.md#object-types) - [Generations](./GenGC.md#generations) - [Write Barriers](./GenGC.md#write-barriers) # Generations Similarly to GenGC, Hades also has two generations: the **Young Generation** (YG) and **Old Generation** (OG). Allocations go initially into YG, and if they survive the first collection they go into OG. YG works exactly the same as GenGC, but OG has a different allocation strategy that allows for gaps. ## Freelist Allocator Hades's OG is a list of heap segments, and each heap segment maintains a **Free List** of empty space. Each **Free List Cell** points to the next cell, called an explicit free list. This is opposed to an implicit free list, where the length is used to traverse both free and used cells. A free list is used because it allows empty space to be left where it is, without requiring compaction. This is a requirement for concurrent allocations and sweeping. Furthermore, the free list is **size-segregated**, meaning each size class gets a separate free list. In other words, cells of size `N` only point to other cells of size `N`. This allows an allocation of size `N` to be satisfied instantly with the head of the free list. Each free list head is stored at an index in a fixed-size array for small cell sizes. These are known as **buckets**. Hades does not do any rounding up of sizes beyond the required heap alignment of 8 bytes. This means there is one bucket for each multiple of 8, up to 2048 bytes. From 2048 bytes to the maximum heap segment size (4 MiB) the buckets go by powers of 2. For large buckets, we store cells that are greater than or equal to the size bucket, but less than the next power of 2. Cells that need less than the size of the free list cell **carve** out a small piece of the cell, and put the remaining piece on a the free list corresponding to its new size. Due to having these free lists be per-segment, we need a quick way to find which segment has free space for a given size. We do this with a series of bit arrays, where bits are flipped to 0 as a free list is exhausted in a segment, and flipped back to 1 when sweeping frees some cells. We have per-segment free lists so that sweeping and compaction (which also operate on a per-segment basis) can destroy them efficiently and create a new list. It can do this to easily coalesce adjacent free regions. # Collection Cycles Hades has two different types of collections: a YG collection (YG GC) and an OG collection (OG GC). The former is almost exactly the same as GenGC's, so we won't repeat it here. The OG GC is very different though, because it runs concurrently in a background thread. For the purposes of distinguishing these two threads, we'll name them as follows: - **Mutator Thread**: The thread running the JS interpreter - **GC Thread**: The thread running any GC operations such as marking or sweeping Note that currently there is only ever a single GC thread at any point in time. We also cache the thread and reuse it instead of making a new one for each collection. There are three different locks used throughout the GC: - The **GC Mutex** is used to protect structures like mark bits, card tables, and the free lists - The **WeakRef Mutex** is used to protect structures used during weak ref marking - The **Write Barrier Mutex** is used to protect a small buffer used by write barriers and concurrent marking The GC mutex is used to protect most things, as they tend to all be accessed at the same time. There was no need for finer grained locks yet, with the exception of the write barrier mutex because write barriers are executed all the time. An OG GC is started once the OG is about 75% full. We start it a bit early so that it can complete sweeping before reaching 100% full and avoid blocking any allocations. ## Mark Phase The first step of an OG GC is to mark all of the roots of the object graph. We only ever start an OG GC when YG is empty, so there's no need to mark any of YG. Marking an object consists of the following steps: - Using mark bits, check if an object has been visited already - If it has been visited already, there's nothing to do - If not, push it onto a **mark stack** that will be drained later - Set its mark bit - If the object pointed to is a WeakMap, put it onto a separate stack (see [Weak Map Resolution](./GenGC.md#weak-map-resolution)) Draining the mark stack works as follows: - Acquire a lock on the GC mutex - Check if the write barrier buffer has objects that need to be marked, if so, add them to the mark stack - While we've marked fewer than a certain number of bytes, defaults to 8 KiB - Pull one object off the mark stack - Get its type metadata (see [Object Types](./GenGC.md#object-types)) - Use the metadata to find pointers to other objects - Those other objects will be pushed on the stack - Release the lock on the GC mutex This can run almost entirely uninterrupted on the background thread since very few things need to acquire the GC mutex. The most common way to interrupt marking is when YG fills up, as it requires the GC mutex in order to evacuate YG. ### Write Barriers There's an important race condition to consider when thinking about concurrent marking: what happens if a pointer is modified while we're reading it? There are two different races that are possible here: - A non-atomic read of the pointer might race with a non-atomic write, and the reads or writes might "tear" (meaning you see only part of the write) - You might miss marking the old value or the new value The first is handled on 64-bit platforms because all of the reads are of a 64 bit value, which can be atomically handled cheaply on a 64-bit CPU. See the [Incremental Mode](#incremental-mode) section for what we do on a 32-bit CPU. The second problem is harder to solve. If we see the old value, and the new object isn't marked anywhere else, we would accidentally think it's garbage and collect it! Alternatively, if we see the new value, the old value won't be marked. This would be a problem if the old pointer was moved from one object to another, but we had already marked the second object. In order to fix this, we need to know when a pointer is modified during concurrent marking. Hades implements this through an additional write barrier. This write barrier is based on a principle called "Snapshot at the Beginning" (SATB). The principle is that we want to collect the OG based on a snapshot of the heap when the collection began. Which means if a pointer is changed, we want to make sure we mark the old value instead of the new value. This might feel counter-intuitive compared to the more common alternative approach known as "Incremental Update" (IU), where the new value is marked. The reason Hades uses SATB instead is that it has a nice guarantee: you'll never need to revisit any object you have already marked. This means there is a finite upper bound on the amount of work marking has to do. IU write barrier based systems often have a race near the end, where the GC thread needs to pause the mutator thread to try and complete marking as fast as possible. If it exceeds a time quota, it resumes the mutator and tries again later. We avoid this complexity with our SATB barrier. A second benefit of SATB is that we can treat any allocations made into OG between the start and end of the collection as alive by default, without needing to mark them. And the final benefit of SATB is that there is never a need to mark the roots again to finish a collection, as their old values were handled at the start of the collection while the mutator was paused. The barrier works by pushing the old value onto a small fixed size buffer, which has space for 128 elements. Once it fills up, the Write Barrier Lock is taken to "flush" the buffer into a separate mark stack used by the concurrent marker. This means a lock is only taken every 128 write barriers. It uses a separate mutex from the GC mutex to ensure a write barrier is not blocked for very long if the GC thread happens to be reading from the separate mark stack. ## Complete Marking Once the mark stack is empty, there are a few details that need to be handled in order to complete marking and move on to sweeping: - Flush any remaining write barrier pointers left - Handle WeakMap resolution - Fix weak references (WeakRefs) Handling these things can be very tricky concurrently, so in order to prevent bugs and infinite loops, we pause the mutator during this time. Even though SATB write barriers don't require the mutator to pause, these other operations do require a pause, so unfortunately this is still required. Flushing the remaining write barrier pointers just means copying the pointers into the mark stack and draining it one more time. This could potentially take a very long time, but in practice that is exceedingly rare. WeakMap resolution is handled in the same way that GenGC handles it. We do this during a mutator pause mostly because we didn't want to rewrite the algorithm to work in a concurrent context, as it's already very complicated on its own. Weak References also need to be cleared if they point to something that is now garbage, and this is much easier to do with the mutator paused. Otherwise the mutator would need a lock to read a weak reference value. This could be improved to simply be an atomic operation in the future, but for now this can't be atomic. Once that's all taken care of, we can move on to sweeping. ### WeakRef Read Barriers There's a caveat to mention about WeakRefs and the SATB barrier. If you read a pointer out of a weak reference and store it in an object on the heap, SATB won't record the change, and the object might not be found reachable. Something similar can happen if a weak ref is read and placed into a root. To fix this, we have WeakRef reads perform a barrier on the pointer being read. This conservatively assumes the pointer being read is alive. WeakRefs are not read from that often, so this was deemed an acceptable cost. Note that there also weak roots, such as the HiddenClass cache stored in each CodeBlock. These do not perform a read barrier, specifically because they are only ever used for comparisons. They never produce a pointer that was otherwise dead. A possible simplification of this in the future could use a HiddenClass ID instead of a pointer, as it achieves the same effect without requiring a special case. ## Sweep Phase Once complete reachability information is known, the OG GC turns off the SATB barriers. The sweeper iterates over one segment at a time, allowing the mutator to interleave. This is specifically allowed because the sweeper only ever modifies garbage objects that aren't used, therefore there's no races. It holds the GC mutex to prevent YG from allocating into the OG while it's being swept. The process works as follows: - Acquire a lock on the GC mutex - Clear one heap segment's free list - Iterate linearly over cells, using the embedded length to skip over live cells - Check if a cell is new garbage using its type tag - If it is not new garbage, continue to the next cell - If it is new garbage, turn it into a free list cell. - Contiguous unused regions are added as a single region onto the new free list - Once all cells in the segment have been processed, release the lock Once that process is completed for every heap segment, sweeping completes and the OG collection is over. ## Compact Phase Compacting live memory to be closer together is still a beneficial concept in Hades, as it allows us to return unused memory to the OS, and reduces the fragmentation of the free lists for mostly empty heap segments. Implementing it is more tricky than GenGC though, as we can't modify pointers concurrently with the mutator thread. Due to these restrictions, we can currently only compact a single segment (called the compactee) for each full collection. Compaction runs as part of the collection cycle and flows as follows: 1. At the start of an OG collection, determine whether the heap is currently larger than its target size. If so, select and record a segment to compact. 2. Write barriers start dirtying cards for pointers pointing into the compaction candidate. This will continue until the compaction is fully complete. 3. Marking begins. During marking, we dirty cards in the card table corresponding to any on-heap pointers that point into the compaction candidate. Any YG collection that occurs during marking needs special care. Promoted objects will not be scanned by the OG since they are allocated as marked, so they need to be scanned for compactee pointers after they have been promoted. Furthermore, the card table cannot be cleared at the end of the YG collection, since that would erase information from the ongoing compaction. 4. During the STW pause, the internal state of the GC is updated to signal that all pointers into the compactee have been marked, and that the next YG collection should complete the compaction. 5. Sweeping. The segment identified for compaction will not be swept, however compaction may take place during sweeping if the next YG collection starts before sweeping is complete. Note that write barriers will continue to be active until compaction is complete, since new pointers from the OG into the compactee may be added. 6. Compaction. The next young gen collection evacuates both the YG and the compactee. It will mark long lived roots and update pointers based on the previously dirtied cards. Combining compaction with YG collections lets us share the overhead of updating roots, and lets us avoid tracking pointers from the YG into the compactee. 7. The now empty segment is released by the GC and returned to the OS. ## Incremental Mode Hades's concurrent marking relies on being able to read a 64-bit value atomically at the same time it might be modified by the mutator. If the underlying hardware supports this natively, then we use it. However, some hardware does not support doing those atomic reads in a lock-free manner, primarily 32-bit ARM CPUs. Since Hermes's main target is mobile devices, it's important for us to still support them, and have some of the fast pause time guarantees that Hades gives. In order to do this, on 32-bit platforms we don't use any other threads, and instead run Hades in "incremental mode". This means instead of marking objects concurrently on the GC thread, we use a portion of each YG GC to do some OG GC work. This means the OG GC is completed incrementally on each individual YG GC. Each YG GC takes a little bit longer while an OG GC is active, but the penalty is small enough to still have better guarantees than running a fully blocking OG GC. The concurrent mode of Hades has faster pauses and is preferred to be used if possible, but incremental mode has to be used on most 32-bit CPUs. You can also use incremental mode if threads aren't supported on your platform, or if you prefer to not use threads for some other reason. --- ### Doc/HighLevelOptimizations --- id: high-level-optimizations title: High Level Optimizations --- JS authors frequently use high level library functions which they expect to perform efficiently. They call these in conjunction with other library calls to write code which has similarities to functional programming languages. Executing this kind of code in Hermes can be slow due to the compiler not having proper visibility into the JS library. However, we can get some information about what is being called in certain scenarios, such as with `-fstatic-builtins` or in actual typed SH code. This document is a place to put some ideas on how to make specific scenarios more efficient in the future. It is possible we'll just happen to optimize some cases here as a result of good type information in SH and a solid optimization pipeline. # Spreading and modifying existing structures An example of some sample code found in input to Hermes to clone a Map and add an element: ``` return new Map([...Array.from(origMap), [id, obj]]); ``` 1. Iterates `origMap` and creates a new array `%tmp1`, element by element. 2. Creates a new array `%tmp2`, iterates `%tmp1`, and copies the elements. 3. Adds the new array `[id, obj]` to `%tmp2`. 4. Iterates `%tmp2` and populates a newly created `Map`. Some potential ways to simplify things: 1. `...Array.from(a)` is the same as `...a` provided that the array iterator has not been modified. 2. `new Map([...oldMap, [x, y]])` is the same as `const %tmp = new Map(oldMap); %tmp.set(x, y)` provided that the `Map` iterator has not been modified. If we can enforce that iterators haven't been modified, then we can do step 1 potentially even in legacy code, and step 2 in typed code. --- ### Doc/IR --- id: ir title: Design of the IR --- ### Introduction This document is a reference manual for the Hermes High-level IR. The IR is a Static Single Assignment (SSA) based representation that captures the JavaScript language semantics. It features optional types (values may be annotated with types). The IR representation is designed to be used as an in-memory form. The IR can be dumped to human readable assembly-like format. ### Well-Formedness This section describes the rules that define a valid IR. - Instructions must be dominated by their operands. - Basic block must end with a terminator, which is a branch instruction or a return instruction. - There has to be exactly one terminator for each basic block. - AllocStack instructions must appear at the 'entry' basic block (the first basic block in the function). - PHI Nodes must appear at the beginning of the basic block and must contain an entry for each predecessor. ### Frames: Every JavaScript function is a closure that can capture variables from its declaration scope. The declaration scope may be the global scope or another function. A closure is a pair of function code, which contains the code of the function, and a context which saves the environment that the closure may access. Function variables that are captured by a closure are allocated in a scope on the heap and the scope is passed as part of the context to the closure. Closures may access variables at all nest-levels, which means that they can access multiple scopes. We implement this feature by nesting scopes and linking them together. Each scope (the set of captured variables) also has a reference to the scope of the caller function. Closures can access variables at different nesting levels by loading the parent scope for each scope. At the IR Level we define a few instructions that can load and store frame variables. Functions own variables, that are storage units that represent variables at the source level. These variables can be optimized away or promoted to the stack, etc. We define the AllocStack instruction for allocating variable storage. The only instructions that can access the storage values (Variable and AllocStack) are the Load and Store instructions. It is not possible to save the address of the allocation itself. Depending on the implementation of the virtual machine, the heap allocations may be packed into a single frame. ### Types: The Hermes high-level IR is optionally typed. Values may be annotated with the expected type of the value. The types are optional and untyped programs are correct. The types represent primitive JavaScript types, or refinement of these types. All values can be annotated with types: Functions, Instructions and Parameters. Annotations of functions represent the type of the returned value. The type annotations are not a suggestion or a hint. They must be correct and consistent or else the program may fail at run time. Programs are expected to run and have the same semantics when the type annotations are stripped. Some instructions in the IR expect operands of specific types, or produce specific types. For example, the CondBranch instruction expects the condition operand to be annotated as a boolean type. The ToBool instruction produces values that are annotated as boolean type. The optimizer may optimize the IR based on type annotations. For example, if the operand of the instruction ToBool is annotated with the boolean type then the optimizer is free to remove the instruction and replace all uses with the operand of the conversion instruction. ### Example: This is a short example of a valid program in textual IR. The function contains four basic blocks with a few instructions. The code below follow the requirements of a well-formed function defined in the previous section. function forEach(cond : boolean, value : number) %BB0: %0 = BranchInst %BB1 %BB1: %2 = CondBranchInst %cond, %BB2, %BB3 %BB2: %3 = ReturnInst %cond %BB3: %4 = ReturnInst %value ### Side Effects: The instructions in the IR are annotated with side effect labels. The labels describe the kind of effect the instruction has on memory, IO state (for example, hardware IO such as drawing to a screen or sending a network packet), and whether they can throw. The two kind of memory side effects are 'read' and 'write'. ('write' actually indicates "read and/or write".) These side effect specifications indicate that the instruction does not have IO effects or throw. The 'unknown' side effect is maximally conservative: it indicates that the instruction may read, write, have IO effects, and/or throw. These side effect annotations allow the optimizer to decide which optimizations are legal. For example, it is not legal to sink instructions that can write to memory past each other. It is not legal to hoist instructions that read to memory outside of a loop if there is another instruction that writes to memory in that loop, because the writer instruction may clobber memory that the reader may read. Some instructions that allocate memory are marked as not having any side effects. This is because the instructions only touch the newly allocated memory and do not influence the rest of the heap. Notice that we don't model the effect of instructions on the garbage collector or anything like that, just the content of the allocated memory. ## Register allocation In Hermes, register allocation is performed on the IR. An infinite number of virtual registers are allocated while preserving the constraints of the IR and of the low-level target. Registers are allocated in an attempt to reduce the number of registers, values across PhiNodes are coalesced, AllocStack instructions are assigned with a dedicated register and arguments to call instructions are placed in consecutive registers. While in SSA form, the IR does not support all of the things that can be done with registers. This is why the Register Allocator introduces MOV instructions that represent a copy of one register to another. We lower some of the load/store instructions into MOVs, and spill registers with MOV instructions. ## Generator Overview When generating the IR for a generator function, we make two functions: an outer GeneratorFunction and an inner function. The outer function calls CreateGenerator on the inner function, and returns the resultant generator. The inner function assumes that it can store and retrieve state from its own closure. As such, it contains instructions to start, save/yield, and resume generators. CreateGenerator: An instruction to create a generator given a `Function`. First, it creates an inner GeneratorInnerFunction, then it wraps it in a Generator object. Used by the GeneratorFunction to create the generator which is returned upon calling it. StartGenerator: Always the first instruction executed when an inner function is called. Restores values for all local variables in the generator, and jumps to the resume point of the generator if it's suspended. If the generator hasn't been started yet, simply continues execution. SaveAndYield: Saves necessary state to the closure and yields execution. In practice, this will save state and use the return opcode to allow the caller to get the yield result. Emitting a SaveAndYield also emits its corresponding ResumeGenerator. ResumeGenerator: Placed at the start of the block following the SaveAndYield to which it corresponds. Resumes execution by loading context from the closure, and then using state stored in the closure, does one of 3 things: - Continues execution with the result of the instruction being the argument to `.next()`. - Throws a value immediately - Sets an `%isReturn` flag to true, which later instructions may branch on to execute the `finally` if necessary, and then return. ## Instruction semantics This section describes the semantic of the instruction that are defined in the IR. Please make sure to update this section as new instructions are added to the compiler. ### BranchInst BranchInst | _ --- | --- | Description | Jumps to a different basic block. Example | %0 = BranchInst %BB1 Arguments | A single operand which is the target basic block. Semantics | Terminates a basic block and 'jumps' to a different basic block. Effects | Does not read or write from memory. ### ReturnInst ReturnInst | _ --- | --- | Description | Leaves the function and returns a value. Example | %0 = ReturnInst %17 Arguments | A single operand which is the returned value. Notice the functions that return without an explicit value return the 'undefined' value. Semantics | Terminates a basic block and transfer the control to the caller of the current function. Effects | Does not read or write from memory. ### AllocStackInst AllocStackInst | _ --- | --- | Description | Allocates a variable on the stack. Example | %0 = AllocStackInst $name Arguments | $name is the textual representation of the variable at the sourcecode level. Semantics | AllocStack allocates a variable on the stack. Depending on the implementation of the VM, the variables may be packed into a single frame. AllocStack values may be used by instructions in different functions that represent closures created by the current functions. AllocStack values are used to represent local and captured variables. The AllocStack itself needs to be used directly. It is not possible to save a reference to the reference. The lifetime of the AllocStack may not exceed the lifetime of the allocating function. Effects | Does not read or write from memory. ### LoadFrameInst LoadFrameInst | _ --- | --- | Description | Loads a value from a variable. Example | %1 = LoadFrameInst %0 Arguments | The variable from which the instruction loads. Semantics | The the instruction reads from a variable. The address must be a valid variable. Effects | Reads from memory. ### LoadStackInst LoadStackInst | _ --- | --- | Description | Loads a value from a stack allocated memory pointed by a reference. Example | %1 = LoadInst %0 Arguments | The address from which the instruction loads. Semantics | The the instruction reads from memory. The address must be a valid stack address. Effects | Reads from memory. ### StoreFrameInst StoreFrameInst | _ --- | --- | Description | Stores a value to a frame variable. Example | %1 = StoreFrameInst %value, %variable Arguments | %value is the value to be stored. %address is the reference to the variable where the value will be stored. Semantics | The the instruction saves a value to memory. The address must be a valid variable. Effects | Writes to memory. ### StoreStackInst StoreStackInst | _ --- | --- | Description | Stores a value to a stack allocated memory. Example | %1 = StoreStackInst %value, %stack_allocated Arguments | %value is the value to be stored. %address is the reference to stack allocation. Semantics | The the instruction saves a value to memory. The address must be a valid stack allocation. Effects | Writes to memory. ### AsNumberInst AsNumberInst | _ --- | --- | Description | Casts a JavaScript value into a number value. Example | %1 = AsNumberInst %input Arguments | The value to cast. Semantics | The instruction follows the JavaScript rules for converting types into numbers. Effects | May read or write to memory. ### AsInt32Inst AsInt32Inst | _ --- | --- | Description | Casts a JavaScript value into a signed 32-bit integer value. Example | %1 = AsInt32Inst %input Arguments | The value to cast. Semantics | The instruction follows the JavaScript rules for converting types into 32-bit signed integers. Effects | May read or write to memory. ### AddEmptyStringInst AddEmptyStringInst | _ --- | --- | Description | Convert a value to string as if evaluating `value + ''` Example | %1 = AddEmptyStringInst %input Arguments | The value to cast. Semantics | The instruction follows the JavaScript rules for adding an empty string to a value (ES5.1 11.6.1). Effects | May read or write to memory or throw. ### CondBranchInst CondBranchInst | _ --- | --- | Description | Jumps to one of two blocks depending on a condition value. Example | %1 = CondBranchInst %cond, %BB1, %BB2 Arguments | %cond is the condition variable, %BB1 is the 'True' block, %BB2 is the 'False' block. Semantics | The instruction observes the value of a typed value and jumps to one of two basic blocks. If the condition is evaluated as 'True' the program jumps to the 'True' block. Otherwise the program jumps to the 'False' block. Effects | Does not read or write from memory. ### CompareBranchInst CompareBranchInst | _ --- | --- | Description | Performs a binary comparison of the two operands and a conditional branch depending on the result. Example | %0 = CompareBranch %x, %y, %BB1, %BB2 Arguments | %x and %y are the operands of the binary operation, %BB1 is the 'True' block, %BB2 is the 'False' block. Semantics | The instruction follows the rules of JavaScript for each one of the binary operators defined in the instruction. If the condition is evaluated as 'True' the program jumps to the 'True' block. Otherwise the program jumps to the 'False' block. Effects | May read and write memory. ### CreateScopeInst CreateScopeInst | _ --- | --- | Description | Create a new function top-level scope. Example | %0 = CreateScopeInst %desc Arguments | %desc describes the function's top-level scope. Semantics | Creates the top-level scope for its function. Effects | Does not read or write to memory. ### CreateInnerScopeInst CreateInnerScopeInst | _ --- | --- | Description | Creates a new scope with the given parent Example | %0 = CreateInnerScopeInst %parent, %desc Arguments | %parent is the inner scope's parent scope, and %desc describes the scope that is being created. Semantics | Creates a new inner scope within the given parent. Effects | Does not read or write to memory. ### CreateFunction CreateFunction | _ --- | --- | Description | Constructs a new function into the current scope from its code representation. Example | %0 = CreateFunction %function, Arguments | %function is the function that represents the code of the generated closure. Semantics | The instruction creates a new closure that may access the lexical scope of the calling function Effects | Does not read or write to memory. ### BinaryOperatorInst BinaryOperatorInst | _ --- | --- | Description | Performs the binary operation on the two operands. Example | %0 = BinaryOperatorInst %x, %y Arguments | %x and %y are the operands of the binary operation. Semantics | The instruction follows the rules of JavaScript for each one of the binary operators defined in the instruction. Effects | May read and write memory. ### DirectEvalInst DirectEvalInst | _ --- | --- | Description | Implement a syntactical call to `eval(arg)` where `eval` is global property. Example | `%0 = DirectEvalInst %value1` Arguments | %value1 is the value which will be evaluated. Semantics | Implement the semantics of ES6 `PerformEval(%value1, evalRealm, strictCaller=true, direct=true)` (ES6 18.2.1.1). Note that we only support "strictCaller=true". Effects | Unknown ### CallInst CallInst | _ --- | --- | Description | Calls another function with some arguments. Example | %0 = CallInst %callee, %this, %arg0, %arg1, %arg2, ... Arguments | %callee is the function to execute. %this is a reference to the 'this' value. Arguments %arg0 ... %argN are the arguments passed to the function. Semantics | The instruction passes the control to the callee, that must be of closure type. The arguments are mapped to the parameters. Unmapped parameters are initialized to 'undefined'. Effects | May read and write memory. ### ConstructInst ConstructInst | _ --- | --- | Description | Construct a new object with a constructor Example | %0 = ConstructInst %constructor, #undefined, %arg0, %arg1, %arg2, ... Arguments | %constructor is the constructor function to execute. #undefined is not used. %arg0 ... %argN are the arguments passed to the constructor function. Semantics | The instruction performs the steps defined in ES5.1 sec-11.2.2 and sec-13.2.2. It allocates the object and calls the constructor function with the new object and the supplied arguments. Effects | May read and write memory. ### CallBuiltinInst CallBuiltinInst | _ --- | --- | Description | Calls a builtin function passing "undefined" for this Example | %0 = CallBuiltinInst %builtinNumber, %undefined, %arg0, %arg1, %arg2, ... Arguments | %builtinNumber is the builtin to execute. Arguments %arg0 ... %argN are the arguments passed to the function. Semantics | The instruction passes the control to the builtin in a VM-specific way. The arguments are mapped to the parameters. Unmapped parameters are initialized to 'undefined'. Effects | May read and write memory. ### CallIntrinsicInst CallIntrinsicInst | _ --- | --- | Description | Calls an unsafe compiler intrinsic, passing "undefined" for this Example | %0 = CallIntrinsicInst %intrinsicsIndex, %undefined, %arg0, %arg1, %arg2, ... Arguments | %intrinsicsIndex is the intrinsic to execute. Arguments %arg0 ... %argN are the arguments passed to the function. Semantics | The instruction passes the control to the intrinsics in a VM-specific way. The arguments are mapped to the parameters. Effects | May read and write memory. ### GetBuiltinClosureInst GetBuiltinClosureInst | _ --- | --- | Description | Get a closure of a builtin function Example | %0 = GetBuiltinClosureInst %builtinNumber Arguments | %builtinNumber is the builtin to return the closure of. Semantics | Effects | Reads from memory. ### LoadPropertyInst LoadPropertyInst | _ --- | --- | Description | Loads the value of a field from a JavaScript object. Example | %0 = LoadPropertyInst %object, %property Arguments | %object is the object to load from. %property is the name of the field. Semantics | The instruction follows the rules of JavaScript property access in ES5.1 sec 11.2.1. The operation GetValue (ES5.1. sec 8.7.1) is then applied to the returned Reference. Effects | May read and write memory or throw. TryLoadGlobalPropertyInst | _ --- | --- | Description | Loads the value of an existing field from the global object or throw if it doesn't exist. Example | %0 = TryLoadGlobalPropertyInst %object, %property Arguments | %object is the global object. %property is the name of the field, which must be a string literal. Semantics | Similar to LoadPropertyInst, but throw if the field doesn't exist. Effects | May read and write memory or throw. ### DeletePropertyInst DeletePropertyInst | _ --- | --- | Description | Deletes the value of a field from a JavaScript object. Example | %0 = DeletePropertyInst %object, %property Arguments | %object is the object to modify. %property is the name of the field. Semantics | The instruction follows the rules of JavaScript property access. Effects | May read and write memory. ### StorePropertyInst StorePropertyInst | _ --- | --- | Description | Stores a value to field in a JavaScript object. Example | %4 = StorePropertyInst %value, %object, %property Arguments | %value is the value to be stored. %object is the object where the field %property will be created or modified. Semantics | The instruction follows the rules of JavaScript property access in ES5.1 sec 11.2.1. The operation PutValue (ES5.1. sec 8.7.2) is then applied to the returned Reference. Effects | May read and write memory or throw. ### TryStoreGlobalPropertyInst TryStoreGlobalPropertyInst | _ --- | --- | Description | Attempt to store a value into an existing field of the global object and throw if it doesn't exist. Example | %4 = TryStoreGlobalPropertyInst %value, %object, %property Arguments | %value is the value to be stored. %object is the global object, where the field %property will be stored. %property must be a string literal. Semantics | Similar to StorePropertyInst, but throw if the field doesn't exist. Effects | May read and write memory or throw. ### StoreOwnPropertyInst StoreOwnPropertyInst | _ --- | --- | Description | Stores a value to an *own property* of JavaScript object. Example | %4 = StoreOwnPropertyInst %value, %object, %property, %enumerable : boolean Arguments | %value is the value to be stored. %object is the object where the field with name %property will be created or modified. %enumerable determines whether a new property will be created as enumerable or not. Semantics | The instruction follows the rules of JavaScript *own* property access. The property is created or updated in the instance of the object, regardless of whether the same property already exists earlier in the prototype chain. Effects | May read and write memory. ### StoreNewOwnPropertyInst StoreNewOwnPropertyInst | _ --- | --- | Description | Create a new *own property* in what is known to be a JavaScript object. Example | `%4 = StoreNewOwnPropertyInst %value, %object, %property, %enumerable : boolean` Arguments | *%value* is the value to be stored. *%object*, which must be an object, is where the field with name *%property* will be created. *%property* must be a string literal, otherwise it is impossible to guarantee that it is new. *%enumerable* determines whether the new property will be created as enumerable or not. Semantics | The instruction follows the rules of JavaScript *own* property access. The property is created in the instance of the object, regardless of whether the same property already exists earlier in the prototype chain. Effects | May read and write memory. ### StoreGetterSetterInst StoreGetterSetterInst | _ --- | --- | Description | Associates a pair of getter and setter with an *own* field in a JavaScript object, replacing the previous value. Example | %4 = StoreGetterSetterInst %getter, %setter, %object, %property, %enumerable Arguments | %getter is a getter accessor, or undefined. %setter is a setter accessor, or undefined. %object is the object where the field %property will be created or modified. %enumerable determines whether a new property will be created as enumerable or not. Semantics | The instruction follows the rules of JavaScript property access. The property is created or updated in the instance of the object, regardless of whether the same property already exists earlier in the prototype chain. It replaces both accessors even if one or both of the parameters are undefined. Effects | May read and write memory. ### ThrowIfHasRestrictedGlobalPropertyInst ThrowIfHasRestrictedGlobalPropertyInst | _ --- | --- | Description | Raises an exception if the given name is a restricted global property. Example | ThrowIfHasRestrictedGlobalPropertyInst %name : string Arguments | %name is the name to be checked agains global restricted properties. Semantics | Implements the semantics of ES2023 9.1.1.4.14 followed by a throw if %name is a restricted global property. Effects | Unknown. ### AllocObjectInst AllocObjectInst | _ --- | --- | Description | Allocates a new JavaScript object on the heap. Example | `%0 = AllocObjectInst %sizeHint : LiteralNumber, %parent : EmptySentinel or null or Value` Arguments | *%sizeHint% indicates that the object will need at least that many property slots. *%parent* is the optional parent to create the object with: *EmptySentinel* means use *Object.prototype*, *null* means no parent, or otherwise use the specified value. Semantics | The instruction creates a new JavaScript object on the heap. If the parent is invalid (not EmptySenyinel, null or object), it is silently ignored. Effects | Does not read or write to memory. ### AllocArrayInst AllocArrayInst | _ --- | --- | Description | Allocates a new JavaScript array on the heap. Example | %0 = AllocArrayInst %sizeHint, %value0, %value1, ... Arguments | sizeHint tells the size of the array that the VM should allocate. It must be equal or larger than the initial list of elements in this instruction. The rest of the values are all literal values as the initial elements of the array. Non-literal values or values after elision will be inserted into the array separately. Semantics | The instruction creates a new JavaScript array on the heap with a hinted size and initial list of elements. Effects | Does not read or write to memory. ### CreateArgumentsInst CreateArgumentsInst | _ --- | --- | Description | Allocates the JavaScript `arguments` array-like object on the heap. Example | %0 = CreateArgumentsInst Arguments | None. Semantics | The instruction creates the `arguments` object, populates it with copies of the values of the arguments (according to "strict mode" semantics) and sets `arguments.length` to the number of arguments (`this` isn't copied or counted). There should be only one CreateArgumentsInst in a function. Effects | Does not read or write to memory. ### CreateRegExpInst CreateRegExpInst | _ --- | --- | Description | Construct a RegExp object from a regexp literal. Example | %0 = CreateRegExpInst "pattern", "flags" Arguments | `pattern: LiteralString` and `flags: LiteralString` Semantics | It is equivalent to calling `RegExp(pattern, flags)`, except that it calls the built-in constructor, even if `RegExp` has been overridden. Effects | Does not read or write to memory. ### SwitchInst SwitchInst | _ --- | --- | Description | The ‘switch‘ instruction is used to transfer control to one of different places. Example | %0 = SwitchInst %input, %default, [%val0, %block0], [%val1, %block1] .. Arguments | The instruction accepts an input, a default block, and one or more pairs of value-destination values. The value must be a primitive JS type, and the destination must be a basic block within the current function. Semantics | The semantic of the instruction is identical to a sequence of 'if' statements that compare the value of the input to each of the case statements. Repeating the same value is not allowed. Effects | May read and write memory. ### GetPNamesInst GetPNamesInt | _ --- | --- | Description | Generates the property enumerator, which is a collection of registers that hold the state of the enumerator (iterator, object base, index, size, etc). Example | %0 = GetPNamesInt %propertyAddr, %baseAddr, %indexAddr, %sizeAddr, %iteratorAddr, %onEmpty, %onLast Arguments | The first 5 parameters are addresses (stack allocated addresses) that represent the state of the property enumerator. The last two argument are jump destination for the two cases: empty object and object with some properties. Semantics | This instruction is a terminator instruction and prepares the enumerator for the GetNextPNameInst instruction to consume. Effects | May read and write memory. ### GetNextPNameInst GetNextPNameInst | _ --- | --- | Description | Loads the next property from the object property enumerator. Example | %0 = GetNextPNameInst %propertyAddr, %baseAddr, %indexAddr, %sizeAddr, %iteratorAddr, %onLast, %onSome Arguments | The first argument is the destination where the name of the property is written into. The next 4 arguments are the state of the property enumerator. The last two arguments are the destination blocks for: no next property, or some property available. Semantics | This instruction is a terminator instruction that uses the state that was prepared by the GetPNamesInst instruction. Effects | May read and write memory. ### CatchInst CatchInst | _ --- | --- | Description | This instruction catches an exception, and returns that exception. Example | %0 = CatchInst Arguments | This instruction does not have arguments. Semantics | This instruction will be generated for each catch block and for each finally block. The current exception will be returned. CatchInst can only show up at the beginning of a basic block. The coverage and depth information for the CatchInst will be constructed dynamically later during bytecode generation. Effects | May read and write memory. ### ThrowInst ThrowInst | _ --- | --- | Description | This instruction will throw an exception. Example | %0 = ThrowInst %e Arguments | This instruction takes one parameter, which is the register that contains the exception value Semantics | This instruction is a terminator instruction that will transition the control to the CatchInst that covers this instruction with closest scope. Effects | May read and write memory. ### CheckHasInstanceInst CheckHasInstanceInst | _ --- | --- | Description | Check whether an object has a particular instance. Example | %0 = CheckHasInstanceInst %check_result, %left, %right, %onTrue, %onFalse Arguments | This instruction takes 5 parameters: %check_result will be a write-only stack register and holds the check result, %left and %right are the operands of instanceof, and %onTrue and %onFalse are the jump targets in case of check returns true/false. Semantics | This instruction is generated as part of instanceof operator. It checks whether %right could possibly have %left as an instance, and returns the check result. If the checked object is invalid to have the target instance, it will throw an exception. It the check returns false, it jumps to the %jump_label. Effects | May read or write memory. ### TryStartInst TryStartInst | _ --- | --- | Description | Mark the beginning of the try blocks. Example | %0 = TryStartInst %catchTargetBlock, %tryBodyBlock Arguments | This instruction takes 2 arguments: %tryBodyBlock is the block where the body of Try starts, %catchTargetBlock is the basic block that contains the CatchInst which covers this try. Both %tryBodyBlock and %catchTargetBlock are successors of this instruction. Semantics | This is a nop, used only for tracking the beginning of try blocks. Effects | Does not read or write memory. ### TryEndInst TryEndInst | _ --- | --- | Description | Mark the end of the try blocks. Example | %0 = TryEndInst Arguments | This instruction does not have arguments. Semantics | This is a nop, used only for tracking the end of try blocks. Effects | Technically this instruction itself does not touch memory, however we mark it as may write to prevent optimizations going pass this instruction. ### PhiInst PhiInst | _ --- | --- | Description | This is a Phi node instruction. Example | %0 = PhiInst %value0, %block0, [%value1, %block1] Arguments | A list of pairs of value and incoming basic block. Semantics | The PhiNode needs to have a single entry for each incoming basic block of the block the PHI is located in. The incoming value must dominate the last instruction in the incoming block. Effects | Does not read or write memory. ### MovInst MovInst | _ --- | --- | Description | The MOV inst represents a low-level operation of moving one register to another. Example | %0 = MovInst %value0 Arguments | Any value. Semantics | The Mov instruction is only valid after Register Allocation in bytecode as we move away from SSA form. Effects | Does not read or write memory. ### ImplicitMovInst ImplicitMovInst | _ --- | --- | Description | The ImplicitMov inst represents moving one register to another, except the mov will be performed implicitly by an immediately-subsequent instruction. This is used to express to the optimizer instructions which modify registers other than their destination. Example | %0 = ImplicitMovInst %value0 Arguments | Any value. Semantics | The ImplicitMov instruction is only valid after Register Allocation in bytecode as we move away from SSA form. Effects | Does not read or write memory. ### DebuggerInst DebuggerInst | _ --- | --- | Description | This instruction corresponds to the JavaScript `debugger` statement. Example | %0 = DebuggerInst Arguments | It takes no arguments and returns no values. Semantics | Its behavior is implementation-dependent. Effects | Does not read or write to memory. ### GetNewTargetInst GetNewTargetInst | _ --- | --- | Description | Obtains the value of `new.target` in the current function or constructor. Example | %0 = GetNewTargetInst Arguments | None Semantics | It must only be called from a ES6 class constructor or ES5 function. If the callee was invoked from `new`, it returns the function object of the direct constructor, otherwise `undefined`. Effects | Does not read or write memory ### ThrowIfEmptyInst ThrowIfEmptyInst | _ --- | --- | Description | Check whether the value is "empty", and if it is, throw ReferenceError, otherwise return it. Example | %_ = ThrowIfEmptyInst %value Arguments | The value to check. Semantics | It is used to implement ES6 TDZ functionality. Variables declared with `let` are *poisoned* with *empty* until they are initialized. Effects | Potentially throws an exception. Has no other side effects. ### CoerceThisNS CoerceThisNS | _ --- | --- | Description | Coerces its argument using the rules of "this" coercion to object in non-strict mode. Example | %0 = CoerceThisNS %value0 Arguments | Any value. Semantics | Effects | Does not read or write memory (it potentially creates a new object) ### CreateGenerator CreateGenerator | _ --- | --- | Description | Constructs a new GeneratorInnerFunction from its code representation, and wraps it in a Generator object. Example | %0 = CreateGenerator %function, Arguments | %function is the function that represents the code of the generator's inner function. Semantics | Creates a new GeneratorInnerFunction closure that may access the environment and wraps it in a generator Effects | Does not read or write to memory (creates a new object). ### StartGenerator StartGenerator | _ --- | --- | Description | Jump to the proper first instruction to execute in a GeneratorInnerFunction Example | %0 = StartGenerator Arguments | None Semantics | Jumps to a BasicBlock which begins with a ResumeGenerator and sets the internal generator state to "executing", but does not handle next(), return(), or throw() as requested by the user. Effects | Reads and writes memory. Restores the stack based on saved state, and jumps to another BasicBlock ### SaveAndYield SaveAndYield | _ --- | --- | Description | Saves information needed to resume generator execution and yield. Example | %0 = SaveAndYield %value, %next Arguments | %value is the value to yield, %next is the next BasicBlock to execute upon resuming, which must begin with a ResumeGeneratorInst (generated alongside SaveAndYield). Semantics | Saves the frame variables and the next IP to the closure, and yield execution. Effects | Reads and writes to memory, may throw or execute. ### ResumeGenerator ResumeGenerator | _ --- | --- | Description | Perform the user-requested action on resuming a generator. Example | %0 = ResumeGenerator %isReturn Arguments | %isReturn is an output argument set to true if the user requested a return, false otherwise. Semantics | If the user requested next(), continue on. If the user requested throw(), throw. If the user requested return(), set %isReturn to true and continue. Subsequent instructions will check %isReturn and execute any `finally` handlers, for example, before returning. Effects | May read and write memory. (may throw) ### IteratorBegin IteratorBegin | _ --- | --- | Description | Begins array destructuring on a given iterable source. Example | %0 = IteratorBegin %sourceOrNext Arguments | %sourceOrNext[in/out] is the stack location for source to destructure from. Is set to source if performing array iteration, else set to the `.next()` method of the iterator. Semantics | If %sourceOrNext is an Array then it remains unmodified and the instruction returns `0`, but if it is not, it is replaced with the 'next' method so that it can be called on each step of the iteration and the instruction returns the iterator object. If the `[Symbol.iterator]` function throws, this instruction will throw. Effects | May read and write memory, may throw or execute. ### IteratorNext IteratorNext | _ --- | --- | Description | Destructures the next value from a given iterator. Example | %0 = IteratorNext %iterator %sourceOrNext Arguments | %iterator is the index or the iterator. %sourceOrNext is the input stack location (source to destructure from) or the next method. Semantics | If %iterator is an index: if %iterator is less than `%sourceOrNext.length`, reads the value from %sourceOrNext and increments the index, else sets %iterator to undefined and returns undefined. If %iterator is an actual iterator, calls %sourceOrNext as a next method and evaluates to the result value. When iteration is complete, sets %iterator to undefined as a signal that we're done. ``` if (typeof %iterator === 'undefined') { return undefined; } if (typeof %iterator === 'number') { if (%iterator >= %sourceOrNext.length) { %iterator = undefined; return undefined; } return %sourceOrNext[%iterator]; } var iterResult = %sourceOrNext(); if (iterResult.done) { %iterator = undefined; return undefined; } return iterResult.value; ``` Effects | May read and write memory, may throw or execute. ### IteratorClose IteratorClose | _ --- | --- | Description | Closes an iterator if it exists. Example | %0 = IteratorClose %iterator %ignoreInnerException Arguments | %iterator is the index or the iterator. %ignoreInnerException is a boolean literal. Semantics | If %iterator is an iterator, calls `.return()` on it to close it. Otherwise, this is a no-op. If `.return()` throws, the exception is ignored when %ignoreInnerException is true. Effects | May read and write memory, may throw or execute. ### UnreachableInst UnreachableInst | _ --- | --- | Description | Crashes the VM (ifndef NDEBUG). Example | %0 = UnreachableInst Arguments | None. Semantics | Can be added to stubs and similar to verify that they are never executed. Effects | Marked as reading/writing memory to avoid reordering. ## Target Instructions Some high-level IR instructions are lowered into a sequence of low-level machine instructions. In order to perform register allocation on these instructions we need to perform lowering, which is a form of instruction selection. The semantic of these instructions are identical to the semantic of the relevant target instructions. ### HBCGetGlobalObjectInst HBCGetGlobalObjectInst | _ --- | --- | Description | Obtain the "global" object Example | %0 = HBCGetGlobalObjectInst Arguments | None. Semantics | The instruction returns a reference to the "global" object. Effects | Does not read or write to memory. ### HBCCreateEnvironment HBCCreateEnvironment | _ --- | --- | Description | Create a new function top-level environment. Example | %0 = HBCCreateEnvironment %desc Arguments | %desc describes the function's top-level environment. Semantics | Creates the top-level environment for its function. Effects | Does not read or write to memory. ### HBCCreateInnerEnvironment HBCCreateInnerEnvironment | _ --- | --- | Description | Creates a new environment with the given parent Example | %0 = HBCCreateInnerEnvironment %parent, %desc Arguments | %parent is the inner environment's parent environment, and %desc describes the environment that is being created. Semantics | Creates a new inner environment within the given parent. Effects | Does not read or write to memory. ### HBCCreateFunction HBCCreateFunction | _ --- | --- | Description | Create a new closure capturing the specified environment and using the specified body Example | %0 = HBCCreateFunction %environment, %body, Arguments | %environment is the closure's environment. %body is the closure's body. Semantics | The instruction creates a new closure that may access the specified environment. Effects | Does not read or write to memory. ### HBCCreateGenerator CreateGenerator | _ --- | --- | Description | Constructs a new Generator into the current scope from its code representation. Example | %0 = CreateGenerator %environment, %body, Arguments | %environment is the closure's environment, %body is the closure's body. Semantics | The instruction creates a new GeneratorInnerFunction access the environment and wraps it in a Generator. Effects | Does not read or write to memory. ### HBCAllocObjectFromBufferInst HBCAllocObjectFromBufferInst | _ --- | --- | Description | Allocates a new JavaScript object on the heap, and initializes it with values from the object buffer. Example | %0 = HBCAllocObjectFromBufferInst %value0, %value1, ... Arguments | The values are all literal values, with alternating keys and values. Non-literal values will be inserted into the array separately. Semantics | The instruction creates a new JavaScript object on the heap with an initial list of properties. Effects | Does not read or write to memory. ### HBCCallNInst HBCCallNInst | _ --- | --- | Description | Calls a function with a fixed number of arguments (from 1 to 4, inclusive). Example | %0 = HBCCallNInst %callee, %this, %arg0, %arg1, %arg2 Arguments | %callee is the function to execute. %this is a reference to the 'this' value. Arguments %arg0 ... %argN are the arguments passed to the function. Semantics | The instruction copies its arguments (starting from this) into the parameter-passing registers at the end of the frame, and passes the control to the callee, which must be of closure type. The arguments are mapped to the parameters. Unmapped parameters are initialized to 'undefined'. Effects | May read and write memory. --- ### Doc/IntlAPIs --- id: intl title: Internationalization APIs --- This document describes the current state of the Android and iOS implementation of the [ECMAScript Internationalization API Specification](https://tc39.es/ecma402/) (ECMA-402, or `Intl`). ECMA-402 is still evolving and the latest iteration that was taken into account is [7th edition](https://402.ecma-international.org/7.0/) which was published in June 2020. Each new edition is built on top of the last one and adds new capabilities typically as, - New `Intl` service constructors (e.g. `Intl.Collator`, `Intl.NumberFormat` etc.) or extending existing ones by accepting more parameters - New functions or properties in `Intl` objects (e.g. `Intl.Collator.prototype.compare`) - New locale aware functions in standard Javascript object prototypes (e.g. `String.prototype.localeCompare`) One popular implementation strategy followed by other engines, is to bundle an internationalization framework (typically [ICU](http://site.icu-project.org/)) along with the application package. This guarantees deterministic behaviours at the cost of applications package bloat. We decided to consume the Android and iOS platform provided facilities for space efficiency, but at the cost of some variance in behaviours across Android and iOS platforms. This also includes behavioural variations between different versions of Android. # ECMA-402 Compliance ## Supported on both platforms - `Intl.Collator` - `Intl.Collator.supportedLocalesOf` - `Intl.Collator.prototype.compare` - `Intl.Collator.prototype.resolvedOptions` - `Intl.NumberFormat`* - `Intl.NumberFormat.supportedLocalesOf` - `Intl.NumberFormat.prototype.format` - `Intl.NumberFormat.prototype.resolvedOptions` - `Intl.DateTimeFormat`* - `Intl.DateTimeFormat.supportedLocalesOf` - `Intl.DateTimeFormat.prototype.format` - `Intl.DateTimeFormat.prototype.resolvedOptions` - `Intl.getCanonicalLocales` - `String.prototype` - `localeCompare` - `toLocaleLowerCase` - `toLocaleUpperCase` - `Array.prototype` - `toLocaleString` - `Number.prototype` - `toLocaleString` - `Date.prototype` - `toLocaleString` - `toLocaleDateString` - `toLocaleTimeString` ## Supported on Android only - `Intl.NumberFormat` - `Intl.NumberFormat.prototype.formatToParts` ## * Limitations on property support ### Limited iOS property support - `Intl.NumberFormat` implementation does not support the following properties, - `notation`: 'compact' - `notation`: 'engineering' - `compactDisplay` - `signDisplay` - `Intl.DateTimeFormat` implementation does not support the following properties, - `numberingSystem` - [`formatMatcher`](https://tc39.es/ecma402/#sec-basicformatmatcher) ### Limited Android property support - `Intl.DateTimeFormat` implementation does not support the following properties, - [`dayPeriod`](https://github.com/tc39/ecma402/issues/29) - [`fractionalSecondDigits`](https://github.com/tc39/ecma402/pull/347) - [`formatMatcher`](https://tc39.es/ecma402/#sec-basicformatmatcher) The property enables the implementation to pick the best display format when it supports only a subset of all possible formats. ICU library in Android platform and hence our implementation allows all subsets and formats which makes this `formatMatcher` property unnecessary. ## Limitations across Android SDKs ### Android 11 - The keys of the object returned by `resolvedOptions` function in all `Intl` services are not deterministically ordered as prescribed by spec. - DateFormat: ECMAScript [beginning of time](https://www.ecma-international.org/ecma-262/11.0/index.html#sec-time-values-and-time-range) (-8,640,000,000,000,000), is formatted as `November 271817`, instead of expected `April 271822`. - `Intl.NumberFormat` implementation has some rough edges in supporting the following properties, - `style`: 'unit' - `notation`: 'compact' - `signDisplay` - `currencyFormat` ### Android 10 and older (SDK < 30) - `Intl.NumberFormat`: Scientific notation formatting has issues on some cases. e.g. `-Infinity` may get formatted as '-∞E0' instead of expected '-∞'. Another manifestation of the issues is that the formatToParts may return 4 parts instead of 2. - `Intl.NumberFormat`: Compact notation `formatToParts` doesn't identify unit, hence we report unit as 'literal'. For e.g. the second part of "100ac" gets reported as "literal" instead of "compact" ### Android 9 and older (SDK < 29) - There are some failures likely due to older Unicode and CLDR version, which are hard to generalize. Some examples are, - `Intl.NumberFormat`: 'Percent' is not accepted as a unit. - `Intl.NumberFormat`: unit symbols difference, kph vs km/h - Some issue in significant digit precision, which is not yet looked into the details. ### Android 8.0 – 8.1 and older (SDK < 28) - `Intl.getCanonicalLocales`: Unicode/CLDR version differences results in some variances. e.g. und-u-tz-utc vs. und-u-tz-gmt. - `Intl.NumberFormat`: CompactFormatter doesn't respect the precision inputs. ### Android 7.0 - 7.1 and older (SDK < 26) - `Intl.getCanonicalLocales`: Unicode/CLDR version differences results in some variances. e.g. und-u-ms-imperial vs. und-u-ms-uksystem. ### Android 7.0 - 7.1 and older (SDK < 24) - `Intl.Collator`: Doesn't canonically decompose the input strings. Canonically equivalent string with non-identical code points may not match. - `Intl.getCanonicalLocales`: Unicode/CLDR version differences results in some variances. e.g. und-u-ca-ethiopic-amete-alem vs. und-u-ca-ethioaa, und-u-ks-primary vs. und-u-ks-level1. - `Intl.NumberFormat`: Unit style does not work. - `Intl.NumberFormat`: There are issues in the precision configuration due to lack of APIs. - `Intl.DateFormat`: There are issues with the calendar configuration which needs to be dug into. - [`dateStyle/timeStyle`](https://tc39.es/proposal-intl-datetime-style/) is not implemented. ### SDK < 21 and older On platforms before 21, `Locale.forLanguageTag()` is not available, hence we can't construct `java.util.Locale` object from locale tag. Hence, we fallback to English for any locale input. # Internationalization framework in Android Platform Our implementation is essentially projecting the Android platform provided internationalization facilities through the ECMA-402 specified services. It implies that the results of running the same code may vary between devices running different versions of Android. Android platform internationalization libraries have been based on [ICU4j project](https://unicode-org.github.io/icu-docs/#/icu4j). Version of ICU4j and the backing [CLDR data](http://cldr.unicode.org/) varies across Android platform versions. Also, the ICU APIs were never exposed directly, but only through wrappers and aliases. This results in significant variance in internationalization API surface and data across platform versions. The following table summarizes ICU, CLDR and Unicode versions available on the Android platforms. ### Platform 24+ where ICU4j APIs are available. | Android Platform Version | ICU | Unicode | CLDR | --- | --- | --- | --- | | Android 11 (API level 30) | ICU4J 66.1 ([ref](https://android.googlesource.com/platform/external/icu/+/refs/heads/android11-mainline-release/icu4j/readme.html)) | Unicode 13 beta | CLDR 36.1 | | Android 10 (API level 29) | ICU4j 63.2 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 34 | Unicode 11.0 | | Android 9 (API level 28) | ICU4j 60.2 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 32.0.1 | Unicode 10.0 | | Android 8.0 - 8.1 (API levels 26 - 27) | ICU4j 58.2( [ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 30.0.3 | Unicode 9.0 | | Android 7.0 - 7.1 (API levels 24 - 25) | ICU4j 56 ([ref](https://developer.android.com/guide/topics/resources/internationalization))| CLDR 28 | Unicode 8.0 | ### Pre-24 platforms | Android Platform Version | ICU | Unicode | CLDR | --- | --- | --- | --- | | Android 6.0 (API level 23) | ICU4j 55.1 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 27.0.1 | Unicode 7.0 | | Android 5.0 (API levels 21–22) | ICU4j 53 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 25 | Unicode 6.3 | | Android 4.4 (API levels 19–20) | ICU4j 51 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 23 | Unicode 6.2 | | Android 4.3 (API level 18) | ICU4j 50 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 22.1 | Unicode 6.2 | | Android 4.1 (API levels 16–17) | ICU4j 4.8 ([ref](https://developer.android.com/guide/topics/resources/internationalization)) | CLDR 2.0 | Unicode 6.0 |
In summary, 1. Platforms >= 24 have much better internationalization support than earlier, as many ICU classes are available as is. 2. Platforms 21-24 still has reasonable internationalization support, by allowing creation of Locale objects and enabling selected ICU services through java.text namespace. 3. Platforms < 21 doesn't allow creation of Locale objects from tags, severely limiting general purpose international code. 4. Platform 30 has introduced classes under [`android.icu.number`](https://developer.android.com/reference/android/icu/util/package-summary) namespace which will majorly improve our `Intl.NumberFormat` implementation # Impact on Android Application Size The following numbers are measured using a test application which takes dependency on the Hermes library to evaluate a JavaScript snippet. Essentially, enabling Intl APIs adds 57-62K per ABI. | **Product APK Size** | **NOINTL** | **INTL** | **DIFF** | **PERC** | | --- | --- | --- | --- | --- | | ARM64 | 1,672,235 | 1,729,579 | 57,344 | 3.43% | | ARM | 1,471,539 | 1,528,883 | 57,344 | 3.90% | | X86\_64 | 1,844,255 | 1,901,599 | 57,344 | 3.11% | | X86 | 1,950,739 | 2,012,179 | 61,440 | 3.15% | The overhead is contributed by both compiled native C++ and Java bits The uncompressed size of the Hermes shared library got bigger as follows, | **libhermes.so Size** | **NOINTL** | **INTL** | **DIFF** | **PERC** | | --- | --- | --- | --- | --- | | ARM64 | 2,473,760 | 2,551,592 | 77,832 | 3.15% | | ARM | 1,696,672 | 1,754,016 | 57,344 | 3.38% | | X86\_64 | 2,633,528 | 2,711,368 | 77,840 | 2.96% | | X86 | 2,859,916 | 2,945,936 | 86,020 | 3.01% | And the Java bits got bigger as well, | **Java Size** | **NOINTL** | **INTL** | **DIFF** | **PERC** | | --- | --- | --- | --- | --- | | classes.jar
(in hermes.aar) | 559 | 120975 | 120,416 | 21541.32% | | classes.dex
(replapp.apk) | 160708 | 234808 | 74,100 | 46.11% | _Please note that the application dex file contains non-hermes class files too._ And finally, this is the increase in the final npm package, | **NPM Package** | **NOINTL** | **INTL** | **DIFF** | **PERC** | | --- | --- | --- | --- | --- | | hermes | 214447973 | 219291220 | 4,843,247 | 2.26% | --- ### Doc/LazyEvalCompilation --- id: lazy-eval-compilation title: Lazy/Eval Compilation --- This is a high level overview of how we handle compiling code while the VM is executing, using existing Environments. Used for lazy compilation (deferring full compilation of functions until they are executed) and debugger local `eval` (used by the debugger REPL). For more detailed explanations about each of the parts, look at comments in the code for each of the compiler pipeline phases. The concepts of lazy and eval compilation have conceptual overlap, but use of one doesn't technically require use of the other. It's possible to run lazy compilation but disallow debugger local `eval` and vice versa. The code supplied to debugger local `eval` may also be lazily compiled, but it doesn't have to be. NOTE: All of the below currently only works when executing from source, as it relies on `BCProviderFromSrc`. Lazy compilation doesn't make sense when running from an HBC file (everything's already compiled) and debugging HBC hasn't been implemented yet. We also rely on optimizations not running, to avoid deleting variables/promoting them to the stack, because we rely on everything being in Environments at runtime. # Parsing The parser has 3 phases when running lazy compilation: * `PreParse`: Run the parser over the whole file, but discard the AST. The only information retained is `PreParsedData`, which has information on function locations and metadata (arrow functions, strict mode, etc.). * `LazyParse`: Run the parser using the `PreParsedData` to skip over sufficiently large function bodies. The function bodies are stubbed out and the `isLazyFunctionBody` flag on their `BlockStatementNode` is set to `true`. * `FullParse`: A regular parse. Produces a full AST for the input JS source. In lazy compilation, the `PreParse` and `LazyParse` passes run before execution begins. Then `FullParse` is run when the program attempts to actually execute a lazy function. # Data Storage The data we need to run both lazy compilation and debugger `eval` is stored in `BCProviderFromSrc`'s `CompilationData`. It points to all the information needed to run semantic resolution, IRGen, and HBC BCGen. `BCProviderFromSrc` uses `shared_ptr` to store the IR `Module` and `SemContext`, because it's possible for us to use the same `Module` and `SemContext` for multiple `BCProviderFromSrc`s. That happens during debugger `eval` when the `SemContext` and IR are reused (to be able to access captured variables) but the source is new so we use a new `BCProvider` (because one `BCProvider` corresponds to one `RuntimeModule`, which corresponds to a single JS source). The fact that we persist `Module` and `SemContext` allows us to run the compiler with new code almost as if it existed the whole time. We introduce two IR instructions: `LazyCompilationDataInst` and `EvalCompilationDataInst`. These store data needed for lazy/eval compilation respectively and ensure that relevant Variables are kept alive by storing every parent `VariableScope` as an operand (the `VariableScope`s have users, so they won't get destroyed). We can optionally have a pointer to an IR `Function` from the `functionIR_` field of `BytecodeFunction`, which allows us to get to the relevant `CompilationDataInst`. The `functionIR_` will be destroyed when the `BytecodeFunction` is itself destroyed along with its `BytecodeModule` when the GC cleans up the corresponding `RuntimeModule`. # Semantic Resolution ## First pass The first time the resolver runs with lazy compilation or in preparation for allowing debugger `eval`, it stores extra data to the `FunctionInfo` by populating the `bindingTableScope` field. In lazy compilation mode, it doesn't have to enter lazy functions because they're empty stub `BlockStatementNode`s. ## Actual Resolution `SemanticResolver::runLazy` is the entrypoint into `SemanticResolver` for lazy compilation. It uses an *existing* `SemContext` and adds new information to it. After resolving a lazy function, it cleans up binding table state unless we still need it for debugger `eval` in the future. `SemanticResolver::runInScope` allows for local `eval`, and operates similarly, though it requires a `ProgramNode` as input. It doesn't free any preexisting `SemContext` data. It is called with a *new* `SemContext`, which is created as a child of the original `SemContext` to share the binding table but to allow it to be freed separately from the root `SemContext`. These paths just run the `SemanticResolver` as usual after some setup, because they can restore the binding table state and internal `SemanticResolver` state based on their input. # IRGen ## First pass When IRGen encounters a lazy function body stub, it calls `setupLazyFunction`, which makes an IR `Function` with a `LazyCompilationDataInst` and an `UnreachableInst` terminator. When IRGen actually compiles a function, if debugger `eval` is to be supported, it replaces the body of the IR `Function` with an `EvalCompilationDataInst`. We also now have two lists of `Function`s in the `Module`: one ordinary list of functions to be compiled, and a `compiledFunctions_` list which only holds functions that have already passed through the whole pipeline once. This is a performance optimization to avoid reiterating through these functions needlessly every single time we rerun IRGen. ## Actual IRGen Running IRGen on a lazy `Function` can produce many new IR `Function`s, because there may be many small functions inside the lazy function. These new functions will be some mix of lazy and eagerly compiled. They are not added to the `compiledFunctions_` list yet. # BCGen This part interacts heavily with the IR data structures. ## First pass On trying to run BCGen for a lazy `Function`, assign it a `bcFunctionID`. This allows it to get a dummy `CodeBlock` created at runtime, and we can use the ID to replace the lazy bytecode with real bytecode. Then, assign it to the `functionIR_` field on the new `BytecodeFunction` so that we can find it later. Move the function to the `compiledFunctions_` list so that we no longer treat it as a member of the regular function list in the IR lowering pipeline. Generate a mostly empty function header and empty bytecode, so we have enough information to run actual compilation later. So an IR `Function` used in lazy compilation can be: not compiled yet (and containing a `LazyCompilationDataInst`), assigned a BC ID but not actually compiled (and in `compiledFunctions_`), or destroyed and replaced with a real `Function` with real instructions. Similarly for functions with `EvalCompilationDataInst`. They're already in the `compiledFunctions_` list, but we store them in `functionIR_`. ## Actual compilation When the function is called during lazy compilation, `generateLazyFunctions` is issued to recompile *every* `Function` in the `Module` that isn't a lazy/eval function. This assigns `bcFunctionID`s to all newly discovered functions. They are then generated as usual, and the `BCProviderFromSrc` is *modified* to point to the updated values for string tables, bytecode function tables, etc. by calling `setBytecodeModuleRefs`. `generateForEval` works similarly but the key distinction is that `eval` creates a new `BCProvider`, so the existing one is not updated, and there's no existing `BytecodeFunction` with an ID that has to be replaced. After either of these functions consumes the newly generated functions in the `Module`, we call `resetForMoreCompilation` which cleans upany `Function`s we don't need any more or replaces their body with just `EvalCompilationDataInst` if they're needed still for `eval`. It also deletes any now-unused `VariableScope`s. # Running the pipeline Lazy compilation is called via `CodeBlock::lazyCompile`, which detects whether there's no bytecode on a `CodeBlock` and calls `hbc::compileLazyFunction`. It modifies the existing `BCProviderFromSrc`, and `CodeBlock` replaces its own internal state with the new information. Debugger `eval` runs through the standard `directEval` pipeline, which uses `evalInEnvironment`. If `evalInEnvironment` is provided a `Handle` then it won't run the pipeline from scratch but rather go through `hbc::compileEvalModule`. --- ### Doc/MemoryProfilers --- id: memory-profilers title: Memory Profilers --- This page describes the various tools you can use to diagnose memory issues in your app using Hermes. The tools can be used in a variety of ways based on your needs. The main goal of these profilers are to help you identify ways your app can reduce its memory footprint. This is important for improving the user experience in many ways: * Your app can run faster and have fewer, less expensive garbage collection cycles * Your app can avoid running out of memory entirely, and crashing with an Out of Memory (OOM) error * Your app can avoid being killed by the operating system for using too much memory # Heap Snapshots A Heap Snapshot is a view of the entire JavaScript heap at a point in time. It represents the data as a graph, where nodes are the values in the heap, and the edges are pointers from one node to another. The snapshot can answer these types of questions: * What types of values is my app using? * How much memory do those values use? * What memory is being retained unnecessarily? The nodes in the snapshot can be any value usable in JS, such as: * Objects: `{a: 1, b: 2}` * Arrays: `[1, 2, 3]` * Functions: `function foo(args) { ... }` * Strings: `"hello world"` * Numbers: `3.14` * Native host memory, injected into the heap via `jsi::HostFunction` and `jsi::HostObject` in the JSI API * Hermes-specific internal memory, such as `Environment`, `ArrayStorage`, and `HiddenClass`, and the backing storage of ArrayBuffers. Each node has a list of edges to other nodes, which can be used to determine what nodes **retain** other nodes. If node A retains node B, that means if A is reachable by your program, B will also remain reachable. Therefore, B cannot be garbage collected until A is garbage collected. Many heap snapshot viewers will define the difference between **shallow size** and **retained size**. **Shallow size** is the size of just that node, whereas **retained size** is the size of all the nodes the current node retains. The snapshot format is a JSON file ending in `.heapsnapshot`, and is the same format used by the Chrome Developer Tools and the V8 JavaScript engine. This means all tools that work with heap snapshots taken from V8, Chrome, or Node.js are also compatible with snapshots taken from Hermes. In particular, you can take memory snapshots from the Chrome Developer Tools connected to Hermes! ## Taking a heap snapshot with the Chrome DevTools Before reading this section, make sure you can [connect the Chrome DevTools to Hermes](https://reactnative.dev/docs/next/hermes#debugging-js-on-hermes-using-google-chromes-devtools) to debug some JavaScript. Once you have that set up you can proceed. 1. Open the "Memory" tab of the DevTools, and make sure the "Heap snapshot" radio button is selected 1. (Optional): Click on the garbage can icon in the top left to collect any unreachable objects. This will prevent them from showing up in the snapshot. 1. Click on "Take snapshot" Chrome will alert Hermes that a snapshot is requested, and Hermes will stream the snapshot JSON file back to Chrome. This may take some time if you have a large heap. Once it's completed, you can go to the [Using the Chrome DevTools Heap Snapshot Explorer](#Using-the-Chrome-Devtools-Heap-Snapshot-Explorer) section to start reading it. You can save the snapshot to disk by pressing the "Save" button on your snapshot in the Chrome menu: ## Taking a heap snapshot from C++ Using the Chrome DevTools only applies when you have attached a debugger. For various reasons, it might be hard to do that for your app. In those cases, you can write some C++ code to ask Hermes for a heap snapshot. Before reading this section, make sure to read the JSI documentation which explains all of the basics of the API. Now, say you have some Native Module in React Native, and you want to create a heap snapshot. Here's what you do: ```cpp void myFunc(jsi::Runtime &rt) { // If you want to write to a file name, use createSnapshotToFile. rt.instrumentation().createSnapshotToFile("/tmp/filename.heapsnapshot"); // If you already have a C++ std::ostream set up, use createSnapshotToStream. rt.instrumentation().createSnapshotToStream(std::cout); } ``` This method gives you a lot of flexibility of when and where you want to set up your heap snapshots. You can also expose the functionality above through a `jsi::HostFunction` and call it from JS. The downside is you'll need to add a new native module and build React Native from source for your app. ## Taking a heap snapshot from JavaScript with the Hermes CLI Currently, it isn't possible to take a heap snapshot from JavaScript unless you are running hermes via the command line interface. If you are running from the command line interface, there's a function defined on the global object called `createHeapSnapshot`, used like so: ```js // Calling with no arguments will print to stdout createHeapSnapshot(); // Calling with a single string argument will write the snapshot to that file // path. If it isn't a valid file, or the permissions won't allow Hermes to // write to it, it'll throw a TypeError createHeapSnapshot("/tmp/filename.heapsnapshot"); ``` Note that `createHeapSnapshot` does not exist if you are running Hermes in React Native, or if Hermes was built without memory instrumentation, and you will get an exception if you try to use it. ## Loading a heap snapshot from disk If after any of the above methods you have a `filename.heapsnapshot` file saved somewhere, you can load that into Chrome without needing to connect to any running app. From the "Memory" tab, next to "Take snapshot" there is a "Load" button which will open a file browser. Navigate to the file you want to load and open it. ## Using the Chrome DevTools Heap Snapshot Explorer Now you have a heap snapshot taken and you want to find a memory problem. Here's an explanation of what you can do in Chrome. ### Sorting You can sort by any of the following categories by clicking on the category name: * Retained Size: size of all nodes pointed to by this node * Shallow Size: size of just the node itself * Constructor: The name of the constructor of the node. Can think of it as a type name * Distance: The number of edges needed to traverse from a root to this node Click a second time to reverse the order of the sort. ### Type names You can search for a type name, which uses the name of the constructor function by default. For example, if you have code like the following: ```js function MyObject() {} var obj = new MyObject(); ``` The node for `obj` in the snapshot will have the constructor name `MyObject`. Expanding the type category will show all objects that are in the heap of that type. Hermes tries to be as specific as it can with type names for objects. For objects created without a constructor, such as object literals (`{a: 1, b: "hello"}`), Hermes will display its type name as `Object(a, b)`. If an object has more than 5 properties, it will be displayed as `Object(a, b, c, d, e, ...)`. If an object has more than `HiddenClass::kDictionaryThreshold` properties (currently 64), it will be displayed as `Object(Dictionary)`. Warning: If you change the name of the constructor function dynamically, or if the `.name` property of a function is an accessor, Hermes may only report the original name of the function as defined in the source file. ### Retainers If you click on a particular object in your snapshot, a drawer will pop up below saying "Retainers". This drawer will show a tree of all nodes that have a reference to this node. If you click on the dropdown arrow for one node, you'll see all of the other nodes which retain that node, and so on until you reach what's called a "root" of the heap. You can also right-click on a node in the retainers drawer and click on "Reveal in Summary view" to jump to that node in the summary box. In this example, you can see that an object (who has an "a" property), is retained by the property "x" in an instance of MyObject. That object is retained by the 1,000th element in an array. That array is retained by `(Registers)`, which is the root category for all local variables on the JS stack. Below you can see some more of the root categories that Hermes uses to describe some things that can retain objects: The most important ones are: * `(Registers)`: all local variables on the JS stack * `(IdentifierTable)`: a table of strings used as object properties and symbol descriptions * `(GCScopes)`: the equivalent of the `(Registers)` group for native code inside the Hermes engine. These hold onto JS values currently in use by native code * `(Prototypes)`: lists of prototypes and constructors of system objects like `Function` and array iterators * `(Custom)`: these are any roots created by native code outside of Hermes. In the case of any embedder using JSI (such as React Native), this corresponds to the `jsi::Value`s being used * `(SymbolRegistry)`: this is a table of all symbols made by `Symbol.for("foo")` Knowing which root anchors your node is an important step to knowing why it is being retained, and if it shouldn't be. If an object doesn't have a retaining path to the root, it means there is nothing keeping it alive, and it will be collected at the next garbage collection cycle. Outside of root categories, there is another frequent retainer of objects: the `Environment` type. An `Environment` in Hermes is a simple array that is used to store captured variables of a closure. In this example you can see that the variable `x` is captured: ```js function makeCallback(x) { return () => x; } ``` The closure returned from `makeCallback` will capture `x`, and Hermes implements this by placing `x` into an `Environment` pointed to by the closure. Environments can be shared if multiple closures capture the same variable: ```js function makeManyCallbacks(x) { return [() => x = {foo: 1}, () => x.foo]; } ``` In this case, both closures will capture the same environment pointing to `x`, so the second closure will see updates made by the first closure. Taking a snapshot of some objects created by calling `makeManyCallbacks` shows the following: The `[1] in Array` shows this was the second closure stored in the array. ### Comparing Snapshots If you have two heap snapshots from the same execution you can compare them to each other and see which objects were allocated or destroyed between those points in time. First, load two snapshots into your Chrome workspace. Make sure they are from the same process. Two snapshots from two separate runs of your app will not be comparable, and the output might not make sense. Then, click on the "Summary" dropdown box at the top and change it to "Comparison". If you don't see the "Comparison" option that means you don't have two snapshots loaded into Chrome yet. The following video shows how to do this: Once you're in a comparison view, you can see what objects were created since the last snapshot represented by a `+` icon, and what objects were destroyed represented by a `-` icon. The columns are as follows: * `# New`: Number of new objects created of a particular type * `# Deleted`: Number of objects deleted (garbage collected) * `# Delta`: New - Deleted. Positive means more were created than deleted. * `Alloc. Size`: Size of all newly created objects of that type added together * `Freed Size`: Size of all deleted objects of that type added together * `Size Delta`: Alloc. Size - Freed Size. Positive means more bytes were created than deleted. Typically sorting by `Size Delta` is the most useful for hunting down memory regressions. A large positive value means a lot of extra bytes were allocated for that type of object. Expanding the type category will show for each object ID, whether it was new or deleted, and the size it was. ### Statistics View From the same dropdown menu for selecting "Summary" or "Comparison", you can also select "Statistics", which shows a pie chart of various memory categories. This view only accounts for a few limited categories of memory, and doesn't have any way to drill down into the category to see more, so this view is of limited use. # Heap Timelines TODO: Fill out this section. # Sampling Heap Profiler TODO: Fill out this section. --- ### Doc/Modules --- id: modules title: Modules --- In which we describe the module system and metadata input. ### Metadata Format In order to provide a directory or zipfile to Hermes, it must contain a `metadata.json` file at the root. The `metadata.json` file must be a JSON object, with the following fields: - `segments` - An object with string keys representing integers, which are the segments IDs. The IDs are generally sequential but there can be gaps (ex. having IDs "6" and "8" and no "7"). ID zero has special meaning, this is the "main segment" that gets loaded on startup (ex. when React Native starts). - Each value must be an array containing file paths of the files to place into that segment, expressed relative to the root of the ZIP file (ex. `subdir/foo.js`). File paths may include `./` at the start, but they are not required to. - The first element of `segments["0"]` is the first module `require`d at run time. - `resolutionTable` (Optional) - An object for which the keys are relative file names (the same file names as in `segments`). - Values are objects which map from strings given to `require()` to their actual resolved file path relative to the directory or zip file root. These relative paths should be the same as in `segments`, with leading `./`. #### Example Metadata File ```js { "segments": { "0": [ "./cjs-subdir-main.js", "cjs-subdir-2.js", "bar/cjs-subdir-bar.js", "foo/cjs-subdir-foo.js" ] }, "resolutionTable": { "./cjs-subdir-main.js": { "foo": "./foo/cjs-subdir-foo.js" }, "./foo/cjs-subdir-foo.js": { "bar": "./bar/cjs-subdir-bar.js" } } } ``` ### Require system Modules can require each other using the `require` function provided as a local variable by the runtime. The argument to `require` must be an absolute path which root is the root of the ZIP file or input directory. For example: ```js const Foo = require('/subdir/foo.js'); Foo.doSmth(); ``` ### Source maps Each JavaScript file can optionally provide a corresponding source map, which is the name of the source file with the suffix `.map`. For example `subdir/foo.js` might provide a `subdir/foo.js.map` file. ### Complete design Module mode is currently activated via passing `-commonjs` to Hermes while compiling. Hermes can then be given a directory and a `metadata.json` file, or a simple list of files with the first being the entry point. First, each file is parsed just like any other JS file. Then, a call to `hermes::wrapCJSModule` puts each file in its own "module function", which binds `exports, require, module` as parameters. IR generation relies on this wrapping of the AST. Every CJS module file generates IR into a shared `hermes::Module` (it's called `M` in `generateIRForSourcesAsCJSModules`). Each of these generated CJS modules are now `hermes::Function *`s. These are registered in the `cjsModules_` field using the `hermes::Module::addCJSModule` function, which stores information in the `CJSModule` struct regarding filename, id, and IR function. This allows lookup of the CJS modules either via `hermes::Function *` or by string literal (file path). If the caller of the Hermes CLI passes `-static-require`, then we attempt to resolve all `require` calls at compilation time. This occurs in `ResolveStaticRequire.cpp`, which is able to resolve files if they were povided by the user at invocation time and if all `require` calls only take string literals as arguments. If every `require` call is able to be resolved, every one of these `require` calls is replaced with a call to `HermesBuiltin_requireFast` with an ID for the CJS module, and that function does no string work and is therefore very fast. After all CJS modules have generated IR and all the `require`s have been resolved, we generate one or more bytecode files from our `IR::Module M`. This requires two special bits of logic in `hbc::generateBytecodeModule`. - We add a mapping from a CJS module to the HBC function ID. This allows us to actually run `require` when JS execution demands it. If `require`s have been resolved, we add to the `cjsModulesStatic_` table in the HBC file, else we add to to the `cjsModules_` table in the HBC file (which maps from strings instead of IDs). - To accommodate bundle splitting, we also pass a `SegmentRange` to the function. This allows us to only compile the functions which are needed by the CJS modules in the segment. We then set a `cjsModuleOffset_` field in the HBC file, which allows us to know how far into the complete set of CJS modules this segment is. **Because every HBC file contains a contiguous set of CJS modules, each of which are unique, it is not possible for multiple segments to contain the same CJS module.** Having built 1 or more HBC files in the compiler, we can now execute them. The `vm::Domain` data structure is used for keeping track of all HBC files which were compiled together. In particular, the `Domain` owns a CJS module table. This table is an array of CJS modules, indexed by the CJS module's ID. If `require`s were not resolved at compile time, there's also a mapping from file path to that ID. The first HBC file to be loaded must have a `cjsModuleOffset_` of `0`. CJSModule `0` is the entry point, and will be executed first. Loading of other segments is then done via a `loadSegment` call in the runtime; the user can call it via the ConsoleHost `loadSegment` or more commonly via the Hermes API. `loadSegment` does need a `requireContext`, which allows us to determine which `Domain` to actually load the new CJS modules from the segment into. This is registered into `require.context` (recall that `require` was bound as a param in all CJS modules). Finally, we can `require`. When `require` is called, one of two things happens: - If we DID resolve all static `require`s, then calls to `require` were turned into Hermes builtin calls, so the actual value of `require`s (the parameter) is not used. We simply call `HermesBuiltin_requireFast` via the `CallBuiltin` instruction. - If we DID NOT resolve all static `require`s, we call the `require` function. The runtime will have set up that function to also pass along the base path (to allow relative `require`), so `require` is now a BoundFunction (as if we'd done `require = require.bind(currentPath)`). Note that this is transparent to the application developer, and doesn't change the way `require` is actually called in JS source. In either case, we do `runRequireCall` as implemented in `require.cpp`. It performs any necessary checks, calls the target CJS module, and caches and reads `exports` back. Hermes also partially supports ECMAScript modules. Currently, the interop of ESM and CJS modules is defined simply by turning `import` into `require` calls. This precludes full correctness of the ESM module system, which requires _live bindings_; when a value is changed in the imported module, the local binding to that value must also be updated. Tests for the current emitted code can be found in `test/hermes/esm/`. --- ### Doc/Optimizer --- id: optimizer title: Design of the Optimizer --- ### Introduction This document describes the high-level design of the Hermes optimizer. The Hermes optimizer transforms the Hermes IR into a more efficient representation that preserves the original semantics of the program. The IR.md document describes the design of the Hermes IR. ### Key concepts This section describes a few key concepts and ideas: - The optimizer is responsible for optimizing the IR. IRGen and BytecodeGen are not the right place for implementing optimizations. The parts of the compiler that translate from one representation to another are inherently complex because they require the understanding of the semantics of both representations. Moreover, translators are not designed like optimizers. They do not have good access to analysis and do not allow the separation of the optimizer from the translation, which makes debugging more difficult. - Passes: Optimizations are organized in passes. There are two kinds of passes: function passes and module passes. Function passes can modify only the functions that they operate on, while module passes operate on the whole module. Function passes are allowed to read the whole module but only touch the current function. - Analysis: Analyses are caches in front of a computation of some property. For example, the dominator analysis is a cache that helps reduce compile time by removing the need to recompute the dominator tree for each function. Analyses are all about caching and invalidating pre-computed properties. - Optimizations do one thing: Optimizations are designed to be simple and this means that they do only one thing. For example, the common subexpression elimination optimization does not delete dead code "on the way" just because it can. - Optimizations are predictable: Sometimes there are several legal representations of the program, but the optimizer should never randomize the output of the compiler. Randomization of the output happens when the output depends on runtime information such as the order of elements in a set or map. Randomizing the output of the compiler makes it very difficult to write tests and reproduce bugs. LLVM has data structures that provide guaranteed order - use them! - Write compile-time efficient algorithms: The compile time of a compiler is a very important metric and we attempt to minimize compile time as much as possible. Do not write exponential algorithms (or polynomial algorithm with a high degree). If you are writing a quadratic algorithm make sure to implement a sliding-window or other techniques that will allows to limit the quadratic search to a small subset of the graph. Always assume that there exist a function with hundreds of consecutive basic blocks or a basic block with thousands of instructions. If you are writing a "solver" then you are probably doing it wrong. - There are three kinds of transformations: canonicalization, simplification and lowering. Make sure that you know exactly what kind of transformation you are doing and why. Canonicalizations are transformations that expose opportunities for other transformations. Re-association (reducing tree height, placing constants on the RHS, etc.) is a canonicalization because it organizes things in predictable patterns and makes the life of future optimizations simpler by reducing the number of possible inputs. Inlining is another example of effective canonicalization because it exposes opportunities for optimizations in the caller function (by providing more information). Another example is loop rotation, which is a canonical representation of all loops. In canonicalization we strive to clean up the program as much as possible and reach a pure representation of the program. Simplification is what we normally think of as optimizations, like removing redundancy by deleting dead code and optimizing arithmetic, etc. Canonicalization can allow simplification that can allow more canonicalization. For example, de-virtualization unblocks inlining that may allow some transformations that enable more de-virtualization. Lowering transformations are the opposite of canonicalization. In Lowering transformations we generate patterns that are closer to the target representation. We may not be able to recover from lowering transformations. One example for lowering transformation is loop strength reduction where the optimizer transforms loop indices into non-consecutive accesses that fit with the hardware instruction set. Another example is loop versioning where the body of the loop is duplicated and versioned multiple times . --- ### Doc/PerfProfiling --- id: perf-profiling title: perf Profiling --- This document describes how to profile the performance of Static Hermes. ## Profiling JIT Currently, we rely on Linux perf tool for profiling JIT'ed code, and we only enable JIT on ARM64 platform. So you need to have a Linux machine with ARM64. ### How To Profile 1. Recording the trace. `-Xperf-prof` is to enable perf profiling, `-Xperf-prof-dir` is to specify the output directory (by default it's `/tmp` so if you don't want to look into those generated files, you can skip this flag). `-k mono` means we use CLOCK_MONOTONIC for clock id, as it's used in jitdump. Here we only sample user space events, but you could also sample kernel events and also specify different flags (e.g., -g for call graph). 2. Injecting the jitdump into the perf.data. This will create an ELF binary for each JIT'ed function. 3. Reporting the trace. ```bash perf record -g -k mono -e cycles:u ./bin/hermes ~/js/test.js -Xjit=force \ -Xperf-prof -Xperf-prof-dir ./ perf inject -j -i perf.data -o perf.data.jitted perf report -i perf.data.jitted --call-graph=fractal,callee --children ``` --- ### Doc/ProhibitInvoke --- id: prohibit-invoke title: Valid-invocation enforcement (prohibitInvoke and the constructor rule) --- ### Introduction Hermes enforces two kinds of "you cannot invoke this function that way" rules: 1. **`prohibitInvoke`** — a per-JS-function flag that says the function is constructor-only or call-only (e.g. an ES6 class constructor cannot be called without `new`; an arrow function, method, generator, or async function cannot be called with `new`). 2. **The "a `NativeFunction` cannot be used as a constructor" rule** — a `CellKind`-based rule that rejects `new`ing a plain C++ builtin that is not a `NativeConstructor`. These two mechanisms are **orthogonal** and fire at different times: the `prohibitInvoke` check runs at the **callee entry** and is keyed on a per-function flag; the constructor rule runs **caller-side** at the `new` site (when `this` is created) and is keyed on the callee's `CellKind`. This document describes both, and how each is realized across the four execution paths: the bytecode interpreter, the JIT, C++ builtins, and the Static Hermes (SH) native C backend. --- ## Part 1 — `prohibitInvoke` (the per-function flag) ### The two enums There are two `ProhibitInvoke` enums, with **deliberately different value orderings**, bridged by `computeProhibitInvoke()`. IR-level (`include/hermes/IR/IR.h`): ```cpp enum class ProhibitInvoke { ProhibitNone, // = 0 ProhibitConstruct, // = 1 ProhibitCall, // = 2 }; ``` Backend/runtime (`include/hermes/BCGen/FunctionInfo.h`): ```cpp enum ProhibitInvoke { Call = 0, // regular (non-new) calls prohibited => constructor-only Construct = 1, // construct (new) calls prohibited => call-only None = 2, }; ``` > **Gotcha:** in the backend enum the names denote *which kind of invocation is > prohibited*, and the numeric values are inverted relative to the IR enum. > Always convert via `computeProhibitInvoke()` (`FunctionInfo.h`); never assume > the numeric values of the two enums line up. ### How the restriction is decided The restriction is derived from the function's definition kind in `Function::getProhibitInvoke()` (`lib/IR/IR.cpp`): - ES6 base/derived constructors → `ProhibitCall` (must use `new`). - Generators, async functions, arrow functions, and object/class methods → `ProhibitConstruct` (cannot use `new`). - Everything else → `ProhibitNone`. ### Where it is stored The value lives in one of two places, depending on the function kind: - **Bytecode functions:** a 2-bit field in the `FunctionHeaderFlag` byte of the code block header (`include/hermes/BCGen/HBC/BytecodeFileFormat.h`), written during bytecode generation (`lib/BCGen/HBC/BytecodeGenerator.cpp`). Bit layout within the flags byte (LSB first): bits 0-1 `ProhibitInvoke`, bit 2 `StrictMode`, bit 3 `HasExceptionHandler`, bit 4 `HasDebugInfo`, bit 5 `Overflowed`, bits 6-7 `Kind`. - **SH/native-compiled functions (`NativeJSFunction`):** a 2-bit `prohibit_invoke` field in `SHNativeFuncInfo` (`include/hermes/VM/static_h.h`), emitted into the generated C function-info table (`lib/BCGen/SH/SH.cpp`). - **C++ builtins (`NativeFunction` / `NativeConstructor`):** no flag at all — for these, invocation validity is handled by the constructor rule (Part 2) and by hand-written checks in the builtin body. The central predicate for the flag (`BytecodeFileFormat.h`): ```cpp bool isCallProhibited(bool construct) const { return getProhibitInvoke() == (uint8_t)construct; } ``` This exploits the backend enum values: for a construct call (`construct == true == 1`) it matches `Construct(1)`; for a plain call (`construct == false == 0`) it matches `Call(0)`; `None(2)` never matches either, so one comparison covers both directions. ### Enforcement — a callee-entry check The `prohibitInvoke` flag is checked at the **callee entry**, keyed on the *callee's* own flags. There is no central gate: `Callable::call` (the vtable funnel), `Interpreter::handleCallSlowPath`, and the SH `doCall` / `_sh_ljs_call` helpers all deliberately do *not* check the flag; they only dispatch. Being a callee-entry check keyed on the callee is exactly what makes it caller-agnostic for bytecode functions. | Callee kind | Flag enforced at entry? | Where | |---|---|---| | Bytecode (interpreted) | Yes | `interpretFunction` entry preamble and inline Call fast-path (`lib/VM/Interpreter.cpp`) | | Bytecode (JIT-compiled) | Yes | Inline in the compiled prologue (`lib/VM/JIT/arm64/JitEmitter.cpp`) → shared slow-path helpers | | C++ builtin | N/A (no flag) | Constructor rule (Part 2) + manual body checks | | SH-compiled (`NativeJSFunction`) | No | Flag is stored but never checked at call time | #### Interpreter (bytecode callees) Two sites, both raising the same two errors: - Entry preamble of `Interpreter::interpretFunction` (`lib/VM/Interpreter.cpp`): checks `curCodeBlock->getHeaderFlags().isCallProhibited(newFrame.isConstructorCall())`. Done before the callee frame is fully set up, so the exception appears to come from the call site. - Inline Call fast-path (`lib/VM/Interpreter.cpp`): checks `calleeBlock->getHeaderFlags().isCallProhibited(isCtorCall)`, where `isCtorCall` is (`new.target` is not undefined). - Messages: `"Function is not a constructor"` / `"Class constructor invoked without new"`. The inline fast path is taken only for `JSFunction` callees *without* a JIT pointer; when the callee is JIT-compiled, the interpreter skips its own check because the JIT prologue self-checks. #### JIT (bytecode callees; arm64 only) Emitted **inline at the compiled function's own prologue** (`lib/VM/JIT/arm64/JitEmitter.cpp`): reads `getHeaderFlags().getProhibitInvoke()`, loads `new.target`, compares to undefined, and branches to an out-of-line slow path that calls the shared helpers `_sh_throw_invalid_call` / `_sh_throw_invalid_construct` (`lib/VM/JIT/arm64/JitHandlers.cpp`) — same two error messages. Complete and caller-agnostic. (arm64 is the only JIT backend present.) #### SH native backend (`NativeJSFunction` callees) — flag enforcement gap The SH C backend **records** `prohibit_invoke` in `SHNativeFuncInfo` and uses it for `isConstructor()` (`lib/VM/Operations.cpp`) and `.prototype` suppression (`lib/VM/Callable.cpp`), but **emits no callee-entry guard** for it: - The generated function prologue (`lib/BCGen/SH/SH.cpp`) emits stack-overflow / frame / try setup but no `new.target`/prohibit check. - Call lowering → `_sh_ljs_call` → `doCall` → `NativeJSFunction::_legacyCall` (just `functionPtr_(shr)`) — no flag check. - The code flags this as unfinished: `TODO(T168592126) standardize on where we perform function call validation for the native backend.` - Consistent with the gap, there is no SH-backend test for `prohibitInvoke`; the existing `test/hermes/prohibit-invoke.js` runs under the interpreter. Note this gap is specifically about the *flag*. The caller-side constructor rule (Part 2) *is* present in the SH backend via `_sh_ljs_create_this`. --- ## Part 2 — The constructor rule (`NativeFunction` cannot be `new`ed) This is a separate, `CellKind`-based rule enforced **caller-side** at the `new` site, when `this` is created — before the callee frame is set up. It rejects `new`ing a plain C++ builtin (`NativeFunction`) that is not a `NativeConstructor`. It does **not** consult the `prohibitInvoke` flag. ### Interpreter: `CreateThisForNew` / `CreateThisForSuper` → `createThisImpl` For `new X()`, the compiler emits a `CreateThisForNew` opcode (and `CreateThisForSuper` for `super()` in derived constructors) *before* the actual `Construct`. The interpreter handlers (`lib/VM/Interpreter.cpp`) call `Interpreter::createThisImpl` (`lib/VM/Interpreter-slowpaths.cpp`), which classifies the callee by `CellKind`: - `>= CallableExpectsThisKind_first` (`JSFunction`, `NativeJSFunction`): the callee wants a pre-made `this` → allocate the object. - `>= CallableMakesThisKind_first` (`NativeConstructor`, `FinalizableNativeFunction`, `JSCallableProxy`, `NativeJSClass`, `JSClass`): the callee makes its own `this` → return `undefined`. - `>= CallableUnknownMakesThisKind_first` (`BoundFunction`, `NativeFunction`): walk the bound-function target chain, then re-check. If after unwrapping the target is still a plain `NativeFunction` (not promoted into the "makes this" range where `NativeConstructor` lives), throw `"This function cannot be used as a constructor."` - else (not a `Callable` / not an object): throw via `raiseTypeErrorForValue` with `" cannot be used as a constructor."`. The ordered `CellKind` ranges that make the `>=` comparisons work are defined in `include/hermes/VM/CellKinds.def` (`CallableUnknownMakesThis = {BoundFunction, NativeFunction}`, `CallableMakesThis` starts at `NativeConstructor`, `CallableExpectsThis = {JSFunction, NativeJSFunction}`), with contiguity enforced by static_asserts in `include/hermes/VM/CellKind.h`. ### SH backend: `_sh_ljs_create_this` `_sh_ljs_create_this` (`lib/VM/StaticH.cpp`) is the SH analog with identical `CellKind` logic and the same `"This function cannot be used as a constructor."` throw. It additionally validates up front that `new.target` is a `Callable` (`" invalid new.target."`). It is emitted by `generateCreateThisInst` (`lib/BCGen/SH/SH.cpp`), and the JIT emits it too (`lib/VM/JIT/arm64/JitEmitter.cpp`). So the constructor rule is present in all backends — this is the caller-side construct gate the SH `prohibitInvoke` gap does *not* affect. ### C++ builtins also self-check Beyond the `CellKind` rule, dual/opposite-mode builtins enforce their own contract in their body by inspecting `args.isConstructorCall()`, e.g.: ```cpp if (args.isConstructorCall()) return runtime.raiseTypeError("BigInt is not a constructor"); // BigInt.cpp if (!args.isConstructorCall()) return runtime.raiseTypeError("ArrayBuffer() called ..."); // ArrayBuffer.cpp ``` Dual-mode builtins (Array, Date, Error, Boolean) branch on `args.isConstructorCall()` internally. `NativeConstructor` itself is largely a marker subclass (its `_callImpl` only *asserts* invariants in debug builds). --- ## How the two mechanisms combine During `new X()` the two checks fire in order: 1. **Caller-side (constructor rule).** `CreateThisForNew` / `createThisImpl` (interpreter) or `_sh_ljs_create_this` (SH/JIT) runs first, classifies the callee by `CellKind`, and either allocates `this`, returns `undefined`, or throws `"This function cannot be used as a constructor."` for a plain `NativeFunction`. No call frame exists yet. 2. **Callee-entry (`prohibitInvoke` flag).** The subsequent `Construct` performs the call; on entry the callee's `prohibitInvoke` flag is checked via `isCallProhibited(isCtorCall)`, throwing `"Function is not a constructor"` / `"Class constructor invoked without new"`. They catch different things and are complementary rather than redundant: | | Caller-side constructor rule | Callee-entry `prohibitInvoke` | |---|---|---| | Mechanism | `CellKind` range check | `prohibit_invoke` / header-flag bit | | Catches | plain `NativeFunction` used with `new` | JS/native function whose flag forbids that invocation (arrow/method/generator/async/class ctor) | | Timing | at the `new` site, before the frame exists | when the callee frame is set up | | Message | `"This function cannot be used as a constructor."` | `"Function is not a constructor"` / `"Class constructor invoked without new"` | | Sites | `createThisImpl` (interp), `_sh_ljs_create_this` (SH/JIT) | `Interpreter.cpp` entry/fast-path, JIT prologue | ### `isConstructor` — the unified predicate `isConstructor` (`lib/VM/Operations.cpp`) is the one place that layers both mechanisms together. It walks the `JSCallableProxy` and `BoundFunction` target chains to the eventual target, then: - for a `JSFunction` (bytecode), consults the flag via `!isCallProhibited(/*construct=*/true)`; - for a `NativeJSFunction`, consults `prohibit_invoke != ProhibitInvoke::Construct`; - otherwise applies the `CellKind` rule: a plain `NativeFunction` is not a constructor unless it is a `FinalizableNativeFunction` or `NativeConstructor`. Note that `createThisImpl` / `_sh_ljs_create_this` do **not** call `isConstructor` and do **not** check the flag — they only do the `CellKind` check. `isConstructor` is used by RJS/spec operations (e.g. `Reflect.construct`, `instanceof` helpers), not as the `new`-site gate. --- ## Cross-calling behavior Because the `prohibitInvoke` check is at the callee entry and keyed on the callee's own flags, and the constructor rule is at the `new` site keyed on the callee's `CellKind`, both hold uniformly regardless of the caller: - Interpreter → bytecode: flag enforced (interpreter entry / fast path); constructor rule enforced at `CreateThisForNew`. - JIT → bytecode, and anyone → JIT-compiled bytecode: flag enforced (JIT prologue self-checks); constructor rule enforced via emitted `_sh_ljs_create_this`. - SH → bytecode: flag enforced — `doCall` routes `JSFunction` callees to their JIT pointer or `_interpret`, both of which carry the callee-entry check; constructor rule enforced via `_sh_ljs_create_this`. - Anyone → C++ builtin: the constructor rule (caller-side `CellKind` check) rejects `new`ing a non-constructor builtin; call/construct contracts beyond that rely on the builtin's own manual checks. - Anyone → SH-compiled `NativeJSFunction`: the constructor rule still applies caller-side, but the `prohibitInvoke` *flag* is **not** enforced at invocation time. This is the one real hole (`TODO(T168592126)`). --- ## Other consumers (not enforcement) - `.prototype` setup: `lib/VM/Callable.cpp` suppresses `.prototype` on call-only (`ProhibitInvoke::Construct`) non-generator functions. - Inliner: `lib/Optimizer/Scalar/Inlining.cpp` refuses to inline a construct call into a `ProhibitConstruct` function, and vice versa for `ProhibitCall`. - InstSimplify: `lib/Optimizer/Scalar/InstSimplify.cpp` can drop an unused `new.target` when `ProhibitNone`. - Disassembler: `lib/BCGen/HBC/BytecodeDisassembler.cpp` prints `Constructor` for `ProhibitInvoke::Call` and `NCFunction` for `ProhibitInvoke::Construct`. --- ## Quick reference `prohibitInvoke` (per-function flag, callee-entry): - Enums: `include/hermes/IR/IR.h`, `include/hermes/BCGen/FunctionInfo.h` - Decision logic: `lib/IR/IR.cpp` (`Function::getProhibitInvoke()`) - Predicate: `include/hermes/BCGen/HBC/BytecodeFileFormat.h` (`isCallProhibited`) - Set: `lib/BCGen/HBC/BytecodeGenerator.cpp` (bytecode), `lib/BCGen/SH/SH.cpp` (SH) - Interpreter enforcement: `lib/VM/Interpreter.cpp` - JIT enforcement: `lib/VM/JIT/arm64/JitEmitter.cpp`, `lib/VM/JIT/arm64/JitHandlers.cpp` - SH flag gap: `lib/BCGen/SH/SH.cpp`, `lib/VM/StaticH.cpp` (`TODO(T168592126)`) Constructor rule (`CellKind`-based, caller-side): - Interpreter: `CreateThisForNew`/`CreateThisForSuper` in `lib/VM/Interpreter.cpp` → `createThisImpl` in `lib/VM/Interpreter-slowpaths.cpp` - SH/JIT: `_sh_ljs_create_this` in `lib/VM/StaticH.cpp`, emitted by `lib/BCGen/SH/SH.cpp` and `lib/VM/JIT/arm64/JitEmitter.cpp` - CellKind ranges: `include/hermes/VM/CellKinds.def`, `include/hermes/VM/CellKind.h` - Manual builtin checks: `lib/VM/JSLib/{BigInt,ArrayBuffer,DataView,Boolean,Array,Date,Error}.cpp` Unified predicate: - `isConstructor`: `lib/VM/Operations.cpp` --- ### Doc/ReactNativeIntegration --- id: react-native-integration title: React Native Integration --- ## Using a custom Hermes build in a React Native app Since React Native 0.69, Hermes is shipped as part of the React Native distribution. We call this [bundled hermes](https://reactnative.dev/architecture/bundled-hermes). If you wish to customize Hermes and use it inside your React Native app, you can do so by using the `REACT_NATIVE_OVERRIDE_HERMES_DIR` environment variable. This variable allows you to specify a folder where you can store your custom copy of the Hermes repository. ```bash export REACT_NATIVE_OVERRIDE_HERMES_DIR=/path/to/your/hermes/repo ``` If you set this variable, React Native will use the Hermes build from the specified directory instead of the one that comes with the React Native distribution. > [!NOTE] > If you are making changes to the compiler in Hermes, be sure to make sure you test your app in release mode as this enables bytecode compilation in advance. ### Instructions for Android On Android, once you set the `REACT_NATIVE_OVERRIDE_HERMES_DIR` environment variable, make sure you also: 1. Enable a build from source following the instructions in the [React Native website](https://reactnative.dev/contributing/how-to-build-from-source#update-your-project-to-build-from-source). 2. Re-run the Android app with the `yarn android` command. ### Instructions for iOS On iOS, once you set the `REACT_NATIVE_OVERRIDE_HERMES_DIR` environment variable, make sure you also: 1. Disable React Native's Default Hermes Pod: Ensure that the `:hermes_enabled` flag is set to `false` in `ios/Podfile`. ```ruby use_react_native!( :path => config[:reactNativePath], :hermes_enabled => false, # ... other configurations ) ``` 2. Enable a build from source by installing the pods as follows: ```bash BUILD_FROM_SOURCE=true bundle exec pod install ``` 3. Re-run the iOS app with the `yarn ios` command. ## Reporting native crashes If Hermes causes a native crash in your application, a stack trace is critical for us to be able to understand where the crash occurred. If you have a native crash to report, please be aware that in most cases, it is not feasible for us to debug crashes in earlier versions of Hermes. Please update your app to the latest React Native version, as that contains the latest hermes-engine versions. Specifically since React Native 0.69, Hermes is now coming [bundled together with React Native](https://reactnative.dev/architecture/bundled-hermes). Including the symbolicated stack trace will make it easier for us to address your bug report more quickly. ### How to symbolicate a native crash on Android To symbolicate a native crash on Android, you need to use the [`ndk-stack`](https://developer.android.com/ndk/guides/ndk-stack) command. This command is part of the Android SDK and you should be able to access with `$ANDROID_HOME/ndk//ndk-stack` (provided you replace the URL with your NDK version like `$ANDROID_HOME/ndk/21.4.7075529/ndk-stack`). To use the `ndk-stack` command you will need the debug symbols (check the paragraph below to see where to find them). You can then symbolicate a stacktrace as follows: ```bash $ANDROID_HOME/ndk/21.4.7075529/ndk-stack -sym .//obj/local/arm64-v8a < crash.txt ``` provided that `crash.txt` contains your stacktrace in plain text, and you replace `armeabi-v7a` with the correct architecture you used when the native crash was recorded. As an alternative, you can trigger a crash and have a symbolicated logcat in real time with the following command: ```bash adb logcat | $ANDROID_HOME/ndk/21.4.7075529/ndk-stack -sym .//obj/local/arm64-v8a ``` ### Where to find the debug symbols #### React Native < 0.69 For React Native versions before 0.69 (i.e. hermes-engine 0.11.0 and previous versions), you can find the debug symbols in the [GitHub release](https://github.com/facebook/hermes/releases) corresponding to the Hermes NPM you used to build your application. Download the `hermes-runtime-android-vX.Y.Z.tar.gz` file for your version, unpack the tar file, then run `ndk-stack` using the contained directory as described in the paragraph above. #### React Native 0.69 and 0.70 For React Native versions 0.69 and 0.70, you can find the debug symbols in the [GitHub release](https://github.com/facebook/react-native/releases) corresponding to the React Native version you used to build your application. For instance for [React Native 0.70.6](https://github.com/facebook/react-native/releases/tag/v0.70.6), you can find the `hermes-native-symbols-v0.70.6.zip` file with the debug symbols inside. #### React Native >= 0.71 For React Native versions 0.71 and above, the debug symbols are uploaded to Maven Central together with the `react-native` and `hermes-engine` artifacts. You don't need to manually download the debug symbols at all, as they will be available to you when you build your apps locally. You can just invoke the `ndk-stack` command suggested above and the symbolication will just work. --- ### Doc/RegExp --- id: regexp title: RegExp --- ## RegExp The Hermes regexp engine is a traditional engine using a backtracking stack. It compiles a regexp into bytecode which can be executed efficiently. For regexp literals like `/abc/`, this occurs at compile time: the regexp bytecode is embedded into the Hermes bytecode file. Note regexp bytecode is distinct from Hermes bytescode. The regexp engine proceeds as follows: 1. *Parse phase.* The regexp parser emits a tree of nodes, effectively an IR. 1. *Optimization phase.* The node tree is traversed and optimized in various ways. 1. *Emitting phase.* The node tree is traversed and emits regexp bytecode. 1. *Execution phase.* The bytecode is executed against an input string. ## Supported Syntax As of this writing, Hermes regexp supports 1. All of ES6, including global, case-insensitive, multiline, sticky, and Unicode (and legacy). 1. ES9 lookbehinds. 1. Named capture groups. 1. Unicode property escapes. --- ### Doc/SpecIncompat # Incompatibilities With The JavaScript Spec This documents aims to collect and explain deliberate differences between Static Hermes and the JavaScript spec. ## Arguments Object ### "Mapped" Arguments Object in Loose Mode In loose mode, updates to the arguments object are not reflected in the function parameter values and vice versa. ```javascript function foo(param) { arguments[0] = 10; print(param, arguments[0]); // Prints different values in SH } ``` Motivation: this is a very rare case. Implementing it correctly is expensive and would impose cost on the majority of usages which do not depend on this behavior. Optimizing it, so it doesn't regress legitimate cases is possible, but complex. This is "implementable", but with very low priority. ### Assigning to Arguments in Loose Mode Assignment to `arguments` is prohibited in loose mode. ```javascript function foo() { arguments = 0; // Allowed by the spec, but prohibited in Static Hermes } ``` Motivation: this is a very rare case, not generally useful. Implementing it correctly is possible, but complex, with very little benefit. This is "implementable", but with very low priority. ### Aliasing Arguments With a Var Declaration in Loose Mode In loose mode declaring `var arguments` does not alias the arguments object. Instead it simply creates a new declaration that *shadows* the arguments object, similar to `let`. ```javascript function foo() { var arguments; print(arguments); // Prints undefined in Static Hermes } ``` Motivation: similar to assigning to `arguments`, this is a very rare case, with no uses that we are aware of. This is "implementable", but with very low priority. ## Full Scoped Function Promotion Semantics in Loose Mode Static Hermes implements most of the scoped function promotion semantics in loose mode, but some corner cases are not spec compliant yet. ```javascript function g() { { function f() { return 1; } { function f() { return 2; } } } print(f()); } g(); ``` Apparently the spec requires this example to print "1", because the second `f()` shouldn't be promoted to function scope. Shermes prints "2". In our (quick and incomplete) tests, other major engines also print "2". Motivation: these are very rare cases. Loose mode itself is rare. While we intend to address them, the priority is low. --- ### Doc/Strings --- id: strings title: Strings --- ## Hermes Bytecode String Kinds Hermes bytecode has three kinds of string. The simple JS program `Object.foo = "bar";` contains examples of all of them. - `Object` is **Predefined** because it is being used directly to access a property (i.e. it is an identifier) -- in this case on the global object -- and both the compiler and runtime are already aware of it. See `hermes/VM/PredefinedStrings.def` for a full list of strings that could be Predefined (if they were used for property access). - `foo` is an **Identifier** because it is being used directly to access a property but it is not built-in to the VM or compiler. - `bar` is a **String**, because it is referred to as a literal but neither of the previous conditions apply. The distinction between these is important during bytecode initialisation, particularly "Identifier Table Initialisation", detailed in the section below. ## String Table Format In the Hermes bytecode format, the string table is split into the following consecutive sections of the file: 1. String Kinds. A sequence which describes the kinds of the strings in the table (as described in "Hermes Bytecode String Kinds"). Abstractly, the i-th element in the sequence is the kind of the i-th string in the table. Represented as a run-length encoding. 2. Identifier Hashes. This sequence has an element corresponding to each identifier in the table. The i-th element of this sequence corresponds to the i-th identifier in the table. If the string is an Identifier, the element contains a hash of the identifier's string representation. 3. Small String Table. The primary index into the string table. When a bytecode instruction refers to a string by its index, it uses the offset into this data structure. Represents the string with three pieces of information: - Whether it is UTF16 or not. - Its offset into the character storage. - Its length. Each entry is packed in 32 bits: 1 bit for the UTF16 flag, 23 bits for the offset and 8 for the length. If the length or the offset do not fit in the available space, the entry spills into the overflow table (the next section). In this case the small entry's length is 255 and its offset field is interpreted as the offset into the overflow table. 4. Overflow String Table. Contains the offset and length information (32 bits for each) for strings that could not fit into a small entry. 5. ASCII String Storage. A contiguous sequence of ASCII character data. Character data for individual strings can potentially overlap. 6. UTF16 String Storage. As above, but for UTF16 strings. ## Identifier Table To speed up property accesses the Runtime interns property names, assigning a number to refer to them by. Although bytecode instructions also refer to property names as numbers, the same string -> number mapping can't be used because a property name's number in a bytecode file stems from that file's string table and will not in general agree across all bytecode files (the Runtime could be running code from multiple files). The Runtime's intern table is managed by the `IdentifierTable` which maintains a two-way mapping between strings and their numbers. It is known to the GC which will clean up entries corresponding to unused names. ### Importing String Table IDs The Runtime representation of a bytecode file maintains a mapping between the numbers that strings are referred to by in the bytecode (in instructions) and the numbers that strings are referred to by in the `IdentifierTable`, this is initialised when the bytecode is loaded. Identifier Translations are used to speed this process up: - Only the entries in the mapping corresponding to identifiers are assigned. - If the identifier is Predefined its Identifier Translation is its IdentifierTable ID and the mapping can be initialised without querying the IdentifierTable. This is because the compiler and Runtime agree ahead of time on the IdentifierTable IDs that Predefined strings will be assigned to. - If the identifier is not predefined, its Identifier Translation is its precomputed hash, this can be passed to the IdentifierTable when inserting it to avoid having to page in the contents of the string to calculate the hash during initialisation. ## Lowering Strings to Hermes Bytecode When a string is mentioned as a literal in the source code, this is always represented by an instance of `LiteralString` in the IR (Intermediate Representation). This is a pointer to a UTF8 string that has been interned in the compiler's memory. In HBC (Hermes bytecode) opcodes refer to literal strings by an index into a string table (part of the bytecode file). See "String Table Format", above, for a detailed description. - Before the IR is lowered, all the mentioned strings are gathered into a table and assigned indices. - Indices are not assigned until all strings are gathered, at which point the table is frozen. It will remain immutable, but can now be queried: Given the UTF8 representation of a string, it will return its ID. - The frozen table is used during lowering to emit String IDs in bytecode instructions. - Finally the table is serialized into the bytecode, following the format laid out above. Gathering is handled in `hbc::generateBytecodeModule`. The `UniquingStringLiteralAccumulator` class is responsible for assigning indices to strings and functions in `include/BCGen/HBC/TraverseLiteralStrings.h` are responsible for visiting each string in the IR. Before lowering instructions, the accumulator is converted into a `StringLiteralTable` which is an immutable representation of the mapping. **NB** Every potential occurrence of a string must be visited by a function declared in `TraverseLiteralStrings.h`, otherwise they will not appear in the string table. Similarly, every instance where a string could be used as an identifier should be enumerated in `isIdOperand` in `TraverseLiteralStrings.cpp`. The compiler will throw an assertion failure in debug builds if it encounters a string without an ID or an identifier that has not been marked as such during lowering. ## String Table Index Ordering The order of entries in the String Table is significant for two reasons: 1. Instructions that access properties have variants. E.g. `GetByIdShort`, `GetById` and `GetByIdLong`. They differ in the number of bytes they have available to encode a string table index (1, 2 and 4 respectively) and their own size increases correspondingly. The compiler emits the narrowest instruction that can fit the ID being accessed, so by arranging for strings that are accessed more often to have smaller IDs, the space taken by instructions can be saved. 2. Because the String Kind section (see "String Table Format" above) is a run-length encoding, its size can be minimised by grouping together strings of the same kind. In order to make good use of these properties, the compiler counts the occurrences of strings as it is gathering them. The top 2^8 most accessed strings are given the first 2^8 IDs and so on, to minimise instruction size with respect to the first constraint. Then within each category of ID (short, regular and long) strings are grouped by kind with all the Strings coming first, then Identifiers, and finally Predefineds. ## Delta Optimizing Mode In delta-optimizing mode Hermes tries to minimise the effect of incremental changes to the source on the bytecode bundle. Outside of this mode, small changes to string usage can cause the output bytecode's string table to be re-ordered. This has knock-on effects throughout the instruction stream wherever strings are referred to. When delta-optimizing mode is enabled, the order of strings that existed in the bundle before the change is preserved. ## How Hermes Packs Strings This is a description of the string packing algorithm employed by Hermes. Its design is guided by the Hermes optimization principles: it must be predictable and compile-time efficient. A Hermes bytecode file represents strings as a pair (offset, length) in a big character buffer, which necessarily contains all strings as substrings. By being clever about arranging the strings in the character buffer, we can take advantage of shared substrings. This reduces the size of the bytecode file and the memory footprint of the app. There are two types of relationships between strings: 1. A full containment relationship. For example, `once upon a time` contains `upon`. In this case, we would like to emit only the characters of the first string, and have the second string reference a substring of the first. We say that the first string is a *parent* of the second. 2. An overlapping relationship: `splitpea` and `peasoup`. Here `pea` is a suffix of the first string and a prefix of the second, and so we would like to emit `splitpeasoup` where the `pea` is shared between strings. We say that the pair (`splitpea`, `peasoup`) has *overlap* of length 3. The challenge is to find a *superstring* of all our strings which is shorter than simply concatenating them. Finding the shortest such string is the "Shortest Common Superstring" problem, and it is NP-Hard. We employ a greedy heuristic. The output is not as small as the Set Cover approach, but the Set Cover approach appears necessarily quadratic while ours is N log N. (Input size is on the order of 35k strings, so quadratic algorithms are not tolerable.) The basic approach is inspired by "A greedy approximation algorithm for constructing shortest common superstrings" by Tarhio and Ukkonen. Given a set of strings S: 1. Consider S to be vertices of a weighted directed graph. 2. Let there be an edge from s1 to s2 if s1 overlaps s2, that is, some string is both a suffix of s1 and a prefix of s2. The weight of the edge is the amount of overlap. 3. Construct a Hamiltonian Path through the graph by greedily choosing edges with the maximum weight, but ignoring edges that would result in a cycle. 4. Output the strings in the order of the path, applying the overlap. The key bottleneck of the algorithm is step 2: identifying overlapping strings. Tarhio and Ukkonen suggest using KMP string matching on all pairs of strings, which is quadratic. We instead build a generalized suffix array on all strings, which allows both finding parent and overlap relationships via binary search. ### Computing Parents and Overlap Recall that an overlap is a pair (left, right) where there is some string that is simultaneously a suffix of left, and a prefix of right. For example, `splitpea` and `peasoup` has overlap of 3. We wish to find all parents and all overlaps. We are armed with a suffix array: a sorted list of suffixes of all our strings, where each suffix points back to the string(s) that contain it. We loop over the right strings, and find all overlapping left mates. For each right string, we loop over its prefixes in increasing length. For example, given `peasoup` we loop over `p`, `pe`, `pea`... Call this the test prefix. We use binary search in our suffix array to identify suffixes that are prefixed by the the test prefix. This set of suffixes is necessarily contiguous, because the suffix array is sorted. If a suffix is exactly equal to that prefix, then we have an overlap. This is necessarily the leftmost element of our range, because our range is sorted. A key idea is that moving to the next prefix can only narrow the matching suffixes. For example, only suffixes that have `pe` as a prefix may have `pea` as a prefix. Therefore we do not need to reset the binary search range across iterations. Furthermore, for each iteration, we only need to consider one character in each suffix, since we know all previous characters necessarily match. This is key to performance. When we find nonzero overlap, we add an `Arc` (left -> right) representing edges in our graph. The Arcs are maintained sorted by weight for our greedy algorithm. #### Example Say we wish to find overlaps with left string `splitpea` and right string `peasoup` (of course, there is only one overlap of length 3). Our proposed right string is `peasoup` and our suffix array is (considering only the suffixes of `splitpea`): `[a, ea, itpea, litpea, pea, plitpea, splitpea, tpea]` We are going to iterate the prefixes of our right string: `p`, `pe`, `pea`, `peas`, `peaso`, `peasou`, `peasoup`, but we will see that we exit early. 1. Start with `p`. Binary search at index 0 to get the contiguous range `[pea, plitpea]` We then check if the first element is exactly equal to `p` (which we can do simply by checking its length); if it were, we would add an arc of weight 1. 2. Next is `pe`. Binary search on index 2 with `e`, yielding a one-element range `[pea]` Again we would add an arc if the first element were equal to `pe`. 3. Next is `pea`. Binary search on index 3 with `a`, again yielding `[pea]` The first string of this range is indeed equal to our prefix `pea`, so we add an Arc `peasoup -> splitpea` with overlap 3. 4. Next is `peas`. Binary search to narrow our range by the fourth character `s`. This yields an empty range, so we exit the loop. After exhausting our prefixes, it may happen that our range of suffixes is not empty. For example, if we searched for `lit` we would end up with one suffix `litpea`. This is how we identify substring containment relationships. In this case we don't add an arc (since there's not actually any overlap) but we do set a pointer from `lit` to the parent string that contains it, and the offset within that parent. #### Suffix Array Construction Optimizations We construct the suffix array by uniquing suffixes via a hash set, and then sorting them. This was found to be faster than using a sorted data structure (such as `std::map`) because comparing long strings lexicographically is expensive. There are some optimizations we take advantage of: 1. We are only interested in suffixes that share a prefix with some string in our set. For example, for the set [splitpea, peasoup] we only need to look at suffixes that start with s or p. We take this a bit further by making a hash set of three-character prefixes of our strings ("trigrams"), and only constructing suffixes prefixed by one of those trigrams. This causes us to miss overlaps of length 1 and 2, but massively reduces the number of suffixes that we have to consider. 2. There are many long strings with shared suffixes. When constructing the suffix array, using a three-way radix quicksort instead of `std::sort()` is a substantial win, because it avoids comparing known-matching prefixes. #### Further Optimization 1. Computing overlap is a natural candidate to be done in parallel. 2. It's possible that we could employ a faster algorithm for suffix array construction such as SA-IS, but it is unclear how we would unique our suffixes with that approach. ### References 1. ["A greedy approximation algorithm for constructing shortest common superstrings" by Tarhio and Ukkonen](http://www.sciencedirect.com/science/article/pii/0304397588901673) 2. [3-way radix quicksort](https://en.wikipedia.org/wiki/Multi-key_quicksort) ---