| 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;
}
In this example, it will eliminate the unconditional fp(a) call at the end by reusing the value of c in the first if block, and storing the result of calling cos(a) in the else block.
IE: 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;
}
(attribute pure is ignored on function pointers, so you can't just s/const/pure/ and expect it to work)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;
}
The call to fp(a) in the loop will be hoisted above the loop through redundancy elimination, the call d = fp(a) will be eliminated in favor of that hoisted value.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.