介绍一个新的，先进的 Visual C++ 代码优化器

  • Article

[原文发表地址] Introducing a new, advanced Visual C++ code optimizer

[原文发表时间] 2016/5/4  Gratian Lup [MSFT]

我们很高兴的宣布，一个新的，先进的 Visual C++编译器后端代码优化器的预览版发布了。它提供了诸多方面的改进，包括代码的大小和性能，让优化器步入到了一个现代本地编译器预期质量的新标准。

这是第一次的公开发布，我们鼓励大家去尝试使用它，并且提出一些建议和反馈一些潜在的bug。新的优化器的正式版本将会在Visual Studio Update 3中发布，而今天的发布可用但并不受支持，主要用于测试目的。

如何尝试使用

使用新优化器的编译器文件很容易得到：只要使用NuGet安装最新的VisualCppTools包就可以了。关于如何安装的详细信息请参考这篇博客。一旦安装成功，在通常的方式下编译应用程序 – 在所有的架构中优化器是默认启用的。

报告bug和建议

我们希望得到尽可能多的反馈，包括你所发现的bug或者你可能有的任何建议。如果您认为您发现了一个bug，您可以通过如下没有文档记录的标记 –d2SSAOptimizer- 去禁用它，以便确认这是否是由新的优化器所导致的。

  • 在Visual Studio IDE中，添加标记到工程属性页面 –> C/C++ -> 命令行 -> 附加选项的文本框中
  • 如果您使用cl.exe在命令行编译，在 /link 选项前添加这个标记

如果使用-d2SSAOptimizer-标记之后，bug不再出现，请按照下列步骤操作：

  • 使用 Connect网站提交一个bug
  • 在标题前加前缀 [SSA Optimizer]
  • 附加上详细的信息，例如编译器的版本，编译选项和能够重现bug的预处理文件或者linkrepro形式的源代码。Bruce Dawson的博客中有关于 提交高质量的bug报告 的文章。
  • 您也可以直接发送邮件到gratilup@microsoft.com

为什么要使用一个新的优化器？

新的优化框架的主要动机是为了有更多积极的优化，比如利用更多的编译时间信息和现代编译器的新进展。一些旧的优化过程的设计使得实现更高级的转换，并以更快的速度做出改进变得难以实现。新的框架旨在成为未来许多优化工作的基础，一个核心设计目标是使它更容易实现，测试和测量新的优化。

项目的一些主要目标：

  • 提高标量和矢量代码的编码质量

在许多情况下，性能和代码长度可以被改善，有时候可以大大地改善。该框架试图解决老的优化器的几个不足之处：

    • 旧的表达式优化器其较小的已知转换和有限的函数视图 – 这阻碍了发现所有的可以被优化的表达式。
    • 许多小的优化基于识别模式 – 被称为窥孔优化 – 或者丢失优化或者只针对对某些特定架构来实现。
    • 矢量代码 – 无论是内置函数还是自动矢量化生成的代码 – 可以实现更好的优化。

新的优化器利用Static Single Assignment 形式，它允许处理更复杂的表达式，即可以跨越整个函数。SSA形式的另一个优点是，它使得可以写更简单和更高效的算法，从而不再需要使用更加复杂和缓慢的技术，如数据流分析。

窥孔优化现在可以通过目标无关的方式来实现，采用模式匹配系统，其速度非常快，（基于模板元编程），并且只需要写入少量代码。这使得可以在很少的时间内，使用通常的识别模式的方式来添加大量的模式。

相同的模式匹配机制可用于矢量操作，这使得优化整数和浮点数矢量操作表达式和标量操作表达式一样简单。注意，此功能尚未完成并启用。

  • 设计一个框架，使得开发变得简单，并且减少潜在的错误

能够快速形成雏形并且得到可靠的实施是新架构的主要优势之一。它提供各种各样的帮助，使得SSA形式的操作，表达式的模式匹配，建立新的表达式以及在存在指针别名和异常处理的情况下进行安全检查变的更容易。

  • 执行更好的代码静态分析

新的优化器还增加了新的静态分析模块，有了这些模块，就能够识别何时值是布尔类型（0或者1），何时值总是正数，以及何时值不能为零。它还有一个强大的模块，此模块能够估算一个值的已知的1位或0位，以及一个值可能的范围。其结果作为某些优化的先决条件，要么来完全消除一些无用的操作，要么转换操作成为可以进行更好的优化的形式

  • 重点强调测试和正确性

鉴于该项目的范围大，保证和维护正确性是重中之重。这是通过使用形式验证，测试随机生成的程序（模糊测试）和流行的程序和库，例如Chrome，Firefox, CoreCLR和Chakra来实现的。请参阅下面的测试方法部分获取更多的详细信息。

实施优化的例子

下面是一个示例，改示例仅仅说明了新的优化工具的许多新变革中很少的几个。在编码解码其中经常可以发现这类代码：

int test(int a) {

return a % 2 != 0 ? 4 : 2;

}

 

具有旧优化器的x64程序集 具有新优化器的x64程序集
?test@@YAHH@Z PROCand   ecx, -2147483647jge   SHORT $LN3@testdec   ecxor   ecx, -2inc   ecx$LN3@test:test ecx, ecxmov   eax, 2mov   edx, 4cmovne eax, edxret   0 ?test@@YAHH@Z PROCand   ecx, 1lea   eax, DWORD PTR [rcx*2+2]ret   0

在最好的情况下，旧的优化器的执行时间约为5个循环（假定乱序执行和完美的分支预测），而在最坏的情况下，执行时间至少需要10个循环。使用新的优化器，执行时间只需2个循环。显然，代码长度也变短了。

通过组合多个较小的转换可以得到非常有趣的结果。在这种情况下，有两种模式被运用来产生最后的结果：

  • a % 2 == 0 -> a & 1 == 0
  • 由于取余（%）的结果是和0进行比较，a 的正负不影响比较的结果，因此取余(%)可以被按位与（&）来替代。
  • a<bool> ? C1 : C2 -> C2 + a*(C1-C2)
  • 一个三元条件选择操作在两个常量之间进行。第一个要求是条件值是布尔类型，这个是由静态分析包决定的。第二个是C1-C2的值必须是2的幂，从而可以进行移位或者LEA操作而不是乘法操作。

让我们来看更多的可以实现的有趣的优化和模式的例子。特别是把重点放在之前没有实现较好优化的操作，例如比较，转换，除法，问题运算符和控制流依赖表达式（SSA形式中的PHI操作）。虽然有些例子似乎不太可能写入源代码中，他们在内联函数和其他的转换之后经常出现。

  • 改进算术表达式的优化，包括标量浮点数操作

SSA形式暴露出大量的表达式，他们可以跨越整个函数 – 这样可以发现更多的优化机会，特别是当与表达式从新组合相结合的时候。同时也增加了许多新的模式，如下：

(a / C1) / C2 -> a / (C1 * C2)

(a * C1) / C2 -> a * (C1 / C2)

a / (x ? C1 : C2) -> a >> (x ? log2(C1), log2(C2)) // C1 and C2 must be power of two constants

大多数新的浮点优化只能在 -fp:fast 下启用，但是其中有些是在 –fp:precise下有效的。

更多关于浮点模型所允许的优化的信息可以从文档中获得：Microsoft Visual C++ 浮点优化

  • 优化依赖于表达式的控制流

我上面提到了SSA格式简化了处理更大，更复杂的表达式。一个优点是它可以在函数中更容易的推断变量，这些变量或者是重新定义的，或者是基于路径的不同值。正如它的名字所暗示的，SSA解决了这一点，通过每次重新定义变量时就创建一个不同版本的变量；如果在函数中有一些地方，一个变量有多个可能值，这时一个被称为PHI的伪指令，其会被插入，来合并所有的值。

虽然创建SSA格式是相当复杂的，然而下面的例子应该足够简单，来很好的了解SSA和PHI运算的作用。

原始代码 SSA 转换后
int test(int a, int b) {

int x, y, z;

if(a > 3) {

x = 4;

y = 1;

z = b & 0xFF00;

}

else {

x = 9;

y = 2;

z = b << 8;

}

int p = (x * y) * 4;

int q = z & 0xF;

return p >= 16 && q == 0;

}

 int test(int a1, int b1) {int x0, y0, z0; // undefinedif(a1 > 3) {x1 = 4;y1 = 1;z1 = b1 & 0xFF00;}else {x2 = 9;y2 = 2;z2 = b1 << 8;}x3 = PHI(x1, x2)y3 = PHI(y1, y2)z3 = PHI(z1, z2) int p1 = (x3 * y3) * 4;int q1 = z3 & 0xF;return p1 >= 16 && q1 == 0;}

 

在右边我们可以看到，每个变量都被重命名为多个版本（由数字后缀表示）。在 if-then-else 语句之后，三个变量都会有两个不同的值，这取决于 a>3 的运行结果，因此有必要插入PHI 运算。

新的优化器能够利用PHI运算的优点，并且把整个函数变成与返回值1等价，所有其他的代码会被Dead Code Elimination 删除。这是1指令与之前在x64上生成的18进行比较。

对于 p1 >=16，会计算所有可能值，并将其与最小的可能值16比较。对于 q1 == 0， 会检测z1和z2的低位是否是零。

旧的表达式优化器不能推断包含这些PHI运算的较大的表达式 – 这将导致它错过了许多进行优化的机会，像上面列举的那些。在新的优化器中，每一个操作和静态分析都支持PHI。几个例子如下：

(phi 3, 5) + 2 -> phi 5, 7     // constant-fold by pushing operand inside a PHI

(phi b+3, b+5) - b -> phi 3, 5 // eliminate operation by pushing operand inside a PHI

phi a+x, b+x -> (phi a, b) + x // extract a common operand from a PHI

(phi 1,2) + 3 < (phi 3,4) + 5 -> true                 // fold compare by testing all combinations

(phi 1,2) * (phi 2,3) > (phi 6,7) * phi(2,3) -> false // similar to above example

(phi 1,0) * 5 > (phi 1,2) -> undecidable             // 0 * 5 < (phi 1,2)

以下是在Mozilla Firefox浏览器中发现的一个有趣的案例。一个布尔表达式，跨越了一个 if-then-else 语句，被用于一个否定的形式中 if(!expr)。新的算法试图取消一个反转布尔运算，通过下面转换来反转每一个子表达式，消除了反转。

(phi 0, (x ? 1 : 0)) ^ 1 -> phi 1, (x ? 0 : 1)

  • 更好的条件移动生成

转换分支成为CMOV 可以生成更多执行速度更快的紧凑的代码。后期的CMOV生成阶段，通过在新的优化过程中生成问题操作符被加强。在这样做的时候，已经存在的转换可以被应用，并且做了进一步简化。在下面的示例中，左边是一个新检测到的CMOV模式，右边是应用了转换之后的代码：

a < 0 ? 1 : 0 -> a >> 31           // logical shift

a < 0 ? 4 : 0 -> (a >> 31) & 4     // arithmetic shift

a<bool> != b<bool> ? 1 : 0 -> a ^ b // a, b must be Boolean values

CMOV的性能有时很难估计，尤其是在有良好的分支预测的现代CPU上。为了有益于分支会更快的情况，当配置文件信息可用的时候，如果此分支是可高度预测的，则不会产生CMOV。（这在很大程度上依赖于采取还是不采取）

  • 改进比较操作的优化

比较操作是改进最多的操作。由于减少分支数量有益于代码长度和性能，因此重点主要是在分支消除（通过证实它是采取还是不采取来消除分支）。此外，除了比较常量的常见测试外，静态分析是用来估计值的范围和已知的1/0位，使得能够处理更复杂的情况。在很多简化比较操作的转换中，下面是一个可以显著减少执行时间的例子：

a / 12 == 15 -> a in range [180, 192) -> (a – 180) < 12 // unsigned compare

除法运算（20+ 循环）被替换为简单的范围检查（2循环）。即使应用了“除以常数”的优化，它仍然比范围检查要慢几十倍。

  • 位估算器

这是一个强大的静态分析器，它可以用来提取关于值在编译时期的更多信息。提供的一些功能如下：

    • 估计已知1或0位
    • 证明一个值不为零
    • 估算最小值和最大值
    • 估算值的范围
    • 改进加法和减法的溢出检测

下面是一个简单的例子，它展示了在编译期间1/0位是如何被计算的，即使对初始值 (下面例子中的参数a）一无所知:

int test(unsigned char a) {

short b = a;   // b: 00000000________, a: ________

b <<= 4;       // b: 0000________0000

b |= 3;         // b: 0000________0011

return b != 0;  // -> return true

}

这些功能目前被使用的一些地方：

  • 转换有符号的指令成为无符号的：为取余或者除法操作生成更少的代码，允许将常量折叠成为LEA指令等。
  • 折叠比较操作和分支： 比较操作是通过已知位和值的范围信息来进行折叠的。例如，给定a == b， 如果已知 a 在某一个位置设置一个位，但是在b中的此位置一定没有设置，这两个值不可能相等。这可以应用到其他条件，例如小于操作可以检验符号位。当时用值的范围的时候，把a 的每一个范围与b 的每一个范围进行比较。
  • 改进溢出检查： 优化 a + C1 < C2 成为 a < C2 – C1 是不合理的，因为 a + C1 可能会溢出，生成不同的结果。使用已知位或者值范围，可以证明加法运算没有溢出。实际上，当 a 是一个较小类型的零扩展的时候，这样的情况经常发生。
  • 发现布尔和正值： 作为各种优化的先决条件，例如应用于问题操作。另一个例子是当一个值为正值时，消除ABS运算。
  • 删除多余的 AND/OR 指令，取消无用的转换：

a % C -> 0 if C is a power of two and the low bits in a are zero (a is a multiple of C)

a & C -> 0 if all bits that are one in C are known to be zero in a

a | C -> a if all bits that are one in C are known to be one in a

  • 改进消除公共子表达式

消除公共子表达式是一种优化，它通过用之前计算等价值的结果来替换一些操作，从而消除了多余的操作 – 这种情况发生的比想象中更多。现有的算法通过一种基于全域数值编号方式被增强，该方式增加了所发现的等价表达式的数量。尽管这是一个非常简单的初始实施，但这会使得此算法变得更加强大，它显示了对于代码长度和性能的显著改进。

在做表达式优化之前消除多余的操作也暴露出更多的机会。

例如，如果b和c相等，那么 (a+b)-c -> a 。

  • 利用有符号整数溢出未被定义

在历史上，Visual C++ 没有利用这样 一个事实，即C 和 C++ 标准中考虑有符号数操作溢出未定义的后果。其他的编译器在这点上非常积极，这促进了我们决定去利用未定义整数溢出的行为来实现一些模式。我们实现的这些，我们认为是安全的，并且在生成的代码中没有强加任何不必要的安全隐患。

添加了一个新的没有文档记载的编译选项来禁用这些优化，以防止应用程序有不符合标准的失败： -d2SSAOptimizerUndefinedIntOverflow- 。由于安全问题，我们已经看到一些情况下这些模式不应该被优化，即使下面的 C 和 C++ 标准允许我们通过潜在的溢出未定义来进行优化。

a + Constant > a -> true   // Constant > 0

a + Constant <= a -> false // Constant > 0

这两项测试（与减法类似）被经常用来检测文件阅读器和内存分配的溢出。然而这种用法是不符合标准的，并且有着众所周知的问题，启用这些转换可能会破坏应用程序的安全性。

 

对代码大小的影响

大多数应用程序的代码大小减少了，但由于与其他优化的交互作用，代码的大小也可能会增加。例如，更小的函数更容易被内联到更多的位置，导致整体代码大小的增加。

下面是在x64的计算机上编译几个大型应用程序的一些代码大小：

应用程序 旧编译器 新编译器 减少量
Windows 1,112,545,269 1,112,096,059 438 KB
SQL Server 64,078,336 64,032,256 46 KB
Chakra 5,963,621 5,952,997 10 KB

 

按照类别划分，下表列出了x64 windows内核建立时生成的链接代码和配置文件信息的指令的数目。可以看到更多复杂的指令，例如分支、区域和乘积中的代码都减少了。CMOV和SETcc中代码的增加是因为更多的分支被转化成了条件代码。

指令类型 旧编译器 新编译器 差异
CONVERSION 28075    27301 -774
LEA 87658    87395 -263
SHIFT 15266    15194 -72
SETcc 2222      2345 +123
JUMP 19797    19791 -6
BRANCH 143795    142591 -1204
MUL 2115    1990 -125
DIV 541    530 -11
CMOV 4192    5913 +1721

 

对编译器吞吐量的影响

对于这些所有的改进，编译时间只有+/-2%的差异，基本上保持不变，具体取决于被编译的应用程序。例如，谷歌chrome浏览器显示编译时间放缓了1.7%，而Windows编译内核显示增速了2.6%。可以让更少的代码完成旧的、较慢的优化传递，以此来解释增速。

测试方法

基于以往的经验和项目范围，它从一开始就明确了广泛测试需要采取中心角色来确保正确性。使用了几种测试方法，一些把避免出错放在第一位，另一些是为了捕获执行问题:

  • 通过正式验证模式避免执行bug

大多数模式都非常简单，例如x & 0 => 0。但总有一些模式需要验证，其并不总是很明显，有遗留错误的地方。最常见的验证bug是：

  • 未能检查输入的前提条件，例如需要正数，2的幂，高N 位是0的数，等等。
  • 未能区分有符号和无符号操作。这对指令来说是特别危险的，例如CMP, DIV/REM 和SHR。

Alive，是由微软研究院的努诺· 洛佩斯发明的一个工具，它是用于确保模式和先决条件都正确才执行他们的一个形式化验证工具。它使用的语言类似于LLVM IR和Z3定理验证装 置来验证输入的模式是否等于输出的模式­— —如果不相等，它打印一个反例。通过使Alive工具，LLVM团体已经成功的发现了许多bug。你可以在John Regehr 的博客：ALIVe: Automatic LLVM InstCombine Verifier 中找到更多关于Alive的详细信息。

  • 使用随机测试覆盖和测试尽可能多的模式

Csmith 是一个随机的C程序生成器，它被用于在各种编译器中发现了大量bug。超过1500万的生成程序已经由 CSmith来进行测试，在新的优化器上显示的几个bug,在其他的优化程序组件中添加这些bug。非常有助于处理大量失败的测试，即C-Reduce :它可以将200KB大小的测试代码减少到2-3kB，使它更容易发现bug所在的位置。

  • 每三个指令组成的表达式的测试

Opt-fuzz 是由美国犹他大学的约翰 Regehr发明的一个工具，它能够产生每N个指令为一组的小整数表达式和位数有限的可行常量作为LLVM IR。Clang/C2 项目使得2亿5000万的测试代码生成三指令表达式成为可能，且能显示细微的bug.

  • 使用检测和运行检查

复杂的组件，例如位估计器和值编号，通过在检测编译代码时调用运行时的库来验证编译时间，静态分析的结果是否真正有效来进行检测。例如，就编译器而言，它是验证那些估计必须始终为零的位在运行时都为零。就值编号而言，它用来确保那些被分配了相同的值数目的两个指令在运行时具有相同的值。

  • 测试流行的开源代码项目

暴露更多真实的编译器代码被证明是找到更多bug的有效的方式。这包括生成和测试谷歌浏览器、火狐浏览器、CoreCLR和Chakra。

未来的改进

正如我在这篇博客文章开头所述，许多未来优化器的功能将在框架设计的一些地方实行。下面的一些优化很可能是下一个版本的Visual Studio 重要的一部分— —它不包括任何有计划的长期项目：

  • 完成并启用对矢量操作的优化
  • 在C++代码中更好的优化布尔表达式
  • 去除对表达式结果没有影响的操作
  • 合并相似的分支
  • 若干位估计器的改进

 

结束语

请尝试用新的优化器生成并测试您的应用程序，报告任何你发现的问题。我们期待在评论部分看到您的建议和意见，让我们知道您是否有可以更好地进行优化或者不能优化的案例。

我们很高兴终于可以与您分享这个令人兴奋的新工作！这标志着将许多优化器改进的开始，这会被添加在未来发布的编译器中— —我们会持续发布。

 

谢谢，

Gratian Lup

Visual C++优化团队