queries/incremental-compilation.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>Incremental compilation - 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.svg">
         <link rel="shortcut icon" href="../favicon.png">
         <link rel="stylesheet" href="../css/variables.css">
         <link rel="stylesheet" href="../css/general.css">
         <link rel="stylesheet" href="../css/chrome.css">
         <link rel="stylesheet" href="../css/print.css" media="print">

         <!-- Fonts -->
         <link rel="stylesheet" href="../FontAwesome/css/font-awesome.css">
         <link rel="stylesheet" href="../fonts/fonts.css">

         <!-- Highlight.js Stylesheets -->
         <link rel="stylesheet" id="highlight-css" href="../highlight.css">
         <link rel="stylesheet" id="tomorrow-night-css" href="../tomorrow-night.css">
         <link rel="stylesheet" id="ayu-highlight-css" href="../ayu-highlight.css">

         <!-- Custom theme stylesheets -->
         <link rel="stylesheet" href="../pagetoc.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.js";
         </script>
         <!-- Start loading toc.js asap -->
         <script src="../toc.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="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="sidebar-toggle-anchor" class="hidden">

         <!-- Hide / unhide sidebar before it is displayed -->
         <script>
             let sidebar = null;
             const sidebar_toggle = document.getElementById("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="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="sidebar-resize-handle" class="sidebar-resize-handle">
                 <div class="sidebar-resize-indicator"></div>
             </div>
         </nav>

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

             <div class="page">
                 <div id="menu-bar-hover-placeholder"></div>
                 <div id="menu-bar" class="menu-bar sticky">
                     <div class="left-buttons">
                         <label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                             <i class="fa fa-bars"></i>
                         </label>
                         <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                             <i class="fa fa-paint-brush"></i>
                         </button>
                         <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                             <li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                         </ul>
                         <button id="search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="searchbar">
                             <i class="fa fa-search"></i>
                         </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">
                             <i id="print-button" class="fa fa-print"></i>
                         </a>
                         <a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
                             <i id="git-repository-button" class="fa fa-github"></i>
                         </a>
                         <a href="https://github.com/rust-lang/rustc-dev-guide/edit/main/src/queries/incremental-compilation.md" title="Suggest an edit" aria-label="Suggest an edit" rel="edit">
                             <i id="git-edit-button" class="fa fa-edit"></i>
                         </a>

                     </div>
                 </div>

                 <div id="search-wrapper" class="hidden">
                     <form id="searchbar-outer" class="searchbar-outer">
                         <div class="search-wrapper">
                             <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                             <div class="spinner-wrapper">
                                 <i class="fa fa-spinner fa-spin"></i>
                             </div>
                         </div>
                     </form>
                     <div id="searchresults-outer" class="searchresults-outer hidden">
                         <div id="searchresults-header" class="searchresults-header"></div>
                         <ul id="searchresults">
                         </ul>
                     </div>
                 </div>

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

                 <div id="content" class="content">
                     <main>
                         <h1 id="incremental-compilation"><a class="header" href="#incremental-compilation">Incremental compilation</a></h1>
 <p>The incremental compilation scheme is, in essence, a surprisingly
 simple extension to the overall query system. We'll start by describing
 a slightly simplified variant of the real thing – the "basic algorithm" –
 and then describe some possible improvements.</p>
 <h2 id="the-basic-algorithm"><a class="header" href="#the-basic-algorithm">The basic algorithm</a></h2>
 <p>The basic algorithm is
 called the <strong>red-green</strong> algorithm<sup class="footnote-reference" id="fr-salsa-1"><a href="#footnote-salsa">1</a></sup>. The high-level idea is
 that, after each run of the compiler, we will save the results of all
 the queries that we do, as well as the <strong>query DAG</strong>. The
 <strong>query DAG</strong> is a <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph">DAG</a> that indexes which queries executed which
 other queries. So, for example, there would be an <a href="https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#edge">edge</a> from a query Q1
 to another query Q2 if computing Q1 required computing Q2 (note that
 because queries cannot depend on themselves, this results in a DAG and
 not a general graph).</p>
 <blockquote>
 <p><strong>NOTE</strong>: You might think of a query as simply the definition of a query.
 A thing that you can invoke, a bit like a function,
 and which either returns a cached result or actually executes the code.</p>
 <p>If that's the way you think about queries,
 it's good to know that in the following text, queries will be said to have colours.
 Keep in mind though, that here the word query also refers to a certain invocation of
 the query for a certain input. As you will read later, queries are fingerprinted based
 on their arguments. The result of a query might change when we give it one argument
 and be coloured red, while it stays the same for another argument and is thus green.</p>
 <p>In short, the word query is here not just used to mean the definition of a query,
 but also for a specific instance of that query with given arguments.</p>
 </blockquote>
 <p>On the next run of the compiler, then, we can sometimes reuse these
 query results to avoid re-executing a query. We do this by assigning
 every query a <strong>color</strong>:</p>
 <ul>
 <li>If a query is colored <strong>red</strong>, that means that its result during
 this compilation has <strong>changed</strong> from the previous compilation.</li>
 <li>If a query is colored <strong>green</strong>, that means that its result is
 the <strong>same</strong> as the previous compilation.</li>
 </ul>
 <p>There are two key insights here:</p>
 <ul>
 <li>First, if all the inputs to query Q are colored green, then the
 query Q <strong>must</strong> result in the same value as last time and hence
 need not be re-executed (or else the compiler is not deterministic).</li>
 <li>Second, even if some inputs to a query changes, it may be that it
 <strong>still</strong> produces the same result as the previous compilation. In
 particular, the query may only use part of its input.
 <ul>
 <li>Therefore, after executing a query, we always check whether it
 produced the same result as the previous time. <strong>If it did,</strong> we
 can still mark the query as green, and hence avoid re-executing
 dependent queries.</li>
 </ul>
 </li>
 </ul>
 <h3 id="the-try-mark-green-algorithm"><a class="header" href="#the-try-mark-green-algorithm">The try-mark-green algorithm</a></h3>
 <p>At the core of incremental compilation is an algorithm called
 "try-mark-green". It has the job of determining the color of a given
 query Q (which must not have yet been executed). In cases where Q has
 red inputs, determining Q's color may involve re-executing Q so that
 we can compare its output, but if all of Q's inputs are green, then we
 can conclude that Q must be green without re-executing it or inspecting
 its value at all. In the compiler, this allows us to avoid
 deserializing the result from disk when we don't need it, and in fact
 enables us to sometimes skip <em>serializing</em> the result as well
 (see the refinements section below).</p>
 <p>Try-mark-green works as follows:</p>
 <ul>
 <li>First check if the query Q was executed during the previous compilation.
 <ul>
 <li>If not, we can just re-execute the query as normal, and assign it the
 color of red.</li>
 </ul>
 </li>
 <li>If yes, then load the 'dependent queries' of Q.</li>
 <li>If there is a saved result, then we load the <code>reads(Q)</code> vector from the
 query DAG. The "reads" is the set of queries that Q executed during
 its execution.
 <ul>
 <li>For each query R in <code>reads(Q)</code>, we recursively demand the color
 of R using try-mark-green.
 <ul>
 <li>Note: it is important that we visit each node in <code>reads(Q)</code> in same order
 as they occurred in the original compilation. See <a href="#dag">the section on the
 query DAG below</a>.</li>
 <li>If <strong>any</strong> of the nodes in <code>reads(Q)</code> wind up colored <strong>red</strong>, then Q is
 dirty.
 <ul>
 <li>We re-execute Q and compare the hash of its result to the hash of the
 result from the previous compilation.</li>
 <li>If the hash has not changed, we can mark Q as <strong>green</strong> and return.</li>
 </ul>
 </li>
 <li>Otherwise, <strong>all</strong> of the nodes in <code>reads(Q)</code> must be <strong>green</strong>. In that
 case, we can color Q as <strong>green</strong> and return.</li>
 </ul>
 </li>
 </ul>
 </li>
 </ul>
 <p><a id="dag"></a></p>
 <h3 id="the-query-dag"><a class="header" href="#the-query-dag">The query DAG</a></h3>
 <p>The query DAG code is stored in
 <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/dep_graph/index.html"><code>compiler/rustc_middle/src/dep_graph</code></a>. Construction of the DAG is done
 by instrumenting the query execution.</p>
 <p>One key point is that the query DAG also tracks ordering; that is, for
 each query Q, we not only track the queries that Q reads, we track the
 <strong>order</strong> in which they were read.  This allows try-mark-green to walk
 those queries back in the same order. This is important because once a
 subquery comes back as red, we can no longer be sure that Q will continue
 along the same path as before. That is, imagine a query like this:</p>
 <pre><code class="language-rust ignore">fn main_query(tcx) {
     if tcx.subquery1() {
         tcx.subquery2()
     } else {
         tcx.subquery3()
     }
 }</code></pre>
 <p>Now imagine that in the first compilation, <code>main_query</code> starts by
 executing <code>subquery1</code>, and this returns true. In that case, the next
 query <code>main_query</code> executes will be <code>subquery2</code>, and <code>subquery3</code> will
 not be executed at all.</p>
 <p>But now imagine that in the <strong>next</strong> compilation, the input has
 changed such that <code>subquery1</code> returns <strong>false</strong>. In this case, <code>subquery2</code>
 would never execute. If try-mark-green were to visit <code>reads(main_query)</code> out
 of order, however, it might visit <code>subquery2</code> before <code>subquery1</code>, and hence
 execute it.
 This can lead to ICEs and other problems in the compiler.</p>
 <h2 id="improvements-to-the-basic-algorithm"><a class="header" href="#improvements-to-the-basic-algorithm">Improvements to the basic algorithm</a></h2>
 <p>In the description of the basic algorithm, we said that at the end of
 compilation we would save the results of all the queries that were
 performed.  In practice, this can be quite wasteful – many of those
 results are very cheap to recompute, and serializing and deserializing
 them is not a particular win. In practice, what we would do is to save
 <strong>the hashes</strong> of all the subqueries that we performed. Then, in select cases,
 we <strong>also</strong> save the results.</p>
 <p>This is why the incremental algorithm separates computing the
 <strong>color</strong> of a node, which often does not require its value, from
 computing the <strong>result</strong> of a node. Computing the result is done via a simple
 algorithm like so:</p>
 <ul>
 <li>Check if a saved result for Q is available. If so, compute the color of Q.
 If Q is green, deserialize and return the saved result.</li>
 <li>Otherwise, execute Q.
 <ul>
 <li>We can then compare the hash of the result and color Q as green if
 it did not change.</li>
 </ul>
 </li>
 </ul>
 <h2 id="resources"><a class="header" href="#resources">Resources</a></h2>
 <p>The initial design document can be found <a href="https://github.com/nikomatsakis/rustc-on-demand-incremental-design-doc/blob/master/0000-rustc-on-demand-and-incremental.md">here</a>, which expands
 on the memoization details, provides more high-level overview and motivation
 for this system.</p>
 <h1 id="footnotes"><a class="header" href="#footnotes">Footnotes</a></h1>
 <hr>
 <ol class="footnote-definition"><li id="footnote-salsa">
 <p>I have long wanted to rename it to the Salsa algorithm, but it never caught on. -@nikomatsakis <a href="#fr-salsa-1">↩</a></p>
 </li>
 </ol>
                     </main>

                     <nav class="nav-wrapper" aria-label="Page navigation">
                         <!-- Mobile navigation buttons -->
                             <a rel="prev" href="../queries/query-evaluation-model-in-detail.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                 <i class="fa fa-angle-left"></i>
                             </a>

                             <a rel="next prefetch" href="../queries/incremental-compilation-in-detail.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                 <i class="fa fa-angle-right"></i>
                             </a>

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

             <nav class="nav-wide-wrapper" aria-label="Page navigation">
                     <a rel="prev" href="../queries/query-evaluation-model-in-detail.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                         <i class="fa fa-angle-left"></i>
                     </a>

                     <a rel="next prefetch" href="../queries/incremental-compilation-in-detail.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                         <i class="fa fa-angle-right"></i>
                     </a>
             </nav>

         </div>


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


         <script src="../elasticlunr.min.js"></script>
         <script src="../mark.min.js"></script>
         <script src="../searcher.js"></script>

         <script src="../clipboard.min.js"></script>
         <script src="../highlight.js"></script>
         <script src="../book.js"></script>

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


     </div>
     </body>
 </html>
	<!DOCTYPE HTML>
	<html lang="en" class="light sidebar-visible" dir="ltr">
	<head>
	<!-- Book generated using mdBook -->
	<meta charset="UTF-8">
	<title>Incremental compilation - 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.svg">
	<link rel="shortcut icon" href="../favicon.png">
	<link rel="stylesheet" href="../css/variables.css">
	<link rel="stylesheet" href="../css/general.css">
	<link rel="stylesheet" href="../css/chrome.css">
	<link rel="stylesheet" href="../css/print.css" media="print">

	<!-- Fonts -->
	<link rel="stylesheet" href="../FontAwesome/css/font-awesome.css">
	<link rel="stylesheet" href="../fonts/fonts.css">

	<!-- Highlight.js Stylesheets -->
	<link rel="stylesheet" id="highlight-css" href="../highlight.css">
	<link rel="stylesheet" id="tomorrow-night-css" href="../tomorrow-night.css">
	<link rel="stylesheet" id="ayu-highlight-css" href="../ayu-highlight.css">

	<!-- Custom theme stylesheets -->
	<link rel="stylesheet" href="../pagetoc.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.js";
	</script>
	<!-- Start loading toc.js asap -->
	<script src="../toc.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="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="sidebar-toggle-anchor" class="hidden">

	<!-- Hide / unhide sidebar before it is displayed -->
	<script>
	let sidebar = null;
	const sidebar_toggle = document.getElementById("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="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="sidebar-resize-handle" class="sidebar-resize-handle">
	<div class="sidebar-resize-indicator"></div>
	</div>
	</nav>

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

	<div class="page">
	<div id="menu-bar-hover-placeholder"></div>
	<div id="menu-bar" class="menu-bar sticky">
	<div class="left-buttons">
	<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
	<i class="fa fa-bars"></i>
	</label>
	<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
	<i class="fa fa-paint-brush"></i>
	</button>
	<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
	<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
	<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
	<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
	<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
	<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
	<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
	</ul>
	<button id="search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="searchbar">
	<i class="fa fa-search"></i>
	</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">
	<i id="print-button" class="fa fa-print"></i>
	</a>
	<a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
	<i id="git-repository-button" class="fa fa-github"></i>
	</a>
	<a href="https://github.com/rust-lang/rustc-dev-guide/edit/main/src/queries/incremental-compilation.md" title="Suggest an edit" aria-label="Suggest an edit" rel="edit">
	<i id="git-edit-button" class="fa fa-edit"></i>
	</a>

	</div>
	</div>

	<div id="search-wrapper" class="hidden">
	<form id="searchbar-outer" class="searchbar-outer">
	<div class="search-wrapper">
	<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
	<div class="spinner-wrapper">
	<i class="fa fa-spinner fa-spin"></i>
	</div>
	</div>
	</form>
	<div id="searchresults-outer" class="searchresults-outer hidden">
	<div id="searchresults-header" class="searchresults-header"></div>
	<ul id="searchresults">
	</ul>
	</div>
	</div>

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

	<div id="content" class="content">
	<main>
	<h1 id="incremental-compilation"><a class="header" href="#incremental-compilation">Incremental compilation</a></h1>
	<p>The incremental compilation scheme is, in essence, a surprisingly
	simple extension to the overall query system. We'll start by describing
	a slightly simplified variant of the real thing – the "basic algorithm" –
	and then describe some possible improvements.</p>
	<h2 id="the-basic-algorithm"><a class="header" href="#the-basic-algorithm">The basic algorithm</a></h2>
	<p>The basic algorithm is
	called the <strong>red-green</strong> algorithm<sup class="footnote-reference" id="fr-salsa-1"><a href="#footnote-salsa">1</a></sup>. The high-level idea is
	that, after each run of the compiler, we will save the results of all
	the queries that we do, as well as the <strong>query DAG</strong>. The
	<strong>query DAG</strong> is a <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph">DAG</a> that indexes which queries executed which
	other queries. So, for example, there would be an <a href="https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#edge">edge</a> from a query Q1
	to another query Q2 if computing Q1 required computing Q2 (note that
	because queries cannot depend on themselves, this results in a DAG and
	not a general graph).</p>
	<blockquote>
	<p><strong>NOTE</strong>: You might think of a query as simply the definition of a query.
	A thing that you can invoke, a bit like a function,
	and which either returns a cached result or actually executes the code.</p>
	<p>If that's the way you think about queries,
	it's good to know that in the following text, queries will be said to have colours.
	Keep in mind though, that here the word query also refers to a certain invocation of
	the query for a certain input. As you will read later, queries are fingerprinted based
	on their arguments. The result of a query might change when we give it one argument
	and be coloured red, while it stays the same for another argument and is thus green.</p>
	<p>In short, the word query is here not just used to mean the definition of a query,
	but also for a specific instance of that query with given arguments.</p>
	</blockquote>
	<p>On the next run of the compiler, then, we can sometimes reuse these
	query results to avoid re-executing a query. We do this by assigning
	every query a <strong>color</strong>:</p>
	<ul>
	<li>If a query is colored <strong>red</strong>, that means that its result during
	this compilation has <strong>changed</strong> from the previous compilation.</li>
	<li>If a query is colored <strong>green</strong>, that means that its result is
	the <strong>same</strong> as the previous compilation.</li>
	</ul>
	<p>There are two key insights here:</p>
	<ul>
	<li>First, if all the inputs to query Q are colored green, then the
	query Q <strong>must</strong> result in the same value as last time and hence
	need not be re-executed (or else the compiler is not deterministic).</li>
	<li>Second, even if some inputs to a query changes, it may be that it
	<strong>still</strong> produces the same result as the previous compilation. In
	particular, the query may only use part of its input.
	<ul>
	<li>Therefore, after executing a query, we always check whether it
	produced the same result as the previous time. <strong>If it did,</strong> we
	can still mark the query as green, and hence avoid re-executing
	dependent queries.</li>
	</ul>
	</li>
	</ul>
	<h3 id="the-try-mark-green-algorithm"><a class="header" href="#the-try-mark-green-algorithm">The try-mark-green algorithm</a></h3>
	<p>At the core of incremental compilation is an algorithm called
	"try-mark-green". It has the job of determining the color of a given
	query Q (which must not have yet been executed). In cases where Q has
	red inputs, determining Q's color may involve re-executing Q so that
	we can compare its output, but if all of Q's inputs are green, then we
	can conclude that Q must be green without re-executing it or inspecting
	its value at all. In the compiler, this allows us to avoid
	deserializing the result from disk when we don't need it, and in fact
	enables us to sometimes skip <em>serializing</em> the result as well
	(see the refinements section below).</p>
	<p>Try-mark-green works as follows:</p>
	<ul>
	<li>First check if the query Q was executed during the previous compilation.
	<ul>
	<li>If not, we can just re-execute the query as normal, and assign it the
	color of red.</li>
	</ul>
	</li>
	<li>If yes, then load the 'dependent queries' of Q.</li>
	<li>If there is a saved result, then we load the <code>reads(Q)</code> vector from the
	query DAG. The "reads" is the set of queries that Q executed during
	its execution.
	<ul>
	<li>For each query R in <code>reads(Q)</code>, we recursively demand the color
	of R using try-mark-green.
	<ul>
	<li>Note: it is important that we visit each node in <code>reads(Q)</code> in same order
	as they occurred in the original compilation. See <a href="#dag">the section on the
	query DAG below</a>.</li>
	<li>If <strong>any</strong> of the nodes in <code>reads(Q)</code> wind up colored <strong>red</strong>, then Q is
	dirty.
	<ul>
	<li>We re-execute Q and compare the hash of its result to the hash of the
	result from the previous compilation.</li>
	<li>If the hash has not changed, we can mark Q as <strong>green</strong> and return.</li>
	</ul>
	</li>
	<li>Otherwise, <strong>all</strong> of the nodes in <code>reads(Q)</code> must be <strong>green</strong>. In that
	case, we can color Q as <strong>green</strong> and return.</li>
	</ul>
	</li>
	</ul>
	</li>
	</ul>
	<p><a id="dag"></a></p>
	<h3 id="the-query-dag"><a class="header" href="#the-query-dag">The query DAG</a></h3>
	<p>The query DAG code is stored in
	<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/dep_graph/index.html"><code>compiler/rustc_middle/src/dep_graph</code></a>. Construction of the DAG is done
	by instrumenting the query execution.</p>
	<p>One key point is that the query DAG also tracks ordering; that is, for
	each query Q, we not only track the queries that Q reads, we track the
	<strong>order</strong> in which they were read. This allows try-mark-green to walk
	those queries back in the same order. This is important because once a
	subquery comes back as red, we can no longer be sure that Q will continue
	along the same path as before. That is, imagine a query like this:</p>
	<pre><code class="language-rust ignore">fn main_query(tcx) {
	if tcx.subquery1() {
	tcx.subquery2()
	} else {
	tcx.subquery3()
	}
	}</code></pre>
	<p>Now imagine that in the first compilation, <code>main_query</code> starts by
	executing <code>subquery1</code>, and this returns true. In that case, the next
	query <code>main_query</code> executes will be <code>subquery2</code>, and <code>subquery3</code> will
	not be executed at all.</p>
	<p>But now imagine that in the <strong>next</strong> compilation, the input has
	changed such that <code>subquery1</code> returns <strong>false</strong>. In this case, <code>subquery2</code>
	would never execute. If try-mark-green were to visit <code>reads(main_query)</code> out
	of order, however, it might visit <code>subquery2</code> before <code>subquery1</code>, and hence
	execute it.
	This can lead to ICEs and other problems in the compiler.</p>
	<h2 id="improvements-to-the-basic-algorithm"><a class="header" href="#improvements-to-the-basic-algorithm">Improvements to the basic algorithm</a></h2>
	<p>In the description of the basic algorithm, we said that at the end of
	compilation we would save the results of all the queries that were
	performed. In practice, this can be quite wasteful – many of those
	results are very cheap to recompute, and serializing and deserializing
	them is not a particular win. In practice, what we would do is to save
	<strong>the hashes</strong> of all the subqueries that we performed. Then, in select cases,
	we <strong>also</strong> save the results.</p>
	<p>This is why the incremental algorithm separates computing the
	<strong>color</strong> of a node, which often does not require its value, from
	computing the <strong>result</strong> of a node. Computing the result is done via a simple
	algorithm like so:</p>
	<ul>
	<li>Check if a saved result for Q is available. If so, compute the color of Q.
	If Q is green, deserialize and return the saved result.</li>
	<li>Otherwise, execute Q.
	<ul>
	<li>We can then compare the hash of the result and color Q as green if
	it did not change.</li>
	</ul>
	</li>
	</ul>
	<h2 id="resources"><a class="header" href="#resources">Resources</a></h2>
	<p>The initial design document can be found <a href="https://github.com/nikomatsakis/rustc-on-demand-incremental-design-doc/blob/master/0000-rustc-on-demand-and-incremental.md">here</a>, which expands
	on the memoization details, provides more high-level overview and motivation
	for this system.</p>
	<h1 id="footnotes"><a class="header" href="#footnotes">Footnotes</a></h1>
	<hr>
	<ol class="footnote-definition"><li id="footnote-salsa">
	<p>I have long wanted to rename it to the Salsa algorithm, but it never caught on. -@nikomatsakis <a href="#fr-salsa-1">↩</a></p>
	</li>
	</ol>
	</main>

	<nav class="nav-wrapper" aria-label="Page navigation">
	<!-- Mobile navigation buttons -->
	<a rel="prev" href="../queries/query-evaluation-model-in-detail.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
	<i class="fa fa-angle-left"></i>
	</a>

	<a rel="next prefetch" href="../queries/incremental-compilation-in-detail.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
	<i class="fa fa-angle-right"></i>
	</a>

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

	<nav class="nav-wide-wrapper" aria-label="Page navigation">
	<a rel="prev" href="../queries/query-evaluation-model-in-detail.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
	<i class="fa fa-angle-left"></i>
	</a>

	<a rel="next prefetch" href="../queries/incremental-compilation-in-detail.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
	<i class="fa fa-angle-right"></i>
	</a>
	</nav>

	</div>




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


	<script src="../elasticlunr.min.js"></script>
	<script src="../mark.min.js"></script>
	<script src="../searcher.js"></script>

	<script src="../clipboard.min.js"></script>
	<script src="../highlight.js"></script>
	<script src="../book.js"></script>

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



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