循环执行时间为零

Question

是否有可能有一个零执行时间的循环？我认为即使是一个空循环也应该有一个执行时间,因为它有与之相关的开销.

Answer 1

是的,在as-if规则下,编译器只有义务模拟代码的可观察行为,因此如果你有一个没有任何可观察行为的循环,那么它可以完全优化掉,因此实际上没有执行时间.

例子

例如,以下代码:

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

gcc 4.9使用该-O3标志编译基本上最终减少到以下(见它直播):

main:
  xorl  %eax, %eax  #
  ret

几乎所有的优化都属于as-if规则,我所知道的唯一例外是复制elison,它被允许影响可观察的行为.

其他一些示例将包括死代码消除,它可以删除编译器可以证明永远不会执行的代码.例如,即使以下循环确实包含副作用,它也可以进行优化,因为我们可以证明它永远不会被执行(现场直播):

#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 ) ;

可以优化到(现场观看):

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

我们可以看到没有涉及循环.

标准中涵盖的as-if规则在何处

在AS-如果规则被覆盖在C99标准草案,5.1.2.3 计划执行它说:

在抽象机器中,所有表达式都按语义指定进行计算.实际实现不需要评估表达式的一部分,如果它可以推断出它的值未被使用并且不产生所需的副作用(包括由调用函数或访问易失性对象引起的任何副作用).

该AS-如果规则也适用于C++,gcc会产生在C++中模式相同的结果为好.C++草案标准在1.9 程序执行部分中介绍了这一点:

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

Answer 2

是 - 如果编译器确定循环是死代码(永远不会执行),那么它将不会为它生成代码.该循环将具有0个执行时间,但严格来说,它在机器代码级别不存在.

Answer 3

除了编译器优化之外,一些CPU架构(尤其是DSP)具有零开销循环,其中具有固定迭代次数的循环被硬件有效地优化,参见例如http://www.dsprelated.com/showmessage/20681 /1.php