为了避免编译器 crash 和出现错误的编译，随机测试(random testing) 是一种有效地发现编译器 bug 的方式。简单了解了一下这块内容，记录一下。

YARPGen(Yet Another Random Program Generator)

这里介绍一种 C/C++ 的随机测试生成器 YARPGen，在不依靠动态检查(dynamic check、运行时检测) 的情况下，使用生成规则(generation policies)，生成没有未定义行为(undefined behavior，UB) 的表达式，同时提升了生成代码的多样性，触发更多编译器优化的可能。

要寻找难以发现的编译器 bug，使用生成规则还可以减少测试时间，而 YARPGen 也提升了 LLVM 20%、GCC 40% 的优化触发次数，更容易发现编译器优化的问题。

编译器错误所面临的问题：

  • 编译器经常会有代码改动的情况，因为修改源码、支持新的平台、支持新的优化等，而且还会不断使用复杂的自定义的算法，去优化编译器的性能，导致可能会出现编译器 bug。
  • 大多数随机测试生成器并不能很好地处理特殊案例，会达到一个饱和点(saturation point)，但再使用另一个生成器时，又可以暴露另外的一些问题。

这里主要关注两种编译器 bug：

  • ICE(internal compiler error)，编译器 crash，或者没有生成代码就提前终止。
  • miscompilation(wrong code bug)，生成的代码没法正确计算。

这里的处理比较麻烦的是 miscompilation，它会导致出现未定义行为(undefined behavior，UB)，YARPGen 会有类型检查，避免非法的类型转换的出现。而且通过一些限制，YARPGen 可以处理掉很多简单的 UB 行为(未初始化变量的使用等)。但还有一些比较难避免的，比如整型溢出(integer overflow)，YARPGen 就通过运行静态检查来保证生成代码的正确性。

生成代码

YARPGen 生成代码会有以下步骤：

  • 创建环境(creating the environment)。YARPGen 创建类型表，然后创建这些类型的全局变量，存到符号表中。
  • 创建语句(creating statements)。每条语句完成以下其中一个事情：
    • 声明一个随机选取的类型的局部变量，分配一个随机表达式的求值。local = <expression>
    • 把随机表达式的结果赋给一个已有的变量。old_value = <expression>
    • 开始使用条件表达式，随机生成条件和一到两个新的条件执行代码块。一旦代码块的嵌套深度超出配置限制，就不要再生成条件表达式了。
  • 创建表达式(creating expressions)。生成表达式是自顶向下(top-down) 的，所以可以避免副作用(side effect)。
  • 避免 UB 行为(avoiding UB in expressions)。表达式会以自下而上(bottom-up) 的方式进行类型检查，自下而上是为了在分析表达式前，先能够知晓子表达式的类型，同时可以进行必要的检查和重写修正。
  • 生成完整的测试(generating the test harness)。除了包含测试函数的文件，YARPGen 还会为每个测试用例创建额外的两个文件，一个是声明，包含所有生成的类型、测试函数、所有全局变量；另一个是主要文件，包含 main 函数、以及测试函数用到的所有全局变量的定义。
    • main 函数会调用测试函数，计算所有输出和全局变量的哈希值。这样，编译器的修改或者不同平台、优化，通过比对哈希值是否一致，就可以知道是否存在编译器 bug 了。

前面还提到过，YARPGen 通过生成规则使得能够触发更多的编译器优化来进行测试。

这些策略主要来源于编译器优化是如何进行的：

  • 运算(Arithmetic, logical, and bitwise contexts)。对于编译器优化的语句，YARPGen 随机选取一段范围的代码，或者是表达式树的子树，生成来使用有限的运算子集，这样主要是为了能够发现更多的 bugs。
  • 常量(policies for constants)。使用边界值，如 INT_MAX，而且 YARPGen 会缓存前面使用过的常量，然后随机重用，来触发如常量折叠等优化。
  • 公共子表达式缓存(common subexpression buffer)。YARPGen 缓存使用过的子表达式，同样随机重用，来触发公共子表达式删除的优化。

当然 YARPGen 还有很多限制和不支持，比如指针操作、函数调用、枚举值、动态内存分配等。

不过最近也支持了编译器循环优化的测试，循环对于机器学习、大数据、游戏运算等至关重要，所以补全这块能力非常必要。

参考