386 lines
20 KiB
HTML
386 lines
20 KiB
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 -->
|
||
|
||
|
||
<!-- Provide site root and default themes to javascript -->
|
||
<script>
|
||
const path_to_root = "../";
|
||
const default_light_theme = "light";
|
||
const default_dark_theme = "navy";
|
||
</script>
|
||
<!-- Start loading toc.js asap -->
|
||
<script src="../toc.js"></script>
|
||
</head>
|
||
<body>
|
||
<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 = sidebar === 'visible';
|
||
html.classList.remove('sidebar-visible');
|
||
html.classList.add("sidebar-" + sidebar);
|
||
</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. (Shortkey: s)" 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/master/src/queries/incremental-compilation.md" title="Suggest an edit" aria-label="Suggest an 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">
|
||
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
||
</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>
|
||
<ul>
|
||
<li><a href="#the-basic-algorithm">The basic algorithm</a>
|
||
<ul>
|
||
<li><a href="#the-try-mark-green-algorithm">The try-mark-green algorithm</a></li>
|
||
<li><a href="#the-query-dag">The query DAG</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a href="#improvements-to-the-basic-algorithm">Improvements to the basic algorithm</a></li>
|
||
<li><a href="#resources">Resources</a></li>
|
||
<li><a href="#footnotes">Footnotes</a></li>
|
||
</ul>
|
||
<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>
|
||
|
||
|
||
</div>
|
||
</body>
|
||
</html>
|