为 Futhark 添加新后端需要做些什么

What it takes to add a new back end to Futhark

Source | HN Comments

这篇文章探讨了为 Futhark 编译器添加新后端的流程。文章首先阐述了添加后端的复杂程度差异，从简单的代码生成到异构硬件的全新后端。核心在于，Futhark 使用中间表示（IR）和后端动作（Action）来支持多种目标。添加新后端涉及选择合适的 IR 方言，编写 Action 来处理 IR，并将其与编译流程连接。文章还提供了编写后端的建议，包括利用现有的 Imp 代码生成机制，以及针对不同目标语言的建议。最后，鼓励开发者寻求帮助，并强调了文档的不足。

The Futhark Programming Language High-performance purely functional data-parallel array programming

Fork me on GitHub

为 Futhark 添加新后端需要做些什么

Posted on March 4, 2025

最近 Scott Pakin 建议写一篇关于如何向 Futhark 编译器添加新后端的博客文章，而且目前正在积极地对后端进行调整，所以这并不是一个坏主意。首先，让我们管理一下期望：这不会是一个关于添加后端的教程。我不会深入探讨应该使用的特定内部 API 的细节。相反，我将专注于核心表示，并让大家了解添加新后端所需的工作类型（通常很复杂）和规模（有时相对较小）。 “后端”的确切含义也有一些开放性。添加一个 futhark foo bar.fut 命令来基于 bar.fut 生成某些东西（非常容易）与实现另一个类似 C 的 GPU 后端（不难，但你需要接触很多部分）之间存在显著的复杂性差异，创建一个用于异构硬件的全新后端（取决于你的需求，可能极具挑战性）。

我仍然会链接相关的源代码片段（如果适用） - 有时，将复杂的部分粘合在一起是多么简单（或过于简单）是很有启发性的。 Futhark 编译器目前支持相当多样化的目标（顺序 CPU、多核、不同的 GPU API、C、Python）。为了在不过度重复代码和工作的情况下实现这一点，编译器使用了程序编译的高度参数化表示。我会尽量传达要点，但完整的细节非常……详细（而且我总是觉得它们应该简化 - 这不是我们最引以为豪的编译器方面）。

对于更枯燥的阐述，还有内部编译器文档。

架构概述

Futhark 编译器是一个用 Haskell 编写的单体程序。所有 pass 和后端都是同一个可执行文件的一部分。原则上，用不同的语言编写后端作为单独的可执行文件并非难事，尽管到目前为止这还没有意义。

编译器由三个主要部分组成：

前端，负责解析 Futhark 源代码语言，进行类型检查，并将其转换为核心中间表示 (IR)。
中端，对以各种 IR 格式（稍后会详细介绍）表示的程序进行逐步细化、转换和优化。
后端，将 IR 表示转换为某些较低级别的表示，例如 C - 可能会经过多个步骤。

这些部分形成一个链。编译器将始终运行前端，最终生成程序的中间表示，然后运行适当的中端pipeline，生成程序的另一种表示，最后将其传递给后端。

无论你如何调用 Futhark 编译器（futhark c、futhark cuda 等），前端几乎都是相同的，但中端和后端的行为会根据编译器模式而有很大差异。例如，编译器实际上拥有一系列适用于不同用途并在编译器的不同阶段使用的 IR 方言，而不是单一的 IR。为了让你了解我的意思，可以考虑一个可扩展的 Haskell 数据类型，用于表示非常简单的表达式：

[](https://futhark-lang.org/blog/<#cb1-1>)data Exp o = Var String
[](https://futhark-lang.org/blog/<#cb1-2>)      | Val Int
[](https://futhark-lang.org/blog/<#cb1-3>)      | Add (Exp o) (Exp o)
[](https://futhark-lang.org/blog/<#cb1-4>)      | Sub (Exp o) (Exp o)
[](https://futhark-lang.org/blog/<#cb1-5>)      | Op o

除了表示变量、值、加法和减法之外，这个 Exp 类型还有一个类型参数 o，它通过 Op 构造函数表示某些其他类型的操作。这意味着我们可以实例化一个包含平方根作为操作的 Exp 变体：

[](https://futhark-lang.org/blog/<#cb2-1>)data SqrtOp = Sqrt ExpWithSqrt
[](https://futhark-lang.org/blog/<#cb2-2>)
[](https://futhark-lang.org/blog/<#cb2-3>)type ExpWithSqrt = Exp SqrtOp

但我们也可以有一个包含函数调用的通用概念：

[](https://futhark-lang.org/blog/<#cb3-1>)data FunOp = Fun String [ExpWithFun]
[](https://futhark-lang.org/blog/<#cb3-2>)
[](https://futhark-lang.org/blog/<#cb3-3>)type ExpWithFun = Exp FunOp

现在我们可以编写对 Exp o 值进行操作的函数，只要我们使用如何处理 o 情况的参数（使用函数参数、类型类或任何其他方式）来参数化这些函数。当我们想要拥有一组大致相同的类型时，此技术很有用。例如，在 Futhark 编译器的中端，我们最初使用一个名为 SOACS 的 IR 方言，其中并行性是使用与源语言非常相似的嵌套高阶运算来表示的。最终，程序会经历一个扁平化转换，之后并行性使用不同的扁平并行操作词汇来表示。后来，即使类型的表示也从类似于源语言的东西变成了包含关于内存布局的信息的表示。 IR 的大多数语言级别细节，例如如何表示算术和控制流，保持不变，并且许多编译器代码（例如简化 pass）也是如此，它们可以在任何方言上运行。

实际表示比上面解释的要复杂一些，并且与论文 Trees that Grow 中描述的方法非常相似。特别是，类型级别函数用于避免为每个可以变化的事物使用不同的类型参数。

我们在整个中端和后端中普遍使用这种 IR 方言的概念。中端使用基于编译模式的 pipeline，最终生成某种 IR 方言的程序。也就是说，pipeline 可以被认为是纯函数，从某种 IR 方言到某种其他（或相同）IR 方言。对于 c 后端，此方言称为 SeqMem （没有并行性，具有关于数组布局和分配的信息），对于 multicore 和 ispc 后端，它是 MCMem（多核并行操作），对于 GPU 后端，它被称为 GPUMem。你可以在此处查看一些默认 pipeline。

因此，编写新后端包括选择一个将 IR 转换为你希望的方言的 pipeline，然后对该 IR 执行 某些操作 - 编译器实际上对该 某些操作 是什么持不可知态度。并非每个后端都需要不同的 IR 方言 - 例如，所有 GPU 后端都使用相同的 IR 方言。

后端动作

在 Futhark 编译器实现的行话中，“后端”被称为“动作”，它本质上是在中端 pipeline 的结果上运行的任意过程：

[](https://futhark-lang.org/blog/<#cb4-1>)data Action rep = Action
[](https://futhark-lang.org/blog/<#cb4-2>) { actionName :: String,
[](https://futhark-lang.org/blog/<#cb4-3>)  actionDescription :: String,
[](https://futhark-lang.org/blog/<#cb4-4>)  actionProcedure :: Prog rep -> FutharkM ()
[](https://futhark-lang.org/blog/<#cb4-5>) }

这里 rep 是一个类型级别 token，表示动作接受的 IR 方言，FutharkM 是一个支持 IO 效果的 monad，这意味着这些“动作”可以执行任意 IO。例如，futhark c 的动作将在纯 Haskell 代码中进行大量代码生成，但也会写入一些文件并运行 C 编译器：

[](https://futhark-lang.org/blog/<#cb5-1>)compileCAction :: FutharkConfig -> CompilerMode -> FilePath -> Action SeqMem
[](https://futhark-lang.org/blog/<#cb5-2>)compileCAction fcfg mode outpath =
[](https://futhark-lang.org/blog/<#cb5-3>) Action
[](https://futhark-lang.org/blog/<#cb5-4>)  { actionName = "Compile to sequential C",
[](https://futhark-lang.org/blog/<#cb5-5>)   actionDescription = "Compile to sequential C",
[](https://futhark-lang.org/blog/<#cb5-6>)   actionProcedure = helper
[](https://futhark-lang.org/blog/<#cb5-7>)  }
[](https://futhark-lang.org/blog/<#cb5-8>) where
[](https://futhark-lang.org/blog/<#cb5-9>)  helper prog = do
[](https://futhark-lang.org/blog/<#cb5-10>)   cprog <- handleWarnings fcfg $ SequentialC.compileProg versionString prog
[](https://futhark-lang.org/blog/<#cb5-11>)   let cpath = outpath `addExtension` "c"
[](https://futhark-lang.org/blog/<#cb5-12>)     hpath = outpath `addExtension` "h"
[](https://futhark-lang.org/blog/<#cb5-13>)     jsonpath = outpath `addExtension` "json"
[](https://futhark-lang.org/blog/<#cb5-14>)
[](https://futhark-lang.org/blog/<#cb5-15>)   case mode of
[](https://futhark-lang.org/blog/<#cb5-16>)    ToLibrary -> do
[](https://futhark-lang.org/blog/<#cb5-17>)     let (header, impl, manifest) = SequentialC.asLibrary cprog
[](https://futhark-lang.org/blog/<#cb5-18>)     liftIO $ T.writeFile hpath $ cPrependHeader header
[](https://futhark-lang.org/blog/<#cb5-19>)     liftIO $ T.writeFile cpath $ cPrependHeader impl
[](https://futhark-lang.org/blog/<#cb5-20>)     liftIO $ T.writeFile jsonpath manifest
[](https://futhark-lang.org/blog/<#cb5-21>)    ToExecutable -> do
[](https://futhark-lang.org/blog/<#cb5-22>)     liftIO $ T.writeFile cpath $ SequentialC.asExecutable cprog
[](https://futhark-lang.org/blog/<#cb5-23>)     runCC cpath outpath ["-O3", "-std=c99"] ["-lm"]
[](https://futhark-lang.org/blog/<#cb5-24>)    ToServer -> do
[](https://futhark-lang.org/blog/<#cb5-25>)     liftIO $ T.writeFile cpath $ SequentialC.asServer cprog
[](https://futhark-lang.org/blog/<#cb5-26>)     runCC cpath outpath ["-O3", "-std=c99"] ["-lm"]

这里 SequentialC.compileProg 函数执行实际的 C 代码生成。我将详细说明一下，但在架构层面上，它在做什么方面根本不受限制。原则上，一个动作可以只是将最终 IR 转储到磁盘并运行一些完全不同的程序来处理代码生成。你甚至可以编写一个动作，该动作期望程序仍然处于早期的 IR 方言之一，例如那些没有内存信息的方言，甚至仍然具有嵌套并行性的方言。如果你的目标是其他一些（相对）高级语言，这可能是合适的。

最终，如果你希望编写一个不需要新的 IR 方言，也不需要重用任何现有 C 生成机制的后端，那么这实际上非常容易 - 至少就与编译器的集成而言是这样。

要将 pipeline 与一个动作连接起来，并生成可以通过命令行调用的东西，你需要编写一个大致是样板文件的 main 定义，比如这个用于 futhark Haskell 的定义：

[](https://futhark-lang.org/blog/<#cb6-1>)main :: String -> [String] -> IO ()
[](https://futhark-lang.org/blog/<#cb6-2>)main = compilerMain
[](https://futhark-lang.org/blog/<#cb6-3>) ()
[](https://futhark-lang.org/blog/<#cb6-4>) []
[](https://futhark-lang.org/blog/<#cb6-5>) "Compile sequential C"
[](https://futhark-lang.org/blog/<#cb6-6>) "Generate sequential C code from optimised Futhark program."
[](https://futhark-lang.org/blog/<#cb6-7>) seqmemPipeline
[](https://futhark-lang.org/blog/<#cb6-8>) $ \fcfg () mode outpath prog ->
[](https://futhark-lang.org/blog/<#cb6-9>)  actionProcedure (compileCAction fcfg mode outpath) prog

然后最后将其连接到子命令的大列表中。这就是全部了。

命令式代码生成

虽然一个动作可以是任意的命令式代码，但在实践中，所有 Futhark 基于 C 的后端（甚至Python 后端）都利用了大量的共享基础设施，以避免不得不过于频繁地重新发明轮子。

作为一个起点，Futhark 编译器定义了一个命令式中间表示，称为 Imp。与中端一样，Imp 实际上是一种可扩展的语言，具有各种方言。例如，顺序 ImpGen。与定义非常明确的功能性中端 IR 相比，Imp 更具有临时性，例如，没有解析器。从语义上讲，它很大程度上是 C 的简化形式。事实上，它甚至不是 SSA 形式，这仍然可以正常工作，因为我们没有在 Imp 级别进行任何优化。

从功能性 IR 到 Imp 的转换由一个名为 ImpGen 的模块完成。它是高度参数化的，因为它本质上必须从任意 IR 方言到任意 Imp 方言。它充满了实现细节，但并不特别有趣。

一旦编译器获得了程序的 Imp 表示，它就可以将该程序转换为 C 或 Python，甚至其他某种语言。这很大程度上是一个机械过程 - 从 Imp 到 C（或 Futhark 生成的巴洛克式 Python）的语义差距并不大，主要涉及将 Imp 构造映射到 Futhark 运行时系统（非常小）提供的工具，当然还要生成语法上有效的代码。为了简化三个 GPU 后端（cuda、opencl、hip）的维护，我们还使用了一个小型的 GPU 抽象层（gpu.h，在本文中讨论）。

编写后端的建议

Futhark 的设置并不是特别容易添加新后端，但也不是特别困难。毕竟，截至本文撰写之时，我们支持 10 种不同的后端。以下是给任何希望通过添加后端来寻求荣耀的潜在人员的一些建议：

如果你想以一种非常高级的并行语言为目标，那么只需使用 Futhark 的前端和中端，直到 SOACS 表示。这将为你提供一个单态一阶程序（除了并行操作），其中所有类型都是标量或标量数组，但仍然具有嵌套并行性，尽管该并行性将被很好地融合。我认为从这种表示形式为 fork-join 语言（例如 MPL）生成代码将是一个有趣的实验。
如果你想以一种稍微不那么高级的并行语言为目标，特别是那些不能很好地处理嵌套并行性的语言，那么可以考虑处理 GPU 表示的输出。尽管名称如此，但它并不是真正的 GPU 特定的（特定的部分可以忽略或修改，并且主要与元数据和调整有关），而只是保证不存在嵌套并行性。它仍然是高级的并且具有面向价值的语义，没有内存的概念。
如果你想以一种新的 GPU 后端为目标，那么实现 gpu.h 抽象层。 CPU 端工作的代码生成工作将会相当简单，尽管你可能仍然需要进行大量工作来生成实际的 GPU 内核代码。我们目前正在通过正在进行的 WebGPU 后端进行此过程，并且大多数挑战都与 WebGPU 的特殊限制有关（另一个帖子的主题），而不是与编译器工程有关。
如果你想生成任何类型的低级代码，那么你可能会发现使用其中一种具有内存信息的 IR 方言最容易。如果你想生成一些相对类似于 C 的东西（并且在这种情况下，生成例如机器代码或 JavaScript 都是“类似于 C”的），那么几乎可以肯定最容易使用现有的用于生成 Imp 的机制。

但是，在所有情况下，我都会说一个非常好的主意是联系一位 Futhark 开发人员寻求建议和帮助。让第三方添加一个新的后端并不是我们真正考虑过的事情（所有的后端都是在我们的密切监督下编写的），虽然按照编写编译器后端的标准，技术挑战并不是那么大，但文档并没有真正达到要求。但我当然会很高兴有人尝试一下。