Possible missed optimization when calling memcpy or memmove in a loop

[ldionne]

I noticed that the following code did not optimize to a single memcpy, unlike I would expect:

template <class T>
void relocate_1(T *first, T *last, T *dest) {
    for ( ; first != last; ++first, ++dest) {
        std::memcpy((void*)dest, first, sizeof(T));
    }
}

I would expect this to be equivalent to roughly:

template <class T>
void relocate_2(T *first, T *last, T *dest) {
    auto n = last - first;
    std::memcpy((void*)dest, first, n);
}

Is this a problem with e.g. the lack of knowledge that the [first, last) range is all valid? Note that both GCC and Clang fail to perform this optimization.

Godbolt: https://godbolt.org/z/zzdhcKPh4

[keinflue]

The behavior is not the same. Suppose for example dest == first + 1, then the first loop will copy *first to the whole range. std::memcpy over the whole range would be UB and std::memmove would not have the same result.

[nikic]

The memcpy's do get combined if you restrict-qualify dest.

[ldionne]

Ah ah! Thanks both, that makes sense.

I can see that this gets optimized if I __restrict the destination: https://godbolt.org/z/heb71docW

However, if I switch to memmove, I don't get the same optimization (but GCC does it): https://godbolt.org/z/K8srPchTr
Is that one a missed optimization?

[b1ackviking]

For memcpy overlapping ranges are UB, but memmove has to handle overlap:

The objects may overlap: copying takes place as if the characters were copied to a temporary character array and then the characters were copied from the array to dest.

I could not find if it is stated in the C++ standard. The above citation is from https://en.cppreference.com/w/cpp/string/byte/memmove

In C99 however, the difference is pretty clear:

void* memcpy( void *restrict dest, const void *restrict src, size_t count );
void* memmove( void* dest, const void* src, size_t count );

[keinflue]

@b1ackviking I don't think that was unknown or up for discussion for anyone in this thread? Or I do not see how this is relevant to the remaining question?

[b1ackviking]

@keinflue I thought my comment could be helpful as a possible explanation to why the compiler does not optimize memmove even in the second case, that's not obvious to me. Sorry, if it was inappropriate, didn't want to break in just to say something.

[ldionne]

I think this is potentially relevant, in fact. The code that doesn't optimizes (and IMO should) is:

template <class T>
void relocate_1(T * __restrict first, T *__restrict last, T * __restrict dest) {
    for ( ; first != last; ++first, ++dest) {
        std::memmove((void*)dest, first, sizeof(T));
    }
}

Here, the pointers are marked as __restrict at the top level but we're still calling memmove, and perhaps Clang is not seeing that it can assume no overlap from within memmove. Kind of like the __restrict assumption didn't survive through the inlining of memmove, but that's just my naive interpretation of what's happening. GCC, however, seems to do the right thing.

[nikic]

This is a phase ordering problem. LoopIdiomRecognize runs before MemCpyOpt.

[ldionne]

I am curious to know what you folks do in these cases. Surely you can't just reorder the two phases since that could have wide ranging effects on other optimizations?