Will It Optimize? See how well you can anticipate gcc's optimizer (2010)(ridiculousfish.com) |
Will It Optimize? See how well you can anticipate gcc's optimizer (2010)(ridiculousfish.com) |
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.
However, what I wrote was not wrong. strlen is not marked as pure or const on OS X, and yet it is hoisted. glibc does happen to mark strlen as pure in string.h, but the optimization occurs even if you do not include that header - even if there is no declaration for strlen in scope at all!
So this optimization really does proceed because strlen is a builtin function, and does not depend on strlen being marked as pure or const.
Under the hood, it may be that strlen is rewritten as __builtin_strlen, which is marked as pure and therefore hoisted like any pure expression. Or it may be due to some of the other magic, like the pass that optimizes strlen("foo") to 3. I don't know which optimization pass is responsible, and it didn't seem important, so I kept my mouth shut on that aspect.
No. It's exactly the other way around. We could not give a crap whether it is a built in function, only whether it is pure or const. We do not special case built-in functions anywhere near this optimization.
~/sources/gcc/gcc (git)-[master]- :) $ grep BUILT_IN tree-ssa-sccvn.c
&& DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
&& gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
&& (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY)
|| gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY)
|| gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE))
~/sources/gcc/gcc (git)-[master]- :) $ grep BUILT_IN tree-ssa-pre.c
~/sources/gcc/gcc (git)-[master]- :( $
The reason the optimization proceeds is because strlen gets marked as pure by the compiler if there is no non-pure definition that overrides it.
Basically, the compiler defines a function named "strlen" that is pure and nothrow behind your back, but you can override it by providing your own definition. This is unrelated to whether it is a builtin (because the builtin version is __builtin_strlen)
"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!"
[1] Normally you have to declare a function as 'static' to tell the compiler that the function isn't being exported form the compilation unit, since the compiler isn't supposed to be able to tell the difference between function declarations in the .c file itself and function declarations that were included from .h files. But in this case the function is just defined and never declared, so I presume that's the same as a static declaration.
uint32_t roll(uint32_t const x) {
return (x << 15) | (x >> 17);
}
Cost: one sleepless night in college."What do you mean, optimization doesn't just make it faster?!?"
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=323 (a centi-bug of back and forth between "it's broken!" and "no it's not, and we're not going to change the compiler.")
http://gcc.gnu.org/ml/gcc/2003-08/msg01183.html (a really informative thread about the issue)
"This need to avoid imprecise intermediate results often prevents compilers from exploiting mathematical properties like associativity when optimizing FP arithmetic."
from the explanation under Q4.
Edit: No. 5 explains why.
random aside: gcc usually uses the LEA instruction for this sort of thing, which lets you compute any combination of {1,2,4,8} * x + y + n in one cycle where x and y are registers and n is a constant number. So even with the LEA instruction you can use either lea eax, [eax*2] or lea eax, [eax+eax] to compute this. And so on. I think add eax, eax is most likely what it does though.
Would you explain a bit more on that? I'm really interested! Thanks!
I don't know that this is necessarily the reason here, but it's one possible explanation.
However, the compiler is perfectly free to both compile it as an external function and inline it wherever it wants. Yes, setting breakpoints on such a function would be 'funny', but that's nothing of real concern to the compiler.
You can see this by inspecting the disassembly yourself, you'll see that printf never actually calls divide, and yet the divide function is still defined within the executable output.
That's what I meant when I wrote that "the compiler recognizes strlen, and optimizes it specially." It was not my intent to say that only builtins or all builtins may be hoisted in this way, although now I see how someone could interpret that. That was bad wording on my part.
The point I was trying to communicate is that gcc can do special optimizations on functions that it recognizes as builtins - for example, replacing printf() with fputs(). One illustration is how strlen is treated as pure, even if it is not marked as pure. As someone with far more gcc expertise than me, would you agree with that point?
"Basically, the compiler defines a function named "strlen" that is pure and nothrow behind your back, but you can override it by providing your own definition. This is unrelated to whether it is a builtin"
Well, the optimization is defeated by -fno-builtin, so I assumed that the underlying mechanism is that a call to strlen is replaced by a call to the builtin. Was this wrong?
Due to some wonderful oddness around freestanding environments, if you use -fno-builtin, it will define neither.
Would it still work with -fno-strict-aliasing? I guess it should, for functions that only work on stack and get parameters from stack, right?