ADT: Remove redundant `alignas` from IntervalMap, NFC

[dexonsmith]

Summary

Alignment is covered by AlignedArrayCharUnion.

[dexonsmith]

@aleksandr.urakov , looking at history, this is effectively a revert of 379daa29744cd96b0a87ed0d4a010fa4bc47ce73 / r344027 / https://reviews.llvm.org/D52613. I don't totally understand why you needed LLVM_ALIGNAS here, since AlignedCharArrayUnion is supposed to handle that. Can you clarify?

And if it's needed here, why not on all other instances of AlignedCharArrayUnion?

[dexonsmith]

In D92509#2429385, @dexonsmith wrote:

@aleksandr.urakov , looking at history, this is effectively a revert of 379daa29744cd96b0a87ed0d4a010fa4bc47ce73 / r344027 / https://reviews.llvm.org/D52613. I don't totally understand why you needed LLVM_ALIGNAS here, since AlignedCharArrayUnion is supposed to handle that. Can you clarify?

And if it's needed here, why not on all other instances of AlignedCharArrayUnion?

@rnk, you reviewed the original patch, maybe you have more background.

The original patch points at https://docs.microsoft.com/en-us/cpp/build/conflicts-with-the-x86-compiler which now gives 404. We dropped some older versions of MSCV when we moved to C++14; I wonder if whatever the need was, it's gone.

[dexonsmith]

This is probably the same root problem as https://reviews.llvm.org/D92500, which transitively points at https://reviews.llvm.org/D64417#1576675. I'll block this on my other patch and mark this as changes planned to get it off queues.

[rnk]

If you look at the copy of AlignedCharArrayUnion at the time, you can see that it did not use alignas:
https://github.com/llvm/llvm-project/blob/379daa29744cd96b0a87ed0d4a010fa4bc47ce73/llvm/include/llvm/Support/AlignOf.h

At the time, x86 MSVC 2015 would reject attempts to pass overaligned objects by value. Instead, it would just misalign them (4 byte alignment only). People were passing AlignedCharArray objects by value, so we couldn't use alignas without breaking the build. We just had to live with misalignment bugs. Somewhere back in MSVC 2017 they added support for passing overaligned arguments by value (nevermind that it had bugs: https://developercommunity2.visualstudio.com/t/msvc-copies-overaligned-non-trivially-copyable-par/1179643), so we started using alignas.

Now that alignas is safe to use anywhere and it is used by AlignedCharArray, we can remove this redundant alignment requirement.

lgtm

[dexonsmith]

Thanks for the review!

[rnk]

I'm worried that this may have ended up causing issues. There is an experimental 32-bit windows buildbot here:
http://lab.llvm.org:8014/#/builders/27/builds/1792
Recently it has started failing with assertions about alignment:

$ "c:\volumes\buildbot\clang-x86-ninja-win10\stage1\bin\filecheck.exe" "--check-prefix=MODE-SINGLE" "C:\volumes\buildbot\clang-x86-ninja-win10\llvm\clang\test\CodeGen\split-debug-single-file.c"
$ ":" "RUN: at line 14"
$ "c:\volumes\buildbot\clang-x86-ninja-win10\stage1\bin\clang.exe" "-cc1" "-internal-isystem" "c:\volumes\buildbot\clang-x86-ninja-win10\stage1\lib\clang\12.0.0\include" "-nostdsysteminc" "-debug-info-kind=limited" "-triple" "x86_64-unknown-linux" "-split-dwarf-file" "C:\volumes\buildbot\clang-x86-ninja-win10\stage1\tools\clang\test\CodeGen\Output\split-debug-single-file.c.tmp.dwo" "-split-dwarf-output" "C:\volumes\buildbot\clang-x86-ninja-win10\stage1\tools\clang\test\CodeGen\Output\split-debug-single-file.c.tmp.dwo" "-emit-obj" "-o" "C:\volumes\buildbot\clang-x86-ninja-win10\stage1\tools\clang\test\CodeGen\Output\split-debug-single-file.c.tmp.o" "C:\volumes\buildbot\clang-x86-ninja-win10\llvm\clang\test\CodeGen\split-debug-single-file.c" "-fno-experimental-new-pass-manager"
# command stderr:
Assertion failed: (uintptr_t(&data) & (alignof(RootLeaf) - 1)) == 0 && "Insufficient alignment", file Q:\clang-x86-ninja-win10\llvm\llvm\include\llvm/ADT/IntervalMap.h, line 1040
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: c:\\volumes\\buildbot\\clang-x86-ninja-win10\\stage1\\bin\\clang.exe -cc1 -internal-isystem c:\\volumes\\buildbot\\clang-x86-ninja-win10\\stage1\\lib\\clang\\12.0.0\\include -nostdsysteminc -debug-info-kind=limited -triple x86_64-unknown-linux -split-dwarf-file C:\\volumes\\buildbot\\clang-x86-ninja-win10\\stage1\\tools\\clang\\test\\CodeGen\\Output\\split-debug-single-file.c.tmp.dwo -split-dwarf-output C:\\volumes\\buildbot\\clang-x86-ninja-win10\\stage1\\tools\\clang\\test\\CodeGen\\Output\\split-debug-single-file.c.tmp.dwo -emit-obj -o C:\\volumes\\buildbot\\clang-x86-ninja-win10\\stage1\\tools\\clang\\test\\CodeGen\\Output\\split-debug-single-file.c.tmp.o C:\\volumes\\buildbot\\clang-x86-ninja-win10\\llvm\\clang\\test\\CodeGen\\split-debug-single-file.c -fno-experimental-new-pass-manager
1.	<eof> parser at end of file
2.	Code generation
3.	Running pass 'Function Pass Manager' on module 'C:\volumes\buildbot\clang-x86-ninja-win10\llvm\clang\test\CodeGen\split-debug-single-file.c'.
4.	Running pass 'Live DEBUG_VALUE analysis' on function '@main'

I'll investigate.

[dexonsmith]

In D92509#2452929, @rnk wrote:

I'm worried that this may have ended up causing issues.

Thanks for investigating; feel free to add back the alignas if necessary (or ask me to) if that's what's needed. Note that a straight-up revert won't work since AlignedCharArrayUnion was deleted; it'll have to be std::aligned_union_t; on that subject, if alignas doesn't fix it, here are the commits where I changed/deleted AlignedCharArrayUnion, since they could be the problem also:

• 4d8bf870a82765eb0d4fe53c82f796b957c05954 ADT: Remove AlignedCharArrayUnion, NFC
• d10f9863a5ac1cb681af07719650c44b48f289ce ADT: Migrate users of AlignedCharArrayUnion to std::aligned_union_t, NFC
• 4b5dc150b9862271720b3d56a3e723a55dd81838 ADT: Change AlignedCharArrayUnion to an alias of std::aligned_union_t, NFC
• 5b267fb7966157e0d79ea85cbc1d07f92f840d3c ADT: Stop peeking inside AlignedCharArrayUnion, NFC

[rnk]

The problem is that MSVC x86 doesn't actually guarantee the 8 byte alignment that we want:
https://github.com/microsoft/STL/issues/1533
On x86, the Visual C++ compiler only assumes 4 byte stack alignment. The compiler doesn't realign the stack for types that do not explicitly use alignas. So, regular double and uint64_t local variables are not actually 8 byte aligned. The STL implements std::aligned* without using alignas, so the compiler doesn't realign the stack for us.

We can either:

1. Go back to using our own type AlignedCharArrayUnion that works reliably
2. Work around the issue with redundant alignas attributes on all the variables that matter

I will also note that MSVC's std::aligned_storage doesn't support alignments of 16 or higher unless you pass -D_ENABLE_EXTENDED_ALIGNED_STORAGE, but AlignedCharArrayUnion would support such alignments.

I think I lean towards option #1, and I can get to it with straight reverts, so I think I'm going to go ahead and do that for now. I'm OK with option 2, if people like the std:: spelling of this better.

[dexonsmith]

In D92509#2453504, @rnk wrote:

The problem is that MSVC x86 doesn't actually guarantee the 8 byte alignment that we want:
https://github.com/microsoft/STL/issues/1533
On x86, the Visual C++ compiler only assumes 4 byte stack alignment. The compiler doesn't realign the stack for types that do not explicitly use alignas. So, regular double and uint64_t local variables are not actually 8 byte aligned. The STL implements std::aligned* without using alignas, so the compiler doesn't realign the stack for us.

We can either:

1. Go back to using our own type AlignedCharArrayUnion that works reliably
2. Work around the issue with redundant alignas attributes on all the variables that matter

I will also note that MSVC's std::aligned_storage doesn't support alignments of 16 or higher unless you pass -D_ENABLE_EXTENDED_ALIGNED_STORAGE, but AlignedCharArrayUnion would support such alignments.

I think I lean towards option #1, and I can get to it with straight reverts, so I think I'm going to go ahead and do that for now. I'm OK with option 2, if people like the std:: spelling of this better.

I missed this email yesterday, but your solution SGTM.

It looks like you did not revert 65c5c9f92ec514ae41c8ea407d1c885737d699ec (ADT: Rely on std::aligned_union_t for math in AlignedCharArrayUnion, NFC), which changed it to rely on the math in std::aligned_union_t:

template <typename T, typename... Ts> struct AlignedCharArrayUnion {
  using AlignedUnion = std::aligned_union_t<1, T, Ts...>;
  alignas(alignof(AlignedUnion)) char buffer[sizeof(AlignedUnion)];
};

Should that be reverted too, or if not, why does alignof(std::aligned_union_t<...>) give us the right answer?

[rnk]

In D92509#2456446, @dexonsmith wrote:

I missed this email yesterday, but your solution SGTM.

It looks like you did not revert 65c5c9f92ec514ae41c8ea407d1c885737d699ec (ADT: Rely on std::aligned_union_t for math in AlignedCharArrayUnion, NFC), which changed it to rely on the math in std::aligned_union_t:

template <typename T, typename... Ts> struct AlignedCharArrayUnion {
  using AlignedUnion = std::aligned_union_t<1, T, Ts...>;
  alignas(alignof(AlignedUnion)) char buffer[sizeof(AlignedUnion)];
};

Should that be reverted too, or if not, why does alignof(std::aligned_union_t<...>) give us the right answer?

Basically, it's an MSVC compiler bug: it won't align local variables unless they have explicit an alignas attribute. std::aligned_union_t<...> produces a type with the right size and alignment, but then the compiler doesn't follow through on the alignment for local variables. LLVM's implementation uses alignas, which makes it work.

This should be documented in comments, I'll send that out.

[dexonsmith]

In D92509#2456538, @rnk wrote:

Basically, it's an MSVC compiler bug: it won't align local variables unless they have explicit an alignas attribute. std::aligned_union_t<...> produces a type with the right size and alignment, but then the compiler doesn't follow through on the alignment for local variables. LLVM's implementation uses alignas, which makes it work.

This should be documented in comments, I'll send that out.

Okay, sounds great, thanks.

llvm/include/llvm/ADT/IntervalMap.h

 public:
   using Allocator = typename Sizer::Allocator;
   using KeyType = KeyT;
   using ValueType = ValT;
   using KeyTraits = Traits;
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
-  alignas(RootLeaf) alignas(RootBranchData)
-      AlignedCharArrayUnion<RootLeaf, RootBranchData> data;
 
   // Tree height.
   // 0: Leaves in root.
   // 1: Root points to leaf.
   // 2: root->branch->leaf ...
   unsigned height;
 
   // Number of entries in the root node.