编译器与应用密码学的激动人心的交汇：Cairo和MLIR

制作 Cairo

不重复造轮子

---

我喜欢爵士乐。

在我喜爱的所有爵士乐风格中，我最喜欢爵士融合乐，因为我发现不同事物的融合更具启发性。

在编程语言理论、编译器实现和应用密码学的交叉领域，一些令人兴奋的事情正在发生。

但爵士融合乐的问题在于，除非你熟悉被组合的元素，否则很难入门。

让我给你们展示几首歌，以及我们是如何将它们混合在一起的。

如果你熟悉以下主题之一，请耐心等待；我保证 это 值得的。

系好安全带。

3, 2, 1...

入门节奏

编译器 & LLVM

大约 20 多年前，伊利诺伊大学的一组编译器研究人员需要一个更灵活的基础设施。

他们开发的东西后来被称为 LLVM，并且已经成为最重要的编译器工具项目。

它为 Clang、Swift、Rust 和更多语言的许多编译器的分析和代码生成组件提供支持。

来自 2004 年 CGO 的介绍性 论文：

LLVM 编译器框架和代码表示结合了关键功能，这些功能对于程序的实际、终身分析和转换非常重要。

LLVM 的核心是 LLVM IR，它的中间表示。

IR 是数据格式和算法的组合，允许工具以最佳方式表达它希望保证或证明的代码属性。

一个例子是 LLVM IR 是所谓的 SSA 形式，或静态单赋值，其中每个变量只会被赋值一次。

这使得编译器可以比其他编译器更好地推理它。 否则，它能够进行分析和优化，例如消除死代码、常量传播和常量折叠，并促进其他阶段，例如寄存器分配。

总而言之，IR 是编译器编写者通过构建抽象阶梯来解决问题的方式，而 LLVM 成为现代编译器事实上的后端平台。

人工智能的兴起

你可能知道机器学习算法及其应用现在很重要。

作为许多经济财富的驱动因素和解决我们以前只能梦想解决的问题的方案，人工智能的统计学派已经确定（？）了一组技术，包括处理大量数字矩阵上的数值运算，并将大量这些运算串在一起形成计算图。

这些计算图的基本要素是矩阵乘法、Rollup、数据操作和数据移动。

这听起来计算量非常大，的确如此。 因此，该行业已经（并且正在）竭尽全力扩展这些方法，使其在越来越大的数据集上更便宜、更有效。

在某个时刻，人们发现了一个关键的观察结果：这些算法解决的许多问题都具有内在或给定的并行性，并且我们已经拥有专门为令人尴尬的并行数值问题而设计的工业生产机器，即在 GPU 上运行的着色器。

因此，这项工作的第一个浪潮是将视频显卡硬件重新用于这个新领域。

为什么我们从 LLVM 转到 AI 和显卡？ 因为随着它们的成熟，这些算法、模型、技术、工具和库被标准化为可以被许多非专业程序员使用的框架，并且需要适当的语言来表达它们及其编译器。

由于 LLVM 具有一个 IR，可以通过一些努力将其抽象到 GPU 处理器上，因此它被用于 PyTorch 和 Tensorflow 等工具中，以生成将在这些图形处理单元上运行的代码。

设计了新的硬件，并且再次使用 LLVM 来定位这些新的张量处理单元。

因此，Tensorflow 在其中嵌入了几个由不同供应商制造的编译器组件：Google 具有 XLA，NVIDIA 具有 TensorRT，Intel 具有 NGraph，所有这些都与 TensorFlow 优化器和代码生成器集成，并且与硬件非常相关，但不共享通用基础设施。

回到语言

自从 2000 年代初期以来的这些年里，钟摆已经从动态类型语言摆回了具有更高级类型系统和代码分析阶段的静态类型语言。

LLVM 支持 Clang 和新的语言，例如 Rust、Julia 和 Swift。

这些项目的一个共同点是，他们发现许多语言实现问题最好在更高的抽象级别上建模，并实现他们的中间表示来解决特定领域的问题，例如特定于语言/库的优化、流敏感类型检查（例如，对于线性类型），并改进降低过程的实现。

Swift 有 SIL，Rust 有 MIR，等等。

换句话说，人们开始意识到低级 IR 之上的软件堆栈的复杂性非常高，因为软件重用率低且质量差异很大。

经过二十年的硬件目标扩展和问题空间变化，人们发现 LLVM 在某些领域存在不足。

什么（是 MLIR？）

由此产生了 MLIR（多级中间表示），这是一个由 Chris Lattner 等人启动的项目，旨在构建一个通用基础设施来支持所有这些不同的子系统，并从 LLVM 开发过程中的错误和经验教训中吸取教训。

我强烈建议你阅读介绍性的 论文（这些图形就是出自这里），因为它非常易于阅读，或者收听 Lattner 和 Shpeisman 给出的 演讲。

MLIR 旨在解决软件碎片化问题，改进异构硬件的编译，显著降低构建特定领域编译器的成本，并帮助连接现有编译器。

中间表示有几种类型：线性（如汇编，指令序列）、树状（如 AST）和图状（如数据流图或调用图）。

正如项目网站所述，“MLIR 旨在成为一种混合 IR，可以在统一的基础架构中支持多种不同的要求。”

与 LLVM IR 不同，在 LLVM IR 中，一个中央 IR 包含一组完整的指令来表示 CPU/GPU 程序，而在 MLIR 中，没有一个 IR。

相反，MLIR 提供了一组非常抽象的概念：方言、操作、区域等。

来自词汇表：

> 方言是一组可用于扩展 MLIR 系统的功能。
> 方言在其中创建一个唯一的命名空间，在其中定义新的操作、属性和类型。
> 这是扩展 MLIR 的基本方法。
> 通过这种方式，MLIR 是一种元 IR：其可扩展框架允许它以许多不同的方式被利用

操作是 MLIR 中的代码单元。

操作是 MLIR 表示的所有代码和计算的构建块。

它们是完全可扩展的（没有固定的操作列表），并且具有特定于应用程序的语义。

在实现代码发射器时，操作可以映射到处理器指令。

在实现 AST 时，表示类型转换、函数调用和语言操作数的节点可以映射到操作。

操作可以具有任意数量的操作数、结果和属性，并且可以包含任意数量的区域。

区域是 MLIR 块的控制流图。

块或基本块是没有控制流的操作的顺序列表。

请注意，这会创建一个嵌套的 IR 结构，因为区域由块组成，而块又由操作列表组成。

区域是一种强大的机制，可以允许嵌套操作和本地化信息，从而简化代码分析和转换。

模块是包含单个区域的操作，该操作包含由操作组成的单个块，从而为 MLIR 操作提供组织结构。

MLIR 允许多个方言（甚至是 MLIR 代码库之外的方言）在一个模块中共存。

在 MLIR 的上下文中，转换与翻译不同。

以方言表示的代码的转换称为转换。 它可以是方言间的（当转换成另一种方言中语义上等效的表示时）或方言内的。 相比之下，翻译是 MLIR 和外部表示之间的转换。

因此，使用 MLIR 的应用程序通常会根据需要使用方言集合。

LLVM 有什么优势？

因此，你正在编写编译器或需要向现有编译器添加后端。

除了整个行业的代码重用之外，MLIR 还能提供什么优势？ 为什么你会选择它而不是 LLVM？

首先，选择不是那么二元的，因为 MLIR 包含一个 LLVM IR 方言，你可以将特定于应用程序的方言转换为它，从而利用现有的 LLVM 工具链。

MLIR 还试图提供可以应用于合适操作的通用模式或过程，而无需对它们进行硬编码。

因此，MLIR 允许你轻松定义你的方言，从不断增长的针对不同计算模型的中低级方言生态系统中进行选择，并将它们集成到你的特定领域编译器中。

正如 Lei Zhang 所说：

换句话说，如果 LLVM IR 本质上是集中的，并且倾向于统一的编译器流程，那么 MLIR 基础设施及其方言生态系统本质上是分散的，并且倾向于多样化的编译器流程。

非常强大的是，MLIR 能够使用相同的基础架构表示不同的级别； 因此，不同级别之间的流程可以变得无缝。

UNIX 式的方式！

其他好处包括：

• 默认情况下跟踪源代码位置（每个操作数都有一个源代码内存地址属性，因此错误直接指向发生错误行代码）
• 所有函数默认在多个内核上运行
• 可以重用其他语言完成的优化
• 重用 LLVM 进行机器代码生成

最后，假设你的领域确实受益于在 GPU、TPU 或 ASIC 中运行全部或部分代码。 在这种情况下，MLIR 提供了一种通过编写到它的转换并插入最终翻译的代码生成器来重用针对该计算模型和硬件的现有方言的方法。

它包括用于 SPIR-V 的方言，一个通用的 GPU 方言，以及用于 NVidia 和 AMD GPU 的特定方言。

所有这些优势都是 MLIR 抽象级别的直接结果。

为什么？

让我们再次改变曲调。

在区块链、加密货币和分布式金融的领域，几个发展趋势汇合在一起：

首先，更成熟的区块链已经与机器学习领域的故事相提并论，尽可能多地将哈希卸载到 GPU，然后卸载到 ASIC（让我们这些凡人争先恐后地争夺残羹剩饭，或者辞职在我的 Raspberry Pi 上玩 emacs Tetris）。

较新的链和 L2 预计会遵循相同的路径。

其次，随着它们的应用变得越来越主流（尽管有起有落），两个问题已成为中心舞台：可扩展性和隐私。

区块链的效率不高是出了名的，因此，人们一直在努力实现两全其美，部分原因是放弃了 Proof of Work，将工作转移到 L2，并转向密码技术提供的保证。

随着新技术的发现和旧技术的成熟，零知识证明系统已经成为构建这些问题的解决方案的主要领域。

但众所周知，尽管有大量的把关措施，密码学并不是周末就可以掌握并“滚动自己的东西”的东西，尤其是在 ZKP 等发展领域。

这不仅仅是因为它们的正确使用很复杂，或者许多组件仍处于 alpha 阶段，而是因为将编程语言中的计算转换为可以输入到这些密码原语的形式需要大量的工作和一些独创性。

大多数 ZKP 协议都涉及算术化，这是以数字格式表示计算的过程，该格式可供证明系统使用，通常是通过获取计算中的指令并构建操作位数的表达式图（称为算术电路），然后生成 执行跟踪 ，简而言之，它是一个字段元素矩阵，表示计算随时间的演变。

此执行跟踪被馈送到证明者。

为了封装这些过程，设计并实现了虚拟机来生成这些数值执行跟踪并提供计算保证，例如 Miden 和 cairo-rs。

有了虚拟机后，你需要一个编译器和一个中间表示。

你也不能只接受任何程序，因为你需要知道它的执行是可证明的，除非你愿意接受非终止程序、消耗过多 gas 的无效事务、生成无效或不完整跟踪以及证明者中途退出的可能性。

编译器中的类型理论和中间表示已成为生成具有我们可以机械地推理和检查的属性的代码的最有效工具之一。

简而言之，在更多样化的硬件上运行、整合编程语言技术、轻松使用复杂的密码原语、将保证从开发人员工具传输到执行层，所有这些都共同促成了加密世界中语言实现的一小次复兴。

Cairo & Sierra

Cairo 是一种“用于通过使用基于 STARK 的有效性证明来创建通用计算的可证明程序的语言”。

如果你没有密码学背景，那么 ZKP 和 STARKS 对于一篇涵盖如此多主题的文章来说过于深入了； STARK 通过有效地证明计算的完整性来支持区块链扩展。

STARK（可扩展、透明的知识论证）是一种证明系统，可以证明和验证计算。

它允许处理大型计算，生成计算正确性的证明，并在极少的步骤中验证该证明。

• www.starknet.io

随着 Cairo 的成熟，添加了诸如实现类似于 Rust 的所有权的线性类型系统和提供保证的中间表示等改进。

用 Cairo 编程与你常用的基于冯诺依曼机的语言略有不同：用它编写的程序在非确定性、不可变的连续内存模型下运行，以确保所有相关内存都具有适当的值，并且在生成证明之前不会销毁适当的值，即所有正确的程序都是可证明的。

Cairo 编译器最终会将 Cairo 代码编译成“Cairo 汇编”，虚拟机运行该汇编来计算结果并生成跟踪。

但是，如前所述，并非所有表示都适合所有任务，因此 Cairo 引入了 Sierra（ S afe I nt E rmediate R ep R esent A tion）。

Sierra 的目标是保证生成的代码始终是可证明的，它通过多种方式实现此目标。

如前所述，内存模型是不可变的和连续的，并保证内存不会被写入两次，因此，对值的提取引用 reference 不会失败。

线性类型系统确保值仅使用一次，

没有循环，而是使用递归； 加上操作的 gas 计量器，这确保了终止。

断言和错误会转换为条件分支。

为什么要在 Cairo 的上下文中使用 MLIR？

Cairo 还用于构建 StarkNet，这是一个无需许可的以太坊Layer2网络，可以在该网络上部署可证明的智能合约。

网络上的节点接收交易，并且必须在进行生成证明的业务之前验证它们是否有效。

必须使用交易输入运行合约代码才能生成状态更改、证明和验证。

另一个动机是开发者体验和工具质量。

在部署上述合约之前，必须编写和测试代码，并且能够更快地运行 Cairo 代码可以缩短开发周期中的周转时间。

• 能够更快地检查 Cairo 合约 TX
• 更快的 Gas 计算
• 为了支持更好的 L2 排序器
• 为了支持更好的开发人员工具

Sierra 结构

那么 Sierra 是什么样的呢？

我们很快会看到一些例子。

简而言之，Sierra 是一种线性中间表示。

Sierra 程序由四个部分组成：

特定程序中使用的类型

使用的 libfuncs

程序语句

用户定义函数的描述

/// 一个完整的 Sierra 程序。
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Program {
    /// 所有用户类型的声明。
    pub type_declarations: Vec<TypeDeclaration>,
    /// 所有使用的库函数的声明。
    pub libfunc_declarations: Vec<LibfuncDeclaration>,
    /// 程序的代码。
    pub statements: Vec<Statement>,
    /// 函数的描述 - 签名和入口点。
    pub funcs: Vec<Function>,
}

Libfuncs（或库函数）表示对内置函数的调用，这些内置函数的实现经过审核以确保正确，然后编译为 Cairo 汇编。

内置 libfuncs 实现是通用的，可以根据 libfunc 声明部分中的定义进行专门化。

语句可以调用 libfunc 或返回变量，并且按顺序执行：

/// 一个可能的声明。
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum GenStatement<StatementId> {
    Invocation(GenInvocation<StatementId>),
    Return(Vec<VarId>),
}

用户定义的函数具有一个标识符、它们的类型签名和参数，以及一个语句标识符，该标识符在程序语句中标记函数入口点。

pub type Function = GenFunction<StatementIdx>;

/// 表示一个函数（其名称、签名和入口点）。
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct GenFunction<StatementId> {
    /// 函数的名称。
    pub id: FunctionId,
    /// 参数类型和返回类型。
    pub signature: FunctionSignature,
    /// 函数的参数。
    pub params: Vec<Param>,
    /// 函数开始的语句 id。
    pub entry_point: StatementId,
}

如何（使用 MLIR）？

在我们的应用程序上下文中，Cairo 和 StarkNet 软件堆栈，其中大部分正在转换为 Rust 或用 Rust 开发，因此我们希望与此语言无缝集成。

MLIR 具有与 C 兼容的 API（https://mlir.llvm.org/docs/CAPI/），可以很容易地进行接口。

mlir-sys 提供到此接口的自动生成绑定，melior 提供围绕它的稍微更惯用的包装器。

MLIR 作为一个库是 LLVM 发行版的一部分，因此如果你拥有最新的 LLVM 作为系统库，你将可以访问 MLIR。

我们的项目位于 github.com/lambdaclass/cairo_sierra2mlir。

你可以找到详细的设置说明，这些说明应该让你拥有一个可用的开发环境。 在 Apple 硬件上进行开发时，如果你不想自己编译，那么商店购买的 brew 提供的 LLVM 系统库就可以了。

我们的首要任务是解析提供的 Sierra 程序。

幸运的是，Cairo 编译器库提供了出色的功能：

cairo_lang_sierra::ProgramParser::new()
            .parse(fs::read_to_string(input).unwrap().as_str())
            .unwrap(),

一旦我们在内存中拥有 Sierra 表示，我们就可以开始翻译过程。

这是一个高级概述：

stateDiagram-v2
    direction LR
    state "加载 sierra 程序" as Sierra
    state "初始化编译器" as init
    state "初始化执行引擎" as engine
    state if_skip_jit <<choice>>
    state "加载 MLIR 方言" as dialects
    state "创建内置模块" as module
    state "创建 libc 包装器" as libc
    state "流程类型" as types
    state "流程库函数" as libfuncs
    state "保存非流程函数信息" as func_info
    state "流程函数" as funcs
    state "计算每个函数的块范围" as blocks
    state "流程语句" as statements
    state "应用 MLIR 流程" as passes
    [*] --> 初始化
    state 初始化 {
        sierra --> init
        init --> if_skip_jit
        if_skip_jit --> engine: 如果 JIT
        if_skip_jit --> dialects: 如果编译
        engine --> dialects
    }
    初始化 --> 编译
    state 编译 {
        module --> libc
        libc --> types
        types --> libfuncs
        types --> func_info
        func_info --> libfuncs
        libfuncs --> funcs
        funcs --> blocks
        blocks --> statements
    }
    编译 --> passes
    passes --> 输出
    输出 --> [*]

第一步是初始化我们的机器。

我们需要创建我们的方言和上下文并注册它们。 上下文包含 IR、方言和流程，并拥有各种对象，例如类型、位置和方言实例。

let registry = dialect::Registry::new();
register_all_dialects(&registry);
let context = Context::new();
context.append_dialect_registry(&registry);
context.load_all_available_dialects();
register_all_llvm_translations(&context);

我们还需要为内置模块创建一个带有块的区域：

let location = Location::unknown(&context);
let region = Region::new();
let block = Block::new(&[]);
region.append_block(block);
let module_op = operation::Builder::new("builtin.module", location)
    .add_regions(vec![region])
    .build();
let module = Module::from_operation(module_op).unwrap();

初始化完成后，我们可以通过按顺序处理类型、libfuncs、函数和语句来开始转换。 我们不会详细介绍，但我们可以看一个令人兴奋的例子，它足够短，可以检查其转换过程：一个执行字段元素加法和减法的程序，并了解如何处理 libruls。

对于 Sierra 程序 libfunc 声明部分中的每个函数声明，将匹配 libfunc 名称，并且编译的执行将分派给适当的 Rust 函数。

这个简单的函数接受一个 Felt（一个 252 位字段元素）并返回一个带有两个值的结构：

fn something(a: felt252) -> (felt252, felt252) {
    (a + 2, a - 2)
}

cairo 编译器输出以下 Sierra：

type felt252 = felt252;
type Tuple<felt252, felt252> = Struct<ut@Tuple, felt252, felt252>;

libfunc felt252_const<2> = felt252_const<2>;
libfunc dup<felt252> = dup<felt252>;
libfunc felt252_add = felt252_add;
libfunc felt252_sub = felt252_sub;
libfunc struct_construct<Tuple<felt252, felt252>> = struct_construct<Tuple<felt252, felt252>>;
libfunc store_temp<Tuple<felt252, felt252>> = store_temp<Tuple<felt252, felt252>>;

felt252_const<2>() -> ([1]);
dup<felt252>([0]) -> ([0], [3]);
felt252_add([3], [1]) -> ([2]);
felt252_const<2>() -> ([4]);
felt252_sub([0], [4]) -> ([5]);
struct_construct<Tuple<felt252, felt252>>([2], [5]) -> ([6]);
store_temp<Tuple<felt252, felt252>>([6]) -> ([7]);
return([7]);

simple::simple::something@0([0]: felt252) -> (Tuple<felt252, felt252>);

尽管级别很低，但仍然可读：

• 将值 2 的 felt 常量声明到内存单元 1 中
• 将内存单元 0 中的值复制到单元 3 中
• 将内存单元 1 中的值添加到单元 3 中的值，并将结果放入单元 2 中
• 将值 2 的 felt 常量声明到内存单元 4 中
• 从单元 0 中的值中减去内存单元 4 中的值，并将结果放入单元 5 中
• 使用单元 2 和 5 中的值构造一个类型为 <felt252, felt252> 的元组，并将其放入单元 6 中
• 将此值存储在单元 7 中，以准备返回它
• 返回单元 7 中的值

这个简单示例中的重点是 "felt252_add" libfunc，它实现了字段元素的加法。

让我们看看这是如何在我们的 MLIR 方言中实现的：

我们将需要一个带有多个块的区域，一个其中发生计算，另一个我们将返回导致数字大于或等于字段素数的值，另一个用于返回小于字段素数的值。

我们获取参数，执行加法，并根据字段素数检查结果。

此条件由 MLIR cf 方言中的 op_cond_br 条件branch 操作表示，该方言

... 包含低级（即非基于区域）的控制流结构。

这些结构通常直接在控制流图的 SSA 块上表示控制流。

cond_br 终止操作表示对布尔值（1 位整数）的条件分支。 如果设置了该位，则跳转到第一个目的地； 如果为假，则选择第二个目的地。

在我们的例子中，由于成瘾在字段中的工作方式，如果结果大于字段素数，我们可以简单地减去素数值来换行。 换句话说，如果结果更大，则跳到 gte_prime_block 或“大于素数块”，否则，跳到 in_range_block.

    pub fn create_libfunc_felt_add(
        & 'ctx self,
        func_decl: &LibfuncDeclaration,
        parent_block: BlockRef<'ctx>,
        storage: &mut Storage<'ctx>,
    ) -> Result<()> {
        let id = func_decl.id.debug_name.as_ref().unwrap().to_string();
        let sierra_felt_type = SierraType::Simple(self.felt_type());
        let felt_type = sierra_felt_type.get_type();
        let felt_type_location = sierra_felt_type.get_type_location(&self.context);

        let region = Region::new();
        //计算发生的块
        let entry_block = Block::new(&[felt_type_location, felt_type_location]);
        //用于包装 >= PRIME 的块
        let gte_prime_block = Block::new(&[]);
        //用于返回 < PRIME 的值的块
        let in_range_block = Block::new(&[]);

        // res = lhs + rhs
        let lhs = entry_block.argument(0)?.into();
        let rhs = entry_block.argument(1)?.into();
        let res_op = self.op_add(&entry_block, lhs, rhs);
        let res = res_op.result(0)?.into();

        // gt_prime <=> res_result >= PRIME
        let prime_op = self.prime_constant(&entry_block);
        let prime = prime_op.result(0)?.into();
        let gte_prime_op = self.op_cmp(&entry_block, CmpOp::UnsignedGreaterThanEqual, res, prime);
        let gte_prime = gte_prime_op.result(0)?.into();

        // if gt_prime
        self.op_cond_br(&entry_block, gte_prime, &gte_prime_block, &in_range_block, &[], &[]);

        // gt prime block
        let wrapped_res_op = self.op_sub(&gte_prime_block, res, prime);
        let wrapped_res = wrapped_res_op.result(0)?.into();
        self.op_return(&gte_prime_block, &[wrapped_res]);

        // in range block
        self.op_return(&in_range_block, &[res]);

        region.append_block(entry_block);
        region.append_block(in_range_block);
        region.append_block(gte_prime_block);
        let func = self.op_func(
            &id,
            &create_fn_signature(&[felt_type, felt_type], &[felt_type]),
            vec![region],
            FnAttributes::libfunc(false, true),
        )?;

        parent_block.append_operation(func);
        storage.libfuncs.insert(
            id,
            SierraLibFunc::create_function_all_args(
                vec![sierra_felt_type.clone(), sierra_felt_type.clone()],
                vec![sierra_felt_type],
            ),
        );
        Ok(())
    }

这是对应于 felt252_add libfunc 的 MLIR：

  func.func @felt252_add(%arg0: i256, %arg1: i256) -> i256 attributes {llvm.dso_local, llvm.linkage = #llvm.linkage<internal>, passthrough = ["norecurse," "alwaysinline," "nounwind"]} {
    %0 = arith.addi %arg0, %arg1 : i256
    %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 = arith.constant 3618502788666131213697322783095070105623107215331596699973092056135872020481 : i256
    %1 = arith.cmpi uge, %0, %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 : i256
    cf.cond_br %1, ^bb2, ^bb1
  ^bb1:  // pred: ^bb0
    return %0 : i256
  ^bb2:  // pred: ^bb0
    %2 = arith.subi %0, %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 : i256
    return %2 : i256
  }

正如你所看到的，我们有三个基本块，第一个的最后一条指令是一个条件跳转。

这是在经过注册的流程之前，整个生成的 MLIR：

module {
  func.func @felt252_add(%arg0: i256, %arg1: i256) -> i256 attributes {llvm.dso_local, llvm.linkage = #llvm.linkage<internal>, passthrough = ["norecurse," "alwaysinline," "nounwind"]} {
    %0 = arith.addi %arg0, %arg1 : i256
    %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 = arith.constant 3618502788666131213697322783095070105623107215331596699973092056135872020481 : i256
    %1 = arith.cmpi uge, %0, %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 : i256
    cf.cond_br %1, ^bb2, ^bb1
  ^bb1:  // pred: ^bb0
    return %0 : i256
  ^bb2:  // pred: ^bb0
    %2 = arith.subi %0, %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 : i256
    return %2 : i256
  }
  func.func @felt252_sub(%arg0: i256, %arg1: i256) -> i256 attributes {llvm.dso_local, llvm.linkage = #llvm.linkage<internal>, passthrough = ["norecurse," "alwaysinline," "nounwind"]} {
    %0 = arith.subi %arg0, %arg1 : i256
    %c0_i256 = arith.constant 0 : i256
    %1 = arith.cmpi slt, %0, %c0_i256 : i256
    cf.cond_br %1, ^bb2, ^bb1
  ^bb1:  // pred: ^bb0
    return %0 : i256
  ^bb2:  // pred: ^bb0
    %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 = arith.constant 3618502788666131213697322783095070105623107215331596699973092056135872020481 : i256
    %2 = arith.addi %0, %c3618502788666131213697322783095070105623107215331596699973092056135872020481_i256 : i256
    return %2 : i256
  }
  func.func @"struct_construct<Tuple<felt252, felt252>>"(%arg0: i256, %arg1: i256) -> !llvm.struct<packed (i256, i256)> attributes {llvm.dso_local, llvm.linkage = #llvm.linkage<internal>, passthrough = ["norecurse," "alwaysinline," "nounwind"]} {
    %0 = llvm. mir.undef : !llvm.struct<packed (i256, i256)>
    %1 = llvm.insertvalue %arg0, %0[0] : !llvm.struct<packed (i256, i256)>
    %2 = llvm.insertvalue %arg1, %1[1] : !llvm.struct<packed (i256, i256)>
    return %2 : !llvm.struct<packed (i256, i256)>
  }
  func.func @"simple::simple::something"(%arg0: i256) -> !llvm.struct<packed (i256, i256)> attributes {llvm.dso_local, llvm.emit_c_interface} {
    cf.br ^bb1(%arg0 : i256)
  ^bb1(%0: i256):  // pred: ^bb0
    %c2_i256 = arith.constant 2 : i256
    %1 = call @felt252_add(%0, %c2_i256) : (i256, i256) -> i256
    %c2_i256_0 = arith.constant 2 : i256
    %2 = call @felt252_sub(%0, %c2_i256_0) : (i256, i256) -> i256
    %3 = call @"struct_construct<Tuple<felt252, felt252>>"(%1, %2) : (i256, i256) -> !llvm.struct<packed (i256, i256)>
    return %3 : !llvm.struct<packed (i256, i256)>
  }
}

太棒了，我们已经使用几个内置的 dialect 和我们自己的 dialect 将 Sierra 转换为了 MLIR。

为了能够运行我们的代码，我们需要将其降级到可以运行的东西。

目前，一个极好的选择是 LLVM IR，因为我们希望将我们的 Cairo 代码作为原生 CPU 指令运行，并且可以使用非常可靠的 LLVM 基础设施将 LLVM IR 编译为二进制对象。

我们还希望利用 MLIR 和 LLVM 的 pass manager 基础设施，以利用它提供的优化。

我们创建一个 pass manager 并添加我们希望代码经历的 pass：

    let pass_manager = pass::Manager::new(&compiler.context);
    register_all_passes();
    pass_manager.add_pass(pass::conversion::convert_func_to_llvm());
    pass_manager.add_pass(pass::conversion::convert_scf_to_cf());
    pass_manager.add_pass(pass::conversion::convert_cf_to_llvm());
    pass_manager.add_pass(pass::conversion::convert_arithmetic_to_llvm());
    pass_manager.add_pass(pass::conversion::convert_index_to_llvm());
    pass_manager.add_pass(pass::conversion::convert_math_to_llvm());
    pass_manager.add_pass(pass::conversion::convert_memref_to_llvmconversion_pass());
    pass_manager.add_pass(pass::conversion::convert_reconcile_unrealized_casts());
    if optimized {
        pass_manager.add_pass(pass::transform::canonicalizer());
        pass_manager.add_pass(pass::transform::inliner());
        pass_manager.add_pass(pass::transform::symbol_dce());
        pass_manager.add_pass(pass::transform::cse());
        pass_manager.add_pass(pass::transform::sccp());
    }
    pass_manager.enable_verifier(true);
    pass_manager.run(&mut compiler.module)?;

    let op = compiler.module.as_operation();
    if op.verify() {
        if debug_info {
            Ok(op.debug_print())
        } else {
            Ok(op.to_string())
        }
    } else {
        Err(color_eyre::eyre::eyre!("error verifying"))
    }
}

这些 pass 做什么？

• convert_func_to_llvm: 转换 func 方言，其中包含围绕高阶函数抽象的操作，例如调用，转换为 llvm 方言，该 方言 通过定义相应的操作和类型将 LLVM IR 映射到 MLIR 中。
• convert_scf_to_cf: 将 scf（结构化控制流，带有循环和 ifs）方言 转换为 cf（控制流）方言，用 CFG 替换结构化控制流。 在 LLVM 中，你必须分析分支以检测循环。 SCF 处于更高的抽象级别。
• convert_cf_to_llvm: 将 cf 方言 转换为 llvm 方言。
• convert_arithmetic_to_llvm: 将 arith 方言（包含基本的整数和浮点数学运算）转换为 llvm 方言。
• convert_math_to_llvm: 将 math 方言（包含超出简单算术的整数和浮点类型的数学运算）转换为 llvm 方言。
• convert_index_to_llvm: 将 index 方言（包含用于操作内置索引类型值的操作）转换为 llvm 方言。
• convert_memref_to_llvmconversion_pass: member 方言 旨在保存核心成员创建和操作操作，这些操作与任何特定的其他 方言 或域抽象没有强关联。
• convert_reconcile_unrealized_casts: 此 pass 简化并消除未实现的转换强制转换操作，这些操作通常由部分 方言 转换引入，这些转换以传递方式将一个值转换为同一类型的另一个值。

我们将应用的优化 pass 包括：

• canonicalize: 规范化操作。 此 pass 通过迭代应用所有已加载 方言 的规范化模式，直到达到不动点或耗尽最大迭代/重写次数，从而对一组操作执行各种类型的规范化。 规范化是编译器 IR 设计的重要组成部分：它使得更容易实现可靠的编译器转换并推理代码中什么是更好或更差，并且它迫使人们对特定级别的 IR 的目标进行有趣的讨论。 大多数编译器都有规范化 pass，有时它们有许多不同的 pass（例如，LLVM 中的 inst-combine、dag combine 等）。 由于 MLIR 是一种多级 IR，因此它可以提供单一的规范化基础设施，并在它表示的许多不同的 IR 中重用它。
• more inline: more inline pass 内联函数调用。
• symbol_dce: 此 pass 删除所有被发现无法访问的符号。
• cse: 此 pass 实现了用于公共子表达式消除的通用算法。
• sccp: 此 pass 实现了用于稀疏条件常量传播的通用算法。 该算法检测已知为常量的值，并乐观地将其传播到整个 IR 中。 任何被证明是常量的值都会被替换并在可能的情况下删除。

执行

现在，我们在优化的 MLIR 中有程序的内存表示。 我们如何执行我们的代码？

MLIR 提供了一个 ExecutionEngine，它接受一个模块并期望它可以转换为 LLVM IR，然后使用 LLVM JIT ExecutionEngine 编译并运行它。

该引擎还必须知道执行的入口点，以下示例来自 Fibonacci 函数的基准测试：

let program = ProgramParser::new().parse(include_str!("programs/fib.sierra")).unwrap();

let engine = ExecutionEngine::new(
    &compiler.module,
    2,
    &[\
        &format!(\
            "{}/libmlir_c_runner_utils.{}",\
            run_llvm_config(&["--libdir"]).trim(),\
            env!("SHARED_LIB_EXT"),\
        ),\
        env!("S2M_UTILS_PATH"),\
    ],
    false,
);

unsafe {
    engine.invoke_packed("fib::fib::main", &mut []).unwrap();
};

结论

如前所述，MLIR 是一个年轻的项目。

虽然有大量的案例研究和 用户 足够多，可以看看日落的天空，并沉思，“这就是道路”，但有一些注意事项。

首先，虽然很明显该项目已经做出了努力，但文档很少。

API 已记录在案，并且有一些很棒的入门教程，但是如果你偏离了指定的路径，你最终会查看测试代码、其他项目以及反复试验。

其次，该项目是用 C++ 编写的。

它提供了一个 C 兼容的 API，可以使用该 API 用你的语言制作绑定，但它正在开发中且不稳定。

Python 绑定也在开发中，默认情况下未启用。

Rust 绑定在某种程度上是自动生成的，并且不是很成熟。

你最终可能不得不构建一些工具来构建此工具，以构建你想要发布的工具，也称为尤为棘手的 yak shaving。

第三，像任何强大的工具一样，它可以让人们在高抽象级别上进行操作，它要求你能够弥合抽象层并真正了解你的目标以及你在实现目标时面临的障碍。

必须具备编译器技术以及所涉及的技术和词汇的知识。

也许随着更多的成熟，可以制造其他工具，这些工具可以为更具体的领域隐藏复杂性。

我们要向 LLVM 和 MLIR 以及 Cairo 背后的团队和社区致敬并感谢他们。

基础技术很少见，难以开发，并且需要极大的洞察力和远见才能达成一致。

这些石头感觉像是伟大事物的基础。

参考文献和资源

• MLIR Homepage
• 2019 EuroLLVM Developers’ Meeting: T. Shpeisman & C. Lattner “MLIR: Multi-Level Intermediate Representation Compiler Infrastructure” Video and Slides
• MLIR Tutorial Video and Slides
• Yizhou Shan's notes on MLIR
• Lei Zhang's "Compilers and IRs: LLVM IR, SPIR-V, and MLIR"
• Starkware glossary: STARKs, StarkEx, and StarkNet
• Starkware: Cairo 1.0
• Starkware: Cairo 1.0 is here

• 原文链接： blog.lambdaclass.com/cai...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～