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

1477

Can we move this inside the condition below?

1508

use erase

[jinlin]

llvm/lib/Linker/IRMover.cpp

1477

Sure.

1508

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 ↗

(On Diff #338131)

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 ↗

(On Diff #338131)

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

338–339 ↗

(On Diff #338131)

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 ↗

(On Diff #338131)

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

1552–1554

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

1562

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

1562

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/lib/Linker/IRMover.cpp

emitWarning("Linking two modules of different target triples: '" +
                 "'\n");
 
   DstM.setTargetTriple(SrcTriple.merge(DstTriple));
 
   // Loop over all of the linked values to compute type mappings.
   computeTypeMapping();
 
   std::reverse(Worklist.begin(), Worklist.end());
+  SmallVector<std::pair<Constant *, GlobalVariable *>, 16> MappedConstants;
+
   while (!Worklist.empty()) {
     GlobalValue *GV = Worklist.back();
     Worklist.pop_back();
 
     // Already mapped.
     if (ValueMap.find(GV) != ValueMap.end() ||
         IndirectSymbolValueMap.find(GV) != IndirectSymbolValueMap.end())
       continue;
 
     assert(!GV->isDeclaration());
-    Mapper.mapValue(*GV);
+
+    // Set the initializer of global variable to be empty so that
+    // the global varaibles in the initializer won't be generated.
+    Constant *InitCnst = nullptr;
+    StringRef Name = GV->getName();
+    if (Name != "llvm.global_ctors" && Name != "llvm.global_dtors") {
+      if (auto *V = dyn_cast<GlobalVariable>(GV)) {
+        if (V->hasInitializer()) {
+          InitCnst = V->getInitializer();
+          if (InitCnst != Constant::getNullValue(V->getValueType()))
+            V->setInitializer(Constant::getNullValue(V->getValueType()));
+          else
+            InitCnst = nullptr;
+        }
+      }
+    }
+
+    // Record the mapping between the old initializer and new
+    // global variable.
+    auto NewV = Mapper.mapValue(*GV);
+    if (InitCnst) {
+      assert(NewV);
+      NewV = NewV->stripPointerCastsAndAliases();
+      auto *NewGV = dyn_cast<GlobalVariable>(NewV);
+      assert(NewGV);
+      MappedConstants.push_back({InitCnst, NewGV});
+    }
+
     if (FoundError)
       return std::move(*FoundError);
     flushRAUWWorklist();
   }
 
+  // Generate the new iniitializer based on the
+  // mapping btween the old initializer and the
+  // new global variable. By this way, the original
+  // lexical order can be preserved.
+  for (auto &MC : MappedConstants) {
+    auto *OldCnst = dyn_cast<Value>(MC.first);
+    auto *NewCnst = Mapper.mapValue(*OldCnst);
+    Constant *C = dyn_cast<Constant>(NewCnst);
+    assert(C);
+    if (MC.second->getInitializer() !=
+        Constant::getNullValue(MC.second->getValueType())) {
+      SmallVector<Constant *, 16> NewElements;
+      getArrayElements(MC.second->getInitializer(), NewElements);
+
+      SmallVector<Constant *, 16> OldElements;
+      getArrayElements(C, OldElements);
+
+      // In some cases, the size of NewElements is larger than that
+      // of OldElemts.
+      unsigned Size = OldElements.size();
+      while (Size > 0) {
+        NewElements.pop_back();
+        Size--;
+      }
+      NewElements.append(OldElements.begin(), OldElements.end());
+      ArrayType *ATyp =
+          dyn_cast<ArrayType>(MC.second->getType()->getElementType());
+      assert(ATyp);
+      C = ConstantArray::get(ATyp, NewElements);
+    }
+    MC.second->setInitializer(C);
+  }
+
   // Note that we are done linking global value bodies. This prevents
   // metadata linking from creating new references.
   DoneLinkingBodies = true;
   Mapper.addFlags(RF_NullMapMissingGlobalValues);
 
   // 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.
ModuleSymbolTable::CollectAsmSymvers(*SrcM,
         S += Name;
         S += ", ";
         S += Alias;
         DstM.appendModuleInlineAsm(S);
       }
     });
   }
 
   // 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() {

llvm/lib/Linker/LinkModules.cpp

if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
     GV.setVisibility(Visibility);
 
     GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(
         DGV->getUnnamedAddr(), GV.getUnnamedAddr());
     DGV->setUnnamedAddr(UnnamedAddr);
     GV.setUnnamedAddr(UnnamedAddr);
   }
 
-  if (!DGV && !shouldOverrideFromSrc() &&
-      (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
-       GV.hasAvailableExternallyLinkage()))
+  if (!DGV && !shouldOverrideFromSrc()) {
+    if (GV.hasAvailableExternallyLinkage())
       return false;
+    if (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage()) {
+      if (GV.getNumUses() == 0)
+        return false;
+      if (GV.hasOneUse() && isa<GlobalValue>(GV.user_back())) {
+        GlobalValue *G = cast<GlobalValue>(GV.user_back());
+        if (G->hasLocalLinkage() || G->hasLinkOnceLinkage())
+          return false;
+      }
+    }
+  }
 
   if (GV.isDeclaration())
     return false;
 
   if (const Comdat *SC = GV.getComdat()) {
     bool LinkFromSrc;
     Comdat::SelectionKind SK;
     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];

llvm/test/Linker/internalize-lazy.ll

 ; RUN: llvm-link -S -internalize %s %p/Inputs/internalize-lazy.ll | FileCheck %s
 
-; CHECK: define internal void @f
 ; CHECK: define internal void @g
+; CHECK: define internal void @f

llvm/test/tools/llvm-link/globalorder.ll

+; Test the order of global variables during llvm-link
+
+; RUN: llvm-link %s -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: @var3 =
+; CHECK-NEXT: @var4 =