{"article":{"slug":"ssa-from-bytecode-imperative-pearl","title":"SSA from bytecode: imperative pearl","subtitle":null,"summary":"Max Bernstein explains how ZJIT converts CRuby's stack-based YARV bytecode into a high-level SSA IR, distilling the approach behind its large add_iseq_to_hir function into a small imperative algorithm, with references to prior compiler work.","content_type":"tutorial","language":"en","canonical_url":"https://bernsteinbear.com/blog/ssa-bytecode/","author":{"name":"Max Bernstein","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Max Bernstein's blog","url":"https://bernsteinbear.com/","listing_slug":null,"listing":null},"topics":[{"name":"programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"open-source","slug":"open-source","url":"https://listedarticles.com/topics/open-source"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":1002,"reading_minutes":4,"published_at":"2026-11-12T00:00:00.000Z","added_at":"2026-11-13T11:13:56.603Z","updated_at":"2026-11-13T11:13:56.603Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/ssa-from-bytecode-imperative-pearl","markdown_url":"https://listedarticles.com/articles/ssa-from-bytecode-imperative-pearl.md","example":false,"citation":"Max Bernstein, Max Bernstein's blog. \"SSA from bytecode: imperative pearl.\" 12 Nov 2026. https://bernsteinbear.com/blog/ssa-bytecode/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://bernsteinbear.com/blog/ssa-bytecode/"},"body_markdown":"# SSA from bytecode: imperative pearl\n\n*November 12, 2026*\n\nUfuk made a comment that he enjoyed my description of SSA from bytecode in\n[Aaron’s livestream with me](https://www.youtube.com/watch?v=h9_FyHYUhww).\nWhile filming the livestream—an intro to ZJIT internals—I got a little\nnervous that people would shy away from our 1900 line `add_iseq_to_hir`\nfunction. This function is responsible for converting CRuby’s stack based\nbytecode for the YARV virtual machine into a high-level SSA IR for ZJIT to\nanalyze and optimize.\n\nIt takes bytecode that looks roughly like this:\n\n```\npush 3\npush 4\nadd\n```\n\ninto SSA form, giving an SSA value to each stack slot, ish:\n\n```\nv0 = const 3\nv1 = const 4\nv2 = add v0, v1\n```\n\nWhile our function is 2000 lines long because it handles a lot of specific\nopcodes and weird facts about those opcodes, the core of it is small. Here is\nthat core.\n\n## What if a stack, but virtual\n\nThe bytecode assumes that when it is run, it will be operating on a stack. This\nmeans that every opcode has implicit stack inputs and implicit stack outputs.\n\n`push 3`, for example, has empty stack inputs and one stack output. By\ncontrast, `add` has two stack inputs and one stack output. Some instructions\nsuch as `nop` are empty on both counts. As far as I can tell, all instructions\nhave *at most* one output.\n\nThese counts are known when looking at the bytecode: we can reason statically\nabout how many inputs and outputs each opcode has. Some are variadic, such as\n`send` (call), but they come bearing an argument count in a nearby field.\n\nLet’s model how the first example runs on the VM by adding a view of the stack\nafter each instruction has run. The stack will be displayed as a list\nleft-to-right, where the left is the bottom and the right is the top.\n\n```\n       ; []\npush 3 ; [3]\npush 4 ; [3, 4]\nadd    ; [7]\n```\n\nBecause the input counts and output counts are static, when ZJIT reads through\nthe bytecode, we can run the stack parts of it at compile-time.\n\nWe don’t *really* need to know what the values on the stack are; we only need\nto keep track of where they came from. And when I say “where they came from”, I\nmean that we name each instruction and refer to its output by the instruction’s\nname. I like how the paper [Design of the Java HotSpot™ Client Compiler for\nJava 6](https://bernsteinbear.com/assets/img/design-hotspot-client-compiler.pdf) (PDF) puts it:\n\n> An instruction that loads or computes a value represents both the operation\n> and its result, so that operands can be represented as pointers to previous\n> instructions.\n\nHere is what that looks like for the above example. In addition to the run-time\nstack, I will also write the SSA instruction to indicate that we are generating\nnew code:\n\n```\n       ; []\npush 3 ; v0 = const 3\n       ; [v0]\npush 4 ; v1 = const 4\n       ; [v0, v1]\nadd    ; v2 = add v0, v1\n       ; [v2]\n```\n\nThis is neat! We have transformed stack based bytecode to a form where\ninstructions can directly reference their inputs. You may notice, though, that\n`v0` and `v2` both end up in the same stack slot (the first element). This is\nwhy I said earlier “giving an SSA value to each stack slot, *ish*”.\n\nThe difference between the two is *time*. `v0` was in the operand stack at one\npoint but now `v2` is. This is kind of why I describe SSA as “pushing time\nthrough the IR”.\n\nAlright, let’s implement it.\n\n## Implementation\n\nWe’ll start with the real (“concrete”) interpreter of the bytecode, which\noperates on a value stack. This gives you a simplified version of how Ruby\ninternals work:\n\n```\ndef interpret(bytecode)\n  stack = []\n  bytecode.each do |op|\n    case op\n    in [:push, c]\n      stack << c\n    in [:add]\n      right = stack.pop\n      left = stack.pop\n      stack << left + right\n    else\n      raise \"Unknown op #{op}\"\n    end\n  end\n  stack.pop\nend\n\nbytecode = [\n  [:push, 3],\n  [:push, 4],\n  [:add],\n]\n\nputs interpret(bytecode)  # 7\n```\n\nNow let’s look at the abstract intepreter, which by contrast operates on an SSA\nstack. You can see that they are quite similar looking:\n\n```\ndef to_ssa(bytecode)\n  code = []\n  stack = []\n  bytecode.each do |op|\n    case op\n    in [:push, c]\n      name = :\"v#{code.length}\"\n      code << \"#{name} = const #{c}\"\n      stack << name\n    in [:add]\n      name = :\"v#{code.length}\"\n      right = stack.pop\n      left = stack.pop\n      code << \"#{name} = add #{left}, #{right}\"\n      stack << name\n    else\n      raise \"Unknown op #{op}\"\n    end\n  end\n  code\nend\n\nbytecode = [\n  [:push, 3],\n  [:push, 4],\n  [:add],\n]\n\nputs to_ssa(bytecode)\n# v0 = const 3\n# v1 = const 4\n# v2 = add v0, v1\n```\n\nThe `name`s could be anything as long as they are unique. For simplicity and\nease of reading, I picked the length of the `code` array, which grows\nmonotonically. This is an array/vector-based analogue to the real-pointer\napproach in the HotSpot paper from above.\n\nTa da! You have built a small abstract interpreter.\n\nNow to make it global (to handle control flow) you need some kind of\ninter-basic-block data flow mechanism such as phi nodes or basic block\nparameters. Perhaps more on that in another post, but for now, you may enjoy\n[my collection of other people’s writing](https://bernsteinbear.com/blog/ssa/) about that.\n\n## Conclusion\n\nI originally wanted to title this blog post “you could have invented abstract\ninterpretation” or similar, but I decided that I find those titles obnoxious\nbecause they assume the reader is or thinks of themself as unintelligent.\nPerhaps *we* could have invented it.\n\nThe title is a bit of a tongue-in-cheek nod to the “functional pearl” papers\nthat I always felt should be simpler than they are but leave me confused. And\nalso kind of a nicer nod to [SSA is Functional\nProgramming](https://bernsteinbear.com/img/appel-basic-block-arguments.pdf) (PDF) by Andrew Appel.\n\n## References\n\n- [A New Approach to Forth Native Code Generation](https://bernsteinbear.com/assets/img/ertl92.pdf) (PDF, 1992)\n- [Java Bytecode to Native Code Translation: The Caffeine Prototype and Preliminary Results](https://bernsteinbear.com/assets/img/caffeine.pdf) (PDF, 1996) section 3.2\n- [CACAO - A 64 bit JavaVM Just-in-Time Compiler](https://bernsteinbear.com/assets/img/cacao.pdf) (PDF, 1997) section 3\n- [Fast, Effective Code Generation in a Just-In-Time Java Compiler](https://dl.acm.org/doi/pdf/10.1145/277650.277740) (PDF, 1998) section 2.2, the mimic stack\n- [The Jalapeño Dynamic Optimizing Compiler for Java™](https://dl.acm.org/doi/pdf/10.1145/304065.304113) (PDF, 1999)\n- [Dynamic optimization through the use of automatic runtime specialization](https://dspace.mit.edu/entities/publication/6896835b-c46b-4ebb-8ecc-1f5cbac364b5) (1999) section 3.4\n\n---\n","body_html":"<h1 id=\"ssa-from-bytecode-imperative-pearl\">SSA from bytecode: imperative pearl</h1>\n<p><em>November 12, 2026</em></p>\n<p>Ufuk made a comment that he enjoyed my description of SSA from bytecode in\n<a href=\"https://www.youtube.com/watch?v=h9_FyHYUhww\" rel=\"nofollow ugc noopener\">Aaron’s livestream with me</a>.\nWhile filming the livestream—an intro to ZJIT internals—I got a little\nnervous that people would shy away from our 1900 line <code>add_iseq_to_hir</code>\nfunction. This function is responsible for converting CRuby’s stack based\nbytecode for the YARV virtual machine into a high-level SSA IR for ZJIT to\nanalyze and optimize.</p>\n<p>It takes bytecode that looks roughly like this:</p>\n<pre><code>push 3\npush 4\nadd</code></pre>\n<p>into SSA form, giving an SSA value to each stack slot, ish:</p>\n<pre><code>v0 = const 3\nv1 = const 4\nv2 = add v0, v1</code></pre>\n<p>While our function is 2000 lines long because it handles a lot of specific\nopcodes and weird facts about those opcodes, the core of it is small. Here is\nthat core.</p>\n<h2 id=\"what-if-a-stack-but-virtual\">What if a stack, but virtual</h2>\n<p>The bytecode assumes that when it is run, it will be operating on a stack. This\nmeans that every opcode has implicit stack inputs and implicit stack outputs.</p>\n<p><code>push 3</code>, for example, has empty stack inputs and one stack output. By\ncontrast, <code>add</code> has two stack inputs and one stack output. Some instructions\nsuch as <code>nop</code> are empty on both counts. As far as I can tell, all instructions\nhave <em>at most</em> one output.</p>\n<p>These counts are known when looking at the bytecode: we can reason statically\nabout how many inputs and outputs each opcode has. Some are variadic, such as\n<code>send</code> (call), but they come bearing an argument count in a nearby field.</p>\n<p>Let’s model how the first example runs on the VM by adding a view of the stack\nafter each instruction has run. The stack will be displayed as a list\nleft-to-right, where the left is the bottom and the right is the top.</p>\n<pre><code>       ; []\npush 3 ; [3]\npush 4 ; [3, 4]\nadd    ; [7]</code></pre>\n<p>Because the input counts and output counts are static, when ZJIT reads through\nthe bytecode, we can run the stack parts of it at compile-time.</p>\n<p>We don’t <em>really</em> need to know what the values on the stack are; we only need\nto keep track of where they came from. And when I say “where they came from”, I\nmean that we name each instruction and refer to its output by the instruction’s\nname. I like how the paper <a href=\"https://bernsteinbear.com/assets/img/design-hotspot-client-compiler.pdf\" rel=\"nofollow ugc noopener\">Design of the Java HotSpot™ Client Compiler for\nJava 6</a> (PDF) puts it:</p>\n<blockquote><p>An instruction that loads or computes a value represents both the operation\nand its result, so that operands can be represented as pointers to previous\ninstructions.</p></blockquote>\n<p>Here is what that looks like for the above example. In addition to the run-time\nstack, I will also write the SSA instruction to indicate that we are generating\nnew code:</p>\n<pre><code>       ; []\npush 3 ; v0 = const 3\n       ; [v0]\npush 4 ; v1 = const 4\n       ; [v0, v1]\nadd    ; v2 = add v0, v1\n       ; [v2]</code></pre>\n<p>This is neat! We have transformed stack based bytecode to a form where\ninstructions can directly reference their inputs. You may notice, though, that\n<code>v0</code> and <code>v2</code> both end up in the same stack slot (the first element). This is\nwhy I said earlier “giving an SSA value to each stack slot, <em>ish</em>”.</p>\n<p>The difference between the two is <em>time</em>. <code>v0</code> was in the operand stack at one\npoint but now <code>v2</code> is. This is kind of why I describe SSA as “pushing time\nthrough the IR”.</p>\n<p>Alright, let’s implement it.</p>\n<h2 id=\"implementation\">Implementation</h2>\n<p>We’ll start with the real (“concrete”) interpreter of the bytecode, which\noperates on a value stack. This gives you a simplified version of how Ruby\ninternals work:</p>\n<pre><code>def interpret(bytecode)\n  stack = []\n  bytecode.each do |op|\n    case op\n    in [:push, c]\n      stack &lt;&lt; c\n    in [:add]\n      right = stack.pop\n      left = stack.pop\n      stack &lt;&lt; left + right\n    else\n      raise &quot;Unknown op #{op}&quot;\n    end\n  end\n  stack.pop\nend\n\nbytecode = [\n  [:push, 3],\n  [:push, 4],\n  [:add],\n]\n\nputs interpret(bytecode)  # 7</code></pre>\n<p>Now let’s look at the abstract intepreter, which by contrast operates on an SSA\nstack. You can see that they are quite similar looking:</p>\n<pre><code>def to_ssa(bytecode)\n  code = []\n  stack = []\n  bytecode.each do |op|\n    case op\n    in [:push, c]\n      name = :&quot;v#{code.length}&quot;\n      code &lt;&lt; &quot;#{name} = const #{c}&quot;\n      stack &lt;&lt; name\n    in [:add]\n      name = :&quot;v#{code.length}&quot;\n      right = stack.pop\n      left = stack.pop\n      code &lt;&lt; &quot;#{name} = add #{left}, #{right}&quot;\n      stack &lt;&lt; name\n    else\n      raise &quot;Unknown op #{op}&quot;\n    end\n  end\n  code\nend\n\nbytecode = [\n  [:push, 3],\n  [:push, 4],\n  [:add],\n]\n\nputs to_ssa(bytecode)\n# v0 = const 3\n# v1 = const 4\n# v2 = add v0, v1</code></pre>\n<p>The <code>name</code>s could be anything as long as they are unique. For simplicity and\nease of reading, I picked the length of the <code>code</code> array, which grows\nmonotonically. This is an array/vector-based analogue to the real-pointer\napproach in the HotSpot paper from above.</p>\n<p>Ta da! You have built a small abstract interpreter.</p>\n<p>Now to make it global (to handle control flow) you need some kind of\ninter-basic-block data flow mechanism such as phi nodes or basic block\nparameters. Perhaps more on that in another post, but for now, you may enjoy\n<a href=\"https://bernsteinbear.com/blog/ssa/\" rel=\"nofollow ugc noopener\">my collection of other people’s writing</a> about that.</p>\n<h2 id=\"conclusion\">Conclusion</h2>\n<p>I originally wanted to title this blog post “you could have invented abstract\ninterpretation” or similar, but I decided that I find those titles obnoxious\nbecause they assume the reader is or thinks of themself as unintelligent.\nPerhaps <em>we</em> could have invented it.</p>\n<p>The title is a bit of a tongue-in-cheek nod to the “functional pearl” papers\nthat I always felt should be simpler than they are but leave me confused. And\nalso kind of a nicer nod to <a href=\"https://bernsteinbear.com/img/appel-basic-block-arguments.pdf\" rel=\"nofollow ugc noopener\">SSA is Functional\nProgramming</a> (PDF) by Andrew Appel.</p>\n<h2 id=\"references\">References</h2>\n<ul><li><a href=\"https://bernsteinbear.com/assets/img/ertl92.pdf\" rel=\"nofollow ugc noopener\">A New Approach to Forth Native Code Generation</a> (PDF, 1992)</li><li><a href=\"https://bernsteinbear.com/assets/img/caffeine.pdf\" rel=\"nofollow ugc noopener\">Java Bytecode to Native Code Translation: The Caffeine Prototype and Preliminary Results</a> (PDF, 1996) section 3.2</li><li><a href=\"https://bernsteinbear.com/assets/img/cacao.pdf\" rel=\"nofollow ugc noopener\">CACAO - A 64 bit JavaVM Just-in-Time Compiler</a> (PDF, 1997) section 3</li><li><a href=\"https://dl.acm.org/doi/pdf/10.1145/277650.277740\" rel=\"nofollow ugc noopener\">Fast, Effective Code Generation in a Just-In-Time Java Compiler</a> (PDF, 1998) section 2.2, the mimic stack</li><li><a href=\"https://dl.acm.org/doi/pdf/10.1145/304065.304113\" rel=\"nofollow ugc noopener\">The Jalapeño Dynamic Optimizing Compiler for Java™</a> (PDF, 1999)</li><li><a href=\"https://dspace.mit.edu/entities/publication/6896835b-c46b-4ebb-8ecc-1f5cbac364b5\" rel=\"nofollow ugc noopener\">Dynamic optimization through the use of automatic runtime specialization</a> (1999) section 3.4</li></ul>\n<hr />","headings":[{"level":1,"text":"SSA from bytecode: imperative pearl","id":"ssa-from-bytecode-imperative-pearl"},{"level":2,"text":"What if a stack, but virtual","id":"what-if-a-stack-but-virtual"},{"level":2,"text":"Implementation","id":"implementation"},{"level":2,"text":"Conclusion","id":"conclusion"},{"level":2,"text":"References","id":"references"}]}}