NI LabVIEW 编译器：深层分析

guitarhua 2013-10-20

展开全文

概览

即便对无足轻重的编程语言来说，编译器的设计往往也是一个复杂的课题。即使对专业的软件工程师们来说，编译理论也需要考虑专业知识。现代的NI LabVIEW软件是一种多范例语言，包括广泛的多种类型的概念，包括数据流，支持面向对象，以及事件驱动编程。LabVIEW也覆盖了各种平台，服务多种操作系统(Windows, Linux, Mac),多种芯片组(PowerPC, Intel),甚至可以服务于嵌入式设备和现场可编程门阵列(FPGAs),它与传统的PC结构有明显不同。也许您会猜想，LabVIEW编译器是一个精密的系统，远远超出一般书面描述的范围。

编译与解释

LabVIEW是一种编译语言，它令人惊奇，因为它在一般的G开发过程没有任何明晰的编译步骤。取而代之的是，您可以对您的VI做出改动并简单地按下运行键来执行它。编译意味着您所写的G代码被转化为本地机器码然后被主机电脑直接执行。这种方法可供选择的另一种途径是解释，程序被另外的软件程序（叫做解释程序）间接地执行，而不是直接由电脑执行。

LabVIEW语言并没有要求其本身被编译或者解释；事实上，LabVIEW的第一个版本使用解释程序。在后来的版本，编译器取代了解释程序以提高VI运行时的性能，这是编译器与解释程序相比最常见的区别。解释程序更容易编写，并以较差的运行性能为代价，而编译器执行起来更加复杂但是却能提供更快的执行时间。LabVIEW编译器最主要的好处之一就是编译器对所有VIs的提高显而易见，而不必做出任何改变。实际上，LabVIEW 2010正式版的编译器进行了内部优化以加快VI的执行时间。

LabVIEW编译器的历史回顾

在急于深入讨论现在编译器内部组成之前，很值得总结一下编译器从20年前最早期版本到现在的发展。这里介绍的一些算法，例如类型传播法，聚丛法，以及内嵌法（inplaceness），在现代的LabVIEW编译器讨论中会更加详细地描述。

LabVIEW 1.0版本于1986上市。如前面提到的，LabVIEW在其第一个版本使用了解释程序并且仅为摩托罗拉68000服务。那时的LabVIEW语言非常简单，也减弱了其对编译器的需求（当时是解释程序）。例如，它不存在任何的多态数据类型，唯一的数据类型是扩展精度浮点数据。LabVIEW 1.1版本首次引入了内嵌（inplaceness）算法，或者称之为“内嵌程序”。此算法支持数据分配，因此您可以在执行的时候重新使用数据，避免了不必要的数据副本，相应地，常常能显著地提高执行性能。

在LabVIEW 2.0版本，解释程序被当前的编译器所取代。仍然专门为摩托罗拉68000服务，LabVIEW可以生成本地机器码。在2.0版本还增加了类传播算法，可以在不断完善的LabVIEW语言中发挥其它职能，处理语法检查与类型解析。LabVIEW 2.0另外一项重大的创新是聚丛程序的引入。聚丛算法支持LabVIEW图表的并行输入，并将节点归类为“丛”，它可以并行运行。类传播算法，嵌入法（inplaceness）以及聚丛算法直到目前也是现代LabVIEW编译器的重要组成部分，并随时间的推移显现出更多的新增改进。LabVIEW 2.5中新的编译器基本结构增加了对多种后端设备的支持，尤其是英特尔x86与 Sparc。LabVIEW 2.5也引入了连接器，当VIs需要被重新编译的时候，它可以管理VIs路径之间的从属关系。

在LabVIEW 3.1，除常数合并外，也增加了两个新的后端，PowerPC 与 HP PA-RISC。LabVIEW 5.0 与6.0 更新了编码生成程序，并增加了GenAPI,一种与多种后端连接的常用接口。GenAPI交叉编译对实时开发来说，是非常重要的。实时开发者一般在主机PC上编写VIs，而将其部署到（将它们编译到）实时对象。另外，一种循环不变代码移出的有限形式也包含在内。最终，LabVIEW多任务执行系统被扩展到支持多线程。

LabVIEW 8.0创建的基于5.0版本引入的GenAPI基本结构，新增了寄存器分配算法。在GenAPI引入之前，每个节点的生成码都是由寄存器硬件编码的。不可执行编码的有限形式以及死码删除也被引入。LabVIEW 2009具有64 位 LabVIEW与数据流中间表示(DFIR)。DFIR立即被用于创建更先进形式的循环不变代码移出，常数合并，死码删除以及不可执行编码删除。2009新语言的特点，例如并行循环，都是基于DFIR创建。

最终，在LabVIEW 2010，DFIR提供了新的编译器优化，例如代数重组，公共子表达式消除，循环展开，以及subVI直接插入。此正式版本也包括在LabVIEW编译器链中采用了低阶虚拟机(LLVM)。LLVM是一种开放源代码的编译器基本结构，广泛应用于工业生产。使用LLVM，新增了很多优化，例如指令调度，循环外提，指令组合，条件传播，以及一种更精密的寄存器分配程序。

当今的编译器

当对LabVIEW编译器的历史有了基本了解后，您现在可以探索现代LabVIEW的编译器了。首先，回顾高级的多种类型编译步骤概述，然后更加详细地浏览每一部分。

一个VI编译的第一步是类传播算法。这复杂的一步是为了解析适于终端输入的隐含类型，并检测语法错误。在G编程语言所有可能的语法错误都在类传播算法这一步被检测。如果算法确定VI有效，编译继续。

在类传播后，VI首先被从结构图编辑器使用的模型转化为编译器使用的DFIR。一旦转化为DFIR，编译器对DFIR图执行几个变换，分解它，优化它，并使其为生成代码做好准备。很多编译器的优化——例如，内嵌程序（inplacer）与丛聚程序——被执行转化并在本步运行。

在DFIR图标被优化与简化后，它被翻译成LLVM中间表示。对LLVM一些列的扫描被执行，通过中间表示来进一步优化并降低其阶次，最终变为机器码。

类传播

如先前提到的，类传播算法解析类型并检测程序错误。实际上，此算法包括如下几个方面的功能：

解析隐藏类型使其适于终端输入
解析subVI调用并确定其合法性
计算纵向
检验VI的周期
检测并报告语法错误

此算法在您对VI进行每个改动后运行，以确定VI是否仍然完好，因此，这步是否是“编译”的真正部分还存在少许争议。无论如何，它是LabVIEW编译链的一环，非常明显地相当于传统编译器的词法分析，句法分析，或者是语义分析。

一个适于终端输入的简单例子是LabVIEW加法基元。如果您将两个整数相加，结果是整数，但是如果您将两个浮点数相加，结果是一个浮点数。类似的案例出现在符合类型的数据，例如阵列和簇。存在其它语言结构，例如对移位寄存器来说，有更复杂的输入规则。在加法基元的情况下，输出类型取决于输入类型，类型被叫做通过图表“传播”，这也是算法名字的由来。

这个加法基元的例子也表明类传播算法的语法检查职能。假设您连接一个整数和一个字符串到一个加法基元——会发生什么？在这种情况下，将二者的值相加没有意义，所以类传播算法将其报告为一个错误并将VI标记为“坏的”，它会引起运行箭头中断。

中间表示——是什么与为什么

在类传播确定VI是有效的，编译器继续并将VI转化成DFIR。一般来说在详细设计DFIR之前要考虑中间表示(IRs)。

IR是由编译过程通过多阶段编辑过的用户程序的表示。IR的概念常见于现代编译文献并能应用于任何编程语言。

请考虑一些例子。当今有多种流行的IRs。两种常见的例子是抽象语法树（AST）与三地址码。

t0 <- y

t1 <- 3

t2 <- t0 * t1

t3 <- x

t4 <- t3 + t2

图 1. AST IR实例

表 1.三地址码 IR实例

图 1显示了“x + y * 3”表达的 AST表示，而表1 显示了三地址码表示

两种表示方式之间最明显的一处不同是AST是更高级的。它更类似于程序(C)的源表示而不是对象表示（机器码）。三地址码相比之下，是低级的并且更类似于汇编。

不论高级或低级表示都有各自的优点。例如，语法分析，比如可靠性分析，对类似于AST的高级表示比类似于三地址码的低级表示更容易实现。其它的优化，例如寄存器分配或指令调度，一般用低级表示，比如三地址码来执行。

因为不同的IR有不同的优势和劣势，所以很多编译器(包括 LabVIEW)会使用多种IR。在LabVIEW中，DFIR作为高级IR使用，而LLVM IR作为低级IR使用。

DFIR

在LabVIEW中，作为高级表示的是 DFIR，它是分等级且基于图形的，其本身类似于G代码。如同G代码，DFIR也是由很多包含接线端的节点组成。每个接线端可以连接到其它接线端。一些节点，例如包含图表的循环，也可以相应地包含其它节点。

图 2. LabVIEW G 代码与相应的DFIR 图表

图2显示了一个简单的VI以及它的初步DFIR表示。当首次创建一个VI的DFIR图表时，它是G代码的直接翻译，DFIR图表的节点一般与G代码中的其它节点进行一对一的通信。随着编译的进行，DFIR节点有可能被移动或者分开，或者新的DFIR节点被加入。DFIR一个最关键的优势是它保留了G代码的固有特性，如并行机制等。用三地址码表示的并行机制相比之下更难识别。

DFIR为LabVIEW编译器提供了两个显著的优势。首先，DFIR从VI编译器的表示分离出编辑器。其次，DFIR能用作拥有多个前端和后端的编译器的公共端。以下是每一个优势的详细解读。

DFIR图表从编译器表示分离出编辑器

在DFIR出现之前，LabVIEW有一个单独的VI表示，由编辑器和编译器共享。这样阻止了编译器在编译过程中修改表示，这样一来，进行编译器优化就变得困难了。

图 3. DFIR 提供一种构架，允许编译过程中优化您的代码

图3显示了对应于刚才提到的VI的DFIR图表。此图表描述了编译器过程较靠后的部分，此时它已被几个变换分解并优化过。您可以看到，这个图表与之前的图表看起来有很大的不同。例如：

分解变换已经移走了控制，指示，以及子VI节点，而用新的节点替代它们——UIAccessor, UIUpdater, FunctionResolver和 FunctionCall。
循环不变式代码已从循环内将增量和乘法节点移出。
聚丛法在For 循环内部增加了YieldIfNeeded节点，可以使执行线程与其它竞争的工作项目共享执行。

我们将会在后面的章节对变换进行更深入探讨。

DFIR IR可以作为多个编译器前端与后端的公共端

LabVIEW可以在数个不同的终端上工作，而其中一些终端与其它终端差别很大，例如，一台x86 台式 PC与一个 Xilinx FPGA。同样地，LabVIEW为用户提供了多种计算模型。除了使用G语言的图形化编程，LabVIEW也在提供了例如MathScript的基于文本的数学运算。这就带来了前端与后端的集中，它们都需要在LabVIEW编译器下工作。使用DFIR作为公共IR，前端进行生产而后端进行消费，这样便促进了不同组合之间的重新使用。例如，运行于DFIR图表的常数合并优化执行过程可以只需写入一次而用于台式，实时，FPGA以及嵌入式对象。

DFIR 分解

一旦进入DFIR, VI首先运行一系列的分解变换。分解变换的目标是缩小或标准化DFIR图表。例如，未连线输出通道分解会寻找在条件结构和事件结构中没有被连线并被配置为“Use Default If Unwired”的输出通道。对这些接线端来说，变换赋给一个常量以默认值，并将其连接到接线端，因而使DFIR图表的“Use Default If Unwired”行为明确。随后的编译器扫描会完全相同地处理这些接线端并假设它们都有连线的输入。在这种情况下，语言的“Use Default If Unwired”特征在将表示缩小到更基本的形式后便被“编译掉”了。

这种做法也可以用于更为复杂的语言特性。例如，分解变换被用于将反馈节点缩小到While循环上的移位寄存器中。另外一个分解将并行的For循环分解为几个顺序的具有额外逻辑的For循环，用以为顺序循环将输入分解为可平行化的部分，随后将所有的部分再次组合到一起。

LabVIEW 2010的一个新特征，子VI直接插入，也是作为DFIR分解来执行。在编译的这个阶段，被标记为“直接插入”的子VI的DFIR图表直接加入调用程序的DFIR图表。除了避免子VI调用的架空，直接插入法通过将调用与被调程序结合到一个单独的DFIR图表，为额外的优化提供了可能性。例如，考虑一个从vi.lib.调用TrimWhitespace.vi的简单VI。

图 4. 用于演示 DFIR优化的简单VI实例

TrimWhitespace.vi在vi.lib中定义如下：

图 5.TrimWhitespace.vi 结构图

子VI直接插入调用程序中，得出等价于如下G代码的DFIR图表。

图 6. 直接插入的TrimWhitespace.vi DFIR图表的等价 G代码

既然子VI图表直接插入调用程序的图表，不可获取代码的删除和死码删除能够简化代码。第一个条件结构总是执行，而第二个条件结构从不执行。

图 7. 由于输入逻辑是常量，条件结构可以删除

类似地，循环不变代码将匹配类型的基元移出循环。最终的DFIR图表等价于如下的G代码。

图 8. 最终 DFIR图表的等价G代码

因为TrimWhitespace.vi在LabVIEW 2010 版本中默认标定为直接插入，所有此VI的客户端使用都能自动享有这些益处。

DFIR 优化

在DFIR图表完全地分解后，DFIR优化扫描开始。更多的优化在随后的LLVM编译时被执行。本章节仅讲述了众多优化当中的一部分。这些变换都是常用的编译器优化，所以，想找到更多具体优化的信息应该较为容易。

无法读取代码的删除

无法读取代码是永远无法执行的代码。删除无法读取代码并不直接让执行变得更快，但是它可以使您的代码更精简并且改善编译时间，因为删除的代码在随后的编译扫描中将不再被访问到。

在无法读取代码删除之前

After Unreachable Code Elimination

图 9. DFIR无法读取代码删除分解的等价G代码

在这个例子中，条件结构的“Do not increment”图表从不执行，所以变换删除了这个条件。由于条件结构只剩下一个条件分支，因此它被顺序结构替换。随后的死码删除移除了边框与枚举常量。

循环不变代码移动

循环不变代码移动将识别循环内部可以安全移至外部的代码。由于移出代码的执行次数更少，整体执行速度将得到改善。

循环不变代码移动变换之前

循环不变代码移动变换之后

图 10. DFIR循环不变代码移出分解的等价G代码

在这个例子中，增量运算被移到循环外面。循环本体不变，因此在创建数组的同时，不必在每个迭代重复进行计算。

公共子表达式删除

公共子表达式删除可识别重复计算，而将执行一次计算，并重复使用计算结果。

Before

After

图 11. DFIR 公共子表达式删除分解的等价G代码

常数合并

常数合并支持那些在运行时是常数的图表部分，因而可以在初期就确定下来

图 12. 常数合并在 LabVIEW结构图中非常直观

图12中VI的哈希码指出了常数合并的一部分。在这种情况下，“偏量”控制不能够常数合并，而加法基元的其它操作数，包括For循环，是恒定值。

循环展开

循环展开通过在合成码部分多次重复一个循环的本体以及减少相同因子总的迭代计数，减少了循环架空。这样减少了循环架空，并且在代码尺寸增长损失的情况下，显露了更多的优化过程。

死码删除

死码是多余的代码。去除死码加快了执行时间，因为去除的死码不再被执行。

死码并不是由您直接编写的，它常常由DFIR图表转换操作产生。请考虑如下的例子。无法读取代码的删除确定事件结构可以被移除。这样“创建”的死码可以被死码删除转换移走。

先前

在无法读取代码删除后

在死码删除后

图13. 死码删除能够减少编译器需要跨越的代码数量

此小节涉及的大部分转换具有像这样的相互关系；运行一个转换也许会引发其它转换运行的机会

DFIR后端转换

在DFIR图表被分解并优化后，很多后端转换被执行。这些转换评估并注解DFIR，为最终将DFIR图表降低为LLVM IR做好准备

聚丛程序

聚丛算法分析DFIR图表的并行机制，并将节点归类为您可以并行运行的丛。这种算法与LabVIEW实时执行系统紧密联系，这些系统使用多线程协同多任务处理。每个由聚丛程序产生的丛都作为执行系统的单独任务罗列出来。丛中的节点以固定的，串行化的次序执行。每个丛具有预订的执行次序允许替代程序共享数据分配并显著地提高了性能。聚丛程序也具有将结果插入长操作的职能。例如循环或者I/O，因此这些聚丛程序与其它聚丛程序协同执行多任务处理。

内嵌程序

内嵌程序分析DFIR图并识别什么时候您可以重新使用数据分配以及什么时候您必须进行复制。LabVIEW中的一个连接也许是一个简单的32位标量或32 MB的阵列。确保数据尽可能地重复使用对LabVIEW这样的数据流语言来说是至关重要的。

请考虑如下的例子（请注意VI调试不能实现最好的性能和存储器空间占用）

图 14. 简单实例演示了内嵌算法

这个VI初始化一个阵列，对每个要素增加了一些标量值，并将其编写为一个二进制文件。应该有多少个阵列副本? LabVIEW最初不得不在本地创建阵列，而加法运算只能在那个阵列运行。因此只需要一个阵列的副本而不是每个连接都分配。这意味着一个显著的不同——无论是存储器消耗还是执行时间——如果阵列很大。在这个VI，内嵌程序意识到运行“内嵌”的时机并配置加法节点以利用它。

您可以在Tools?Profile下使用“缓冲区分配”来检验您编写的VIs的这种行为。工具不会显示加法基元的分配，而显示为没有数据副本并且加法运算内嵌。

这是可以接受的，因为没有其它节点需要原始阵列。如果您如图15所示修改了VI，内嵌程序会为加法基元制作一个副本。这是因为第二次写为二进制（Write to Binary File）需要原始的阵列并且必须在第一次写为二进制基元（Write to Binary File Primitive）后。采取此修改，显示缓冲区分配工具显示加法基元的分配。

图 15. 原始阵列连线分支引起存储器中副本的创建

分配程序

在内嵌程序识别出哪一个节点可以与其它节点共享存储单元，分配程序运行以创建VI需要执行的分配区。它通过访问每一个节点与端点来执行。内嵌到其它端点的端点重新使用分配区而不必创建一个新的。

编码发生程序

编码发生程序是编译器的组成部分，为对象过程将DFIR图转化为可执行的机器指令。LabVIEW在DFIR图按数据流次序渡越每个节点，每个节点调用一个叫做GenAPI的接口，它被用来将DFIR图转化为顺序的中间语言(IL)，以描述节点的功能性。IL提供了一个独立平台来描述节点的低级行为。IL的多种指令被用来执行运算，读写存储器，实现比较与条件跳转，等等。IL指令能够对存储器或用来存储中间值的虚拟寄存器中的值进行操作。常用IL指令包括GenAdd, GenMul, GenIf, GenLabel,及 GenMove。

在LabVIEW 2009及早期版本中，IL结构直接转化为用于对象平台的机器指令(例如 80X86与 PowerPC)。LabVIEW使用一个简单的一次扫描寄存器分配程序将虚拟寄存器映射到物理机器寄存器。每个IL指令发出一组用于特定机器指令的硬件编码，从而在每个支持对象的平台执行它。它盲目地追求速度，是一种即席（ad hoc）网络，产生质量低下的代码，并不适于优化。DFIR，作为高级的，独立平台表示，受限于它能支持的代码转换类型。在现代优化编译器中，为增加支持整套代码优化，LabVIEW近来采用一种第三方开放源码技术，称为LLVM。

LLVM

低级虚拟机(LLVM)是一种多用途，高性能，开放源代码的编译器构架，起初作为伊利诺斯州立大学的一个研究项目被发明出来。LLVM 现在广泛地用于学术和工业，因为它灵活，简洁的API以及无许可证限制。

在LabVIEW 2010版本，LabVIEW 编码生成程序是使用LLVM重构生成对象机器代码。已经存在的LabVIEW IL表示为这种尝试提供了很好的起点，只需要重写大概80 条IL指令，不超过LabVIEW支持的大量DFIR节点与基元。

在由VI的DFIR图创建IL代码流后，LabVIEW访问每个IL指令并创建一个等价的LLVM汇编表示。它可以援引多种优化扫描，然后使用LLVM即时(JIT)架构从而在存储器中创建可执行机器指令。LLVM的机器变换布置信息被转化为LabVIEW表示，所以当您将VI保存到硬盘中并在另外不同的基于地址的存储器中重新载入时，您可以正确地修改使其在新的地址运行。

LabVIEW使用LLVM实现的一些标准编译器优化包括如下：

指令综合
跳转线程
聚合体标量替换
条件传播
尾调用消除
表达重组
循环不变代码移出
循环外提与引导分割
归纳变量简化
循环展开
总值编号
死存储消除
主动死代码删除
稀有条件持续传播

所有这些优化的完整解释超出了本文的范围，而网络上以及大部分的编译器教科书都有关于它们的丰富信息。

内部基准显示LLVM的引入节约了20%的VI执行时间。单独的结果取决于VI执行运算的类型；一些VIs的提高远胜于此，一些性能并无变化。例如，使用先进分析库的VIs 或者其它的很大程度依赖于代码的，如使用优化过的C实现的VIs，性能看起来几乎没有不同。LabVIEW 2010是使用LLVM的首个版本，仍然具有很多有待挖掘的潜力用于未来的改进。

DFIR 与LLVM协同工作

您也许已经注意到了，这些优化当中的某一些，比如循环不变代码移出以及死码删除，已经由DFIR正在执行。事实上，某些优化扫描适于多次，并在编译器的不同层次运行，因为其它的优化扫描或许在将代码转换时，出现有用的新的优化机会。最终标准是，DFIR作为高级IR，LLVM作为低级IR，它们两个协同优化您为处理器结构所写的，用于代码执行的LabVIEW代码。