Land ahoy: leaving the Sea of Nodes · V8V8’s end-tier optimizing compiler, Turbofan, is famously one of the few large-scale production compilers to use Sea of Nodes (SoN). However, since almost 3 years ago, we’ve started to get rid of Sea of Nodes and fall back to a more traditional Control-Flow Graph (CFG) Intermediate Representation (IR), which we named Turboshaft. By now, the whole JavaScript backend of Turbofan uses Turboshaft instead, and WebAssembly uses Turboshaft throughout its whole pipeline. Two parts of Turbofan still use some Sea of Nodes: the builtin pipeline, which we’re slowly replacing by Turboshaft, and the frontend of the JavaScript pipeline, which we’re replacing by Maglev, another CFG-based IR. This blog post explains the reasons that led us to move away from Sea of Nodes.The birth of Turbofan and Sea of Nodes #<br>12 years ago, in 2013, V8 had a single optimizing compiler: Crankshaft. It was using a Control-Flow Graph based Intermediate Representation. The initial version of Crankshaft provided significant performance improvements despite still being quite limited in what it supported. Over the next few years, the team kept improving it to generate even faster code in ever more situations. However, technical debt was starting to stack up and a number of issues were arising with Crankshaft:It contained too much hand-written assembly code. Every time a new operator was added to the IR, its translation to assembly had to be manually written for the four architectures officially supported by V8 (x64, ia32, arm, arm64).It struggled with optimizing asm.js, which was back then seen as an important step towards high-performance JavaScript.It didn’t allow introducing control flow in lowerings. Put otherwise, control flow was created at graph building time, and was then final. This was a major limitation, given that a common thing to do when writing compilers is to start with high-level operations, and then lower them to low-level operations, often by introducing additional control flow. Consider for instance a high-level operation JSAdd(x,y), it could make sense to later lower it to something like if (x is String and y is String) { StringAdd(x, y) } else { … }. Well, that wasn’t possible in Crankshaft.Try-catches were not supported, and supporting them was very challenging: multiple engineers had spent months trying to support them, without success.It suffered from many performance cliffs and bailouts. Using a specific feature or instruction, or running into a specific edge case of a feature, could cause performance to drop by a factor 100. This made it hard for JavaScript developers to write efficient code and to anticipate the performance of their applications.It contained many deoptimization loops: Crankshaft would optimize a function using some speculative assumptions, then the function would get deoptimized when those assumptions didn’t hold, but too often, Crankshaft would reoptimize the function with the same assumptions, leading to endless optimization-deoptimization loops.Individually, each of these issues could have probably been overcome. However, combined all together, they seemed like too much. So, the decision was made to replace Crankshaft with a new compiler written from scratch: Turbofan. And, rather than using a traditional CFG IR, Turbofan would use a supposedly more powerful IR: Sea of Nodes. At the time, this IR had already been used for more than 10 years in C2, the JIT compiler of the Java HotSpot Virtual Machine.But what is Sea of Nodes, really? #<br>First, a small reminder about control-flow graph (CFG): a CFG is a representation of a program as a graph where nodes of the graph represent basic blocks of the program (that is, sequence of instructions without incoming or outgoing branches or jumps), and edges represent the control flow of the program. Here is a simple example:Simple CFG graphInstructions within a basic block are implicitly ordered: the first instruction should be executed before the second one, and the second one before the third, etc. In the small example above, it feels very natural: v1 == 0 can’t be computed before x % 2 has been computed anyways. However, considerCFG graph with arithmetic operations that could be reorderedHere, the CFG seemingly imposes that a * 2 be computed before b * 2, even though we could very well compute them the other way around.<br>That’s where Sea of Nodes comes in: Sea of Nodes does not represent basic blocks, but rather only true dependencies between the instructions. Nodes in Sea of Nodes are single instructions (rather than basic blocks), and edges represent value uses (meaning: an edge from a to b represents the fact that a uses b). So, here is how this last example would be represented with Sea of Nodes:Simple Sea of Nodes graph with arithmetic operationsEventually, the compiler will need to generate assembly and thus will sequentially schedule these two multiplications, but until then, there is no more dependency between...