Will It Optimize? See how well you can anticipate gcc's optimizer (2010)

Err, "GCC does this optimization, because strlen is a "built-in function:"

No. I wrote the optimization pass that does this (GVN PRE with SCC based value numbering).

It does it to any pure/const function. Const ones no matter what, and pure ones if it can prove the global memory state does not otherwise change between calls in a way that impacts that pure call (IE there are times it can prove the calls that happen in between don't matter, and will still do the elimination). You don't usually have to mark the functions const/pure if they are visible to GCC, it does interprocedural analysis to prove they are pure/const and mark them for you.

It will even do it through function pointers if the value numbering or alias analysis can prove what they point to, or that they don't change in between the calls.

  double cos (double) __attribute__ ((const));
  double sin (double) __attribute__ ((const));
  double f(double a)
  {
    double b;
    double c,d;
    double (*fp) (double) __attribute__ ((const));
    /* Partially redundant call */
    if (a < 2.0)
      {
        fp = sin;
        c = fp (a);
      }
    else
      {
        c = 1.0;
        fp = cos;
      }
    d = fp (a);
    return d + c;
  }

  double cos (double) __attribute__ ((const));
  double sin (double) __attribute__ ((const));
  double f(double a)
  {
    double b;
    double c,d;
    double (*fp) (double) __attribute__ ((const));
    /* Partially redundant call */
    if (a < 2.0)
      {
        fp = sin;
        c = fp (a);
        temp = c
      }
    else
      {
        c = 1.0;
        fp = cos;
        temp = cos(a)
      }
    d = temp;
    return d + c;
  }

Loop code hoisting is actually a special case of this partial redundancy elimination.

  double sin (double) __attribute__ ((const));
  double f (double a)
  {
    int i;
    double c, d;
    double (*fp) (double) __attribute__ ((const));
    fp = sin;
    for (i = 0; i < 50; i++)
      {
        c = fp (a);
      }
    d = fp (a);
    return d + c;
  }

Basically, the optimization is a lot more powerful than he describes.

This reminds me of something my assembly instructor said in class once (paraphrased):

"Once, I was interested in finding out how a C compiler would handle the div instruction. So, I opened up my editor, and wrote this C program:

    void main () {
        printf("%f", 14.0 / 3.0);
    }

[Various guesses, mostly "one."]

The correct answer is "zero." The compiler figured it out at compile time, and put a constant in instead. So, I decided to put it in a function:

    float divide (float a, float b) {
        return a / b;
    }
    
    void main () {
        printf("%f", divide(a, b));
    }

[Various guesses.]

The f--king compiler optimized it out again!"

I did some similar experiments myself a long time ago. Something mildly surprising for me at that time was that this got optimized to a single roll instruction:

    uint32_t roll(uint32_t const x) {
        return (x << 15) | (x >> 17);
    }

Question 4 points at a huge surprise. With a scientific computing project, I got (if I recall correctly), correct and expected output at no optimization and -O1, and patently incorrect output at -O2 and -O3.

Cost: one sleepless night in college."What do you mean, optimization doesn't just make it faster?!?"

I am surprised at number 3, I would have thought that it would be optimised to x << 1, rather than the addition?

Edit: No. 5 explains why.

What an interesting read. Thanks OP. I got stumbled on the floating point question. I remember a few weeks ago in class our instructor taught us about floating point precision loss and I thought the compiler might take care into that and not optimize it, but I guess I was wrong.

Would you explain a bit more on that? I'm really interested! Thanks!

Previous submission: https://news.ycombinator.com/item?id=1540567 (335 points, 989 days ago, 61 comments)