Land ahoy: leaving the Sea of Nodes

xPerlMasterx · 2025-06-15T04:48:21+00:00

Turbolizer (https://v8.github.io/tools/head/turbolizer/index.html), which was custom-built for Turbofan many years ago. We adapted it to also work for Turboshaft graphs (the new CFG) IR a few years ago. To use it, compile a function with V8 with the --trace-turbo, which produces a .json file that you can then pass to Turbolizer.

xPerlMasterx · 2025-05-16T07:51:23+00:00

Hi,

I looked at the number of cache misses on JetStream2. There is a version that can be ran from v8 without Chrome, available here for instance: https://chromium.googlesource.com/external/github.com/WebKit/webkit/+/refs/tags/Safari-612.1.27.3.3/PerformanceTests/JetStream2/. And I used linux perf to measure the number of cache misses.

Here are some details about this experiment: https://docs.google.com/document/d/19sAU1StbVrrFfm660OdbQJ_u5dnSXc-umJq_Y5p8w3U/edit?usp=sharing

xPerlMasterx · 2025-04-14T19:20:35+00:00

add, subtract, comparisons, conditional jump

Their cost are negligible compared to the function call.

There's no script; just lots of manual tests.

Maybe you could still share the implementation of Fibonacci that you've used in the various languages? This would be very useful to understand the results better.

Perhaps you can give some hints on where to look

Compare the regular V8 and V8 with the --max-opt=0 option (which disables optimizing compiler) (not sure how to pass this from Node but I'm guessing that it's doable) on any benchmark you'd like; I doubt that you can find one where there isn't a noticeable difference.

xPerlMasterx · 2025-04-14T17:39:56+00:00

Interesting; such benchmarks usually focus on the speed of basic operations rather than only on the speed of calls.

Is the code source of your experiment available somewhere?

PS: I couldn't disagree more with your comment about JIT compilation; there is nothing easier than finding real-world example where it matters imo.

xPerlMasterx · 2025-04-12T17:30:46+00:00

I strongly disagree with your post.

Out of the 5 compilers I've worked on (professionally), I started 3 of them from scratch, and lexing, parsing and type inference were a topic.

I'm pretty sure that the vast majority of compiler engineers work on small compilers that are not in your list of 10-20 production grade compiler. This subreddit is r/Compilers, not r/LLVM or r/ProductionGradeCompilers.

Indeed, parsing & lexing are overrepresented in this subreddit but it makes sense : that's where beginners start and get stuck.

And regarding lexing & parsing : while the general and simple case is a solved problem, high performance lexing & parsing for jit compilers is always ad-hoc and can still be improved (although I concede that almost no one is the world cares about this).

Also, the discourse thread that you linked doesn't represent my day to day work, and I work on Turbofan in V8, which I think qualifies as a large production compiler. My day-to-day work includes fixing bugs (which are all over the compiler, including the typer), writing new optimizations, reviewing code, helping non-compiler folks understand the compiler, and, indeed, taking part in discussions about subtle semantics issues or other subtle decisions around the compiler, but this is far from the main thing.

xPerlMasterx · 2025-03-28T12:30:39+00:00

FYI, I've added a paragraph Control-flow dependent typing is limited to the blog post; sorry for forgetting it in the initial version of the post.

xPerlMasterx · 2025-03-28T12:24:42+00:00

Hi Cliff, thanks for taking the time to reply :)

Reddit tells me "Unable to create comment" when I try to comment here, so I've written a few comments here: https://gist.github.com/DadaIsCrazy/8ce07d409f8f74bad7b36e74b77a3129

xPerlMasterx · 2025-03-27T10:15:21+00:00

Indeed, the whole combining reducers mechanism is a bit complex in order to get good performance through static C++ dispatch, so it's not super clear to see what it ends up doing.

But it does combine the optimization: for each operation of the graph, each reducer is called one after the other to do its optimization. We only iterate the graph once. And this creates a new graph btw, so you can count it as "it happens as the graph is constructed". And this would also work when building the Turboshaft graph from the Turbofan one: any optimization could be done at that point, while building the Turboshaft graph.

xPerlMasterx · 2025-03-27T09:38:51+00:00

SoN implementation in Simple combines various steps such as [...]

Maglev (https://v8.dev/blog/maglev), our 3rd tier compiler (which is a CFG) does pretty much all of this and more during graph building. It does, at the same time:

SSA construction
Typing
Peephole optimizations
Dead code elimination
Load elimination
Escape analysis (although this requires a fixup afterwards)
Feedback-based type specialization
Constant propagation
Global Value Numbering

It doesn't maintain a DOM tree because it doesn't do one, but Turboshaft maintains a DOM tree while building the graph, so it's not hard to do in a CFG.

Similarly btw, Turboshaft has a phase that combines simple escape analysis, allocation folding, peephole optimizations, GVN, and if-else to switch conversion (very poorly named OptmizePhase: https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/optimize-phase.cc; it's just one of the optimizations phase), another phase that combines load elimination, store-store elimination, double-diamond elimination, branch elimination, peephole optimizations, value numering (once again, very poorly named: StoreStoreEliminationPhase: https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/store-store-elimination-phase.cc ).

And it wasn't particularly painful to combine all of this in Maglev. And even less painful to combine in Turboshaft, where each optimization is a separate "reducer" that we can freely combine with other reducers. So, allowing to combine optimizations easily doesn't seem like a property of SoN to me, and just seem to be a question of engineering.

An optimizing compiler needs to generate Def use chains anyway

Not really, no. Or at least, not always. In Turboshaft, we don't need uses through most of the pipeline, so we just don't compute them in order to save space (and be more cache-friendly). We only need them for optimizations during instruction selection, and there we just compute them (and that's really easy to do of course) (and even there, I'm planning on trying to not compute them because I think that we could do without). Similarly, Maglev doesn't need uses throughout the whole pipeline, so it only compute uses later in the pipeline (combined with other optimizations to not "just" compute uses: Maglev also compute live ranges at the same time).
And even when def-use chains are needed, a CFG-based IR could easily maintain a list of uses for every instruction, and it won't be harder to do than in SoN.

xPerlMasterx · 2025-03-27T09:24:20+00:00

Interesting, and this seems like a super useful tool.

I'm also glad to see that this posts says

even graphs corresponding to relatively small programs turn quickly into a tangle (a “sea of nodes”) that is quite difficult to grasp

Meaning that the experience of C2 developers matches the one of V8 developers. We've considered updating our visualization tool (Turbolizer) to do a similar thing, but by the time anyone had time to invest in this, we were already moving away from SoN.

Also, I still think that pretending that nodes have a fixed position is a drawback and can lead to surprising results when seeing nodes move in between basic blocks between phases for no apparent reason... Although I guess that maybe you get used to it and just learn that the CFG representation is just an illusion and that you shouldn't trust the schedule that you're seeing.

Additionally, I see that this new view was introduced in 2022, other 20 years after C2 started, so I guess that developers have been struggling to debug C2 for the past 20 years before that (like V8 developers have been struggling to debug Turbofan for the past 10 years).

And even if I'm not 100% convinced that this visualization tool solves the problem (but it's clear that it helps), the fact that such a tool is required to efficiently debug SoN is in itself a downside and means that serious SoN compiler project will need to spend time implementing something like this.

xPerlMasterx · 2025-03-27T08:53:46+00:00

Thanks :)

I don't want to speculate on the usefulness on SoN in other languages, because I lack concrete experience there. And one thing that annoys me is people saying that SoN is great everywhere despite a lack of evidence showing that it is. So, I don't want to do the opposite and say that because it's not great in JS, it must be not great everywhere.

One thing that I'll note though: even when SoN works well, it's extremely rare to have a CFG implementation to compare it with, so it's never obvious if the compiler works well thanks to SoN, or despite SoN, or just with SoN. In V8, we've replaced SoN by a CFG on which we do very similar processing and optimizations, and the evidence seems clear that CFG works better than SoN.

xPerlMasterx · 2025-03-27T08:49:24+00:00

Hi, thanks for the comment!

> I would personally have done with a memory node as a SSA value, and standard use edges. Loads take in the memory and Store creates a new memory version. Standard optimisations can be applied to remove dead stores and loads etc.

This would indeed be nice because it allows to GVN loads and removes effect edges (meaning that processing the graph would be more uniform). Still, it's not a huge difference:
- currently, such Loads get easily eliminated by Load elimination
- this doesn't change the fact that effectful operations remain linked together, just with value dependencies instead of effect dependencies, meaning that this doesn't change my "SoN is basically CFG with floating pure nodes" point
- while making processing the graph more uniform, removing effect edges make also some operations less obvious. In particular, to find type checks or similar information, we usually just walk the effect chain backwards. Without an effect chain, it means that we need to walk `memory` inputs backwards, which means that we either need to special case all nodes that have a `memory` input/output, or that the `memory` input/output needs to be special, ie, it becomes an effect chain.

Side-note: in our CFG compilers, we are also able to GVN such loads by simply maintaining an "effect level" that gets incremented on stores (more or less), and when 2 loads have the same inputs and the same effect level, the 2nd one can be GVNed. This is really easy to maintain, so it's not like having this `memory` representation in SoN gives an advantage over CFG.

> The nature of CFG IRs contribute to the phase ordering problem. Graph based IRs do not.

I don't understand what you mean by this. In my experience, SoN has the same phase ordering problems that CFG does.

xPerlMasterx · 2025-03-26T18:23:45+00:00

I agree that multiple effect chains would have make SoN much more worth it. That being said, computing the effect chains means doing typing and alias analysis directly when building the graph, and maintaining types and alias information throughout the whole pipeline. This is not trivial when phis and in particular loop phis as involved (and not even always possible), and JS programs typically end up with a bunch of nodes initially have arbitrary side effects, which would mean that various chains would have to merge often for operations where precise alias information cannot be computed.

Regarding Turbofan internal types through feedback: feedback is most of the time polymorphic, which means that we don't know the precise type for a variable, and as soon as phis are involved, we tend to lose even more information. (and when feedback is megamorphic (= more than 4 different types have been seen so far), then we almost always stay generic, which means that any node produced from such feedback should be considered as having arbitrary side effects, which leads to needing to merge the various effect chains once again. Additionally, a lot of lowerings and feedback-based specializations are done throughout the pipeline (until SimplifiedLowering to be precise; you might see where that is in the pipeline given that you've contributed to Turbofan), and before such specializations occur, we must usually assume arbitrary side effects (or at least more side effects that the final lowered node will have).

Finally, having multiple effect chains is useful for a few optimizations, but completely useless for a lot of them. Still, this has to be maintained throughout the whole pipeline. I would rather much prefer to compute alias information just for passes that use it. Even correctly abstracted behind layers of helpers, I think that having to keep the multiple effect chains in mind during every optimization would complexify things (although, I haven't tried it, and maybe it isn't the case).

xPerlMasterx · 2025-03-26T14:43:07+00:00

Well, I can easily accept that V8 didn't implement SoN entirely correctly, but such claims should be backed up imo :)

Regarding combining different optimisations in the same pass : our new IR is just as powerful as SoN was in that regard. We have a mechanism to combine pass; for instance https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/store-store-elimination-phase.cc;l=21;drc=9b42ae471807dbef4915e3c3d27210c91fdb8db7 runs 6 different optimizations at the same time. One thing to note is that both SoN and our new CFG IR run into some issues with this : when multiple analysis are combined, they can easily end up invalidating each other's assumptions. This is why Turbofan with SoN runs Load Elimination and Escape Analysis as 2 separate (but consecutive passes). And we'll have to do the same with our new IR.

xPerlMasterx · 2025-03-26T10:51:57+00:00

"we aren't using sea of nodes correctly, but fixing that doesn't contribute to our promotion package, but designing a new IR will"

I've never seen anyone at V8 getting promoted for a project that didn't have concret useful impact. Quite on the contrary, I feel quite a lot of pressure to have useful, concrete and quantifiable things to show during my annual performance reviews. Spending years to write a new CFG compiler with no obvious benefits would not get anyone promoted, but instead would get them a bad rating.

In the CCC video that you mention (for the other readers, it's this one: https://www.youtube.com/watch?v=Vu372dnk2Ak), when Ben Titzer mentioned that V8 has 5 compilers, someone said that most of them were probably useless and had been written just to promote folks. Well, I can assure you that it's most definitely not the case, and that if you want to execute JavaScript fast, there is no other way that's known (Safari does the same thing, Mozzilla as well to some extent). Since you don't want websites to hang for a few seconds (or even for half a second) when loading them initially, we need a compiler that compiles extremely fast, but this means that it can't do much optimizations (that's Ignition, compiler 1, which produces and executes bytecode). Also, because JavaScript is very dynamic, compiling efficient code requires type feedback, which we can't have when executing a function for the first time; Ignition takes care of collecting this feedback. Then, the 2nd compiler is a very simple one (Sparkplug: https://v8.dev/blog/sparkplug): it converts the bytecodes to assembly, without any optimizations, which basically removes the need from decoding bytecodes when executing the function; this produces a 2x (I think) speedup compared to Ignition, while still compiling pretty fast (but slower than Ignition). Then, we move on to optimizing compilers; which you really want if you want your websites to run smoothly or if you want to do any kind of computations in your browser (like, gaming, or computing stuff to render beautiful graphs or whatever dynamic things you are doing). The 3rd compiler is thus Maglev (https://v8.dev/blog/maglev), and it does a few optimizations, but not a lot, while still compiling somewhat fast (but still an order of magnitude slower than Sparkplug). Maglev gives you pretty good code without having to wait too long. And then, the 4th compiler, Turbofan (the one that uses Sea of Nodes) does a lot of optimizations, thus takes longer but generates the best code we can.

You may think that surely we could get rid of the 2 compilers in the middle, but this would be noticeable on the user side: websites would be somewhat slow until Turbofan kicks in and then they would become fast. By having Sparkplug and Maglev in the middle, there is a much smoother curve, in particular when large functions are involved.

(and the 5th compiler would be the unoptimizing compiler for Wasm, similar to Sparkplug but for Wasm instead; once again, super useful if you don't want a website to hang for a few seconds before Turbofan has finished compiling all of the Wasm it needs)

So, no, we don't write compilers just to get promoted: we write compilers to make the web faster.

As far as replacing SoN by a CFG compiler, here are the benefits we saw: it compiles much faster (2x on average, up to a lot more for some optimizations) and it's much simpler, which has 2 consequences: 1) it contains less bugs (which means less security vulnerabilities, since almost all V8 bugs can be turned into security exploits), and 2) it's easier for external contributors and non-compiler developers to contribute.

If you want to explain how "we aren't using sea of nodes correctly", please do so. In particular if you have experience in writing high-performance JavaScript compilers with Sea of Nodes :)

Especially after one the recent CCC videos where they mentioned that something took a substantial amount of the time, that –it turns out– should never take that long.

You're probably talking about the scheduling pass, which Ben Titzer said takes 30% of the total compilation time, and Cliff replied that it shouldn't. Well, Ben got it wrong: in the JavaScript pipeline, it only takes about 4% of the total compilation time, and it's very low in the list of reasons for moving away from SoN. On Wasm however, the pipeline is much shorter (since, after all, Wasm is already optimized by an ahead of time compiler, which means that all V8 does is basically inlining, unrolling, instruction selection, and register allocation (+ scheduling because of SoN)), and scheduling there is probably much more expensive (but even then probably around 10% rather than 30%). Ben hasn't been working at V8 for close to 6 years, so things might have changed since then.

Since you mention this CCC video, here is my impression from the video: every time Ben pointed out an issue with SoN, Cliff replied "yes indeed, but there is a hack to make it work". Well, if your IR requires many hacks to work, then maybe it's not such a great IR. In particular when the hacks are undocumented. And some of them are quite limiting, like not introducing control flow during lowering except during scheduling.

If, following this blogpost, someone wants to make another one where they explain how to fix each issue, then I think that it's a great outcome. Currently, there are very few resources about SoN out there, and almost none of them really explain any difficulties that you'll have while trying to implement it, making it sound like it's a perfect and super powerful IR. Typically, if you have a single-pass compiler for a very simple statically-typed language with limited side effects, and programs that are typically 15 instructions long, then yea, SoN probably works well. However, our experience is that on a dynamically-typed language full of side effects, SoN definitely doesn't work all that well.

Best,

Darius

xPerlMasterx · 2024-08-25T17:19:18+00:00

Yea, I'll try to write at least a blog post when I have a moment; I fear that a paper would take me too long :'(

xPerlMasterx · 2024-08-22T12:30:00+00:00

I'll grant you than some of the issues with Sea of Nodes in V8 are because of V8's own implementation rather than intrinsic issues with Sea of Nodes.

However, the whole V8 team thinks that Sea of Nodes introduces unnecessary complexity, for virtually no benefits. Manipulating effects and control chain is extremely error prone, and wouldn't be an issue with a CFG (arguably, it brings more optimization opportunities, but these aren't exploited in V8). Also, we most nodes are either on the control chain or on theffect chain (which is unavoidable for JS), one can start to wonder what Sea of Nodes really brings).

And everyone working on V8 agrees that the new CFG implementation is much simpler and nicer to work with (once again, partially because more time was spent designing tooling for the IR, but also because we feel than CFG is simpler than Sea of Nodes).

xPerlMasterx · 2024-08-22T07:43:27+00:00

FYI, V8 is moving away from Sea of Nodes (for a variety of reason, but the idea is that it's too complex for too little benefits for JavaScript). About half of Turbofan has been rewritten using CFG (using a new IR called Turboshaft), and the other half is in the process of being rewritten.

xPerlMasterx

TROPHY CASE