Why are gcc and clang not hoisting strlen out of this loop?

Question

Consider the following code:

#include <string.h>

void bar(char c);

void foo(const char* restrict ss) {
    for (int i = 0; i < strlen(ss); ++i) {
        bar(*ss);
    }
}    

I would expect the strlen(ss) to be hoisted out of the loop in these essentially ideal conditions; and yet - it isn't, neither by clang 5.0 nor by gcc 7.3 with maximum optimization (-O3).

Why is this the case?

Note: Inspired by (my answer to) this question.

Answer 1

The other answers claim that the strlen call cannot be hoisted because the string's contents might change between calls. Those answers do not properly account for the semantics of restrict; even if bar had access to the string through a global variable or some other mechanism, the semantics of restrict pointers to const types should^{(see caveat)} prohibit bar from modifying the string.

From C11, N1570 draft, 6.7.3.1:

1 Let D be a declaration of an ordinary identifier that provides a means of designating an object P as a restrict-qualified pointer to type T.

2 If D appears inside a block and does not have storage class extern, let B denote the block. If D appears in the list of parameter declarations of a function definition, let B denote the associated block. Otherwise, let B denote the block of main (or the block of whatever function is called at program startup in a freestanding environment).

3 In what follows, a pointer expression E is said to be based on object P if (at some sequence point in the execution of B prior to the evaluation of E) modifying P to point to a copy of the array object into which it formerly pointed would change the value of E.¹³⁷⁾ Note that ''based'' is defined only for expressions with pointer types.

4 During each execution of B, let L be any lvalue that has &L based on P. If L is used to access the value of the object X that it designates, and X is also modified (by any means), then the following requirements apply: T shall not be const-qualified. Every other lvalue used to access the value of X shall also have its address based on P. Every access that modifies X shall be considered also to modify P, for the purposes of this subclause. If P is assigned the value of a pointer expression E that is based on another restricted pointer object P2, associated with block B2, then either the execution of B2 shall begin before the execution of B, or the execution of B2 shall end prior to the assignment. If these requirements are not met, then the behavior is undefined.

5 Here an execution of B means that portion of the execution of the program that would correspond to the lifetime of an object with scalar type and automatic storage duration associated with B.

Here, the declaration D is const char* __restrict__ ss, and the associated block B is the body of foo. All lvalues through which strlen accesses the string have &L based on ss^{(see caveat)}, and those accesses occur during the execution of B (since, by the definition in section 5, the execution of strlen is part of the execution of B). ss points to a const-qualified type, so by section 4, the compiler is allowed to assume string elements accessed by strlen are not modified during the execution of foo; modifying them would be undefined behavior.

^(caveat)The above analysis assumes that strlen accesses the string through "ordinary" pointer dereferencing or indexing. If strlen uses techniques like SSE intrinsics or inline assembly, it is not clear to me whether such accesses technically count as using an lvalue to access the value of the object that it designates. If they do not count as such, the protections of restrict may not apply, and the compiler may not be able to perform the hoisting.

Maybe the above caveat voids the protections of restrict. Maybe the compiler doesn't know enough about the definition of strlen to analyze its interaction with restrict (I'm surprised it wasn't inlined). Maybe the compiler is free to perform the hoisting and just didn't realize it; perhaps some relevant optimization is not implemented, or it failed to propagate the necessary information between the right compiler components. Determining the exact cause would require much more familiarity with the GCC and Clang internals than I possess.

Further-simplified tests that eliminate strlen and the loop show that Clang definitely has some support for restrict-pointer-to-const optimizations, but I wasn't able to observe any such support from GCC.

Answer 2

Since strlen is being passed a pointer and it is possible that the contents of the memory it is pointing to will change between invocations to strlen so optimizing the call away could introduce bugs. If you can guarantee to the gcc that the function will always return the same value it will optimize it away. From the function attribute documentation:

const

Many functions do not examine any values except their arguments, and have no effects except to return a value. Calls to such functions lend themselves to optimization such as common subexpression elimination. The const attribute imposes greater restrictions on a function’s definition than the similar pure attribute below because it prohibits the function from reading global variables. Consequently, the presence of the attribute on a function declarations allows GCC to emit more efficient code for some calls to the function. Decorating the same function with both the const and the pure attribute is diagnosed.

So taking out the external dependency on strlen, look at the difference in the following two compilations:

int baz (const char* s) __attribute__ ((pure));

void foo(const char* __restrict__ ss)
{
    for (int i = 0; i < baz(ss); ++i)
        bar(*ss);
}

Yields:

foo:
        push    rbp
        push    rbx
        mov     rbp, rdi
        xor     ebx, ebx
        sub     rsp, 8
        jmp     .L2
.L3:
        movsx   edi, BYTE PTR [rbp+0]
        add     ebx, 1
        call    bar
.L2:
        mov     rdi, rbp
        call    baz
        cmp     eax, ebx
        jg      .L3
        add     rsp, 8
        pop     rbx
        pop     rbp
        ret

But if we change the pure attribute on baz to const you can see the call hoisted out of the loop:

foo:
        push    r12
        push    rbp
        mov     r12, rdi
        push    rbx
        xor     ebx, ebx
        call    baz
        mov     ebp, eax
        jmp     .L2
.L3:
        movsx   edi, BYTE PTR [r12]
        add     ebx, 1
        call    bar
.L2:
        cmp     ebp, ebx
        jg      .L3
        pop     rbx
        pop     rbp
        pop     r12
        ret

So maybe hunt through your header files and see how strlen is declared.

Answer 3

ss might be some global variable because you could call foo with some global array like char str[100]; as its argument (e.g. by having foo(str); in your main)...

and bar could modify that global variable (then strlen(ss) could change at every loop).

BTW restrict has perhaps not the meaning you believe. Read carefully section §6.7.3 of the C11 standard and §6.7.3.1. IMHO restrict is in practice mostly useful on two formal arguments of the same function to express the fact that they are not "aliases" or "overlapping" pointers (if you guess what I really mean), and perhaps optimization efforts on restrict have probably been focused on such cases.

Perhaps (but unlikely), on your particular program, a compiler might optimize as you want if you invoke it as gcc -flto -fwhole-program -O3 (on every translation unit, and at program link time). I won't bet on that (but I leave you to check).

Why is this case?

As to why current GCC (or Clang) does not optimize like you want it to, it is because nobody has written such an optimization pass and have it enabled at -O3.

^{Compilers are not required to do optimizations, just allowed to do some of them (at the choice of their implementors).}

Since it is free software, feel free to propose a patch by contributing to GCC (or to Clang). You might need a whole year of work, and you are not sure that your optimization would be accepted (because in practice nobody codes like you show, or because your optimization would be too specific, so unlikely to be triggered, but still slowing down the compiler). But you are welcome to try.

Even if §6.7.3.1 allows your optimization (as the answer by user2357112 demonstrates), it might practically not worth the effort to implement it.

^{(my intuition is that implementing such an optimization is hard, and won't profit much to existing programs in practice)}

BTW, you can definitely experiment such an optimization by coding some GCC plugin doing it (since the plugin framework was designed for such experimentations). You might discover that coding such an optimization is a lot of work and that practically speaking it does not improve the performance of most existing programs (e.g. in a Linux distribution), because few people code that way.

Both GCC and Clang are free software projects, and contributors to them are (from the point of view of e.g. the FSF) volunteers. So feel free to improve GCC (or Clang) like you want it to optimize. By past experience, contributing even a small piece of code to GCC takes a lot of time. And GCC is a huge program (about ten millions lines of code), so understanding its internals is not easy.