When code optimization happens?

Question

Yesterday, I had an interview. There they asked me when the code optimization happens? Say,

int abc;//Global variable
abc = 3;
if(abc == 3)
{
  printf("abc will be always 3");
}
else
{
  printf("This will never executed");
}

Now the question is when the optimization happens? A... At Run time B... At compile time. I answered at compile time... To me I thought, compiler checks for volatile keyword at compile time. If the variable is not declared as volatile then it optimizes the code. But, when the compiler comes to know that, this variable is never ever going to be other than 3? If it is at run-time, then when compiler comes to know that variable is never ever going to be other than 3? Because if the variable is going to be changed after this part of the code executed. Please clear my doubt

Answer 1

Not replying the question but giving an example of compile time optimization. gcc optimizes the code when asked to do so. The -O (Optimize) option enables optimization in different leves. It can be used as -O1, -O2 and -O3. The gcc man page describes precisely the meaning of each level.

The -S option translates C into assembly and saves on .s file.

test.c

#include <stdio.h>

int abc;//Global variable

void main()
{
    abc = 3;
    if(abc == 3)
        printf("abc will be always 3");
    else
        printf("This will never executed");
}

Whitout gcc optimization the two strings appear on the assembly code.

$ gcc -S test.c;cat test.s

    .file   "test.c"
    .comm   abc,4,4
    .section    .rodata
.LC0:
    .string "abc will be always 3"
.LC1:
    .string "This will never executed"
    .text
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $3, abc(%rip)
    movl    abc(%rip), %eax
    cmpl    $3, %eax
    jne .L2
    movl    $.LC0, %eax
    movq    %rax, %rdi
    movl    $0, %eax
    call    printf
    jmp .L1
.L2:
    movl    $.LC1, %eax
    movq    %rax, %rdi
    movl    $0, %eax
    call    printf
.L1:
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .ident  "GCC: (GNU) 4.6.1 20110908 (Red Hat 4.6.1-9)"
    .section    .note.GNU-stack,"",@progbits

Whit gcc level 1 optimization only one string is translated into assembly

$ gcc -O1 -S test.c;cat test.s

    .file   "test.c"
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string "abc will be always 3"
    .text
    .globl  main
    .type   main, @function
main:
.LFB11:
    .cfi_startproc
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movl    $3, abc(%rip)
    movl    $.LC0, %edi
    movl    $0, %eax
    call    printf
    addq    $8, %rsp
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE11:
    .size   main, .-main
    .comm   abc,4,4
    .ident  "GCC: (GNU) 4.6.1 20110908 (Red Hat 4.6.1-9)"
    .section    .note.GNU-stack,"",@progbits

Answer 2

Simplest answer: Code optimization occurs at the time of writing.

Simple answer: maybe, it's compiler dependent given the scope.

Hard answer: Given the global scope, the compiler should leave that alone with the assumption that it could be accessed elsewhere in the file. Multiple passes could optimize it out. If it is not considered static to the file by the compiler (think systems with flat memory models), then global is truly global and the assumption should be anything could change the value. This is why you avoid globals unless the intent really is global access.

Depending on the processor, the branch prediction argument would apply, but mostly it's compile time or not at all.

ps: I really dislike interview questions like this.

Answer 3

I wonder if they were looking for one answer or a few possible answers.

The compiler does not do anything at run time, usually. The compiler binary and its components are not required to be present (for the language C) at the run-time environment.

The type of optimization which would eliminate this dead branch would use certain techniques for writing optimizing compilers. See Muchnik's book on compilers. The techniques used might involve creating a directed graph of basic blocks, then using one of:

• def-use analysis
• static single assignment (ssa) analysis
  along with
• constant propagation (transform the if into if(3==3)
  and then
• constant expression elimination
  then
• dead code/dead branch removal

On the other hand, some compiler might not calculate enough to remove this during optimization.

In that case, if you ran the code on a chip with branch prediction, the chip would "learn" that the first branch is predicted, and cache (fetch) that branch favorably. But this is not a compiler mechanism, not usually called optimization.

Answer 4

Most code optimization can't happen at runtime, at least not how you mean. The code can't change during execution to reflect a new or different set of variables, that would just make an absolute mess.

What can be done at runtime is choosing the best path through the code, but that has to be done mostly manually in order to create the separate paths, early outs, branches and so on to allow optimization.

Code like this is, as written, allows compile-time optimization because the compiler can check for any possible alternate values of abc and, if none are found, optimize out the call. The scope of the search greatly influences whether that can happen, however, and the compiler settings influence that.

If the compiler is simply naively optimizing single object files and your second line is in another file from the print section, then it may not be able to guarantee abc doesn't change, and so won't be able to optimize this at all. Regardless of variable use, it depends on how aggressive your compiler settings are and whether they are allowed to discard dead branches, or will consider doing so. Optimizing for size may be more likely to remove the branch than for speed, but medium/high settings will likely do it either way (if possible).

Most modern compilers have a whole-program-optimization option, which delays much of the optimization until the linker stage. This allows it to search the whole program, potentially discover that abc is never changed or used anywhere else, and remove the variable and failing branch from the condition. Whole program optimization can be far more effective than separate optimization for each object, because it can allow more accurate searching.

In the case where it's not possible for the compiler to trim dead code, you can either hint it (recent constructs such as constexpr can help with that) or add optimizations yourself. It could be as simple as putting the most-likely path first and including a return before the else, saving the CPU from doing a jump. That sort of micro-optimization is unlikely to be necessary, certainly not in a simple example like this, where the if is plenty optimization by itself.

Answer 5

At compile-time :)

(Well, in principle it depends on the compiler, etc.)

Answer 6

I'm not overly familiar with how a compiler optimizes code, however I know that from the code you have there, the compiler can deduce that abc is never being changed. This means it could take out the if statement entirely and just call the first printf function.

Then at runtime, there isn't much optimization left, as the code is pretty straightforward. If abc were to change, then obviously the if couldn't be elided, however, then at runtime, there is things like branch prediction on the CPU that will try predict the code path being taken. Which could also be considered to be a form of optimization.

Note: I make no claims that this is what happens, but I could see that a compiler might optimize that way, in an aggressive optimization setting.

Answer 7

C code is usually compiled using static (aka ahead-of-time) compilation. The code is set in stone once it leaves the compiler; it cannot change at runtime.

This is in contrast to languages that use just-in-time compilation, such as Java. There, optimizations can happen pretty much at any time while then program is running.