编译原理及技术(八)——代码形式

一、分配存储位置

对程序中计算的每个值（如赋值语句a = b + 1，命名值a，未命名值b + 1），编译器都必须确定在何处存储这些值：是在内存中还是在寄存器中，不管是哪种情况，都要给出具体的位置。它必须为每个值分配一个位置，该位置必须符合值的生命周期和可寻址性。因而，编译器会将值群集到数据区中，同一数据区中的每个值都具有同样的存储类别。

1.1 设定运行时数据结构的位置

为分配存储，编译器必须理解全系统范围内对内存分配和使用的约定。编译器、操作系统和处理器协作，以确保多个程序能够以交错的方式（时间片）安全地执行。因而，有关程序地址空间布局、操控和管理的许多决策超出了编译器编写者的权责范围。但这些决策对编译器产生的代码有着巨大的影响。因而，编译器编写者必须充分地理解这些问题。

下图给出了单个程序编译后所用地址空间的典型布局 。该布局将代码和数据的各个定长区域放置在地址空间的低端，代码位于地址空间的底部，与之相邻的区域标记为静态，包含了静态数据区和全局数据区，以及由编译器创建的所有定长数据。静态数据区之上的区域用于可能会扩展和收缩的数据区。如果编译器在栈上分配AR，它将需要一个运行时栈。在大多数语言中，编译器都需要一个堆，以便为动态分配的数据结构提供内存。为保证高效地利用内存空间，堆和栈应该置于开放空间的两端，彼此相对增长。在图中，堆向着高地址方向增长，而栈向着低地址方向增长。将上述安排调换一下，同样工作良好。编译器也可能创建额外的静态数据区，以保存常量值、跳转表和调试信息。

关于内存这一块的知识，之前专门做过总结，可以看虚拟内存（上）、虚拟内存（下）

1.2 数据区的布局

编译器将具有同样生命周期和可见性的值群集起来存储，编译器为此创建了若干不同的数据区，这些数据区的放置取决于有关值的生命周期和可见性的语言规则。例如，编译器可以将过程局部的自动存储区(automatic storage，指存放局部变量的数据区）放置在过程活动记录内部，这是因为这种变量的生命周期恰好与AR的生命周期相匹配；与此相反，编译器必须将过程局部的静态存储区(static storage，指静态变量的数据区）存放在内存中的“静态”区域，因为这种变量是跨调用存在的。

将局部变量放置在AR中，访问可以变得更为高效。因为代码已经将ARP加载到一个寄存器，故此可以利用loadAI或loadAO这样的操作，使用相对于ARP的偏移量来访问这些值。对AR的频繁访问，可能会使之保持在数据高速缓存中。编译器将具有静态生命周期或全局可见性的变量放置到位于内存“静态”区域的数据区中。在运行时对这些值的访问需要稍微多一些工作，编译器必须确保获得对应数据区的地址并将其加载到一个寄存器中。

存储在堆中的值，其生命周期是编译器无法轻易预测的，有两种不同的机制可以将一个值置于堆中：一是程序员可以从堆中显式分配存储；二是在编译器检测到值的生命周期可能超越创建该值的过程时，可以将该值置于堆中。但不论是哪种情况，堆中的值都是通过一个全地址表示的，而非相对于某个基地址的偏移值。

1.3 将值保存到寄存器

在寄存器到寄存器的内存模型中，编译器试图将尽可能多的值分配到虚拟寄存器。在这种方法中，编译器需要依赖寄存器分配器，以便将IR中的虚拟寄存器映射到处理器上的物理寄存器，同时将无法保持在物理寄存器中的虚拟寄存器溢出（在寄存器分配器无法将某个虚拟寄存器分配到物理寄存器时，它将溢出该值：在每次定义该值后将其存储到内存，每次使用该值前将其加载到一个临时寄存器）到内存中。如果编译器将一个静态值保持在寄存器中，那么在过程中第一次使用该值之前，必须将其从内存加载到寄存器，在离开过程之前（退出该过程时，或在过程内部调用其他过程时），必须将其写回到内存。

只能有一个名字访问的值是无歧义值（unambiguous value），编译器可以将无歧义值保持在寄存器中；有多个名字、且可用多个名字访问的值称为有歧义值（ambiguous value）。歧义的出现有几种可能性：

1. 存储在基于指针的变量中的值，通常是具有歧义的。
2. 传引用形参和名字作用域规则之间的交互可能使形参具有歧义。
3. 许多编译器将数组元素值当做是歧义值，因为编译器无法断定两个引用（如A[i,j]和A[m,n]）是否曾经指向同一内存位置。

一般来说，编译器将歧义值保持在寄存器中的时间，将在另一个歧义值的定义或使用之前结束。编译器也会通过缜密的分析与优化，可以在一些情形中消除歧义。

二、算数运算符

许多问题都会影响到代码生成的质量。比如数据存储位置不同，生成的加载指令数目也不同，使用的寄存器数目也不同。即使存储位置相同，不同的代码形式也会影响到对寄存器的需求。

比如 a - b * c。假设数据都在内存中，且按照树后序遍历的方式生成代码。从左到右遍历和从右到左遍历生成的代码经过寄存器分配器优化后，所需的寄存器数目不同。

在生成代码的阶段，以上面的例子，我们生成的加载指令是

loadI @a        -> r1
loadA0 rarp, r1 -> r2
1
2

而非 loadAI rarp, @a -> r2，这有几个原因：

• 针对 @a 给出了显式名字，如果在上下文需要 @a，则可以重用
• 偏移量 @a 可能无法转入 loadAI 的立即数字段

在优化阶段，编译器可能通过发现的知识将两条指令合并为单个指令。但更好的做法是将该问题推迟到指令选择器，将第二个原因中与机器相关的因素隔离到编译器处理机器相关的阶段。

为了选择一种能够减少寄存器使用量的求值顺序，必须不断交换左右子树并计算可能的改进。一般来说，只要对每个节点中使用寄存器数最大的子树先求值，就能最小化寄存器的使用。因此要求对代码进行两趟处理，先计算寄存器使用量，然后输出处理后的代码。

重排表达式可以暴露出一些额外的优化机会。但是由于精度的限制，浮点数表达式不应该重排，除非语言定义允许这么做。

函数调用的存在，可能会限制编译器改变表达式顺序的能力，因为函数可能有副作用，可能修改其他变量的值。这促进过程间分析的大部分工作。

三、布尔表达式和关系运算符

布尔值有两种表达方式：数值编码和位置编码。前者为 true 和 false 分配具体的数值。后者通过代码不同分支控制流来表示求值结果。如果布尔表达式的结果不需要存储，则使用位置编码是有意义的，否则选择数值编码方案。

目标机指令集的具体细节会影响到关系运算的实现方式，其中有几种方案：直接条件码、条件复制、布尔值比较和谓词操作。

直接条件码中比较操作会设置一个条件码寄存器，只有条件分支操作能够读取寄存器的值。优势在于一些处理器能够通过算术运算来设置条件码，这样可以避免比较操作。？

条件复制方案为模型增加一个条件复制的指令，这样可以避免比较操作和分支，但是会对指令中的两个表达式都求值。对于要求短路求值的语言，这可能带来风险。

布尔值比较和直接条件码类似，不过它对关系运算求值可以无需分支操作。缺点在于总是需要显式的比较操作。

谓词执行模型中，目标机可以在指令前加一个谓词表达式来决定指令是否生效。这种方案生成的代码精炼，但在一些场合下，不如其他采用分支的方案，这在后面小节会谈及到。

四、数组的存储和访问

4.1 一维数组的存储和引用

最简单形式的数组只有一维，我们称其为向量，向量通常存储在连续内存中。因而，向量V[3...10]将产生以下内存布局，其中单元格下方的数字表示其在向量中的索引：

假定V声明为V[low...high]，其中low和high是向量（索引）的下界和上界。为转换引用V[i]，编译器需要指向V起始处的指针和元素i在V内部的偏移量。偏移量是(i - low) * w，其中w是V一个元素的长度。因而，如果low为3，i为6，w为4，偏移量即为(6 - 3) x 4 = 12。假定ri包含i的值，以下代码片断计算V[i]的地址，设置到r3中，并将其值加载到rv中：

使用零作为索引下界，可以消除减法。如果编译器知道V的下界，它可以将减法折合到＠V中，即不使用＠V作为V的基地址，而使用V0 = @V - low * w。我们称＠V0为V的虚零点(falsezero，向量V[0]所处的地址叫做虚零点)。

使用＠V0并假定i已经加载到ri中，访问V[i]的代码将变为：

4.2 多维数组存储布局

多维数组
访问多维数组的一个元素需要更多的工作。在讨论编译器必须为此生成的代码序列之前，我们必须考虑编译器如何将数组索引映射到正确的内存位置。大多数实现使用下述三种方案之一：行主序(row-major order)、列主序(coltunn-major order)和间接向量(indirection vector)。源语言定义通常会规定使用上述映射中的某一种。

访问数组元素所需的代码取决于数组映射到内存的方式。考虑数组A[1...2，1...4]，概念上，它看起来像是：

在线性代数中，二维矩阵的行是其第一个维度，而列是其第二个维度。在行主序中，A的元素被映射到连续的内存位置，使得一行中的相邻元素占据相邻的内存位置，这将产生以下布局：

行主序最明显的备选方案是列主序，它将A的各列分别置于连续的内存位置，产生如下所示的布局：

【注】行主序和列主序的布局，出于性能的考虑，在访问数组元素时要更倾向存储的局部性原理，所以他们的访问方式会有所区别。

第三种备选方案，虽然并不十分明显，但已经用于几种语言中。该方案使用间接向量，将所有的多维数组都降阶为向量集合。对于我们的数组A，这样做将产生下述布局：

4.3 引用多维数组元素

使用数组的程序通常会引用各个数组元素。类似向量，编译器必须将数组引用转换为一个基地址和一个偏移量，基地址表示数组存储的起始地址，而偏移最表示目标元素相对于起始地址的偏移量。

接下来分别讲述按行主序存储为连续内存块的数组和存储为间接向量集合的数组的地址计算方法。列主序的计算遵循了与行主序相同的基本方案，只是维度的次序要反过来。

行主序引用

设low1、high1是第一维的上下界，low2、high2是第二维的上下界。在我们的例子A[1...2,1...4]中，low1、low2为1，而high1、high2为2和4。

为访问元素A[i,j]，编译器必须输出代码计算行i的地址并计算元素j在该行中的偏移值。可知每一行的元素个数为len = high2 - low2 + 1，所以行i的偏移量为(i - low1) * len * w；而根据前面向量偏移值的算法，j在其所处行的偏移值为(j - low2) * w。所以由此推出元素A[i,j]的地址如下，其中@A是A[1, 1]的地址：

@A + (i - low1) * len * w + (j - low2) * w
1

将A[2, 3]带入公式计算偏移量为(2 - 1) * (4 - 1 + 1) * 4 + (3 - 1) * 4 = 24，所以A[2, 3]的地址为@A + 24，对应内存布局如下所示：

再回顾向量访问时提出的虚零点，如果二维数组的第一维和第二维的下界均为零（low1=0，low2=0），则可推出元素A[i,j]的地址如下，其中@A0是A[0, 0]的地址：

	@A0 + (i - low1) * len * w + (j - low2) * w
=>  @A0 + i * len * w + j * w
=>  @A0 + (i * len + j) * w
1
2
3

将A[2, 3]带入公式计算偏移量为(2 * 4 + 3) * 4 = 44，所以A[2, 3]的地址为@A0 + 44。

间接向量引用

使用间接向量简化了为访问各个元素而生成的代码。由于最外层的维存储为一组向量，那么最后一步看起来就像是2.1节中描述的向量访问方式。对于B[i,j,k]，最后一步根据k、最后一维的下界、B中一个元素的长度，来计算一个偏移量。而预备步骤则通过跟踪间接向量结构中的适当指针，来推算该向量的起始地址。

因而，访问下图所示数组B中的元素B[i,j,k]，编译器需要使用最外维数组的基地址＠B0、i和一个指针的长度（一般为8字节），来找到对应于子数组B[i,*,*]的向量基地址。然后使用该地址、j以及一个指针的长度，来找到对应于子数组B[i,j,*]的向量基地址。最后使用该向量的基地址、k和元素长度w,来找到B[i,j,k]的地址。

五、字符串

编译器编写者必须为字符串选择一种表示，该表示的细节对字符串操作的代价有着巨大影响。为理解这一点，考虑字符串"a string"的两种常见表示。左侧是C语言实现中的传统表示，它使用一个简单的字符向量，用指定字符('\0')充当结束符，符号'b/'(左边数第二个)表示空格。右侧的表示同时存储了字符串的长度(8)和内容，许多语言也使用了这种方法。

如果长度字段比结束符('\0')更占空间，那么存储长度的做法将或多或少地增加字符串在内存中占用的空间（4字节或8字节），但存储长度简化了对字符串的几种操作（如求字符串长度）。如果语言允许在分配的定长字符串内部存储变长字符串，那么实现者可能还需要存储字符串的分配长度。编译器可以使用分配长度，对字符串赋值和连接进行运行时范围检查。

六、结构引用

在对结构进行布局以及为其中各成员分配偏移最的过程中，编译器必须遵守目标体系结构的对齐规则。这可能迫使编译器在结构中留出不使用的空间。在编译器对下图中左侧声明的结构进行布局时，就会面临该问题：

如果编译器不得不按结构成员声明的顺序来进行布局，将如图中右上所示。因为fie和furn必须对齐到双字，编译器必须在fee和foe之后插入填充字节。如果编译器可以在内存中按任意顺序部署结构成员，它可能会使用如上图右下所示的布局，该布局不需要填充字节。这是一个语言设计问题：语言定义会规定结构布局是否向用户开放。

结构数组

许多程序设计语言容许用户声明结构数组。如果允许用户获得结构数组中数组元素的地址，那么编译骈在内存中对数据进行布局时，结构数组的布局将呈现为多个布局相同、在内存中连续出现的结构实例。如果程序员无法获得结构数组中数组元素的地址，编译器在布局结构数组时，可以将其作为单个结构处理，其中的 每个成员变为数组。依赖于外围代码访问数据的方式，这两种策略在具有高速缓存的系统上可能表现出非常不同的性能。

在寻址布局为多个结构实例的结构数组时，编译器使用7.5节描述的数组地址多项式。结构的全长（包括任何必需的填充字节）将变为地址多项式中的数组元素长度(w)。该多项式会产生结构实例的开始地址。为获取结构实例中特定成员的值，该成员的偏移量将加到结构实例的起始地址上。

如果编译器将结构数组布局为成员为数组的结构，它必须使用偏移量表的信息和数组维数来计算成员数组的起始地址。该地址接下来可以作为起点，使用适当的数组地址多项式来进行进一步的地址计算。

七、控制流结构

在条件执行语句中，随着 then 和 else 代码的增长，内部代码高效执行的重要性开始超过控制表达式执行的代价。假设 then 和 else 都包含 10 条独立的操作，在双发射机器上，支持谓词执行的方式会使每个 false 的操作都占用一个发射槽，这导致每个分支都需要 10 个周期。而不使用谓词方式，采取分支跳跃则能使每个分支都只需要 5 个周期。

因此实现条件判断语句方案中，选择分支还是谓词需要考虑：

• 如果一条分支执行频度显著高于另一条，那更需要加速该路径，这倾向于使用分支方案
• 如果一条分支的代码数比另一条多得多，则也不适合使用谓词执行
• 每个分支都包含复杂的控制流，比如嵌套 if，那么使用谓词执行会很糟糕

循环结构都有一个相似的结构，也有一些优化的地方。比如可以使用循环体中的指令来填充延迟槽、常量折叠以消除部分分支甚至循环本身。

许多程序语言都有包含 case 语句的变体，比如 Fortran 的 goto，C 语言的 switch。case 语句的复杂点在于，如何高效定位目标 case 子句。有三种策略：线性查找，二分查找和直接计算地址。