Missed optimization of std::vector access

[hiraditya]

I originally reported the bug in GCC (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109443) but it seems Clang also has the problem. Both accesses are similar but different code is generated. the function h has better codegen than g for some reason.

void f(int);

void g(std::vector<int> v)
{
    for (std::vector<int>::size_type i = 0; i < v.size(); i++)
        f( v[ i ] );
}

void h(std::vector<int> v)
{
    for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
        f( *i );
}

$ clang++ -std=c++2a -O3 -stdlib=libc++

g(std::vector<int, std::allocator<int> >): # @g(std::vector<int, std::allocator<int> >)
  push r14
  push rbx
  push rax
  mov rax, qword ptr [rdi]
  cmp qword ptr [rdi + 8], rax
  je .LBB0_3
  mov rbx, rdi
  xor r14d, r14d
.LBB0_2: # =>This Inner Loop Header: Depth=1
  mov edi, dword ptr [rax + 4*r14]
  call f(int)@PLT
  inc r14
  mov rax, qword ptr [rbx]
  mov rcx, qword ptr [rbx + 8]
  sub rcx, rax
  sar rcx, 2
  cmp r14, rcx
  jb .LBB0_2
.LBB0_3:
  add rsp, 8
  pop rbx
  pop r14
  ret


h(std::vector<int, std::allocator<int> >): # @h(std::vector<int, std::allocator<int> >)
  push r14
  push rbx
  push rax
  mov r14, qword ptr [rdi]
  cmp r14, qword ptr [rdi + 8]
  je .LBB1_3
  mov rbx, rdi
.LBB1_2: # =>This Inner Loop Header: Depth=1
  mov edi, dword ptr [r14]
  call f(int)@PLT
  add r14, 4
  cmp r14, qword ptr [rbx + 8]
  jne .LBB1_2
.LBB1_3:
  add rsp, 8
  pop rbx
  pop r14
  ret

There are two issues:

• v.size() is not loop invariant
  • This can be fixed by programmer by hoisting v.size() out of the loop body. However, compiler should be able to figure it out.
• operator[] loads v in each iteration

[fhahn]

The issue is that the vector is passed through memory and there's no info that the loads of the start pointer and the size of the vector don't get modified by the call.

I added an option to mark objects passed by value as no alias (a874d63) a while ago which should help with that in general. It links a thread discussing whether to make this default to true or not (so far it's not on by default). The std::vector case is not handled at the moment (no no alias gets added), so I'd need to check where this gets missed.

[ldionne]

Related discussion about noalias: https://lists.llvm.org/pipermail/cfe-dev/2020-July/066353.html

[hiraditya]

Even when the vector is created inside the function, as long as v escapes, compiler can't prove loop invariance of v after that. e.g.,

Base case, when vector is created inside function and nothing changes it after that. clang doesn't load v in every iteration.

#include<vector>

void f(int);

void use_idx_const_size_init() {
    std::vector<int> v(10000);
    auto s = v.size();
    for (std::vector<int>::size_type i = 0; i < s; i++)
        f(v[i]);
}

$ clang++ -O3 -stdlib=libc++

.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        mov     edi, dword ptr [rbx + 4*r14]
        call    f(int)@PLT
        inc     r14
        cmp     r14, 10000
        jne     .LBB0_1

$ clang++ -O3 -stdlib=libc++

When v.resize() is called, compiler fails to prove loop-invariance of v.

#include<vector>

void f(int);

void use_idx_const_size_resize() {
    std::vector<int> v;
    v.resize(100000);
    auto s = v.size();
    for (std::vector<int>::size_type i = 0; i < s; i++)
        f(v[i]);
}

Again the code is sub-optimal.

.LBB1_3:                                # =>This Inner Loop Header: Depth=1
        mov     rax, qword ptr [rsp]
        mov     edi, dword ptr [rax + 4*r14]
        call    f(int)@PLT
        inc     r14
        cmp     rbx, r14
        jne     .LBB1_3
        mov     rdi, qword ptr [rsp]

[hiraditya]

And the best code is generated by range-for loop which is same if we hoist the end() iter in the iterator version.

void range(const vector<int> &input) {
    for (int i : input) {
        f(i);
    }
}
/* same as


void iter(const vector<int> &input) {
    for (auto i = input.begin(), e = input.end(); i != e; ++i) {
        f(*i);
    }
}
*/

range(std::vector<int, std::allocator<int> > const&):
        push    rbp
        push    rbx
        sub     rsp, 8
        mov     rbx, QWORD PTR [rdi]
        mov     rbp, QWORD PTR [rdi+8]
        cmp     rbp, rbx
        je      .L1
.L3:
        mov     edi, DWORD PTR [rbx]
        add     rbx, 4
        call    f(int)
        cmp     rbp, rbx
        jne     .L3
.L1:
        add     rsp, 8
        pop     rbx
        pop     rbp
        ret

[hiraditya]

@EugeneZelenko please don't remove libc++ tag. it makes it harder for folks who are looking at libc++ performance issues.

[philnik777]

@EugeneZelenko please don't remove libc++ tag. it makes it harder for folks who are looking at libc++ performance issues.

This isn't anything libc++ can fix though, so this shouldn't be marked libc++. The tag is for things that could be fixed in libc++, not anything that has something to do with libc++ in some way.