Loop with a zero execution time

Is it possible to have a loop which has a zero execution time? I would think that even an empty loop should have an execution time since there is an overhead associated with it.

Solution 1:

Yes, under the as-if rule the compiler is only obligated to emulate the observable behavior of the code, so if you have a loop that does not have any observable behavior then it can be optimized away completely and therefore will effectively have zero execution time.

Examples

For example the following code:

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

compiled with gcc 4.9 using the -O3 flag basically ends up reducing to the following (see it live):

main:
  xorl  %eax, %eax  #
  ret

Pretty much all optimizations allowed fall under the as-if rule, the only exception I am aware of is copy elison which is allowed to effect the observable behavior.

Some other examples would include dead code elimination which can remove code that the compiler can prove will never be executed. For example even though the following loop does indeed contain a side effect it can be optimized out since we can prove it will never be executed (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 ;
    }
  }
}

The loop will optimize away the same as the previous example. A more interesting example would be the case where a calculation in a loop can be deduced into a constant thereby avoiding the need for a loop(not sure what optimization category this falls under), for example:

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

can be optimized away to (see it live):

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

We can see there is no loop involved.

Where is as-if Rule covered in the standard

The as-if rule is covered in the draft C99 standard section 5.1.2.3 Program execution which says:

In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

The as-if rule also applies to C++, gcc will produce the same result in C++ mode as well. The C++ draft standard covers this in section 1.9 Program execution:

The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.5

Solution 2:

Yes - if the compiler determines that the loop is dead code (will never execute) then it will not generate code for it. That loop will have 0 execution time, although strictly speaking it doesn't exist at the machine code level.

Solution 3:

As well as compiler optimisations, some CPU architectures, particularly DSPs, have zero overhead looping, whereby a loop with a fixed number of iterations is effectively optimised away by the hardware, see e.g. http://www.dsprelated.com/showmessage/20681/1.php