Actually I think this is a glibc/BSD difference. You're right that any pure function would be hoisted in the same way, but in fact strlen() is not marked pure in my OS X header (which looks to be the same as in FreeBSD). Compiling with -fno-builtin defeats the optimization, which shows that it is due to strlen being built-in on those platforms.

On my Linux machine, on the other hand, strlen() is marked pure, and there the optimization persists even with -fno-builtin.

There must be more to it than that. For example, if something in the loop body writes to s, then the result of "strlen" could change and the optimisation will be wrong.

So, it must know a bit about what strlen() does, mustn't it -- otherwise it wouldn't know that it has to ensure that \0 isn't written to s inside the loop body.

The compiler can see the loop, so it can optimize it. Hosting constant expressions out of loops is a long-standing optimization in all compilers. Here, the expression "s" is unchanged* inside the loop, so the compiler can hoist it. If the expression were "s[0]" it could do the same. But can it do it for strlen(s)? It can, if it knows that strlen() has no side effects. So gcc extends C's syntax to add a "pure" attribute to tell the compiler exactly that.

* Pedants will point out all subtleties about C pointer aliasing rules apply here. But for the purpose of explanation, assume that nothing assigning throuh s means "s is constant".

GCC can statically prove that `s` isn't changed at all in the loop body, just accessed. Thus the analysis goes: `strlen()` is pure, and its argument never changes, so its result never changes, so I can hoist it.

No, there is more to it than that. It has to perform an aliasing analysis to prove that nothing that s points to changes. Consider this code:

    unsigned sum(const unsigned char *s, char *t) {
        unsigned result = 0;
        for (size_t i=0; i < strlen(s); i++) {
            result += s[i];
            *t = 'x';
        }
        return result;
    }

gcc can't hoist strlen() in this case, because *t = 'x' could potentially overwrite the null termination of s.

Note that C99 has added "restrict" for such cases, which essentially promises that the restricted pointer (and any pointers derived from it) is the only pointer to that chunk of memory.

Can GCC handle more complicated loops? For example what if I go several functions deep in in my loop with s? What if I call a function in a shared object? Does gcc do this analysis for all cases where a function is marked pure or is strlen a specific case?

The compiler can't see inside functions in the general case (because they're opaque binary blobs in a library that hasn't been linked yet), so no. It's limited to optimizing stuff it can "see", which broadly means the current function and anything inlinable into it.

But yes, if all your functions are marked inline and visible to the compiler, there's no theoretical limit to GCC's ability to hoist constants out of the innermost parts of the loop. In practice, there are surely some performance limits to how much inlining will be expanded.

Thanks. If this helps anyone else, the realisation I was missing was that the compiler must treat any write based off a pointer as a write to the thing pointed at. Which is conservative if there is no aliasing.