LLVM IR 未定义行为 (UB) 手册

摘要

本文档描述了 LLVM IR 中的未定义行为 (UB)，包括 undef 和 poison 值，以及 freeze 指令。我们还提供了关于何时使用每种形式的 UB 的指南。

引言

未定义行为 (UB) 用于指定我们不希望指定具体结果的边界情况的行为。UB 也用于为优化器提供额外的约束（例如，前端通过语言类型系统或运行时保证的假设）。例如，我们可以将除以零的结果指定为零，但由于我们实际上对结果不感兴趣，因此我们说它是 UB。

LLVM 中存在两种形式的未定义行为：立即 UB 和延迟 UB。后者有两种形式：undef 和 poison 值。还有一个 freeze 指令来驯服延迟 UB 的传播。LLVM 中的值格是：立即 UB > poison > undef > freeze(poison) > 具体值。

我们在下面详细解释每个概念。

立即 UB

立即 UB 是最严重的 UB 形式。应尽可能避免使用它。立即 UB 应该仅用于在 LLVM 支持的大多数 CPU 中会陷入陷阱的操作。示例包括除以零、解引用空指针等。

应该避免立即 UB 的原因是它使诸如提升之类的优化变得更加困难。考虑以下示例

define i32 @f(i1 %c, i32 %v) {
  br i1 %c, label %then, label %else

then:
  %div = udiv i32 3, %v
  br label %ret

else:
  br label %ret

ret:
  %r = phi i32 [ %div, %then ], [ 0, %else ]
  ret i32 %r
}

我们可能会倾向于通过删除分支并推测性地执行除法来简化此函数，因为 %c 在大多数情况下为真。我们将获得以下 IR

define i32 @f(i1 %c, i32 %v) {
  %div = udiv i32 3, %v
  %r = select i1 %c, i32 %div, i32 0
  ret i32 %r
}

但是，这种转换是不正确的！由于当除数为零时，除法会触发 UB，因此我们只能在我们确定不会遇到该条件时才推测性地执行。上面的函数，当作为 f(false, 0) 调用时，在优化之前将返回 0，并在优化后触发 UB。

此示例突出了为什么我们尽可能减少触发立即 UB 的情况。作为经验法则，仅对于大多数受支持架构的 CPU 陷入陷阱的情况使用立即 UB。

时间旅行

LLVM IR 中的立即 UB 允许所谓的“时间旅行”。这意味着如果程序触发 UB，那么我们不需要保留其任何可观察的行为，包括 I/O。例如，以下函数在调用 printf 后触发 UB

define void @fn() {
  call void @printf(...) willreturn
  unreachable
}

由于我们知道 printf 总是会返回，并且由于 LLVM 的 UB 可以时间旅行，因此完全可以删除对 printf 的调用，并将函数优化为简单的

define void @fn() {
  unreachable
}

延迟 UB

延迟 UB 是一种较轻形式的 UB。它使指令能够被推测性地执行，同时将一些边界情况标记为具有错误的值。延迟 UB 应该用于常见 CPU 提供的语义不同的情况，但 CPU 不会陷入陷阱。

例如，考虑移位指令。当移位量等于或大于位宽时，x86 和 ARM 架构提供不同的语义。我们可以通过以下两种方式之一解决这种紧张关系：1) 为 LLVM 选择 x86/ARM 语义之一，这将使为另一个架构发出的代码速度变慢；2) 将这种情况定义为产生 poison。LLVM 选择了后一种选择。对于 C 或 C++ 等语言的前端（例如，clang），它们可以将源代码程序中的移位直接映射到 LLVM IR 中的移位，因为 C 和 C++ 的语义将此类移位定义为 UB。对于提供强大语义的语言，它们必须有条件地使用移位的值，例如

define i32 @x86_shift(i32 %a, i32 %b) {
  %mask = and i32 %b, 31
  %shift = shl i32 %a, %mask
  ret i32 %shift
}

LLVM 中有两种延迟 UB 值：undef 和 poison，我们将在下面描述它们。

Undef 值

警告

Undef 值已被弃用，应仅在绝对必要时使用。Undef 值的用法应限制为表示未初始化内存的加载。这是 IR 语义中唯一尚未被替代方案替换的部分（工作正在进行中）。

undef 值表示给定类型的任何值。此外，每个使用依赖于 undef 的指令都可以观察到不同的值。例如

define i32 @fn() {
  %add = add i32 undef, 0
  %ret = add i32 %add, %add
  ret i32 %ret
}

毫不奇怪，第一个加法产生 undef。但是，第二个加法的结果更加微妙。我们可能会倾向于认为它会产生一个偶数。但它可能不是！由于每个 undef 的（传递）使用都可以观察到不同的值，因此第二个加法等效于 add i32 undef, undef，这等效于 undef。因此，上面的函数等效于

define i32 @fn() {
  ret i32 undef
}

每次调用此函数都可能观察到不同的值，即任何 32 位数字（偶数和奇数）。

由于每次使用 undef 都可以观察到不同的值，因此如果我们不确定某个值不是 undef，则某些优化是错误的。考虑一个将数字乘以 2 的函数

define i32 @fn(i32 %v) {
  %mul2 = mul i32 %v, 2
  ret i32 %mul2
}

即使 %v 是 undef，此函数也保证返回一个偶数。但是，正如我们在上面看到的，以下函数不是

define i32 @fn(i32 %v) {
  %mul2 = add i32 %v, %v
  ret i32 %mul2
}

这个优化是错误的，仅仅是因为 undef 值存在，即使它们没有在此程序的这一部分中使用，因为 LLVM 无法判断 %v 是否为 undef。

查看值格，undef 值只能用 freeze 指令或具体值替换。一个结果是，将 undef 作为操作数提供给对于该操作数的某些值会触发 UB 的指令会使程序变为 UB。例如，udiv %x, undef 是 UB，因为我们将 undef 替换为 0 (udiv %x, 0)，这变得很明显它是 UB。

Poison 值

Poison 值是比 undef 更强形式的延迟 UB。它们仍然允许指令被推测性地执行，但它们会污染整个表达式 DAG（除了一些例外），类似于浮点 NaN 值。

示例

define i32 @fn(i32 %a, i32 %b, i32 %c) {
  %add = add nsw i32 %a, %b
  %ret = add nsw i32 %add, %c
  ret i32 %ret
}

加法中的 nsw 属性指示如果存在有符号溢出，则操作产生 poison。如果第一个加法溢出，则 %add 为 poison，因此 %ret 也是 poison，因为它会污染整个表达式 DAG。

Poison 值可以用任何类型的值替换（undef、具体值或 freeze 指令）。

Poison 值通过 Select 的传播

如果任何输入是 poison，则大多数指令都返回 poison。select 指令是一个值得注意的例外，当且仅当条件是 poison 或选定的值是 poison 时，它才是 poison。这意味着 select 充当 poison 传播的屏障，这会影响可以执行哪些优化。

例如，考虑以下函数

define i1 @fn(i32 %x, i32 %y) {
  %cmp1 = icmp ne i32 %x, 0
  %cmp2 = icmp ugt i32 %x, %y
  %and = select i1 %cmp1, i1 %cmp2, i1 false
  ret i1 %and
}

将 select 优化为 and 是不正确的，因为当 %cmp1 为 false 时，仅当 %x 为 poison 时，select 才是 poison，而下面的 and 如果 %x 或 %y 是 poison，则为 poison。

define i1 @fn(i32 %x, i32 %y) {
  %cmp1 = icmp ne i32 %x, 0
  %cmp2 = icmp ugt i32 %x, %y
  %and = and i1 %cmp1, %cmp2     ;; poison if %x or %y are poison
  ret i1 %and
}

但是，如果条件中使用了值的所有操作数，则可以进行优化（请注意 select 中翻转的操作数）

define i1 @fn(i32 %x, i32 %y) {
  %cmp1 = icmp ne i32 %x, 0
  %cmp2 = icmp ugt i32 %x, %y
  %and = select i1 %cmp2, i1 %cmp1, i1 false
  ; ok to replace with:
  %and = and i1 %cmp1, %cmp2
  ret i1 %and
}

Freeze 指令

有时 undef 和 poison 值都会过多地向下传播到表达式 DAG 中。Undef 值是因为每个传递使用都可以观察到不同的值，而 poison 值是因为它们使整个 DAG 变为 poison。在某些情况下，停止这种传播非常重要。这就是 freeze 指令的用武之地。

以下面的示例函数为例

 define i32 @fn(i32 %n, i1 %c) {
 entry:
   br label %loop

loop:
   %i = phi i32 [ 0, %entry ], [ %i2, %loop.end ]
   %cond = icmp ule i32 %i, %n
   br i1 %cond, label %loop.cont, label %exit

loop.cont:
   br i1 %c, label %then, label %else

 then:
   ...
   br label %loop.end

 else:
   ...
   br label %loop.end

 loop.end:
   %i2 = add i32 %i, 1
   br label %loop

 exit:
   ...
 }

假设我们想对上面的循环执行循环解开关，因为循环内的分支条件是不变的。我们将获得以下 IR

 define i32 @fn(i32 %n, i1 %c) {
 entry:
   br i1 %c, label %then, label %else

then:
   %i = phi i32 [ 0, %entry ], [ %i2, %then.cont ]
   %cond = icmp ule i32 %i, %n
   br i1 %cond, label %then.cont, label %exit

then.cont:
   ...
   %i2 = add i32 %i, 1
   br label %then

else:
   %i3 = phi i32 [ 0, %entry ], [ %i4, %else.cont ]
   %cond = icmp ule i32 %i3, %n
   br i1 %cond, label %else.cont, label %exit

else.cont:
   ...
   %i4 = add i32 %i3, 1
   br label %else

 exit:
   ...
 }

有一个微妙的陷阱：当使用 %n 为零调用函数时，原始函数不会在 %c 上分支，而优化后的函数会分支。在延迟 UB 值上分支是立即 UB，因此这种转换通常是错误的，因为 %c 可能是 undef 或 poison。

像这样的情况需要一种驯服延迟 UB 值的方法。这正是 freeze 指令的用途！当给定一个具体值作为参数时，freeze 是一个空操作，按原样返回参数。当给定一个 undef 或 poison 值时，freeze 返回该类型的非确定性值。这与 undef 不同：freeze 返回的值对于所有用户都是相同的。

在 freeze 返回的值上分支始终是安全的，因为它要么始终如一地评估为 true，要么始终如一地评估为 false。我们可以使上面的循环解开关优化正确，如下所示

define i32 @fn(i32 %n, i1 %c) {
entry:
  %c2 = freeze i1 %c
  br i1 %c2, label %then, label %else

编写没有未定义行为的测试

编写测试时，务必确保它们不会不必要地触发 UB。一些自动化测试缩减有时使用 undef 或 poison 值作为虚拟值，但如果这导致触发 UB，则认为这是一种不良做法。

例如，假设我们想编写一个测试，并且我们不关心特定的除数值，因为我们的优化无论如何都会启动

 define i32 @fn(i8 %a) {
   %div = udiv i8 %a, poison
   ...
}

此测试的问题在于它触发了立即 UB。这阻止了 Alive 等验证工具验证优化的正确性。因此，拥有不必要的立即 UB 的测试被认为是一种不良做法（除非这正是测试的目的）。上面的测试应该使用虚拟函数参数而不是使用 poison

 define i32 @fn(i8 %a, i8 %dummy) {
   %div = udiv i8 %a, %dummy
   ...
}

测试中立即 UB 的常见来源包括在 undef/poison 条件上分支以及解引用 undef/poison/空指针。

注意

如果您需要一个占位符值作为可能触发 UB 的指令的参数传递，请向函数添加一个新参数，而不是使用 undef 或 poison。

总结

LLVM IR 中的未定义行为 (UB) 由两个明确定义的概念组成：立即 UB 和延迟 UB（undef 和 poison 值）。将延迟 UB 值传递给某些操作会导致立即 UB。在某些情况下，可以通过使用 freeze 指令来避免这种情况。

LLVM 中的值格是：立即 UB > poison > undef > freeze(poison) > 具体值。仅将值从左向右转换是有效的（例如，poison 值可以用具体值替换，但反之则不然）。

Undef 现在已被弃用，应仅用于表示未初始化内存的加载。