执行时间为零的循环

有没有可能有一个执行时间为零的循环？我认为即使是一个空循环也应该有一个执行时间，因为存在与之相关的开销。

5091 次浏览
小开

是的-如果编译器确定循环是死代码(永远不会执行) ，那么它将不会为它生成代码。该循环的执行时间为0，尽管严格地说，它不存在于机器代码级别。

小开

是的，在 仿佛统治一切下，编译器只有义务模拟代码的可观察行为，所以如果你有一个没有任何可观察行为的循环，那么它可以被完全优化掉，因此有效地执行时间为零。

例子

例如以下代码:

int main()
{
int j = 0 ;
for( int i = 0; i < 10000; ++i )
{
++j ;
}
}

使用 -O3标志用 gcc 4.9编译，最终基本上减少到以下(% 2C% 22指令% 22% 3Atrue% 2C% 22评论只有% 22% 3Atrue% 2C% 22着色 Asm% 22% 3Atrue% 7D% 2C% 22编译器% 22% 3A% 5B% 7B% 22source% 22% 3A% 22JYOwLgBAtghqAUBKAUAb2RCpICsIF4IAGCAbgwgDMB7AJ3i3CwONOYB4IBGI3otgNQDgEFJnSZMQvOUwBfZHKAAA% 22% 2C% 22编译器% 2A% 22% 22% 22% 2Fopt% 2Fgcc-4.9.0% 2Fbin% 2Fg% 2B% 2B% 22% 2C% 2C% 22-std% 22% 3A% 3Dc% 2B% 2B11% 20-O2% 20-fno-inline-small-function% 20% 22% 7D% 7D”rel = “ nofollow”>) :

main:
xorl  %eax, %eax  #
ret

几乎所有允许的优化都属于 仿佛统治一切，我所知道的唯一例外是 收到 Elison，它允许影响可观察到的行为。

其他一些例子包括 死码删除，它可以删除编译器可以证明永远不会执行的代码。例如，即使下面的循环确实包含一个副作用，它可以被优化出来，因为我们可以证明它将永远不会被执行(@ 2% 3A% 22-std% 3Dc% 2B% 2B11% 20-O3% 20-f怖-asm% 20-fno-inline-small-function% 20% 22% 7D% 5D% 7D”rel = “ nofollow”> see it live ) :

#include <stdio.h>


int main()
{
int j = 0 ;
if( false ) // The loop will never execute
{
for( int i = 0; i < 10000; ++i )
{
printf( "%d\n", j ) ;
++j ;
}
}
}

循环将与前面的示例一样进行优化。一个更有趣的例子是，循环中的一个计算可以推导成一个常数，从而避免了循环(不确定这属于哪个优化类别)的需要，例如:

int j = 0 ;
for( int i = 0; i < 10000; ++i )
{
++j ;
}
printf( "%d\n", j ) ;

可优化为(2C% 22编译器% 22% 3A% 5B% 7B% 22source% 22% 3A% 22MQSwdgxgNgrgJgUwAQB4DOAXOID2A6ACwD4AoE8DJAWwENwAKAShIG8SkOkKkArJAXiQAGJAG52nAGY4ATvS5hKIAcNFdUSAIxCdQtQGp9y5pyRtAvhI4AHGRUnyARAFI4AHTDuAGl4kRjESWyAA% 3D% 22% 2C% 22% 2A% 22% 2A% 22% 22% 2Fopt% 2Fgcc-4.9.0% 2Fbin% 2Fg% 2B% 22% 2C% 22options% 22% 3A% 22-std% 3Dc% 2B% 2B11% 20-O3% 20-fno-inline-small-function% 20% 22% 7D% 7D”rel = “ nofollow”>) :

movl    $10000, %esi    #,
movl    $.LC0, %edi #,
xorl    %eax, %eax  #
call    printf  #

我们可以看到没有循环。

标准中哪些地方涵盖了仿真规则

仿佛统治一切涵盖在 C99标准条款草案 5.1.2.3 程序执行中，其中说:

在抽象机器中，所有表达式都按照 实际的实现不需要计算 如果它能够推断出它的值没有被使用，并且没有 产生所需的副作用(包括调用 函数或访问易失性对象)。

仿佛统治一切也适用于 C + + ，gcc在 C + + 模式下也会产生同样的结果。C + + 标准草案在 1.9 程序执行节中涵盖了这一点:

本国际标准中的语义描述定义了 参数化不确定抽象机 标准对合格的结构没有要求 特别是，它们不需要复制或模拟 抽象机器的结构。相反，一致的实现 要求(仅仅)模仿抽象的可观察的行为 机器，如下所述。5

小开

除了编译器优化，一些 CPU 架构，特别是 DSP，也有 零开销循环，通过这种方式，具有固定迭代次数的循环被硬件有效地优化掉了，参见例如 http://www.dsprelated.com/showmessage/20681/1.php

小开

编译器不必计算没有副作用且其结果被丢弃的表达式或表达式的一部分。

Harbison 和 Steele C: 参考手册


提交答案