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

<h1 id="link-recording"><a rel="noopener" target="_blank" href="https://youtu.be/DBw7MHUTKnc">🔗 Recording</a></h1>

<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: &lt;2015&gt;</li>
<li>Demo 5: &lt;2020&gt;</li>
<li>Latest Commit at time of writing: <span class="timestamp-wrapper"><span class="timestamp">&lt;2025-05-01 Thu&gt;</span></span></li>
</ul>

<h1 id="what-is-mezanno">What is <a rel="noopener" target="_blank" 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 rel="noopener" target="_blank" href="https://github.com/froggey/Mezzano/blob/master/doc/quickstart.md">Blinkenlights</a>:</p>
<ul>
<li><span style="color:green">**Green**</span>: Disk read in progress</li>
<li><span style="color:red">**Red**</span>: Disk write in progress</li>
<li><span style="color:purple">**Purple**</span>: GC in progress</li>
<li><span style="color:cyan">**Cyan**</span>: Activity, system is not idle</li>
<li><span style="color:yellow">**Yellow**</span>: Snapshot in progress</li>
<li><span style="color:brown">**Brown**</span>: Page fault being serviced</li>
<li><span style="color:lightgreen">**Light Green**</span>: Network activity</li>
</ul>
<p><img src="https://blog.michal-atlas.cz/posts/lang-talks/19-i/pipeline.svg" alt="img" /></p>
<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="img" title="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 rel="noopener" target="_blank" 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>