Петля с нулевым временем выполнения

Ответ 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, единственным исключением, о котором я знаю, является copy 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 рассматривается в стандартном разделе проекта C99 5.1.2.3 Выполнение программы, в котором говорится:

В абстрактной машине все выражения оцениваются в соответствии с семантика. Фактическая реализация не должна оценивать часть выражение, если оно может вывести, что его значение не используется и что нет требуются побочные эффекты (в том числе вызванные вызовом функция или доступ к энергозависимому объекту).

правило as-if также применимо к С++, gcc приведет к такому же результату в режиме С++. Проект стандарта С++ охватывает это в разделе 1.9 Выполнение программы:

Семантические описания в этом Международном стандарте определяют параметризованной недетерминированной абстрактной машиной. Этот международный Стандарт не требует от структуры соответствия Реализации. В частности, им не нужно копировать или эмулировать структура абстрактной машины. Скорее, соответствующие реализации требуются для подражания (только) наблюдаемого поведения абстрактного как описано ниже .5

Ответ 2

Да - если компилятор определяет, что цикл является мертвым кодом (никогда не будет выполняться), то он не будет генерировать код для него. Этот цикл будет иметь 0 времени выполнения, хотя, строго говоря, он не существует на уровне машинного кода.

Ответ 3

Как и оптимизация компилятора, некоторые архитектуры ЦП, особенно DSP, имеют нулевой цикл обработки, в результате чего цикл с фиксированным числом итераций эффективно оптимизируется аппаратным обеспечением, см., например, http://www.dsprelated.com/showmessage/20681/1.php

Ответ 4

Компилятор не обязан оценивать выражение или часть выражения, которое не имеет побочных эффектов и результат которого отбрасывается.

Harbison and Steele, C: Справочное руководство