What's LLVM?
Tags: computerscience, productivity, architecture, opensource
Published: 2020-12-12 09:09:20

*In case it helped :)*
<a href="https://www.buymeacoffee.com/aseemwangoo" target="_blank"><img src="https://www.buymeacoffee.com/assets/img/custom_images/orange_img.png" alt="Pass Me A Coffee!!" style="height: 41px !important;width: 174px !important;box-shadow: 0px 3px 2px 0px rgba(190, 190, 190, 0.5) !important;-webkit-box-shadow: 0px 3px 2px 0px rgba(190, 190, 190, 0.5) !important;" ></a>

<!-- wp:paragraph -->
<p>As per the <a href="https://llvm.org/" rel="noreferrer noopener" target="_blank">official site</a>:</p>
<!-- /wp:paragraph -->

<!-- wp:quote -->
<blockquote class="wp-block-quote"><p>LLVM is a collection of the modular and reusable compiler and toolchain technologies. “LLVM” is not an acronym; it is the full name of the project.</p></blockquote>
<!-- /wp:quote -->


<!-- wp:paragraph -->
<p>Let’s take the below diagram,</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/0*nm9Qy1jy7zka09iw.png" alt="LLVM"/><figcaption>Human readable to Machine&nbsp;readable</figcaption></figure>
<!-- /wp:image -->

####Article here: https://flatteredwithflutter.com/what-is-llvm/

<!-- wp:paragraph -->
<p>We write source code, in the language of our choice. This code is human-readable, but the machine on which it runs does not understand it. That’s why we compile, which converts the source code and translates it into something which the machine understands.</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>Compilers Approach</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>There are various phases involved when we compile our source program, (source, scanner, parsing, etc.). Traditional compilers had all these steps as a monolithic structure.</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*-fn1j4wz4zVEO4iTdZrB_g.png" alt="LLVM"/><figcaption>Modern Compilers</figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>What modern compilers do, it delegates the compiling tasks to a set of different components (shown in the above diagram).</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><strong>What does this mean?</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Different teams can work on the tasks they specialize in. For instance, a team good at parsing can focus only on it and make it better.</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4><strong>Enter LLVM</strong></h4>
<!-- /wp:heading -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1600/0*3L1fkXfy8E_kk2br.jpg" alt="Chris Lattener"/><figcaption>Chris Lattner</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:quote -->
<blockquote class="wp-block-quote"><p><strong>Chris Lattner</strong> is the main author of LLVM and related projects such as the Clang compiler and the <strong>Swift</strong> programming language. <a href="http://www.nondot.org/sabre/Resume.html" rel="noreferrer noopener" target="_blank">Resume here</a></p></blockquote>
<!-- /wp:quote -->

<!-- wp:paragraph -->
<p>LLVM is famous for <strong>Intermediate Representation(LLVM IR) </strong>and <strong>IR Optimizer.</strong> During a program compilation, the source language is converted into this <strong>IR, </strong>and the output is finally run on a target architecture (x86, ARM, etc.)</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/0*bKbFhurcfJJUFjpH.png" alt="Compilers Overview"/><figcaption>Compilers Overview</figcaption></figure>
<!-- /wp:image -->

<!-- wp:list -->
<ul><li><strong>Front-end</strong>: compiles source language to IR.</li><li><strong>Middle-end</strong>: optimizes IR.</li><li><strong>Back-end</strong>: compiles IR to machine code.</li></ul>
<!-- /wp:list -->

<!-- wp:heading {"level":4} -->
<h4><strong>What</strong>'s<strong> LLVM&nbsp;IR?</strong></h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>LLVM IR </p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>a platform-independent assembly language.</li><li>strongly typed</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>(e.g., <code>i32</code> a 32-bit integer, <code>i32**</code> a pointer to pointer to 32-bit integer)</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>has unlimited <strong>SSA(Static Single Assignment)</strong> Register machine instruction set.</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>SSA: Every variable is assigned exactly once, named with a % character.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>a low-level RISC-like virtual instruction set.</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>LLVM IR has 3 common representations</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>Human-readable LLVM assembly (.ll files)</li><li>Bitcode binary representation (.bc files)</li><li>C++ classes</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>In particular, LLVM IR is both well-specified and the <em>only</em> interface to the optimizer. This property means that all you need to know to write a front end for LLVM is what LLVM IR is, how it works, and the invariants it expects.</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>Programming Example</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>Let’s look at a simple C code,</p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1600/1*CloSdnn_TRmTBSwoJFhz7w.png" alt="C Code"/><figcaption>C Code</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>If we compile this code into LLVM using below&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">clang -S -emit-llvm -O3 hello_world.c</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>or online (see links below), we get</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">// LLVM IR
<strong>define</strong> <em>i32</em> @main() #0 {
  <strong>ret</strong> <em>i32</em> 7              <em>; Return an integer value of 7</em>
}</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>A sequence of instructions that execute in order is a basic block. Basic blocks must end with a terminator.</p>
<!-- /wp:paragraph -->

<!-- wp:quote -->
<blockquote class="wp-block-quote"><p>Note: You can’t jump into the middle of a basic block</p></blockquote>
<!-- /wp:quote -->

<!-- wp:paragraph -->
<p>There are some terminator instructions defined in LLVM:</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li><code><a href="https://llvm.org/docs/LangRef.html#ret-instruction" rel="noreferrer noopener" target="_blank">ret</a></code>&nbsp;</li><li><code><a href="https://llvm.org/docs/LangRef.html#br-instruction" rel="noreferrer noopener" target="_blank">br</a></code></li><li><code><a href="https://llvm.org/docs/LangRef.html#switch-instruction" rel="noreferrer noopener" target="_blank">switch</a></code> and others</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>Global identifiers (functions, global variables) begin with the <code>'@'</code> character</p>
<!-- /wp:paragraph -->

<!-- wp:quote -->
<blockquote class="wp-block-quote"><p><a href="https://llvm.org/docs/LangRef.html#overview" rel="noreferrer noopener" target="_blank">Guide to LLVM Language</a></p></blockquote>
<!-- /wp:quote -->

<!-- wp:paragraph -->
<p>Links for programming online:</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><a href="https://godbolt.org/">Godbolt</a>, <a href="http://ellcc.org/demo/index.cgi">ELCC</a></p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>Phi φ</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>There are some times when you want to select the values executed from the previous basic block.</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">SYNTAX FOR phi
&lt;result&gt; = phi &lt;ty&gt; [ &lt;val0&gt;, &lt;label0&gt;], ...</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>Using phi:</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted"><strong>Loop:</strong>       <em>; Infinite loop that counts from 0 on up...</em><br>  %indvar = <strong>phi</strong> <strong>i32</strong> [ 0, %LoopHeader ], [ %nextindvar, %Loop ]<br>  %nextindvar = <strong>add</strong> <strong>i32</strong> %indvar, 1<br>  <strong>br</strong> <strong>label</strong> %Loop</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>This basically says take the value <strong>0, </strong>if we are coming from basic block <strong>LoopHeader</strong>, or take the value of <strong>nextindvar</strong> if we are coming from <strong>Loop</strong> block<strong>.</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>At runtime, the ‘<code>phi</code>’ instruction logically takes on the value from the block that executed just prior to the current block.</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>LLVM IR Optimization</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>Most optimizations follow a simple three-part structure:</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>Look for a pattern to be transformed.</li><li>Verify that the transformation is safe/correct.</li><li>Do the transformation, updating the code.</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>The most trivial optimization is pattern matching on arithmetic identities, for any integer <code>X</code>,</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li><code>X-X</code> is 0</li><li><code>X-0</code> is <code>X</code></li><li><code>(X*2)-X</code> is <code>X</code></li></ul>
<!-- /wp:list -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">// LLVM IR REPRESENATION<br>⋮    ⋮    ⋮<br>%example1 = sub i32 %a, %a<br>⋮    ⋮    ⋮<br>%example2 = sub i32 %b, 0<br>⋮    ⋮    ⋮<br>%tmp = mul i32 %c, 2<br>%example3 = sub i32 %tmp, %c<br>⋮    ⋮    ⋮</pre>
<!-- /wp:preformatted -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">// LLVM IR OPTIMIZATION<br>// X - 0 -&gt; X<br>if (match(Op1, m_Zero()))<br>  return Op0;<br><br>// X - X -&gt; 0<br>if (Op0 == Op1)<br>  return Constant::getNullValue(Op0-&gt;getType());<br><br>// (X*2) - X -&gt; X<br>if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt&lt;2&gt;())))<br>  return Op1;</pre>
<!-- /wp:preformatted -->

<!-- wp:separator -->
<hr class="wp-block-separator"/>
<!-- /wp:separator -->

<!-- wp:paragraph -->
<p><a href="https://llvm.org/docs/LangRef.html#id310" rel="noreferrer noopener" target="_blank"><em>LLVM Language Reference here.</em></a></p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>LLVM in different languages</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>A programming language is incomplete without a compiler. Many languages use LLVM to produce their compilers since LLVM removes a lot of additional tasks.</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li><a href="https://github.com/kripken/emscripten" rel="noreferrer noopener" target="_blank">Emscripten</a> project takes LLVM IR code and converts it into JavaScript, allowing any language with an LLVM back end to export code that can run on the browser.</li><li>Nvidia used LLVM for the <a href="https://developer.nvidia.com/cuda-llvm-compiler" rel="noreferrer noopener" target="_blank">Nvidia CUDA Compiler</a>, which lets languages add native support for CUDA.</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>Many languages and language runtimes have LLVM support, including <a href="https://github.com/Microsoft/LLVMSharp" rel="noreferrer noopener" target="_blank">C#/.NET/Mono</a>, <a href="https://crates.io/crates/llvm-sys" rel="noreferrer noopener" target="_blank">Rust</a>, <a href="https://hackage.haskell.org/package/llvm" rel="noreferrer noopener" target="_blank">Haskell</a>, <a href="https://opam.ocaml.org/packages/llvm/" rel="noreferrer noopener" target="_blank">OCAML</a>, <a href="https://www.npmjs.com/package/llvm-node" rel="noreferrer noopener" target="_blank">Node.js</a>, <a href="https://llvm.org/svn/llvm-project/llgo/trunk/README.TXT" rel="noreferrer noopener" target="_blank">Go</a>, and <a href="https://github.com/numba/llvmlite" rel="noreferrer noopener" target="_blank">Python</a>.</p>
<!-- /wp:paragraph -->

<!-- wp:separator -->
<hr class="wp-block-separator"/>
<!-- /wp:separator -->

<!-- wp:heading {"level":4} -->
<h4>Future of LLVM — MLIR</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>As we know, not every language is supported by LLVM, but the increasing use of LLVM is attracting new languages to use it.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:quote -->
<blockquote class="wp-block-quote"><p>Introducing <strong>MLIR (Multi-Level Intermediate Representation)</strong></p></blockquote>
<!-- /wp:quote -->

<!-- wp:paragraph -->
<p>MLIR is a flexible infrastructure for modern optimizing compilers. This means it consists of a specification for intermediate representations (IR) and a toolkit to perform transformations on that representation.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>MLIR is highly influenced by <a href="https://llvm.org/" rel="noreferrer noopener" target="_blank">LLVM</a> and reuses many great ideas from it. It also supports hardware-specific operations.&nbsp;</p>
<!-- /wp:paragraph -->

*In case it helped :)*
<a href="https://www.buymeacoffee.com/aseemwangoo" target="_blank"><img src="https://www.buymeacoffee.com/assets/img/custom_images/orange_img.png" alt="Pass Me A Coffee!!" style="height: 41px !important;width: 174px !important;box-shadow: 0px 3px 2px 0px rgba(190, 190, 190, 0.5) !important;-webkit-box-shadow: 0px 3px 2px 0px rgba(190, 190, 190, 0.5) !important;" ></a>


<!-- wp:paragraph -->
<p><a href="https://docs.google.com/presentation/d/11-VjSNNNJoRhPlLxFgvtb909it1WNdxTnQFipryfAPU/edit#slide=id.g7d334b12e5_0_4" rel="noreferrer noopener" target="_blank"><em>Slides here.</em></a></p>
<!-- /wp:paragraph -->