mir/index.html - rust-lang/rustc-dev-guide - Git at Google

 <!DOCTYPE HTML>
 <html lang="en" class="light sidebar-visible" dir="ltr">
     <head>
         <!-- Book generated using mdBook -->
         <meta charset="UTF-8">
         <title>The MIR (Mid-level IR) - Rust Compiler Development Guide</title>


         <!-- Custom HTML head -->

         <meta name="description" content="A guide to developing the Rust compiler (rustc)">
         <meta name="viewport" content="width=device-width, initial-scale=1">
         <meta name="theme-color" content="#ffffff">

         <link rel="icon" href="../favicon-de23e50b.svg">
         <link rel="shortcut icon" href="../favicon-8114d1fc.png">
         <link rel="stylesheet" href="../css/variables-8adf115d.css">
         <link rel="stylesheet" href="../css/general-2459343d.css">
         <link rel="stylesheet" href="../css/chrome-ae938929.css">
         <link rel="stylesheet" href="../css/print-9e4910d8.css" media="print">

         <!-- Fonts -->
         <link rel="stylesheet" href="../fonts/fonts-9644e21d.css">

         <!-- Highlight.js Stylesheets -->
         <link rel="stylesheet" id="mdbook-highlight-css" href="../highlight-493f70e1.css">
         <link rel="stylesheet" id="mdbook-tomorrow-night-css" href="../tomorrow-night-4c0ae647.css">
         <link rel="stylesheet" id="mdbook-ayu-highlight-css" href="../ayu-highlight-3fdfc3ac.css">

         <!-- Custom theme stylesheets -->
         <link rel="stylesheet" href="../pagetoc-88f5e8d1.css">


         <!-- Provide site root and default themes to javascript -->
         <script>
             const path_to_root = "../";
             const default_light_theme = "light";
             const default_dark_theme = "navy";
             window.path_to_searchindex_js = "../searchindex-a91e6627.js";
         </script>
         <!-- Start loading toc.js asap -->
         <script src="../toc-923879be.js"></script>
     </head>
     <body>
     <div id="mdbook-help-container">
         <div id="mdbook-help-popup">
             <h2 class="mdbook-help-title">Keyboard shortcuts</h2>
             <div>
                 <p>Press <kbd>←</kbd> or <kbd>→</kbd> to navigate between chapters</p>
                 <p>Press <kbd>S</kbd> or <kbd>/</kbd> to search in the book</p>
                 <p>Press <kbd>?</kbd> to show this help</p>
                 <p>Press <kbd>Esc</kbd> to hide this help</p>
             </div>
         </div>
     </div>
     <div id="mdbook-body-container">
         <!-- Work around some values being stored in localStorage wrapped in quotes -->
         <script>
             try {
                 let theme = localStorage.getItem('mdbook-theme');
                 let sidebar = localStorage.getItem('mdbook-sidebar');

                 if (theme.startsWith('"') && theme.endsWith('"')) {
                     localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                 }

                 if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                     localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                 }
             } catch (e) { }
         </script>

         <!-- Set the theme before any content is loaded, prevents flash -->
         <script>
             const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
             let theme;
             try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
             if (theme === null || theme === undefined) { theme = default_theme; }
             const html = document.documentElement;
             html.classList.remove('light')
             html.classList.add(theme);
             html.classList.add("js");
         </script>

         <input type="checkbox" id="mdbook-sidebar-toggle-anchor" class="hidden">

         <!-- Hide / unhide sidebar before it is displayed -->
         <script>
             let sidebar = null;
             const sidebar_toggle = document.getElementById("mdbook-sidebar-toggle-anchor");
             if (document.body.clientWidth >= 1080) {
                 try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                 sidebar = sidebar || 'visible';
             } else {
                 sidebar = 'hidden';
                 sidebar_toggle.checked = false;
             }
             if (sidebar === 'visible') {
                 sidebar_toggle.checked = true;
             } else {
                 html.classList.remove('sidebar-visible');
             }
         </script>

         <nav id="mdbook-sidebar" class="sidebar" aria-label="Table of contents">
             <!-- populated by js -->
             <mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
             <noscript>
                 <iframe class="sidebar-iframe-outer" src="../toc.html"></iframe>
             </noscript>
             <div id="mdbook-sidebar-resize-handle" class="sidebar-resize-handle">
                 <div class="sidebar-resize-indicator"></div>
             </div>
         </nav>

         <div id="mdbook-page-wrapper" class="page-wrapper">

             <div class="page">
                 <div id="mdbook-menu-bar-hover-placeholder"></div>
                 <div id="mdbook-menu-bar" class="menu-bar sticky">
                     <div class="left-buttons">
                         <label id="mdbook-sidebar-toggle" class="icon-button" for="mdbook-sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="mdbook-sidebar">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M0 96C0 78.3 14.3 64 32 64H416c17.7 0 32 14.3 32 32s-14.3 32-32 32H32C14.3 128 0 113.7 0 96zM0 256c0-17.7 14.3-32 32-32H416c17.7 0 32 14.3 32 32s-14.3 32-32 32H32c-17.7 0-32-14.3-32-32zM448 416c0 17.7-14.3 32-32 32H32c-17.7 0-32-14.3-32-32s14.3-32 32-32H416c17.7 0 32 14.3 32 32z"/></svg></span>
                         </label>
                         <button id="mdbook-theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="mdbook-theme-list">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M371.3 367.1c27.3-3.9 51.9-19.4 67.2-42.9L600.2 74.1c12.6-19.5 9.4-45.3-7.6-61.2S549.7-4.4 531.1 9.6L294.4 187.2c-24 18-38.2 46.1-38.4 76.1L371.3 367.1zm-19.6 25.4l-116-104.4C175.9 290.3 128 339.6 128 400c0 3.9 .2 7.8 .6 11.6c1.8 17.5-10.2 36.4-27.8 36.4H96c-17.7 0-32 14.3-32 32s14.3 32 32 32H240c61.9 0 112-50.1 112-112c0-2.5-.1-5-.2-7.5z"/></svg></span>
                         </button>
                         <ul id="mdbook-theme-list" class="theme-popup" aria-label="Themes" role="menu">
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-default_theme">Auto</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-light">Light</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-rust">Rust</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-coal">Coal</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-navy">Navy</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-ayu">Ayu</button></li>
                         </ul>
                         <button id="mdbook-search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="mdbook-searchbar">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M416 208c0 45.9-14.9 88.3-40 122.7L502.6 457.4c12.5 12.5 12.5 32.8 0 45.3s-32.8 12.5-45.3 0L330.7 376c-34.4 25.2-76.8 40-122.7 40C93.1 416 0 322.9 0 208S93.1 0 208 0S416 93.1 416 208zM208 352c79.5 0 144-64.5 144-144s-64.5-144-144-144S64 128.5 64 208s64.5 144 144 144z"/></svg></span>
                         </button>
                     </div>

                     <h1 class="menu-title">Rust Compiler Development Guide</h1>

                     <div class="right-buttons">
                         <a href="../print.html" title="Print this book" aria-label="Print this book">
                             <span class=fa-svg id="print-button"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M128 0C92.7 0 64 28.7 64 64v96h64V64H354.7L384 93.3V160h64V93.3c0-17-6.7-33.3-18.7-45.3L400 18.7C388 6.7 371.7 0 354.7 0H128zM384 352v32 64H128V384 368 352H384zm64 32h32c17.7 0 32-14.3 32-32V256c0-35.3-28.7-64-64-64H64c-35.3 0-64 28.7-64 64v96c0 17.7 14.3 32 32 32H64v64c0 35.3 28.7 64 64 64H384c35.3 0 64-28.7 64-64V384zm-16-88c-13.3 0-24-10.7-24-24s10.7-24 24-24s24 10.7 24 24s-10.7 24-24 24z"/></svg></span>
                         </a>
                         <a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 496 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M165.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6zm-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3zm44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9zM244.8 8C106.1 8 0 113.3 0 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C428.2 457.8 496 362.9 496 252 496 113.3 383.5 8 244.8 8zM97.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1zm-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7zm32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1zm-11.4-14.7c-1.6 1-1.6 3.6 0 5.9 1.6 2.3 4.3 3.3 5.6 2.3 1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2z"/></svg></span>
                         </a>
                         <a href="https://github.com/rust-lang/rustc-dev-guide/edit/main/src/mir/index.md" title="Suggest an edit" aria-label="Suggest an edit" rel="edit">
                             <span class=fa-svg id="git-edit-button"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M421.7 220.3l-11.3 11.3-22.6 22.6-205 205c-6.6 6.6-14.8 11.5-23.8 14.1L30.8 511c-8.4 2.5-17.5 .2-23.7-6.1S-1.5 489.7 1 481.2L38.7 353.1c2.6-9 7.5-17.2 14.1-23.8l205-205 22.6-22.6 11.3-11.3 33.9 33.9 62.1 62.1 33.9 33.9zM96 353.9l-9.3 9.3c-.9 .9-1.6 2.1-2 3.4l-25.3 86 86-25.3c1.3-.4 2.5-1.1 3.4-2l9.3-9.3H112c-8.8 0-16-7.2-16-16V353.9zM453.3 19.3l39.4 39.4c25 25 25 65.5 0 90.5l-14.5 14.5-22.6 22.6-11.3 11.3-33.9-33.9-62.1-62.1L314.3 67.7l11.3-11.3 22.6-22.6 14.5-14.5c25-25 65.5-25 90.5 0z"/></svg></span>
                         </a>

                     </div>
                 </div>

                 <div id="mdbook-search-wrapper" class="hidden">
                     <form id="mdbook-searchbar-outer" class="searchbar-outer">
                         <div class="search-wrapper">
                             <input type="search" id="mdbook-searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="mdbook-searchresults-outer" aria-describedby="searchresults-header">
                             <div class="spinner-wrapper">
                                 <span class=fa-svg id="fa-spin"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M304 48c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zm0 416c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zM48 304c26.5 0 48-21.5 48-48s-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48zm464-48c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zM142.9 437c18.7-18.7 18.7-49.1 0-67.9s-49.1-18.7-67.9 0s-18.7 49.1 0 67.9s49.1 18.7 67.9 0zm0-294.2c18.7-18.7 18.7-49.1 0-67.9S93.7 56.2 75 75s-18.7 49.1 0 67.9s49.1 18.7 67.9 0zM369.1 437c18.7 18.7 49.1 18.7 67.9 0s18.7-49.1 0-67.9s-49.1-18.7-67.9 0s-18.7 49.1 0 67.9z"/></svg></span>
                             </div>
                         </div>
                     </form>
                     <div id="mdbook-searchresults-outer" class="searchresults-outer hidden">
                         <div id="mdbook-searchresults-header" class="searchresults-header"></div>
                         <ul id="mdbook-searchresults">
                         </ul>
                     </div>
                 </div>

                 <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                 <script>
                     document.getElementById('mdbook-sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                     document.getElementById('mdbook-sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                     Array.from(document.querySelectorAll('#mdbook-sidebar a')).forEach(function(link) {
                         link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                     });
                 </script>

                 <div id="mdbook-content" class="content">
                     <main>
                         <h1 id="the-mir-mid-level-ir"><a class="header" href="#the-mir-mid-level-ir">The MIR (Mid-level IR)</a></h1>
 <p>MIR is Rust’s <em>Mid-level Intermediate Representation</em>. It is
 constructed from <a href="../hir.html">HIR</a>. MIR was introduced in
 <a href="https://rust-lang.github.io/rfcs/1211-mir.html">RFC 1211</a>. It is a radically simplified form of Rust that is used for
 certain flow-sensitive safety checks – notably the borrow checker! –
 and also for optimization and code generation.</p>
 <p>If you’d like a very high-level introduction to MIR, as well as some
 of the compiler concepts that it relies on (such as control-flow
 graphs and desugaring), you may enjoy the
 <a href="https://blog.rust-lang.org/2016/04/19/MIR.html">rust-lang blog post that introduced MIR</a>.</p>
 <h2 id="introduction-to-mir"><a class="header" href="#introduction-to-mir">Introduction to MIR</a></h2>
 <p>MIR is defined in the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/index.html"><code>compiler/rustc_middle/src/mir/</code></a> module, but much of the code
 that manipulates it is found in <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_build/index.html"><code>compiler/rustc_mir_build</code></a>,
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/index.html"><code>compiler/rustc_mir_transform</code></a>, and
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/index.html"><code>compiler/rustc_mir_dataflow</code></a>.</p>
 <p>Some of the key characteristics of MIR are:</p>
 <ul>
 <li>It is based on a <a href="../appendix/background.html#cfg">control-flow graph</a>.</li>
 <li>It does not have nested expressions.</li>
 <li>All types in MIR are fully explicit.</li>
 </ul>
 <h2 id="key-mir-vocabulary"><a class="header" href="#key-mir-vocabulary">Key MIR vocabulary</a></h2>
 <p>This section introduces the key concepts of MIR, summarized here:</p>
 <ul>
 <li><strong>Basic blocks</strong>: units of the control-flow graph, consisting of:
 <ul>
 <li><strong>statements:</strong> actions with one successor</li>
 <li><strong>terminators:</strong> actions with potentially multiple successors; always at
 the end of a block</li>
 <li>(if you’re not familiar with the term <em>basic block</em>, see the <a href="../appendix/background.html#cfg">background
 chapter</a>)</li>
 </ul>
 </li>
 <li><strong>Locals:</strong> Memory locations allocated on the stack (conceptually, at
 least), such as function arguments, local variables, and
 temporaries. These are identified by an index, written with a
 leading underscore, like <code>_1</code>. There is also a special “local”
 (<code>_0</code>) allocated to store the return value.</li>
 <li><strong>Places:</strong> expressions that identify a location in memory, like <code>_1</code> or
 <code>_1.f</code>.</li>
 <li><strong>Rvalues:</strong> expressions that produce a value. The “R” stands for
 the fact that these are the “right-hand side” of an assignment.
 <ul>
 <li><strong>Operands:</strong> the arguments to an rvalue, which can either be a
 constant (like <code>22</code>) or a place (like <code>_1</code>).</li>
 </ul>
 </li>
 </ul>
 <p>You can get a feeling for how MIR is constructed by translating simple
 programs into MIR and reading the pretty printed output. In fact, the
 playground makes this easy, since it supplies a MIR button that will
 show you the MIR for your program. Try putting this program into play
 (or <a href="https://play.rust-lang.org/?gist=30074856e62e74e91f06abd19bd72ece&amp;version=stable&amp;edition=2021">clicking on this link</a>), and then clicking the “MIR”
 button on the top:</p>
 <pre class="playground"><code class="language-rust">fn main() {
     let mut vec = Vec::new();
     vec.push(1);
     vec.push(2);
 }</code></pre>
 <p>You should see something like:</p>
 <pre><code class="language-mir">// WARNING: This output format is intended for human consumers only
 // and is subject to change without notice. Knock yourself out.
 fn main() -&gt; () {
     ...
 }
 </code></pre>
 <p>This is the MIR format for the <code>main</code> function.
 MIR shown by above link is optimized.
 Some statements like <code>StorageLive</code> are removed in optimization.
 This happens because the compiler notices the value is never accessed in the code.
 We can use <code>rustc [filename].rs -Z mir-opt-level=0 --emit mir</code> to view unoptimized MIR.
 This requires the nightly toolchain.</p>
 <p><strong>Variable declarations.</strong> If we drill in a bit, we’ll see it begins
 with a bunch of variable declarations. They look like this:</p>
 <pre><code class="language-mir">let mut _0: ();                      // return place
 let mut _1: std::vec::Vec&lt;i32&gt;;      // in scope 0 at src/main.rs:2:9: 2:16
 let mut _2: ();
 let mut _3: &amp;mut std::vec::Vec&lt;i32&gt;;
 let mut _4: ();
 let mut _5: &amp;mut std::vec::Vec&lt;i32&gt;;
 </code></pre>
 <p>You can see that variables in MIR don’t have names, they have indices,
 like <code>_0</code> or <code>_1</code>.  We also intermingle the user’s variables (e.g.,
 <code>_1</code>) with temporary values (e.g., <code>_2</code> or <code>_3</code>). You can tell apart
 user-defined variables because they have debuginfo associated to them (see below).</p>
 <p><strong>User variable debuginfo.</strong> Below the variable declarations, we find the only
 hint that <code>_1</code> represents a user variable:</p>
 <pre><code class="language-mir">scope 1 {
     debug vec =&gt; _1;                 // in scope 1 at src/main.rs:2:9: 2:16
 }
 </code></pre>
 <p>Each <code>debug &lt;Name&gt; =&gt; &lt;Place&gt;;</code> annotation describes a named user variable,
 and where (i.e. the place) a debugger can find the data of that variable.
 Here the mapping is trivial, but optimizations may complicate the place,
 or lead to multiple user variables sharing the same place.
 Additionally, closure captures are described using the same system, and so
 they’re complicated even without optimizations, e.g.: <code>debug x =&gt; (*((*_1).0: &amp;T));</code>.</p>
 <p>The “scope” blocks (e.g., <code>scope 1 { .. }</code>) describe the lexical structure of
 the source program (which names were in scope when), so any part of the program
 annotated with <code>// in scope 0</code> would be missing <code>vec</code>, if you were stepping
 through the code in a debugger, for example.</p>
 <p><strong>Basic blocks.</strong> Reading further, we see our first <strong>basic block</strong> (naturally
 it may look slightly different when you view it, and I am ignoring some of the
 comments):</p>
 <pre><code class="language-mir">bb0: {
     StorageLive(_1);
     _1 = const &lt;std::vec::Vec&lt;T&gt;&gt;::new() -&gt; bb2;
 }
 </code></pre>
 <p>A basic block is defined by a series of <strong>statements</strong> and a final
 <strong>terminator</strong>.  In this case, there is one statement:</p>
 <pre><code class="language-mir">StorageLive(_1);
 </code></pre>
 <p>This statement indicates that the variable <code>_1</code> is “live”, meaning
 that it may be used later – this will persist until we encounter a
 <code>StorageDead(_1)</code> statement, which indicates that the variable <code>_1</code> is
 done being used. These “storage statements” are used by LLVM to
 allocate stack space.</p>
 <p>The <strong>terminator</strong> of the block <code>bb0</code> is the call to <code>Vec::new</code>:</p>
 <pre><code class="language-mir">_1 = const &lt;std::vec::Vec&lt;T&gt;&gt;::new() -&gt; bb2;
 </code></pre>
 <p>Terminators are different from statements because they can have more
 than one successor – that is, control may flow to different
 places. Function calls like the call to <code>Vec::new</code> are always
 terminators because of the possibility of unwinding, although in the
 case of <code>Vec::new</code> we are able to see that indeed unwinding is not
 possible, and hence we list only one successor block, <code>bb2</code>.</p>
 <p>If we look ahead to <code>bb2</code>, we will see it looks like this:</p>
 <pre><code class="language-mir">bb2: {
     StorageLive(_3);
     _3 = &amp;mut _1;
     _2 = const &lt;std::vec::Vec&lt;T&gt;&gt;::push(move _3, const 1i32) -&gt; [return: bb3, unwind: bb4];
 }
 </code></pre>
 <p>Here there are two statements: another <code>StorageLive</code>, introducing the <code>_3</code>
 temporary, and then an assignment:</p>
 <pre><code class="language-mir">_3 = &amp;mut _1;
 </code></pre>
 <p>Assignments in general have the form:</p>
 <pre><code class="language-text">&lt;Place&gt; = &lt;Rvalue&gt;
 </code></pre>
 <p>A place is an expression like <code>_3</code>, <code>_3.f</code> or <code>*_3</code> – it denotes a
 location in memory.  An <strong>Rvalue</strong> is an expression that creates a
 value: in this case, the rvalue is a mutable borrow expression, which
 looks like <code>&amp;mut &lt;Place&gt;</code>. So we can kind of define a grammar for
 rvalues like so:</p>
 <pre><code class="language-text">&lt;Rvalue&gt;  = &amp; (mut)? &lt;Place&gt;
           | &lt;Operand&gt; + &lt;Operand&gt;
           | &lt;Operand&gt; - &lt;Operand&gt;
           | ...

 &lt;Operand&gt; = Constant
           | copy Place
           | move Place
 </code></pre>
 <p>As you can see from this grammar, rvalues cannot be nested – they can
 only reference places and constants. Moreover, when you use a place,
 we indicate whether we are <strong>copying it</strong> (which requires that the
 place have a type <code>T</code> where <code>T: Copy</code>) or <strong>moving it</strong> (which works
 for a place of any type). So, for example, if we had the expression <code>x = a + b + c</code> in Rust, that would get compiled to two statements and a
 temporary:</p>
 <pre><code class="language-mir">TMP1 = a + b
 x = TMP1 + c
 </code></pre>
 <p>(<a href="https://play.rust-lang.org/?gist=1751196d63b2a71f8208119e59d8a5b6&amp;version=stable">Try it and see</a>, though you may want to do release mode to skip
 over the overflow checks.)</p>
 <h2 id="mir-data-types"><a class="header" href="#mir-data-types">MIR data types</a></h2>
 <p>The MIR data types are defined in the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/index.html"><code>compiler/rustc_middle/src/mir/</code></a>
 module. Each of the key concepts mentioned in the previous section
 maps in a fairly straightforward way to a Rust type.</p>
 <p>The main MIR data type is <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Body.html"><code>Body</code></a>. It contains the data for a single
 function (along with sub-instances of Mir for “promoted constants”,
 but <a href="#promoted">you can read about those below</a>).</p>
 <ul>
 <li><strong>Basic blocks</strong>: The basic blocks are stored in the field
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Body.html#structfield.basic_blocks"><code>Body::basic_blocks</code></a>; this is a vector
 of <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.BasicBlockData.html"><code>BasicBlockData</code></a> structures. Nobody ever references a
 basic block directly: instead, we pass around <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.BasicBlock.html"><code>BasicBlock</code></a>
 values, which are <a href="../appendix/glossary.html#newtype">newtype’d</a> indices into this vector.</li>
 <li><strong>Statements</strong> are represented by the type <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Statement.html"><code>Statement</code></a>.</li>
 <li><strong>Terminators</strong> are represented by the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/terminator/struct.Terminator.html"><code>Terminator</code></a>.</li>
 <li><strong>Locals</strong> are represented by a <a href="../appendix/glossary.html#newtype">newtype’d</a> index type <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Local.html"><code>Local</code></a>.
 The data for a local variable is found in the
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Body.html#structfield.local_decls"><code>Body::local_decls</code></a> vector. There is also a special constant
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/constant.RETURN_PLACE.html"><code>RETURN_PLACE</code></a> identifying the special “local” representing the return value.</li>
 <li><strong>Places</strong> are identified by the struct <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Place.html"><code>Place</code></a>. There are a few
 fields:
 <ul>
 <li>Local variables like <code>_1</code></li>
 <li><strong>Projections</strong>, which are fields or other things that “project
 out” from a base place. These are represented by the <a href="../appendix/glossary.html#newtype">newtype’d</a> type
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.ProjectionElem.html"><code>ProjectionElem</code></a>. So e.g. the place <code>_1.f</code> is a projection,
 with <code>f</code> being the “projection element” and <code>_1</code> being the base
 path. <code>*_1</code> is also a projection, with the <code>*</code> being represented
 by the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.ProjectionElem.html#variant.Deref"><code>ProjectionElem::Deref</code></a> element.</li>
 </ul>
 </li>
 <li><strong>Rvalues</strong> are represented by the enum <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.Rvalue.html"><code>Rvalue</code></a>.</li>
 <li><strong>Operands</strong> are represented by the enum <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.Operand.html"><code>Operand</code></a>.</li>
 </ul>
 <h2 id="representing-constants"><a class="header" href="#representing-constants">Representing constants</a></h2>
 <p>When code has reached the MIR stage, constants can generally come in two forms:
 <em>MIR constants</em> (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.Const.html"><code>mir::Constant</code></a>) and <em>type system constants</em> (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.Const.html"><code>ty::Const</code></a>).
 MIR constants are used as operands: in <code>x + CONST</code>, <code>CONST</code> is a MIR constant;
 similarly, in <code>x + 2</code>, <code>2</code> is a MIR constant. Type system constants are used in
 the type system, in particular for array lengths but also for const generics.</p>
 <p>Generally, both kinds of constants can be “unevaluated” or “already evaluated”.
 An unevaluated constant simply stores the <code>DefId</code> of what needs to be evaluated
 to compute this result. An evaluated constant (a “value”) has already been
 computed; their representation differs between type system constants and MIR
 constants: MIR constants evaluate to a <code>mir::ConstValue</code>; type system constants
 evaluate to a <code>ty::ValTree</code>.</p>
 <p>Type system constants have some more variants to support const generics: they
 can refer to local const generic parameters, and they are subject to inference.
 Furthermore, the <code>mir::Constant::Ty</code> variant lets us use an arbitrary type
 system constant as a MIR constant; this happens whenever a const generic
 parameter is used as an operand.</p>
 <h3 id="mir-constant-values"><a class="header" href="#mir-constant-values">MIR constant values</a></h3>
 <p>In general, a MIR constant value (<code>mir::ConstValue</code>) was computed by evaluating
 some constant the user wrote. This <a href="../const-eval.html">const evaluation</a> produces
 a very low-level representation of the result in terms of individual bytes. We
 call this an “indirect” constant (<code>mir::ConstValue::Indirect</code>) since the value
 is stored in-memory.</p>
 <p>However, storing everything in-memory would be awfully inefficient. Hence there
 are some other variants in <code>mir::ConstValue</code> that can represent certain simple
 and common values more efficiently. In particular, everything that can be
 directly written as a literal in Rust (integers, floats, chars, bools, but also
 <code>"string literals"</code> and <code>b"byte string literals"</code>) has an optimized variant that
 avoids the full overhead of the in-memory representation.</p>
 <h3 id="valtrees"><a class="header" href="#valtrees">ValTrees</a></h3>
 <p>An evaluated type system constant is a “valtree”. The <code>ty::ValTree</code> datastructure
 allows us to represent</p>
 <ul>
 <li>arrays,</li>
 <li>many structs,</li>
 <li>tuples,</li>
 <li>enums and,</li>
 <li>most primitives.</li>
 </ul>
 <p>The most important rule for
 this representation is that every value must be uniquely represented. In other
 words: a specific value must only be representable in one specific way. For example: there is only
 one way to represent an array of two integers as a <code>ValTree</code>:
 <code>Branch([Leaf(first_int), Leaf(second_int)])</code>.
 Even though theoretically a <code>[u32; 2]</code> could be encoded in a <code>u64</code> and thus just be a
 <code>Leaf(bits_of_two_u32)</code>, that is not a legal construction of <code>ValTree</code>
 (and is very complex to do, so it is unlikely anyone is tempted to do so).</p>
 <p>These rules also mean that some values are not representable. There can be no <code>union</code>s in type
 level constants, as it is not clear how they should be represented, because their active variant
 is unknown. Similarly there is no way to represent raw pointers, as addresses are unknown at
 compile-time and thus we cannot make any assumptions about them. References on the other hand
 <em>can</em> be represented, as equality for references is defined as equality on their value, so we
 ignore their address and just look at the backing value. We must make sure that the pointer values
 of the references are not observable at compile time. We thus encode <code>&amp;42</code> exactly like <code>42</code>.
 Any conversion from
 valtree back to a MIR constant value must reintroduce an actual indirection. At codegen time the
 addresses may be deduplicated between multiple uses or not, entirely depending on arbitrary
 optimization choices.</p>
 <p>As a consequence, all decoding of <code>ValTree</code> must happen by matching on the type first and making
 decisions depending on that. The value itself gives no useful information without the type that
 belongs to it.</p>
 <p><a id="promoted"></a></p>
 <h3 id="promoted-constants"><a class="header" href="#promoted-constants">Promoted constants</a></h3>
 <p>See the const-eval WG’s <a href="https://github.com/rust-lang/const-eval/blob/master/promotion.md">docs on promotion</a>.</p>

                     </main>

                     <nav class="nav-wrapper" aria-label="Page navigation">
                         <!-- Mobile navigation buttons -->
                             <a rel="prev" href="../thir.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                 <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M41.4 233.4c-12.5 12.5-12.5 32.8 0 45.3l160 160c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L109.3 256 246.6 118.6c12.5-12.5 12.5-32.8 0-45.3s-32.8-12.5-45.3 0l-160 160z"/></svg></span>
                             </a>

                             <a rel="next prefetch" href="../mir/construction.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                 <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M278.6 233.4c12.5 12.5 12.5 32.8 0 45.3l-160 160c-12.5 12.5-32.8 12.5-45.3 0s-12.5-32.8 0-45.3L210.7 256 73.4 118.6c-12.5-12.5-12.5-32.8 0-45.3s32.8-12.5 45.3 0l160 160z"/></svg></span>
                             </a>

                         <div style="clear: both"></div>
                     </nav>
                 </div>
             </div>

             <nav class="nav-wide-wrapper" aria-label="Page navigation">
                     <a rel="prev" href="../thir.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                         <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M41.4 233.4c-12.5 12.5-12.5 32.8 0 45.3l160 160c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L109.3 256 246.6 118.6c12.5-12.5 12.5-32.8 0-45.3s-32.8-12.5-45.3 0l-160 160z"/></svg></span>
                     </a>

                     <a rel="next prefetch" href="../mir/construction.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                         <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M278.6 233.4c12.5 12.5 12.5 32.8 0 45.3l-160 160c-12.5 12.5-32.8 12.5-45.3 0s-12.5-32.8 0-45.3L210.7 256 73.4 118.6c-12.5-12.5-12.5-32.8 0-45.3s32.8-12.5 45.3 0l160 160z"/></svg></span>
                     </a>
             </nav>

         </div>

         <template id=fa-eye><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M288 32c-80.8 0-145.5 36.8-192.6 80.6C48.6 156 17.3 208 2.5 243.7c-3.3 7.9-3.3 16.7 0 24.6C17.3 304 48.6 356 95.4 399.4C142.5 443.2 207.2 480 288 480s145.5-36.8 192.6-80.6c46.8-43.5 78.1-95.4 93-131.1c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C433.5 68.8 368.8 32 288 32zM432 256c0 79.5-64.5 144-144 144s-144-64.5-144-144s64.5-144 144-144s144 64.5 144 144zM288 192c0 35.3-28.7 64-64 64c-11.5 0-22.3-3-31.6-8.4c-.2 2.8-.4 5.5-.4 8.4c0 53 43 96 96 96s96-43 96-96s-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6z"/></svg></span></template>
         <template id=fa-eye-slash><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 640 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M38.8 5.1C28.4-3.1 13.3-1.2 5.1 9.2S-1.2 34.7 9.2 42.9l592 464c10.4 8.2 25.5 6.3 33.7-4.1s6.3-25.5-4.1-33.7L525.6 386.7c39.6-40.6 66.4-86.1 79.9-118.4c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C465.5 68.8 400.8 32 320 32c-68.2 0-125 26.3-169.3 60.8L38.8 5.1zM223.1 149.5C248.6 126.2 282.7 112 320 112c79.5 0 144 64.5 144 144c0 24.9-6.3 48.3-17.4 68.7L408 294.5c5.2-11.8 8-24.8 8-38.5c0-53-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6c0 10.2-2.4 19.8-6.6 28.3l-90.3-70.8zm223.1 298L373 389.9c-16.4 6.5-34.3 10.1-53 10.1c-79.5 0-144-64.5-144-144c0-6.9 .5-13.6 1.4-20.2L83.1 161.5C60.3 191.2 44 220.8 34.5 243.7c-3.3 7.9-3.3 16.7 0 24.6c14.9 35.7 46.2 87.7 93 131.1C174.5 443.2 239.2 480 320 480c47.8 0 89.9-12.9 126.2-32.5z"/></svg></span></template>
         <template id=fa-copy><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M502.6 70.63l-61.25-61.25C435.4 3.371 427.2 0 418.7 0H255.1c-35.35 0-64 28.66-64 64l.0195 256C192 355.4 220.7 384 256 384h192c35.2 0 64-28.8 64-64V93.25C512 84.77 508.6 76.63 502.6 70.63zM464 320c0 8.836-7.164 16-16 16H255.1c-8.838 0-16-7.164-16-16L239.1 64.13c0-8.836 7.164-16 16-16h128L384 96c0 17.67 14.33 32 32 32h47.1V320zM272 448c0 8.836-7.164 16-16 16H63.1c-8.838 0-16-7.164-16-16L47.98 192.1c0-8.836 7.164-16 16-16H160V128H63.99c-35.35 0-64 28.65-64 64l.0098 256C.002 483.3 28.66 512 64 512h192c35.2 0 64-28.8 64-64v-32h-47.1L272 448z"/></svg></span></template>
         <template id=fa-play><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 384 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M73 39c-14.8-9.1-33.4-9.4-48.5-.9S0 62.6 0 80V432c0 17.4 9.4 33.4 24.5 41.9s33.7 8.1 48.5-.9L361 297c14.3-8.7 23-24.2 23-41s-8.7-32.2-23-41L73 39z"/></svg></span></template>
         <template id=fa-clock-rotate-left><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M75 75L41 41C25.9 25.9 0 36.6 0 57.9V168c0 13.3 10.7 24 24 24H134.1c21.4 0 32.1-25.9 17-41l-30.8-30.8C155 85.5 203 64 256 64c106 0 192 86 192 192s-86 192-192 192c-40.8 0-78.6-12.7-109.7-34.4c-14.5-10.1-34.4-6.6-44.6 7.9s-6.6 34.4 7.9 44.6C151.2 495 201.7 512 256 512c141.4 0 256-114.6 256-256S397.4 0 256 0C185.3 0 121.3 28.7 75 75zm181 53c-13.3 0-24 10.7-24 24V256c0 6.4 2.5 12.5 7 17l72 72c9.4 9.4 24.6 9.4 33.9 0s9.4-24.6 0-33.9l-65-65V152c0-13.3-10.7-24-24-24z"/></svg></span></template>


         <script>
             window.playground_copyable = true;
         </script>


         <script src="../elasticlunr-ef4e11c1.min.js"></script>
         <script src="../mark-09e88c2c.min.js"></script>
         <script src="../searcher-c2a407aa.js"></script>

         <script src="../clipboard-1626706a.min.js"></script>
         <script src="../highlight-abc7f01d.js"></script>
         <script src="../book-a0b12cfe.js"></script>

         <!-- Custom JS scripts -->
         <script src="../mermaid-cc85ecea.min.js"></script>
         <script src="../mermaid-init-4533fb11.js"></script>
         <script src="../pagetoc-ad825849.js"></script>


     </div>
     </body>
 </html>