LLVM does not eliminate or hoist redundant bounds checks for std::vector and std::string

[ldionne]

Given the following code:

#include <vector>
#include <span>
#include <string>

template <class T>
void use(T const&);

template <class Container>
void f(Container container) {
  for (int i = 0; i != container.size(); ++i) {
    use(container[i]);
  }
}

template void f(std::string);
template void f(std::vector<int>);
template void f(std::span<int>);

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

When we compile with hardening enabled, there is a bounds check inside operator[]. That check is basically equivalent to index < size(). However, it doesn't get elided even though the loop condition should guarantee that the condition always holds. It seems to be elided when iterating over a span, but not a string or a vector, which makes me think the optimizer could be improved.

[ldionne]

CC @fhahn I'm curious to know what you think about this. Do you think there's room to improve or is this difficult to optimize for a reason I missed?

[fhahn]

at first glance, at least for the vector case is that we have to re-load the base pointer and count on each iteration, as use() might modify them

[efriedma-quic]

Right, we'd need to mark the pointer noalias. But we can't do that for arbitrary classes because the copy constructor can stash a pointer to the class anywhere. So we'd need some marking on std::vector in particular to indicate the transform is safe. Something along the lines of trivial_abi.

[ldionne]

Hmm, that's interesting. So the compiler must assume that the address of the container could be stored in a global and then accessed by use(...), so it has to reload it. That makes sense from a correctness perspective, it's just really unfortunate to pessimize the common case (by far).

Do you understand why std::span doesn't exhibit the same issue?

[ldionne]

Actually, I believe something different is happening. Indeed, even if use(...) were to modify the container, at the end of the day we have a check for i != container.size() immediately before the assertion i < size() inside operator[]. Nothing happens between those two checks, so in theory I think the compiler could see that the second one is redundant.

And lo and behold, if I change the loop condition to i < container.size() instead of i != container.size(), the check does get optimized out! So I think there's something happening that causes the optimizer not to remove the duplicate constraint because it's written as i != size() instead of i < size(): https://godbolt.org/z/b779PeqEq

[efriedma-quic]

So I think there's something happening that causes the optimizer not to remove the duplicate constraint because it's written as i != size() instead of i < size()

Isn't that the same thing? If the size of the container can change every iteration, i != container.size() doesn't imply i < container.size().

Do you understand why std::span doesn't exhibit the same issue?

std::span is POD, so it gets passed by copy.

[ldionne]

Ah yes, of course that makes sense.

For the compiler to know (without any annotations) that the address of container wasn't stashed in a global in the constructor that initialized the function argument, it would need to inspect all the constructors that could have been called and confirm that none of them is sneaky. Is that right? And clearly that is not scalable or even possible.

Would you want the attribute to apply to std::vector (e.g. __attribute__((__value_type__)) meaning that it's a value type with value semantics and when you get a copy, it's truly disjoint from other copies)?

Or would you want an attribute on the members of the vector that says "I guarantee that those members have not escaped somewhere sneaky via a constructor or anything else"?

[efriedma-quic]

it would need to inspect all the constructors that could have been called and confirm that none of them is sneaky

Yes.

Would you want the attribute to apply to std::vector (e.g. __attribute__((__value_type__)) meaning that it's a value type with value semantics and when you get a copy, it's truly disjoint from other copies)?

Something like that. clang::trivial_abi on std::vector would allow the optimization here, I think, but that's an ABI break. You could specify an attribute with the same semantics, but doesn't actually change the way the object is passed.

[fhahn]

I had a look at what would be needed to get such an attribute working, and stumbled across -fpass-by-value-is-noalias which had a similar goal. Put up a sketch of the attribute that just adds no-alias, still needs docs for the new attribute: #95004

[hiraditya]

yeah surprising that it hasn't been optimized yet. I found this issue in vector last year #63328 and reported to gcc bugzilla as well.