Lib.rs

› 编程语言 › wasmtime-cli
#优化 #DSL #side #cranelift #编译器 #peephole #指令

peepmatic

用于生成窥孔优化器的 DSL 和编译器

由 Alex Crichton、Dan Gohman、Nick Fitzgerald、wasmtime-publish 以及 95 位贡献者 开发。 合作拥有者 Bytecode Alliance。

12 个重大版本更新

0.78.0 2021 年 10 月 29 日
0.76.0 2021 年 8 月 2 日
0.75.0 2021 年 6 月 9 日
0.72.0 2021 年 3 月 16 日
0.66.0 2020 年 7 月 16 日

#534 in 编程语言

Download history 5/week @ 2024-05-19 6/week @ 2024-06-09 8/week @ 2024-06-16 1/week @ 2024-06-23 139/week @ 2024-07-28

每月 139 次下载
用于 peepmatic-souper

Apache-2.0 WITH LLVM-exception

390KB
6.5K SLoC

peepmatic

peepmatic 是 Cranelift 的窥孔优化器的 DSL 和编译器。

关于

Peepmatic 是一个用于窥孔优化的 DSL 和将这些优化编译成生成窥孔优化器的编译器。用户用 DSL 编写一组优化，然后 peepmatic 将优化集编译成高效的窥孔优化器。

DSL ----peepmatic----> Peephole Optimizer

生成的窥孔优化器将所有优化的左侧合并到一个紧凑的自动机中，这使得匹配候选指令序列变得快速。

DSL 的优化可以手动编写或使用像 Souper 这样的超级优化器机械地发现。最终，peepmatic 应该有一个验证器，确保 DSL 的优化是正确的，类似于 Alive 对 LLVM 优化所做的那样。

示例

以下是我们 DSL 的一个片段，描述了移除无操作的冗余位或指令的优化

(=> (bor $x (bor $x $y))
    (bor $x $y))

(=> (bor $y (bor $x $y))
    (bor $x $y))

(=> (bor (bor $x $y) $x)
    (bor $x $y))

(=> (bor (bor $x $y) $y)
    (bor $x $y))

编译成窥孔优化器自动机时，它们看起来像这样

优化 DSL

单个窥孔优化器有两个部分

  1. 一个 左侧，它描述了优化应用到的候选指令序列。
  2. 右侧包含新的指令序列，用于替换左侧匹配的旧指令序列。

左侧可以绑定子表达式到变量，右侧可以包含这些绑定的变量以重用子表达式。左右两侧的操作是clif操作的子集。

让我们看一个例子

(=> (imul $x 2)
    (ishl $x 1))

如你所见，DSL使用S表达式。（S表达式易于解析，我们已经有了一组用于S表达式的优秀解析基础设施，用于我们的wat和wast包。）

这个优化的左侧是(imul $x 2)。它匹配乘以常量二的整数乘法操作。乘以二的值绑定到变量$x。

这个优化的右侧是(ishl $x 1)。它重用了左侧绑定的$x变量。

这个优化将形式为x * 2的表达式替换为x << 1。这是因为乘以二是与二进制整数左移一位相同的操作，而且这是可取的，因为左移指令比乘法指令执行周期更少。

优化的通用形式是

(=> <left-hand-side> <right-hand-side>)

变量

变量以美元符号开头，后跟小写字母、数字、连字符和下划线：$x、$y、$my-var、$operand2。

左侧模式可以包含匹配任何子表达式的变量，并为其命名，以便在右侧重用。

;; Replace `x + 0` with simply `x`.
(=> (iadd $x 0)
    $x)

在模式中，具有相同名称的变量的每个出现都必须匹配相同的值。也就是说，(iadd $x $x)匹配(iadd 1 1)，但不匹配(iadd 1 2)。这使得我们可以编写这样的优化

;; Xor'ing a value with itself is always zero.
(=> (bxor $x $x)
    (iconst 0))

常量

我们已经看到了模式中的特定整数字面值和通配符变量，但我们也可以匹配任何常量。这些与变量书写类似，但使用大写字母而不是小写：$C、$MY-CONST和$OPERAND2。

例如，我们可以使用常量模式将一个iconst和一个iadd组合成一个单独的iadd_imm指令

(=> (iadd (iconst $C) $x)
    (iadd_imm $C $x))

嵌套模式

模式也可以匹配具有自己嵌套的嵌套操作

(=> (bor $x (bor $x $y))
    (bor $x $y))

前提条件和转义

让我们重新考虑我们的第一个例子优化

(=> (imul $x 2)
    (ishl $x 1))

这种优化过于具体。这是我们希望支持的另一种优化版本的优化

(=> (imul $x 4)
    (ishl $x 2))

我们不想编写这类优化的一般化实例！这会造成大量重复，也可能使生成的窥视孔优化器的匹配自动机规模膨胀。

相反，我们可以通过匹配任何乘以2的幂的常数C并将其替换为左移log2(C)

首先，我们想要匹配任何常数变量C，而不是直接匹配2

(imul $x $C)

请注意，变量以小写字母开头，而常量以大写字母开头。常量模式$C和变量模式$x都会匹配5，但只有变量模式$x会匹配整个子表达式，如(iadd 1 2)。常量模式$C仅匹配常量值。

接下来，我们通过使用when形式将一个模式包裹起来，给左手边的模式增加一个前置条件，要求常数$C必须是2的幂。

;; Our new left-hand side, augmenting a pattern with a precondition!
(when
  ;; The pattern matching multiplication by a constant value.
  (imul $x $C)

  ;; The precondition that $C must be a power of two.
  (is-power-of-two $C))

在右手边，我们使用取消引用来在编译时评估log2($C)。取消引用通过使用$(...)形式完成

;; Our new right-hand side, using unqouting to do compile-time evaluation of
;; constants that were matched and bound in the left-hand side!
(ishl $x $(log2 $C))

最后，这里是结合了新的左右两边的一般优化

(=> (when (imul $x $C)
          (is-power-of-two $C))
    (ishl $x $(log2 $C)))

位宽

与Cranelift的指令类似，peepmatic优化也是位宽多态的。除非另有说明，否则模式将匹配操作i32与操作i64等一样。一个不约束其模式位宽的优化必须对所有位宽都有效

  • 1
  • 8
  • 16
  • 32
  • 64
  • 128

例如，要限制一个优化仅匹配i32，可以使用bit-width前置条件

(=> (when (iadd $x $y)
          (bit-width $x 32)
          (bit-width $y 32))
    ...)

或者，您可以通过在操作符后面放置花括号内的类型来给一个操作指定一个类型，如下所示

(=> (when (sextend{i64} (ireduce{i32} $x))
          (bit-width $x 64))
    (sshr (ishl $x 32) 32))

实现

Peepmatic大约有四个阶段

  1. 解析
  2. 类型检查
  3. 线性化
  4. 自动化

（我说“大约”，因为在线性化和自动化之后还有几个微阶段。但那四个是主要阶段。）

解析

解析将DSL源文本转换为抽象语法树（AST）。

我们使用the wast crate。它为我们提供了带有源上下文的格式化错误，以及一些其他通常很有用的解析基础设施。

相关源文件

  • src/parser.rs
  • src/ast.rs

类型检查

类型检查在抽象语法树（AST）上操作。它检查优化中类型和位宽是否都有效。例如，它确保优化的左侧和右侧的类型和位宽相同，因为用布尔表达式替换整数表达式是没有意义的。

类型检查完成后，某些AST节点被分配一个类型和位宽，这些类型和位宽随后在线性化和匹配以及应用优化时使用。

我们遍历AST并收集类型约束。每个约束都与源文件中的一个范围相关联。我们将这些约束交给Z3。在存在类型错误的情况下（即Z3返回unsat），我们通过z3::Solver::get_unsat_core获取相互冲突的约束，并通过约束关联的范围将类型错误报告给用户。

使用Z3不仅使得实现类型检查比以往更容易，而且还使得未来通过搜索反例输入扩展类型检查更加容易。也就是说，输入的右侧不等于左侧，这意味着优化是不一致的。

相关源文件

  • src/verify.rs

线性化

线性化将优化AST转换为线性形式。目的是使自动化步骤中的自动机构建更加容易，同时简化语言以便于匹配和应用优化。

每个优化的左侧被转换为一系列

  • 匹配操作，
  • 到达要应用操作的指令/值/立即数的路径，以及
  • 操作预期的结果。

所有匹配操作都必须有预期的结果，优化才能应用于指令序列。

每个优化的右侧被转换为一系列构建动作。这些是描述如何构建右侧的命令，前提是左侧已经匹配。

相关源文件

  • src/linearize.rs
  • src/linear_passes.rs
  • crates/runtime/src/linear.rs

自动化

自动化将一组线性优化组合成一个转换自动机。这个自动机是最终的、编译后的窥孔优化。目标是尽可能多地从所有线性优化中去除重复内容，产生尽可能紧凑且缓存友好的表示。

普通自动机可以告诉你它是否匹配输入字符串。它可以看作是一组字符串的紧凑表示。转换器是一种自动机，它不仅匹配输入字符串，还可以将它们映射到输出值。它可以看作是一组字典或映射的紧凑表示。通过使用转换器，我们不仅去除了匹配操作的词首和词尾，还去除了右侧构建动作。

发出转换器中的每个状态都与一个匹配操作和路径相关联。从这个状态的转换是基于匹配操作的结果。每个转换可以选择累积一些RHS构建动作。当我们达到最终状态时，RHS构建动作已经完成，可以解释为应用匹配的优化。

构建转换自动机的相关源文件是

  • src/automatize.rs
  • crates/automata/src/lib.rs

解释转换器并应用优化的运行时的相关源文件是

  • crates/runtime/src/optimizations.rs
  • crates/runtime/src/optimizer.rs

参考

我在设计peepmatic时发现这些资源很有帮助

致谢

感谢 Jubi Taneja、Dan Gohman、John Regehr 和 Nuno Lopes 在设计讨论中提供意见以及分享有用资源！

依赖项

~23MB
~483K SLoC