This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by jinlin on Jan 6 2021, 4:12 PM.

Details

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.

Diff Detail

Event Timeline

jinlin created this revision.Jan 6 2021, 4:12 PM
jinlin requested review of this revision.Jan 6 2021, 4:12 PM
jinlin updated this revision to Diff 316570.Jan 13 2021, 10:38 PM
jinlin updated this revision to Diff 316672.Jan 14 2021, 8:40 AM
hiraditya added inline comments.Jan 16 2021, 10:01 AM
llvm/lib/Linker/IRMover.cpp
1477

Can we move this inside the condition below?

1508

use erase

jinlin added inline comments.Jan 21 2021, 5:57 PM
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.

jinlin updated this revision to Diff 318373.Jan 21 2021, 6:00 PM
jinlin updated this revision to Diff 327348.Mar 1 2021, 9:04 PM
jinlin updated this revision to Diff 327349.Mar 1 2021, 9:09 PM
jinlin updated this revision to Diff 327350.
jdoerfert requested changes to this revision.Mar 2 2021, 9:06 AM

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)?

This revision now requires changes to proceed.Mar 2 2021, 9:06 AM
jinlin added a comment.Mar 2 2021, 9:13 AM

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.

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 added a comment.Mar 2 2021, 9:49 AM

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.

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 updated this revision to Diff 327511.Mar 2 2021, 10:33 AM

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 added a comment.EditedMar 3 2021, 8:02 PM

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 updated this revision to Diff 338131.Apr 16 2021, 8:35 AM
jinlin edited the summary of this revision. (Show Details)

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.

jinlin retitled this revision from Preserve the lexical order of global variables during llvm-link merge to Preserve the lexical order for global variables during llvm-link merge.Apr 16 2021, 8:57 AM

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.

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).

  1. 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).

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());
}

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.

jinlin updated this revision to Diff 339043.Apr 20 2021, 4:32 PM

This looks clean. LGTM. @dexonsmith comments?

jdoerfert accepted this revision.Apr 22 2021, 9:05 AM
This revision is now accepted and ready to land.Apr 22 2021, 9:05 AM
dexonsmith accepted this revision.Apr 22 2021, 11:38 AM

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."

jinlin updated this revision to Diff 339851.Apr 22 2021, 8:02 PM
jinlin marked an inline comment as done.
jinlin updated this revision to Diff 339853.Apr 22 2021, 8:09 PM
jinlin updated this revision to Diff 339854.Apr 22 2021, 8:12 PM
jinlin updated this revision to Diff 339877.Apr 22 2021, 10:04 PM
jinlin updated this revision to Diff 340065.Apr 23 2021, 9:09 AM
jinlin updated this revision to Diff 340135.Apr 23 2021, 12:09 PM
MaskRay added inline comments.
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 added inline comments.Apr 26 2021, 11:52 PM
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.