The compiler could generate both vectorized and non-vectorized variants and decide dynamically which one to use based on a simple aliasing check. That's an approach that would be more usual for JIT compilers than AOT compilers, but habits can change.

Yeah I came here to say this: I don't see a good way to prove this at compile time, but you could always do a dynamic check.

In general, compilers don't generate runtime checks like this. In the case of aliasing problems, however, they actually do make such checks, but usually only in the case of possibly overlapping arrays. An example:

https://godbolt.org/z/9vZfl_

Both gcc and clang make a check to see if the x and y arrays overlap, and if they do they fall back to a scalar loop (instructions ending in ss: scalar single-precision) - but if there is no overlap they proceed with the vectorized approach (instructions ending in ps: packed single-precision).

So I guess these cases were important enough that they got specific handling in the compiler, but I haven't seen it for possible aliasing with a scalar, even though the same type of check could be used. Actually it's a bit trickier, because the compiler wants to know the array size to make this calculation, but the array size itself, which comes from size() is the thing subject to aliasing! So it takes a more complex analysis to show that it's safe.

If I'm reading the generated asm correctly (which I might well be not), the following function is vectorized conditional to a runtime alias check (the non vectorized case is completely removed if the pragma is uncommented). So even scalars seem to be handled:

  void inc(float* x, float*  c, size_t n)
  {
    //#pragma GCC ivdep
    for (int i = 0; i < n; ++i)
      x[i]+= *c;
  }

the issue really seems to be that the compiler just gives up very early if the iteration count is not a loop invariant.

Yeah, I read it the same as you: so alias checks can definitely happen even for single values.

It seems like it's not just the loop counts that's the problem: in the blog post even when size is a local, it fails to check to see if the vector array pointer itself can alias.

I.e., analogous to incB here:

https://godbolt.org/z/ptQZcs

incA is like your example: the possibly aliasing is between the array and the value added, and an alias check occurs. incB is like the v[i] example: possible aliasing is between the array and the pointer to the same array, no check and conservative code is generated.

Interesting...

That's true. In fact GCC should be able to do that in principle. I guess it only does it if it believes that the vectorization is significantly profitable.

edit: it is possible it only does it on PGO builds.

I linked an example [1] in a parallel reply that shows gcc (and clang) doing it at -O3 without PGO, for the case of possibly overlapping arrays.

---

[1] https://godbolt.org/z/9vZfl_

> how, without whole program compilation?

Dataflow analysis. If size() depends on values that are in one malloc'ed block, and the vector elements are in a different malloc'ed block, then you know there is no aliasing. (For example).

std::vector is entirely defined in a header file (it has to be, it's a template), so whole program optimization (which is what I presume you mean?) doesn't enter into it. The entire definition of vector is within the same translation unit.

I don't know enough about compiler optimization algorithms to say how trivial it would be to figure out these two things don't alias, but when you have a type with the magic property "this guy is allowed to alias ANYTHING", then I imagine it gets pretty tricky.

Definition of the type is not enough, the compiler need to track the origin of all pointer values, which means it needs to 'see', recursively, all callers of the function it is optimizing up to the point where the parameter objects were originally constructed, plus any function where a pointer to the object might potentially escape to (which might be potentially any function, if it escapes to the heap).

And that might still not be enough: passing the vector by value still doesn't trigger the optimization in GCC and clang (but it does for a bare bone vector implementation, probably std vector itself ends up leaking its own internals).

> when you have a type with the magic property "this guy is allowed to alias ANYTHING", then I imagine it gets pretty tricky.

well, yes, that's the whole point of the article :)

> the compiler need to track the origin of all pointer values

If the size and the buffer pointer are both private, wouldn't it be enough to analyze all the member functions to ensure that there is no aliasing between them? Users might try to muck around in the internal representation using memcpy or whatever, but that would presumably be undefined behavior.

User specialized member functions can be used to circumvent the private barrier (IIRC formally you are not allowed to do this for std types). Also elsethread someone discussed the extremely evil example of placement new'ing a vector on another vector's buffer then swapping them.

Surely both of those things are UB?

I mean, it's not like the optimization is impossible (by rejiggering the code a bit, it kicks in), it's just that using uint8_t's makes the optimzation far more brittle, because the compiler has to walk on eggshells around uint8_t's. Right?

the placement new is not UB, at least at a language level. Modifying the vector would break the vector invariant, leading to UB. The specialization is UB only because vector is an std type, otherwise is perfectly legal.

In both cases, yes, if you hardcode the specific std::vector invariants in the compiler, it might be able to do better, but a user provided vector class wouldn't benefit from the same optimisations.

Note that compilers are not beyond hardcoding invariants of standard library facilities: malloc, C string functions, etc are treated as primitives by the compiler (for example, the result of malloc cannot alias with any other pointer), but for a complex class like vector, it does not seem appropriate and it is better to use compiler hooks in the implementation that are also available to the user (restrict, builtin functions, alias annotations, etc).