CODEWITHSUNDEEP
cloopsfor-loopoptimizationcompiler-optimization
Ariel
Ariel

Reputation: 26783

C compiler optimize loop by running it

Can a C compiler ever optimize a loop by running it?

For example:

int num[] = {1, 2, 3, 4, 5}, i;
for(i = 0; i < sizeof(num)/sizeof(num[0]); i++) {
  if(num[i] > 6) {
    printf("Error in data\n");
    exit(1);
  }
}

Instead of running this each time the program is executed, can the compiler simply run this and optimize it away?

Upvotes: 3

Views: 245

Answers (4)

supercat
supercat

Reputation: 81307

Compilers can do even better than that. Not only can compilers examine the effect of running code "forward", but the Standard even allows them to work code logic in reverse in situations involving potential Undefined Behavior. For example, given:

#include <stdio.h>
int main(void)
{
  int ch = getchar();
  int q;
  if (ch == 'Z')
    q=5;
  printf("You typed %c and the magic value is %d", ch, q);
  return 0;
}

a compiler would be entitled to assume that the program will never receive any input which would cause the printf to be reached without q having received a value; since the only input character which would cause q to receive a value would be 'Z', a compiler could thus legitimately replace the code with:

int main(void)
{
  getchar();
  printf("You typed Z and the magic value is 5");
}

If the user types Z, the behavior of the original program will be well-defined, and the behavior of the latter will match it. If the user types anything else, the original program will invoke Undefined Behavior and, as a consequence, the Standard will impose no requirements on what the compiler may do. A compiler will be entitled to do anything it likes, including producing the same result as would be produced by typing Z.

Upvotes: 0

5gon12eder
5gon12eder

Reputation: 25459

Let's have a look… (This really is the only way to tell.)

Fist, I've converted your snippet into something we can actually try to compile and run and saved it in a file named main.c.

#include <stdio.h>

static int
f()
{
  const int num[] = {1, 2, 3, 4, 5};
  int i;
  for (i = 0; i < sizeof(num) / sizeof(num[0]); i++)
    {
      if (num[i] > 6)
        {
          printf("Error in data\n");
          return 1;
        }
    }
  return 0;
}

int
main()
{
  return f();
}

Running gcc -S -O3 main.c produces the following assembly file (in main.s).

        .file   "main.c"
        .section        .text.unlikely,"ax",@progbits
.LCOLDB0:
        .section        .text.startup,"ax",@progbits
.LHOTB0:
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB22:
        .cfi_startproc
        xorl    %eax, %eax
        ret
        .cfi_endproc
.LFE22:
        .size   main, .-main
        .section        .text.unlikely
.LCOLDE0:
        .section        .text.startup
.LHOTE0:
        .ident  "GCC: (GNU) 5.1.0"
        .section        .note.GNU-stack,"",@progbits

Even if you don't know assembly, you'll notice that the string "Error in data\n" is not present in the file so, apparently, some kind of optimization must have taken place.

If we look closer at the machine instructions generated for the main function,

xorl    %eax, %eax
ret

We can see that all it does is XOR'ing the EAX register with itself (which always results in zero) and writing that value into EAX. Then it returns again. The EAX register is used to hold the return value. As we can see, the f function was completely optimized away.

Upvotes: 4

TheGreatContini
TheGreatContini

Reputation: 6639

Yes. The C compiler unrolls loops automatically with options -O3 and -Otime.

Upvotes: 1

prmottajr
prmottajr

Reputation: 1824

You didn't specify the compiler, but using gcc with -O3 and taking the size calculation outside the for maybe it could do a little adjustment.

Upvotes: 0

Related Questions