当循环变量在溢出时未定义时，可以进行哪些优化？

Question

本文提供了一个 C 代码示例片段，由于循环计数器的类型未定义溢出，编译器可以对其进行优化。

这是带有评论的片段

for (i = 0; i <= N; ++i) { ... }

在此循环中，如果“i”在溢出时未定义，编译器可以假设循环将精确迭代 N+1 次，这允许进行广泛的循环优化。另一方面，如果定义了变量为了解决溢出问题，编译器必须假设循环可能是无限的（如果 N 为 INT_MAX，就会发生这种情况）——然后禁用这些重要的循环优化。这尤其影响 64 位平台，因为很多代码使用“int”作为归纳变量。

我有很多疑问：

• 我明白，如果

  i

  的类型在溢出时未定义，编译器可以假设

  i

  不会回绕，但是为什么这意味着循环运行

  N+1

  次？循环体中的

  i

  不能被改变吗？
• 即使有了这个假设，它还能基于此进行哪些优化？例如，如果

  N

  在编译时未知，则无法展开循环，不是吗？
• “广泛的循环优化”让我觉得我在这里错过了很多。

Answer 1

我明白，如果

i

的类型在溢出时未定义，编译器可以假设

i

不会回绕，但是为什么这意味着循环运行

N+1

次？循环体中的

i

不能被改变吗？

首先回答第二个问题，作者以他们的例子为例，

i

在循环中没有改变，并且循环不包含

break

或其他会终止循环的代码。这只是一个简短的示例，针对知识渊博的受众，希望他们熟悉这些内容并填补空白。

回答第一个问题，

i

不会换行这一事实并不意味着循环将运行

N+1

次。这段话并没有这么说，它说它“允许”编译器“假设”这一点。理由是这样的： 如果 N

使得

++i
• 永远不会溢出，则循环恰好运行

  N+1

  次。如果

  N

  使得
++i
• 在某个时刻溢出，则该行为未定义，并且语言标准允许任何行为。如果程序崩溃，则符合标准。如果

  N+1

  换行并且测试

  i <= N

  始终为 true，并且循环永远迭代，则符合标准。如果循环运行

  N+1

  次，则符合标准。作为编译器实现者，我们可以选择这些行为中的任何一个，并且生成的行为将符合语言标准。

  如果有自由选择，在这种情况下，我们选择表现得好像循环总是运行 

  N+1
次，因为这是一个简化的假设：它为我们提供了针对非溢出情况和溢出情况的相同规范。

即使有了这个假设，它还能基于此进行哪些优化？例如，如果

N

在编译时未知，则无法展开循环，不是吗？

• 如果循环是
for (int i = 0; i <= N; ++i) { sum += i; }

，我们可以优化为

sum += N*(N+1)/2;

（适当考虑可能的溢出情况进行计算）并完全删除循环。如果我们需要表现得就像

i

在溢出时被包裹一样，我们就无法完全删除循环；我们需要测试一下

N

的值是否会导致循环退出或永远继续下去。 （尽管标准中关于循环取得进展的其他语言；这是一个简化的示例。） “广泛的循环优化”让我觉得我在这里错过了很多。

• 这是一个广泛的主张，无需列出几个，所以不要太担心这部分。