Preserve the lexical order for global variables during llvm-link merge

[jinlin]

Summary

The order of global variables is generated in the order of recursively materializing variables if the global variable has the attribute of hasLocalLinkage or hasLinkOnceLinkage during the module merging. In practice, it is often the exact reverse of source order. This new order may cause performance regression.

The change is to preserve the original lexical order for global variables.

[hiraditya]

llvm/lib/Linker/IRMover.cpp

1484

Can we move this inside the condition below?

1488

use erase

[jinlin]

llvm/lib/Linker/IRMover.cpp

1484

Sure.

1488

In some cases, the size of NewElements is larger than that
of OldElemts. You cannot simply use erase.

[jdoerfert]

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

[jinlin]

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

[jdoerfert]

In D94202#2597614, @jinlin wrote:

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

Aren't the globals stored in a list that allows to change their order? It has a remove and insert, that should be sufficient.

[jinlin]

In D94202#2597644, @jdoerfert wrote:

In D94202#2597614, @jinlin wrote:

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

Aren't the globals stored in a list that allows to change their order? It has a remove and insert, that should be sufficient.

You can remove, replace or append. However, you cannot insert. Please correct me if I am wrong.

[jdoerfert]

In D94202#2597735, @jinlin wrote:

In D94202#2597644, @jdoerfert wrote:

In D94202#2597614, @jinlin wrote:

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

Aren't the globals stored in a list that allows to change their order? It has a remove and insert, that should be sufficient.

You can remove, replace or append. However, you cannot insert. Please correct me if I am wrong.

As far as I can tell the list has insert with a position.

[jinlin]

In D94202#2597753, @jdoerfert wrote:

In D94202#2597735, @jinlin wrote:

In D94202#2597644, @jdoerfert wrote:

In D94202#2597614, @jinlin wrote:

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

Aren't the globals stored in a list that allows to change their order? It has a remove and insert, that should be sufficient.

You can remove, replace or append. However, you cannot insert. Please correct me if I am wrong.

As far as I can tell the list has insert with a position.

The globals are in the SymbolTableList. It does not provide any util for insertion.

94 public:
95 void addNodeToList(ValueSubClass *V);
96 void removeNodeFromList(ValueSubClass *V);
97 void transferNodesFromList(SymbolTableListTraits &L2, iterator first,
98 iterator last);
99 // private:
100 template<typename TPtr>
101 void setSymTabObject(TPtr *, TPtr);
102 static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; }
103 static ValueSymbolTable *toPtr(ValueSymbolTable &R) { return &R; }
104 };

[jdoerfert]

In D94202#2597943, @jinlin wrote:

In D94202#2597753, @jdoerfert wrote:

In D94202#2597735, @jinlin wrote:

In D94202#2597644, @jdoerfert wrote:

In D94202#2597614, @jinlin wrote:

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

Aren't the globals stored in a list that allows to change their order? It has a remove and insert, that should be sufficient.

You can remove, replace or append. However, you cannot insert. Please correct me if I am wrong.

As far as I can tell the list has insert with a position.

The globals are in the SymbolTableList. It does not provide any util for insertion.

94 public:
95 void addNodeToList(ValueSubClass *V);
96 void removeNodeFromList(ValueSubClass *V);
97 void transferNodesFromList(SymbolTableListTraits &L2, iterator first,
98 iterator last);
99 // private:
100 template<typename TPtr>
101 void setSymTabObject(TPtr *, TPtr);
102 static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; }
103 static ValueSymbolTable *toPtr(ValueSymbolTable &R) { return &R; }
104 };

Isn't a SymbolTableList a iplist_impl which has insert and remove? (FWIW, you copied the interface of SymbolTableListTraits not SymbolTableList)

[jinlin]

In D94202#2602191, @jdoerfert wrote:

In D94202#2597943, @jinlin wrote:

In D94202#2597753, @jdoerfert wrote:

In D94202#2597735, @jinlin wrote:

In D94202#2597644, @jdoerfert wrote:

In D94202#2597614, @jinlin wrote:

In D94202#2597598, @jdoerfert wrote:

This looks brittle and wrong to fiddle with the initializers of the variables and doing some complex logic.
You want to preserve the order, ok, couldn't we just sort the globals in the resulting module according to the order in the source(s)?

Sorry I have sent the wrong patch to the review and it causes many lit cases fails.

The order of the globals is determined when the globals are generated. If you want to sort the order, you have to regenerate the globals and replace the old ones with new ones.

Aren't the globals stored in a list that allows to change their order? It has a remove and insert, that should be sufficient.

You can remove, replace or append. However, you cannot insert. Please correct me if I am wrong.

As far as I can tell the list has insert with a position.

The globals are in the SymbolTableList. It does not provide any util for insertion.

94 public:
95 void addNodeToList(ValueSubClass *V);
96 void removeNodeFromList(ValueSubClass *V);
97 void transferNodesFromList(SymbolTableListTraits &L2, iterator first,
98 iterator last);
99 // private:
100 template<typename TPtr>
101 void setSymTabObject(TPtr *, TPtr);
102 static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; }
103 static ValueSymbolTable *toPtr(ValueSymbolTable &R) { return &R; }
104 };

Isn't a SymbolTableList a iplist_impl which has insert and remove? (FWIW, you copied the interface of SymbolTableListTraits not SymbolTableList)

You are right. So I added post-process code to preserve the lexical order of global variables.

[jdoerfert]

OK, much nicer already (IMHO).

I think the only thing left to do is to document the "sort" function properly. It's arguably not a trivial sort, see below.

llvm/include/llvm/ADT/simple_ilist.h

270

This function, at least the comment, is not generic (this is ilist after all) and not really explaining what is going on. I don't mind this function here but maybe make the name, and the comment, more descriptive.

[dexonsmith]

I have a few nitpick comments inline, but they might be distractions.

Stepping back, this new sort function seems very special purpose, and unlikely to be reused. It's also pretty complicated, with a few different maps... not sure how easy it will be to document / test / etc.

I wonder about doing this instead:

1. Add a sort function to simple_ilist that takes iterators (for the subrange to be sorted). This would be pretty easy to reuse. Maybe something like this would do it:

template <class Compare>
void sort(iterator First, iterator Last, Compare comp) {
  simple_ilist Sublist;
  Sublist.splice(Sublist.end(), *this, First, Last);
  Sublist.sort(comp);
  splice(Last, Sublist, Sublist.begin(), Sublist.end());
}

That'd be pretty easy to add a unit test for as well. Maybe the sublist sort could be a helper extracted from the full list sort (didn't look closely to see if that was easy).

2. Use the generic Compare argument for proscribing the new order. You could do something like this:

DenseMap<GlobalVariable *, int> Order;
// Build the map table to figure out the desired order of the new
// globals in the destination module.
for (GlobalVariable &GV : SrcM->globals()) {
  if (GV.hasAppendingLinkage())
    continue;
  auto NewGV = Mapper.mapValue(GV);
  if (!NewGV)
    continue;
  NewGV = NewGV->stripPointerCasts();
  if (isa<GlobalVariable>(NewGV))
    Order[&NewGV] = Order.size() + 1; // Start from 1.
}
 
// Advance the pointer to the first newly added element.
auto Begin = Globals.begin();
std::advance(Begin, OldSize);

// Reorder the newly added globals based on the map table.
Globals.sort(Begin, Globals.end(),
    [&Order](const GlobalVariable &LHS, const GlobalVariable &RHS) {
      return Order.lookup(&LHS) < Order.lookup(&RHS);
    });

Note that I started from 1 because Order.lookup() returns 0 for anything not in the map.

llvm/include/llvm/ADT/simple_ilist.h

324

Is comp being used here? I'm not seeing it...

338–339

I think these two dense map lookups can be turned into one with:

if (pointer Dest = DM.lookup(&G)) {

It'd also be good form to invert the condition to avoid nesting:

pointer Dest = DM.lookup(&G);
if (!Dest)
  continue;

340–341

The double-lookup and nesting should be avoided here too, presumably with .find(), unless lookup() will work with an iterator return (I don't think it will but my memory might be wrong).

[dexonsmith]

Or, maybe you can just splice as you go during your first iteration, and you don't need to sort at all or build up any maps...

// Reorder the new globals to match the old order.
for (GlobalVariable &GV : SrcM->globals()) {
  if (GV.hasAppendingLinkage())
    continue;
  auto NewValue = Mapper.mapValue(GV);
  if (!NewValue)
    continue;
  auto *NewGV = dyn_cast<GlobalVariable>(NewValue->stripPointerCasts());
  if (!NewGV)
    continue;
  Globals.splice(Globals.end(), Globals, NewGV->getIterator());
}

[jinlin]

In D94202#2696207, @dexonsmith wrote:

Or, maybe you can just splice as you go during your first iteration, and you don't need to sort at all or build up any maps...

// Reorder the new globals to match the old order.
for (GlobalVariable &GV : SrcM->globals()) {
  if (GV.hasAppendingLinkage())
    continue;
  auto NewValue = Mapper.mapValue(GV);
  if (!NewValue)
    continue;
  auto *NewGV = dyn_cast<GlobalVariable>(NewValue->stripPointerCasts());
  if (!NewGV)
    continue;
  Globals.splice(Globals.end(), Globals, NewGV->getIterator());
}

Great! Many thanks for your suggestions.

[jdoerfert]

This looks clean. LGTM. @dexonsmith comments?

[dexonsmith]

I have a suggestion for the comment inline; with a change there (doesn't need to match my wording) this LGTM.

llvm/lib/Linker/IRMover.cpp

1499–1501

I think it might be more useful to document the goal here, rather than describing how the code accomplishes it. Maybe something like: "Reorder the globals just added to the destination module to match their original order in the source module."

[MaskRay]

llvm/lib/Linker/IRMover.cpp

1509

See test/tools/gold/X86/weak.ll for a case (merging a b and a c, a is weak) where the splice usage regressed the order.

[jinlin]

llvm/lib/Linker/IRMover.cpp

1509

Yes. I have observed this. This change can improve the startup performance of Uber iOS app by 10%. I agree it may miss some corner cases. I can help update this test case if you prefer.

llvm/include/llvm/ADT/ilist.h

 /// ownership semantics.
 ///
 /// This is a subset of ilist functionality that can safely be used on nodes of
 /// polymorphic types, i.e. a heterogeneous list with a common base class that
 /// holds the next/prev pointers.  The only state of the list itself is an
 /// ilist_sentinel, which holds pointers to the first and last nodes in the
 /// list.
 template <class IntrusiveListT, class TraitsT>
-class iplist_impl : public TraitsT, IntrusiveListT {
+class iplist_impl : public TraitsT, public IntrusiveListT {
   typedef IntrusiveListT base_list_type;
 
 public:
   typedef typename base_list_type::pointer pointer;
   typedef typename base_list_type::const_pointer const_pointer;
   typedef typename base_list_type::reference reference;
   typedef typename base_list_type::const_reference const_reference;
   typedef typename base_list_type::value_type value_type;

llvm/include/llvm/ADT/simple_ilist.h

 //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SIMPLE_ILIST_H
 #define LLVM_ADT_SIMPLE_ILIST_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/ilist_base.h"
 #include "llvm/ADT/ilist_iterator.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/ilist_node_options.h"
 #include "llvm/Support/Compiler.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
public:
   void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
   template <class Compare> void merge(simple_ilist &RHS, Compare comp);
   ///@}
 
   /// Sort the list.
   ///@{
   void sort() { sort(std::less<T>()); }
   template <class Compare> void sort(Compare comp);
+
+  /// Reorder the items in the list based on the input map table.
+  template <class Compare>
+  void sort(simple_ilist &RHS, DenseMap<pointer, pointer> &DM, iterator First,
+            iterator Last, Compare comp);
   ///@}
 };
 
 template <class T, class... Options>
 template <class Compare>
 void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) {
   if (this == &RHS || RHS.empty())
     return;
void simple_ilist<T, Options...>::sort(Compare comp) {
   RHS.splice(RHS.end(), *this, Center, end());
 
   // Sort the sublists and merge back together.
   sort(comp);
   RHS.sort(comp);
   merge(RHS, comp);
 }
 
+// Reorder the items in the list based on the input map table.
+template <class T, class... Options>
+template <class Compare>
+void simple_ilist<T, Options...>::sort(simple_ilist &SourceList,
+                                       DenseMap<pointer, pointer> &DM,
+                                       iterator First, iterator Last,
+                                       Compare comp) {
+  // Vacuously sorted.
+  if (empty() || std::next(begin()) == end())
+    return;
+
+  DenseMap<pointer, iterator> PointerMap;
+  iterator Begin = First;
+  while (Begin != Last) {
+    PointerMap[&*Begin] = Begin;
+    ++Begin;
+  }
+
+  simple_ilist ShuffleList;
+  for (auto &G : SourceList) {
+    if (DM.count(&G)) {
+      auto Dest = DM[&G];
+      if (PointerMap.count(Dest)) {
+        auto It = PointerMap[Dest];
+        It++;
+        ShuffleList.splice(ShuffleList.end(), *this, PointerMap[Dest], It);
+      }
+    }
+  }
+
+  iterator LE = end();
+  iterator RI = ShuffleList.begin(), RE = ShuffleList.end();
+  splice(LE, ShuffleList, RI, RE);
+}
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_SIMPLE_ILIST_H

llvm/lib/Linker/IRMover.cpp

class IRLinker {
   Error stringErr(const Twine &T) {
     return make_error<StringError>(T, inconvertibleErrorCode());
   }
 
   /// Entry point for mapping values and alternate context for mapping aliases.
   ValueMapper Mapper;
   unsigned IndirectSymbolMCID;
 
+  /// The map table which maps the old global in the SrcM to the new global
+  /// in the DstM.
+  DenseMap<GlobalVariable *, GlobalVariable *> OldToNewSymbolTable;
+
   /// Handles cloning of a global values from the source module into
   /// the destination module, including setting the attributes and visibility.
   GlobalValue *copyGlobalValueProto(const GlobalValue *SGV, bool ForDefinition);
 
   void emitWarning(const Twine &Message) {
     SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Warning, Message));
   }
 
Error IRLinker::run() {
   if (SrcM->getDataLayout() != DstM.getDataLayout()) {
     emitWarning("Linking two modules of different data layouts: '" +
                 SrcM->getModuleIdentifier() + "' is '" +
                 SrcM->getDataLayoutStr() + "' whereas '" +
                 DstM.getModuleIdentifier() + "' is '" +
                 DstM.getDataLayoutStr() + "'\n");
   }
 
+  OldToNewSymbolTable.clear();
+
   // Copy the target triple from the source to dest if the dest's is empty.
   if (DstM.getTargetTriple().empty() && !SrcM->getTargetTriple().empty())
     DstM.setTargetTriple(SrcM->getTargetTriple());
 
   Triple SrcTriple(SrcM->getTargetTriple()), DstTriple(DstM.getTargetTriple());
 
   if (!SrcM->getTargetTriple().empty()&&
       !SrcTriple.isCompatibleWith(DstTriple))
     emitWarning("Linking two modules of different target triples: '" +
                 SrcM->getModuleIdentifier() + "' is '" +
                 SrcM->getTargetTriple() + "' whereas '" +
                 DstM.getModuleIdentifier() + "' is '" + DstM.getTargetTriple() +
                 "'\n");
 
   DstM.setTargetTriple(SrcTriple.merge(DstTriple));
 
   // Loop over all of the linked values to compute type mappings.
   computeTypeMapping();
 
+  Module::GlobalListType &Globals = DstM.getGlobalList();
+  unsigned OldSize = Globals.size();
+
   std::reverse(Worklist.begin(), Worklist.end());
   while (!Worklist.empty()) {
     GlobalValue *GV = Worklist.back();
     Worklist.pop_back();
 
     // Already mapped.
     if (ValueMap.find(GV) != ValueMap.end() ||
         IndirectSymbolValueMap.find(GV) != IndirectSymbolValueMap.end())
Error IRLinker::run() {
   // Remap all of the named MDNodes in Src into the DstM module. We do this
   // after linking GlobalValues so that MDNodes that reference GlobalValues
   // are properly remapped.
   linkNamedMDNodes();
 
   if (!IsPerformingImport && !SrcM->getModuleInlineAsm().empty()) {
     // Append the module inline asm string.
     DstM.appendModuleInlineAsm(adjustInlineAsm(SrcM->getModuleInlineAsm(),
                                                SrcTriple));
   } else if (IsPerformingImport) {
     // Import any symver directives for symbols in DstM.
     ModuleSymbolTable::CollectAsmSymvers(*SrcM,
                                          [&](StringRef Name, StringRef Alias) {
       if (DstM.getNamedValue(Name)) {
         SmallString<256> S(".symver ");
         S += Name;
         S += ", ";
         S += Alias;
         DstM.appendModuleInlineAsm(S);
       }
     });
   }
 
+  // Build the map table to store the mapping between the old globals in
+  // the source module to the new globals in the destination module.
+  for (GlobalVariable &GV : SrcM->globals()) {
+    if (GV.hasAppendingLinkage())
+      continue;
+    auto NewGV = Mapper.mapValue(GV);
+    if (NewGV) {
+      NewGV = NewGV->stripPointerCasts();
+      if (isa<GlobalVariable>(NewGV))
+        OldToNewSymbolTable[&GV] = cast<GlobalVariable>(NewGV);
+    }
+  }
+
+  // Advance the pointer to the first newly added element.
+  auto Begin = Globals.begin();
+  std::advance(Begin, OldSize);
+
+  // Reorder the newly added globals based on the map table.
+  Globals.sort(SrcM->getGlobalList(), OldToNewSymbolTable, Begin, Globals.end(),
+               nullptr);
+
+
   // Merge the module flags into the DstM module.
   return linkModuleFlagsMetadata();
 }
 
 IRMover::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P)
     : ETypes(E), IsPacked(P) {}
 
 IRMover::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST)
     : ETypes(ST->elements()), IsPacked(ST->isPacked()) {}
 
 bool IRMover::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const {
   return IsPacked == That.IsPacked && ETypes == That.ETypes;
 }
 
 bool IRMover::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const {
   return !this->operator==(That);
 }
 
 StructType *IRMover::StructTypeKeyInfo::getEmptyKey() {
   return DenseMapInfo<StructType *>::getEmptyKey();
 }
 
 StructType *IRMover::StructTypeKeyInfo::getTombstoneKey() {
   return DenseMapInfo<StructType *>::getTombstoneKey();
 }
 
 unsigned IRMover::StructTypeKeyInfo::getHashValue(const KeyTy &Key) {
   return hash_combine(hash_combine_range(Key.ETypes.begin(), Key.ETypes.end()),
                       Key.IsPacked);
 }

llvm/test/Linker/Inputs/globalorder-2.ll

+@var5 = internal global i32 0, align 4
+@var6 = internal global i32 0, align 4
+@var7 = global i32* @var5, align 4
+@var8 = global i32* @var6, align 4
+
+define i32 @foo2() {
+entry:
+  %0 = load i32*, i32** @var7, align 4
+  %1 = load i32, i32* %0, align 4
+  %2 = load i32*, i32** @var8, align 4
+  %3 = load i32, i32* %2, align 4
+  %add = add nsw i32 %3, %1
+  ret i32 %add
+}

llvm/test/Linker/comdat14.ll

 ; RUN: llvm-link -S %s %p/Inputs/comdat14.ll -o - | FileCheck %s
 
 $c = comdat any
 
 @v = global i32 0, comdat ($c)
 
 ; CHECK: @v = global i32 0, comdat($c)
-; CHECK: @v2 = external dllexport global i32
 ; CHECK: @v3 = external global i32
+; CHECK: @v2 = external dllexport global i32

llvm/test/Linker/ctors.ll

 ; RUN: llvm-link %s %p/Inputs/ctors.ll -S -o - | \
 ; RUN:   FileCheck --check-prefix=ALL --check-prefix=CHECK1 %s
 ; RUN: llvm-link %p/Inputs/ctors.ll %s -S -o - | \
 ; RUN:   FileCheck --check-prefix=ALL --check-prefix=CHECK2 %s
 
 ; Test the bitcode writer too. It used to crash.
 ; RUN: llvm-link %s %p/Inputs/ctors.ll -o %t.bc
 
+; ALL: @llvm.global_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* @v }]
 @v = weak global i8 0
 ; CHECK1: @v = weak global i8 0
 ; CHECK2: @v = weak global i8 1
 
 @llvm.global_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* @v }]
-; ALL: @llvm.global_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* @v }]
 
 define weak void @f() {
   ret void
 }

llvm/test/Linker/globalorder.ll

+; Test the order of global variables during llvm-link
+
+; RUN: llvm-link %s %S/Inputs/globalorder-2.ll -o %t.bc
+; RUN: llvm-dis  -o - %t.bc | FileCheck %s
+
+@var1 = internal global i32 0, align 4
+@var2 = internal global i32 0, align 4
+@var3 = global i32* @var1, align 4
+@var4 = global i32* @var2, align 4
+
+define i32 @foo() {
+entry:
+  %0 = load i32*, i32** @var3, align 4
+  %1 = load i32, i32* %0, align 4
+  %2 = load i32*, i32** @var4, align 4
+  %3 = load i32, i32* %2, align 4
+  %add = add nsw i32 %3, %1
+  ret i32 %add
+}
+; CHECK: @var1 =
+; CHECK-NEXT: @var2 =
+; CHECK-NEXT: @var3 =
+; CHECK-NEXT: @var4 =
+; CHECK-NEXT: @var5 =
+; CHECK-NEXT: @var6 =
+; CHECK-NEXT: @var7 =
+; CHECK-NEXT: @var8 =

llvm/test/Linker/link-flags.ll

 ; RUN: llvm-link -S %S/Inputs/linkage.b.ll %S/Inputs/linkage.c.ll | FileCheck %s -check-prefix=B -check-prefix=C -check-prefix=CU
 ; RUN: llvm-link -S -only-needed %S/Inputs/linkage.b.ll %S/Inputs/linkage.c.ll | FileCheck %s -check-prefix=B -check-prefix=C -check-prefix=CN
 ; RUN: llvm-link -S -internalize %S/Inputs/linkage.b.ll %S/Inputs/linkage.c.ll | FileCheck %s -check-prefix=B -check-prefix=CI
 ; RUN: llvm-link -S -internalize -only-needed %S/Inputs/linkage.b.ll %S/Inputs/linkage.c.ll | FileCheck %s -check-prefix=B -check-prefix=CN
 ; RUN: llvm-link -S -internalize %S/Inputs/linkage.b.ll %S/Inputs/linkage.c.ll %S/Inputs/linkage.d.ll | FileCheck %s -check-prefix=B -check-prefix=DI
 
 C-LABEL: @X = global i32 5
 CI-LABEL: @X = internal global i32 5
 CU-LABEL:@U = global i32 6
 CI-LABEL:@U = internal global i32 6
 CN-NOT:@U
-DI-LABEL: @Y = global i8 42
 DI-LABEL: @llvm.used = appending global [2 x i8*] [i8* @Y, i8* bitcast (i64 ()* @foo to i8*)], section "llvm.metadata"
+DI-LABEL: @Y = global i8 42
 
 B-LABEL: define void @bar() {
 
 C-LABEL: define i32 @foo()
 CI-LABEL: define internal i32 @foo()
 
 CU-LABEL:define i32 @unused() {
 CI-LABEL:define internal i32 @unused() {
 CN-NOT:@unused()
 
 DI-LABEL: define internal i32 @foo.6()
 DI-LABEL: define i64 @foo()

llvm/test/Linker/metadata-attach.ll

 ; RUN: llvm-link %s -S -o - | FileCheck %s
 ; RUN: llvm-link %s %S/Inputs/metadata-attach.ll -S -o - | FileCheck --check-prefix=CHECK-LINKED1 %s
 ; RUN: llvm-link %S/Inputs/metadata-attach.ll %s -S -o - | FileCheck --check-prefix=CHECK-LINKED2 %s
 
 ; CHECK: @g1 = global i32 0, !attach !0{{$}}
 ; CHECK-LINKED1: @g1 = global i32 0, !attach !0{{$}}
 @g1 = global i32 0, !attach !0
 
-; CHECK: @g3 = weak global i32 1, !attach !0{{$}}
 ; CHECK: @g2 = external global i32, !attach !0{{$}}
+; CHECK: @g3 = weak global i32 1, !attach !0{{$}}
 ; CHECK-LINKED1: @g2 = global i32 1, !attach !1{{$}}
 @g2 = external global i32, !attach !0
 
 ; CHECK-LINKED1: @g3 = global i32 2, !attach !1{{$}}
 @g3 = weak global i32 1, !attach !0
 
 ; CHECK-LINKED2: @g2 = global i32 1, !attach !0{{$}}
 ; CHECK-LINKED2: @g3 = global i32 2, !attach !0{{$}}

llvm/test/ThinLTO/X86/import-constant.ll

 ; RUN:    -r=%t2.bc,val,pl \
 ; RUN:    -r=%t2.bc,outer,pl
 ; RUN: llvm-dis %t-out-norefs.1.3.import.bc -o - | FileCheck %s --check-prefix=NOREFS
 
 ; Check that variable has been promoted in the source module
 ; PROMOTE: @_ZL3Obj.llvm.{{.*}} = hidden constant %struct.S { i32 4, i32 8, i32* @val }
 
 ; @outer is a write-only variable, so it's been converted to zeroinitializer.
-; IMPORT:      @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
+; IMPORT: @val = available_externally global i32 42
 ; IMPORT-NEXT: @_ZL3Obj.llvm.{{.*}} = available_externally hidden constant %struct.S { i32 4, i32 8, i32* @val }
-; IMPORT-NEXT: @val = available_externally global i32 42
+; IMPORT-NEXT:      @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
 
 ; OPT: @outer = internal unnamed_addr global %struct.Q zeroinitializer
 
 ; OPT:      define dso_local i32 @main()
 ; OPT-NEXT: entry:
 ; OPT-NEXT:   store %struct.S* null, %struct.S** getelementptr inbounds (%struct.Q, %struct.Q* @outer, i64 0, i32 0)
 ; OPT-NEXT:   ret i32 12
 
-; NOREFS:      @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
-; NOREFS-NEXT: @_ZL3Obj.llvm.{{.*}} = external hidden constant %struct.S
+; NOREFS: @_ZL3Obj.llvm.{{.*}} = external hidden constant %struct.S
+; NOREFS-NEXT:      @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 %struct.S = type { i32, i32, i32* }
 
 define dso_local i32 @main() local_unnamed_addr {
 entry: