Unaligned memory access and vector algorithms

[AlexGuteniev]

I've attempted to avoid misaligned access in recent PRs;

• vector_algorithms.cpp: avoid cast to integral in __std_bitset_from_string_N #5759
• vector_algorithms.cpp: avoid unaligned access #5760

This was mostly motivated by #5746 , UBSan reminded that misaligned access is considered UB.

However, x64 and x86 behave correctly for misaligned access for non-atomic operations. There is misalignment performance penalty which varies from none or almost none to something noticeable, but it is not very big either. So in reality everything works for misaligned access.

Apart from the PRs mentioned above, we have some examples, when we rely on unaligned access:

• "Swizzling" algorithms reverse, reverse_copy, swap_ranges, rotate. They don't impose much requirements on the type, so struct Point { short x; short y; } is suitable type, and may be not aligned to 4 bytes. Apart from class types, member function pointers of some layout can also go here.
• Newly enabled vectorization in scope of Use Clang's __is_trivially_equality_comparable intrinsic to optimize more cases in vector algorithms #5479: "searching" algorithms, and mismatch algorithm, and future "finding" algorithms, They would also work on structures with alignment less than size, and member function pointers of certain kind.
• x86 famous 4-byte alignment of 8-byte type, under specific conditions.
• The user may not care about alignment, and expect unaligned arrays to work.

---

I see the following ways to deal with that:

• Do nothing. As it currently works
• Prohibit potentially misaligned types from vectorization at compile time
• Check runtime alignment of potentially misaligned types
• Modify vector algorithms, so that they would work exclusively via memcpy or intrinsics, so that they are safe for any alignment

There may be macro-configurable approach or hybrid approach too.

---

Next to aligning problem, there's also aliasing problem, so it may still be UB to work with aligned alignas(4) struct Point { short x; short y; } as with int. But MSVC does not enforce strict aliasing rule, and clang-cl should not do this too. So we should not need to address this problem.

[StephanTLavavej]

Since vector_algorithms.cpp is currently x64/x86-specific, and is not subject to UBSan (being separately compiled), I am not inclined to add compile-time or runtime-checks to detect misaligned inputs. (Such logic is another thing that can go wrong, and makes it more difficult to test all codepaths.) I think that we should consider using misalignment-respecting techniques when doing so is locally easy, since they're about as complicated as quick-and-dirty reinterpret_casting.

[AlexGuteniev]

I think locally easy cases are limited to the two currently open PRs.

Other cases are scalar tails/fallbacks, and they are not easy.

(Vector intrinsics are defined to accept misaligned types and correctly alias with anything)