MX Reveal: #19 - ι: Transpiling LLVM to a high-level language

<h2 id="iota-transpiling-llvm-to-a-high-level-language">Iota: Transpiling LLVM to a high-level language</h2>


<h1 id="why">?!?!WHY!?!?</h1>


<h2 id="created-by-froggey-as-part-of-the-mezzano-project">Created by froggey as part of the Mezzano project</h2>
<ul>
<li>Demo 1: 2015</li>
<li>Demo 5: 2020</li>
<li>Latest Commit at time of writing: 2025-05-01</li>
</ul>

<h1 id="what-is-mezanno">What is <a href="https://github.com/froggey/Mezzano">Mezanno</a>?</h1>

<p>Mezzano is a high-level language operating system, meaning no ELF binaries, the
only thing it runs is a given high-level language. But what if we wish to run
something written for a conventional Unix system? I dunno, maybe DOOM!!! If it
doesn't run DOOM is it even a viable piece of tech?</p>
<p><a href="https://github.com/froggey/Mezzano/blob/master/doc/quickstart.md">Blinkenlights</a>:</p>
<ul>
<li><span style="color:green"><strong>Green</strong></span>: Disk read in progress</li>
<li><span style="color:red"><strong>Red</strong></span>: Disk write in progress</li>
<li><span style="color:purple"><strong>Purple</strong></span>: GC in progress</li>
<li><span style="color:cyan"><strong>Cyan</strong></span>: Activity, system is not idle</li>
<li><span style="color:yellow"><strong>Yellow</strong></span>: Snapshot in progress</li>
<li><span style="color:brown"><strong>Brown</strong></span>: Page fault being serviced</li>
<li><span style="color:lightgreen"><strong>Light Green</strong></span>: Network activity</li>
</ul>
 <svg aria-roledescription="flowchart-v2" role="graphics-document document" viewBox="0 0 1010.453125 269" height="269" class="flowchart" xmlns="http://www.w3.org/2000/svg" width="1010.453125" id="container"><style>#container{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#000000;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#container .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#container .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#container .error-icon{fill:#552222;}#container .error-text{fill:#552222;stroke:#552222;}#container .edge-thickness-normal{stroke-width:1px;}#container .edge-thickness-thick{stroke-width:3.5px;}#container .edge-pattern-solid{stroke-dasharray:0;}#container .edge-thickness-invisible{stroke-width:0;fill:none;}#container .edge-pattern-dashed{stroke-dasharray:3;}#container .edge-pattern-dotted{stroke-dasharray:2;}#container .marker{fill:#666;stroke:#666;}#container .marker.cross{stroke:#666;}#container svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#container p{margin:0;}#container .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#000000;}#container .cluster-label text{fill:#333;}#container .cluster-label span{color:#333;}#container .cluster-label span p{background-color:transparent;}#container .label text,#container span{fill:#000000;color:#000000;}#container .node rect,#container .node circle,#container .node ellipse,#container .node polygon,#container .node path{fill:#eee;stroke:#999;stroke-width:1px;}#container .rough-node .label text,#container .node .label text,#container .image-shape .label,#container .icon-shape .label{text-anchor:middle;}#container .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#container .rough-node .label,#container .node .label,#container .image-shape .label,#container .icon-shape .label{text-align:center;}#container .node.clickable{cursor:pointer;}#container .root .anchor path{fill:#666!important;stroke-width:0;stroke:#666;}#container .arrowheadPath{fill:#333333;}#container .edgePath .path{stroke:#666;stroke-width:2.0px;}#container .flowchart-link{stroke:#666;fill:none;}#container .edgeLabel{background-color:white;text-align:center;}#container .edgeLabel p{background-color:white;}#container .edgeLabel rect{opacity:0.5;background-color:white;fill:white;}#container .labelBkg{background-color:rgba(255, 255, 255, 0.5);}#container .cluster rect{fill:hsl(0, 0%, 98.9215686275%);stroke:#707070;stroke-width:1px;}#container .cluster text{fill:#333;}#container .cluster span{color:#333;}#container div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(-160, 0%, 93.3333333333%);border:1px solid #707070;border-radius:2px;pointer-events:none;z-index:100;}#container .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#000000;}#container rect.text{fill:none;stroke-width:0;}#container .icon-shape,#container .image-shape{background-color:white;text-align:center;}#container .icon-shape p,#container .image-shape p{background-color:white;padding:2px;}#container .icon-shape rect,#container .image-shape rect{opacity:0.5;background-color:white;fill:white;}#container :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}</style><g><marker orient="auto" markerHeight="8" markerWidth="8" markerUnits="userSpaceOnUse" refY="5" refX="5" viewBox="0 0 10 10" class="marker flowchart-v2" id="container_flowchart-v2-pointEnd"><path style="stroke-width: 1; stroke-dasharray: 1, 0;" class="arrowMarkerPath" d="M 0 0 L 10 5 L 0 10 z"></path></marker><marker orient="auto" markerHeight="8" markerWidth="8" markerUnits="userSpaceOnUse" refY="5" refX="4.5" viewBox="0 0 10 10" class="marker flowchart-v2" id="container_flowchart-v2-pointStart"><path style="stroke-width: 1; stroke-dasharray: 1, 0;" class="arrowMarkerPath" d="M 0 5 L 10 10 L 10 0 z"></path></marker><marker orient="auto" markerHeight="11" markerWidth="11" markerUnits="userSpaceOnUse" refY="5" refX="11" viewBox="0 0 10 10" class="marker flowchart-v2" id="container_flowchart-v2-circleEnd"><circle style="stroke-width: 1; stroke-dasharray: 1, 0;" class="arrowMarkerPath" r="5" cy="5" cx="5"></circle></marker><marker orient="auto" markerHeight="11" markerWidth="11" markerUnits="userSpaceOnUse" refY="5" refX="-1" viewBox="0 0 10 10" class="marker flowchart-v2" id="container_flowchart-v2-circleStart"><circle style="stroke-width: 1; stroke-dasharray: 1, 0;" class="arrowMarkerPath" r="5" cy="5" cx="5"></circle></marker><marker orient="auto" markerHeight="11" markerWidth="11" markerUnits="userSpaceOnUse" refY="5.2" refX="12" viewBox="0 0 11 11" class="marker cross flowchart-v2" id="container_flowchart-v2-crossEnd"><path style="stroke-width: 2; stroke-dasharray: 1, 0;" class="arrowMarkerPath" d="M 1,1 l 9,9 M 10,1 l -9,9"></path></marker><marker orient="auto" markerHeight="11" markerWidth="11" markerUnits="userSpaceOnUse" refY="5.2" refX="-1" viewBox="0 0 11 11" class="marker cross flowchart-v2" id="container_flowchart-v2-crossStart"><path style="stroke-width: 2; stroke-dasharray: 1, 0;" class="arrowMarkerPath" d="M 1,1 l 9,9 M 10,1 l -9,9"></path></marker><g class="root"><g class="clusters"><g data-look="classic" id="subGraph0" class="cluster"><rect height="140" width="769.921875" y="121" x="232.53125" style=""></rect><g transform="translate(572.7578125, 121)" class="cluster-label"><foreignObject height="24" width="89.46875"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" xmlns="http://www.w3.org/1999/xhtml"><span class="nodeLabel"><p>Managed OS</p></span></div></foreignObject></g></g></g><g class="edgePaths"><path marker-end="url(#container_flowchart-v2-pointEnd)" style="" class="edge-thickness-normal edge-pattern-solid edge-thickness-normal edge-pattern-solid flowchart-link" id="L_HLC_SC_0" d="M182.531,199L186.698,199C190.865,199,199.198,199,207.531,199C215.865,199,224.198,199,241.061,199C257.924,199,283.318,199,296.014,199L308.711,199"></path><path marker-end="url(#container_flowchart-v2-crossEnd)" style="" class="edge-thickness-normal edge-pattern-solid edge-thickness-normal edge-pattern-solid flowchart-link" id="L_INS_AS_0" d="M451.73,86L472.581,98.667C493.432,111.333,535.134,136.667,565.869,150.816C596.604,164.966,616.372,167.932,626.257,169.416L636.141,170.899"></path><path marker-end="url(#container_flowchart-v2-pointEnd)" style="" class="edge-thickness-normal edge-pattern-solid edge-thickness-normal edge-pattern-solid flowchart-link" id="L_SC_AS_0" d="M462.352,199L481.432,199C500.513,199,538.674,199,566.977,197.946C595.279,196.891,613.723,194.783,622.945,193.729L632.167,192.674"></path><path marker-end="url(#container_flowchart-v2-pointEnd)" style="" class="edge-thickness-normal edge-pattern-solid edge-thickness-normal edge-pattern-solid flowchart-link" id="L_AS_OS_0" d="M797.438,183L805.789,183C814.141,183,830.844,183,846.88,183C862.917,183,878.286,183,885.971,183L893.656,183"></path></g><g class="edgeLabels"><g class="edgeLabel"><g transform="translate(0, 0)" class="label"><foreignObject height="0" width="0"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" class="labelBkg" xmlns="http://www.w3.org/1999/xhtml"><span class="edgeLabel"></span></div></foreignObject></g></g><g class="edgeLabel"><g transform="translate(0, 0)" class="label"><foreignObject height="0" width="0"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" class="labelBkg" xmlns="http://www.w3.org/1999/xhtml"><span class="edgeLabel"></span></div></foreignObject></g></g><g transform="translate(576.8359375, 199)" class="edgeLabel"><g transform="translate(-34.3046875, -12)" class="label"><foreignObject height="24" width="68.609375"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" class="labelBkg" xmlns="http://www.w3.org/1999/xhtml"><span class="edgeLabel"><p>Compiled</p></span></div></foreignObject></g></g><g transform="translate(847.546875, 183)" class="edgeLabel"><g transform="translate(-25.109375, -12)" class="label"><foreignObject height="24" width="50.21875"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" class="labelBkg" xmlns="http://www.w3.org/1999/xhtml"><span class="edgeLabel"><p>Run By</p></span></div></foreignObject></g></g></g><g class="nodes"><g transform="translate(387.53125, 199)" id="flowchart-SC-0" class="node default"><rect height="54" width="149.640625" y="-27" x="-74.8203125" style="" class="basic label-container"></rect><g transform="translate(-44.8203125, -12)" style="" class="label"><rect></rect><foreignObject height="24" width="89.640625"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" xmlns="http://www.w3.org/1999/xhtml"><span class="nodeLabel"><p>Source Code</p></span></div></foreignObject></g></g><g transform="translate(716.7890625, 183)" id="flowchart-AS-1" class="node default"><rect height="54" width="161.296875" y="-27" x="-80.6484375" style="" class="basic label-container"></rect><g transform="translate(-50.6484375, -12)" style="" class="label"><rect></rect><foreignObject height="24" width="101.296875"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" xmlns="http://www.w3.org/1999/xhtml"><span class="nodeLabel"><p>Machine Code</p></span></div></foreignObject></g></g><g transform="translate(95.265625, 199)" id="flowchart-HLC-2" class="node default"><rect height="54" width="174.53125" y="-27" x="-87.265625" style="" class="basic label-container"></rect><g transform="translate(-57.265625, -12)" style="" class="label"><rect></rect><foreignObject height="24" width="114.53125"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" xmlns="http://www.w3.org/1999/xhtml"><span class="nodeLabel"><p>High-level Code</p></span></div></foreignObject></g></g><g transform="translate(387.53125, 47)" id="flowchart-INS-5" class="node default"><rect height="78" width="260" y="-39" x="-130" style="" class="basic label-container"></rect><g transform="translate(-100, -24)" style="" class="label"><rect></rect><foreignObject height="48" width="200"><div style="display: table; white-space: break-spaces; line-height: 1.5; max-width: 200px; text-align: center; width: 200px;" xmlns="http://www.w3.org/1999/xhtml"><span class="nodeLabel"><p>Cannot be Inserted from the outside</p></span></div></foreignObject></g></g><g transform="translate(937.5546875, 183)" id="flowchart-OS-10" class="node default"><rect height="54" width="79.796875" y="-27" x="-39.8984375" style="" class="basic label-container"></rect><g transform="translate(-9.8984375, -12)" style="" class="label"><rect></rect><foreignObject height="24" width="19.796875"><div style="display: table-cell; white-space: nowrap; line-height: 1.5; max-width: 200px; text-align: center;" xmlns="http://www.w3.org/1999/xhtml"><span class="nodeLabel"><p>OS</p></span></div></foreignObject></g></g></g></g></g></svg>
<p>Hope you can all compile mermaid in your heads... no? Well nevermind let me
fetch the blackboard.</p>
<p>Python to python OS</p>

<h1 id="but-why">But why?</h1>
<ul>
<li>Easier to compile to</li>
<li>Memory-safe</li>
<li>High-level ABI</li>
<li>Extremely cheap IPC
<ul>
<li>Global Address Space</li>
</ul>
</li>
<li>Higher-level errors (conditions and segfaults)</li>
<li>Safer???</li>
</ul>

<h1 id="iota">Iota</h1>

<h2 id="what-is-an-instruction">What is an instruction?</h2>

<pre><code class="language-llvm">%x = add i32 1, %y
</code></pre>

<h2 id="it-got-inputs">It got inputs</h2>
<pre><code class="language-llvm">%x = add i32 >>1, %y<<
</code></pre>

<h2 id="it-got-an-output">It got an output</h2>
<pre><code class="language-llvm">>>%x<< = add i32 1, %y
</code></pre>

<h2 id="it-got-types">It got types</h2>
<pre><code class="language-llvm">%x = add >>i32<< 1, %y
</code></pre>

<h2 id="it-s-basically-a-function">??? It's basically a function ???</h2>
<p><code>@llvm.sqrt.f32 == math.sqrt</code></p>

<p><img src="https://images.squarespace-cdn.com/content/v1/53ae3013e4b0a141bca21c9f/1409962221681-H8BI0BY0UE3GHE79A80L/close+enough.jpg" alt="Close Enough stick meme" /></p>

<h1 id="not-really">Not really.</h1>

<h1 id="but-still">But still</h1>

<h1 id="iota-the-transpiler">Iota the transpiler</h1>

<h3 id="c-llvm-bitcode-lisp">C ➢ LLVM bitcode ➢ Lisp</h3>

<pre><code class="language-c">int zoo(int x, int y) {
  return x + y;
}
</code></pre>
<pre><code class="language-llvm">define i32 @zoo(i32 %x, i32 %y) #0 {
  %add = add nsw i32 %y, %x
  ret i32 %add
}
</code></pre>
<pre><code class="language-lisp">(define-llvm-function |zoo| (|x.0| |y.1|)
  (add.i32 |x.0| |y.1|))
</code></pre>

<pre><code class="language-lisp" data-line-numbers="|1|3-4|5,7|6">(define-llvm-function |zoo| ((|x.0| |y.1|) :need-frame-pointer nil)
  (let ()
    (declare (type (unsigned-byte 32) |x.0|)
             (type (unsigned-byte 32) |y.1|))
    (block nil
      (tagbody
         (return (add.i32 |x.0| |y.1|))))))
</code></pre>

<pre><code class="language-lisp">(defstruct (llvm-context
			 (:constructor make-llvm-context-1))
	(stack-pointer 0 :type (unsigned-byte 64))
	(memory (error "memory not supplied") :type octet-vector)
	entry-point
	(setjmp-stack
		(make-array 8 :adjustable t :fill-pointer 0)))
</code></pre>

<h3 id="initial-memory">Initial memory</h3>
<pre><code class="language-lisp">(defun make-context (&rest personality-initargs)
  (make-llvm-context
   2097152 ;; data start
   #.(make-array 2320
	   :element-type '(unsigned-byte 8)
	   :initial-contents
	   '(0 9 32 0 0 0 0 0
		 56 0 32 0 56 0 32
		 72 101 108 108 111 ...))
   '|_start|))
</code></pre>

<h1 id="control-flow">Control flow</h1>

<pre><code class="language-c">int fib(int n) {
  if (n <= 1)
    return 1;
  return n * fib(n - 1);
}
</code></pre>

<pre><code class="language-llvm">define i32 @fib(i32 %n) #0 {
entry:
  %retval = alloca i32, align 4
  %n.addr = alloca i32, align 4
  store i32 %n, i32* %n.addr, align 4
  %0 = load i32, i32* %n.addr, align 4
  %cmp = icmp sle i32 %0, 1
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  store i32 1, i32* %retval
  br label %return

if.end:                                           ; preds = %entry
  %1 = load i32, i32* %n.addr, align 4
  %2 = load i32, i32* %n.addr, align 4
  %sub = sub nsw i32 %2, 1
  %call = call i32 @fib(i32 %sub)
  %mul = mul nsw i32 %1, %call
  store i32 %mul, i32* %retval
  br label %return

return:                                           ; preds = %if.end, %if.then
  %3 = load i32, i32* %retval
  ret i32 %3
}
</code></pre>

<pre><code class="language-lisp" data-line-numbers="|2|10,14,17,19|12,13|15">(define-llvm-function |fib| ((|n.0|) :need-frame-pointer t)
  (let ((|storemerge.11| 0))
	(declare (type (unsigned-byte 32) |n.0|)
			 (type (unsigned-byte 32) |storemerge.11|))
	(block nil
	  (tagbody
		 (let* ((|n.addr2.5| (alloca 4)))
		   (declare (type (unsigned-byte 32) |n.addr2.5|))
		   (store.i32 |n.0| |n.addr2.5|)
		   (tagbody
			  (if (icmp.slt.fused.i32 |n.0| 2)
				  (progn (go |if.then.2|))
				  (progn (go |if.end.3|)))
			  |if.then.2|
			  (psetq |storemerge.11| 1)
			  (go |return.4|)
			  |return.4|
			  (return |storemerge.11|)
			  |if.end.3|
			  (let* ((|%7| (load.i32 |n.addr2.5|)))
				(declare (type (unsigned-byte 32) |%7|))
				(psetq |storemerge.11|
					   (mul.i32 |%7| (call-direct |fib| (add.i32 |%7| 4294967295))))
				(go |return.4|))))))))
</code></pre>

<h2 id="runtime-implementation">Runtime implementation</h2>

<h3 id="alloca">Alloca</h3>
<pre><code class="language-lisp">(defmacro alloca (size)
  (incf size 15)
  (setf size (logand size (lognot 15)))
  `(decf (llvm-context-stack-pointer llvm-context) ,size))
</code></pre>

<h3 id="typed-operations">Typed operations</h3>
<pre><code class="language-lisp">(define-sized-op mul ((lhs rhs) size)
  `(* ,lhs ,rhs))
</code></pre>
<p>Generates:</p>
<ul>
<li><code>mul.i32</code></li>
<li><code>mul.i64</code></li>
<li><code>mul.f32</code></li>
<li><code>mul.f64</code></li>
<li>...</li>
</ul>

<h2 id="even-fuller-program">Even fuller program!!!</h2>
<h1 id="doom">DOOM</h1>

<h2 id="discussion-points">Discussion points:</h2>
<ul>
<li>
<p>GO uses <code>for</code> even for <code>while</code></p>
</li>
<li>
<p>Even <code>if</code> is syntax sugar in Haskell</p>
</li>
<li>
<p>Elixir removed <code>unless</code></p>
<ul>
<li><code>if</code> is often extended with an <code>else</code> later on</li>
<li><code>unless ... else</code> is considered an anti-pattern</li>
</ul>
</li>
<li>
<p>Would <code>if</code> be replaced with <code>&amp;&amp;</code></p>
</li>
<li>
<p><code>until</code> instead of <code>do ... while</code></p>
</li>
<li>
<p><code>while</code> itself can be misunderstood as an <code>if</code></p>
</li>
<li>
<p><code>linters</code> automatically folding <code>if (!cond)</code> to <code>unless (cond)</code></p>
</li>
<li>
<p><code>Bools</code> should not be used in general</p>
</li>
<li>
<p><code>x % y == 0</code> vs. <code>divisible_by(x, y)</code></p>
</li>
<li>
<p><code>oddp</code>, <code>evenp</code>, <code>zerop</code></p>
</li>
<li>
<p><a href="https://dl.acm.org/doi/10.1145/3661167.3661180">Fun paper</a> on negations being
the primary source of slow comprehension</p>
</li>
</ul>