search

cisen / blog

Time waits for no one.
130 stars 20 forks source link

rust MIR 相关 #999

Open cisen opened 3 years ago

cisen commented 3 years ago

总结

捕获616

cisen commented 3 years ago

Introducing MIR

我们正处于Rust编译器内部的全面转型的最后阶段。在过去的一年左右的时间里，我们一直在稳步制定一项计划，以更改内部编译器管道，如下所示：

编译流程图 捕获

也就是说，我们正在为您的程序引入一个新的中间表示（IR），我们称其为MIR：MIR代表中级IR，因为MIR介于现有HIR（“高级IR”，大致为 抽象语法树）之间）和LLVM（“低级” IR）。以前，编译器中的“翻译”阶段将在一个相当大的步骤中将成熟的Rust转换为类似机器代码的LLVM。但是现在，它将分两个阶段完成其工作，中间是一个大大简化的Rust版本-MIR。

如果您不是编译器爱好者，那么这一切似乎都是不可思议的，不太可能直接影响您。但实际上，MIR是勾勒出Rust的许多最优先事项的关键：

更快的编译时间。我们正在努力使Rust的编译成为增量编译 ，以便在您重新编译代码时，编译器仅重新编译它必须执行的操作。MIR从一开始就考虑到该用例而设计，因此即使程序的其他部分同时发生了更改，对于我们来说，保存和重新加载也要容易得多。

MIR还为更有效的数据结构和消除编译器中的冗余工作提供了基础，这两者都将加快整体编译速度。

执行时间更快。您可能已经注意到，在新的编译器管道中，优化出现了两次。这绝非偶然：以前，编译器仅依靠LLVM来执行优化，但是借助MIR，我们可以在打LLVM之前进行某些Rust特定的优化-或就此而言，在使代码单一化之前。Rust的丰富类型系统应该为超越LLVM的优化提供沃土。

此外，MIR将取消Rust生成的代码的某些长期性能改进，例如“ non-zeroing” drop。

更精确的类型检查。如今的Rust编译器对借用施加了一些人为限制，这些限制很大程度上源于编译器当前表示程序的方式。MIR将使借用更加灵活，从而改善Rust的人体工程学和学习曲线。

除了这些面向用户的改进之外，MIR还为编译器提供了许多工程上的好处：

消除冗余。当前，由于我们用完整的Rust语言编写所有通行证，因此有很多重复项。例如，安全性分析和产生LLVM IR的后端必须就如何翻译墨滴或match 测试和执行表达臂的确切顺序（可能会变得非常复杂）达成一致。使用MIR，所有这些逻辑都集中在MIR构造中，以后的过程可以仅依赖于此。

雄心勃勃。除了更加DRY之外，使用MIR更加容易，因为与常规Rust相比，它包含了更多的原始操作集。这种简化使我们能够做很多以前复杂的事情。我们将在这篇文章中探讨一种这样的情况-非归零下降-但正如我们将在最后看到的那样，管道中已经有许多其他情况。

不用说，我们很兴奋，Rust社区已大力推进使MIR成为现实。编译器可以使用MIR引导并运行其测试套件，并且这些测试必须通过每个新的提交。一旦我们能够在启用MIR的情况下运行Crater并且在整个crates.io 生态系统中看不到任何回归，就默认情况下将其打开（或者，您将原谅一个可怕的（很棒的）双关语，将MIR发射到轨道上） 。

这篇博客文章首先概述了MIR的设计，并展示了MIR能够抽象出Rust语言的全部细节的一些方式。接下来，我们看一下MIR如何帮助实现非期望的掉落，这是人们一直以来所希望的优化。如果您在这篇文章之后发现自己渴望更多，请查看引入了MIR的RFC，或者直接进入代码。（编译器爱好者可能对“替代”部分特别感兴趣，该部分详细讨论了某些设计选择，例如为什么MIR当前不使用SSA。）

将Rust减少到一个简单的核心

MIR将Rust简化为一个简单的核心，删除了几乎每天使用的所有Rust语法，例如for循环，match 表达式，甚至方法调用。取而代之的是，将这些构造转换为一小组原始元素。这并不意味着MIR是Rust的子集。正如我们将看到的那样，其中许多基本操作在真正的Rust中不可用。这是因为这些原语可能会被误用于编写不安全或不受欢迎的程序。

MIR支持的简单核心语言不是您要编程的东西。实际上，它使事情变得非常痛苦。但是，如果您想编写类型检查器或生成汇编代码，那就太好了，因为现在您只需要处理在MIR转换后仍保留的核心操作。

为了理解我的意思，让我们从简化Rust代码的片段开始。首先，我们只是将Rust分解为“更简单的Rust”，但最终我们将完全脱离Rust，进入MIR代码。

我们的Rust示例从这个简单的for循环开始，该循环遍历向量中的所有元素并逐个处理它们：

for elem in vec {
    process(elem);
}

Rust本身提供了三种循环：for像这样的循环； while并while let循环，直到满足某些条件为止；最后是simple loop，它会反复进行直到您脱离它为止。这些循环中的每一个都封装了一个特定的模式，因此在编写代码时它们非常有用。但是对于MIR，我们希望将所有这些简化为一个核心概念。

forRust中的循环通过将值转换为迭代器，然后重复调用next该迭代器来工作。这意味着我们可以将for之前看到的循环重写为如下所示的while let循环：

let mut iterator = vec.into_iter();
while let Some(elem) = iterator.next() {
    process(elem);
}

通过应用这种重写，我们可以删除所有for循环，但是仍然留下多种循环。因此，接下来我们可以想象将所有while let循环重写为与loop组合的简单循环match：

let mut iterator = vec.into_iter();
loop {
    match iterator.next() {
        Some(elem) => process(elem),
        None => break,
    }
}

我们已经消除了两个构造（for循环和while 循环），但是我们可以走得更远。让我们从循环中稍微看一下我们看到的方法调用。在Rust中，方法调用 vec.into_iter()和iterator.next()也是一种 语法糖。这些特定的方法在特征中定义，这些特征基本上是预定义的接口。例如，into_iter 是特征中的一种方法IntoIterator。可以转换为迭代器的类型实现该特征并定义该into_iter 方法对它们的工作方式。同样，next在Iterator 特征中定义。当您编写类似的方法调用时iterator.next()，Rust编译器会根据程序类型自动确定该方法属于哪个特征iterator以及范围内的特征集。但是，如果我们希望更加明确，可以使用函数调用语法直接在trait中调用方法：

// Rather than `vec.into_iter()`, we are calling
// the function `IntoIterator::into_iter`. This is
// exactly equivalent, just more explicit.
let mut iterator = IntoIterator::into_iter(vec);
loop {
    // Similarly, `iterator.next()` can be rewritten
    // to make clear which trait the `next` method
    // comes from. We see here that the `.` notation
    // was also adding an implicit mutable reference,
    // which is now made explicit.
    match Iterator::next(&mut iterator) {
        Some(elem) => process(elem),
        None => break,
    }
}

在这一点上，我们已经设法减少了一些小片段的语言功能：我们现在只使用loop循环，而没有使用方法调用。但是，我们可以进一步降低集的概念，如果从移开loop并break朝更根本的问题：goto。使用goto我们可以将前面的代码示例转换为如下形式：

    let mut iterator = IntoIterator::into_iter(vec);

loop:
    match Iterator::next(&mut iterator) {
        Some(elem) => { process(elem); goto loop; }
        None => { goto break; }
    }

break:
    ...

我们已经将示例分解为更简单的结构。我们还没有完成，但是在继续之前，值得退一步来做一些观察：

一些MIR原语比它们替代的结构化结构更强大。从goto某种意义上说，引入关键字是一种极大的简化：它统一并替换了大量的控制流关键字。goto完全取代loop，break，continue，但它也使我们能够简化if和match以及（我们会看到更多的match尤其是在一个位）。然而，这种简化是唯一可能的，因为goto是一个更普遍的结构比 loop，这是我们不希望引入到适当的语言中的东西，因为我们不希望人们能够编写类似意大利面条的代码并具有复杂的控制流，而该流很难被阅读和遵循。但是在MIR中使用这样的构造很好，因为我们知道它只会以特定的方式使用，例如表示aloop或a break。

MIR构造是类型驱动的。我们看到，所有的方法调用（例如） iterator.next()都可以分解为完全合格的函数调用（例如）Iterator::next(&mut iterator)。但是，只有在具有完整类型信息的情况下，才能进行这种重写，因为我们必须（例如）知道类型，iterator以确定该next方法来自哪个特征。通常，只有在完成类型检查后才能构造MIR。

MIR使所有类型都明确。由于我们是在完成主要类型检查之后构造MIR，因此MIR可以包含完整的类型信息。这对于诸如借位检查器之类的分析很有用，此类分析需要使用局部变量的类型等，但也意味着我们可以定期运行类型检查器，作为一种健全性检查，以确保MIR格式正确。

控制流图

在上一节中，我将Rust程序逐步“解构”为类似于MIR的内容，但我们保持文本形式。但是，在编译器内部，我们绝不会“解析” MIR或以文本形式使用它。相反，我们将MIR表示为对控制流图（CFG）进行编码的 一 组数据结构。如果您曾经使用过流程图，那么控制流图的概念将非常熟悉。它是您的程序的一种表示形式，以一种非常清晰的方式公开了底层的控制流。

控制流图被构造为一组由边连接的基本块。每个基本块均包含一系列语句，并以终止符结尾，该终止符定义了各块之间的连接方式。使用控制流图时，循环只是在图中显示为一个循环，break关键字将转换为该循环之外的路径。

这是上一节中的运行示例，以控制流图表示：

控制流图

建立控制流图通常是任何类型的流量敏感分析的第一步。这也是LLVM IR的自然匹配，后者也以控制流图形式构建。MIR和LLVM彼此相当接近的事实使翻译变得非常简单。它还消除了错误的向量：在当今的编译器中，用于分析的控制流图不一定与LLVM构造所产生的控制流图相同，后者可能导致错误的程序被接受。

简化匹配表达式

上一节中的示例显示了如何将Rust的所有循环有效地简化为MIR中的gotos，以及如何删除方法调用以支持对特征函数的显式调用。但是它掩盖了一个细节：匹配表达式。

MIR的一大目标是将匹配表达式简化为很小的运算核心。为此，我们引入了两种主要语言不包含的构造：switch和 variant downcasts。就像goto，这些是我们在基本语言中不希望看到的东西，因为它们可能被误用于编写错误的代码。但它们在MIR方面表现很好。

通过示例解释匹配处理可能是最简单的。让我们考虑match上一节中看到的表达式：

match Iterator::next(&mut iterator) {
    Some(elem) => process(elem),
    None => break,
}

在这里，调用的结果next是type Option，其中T 元素的类型是。match因此，该表达式在做两件事：首先，它确定这Option是带有Some还是None变量的值。然后，在Some 变体的情况下，它将值提取elem出来。

在普通的Rust中，这两个操作是有意耦合的，因为我们不希望您从an读取数据，Option除非它具有Some变体（否则将实际上是C并集，其中不检查读取是否正确）。

但是，在MIR中，我们将变体的检查与数据的提取分开。我将首先以一种伪代码给出等效的MIR，因为这些操作没有实际的Rust语法：

loop:
    // Put the value we are matching on into a temporary variable.
    let tmp = Iterator::next(&mut iterator);

    // Next, we "switch" on the value to determine which it has.
    switch tmp {
        Some => {
            // If this is a Some, we can extract the element out
            // by "downcasting". This effectively asserts that
            // the value `tmp` is of the Some variant.
            let elem = (tmp as Some).0;

            // The user's original code:
            process(elem);

            goto loop;
        }
        None => {
            goto break;
        }
    }

break:
    ....

当然，实际的MIR是基于控制流图的，因此它看起来像这样：

回路中断控制流程图

明确的掉落和恐慌

因此，现在我们已经了解了如何从MIR中删除循环，方法调用和匹配项，并用更简单的等效项替换它们。但是，我们仍然可以简化一个关键领域。有趣的是，这在当今的代码中几乎是不可见的：在发生恐慌的情况下运行析构函数并进行清理。

在我们之前看到的示例控制流图中，我们假设所有代码都将成功执行。但实际上，我们不知道这一点。例如，我们看到的任何函数调用都可能会惊慌，这将触发展开。展开堆栈时，我们将必须为发现的任何值运行析构函数。确切地找出在恐慌的每个点上应该释放哪些局部变量实际上有些复杂，因此我们想在MIR中明确指出：这样，MIR的构造就必须弄清楚，但是以后的遍历只能依靠先生

我们这样做的方式有两个方面。首先，我们在MIR中使液滴明确。Drop是用于在值上运行析构函数的术语。在MIR中，每当控制流经过应该删除值的点时，我们都会添加一个特殊的drop(...)操作。其次，我们在控制流图中添加显式边缘以表示潜在的紧急情况以及我们必须执行的清除操作。

让我们先看一下显式丢弃。回想一下，我们从一个仅是for循环的示例开始：

for elem in vec { process(elem); } 然后，我们将此for循环转换为显式调用 IntoIterator::into_iter(vec)，产生一个value iterator，从中提取各种元素。好吧，这个值iterator 实际上有一个析构函数，将需要释放它（在这种情况下，它的工作是释放向量使用的内存vec；不再需要该内存，因为我们已经完成了对向量）。使用该drop操作，我们可以调整MIR控制流图以明确显示iterator释放值的位置。看一下新图，特别None是发现变体时会发生什么：

下降控制流程图

在这里我们看到，当循环正常退出时，一旦迭代器完成，我们将删除它。但是，如果出现恐慌怎么办？毕竟，我们在这里看到的任何函数调用都可能会惊慌。为了解决这个问题，我们在图表中引入了恐慌边缘：

应急控制流程图

在这里，我们已经panic在每个函数调用中引入了优势。通过查看这些边缘，您可以看到，如果对next或的调用 process感到恐慌，那么我们将删除该变量 iterator；但如果是对into_iter紧急事件的调用，则iterator 尚未初始化，因此不应删除它。

有趣的一面：我们最近批准了RFC 1513，它允许应用程序将紧急情况视为对的调用abort，而不是触发平仓。如果程序使用“紧急退出”语义进行编译，那么这也将反映在MIR中，因为在图形中根本没有紧急边缘和处理方法。

查看正在播放的MIR

此时，我们已将示例简化为与MIR实际外观相当接近的示例。如果您想亲自看看，可以在play.rust-lang.org上 查看我们示例的MIR。只需 点击此链接，然后按顶部的“ MIR”按钮即可。您将看到MIR的几个功能，因此您必须进行搜索以查找fn的开头 。（我不会在这里重现输出，因为它相当长。）在编译器本身中，您还可以启用graphviz输出。example

丢弃和堆栈标志

到目前为止，我认为您对MIR如何表示简化的Rust有所了解。让我们看一个示例，其中MIR将使我们能够实现对Rust的期待已久的改进：向非零下降的转变。这是对我们检测何时必须执行析构函数的方式的一种更改，尤其是在有时仅移动值的情况下。此举是在RFC 320中提出（并批准）的，但尚未实现。这主要是因为在MIR之前的编译器上执行此操作在架构上具有挑战性。

为了更好地了解功能是什么，请考虑以下函数send_if，该函数 有条件地将向量发送到另一个线程：

fn send_if(data: Vec<Data>) {
    // If `some_condition` returns *true*, then ownership of `data`
    // moves into the `send_to_other_thread` function, and hence
    // we should not free it (the other thread will free it).
    if some_condition(&data) {
        send_to_other_thread(data);
    }

    post_send();

    // If `some_condition` returned *false*, the ownership of `data`
    // remains with `send_if`, which means that the `data` vector
    // should be freed here, when we return.
}

如评论中所指出的，关键点在于我们无法静态地知道我们是否应该释放data。这取决于我们是否输入了if。

为了处理这种情况，编译器使用了zeroing。或者，更准确地说，是覆盖。这意味着，如果data移动了所有权 ，我们将data使用特定的，独特的位模式（不是有效的指针）来覆盖堆栈插槽（我们曾经使用零，因此通常将其称为零位，但是我们已经因为转移到其他地方）。然后，当需要释放时data，我们检查它是否被覆盖。（顺便说一句，这与等效的C ++代码大致相同。）

但是我们想做得更好。我们会希望做的是堆栈，告诉我们需要释放什么样的使用布尔标志。所以可能看起来像这样：

fn send_if(data: Vec<Data>) {
    let mut data_is_owned = true;

    if some_condition(&data) {
        send_to_other_thread(data);
        data_is_owned = false;
    }

    post_send();

    // Free `data`, but only if we still own it:
    if data_is_owned {
        mem::drop(data);
    }
}

当然，您不能在Rust中编写这样的代码。你不能访问变量data后if，因为它可能已被移动。（这是我们可以在MIR中做我们不希望在完全Rust中允许的事情的另一个示例。）

像这样使用布尔堆栈标志具有很多优点。首先，它更有效：我们不必覆盖整个向量，而只需设置一个标志。而且，优化也更容易：想象一下，通过内联或其他某种方式，编译器能够确定some_condition始终是正确的。在这种情况下，标准的常数传播技术会告诉我们这 data_is_owned始终是错误的，因此我们可以优化对的整个调用mem::drop，从而获得更紧凑的代码。有关更多详细信息，请参见 RFC 320。

但是，很难在当前的编译器体系结构上正确实现此优化。使用MIR，它变得相对简单。MIR控制流图明确告诉我们将在哪里删除值以及何时删除值。首次生成MIR时，我们假设删除移动的数据没有任何影响-大致类似于当前的覆盖语义。因此，这意味着MIR send_if可能看起来像这样（为简单起见，我将忽略展开的边缘）。

非归零的例子

然后，我们可以通过标识data移动或放置的每个位置并检查其中任何一个位置是否可以相互到达来变换此图 。在这种情况下，send_to_other_thread(data)区块可以达到drop(data)。这表明我们将需要引入一个标志，可以相当机械地完成它：

带标志的非调零

最后，我们可以应用标准的编译器技术来优化此标志（但是在这种情况下，需要该标志，因此最终结果将是相同的）。

为了说明MIR为何有用，让我们考虑一下send_if名为的函数的变体send_if2。此变体检查某些条件，如果满足，则将数据发送到另一个线程进行处理。否则，它将在本地处理它：

fn send_if2(data: Vec<Data>) {
    if some_condition(&data) {
        send_to_other_thread(data);
        return;
    }

    process(&data);
}

这将生成如下的MIR：

send_if2的控制流程图

和以前一样，data至少在开始时，我们仍然会在所有情况下生成的液滴。由于仍有一些动作可以稍后下降，因此我们现在可以像以前一样引入一个堆栈标志变量：

send_if2与标志

但是在这种情况下，如果我们应用恒定传播，我们可以看到在测试的每个点上data_is_owned，我们都静态地知道它是对还是错，这将使我们能够删除堆栈标志并优化上面的图，从而得出结果：

优化的send_if2

结论

我希望MIR的使用在编译器可以完成的工作方面具有很大的变革性。通过将语言简化为一组基本的原语，MIR为许多语言改进打开了大门。我们在这篇文章中查看了下降标志。另一个例子是改进Rust的生命周期系统，以 利用控制流图来提高精度。但是我认为会有很多我们尚未预见到的应用。实际上，已经出现了一个这样的例子：Scott Olson在开发MIR解释器miri方面已经取得了长足的进步，并且正在探索的技术很可能构成编译器本身中更强大的常量评估器的基础。

在编译器中向MIR的过渡尚未完成，但是已经非常接近了。特别感谢Simonas Kazlauskas（nagisa）和Eduard-Mihai Burtescu（eddyb），他们对将MIR推向终点线都产生了特别大的影响。我们最初的目标是将我们的LLVM代换成仅由MIR运行。移植借阅检查器的工作也正在进行。在那之后，我希望我们将在当前使用HIR的编译器上移植许多其他代码。如果您有贡献，请在IRC上查找带有标签A-mir的 问题或在#rustc频道中询问 。