代码转换元数据

概述

LLVM 转换 pass 可以通过将元数据附加到要转换的代码来控制。默认情况下,转换 pass 使用启发式方法来确定是否执行转换,以及在执行转换时,如何应用转换的其他细节 (例如,选择哪个向量化因子)。除非优化器另有指示,否则转换会保守地应用。这种保守主义通常允许优化器避免无利可图的转换,但在实践中,这会导致优化器不应用可能非常有利可图的转换。

前端可以向 LLVM pass 提供关于它们应该应用哪些转换的额外提示。这可以是无法从发出的 IR 中推导出的额外知识,或者是用户/程序员传递的指令。OpenMP 编译指导是后者的一个例子。

如果从程序中删除任何此类元数据,代码的语义绝不能改变。

循环元数据

属性可以附加到循环,如 ‘llvm.loop’ 中所述。属性可以描述循环的属性、禁用转换、强制执行特定转换和设置转换选项。

由于元数据节点是不可变的(除了 MDNode::replaceOperandWith,在唯一元数据上使用它是危险的),为了添加或删除循环属性,必须创建一个新的 MDNode 并将其分配为新的 llvm.loop 元数据。旧 MDNode 和循环之间的任何连接都将丢失。llvm.loop 节点也用作 LoopID (Loop::getLoopID()),即循环实际上获得了一个新的标识符。例如,llvm.mem.parallel_loop_access 引用了 LoopID。因此,如果在添加/删除循环属性后要保留并行访问属性,则任何 llvm.mem.parallel_loop_access 引用都必须更新为新的 LoopID。

转换元数据结构

一些属性描述了代码转换(展开、向量化、循环分发等)。它们可以是给优化器的提示,表明转换可能是有益的,使用特定选项的指令,或者传达来自用户的特定请求(例如 #pragma clang loop#pragma omp simd)。

如果强制执行转换但由于任何原因无法执行,则必须发出 optimization-missed 警告。语义信息,例如转换是安全的(例如 llvm.mem.parallel_loop_access),可以被优化器忽略而不生成警告。

除非显式禁用,否则任何优化 pass 都可以启发式地确定转换是否有利并应用它。如果指定了另一个转换的元数据,则在其之前应用不同的转换可能是无意的,因为它是应用于不同的循环或循环不再存在。为了避免必须显式禁用未知数量的 pass,属性 llvm.loop.disable_nonforced 禁用了所有可选的、高层次的、重构转换。

以下示例避免了循环在向量化之前被更改,例如被展开。

  br i1 %exitcond, label %for.exit, label %for.header, !llvm.loop !0
...
!0 = distinct !{!0, !1, !2}
!1 = !{!"llvm.loop.vectorize.enable", i1 true}
!2 = !{!"llvm.loop.disable_nonforced"}

在应用转换之后,将在转换后的和/或新的循环上设置后续属性。这允许指定包括后续转换在内的其他属性。出于兼容性原因,可以在同一元数据节点中指定多个转换,但它们的执行顺序是未定义的。例如,当同时指定 llvm.loop.vectorize.enablellvm.loop.unroll.enable 时,展开可能发生在向量化之前或之后。

例如,以下指示循环被向量化,然后才展开。

!0 = distinct !{!0, !1, !2, !3}
!1 = !{!"llvm.loop.vectorize.enable", i1 true}
!2 = !{!"llvm.loop.disable_nonforced"}
!3 = !{!"llvm.loop.vectorize.followup_vectorized", !{"llvm.loop.unroll.enable"}}

如果且仅当未指定后续属性时,pass 可能会自行添加属性。例如,向量化器添加 llvm.loop.isvectorized 属性和来自原始循环的所有属性,但不包括其循环向量化器属性。为了避免这种情况,可以使用空的后续属性,例如:

!3 = !{!"llvm.loop.vectorize.followup_vectorized"}

无法应用的转换的后续属性将永远不会添加到循环,因此实际上被忽略。这意味着此类属性中的任何后续转换都要求在其之前的转换在后续转换之前应用。如果强制执行转换,用户应该收到关于转换链中第一个无法应用的转换的警告。所有后续转换都将被跳过。

Pass 特定的转换元数据

转换选项特定于每个转换。在下面,我们介绍了每个 LLVM 循环优化 pass 的模型以及影响它们的元数据。

循环向量化和交错

循环向量化和交错被解释为单个转换。如果设置了 !{"llvm.loop.vectorize.enable", i1 true},则它被解释为强制的。

假设预向量化循环是

for (int i = 0; i < n; i+=1) // original loop
  Stmt(i);

那么向量化后的代码将近似为(假设 SIMD 宽度为 4)

int i = 0;
if (rtc) {
  for (; i + 3 < n; i+=4) // vectorized/interleaved loop
    Stmt(i:i+3);
}
for (; i < n; i+=1) // epilogue loop
  Stmt(i);

其中 rtc 是生成的运行时检查。

llvm.loop.vectorize.followup_vectorized 将设置向量化循环的属性。如果未指定,llvm.loop.isvectorized 将与原始循环的属性组合,以避免它被多次向量化。

llvm.loop.vectorize.followup_epilogue 将设置剩余循环的属性。如果未指定,它将具有原始循环的属性,并结合 llvm.loop.isvectorizedllvm.loop.unroll.runtime.disable (除非原始循环已经具有展开元数据)。

llvm.loop.vectorize.followup_all 指定的属性将添加到两个循环。

当使用后续属性时,它会替换为所生成的循环自动推导出的任何属性。因此,建议将 llvm.loop.isvectorized 添加到 llvm.loop.vectorize.followup_all,这可以避免循环向量化器再次尝试优化循环。

循环展开

如果存在任何 !{"llvm.loop.unroll.enable"} 元数据或选项 (llvm.loop.unroll.count, llvm.loop.unroll.full),则展开被解释为强制的。展开可以是完全展开、具有恒定循环次数的循环的部分展开或循环次数在编译时未知的循环的运行时展开。

如果循环已完全展开,则没有后续循环。对于部分/运行时展开,原始循环为

for (int i = 0; i < n; i+=1) // original loop
  Stmt(i);

被转换为(使用展开因子 4)

int i = 0;
for (; i + 3 < n; i+=4) { // unrolled loop
  Stmt(i);
  Stmt(i+1);
  Stmt(i+2);
  Stmt(i+3);
}
for (; i < n; i+=1) // remainder loop
  Stmt(i);

llvm.loop.unroll.followup_unrolled 将设置展开循环的循环属性。如果未指定,则复制原始循环的属性,但不包括 llvm.loop.unroll.* 属性,并将 llvm.loop.unroll.disable 添加到其中。

llvm.loop.unroll.followup_remainder 定义了剩余循环的属性。如果未指定,则剩余循环将没有属性。剩余循环可能由于完全展开而不存在,在这种情况下,此属性无效。

llvm.loop.unroll.followup_all 中定义的属性将添加到展开循环和剩余循环。

为了避免部分展开的循环再次展开,建议将 llvm.loop.unroll.disable 添加到 llvm.loop.unroll.followup_all。如果未为生成的循环指定后续属性,则会自动添加。

展开-并-阻塞

展开-并-阻塞使用以下转换模型(此处展开因子为 2)。目前,当转换不安全时,它不支持回退版本。

for (int i = 0; i < n; i+=1) { // original outer loop
  Fore(i);
  for (int j = 0; j < m; j+=1) // original inner loop
    SubLoop(i, j);
  Aft(i);
}
int i = 0;
for (; i + 1 < n; i+=2) { // unrolled outer loop
  Fore(i);
  Fore(i+1);
  for (int j = 0; j < m; j+=1) { // unrolled inner loop
    SubLoop(i, j);
    SubLoop(i+1, j);
  }
  Aft(i);
  Aft(i+1);
}
for (; i < n; i+=1) { // remainder outer loop
  Fore(i);
  for (int j = 0; j < m; j+=1) // remainder inner loop
    SubLoop(i, j);
  Aft(i);
}

llvm.loop.unroll_and_jam.followup_outer 将设置展开的外部循环的循环属性。如果未指定,则复制原始外部循环的属性,但不包括 llvm.loop.unroll.* 属性,并将 llvm.loop.unroll.disable 添加到其中。

llvm.loop.unroll_and_jam.followup_inner 将设置展开的内部循环的循环属性。如果未指定,则原始内部循环的属性将保持不变。

llvm.loop.unroll_and_jam.followup_remainder_outer 设置外部剩余循环的循环属性。如果未指定,它将没有任何属性。剩余循环可能由于完全展开而不存在。

llvm.loop.unroll_and_jam.followup_remainder_inner 设置内部剩余循环的循环属性。如果未指定,它将具有原始内部循环的属性。如果外部剩余循环被展开,则内部剩余循环可能会多次出现。

llvm.loop.unroll_and_jam.followup_all 中定义的属性将添加到所有上述输出循环。

为了避免展开的循环再次展开,建议将 llvm.loop.unroll.disable 添加到 llvm.loop.unroll_and_jam.followup_all。它抑制展开-并-阻塞以及额外的内部循环展开。如果未为生成的循环指定后续属性,则会自动添加。

循环分发

LoopDistribution pass 尝试将循环的可向量化部分与不可向量化部分分开(否则会使整个循环不可向量化)。从概念上讲,它转换如下循环

for (int i = 1; i < n; i+=1) { // original loop
  A[i] = i;
  B[i] = 2 + B[i];
  C[i] = 3 + C[i - 1];
}

转换为以下代码

if (rtc) {
  for (int i = 1; i < n; i+=1) // coincident loop
    A[i] = i;
  for (int i = 1; i < n; i+=1) // coincident loop
    B[i] = 2 + B[i];
  for (int i = 1; i < n; i+=1) // sequential loop
    C[i] = 3 + C[i - 1];
} else {
  for (int i = 1; i < n; i+=1) { // fallback loop
    A[i] = i;
    B[i] = 2 + B[i];
    C[i] = 3 + C[i - 1];
  }
}

其中 rtc 是生成的运行时检查。

llvm.loop.distribute.followup_coincident 设置所有没有循环携带依赖的循环(即可向量化循环)的循环属性。可能存在多个这样的循环。如果未定义,则循环将继承原始循环的属性。

llvm.loop.distribute.followup_sequential 设置具有潜在不安全依赖的循环的循环属性。应该最多只有一个这样的循环。如果未定义,则循环将继承原始循环的属性。

llvm.loop.distribute.followup_fallback 定义了回退循环的循环属性,当需要循环版本控制时,它是原始循环的副本。如果未定义,则回退循环将继承原始循环的所有属性。

llvm.loop.distribute.followup_all 中定义的属性将添加到所有上述输出循环。

建议将 llvm.loop.disable_nonforced 添加到 llvm.loop.distribute.followup_fallback。这避免了回退版本(可能永远不会执行)被进一步优化,从而增加代码大小。

版本控制 LICM

Pass 将代码从循环中提升出来,这些代码仅在动态条件适用时才是循环不变的。例如,它转换循环

for (int i = 0; i < n; i+=1) // original loop
  A[i] = B[0];

转换为

if (rtc) {
  auto b = B[0];
  for (int i = 0; i < n; i+=1) // versioned loop
    A[i] = b;
} else {
  for (int i = 0; i < n; i+=1) // unversioned loop
    A[i] = B[0];
}

运行时条件 (rtc) 检查数组 A 和元素 B[0] 是否不别名。

目前,此转换不支持后续属性。

循环交换

目前,LoopInterchange pass 不使用任何元数据。

不明确的转换顺序

如果定义了多个转换,则它们的执行顺序取决于 LLVM 的 pass pipeline 中的顺序,该顺序可能会发生变化。默认优化 pipeline(任何高于 -O0 的级别)具有以下顺序。

当使用旧版 pass 管理器时

  • LoopInterchange(如果启用)

  • SimpleLoopUnroll/LoopFullUnroll(仅执行完全展开)

  • VersioningLICM(如果启用)

  • LoopDistribute

  • LoopVectorizer

  • LoopUnrollAndJam(如果启用)

  • LoopUnroll(部分和运行时展开)

当使用带有 LTO 的旧版 pass 管理器时

  • LoopInterchange(如果启用)

  • SimpleLoopUnroll/LoopFullUnroll(仅执行完全展开)

  • LoopVectorizer

  • LoopUnroll(部分和运行时展开)

当使用新的 pass 管理器时

  • SimpleLoopUnroll/LoopFullUnroll(仅执行完全展开)

  • LoopDistribute

  • LoopVectorizer

  • LoopUnrollAndJam(如果启用)

  • LoopUnroll(部分和运行时展开)

剩余的转换

在最后一个转换 pass 之后未应用的强制转换应报告给用户。转换 pass 本身不能负责此报告,因为它们可能不在 pipeline 中,可能有多个 pass 能够应用转换(例如 LoopInterchange 和 Polly),或者转换属性可能“隐藏”在另一个 pass 的后续属性中。

-transform-warning pass (WarnMissedTransformationsPass) 发出此类警告。它应该放在最后一个转换 pass 之后。

当前的 pass pipeline 具有固定的转换 pass 执行顺序。转换可能在稍后执行的 pass 的后续步骤中,因此会剩余。例如,循环嵌套不能使用当前的 pass pipeline 进行分发,然后再交换。循环分发将执行,但之后没有循环交换 pass,因此任何循环交换元数据都将被忽略。在这种情况下,-transform-warning 应该发出警告。

未来版本的 LLVM 可能会通过使用动态排序执行转换来解决此问题。