[WebAssembly] Fix the order of destructors in the LowerGlobalDtors pass.

[sunfish]

Summary

Fix the LowerGlobalDtors pass to run destructors in the same order as the regular LLVM destructor lowering -- in reverse order, and not ordered to group destructors with common associated objects.

[dschuff]

the commit description says "not ordered to group destructors with common associated objects" but it looks this patch is doing grouping by associated object. Is that intentional?
Also, maybe there should be a test which has destructors of different priorities associated with the same object?

[dschuff]

(also, the langref says that the order within a priority is unspecfied. is something depending on this ordering (I assume so, since you bothered to change it)?

[sunfish]

• Add a comment.
• Add a test of two destructors with different priorities and the same associated object.

[sunfish]

The commit description says "not ordered to group destructors with common associated objects" but it looks this patch is doing grouping by associated object. Is that intentional?

It groups adjacent destructors which happen to have the same associated
object, but doesn't order them by the associated object. I've now added a
comment to clarify that.

Also, maybe there should be a test which has destructors of different priorities associated with the same object?

Test added.

(also, the langref says that the order within a priority is unspecfied. is something depending on this ordering (I assume so, since you bothered to change it)?

C++ says we need to run the destructors in reverse order from the
corresponding constructors, so we need to match the order.

[dschuff]

Thanks; please also update the commit message to match your comment update.

llvm/lib/Target/WebAssembly/WebAssemblyLowerGlobalDtors.cpp

bool LowerGlobalDtors::runOnModule(Module &M) {
   if (!ETy || ETy->getNumElements() != 3 ||
       !ETy->getTypeAtIndex(0U)->isIntegerTy() ||
       !ETy->getTypeAtIndex(1U)->isPointerTy() ||
       !ETy->getTypeAtIndex(2U)->isPointerTy())
     return false; // Not (int, ptr, ptr).
 
   // Collect the contents of @llvm.global_dtors, collated by priority and
   // associated symbol.
-  std::map<uint16_t, MapVector<Constant *, std::vector<Constant *>>> DtorFuncs;
+  std::map<
+      uint16_t,
+      std::vector<std::pair<Constant *, std::vector<Constant *>>>
+  > DtorFuncs;
   for (Value *O : InitList->operands()) {
     auto *CS = dyn_cast<ConstantStruct>(O);
     if (!CS)
       continue; // Malformed.
 
     auto *Priority = dyn_cast<ConstantInt>(CS->getOperand(0));
     if (!Priority)
       continue; // Malformed.
     uint16_t PriorityValue = Priority->getLimitedValue(UINT16_MAX);
 
     Constant *DtorFunc = CS->getOperand(1);
     if (DtorFunc->isNullValue())
       break; // Found a null terminator, skip the rest.
 
     Constant *Associated = CS->getOperand(2);
     Associated = cast<Constant>(Associated->stripPointerCasts());
 
-    DtorFuncs[PriorityValue][Associated].push_back(DtorFunc);
+    auto &AtThisPriority = DtorFuncs[PriorityValue];
+    if (AtThisPriority.empty() || AtThisPriority.back().first != Associated) {
+        std::vector<Constant *> NewList;
+        NewList.push_back(DtorFunc);
+        AtThisPriority.push_back(std::make_pair(Associated, NewList));
+    } else {
+        AtThisPriority.back().second.push_back(DtorFunc);
+    }
   }
   if (DtorFuncs.empty())
     return false;
 
   // extern "C" int __cxa_atexit(void (*f)(void *), void *p, void *d);
   LLVMContext &C = M.getContext();
   PointerType *VoidStar = Type::getInt8PtrTy(C);
   Type *AtExitFuncArgs[] = {VoidStar};
if (!DsoHandle) {
     DsoHandle = Handle;
   }
 
   // For each unique priority level and associated symbol, generate a function
   // to call all the destructors at that level, and a function to register the
   // first function with __cxa_atexit.
   for (auto &PriorityAndMore : DtorFuncs) {
     uint16_t Priority = PriorityAndMore.first;
-    for (auto &AssociatedAndMore : PriorityAndMore.second) {
+    uint64_t Id = 0;
+    auto &AtThisPriority = PriorityAndMore.second;
+    for (auto &AssociatedAndMore : AtThisPriority) {
       Constant *Associated = AssociatedAndMore.first;
+      auto ThisId = Id++;
 
       Function *CallDtors = Function::Create(
           AtExitFuncTy, Function::PrivateLinkage,
           "call_dtors" +
               (Priority != UINT16_MAX ? (Twine(".") + Twine(Priority))
                                       : Twine()) +
+              (AtThisPriority.size() > 1 ? Twine("$") + Twine(ThisId)
+                                         : Twine()) +
               (!Associated->isNullValue() ? (Twine(".") + Associated->getName())
                                           : Twine()),
           &M);
       BasicBlock *BB = BasicBlock::Create(C, "body", CallDtors);
       FunctionType *VoidVoid = FunctionType::get(Type::getVoidTy(C),
                                                  /*isVarArg=*/false);
 
-      for (auto Dtor : AssociatedAndMore.second)
+      for (auto Dtor : reverse(AssociatedAndMore.second))
         CallInst::Create(VoidVoid, Dtor, "", BB);
       ReturnInst::Create(C, BB);
 
       Function *RegisterCallDtors = Function::Create(
           VoidVoid, Function::PrivateLinkage,
           "register_call_dtors" +
               (Priority != UINT16_MAX ? (Twine(".") + Twine(Priority))
                                       : Twine()) +
+              (AtThisPriority.size() > 1 ? Twine("$") + Twine(ThisId)
+                                         : Twine()) +
               (!Associated->isNullValue() ? (Twine(".") + Associated->getName())
                                           : Twine()),
           &M);
       BasicBlock *EntryBB = BasicBlock::Create(C, "entry", RegisterCallDtors);
       BasicBlock *FailBB = BasicBlock::Create(C, "fail", RegisterCallDtors);
       BasicBlock *RetBB = BasicBlock::Create(C, "return", RegisterCallDtors);
 
       Value *Null = ConstantPointerNull::get(VoidStar);

llvm/test/CodeGen/WebAssembly/lower-global-dtors.ll

 ; RUN: llc < %s -asm-verbose=false -wasm-keep-registers | FileCheck --check-prefix=CHECK --check-prefix=FINI --check-prefix=NULL %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; Test that @llvm.global_dtors is properly lowered into @llvm.global_ctors,
 ; grouping dtor calls by priority and associated symbol.
 
 declare void @orig_ctor()
 declare void @orig_dtor0()
 declare void @orig_dtor1a()
 declare void @orig_dtor1b()
 declare void @orig_dtor1c0()
 declare void @orig_dtor1c1a()
 declare void @orig_dtor1c1b()
-declare void @orig_dtor65536()
+declare void @orig_dtor1c2a()
+declare void @orig_dtor1c2b()
+declare void @orig_dtor1c3()
+declare void @orig_dtor1d()
+declare void @orig_dtor65535()
 declare void @after_the_null()
 
 @associated1c0 = external global i8
 @associated1c1 = external global i8
+@associated1c2 = global i8 42
+@associated1c3 = global i8 84
 
 @llvm.global_ctors = appending global
 [1 x { i32, void ()*, i8* }]
 [
   { i32, void ()*, i8* } { i32 200, void ()* @orig_ctor, i8* null }
 ]
 
 @llvm.global_dtors = appending global
-[9 x { i32, void ()*, i8* }]
+[13 x { i32, void ()*, i8* }]
 [
   { i32, void ()*, i8* } { i32 0, void ()* @orig_dtor0, i8* null },
   { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1a, i8* null },
   { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1b, i8* null },
   { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1c0, i8* @associated1c0 },
   { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1c1a, i8* @associated1c1 },
   { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1c1b, i8* @associated1c1 },
-  { i32, void ()*, i8* } { i32 65535, void ()* @orig_dtor65536, i8* null },
+  { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1c2a, i8* @associated1c2 },
+  { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1c2b, i8* @associated1c2 },
+  { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1c3, i8* @associated1c3 },
+  { i32, void ()*, i8* } { i32 1, void ()* @orig_dtor1d, i8* null },
+  { i32, void ()*, i8* } { i32 65535, void ()* @orig_dtor65535, i8* null },
   { i32, void ()*, i8* } { i32 65535, void ()* null, i8* null },
   { i32, void ()*, i8* } { i32 65535, void ()* @after_the_null, i8* null }
 ]
 
 ; CHECK-LABEL: .Lcall_dtors.0:
 ; CHECK-NEXT: .functype .Lcall_dtors.0 (i32) -> (){{$}}
 ; CHECK-NEXT: call            orig_dtor0{{$}}
 
 ; CHECK-LABEL: .Lregister_call_dtors.0:
 ; CHECK:      block
 ; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.0{{$}}
 ; CHECK-NEXT: i32.const       $push1=, 0
 ; CHECK-NEXT: i32.const       $push0=, __dso_handle
 ; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
 ; CHECK-NEXT: i32.eqz         $push4=, $pop3
 ; CHECK-NEXT: br_if           0, $pop4
 ; CHECK-NEXT: unreachable
 ;      CHECK: end_block
 
-; CHECK-LABEL: .Lcall_dtors.1:
-; CHECK-NEXT: .functype .Lcall_dtors.1 (i32) -> (){{$}}
-; CHECK-NEXT: call            orig_dtor1a{{$}}
+; CHECK-LABEL: .Lcall_dtors.1$0:
+; CHECK-NEXT: .functype .Lcall_dtors.1$0 (i32) -> (){{$}}
 ; CHECK-NEXT: call            orig_dtor1b{{$}}
+; CHECK-NEXT: call            orig_dtor1a{{$}}
 
-; CHECK-LABEL: .Lregister_call_dtors.1:
+; CHECK-LABEL: .Lregister_call_dtors.1$0:
 ; CHECK:      block
-; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1{{$}}
+; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1$0{{$}}
 ; CHECK-NEXT: i32.const       $push1=, 0
 ; CHECK-NEXT: i32.const       $push0=, __dso_handle
 ; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
 ; CHECK-NEXT: i32.eqz         $push4=, $pop3
 ; CHECK-NEXT: br_if           0, $pop4
 ; CHECK-NEXT: unreachable
 ;      CHECK: end_block
 
-; CHECK-LABEL: .Lcall_dtors.1.associated1c0:
-; CHECK-NEXT: .functype .Lcall_dtors.1.associated1c0 (i32) -> (){{$}}
+; CHECK-LABEL: .Lcall_dtors.1$1.associated1c0:
+; CHECK-NEXT: .functype .Lcall_dtors.1$1.associated1c0 (i32) -> (){{$}}
 ; CHECK-NEXT: call            orig_dtor1c0{{$}}
 
-; CHECK-LABEL: .Lregister_call_dtors.1.associated1c0:
+; CHECK-LABEL: .Lregister_call_dtors.1$1.associated1c0:
 ; CHECK:      block
-; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1.associated1c0{{$}}
+; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1$1.associated1c0{{$}}
 ; CHECK-NEXT: i32.const       $push1=, 0
 ; CHECK-NEXT: i32.const       $push0=, __dso_handle
 ; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
 ; CHECK-NEXT: i32.eqz         $push4=, $pop3
 ; CHECK-NEXT: br_if           0, $pop4
 ; CHECK-NEXT: unreachable
 
-; CHECK-LABEL: .Lcall_dtors.1.associated1c1:
-; CHECK-NEXT: .functype .Lcall_dtors.1.associated1c1 (i32) -> (){{$}}
-; CHECK-NEXT: call            orig_dtor1c1a{{$}}
+; CHECK-LABEL: .Lcall_dtors.1$2.associated1c1:
+; CHECK-NEXT: .functype .Lcall_dtors.1$2.associated1c1 (i32) -> (){{$}}
 ; CHECK-NEXT: call            orig_dtor1c1b{{$}}
+; CHECK-NEXT: call            orig_dtor1c1a{{$}}
+
+; CHECK-LABEL: .Lregister_call_dtors.1$2.associated1c1:
+; CHECK:      block
+; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1$2.associated1c1{{$}}
+; CHECK-NEXT: i32.const       $push1=, 0
+; CHECK-NEXT: i32.const       $push0=, __dso_handle
+; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
+; CHECK-NEXT: i32.eqz         $push4=, $pop3
+; CHECK-NEXT: br_if           0, $pop4
+; CHECK-NEXT: unreachable
+
+; CHECK-LABEL: .Lcall_dtors.1$3.associated1c2:
+; CHECK-NEXT: .functype .Lcall_dtors.1$3.associated1c2 (i32) -> (){{$}}
+; CHECK-NEXT: call            orig_dtor1c2b{{$}}
+; CHECK-NEXT: call            orig_dtor1c2a{{$}}
+
+; CHECK-LABEL: .Lregister_call_dtors.1$3.associated1c2:
+; CHECK:      block
+; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1$3.associated1c2{{$}}
+; CHECK-NEXT: i32.const       $push1=, 0
+; CHECK-NEXT: i32.const       $push0=, __dso_handle
+; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
+; CHECK-NEXT: i32.eqz         $push4=, $pop3
+; CHECK-NEXT: br_if           0, $pop4
+; CHECK-NEXT: unreachable
+
+; CHECK-LABEL: .Lcall_dtors.1$4.associated1c3:
+; CHECK-NEXT: .functype .Lcall_dtors.1$4.associated1c3 (i32) -> (){{$}}
+; CHECK-NEXT: call            orig_dtor1c3{{$}}
+
+; CHECK-LABEL: .Lregister_call_dtors.1$4.associated1c3:
+; CHECK:      block
+; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1$4.associated1c3{{$}}
+; CHECK-NEXT: i32.const       $push1=, 0
+; CHECK-NEXT: i32.const       $push0=, __dso_handle
+; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
+; CHECK-NEXT: i32.eqz         $push4=, $pop3
+; CHECK-NEXT: br_if           0, $pop4
+; CHECK-NEXT: unreachable
+
+; CHECK-LABEL: .Lcall_dtors.1$5:
+; CHECK-NEXT: .functype .Lcall_dtors.1$5 (i32) -> (){{$}}
+; CHECK-NEXT: call            orig_dtor1d{{$}}
 
-; CHECK-LABEL: .Lregister_call_dtors.1.associated1c1:
+; CHECK-LABEL: .Lregister_call_dtors.1$5:
 ; CHECK:      block
-; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1.associated1c1{{$}}
+; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors.1$5{{$}}
 ; CHECK-NEXT: i32.const       $push1=, 0
 ; CHECK-NEXT: i32.const       $push0=, __dso_handle
 ; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
 ; CHECK-NEXT: i32.eqz         $push4=, $pop3
 ; CHECK-NEXT: br_if           0, $pop4
 ; CHECK-NEXT: unreachable
 
 ; CHECK-LABEL: .Lcall_dtors:
 ; CHECK-NEXT: .functype .Lcall_dtors (i32) -> (){{$}}
-; CHECK-NEXT: call            orig_dtor65536{{$}}
+; CHECK-NEXT: call            orig_dtor65535{{$}}
 
 ; CHECK-LABEL: .Lregister_call_dtors:
 ; CHECK:      block
 ; CHECK-NEXT: i32.const       $push2=, .Lcall_dtors{{$}}
 ; CHECK-NEXT: i32.const       $push1=, 0
 ; CHECK-NEXT: i32.const       $push0=, __dso_handle
 ; CHECK-NEXT: i32.call        $push3=, __cxa_atexit, $pop2, $pop1, $pop0{{$}}
 ; CHECK-NEXT: i32.eqz         $push4=, $pop3
 ; CHECK-NEXT: br_if           0, $pop4
 ; CHECK-NEXT: unreachable
 
 ; CHECK-LABEL: .section .init_array.0,"",@
 ;      CHECK: .int32  .Lregister_call_dtors.0{{$}}
 ; CHECK-LABEL: .section .init_array.1,"",@
-;      CHECK: .int32  .Lregister_call_dtors.1{{$}}
+;      CHECK: .int32  .Lregister_call_dtors.1$0{{$}}
+; CHECK-NEXT: .int32  .Lregister_call_dtors.1$3.associated1c2{{$}}
+; CHECK-NEXT: .int32  .Lregister_call_dtors.1$4.associated1c3{{$}}
+; CHECK-NEXT: .int32  .Lregister_call_dtors.1$5{{$}}
 ; CHECK-LABEL: .section .init_array.200,"",@
 ;      CHECK: .int32  orig_ctor{{$}}
 ; CHECK-LABEL: .section .init_array,"",@
 ;      CHECK: .int32  .Lregister_call_dtors{{$}}
 
 ; CHECK-LABEL: .weak __dso_handle
 
 ; CHECK-LABEL: .functype __cxa_atexit (i32, i32, i32) -> (i32){{$}}