LLVM上的Dart

这是一个有关使用LLVM编译器框架编译Dart语言的实验的故事。 从表面上看这毫无意义,因为

Dart已经拥有出色的虚拟机,该虚拟机使用即时编译来获得出色的性能。 由于Dart是动态类型的(更准确地说,它是可选类型的),因此JIT编译器是很自然的选择-它可以使用运行时可用的类型来执行静态编译器无法执行的优化。

LLVM上的Dart看上去很傻的另一个原因是,尽管名称如此,LLVM并不是虚拟机,直到最近它才不适合带有垃圾回收的语言。 适当地,我们的意思是:

  • 移动,精确(无泄漏)GC
  • 高度优化

这是因为,一旦优化器修改了代码,您就再也找不到在堆栈上可以使用GC的指针了。 一种常见的策略是将所有指针移到特殊的内存区域,但这在现代编译器中击败了许多优化策略,后者依赖于局部变量的寄存器分配来发挥其魔力。 您可能具有良好的GC或完整的性能,但不能兼而有之。

但是,LLVM领域正在迎来新的风。 最近,LLVM以实验性Statepoint功能的形式增加了一些GC支持。 各种勇敢的小组都使用了此方法,包括LLV8实验的幕后工作人员和Azul,他们正在将其用作其JVM的新顶层编译器。

看起来,基于LLVM构建真实的VM已从“不可能完成任务”变成了仅“难以完成任务”。 同时,强模式使Dart更具静态类型,而动态性更差。 另外,我们在Google上正在为iOS开发Flutter,该应用禁止JIT编译。 这两个方面的发展都使Dart更适合LLVM项目的目标和权衡。

为什么选择LLVM?

LLVM是一个现代的,维护良好的开源编译器框架,它为我们提供了许多免费的优化和平台。 例如,有一个完整的内联通道可以将任何函数内联到任何其他函数中,并包含何时执行此操作的启发式方法。

它看起来也像一个开放,欢迎的社区,欢迎大家的贡献。

实验目标

  • 在预先编译的场景中,上下文是“强模式飞镖”
  • 评估使用Statepoint支持进行精确移动GC的可行性
  • 评估表现

方法

我们(Erik Corry和Dmitry Olshansky)基于不连续的“ Dartino”运行时进行了实验。 这是针对小型设备进行优化的实验性Dart运行时。 与使用DartVM作为基础相比,它具有一些优势:

  • Martin Kustermann为Dartino建立了一个实验性LLVM后端。 它没有GC支持,因此在内存不足时崩溃了。
  • Dartino利用了Dart2JS的许多机制,因此不需要完整的解析器,前端等。我们用作输入的Dartino字节码已经降低了许多困难的Dart功能。 例如,闭包是对象,并且可选参数已变成不同版本的函数。
  • 我们俩都已经熟悉Dartino。
  • Dartino具有相对完整的运行时,并且能够运行大型应用程序,例如托管Dart2JS。 它没有很多Unix IO支持,并且线程模型不同,因此它不是临时替代品。

达蒂诺垃圾分类

现有的Dartino LLVM实验是从Dartino分支出来的,当时的GC非常简单(半空间Cheney收集器,无代数,大停顿,内存占用量增加了2倍)。 我们从Dartino的主要分支中挑选出一些变化,以获得具有写壁垒的更传统的2代GC。 没有读取障碍,并且没有并发GC,收集是世界一流的(尽管LLVM状态点确实支持这些功能,并且Azul在其封闭源VM中几乎肯定会使用它们)。

我们没有从较新的Dartino版本中挑选紧凑的老一代支持。

建筑

上面的管道显示了从Dart源代码到机器代码的路径。 在实际的实现中,第一部分将被替换为基于“内核”格式的东西(准备好的Dart源前端)。

转换为LLVM和高级优化

llvm-codegen链接到我们自己的LLVM副本,并执行高级优化。 在此阶段,LLVM维持以下假设:指针在各个GC上均有效,但是指针标记有非默认的“地址空间”,这禁止LLVM以存在移动GC时不正确的方式推理其位模式。 各种自定义LLVM内部函数用于标记可能发生GC的点。

由于带有标记的指针,LLVM位代码非常丑陋,具有大量的强制转换和添加。 因此,本文档包含“ LLVM伪代码”,而不是真正的.ll文件。 如果您习惯使用实际的.ll文件,这将看起来像“婴儿的第一个.ll babblings”,对不起! 以下代码表示mem2reg之后的动态调度的代码,该过程将本地变量从堆栈提升到SSA寄存器中:

我们将其与常规的JITing DartVM以及DartVM for Flutter中添加的新的提前支持进行了比较。 基准测试来自Dartino。

运行一个像Hello World这样短暂的程序,主要显示了启动时间。 基于JIT的系统花费时间来编译代码,并且这两种非LLVM解决方案都在启动时反序列化数据堆。

性能结论

我们的性能可与Flutter现有的提前技术相媲美(这是一个不断变化的目标-这些测量是在2016年11月下旬在功能强大的64位Linux工作站上进行的)。 JIT仍有很长的路要走。 我们正在运行的Dartino分支的垃圾收集性能并不高。
我们还测量了启动时间。 Dartino-LLVM为类,常量和调度表生成静态数据。 这些文件是由高度优化的ld.linux运行时链接程序加载的,并且它们的加载速度比当前的Dart AOT数据堆快照更快,从而为启动提供了非常好的性能。 对于启动测试,CPU调速器设置为“性能”。

兼容性说明

对于本研究,我们并未特别关注获得100%Dart兼容性。 进行“困难的事情”即GC和异常处理就足够了,以证明它们是可能的。 在某些情况下,我们采用了一种捷径,表明可以在不浪费时间实际实施实际解决方案的情况下实现实际解​​决方案。 这是我们妥协的一些地方:

  • 像Dartino一样,我们没有无限精度的整数。 但是,我们会检查所有int运算是否溢出,并动态切换到带框的数字表示形式(但是,带框的表示形式只有64位,用于包装)。
  • 在no-such-method(本质上是失败的类型检查)上,我们没有遵循完整的Dart语义,包括调用no-such-method方法并检查与丢失方法同名的getter。并使用’call’方法返回一个对象。 但是,我们确实在安全点(可以进行分配的点)抛出异常。
  • 我们不检查调用中堆栈是否溢出,也不检查回送边缘是否中断。 LLVM确实对此有实验性支持。 我们正在比较的解决方案确实支持这一点。 V8的经验表明,解决此问题可能会导致大约10%的性能下降。
  • 我们的前端编译器是经过修改的Dart2JS。 自Dartino停产以来,它没有跟上对语言的最新更改,因此有些测试我们无法运行。
  • Dart异常处理是完全实现的,与无方法相关的异常无关。 为此,我们使用了内置于LLVM的异常处理支持,该支持看起来足以胜任该任务,并且与Dart的异常模型(在本质上与LLVM为其设计的C ++并没有太大不同)保持一致。

总体而言,我们通过了Dartino可以通过的几乎90%的测试。 在失败的原因中,最大的原因是编译器前端存在问题,以及处理无此类事件的问题。

在大约11.6%的失败测试中,以下是失败原因的细分:

结论

实验性LLVM GC支持似乎在x64上具有全部功能。
原型的性能与我们更成熟的基于DartVM的提前解决方案相当。

对于性能分析,我们没有使用Dart强模式,可以期望它会产生发挥LLVM优势的优化机会。 但是,我们正在使用一些我们认为是现实的封闭世界的假设。

我们能够仅使用未打补丁的LLVM ToT版本(在上面的管线图上以蓝色标记)来编译从LLVM位代码到机器代码的最后阶段。 在此阶段(-O3)进行的优化未引起我们观察到的任何错误编译或GC问题。

未来

尚未决定如何以及是否将这种方法用于Dart或Flutter,但是这里有一些关于有趣途径的随机想法可以探索。

  • 使用C ++-with-handles以外的本地语言编写运行时例程。 后端将是LLVM-with-Statepoints。 (当前分支中有一个Forth小实验,但是要比其中最简单的本机例程编写更多代码,还需要更强大的功能)。
  • 包装64位整数会有什么影响?
  • 在仍然允许大型项目的并行编译的同时,我们如何使用全程序知识来生成代码?

参考文献

LLVM GC支持http://llvm.org/docs/Statepoints.html
Dartino-LLVM存储库https://github.com/dartino/sdk/tree/llvm
修改后的LLVM存储库https://github.com/ErikCorryGoogle/llvm
UrsHölzle博士:http://hoelzle.org/publications/urs-thesis.pdf
LLV8:https://github.com/ispras/llv8