[ThinLTO] Ensure objects from static libraries linked in correct order

[tejohnson]

Summary

I recently discovered that ThinLTO native objects links sometimes
occur in a different order than the objects were selected out of
static libraries by the native linker. The ThinLTO ModuleMap
is built (e.g. for gold-plugin) in the original order the objects are
listed in the library. However, the linker may select for inclusion
a later object in a static library first, based on the strong references
it satisfies. It's copies of weak symbols may then be prevailing instead
of an earlier object in the same library. However, the native objects
are linked in the order they were added to the ModuleMap, which would
result in the wrong copy of a weak function being selected in the final
native link for ThinLTO, resulting in incorrect behavior.

Since the linker doesn't provide the native object ordering to the
plugin, we can deduce the correct ordering among modules defining
the same weak symbol based on the prevailing symbols
in the combined index. With this patch we use a stable topological
sort to sort the ModuleMap based on the partial ordering provided by
the combined index.

[mehdi_amini]

I'm not fond of this patch, this does not seems it should belong here: the client of the API is providing the module in order, we should just return them back in the same order. Up to the client to handle this correctly.

lib/LTO/LTO.cpp

839

That assuming that it is possible, i.e. that a linker will always ask for the first symbol to be the prevailing one (if it is not the case you may not be able to generate a topological sort)

[pcc]

Couldn't this be fixed more simply by dropping the losing weak definitions?

[mehdi_amini]

I like better what @pcc said :)

[tejohnson]

In D28523#641676, @pcc wrote:

Couldn't this be fixed more simply by dropping the losing weak definitions?

Maybe, maybe not. A few thoughts:

• Right now we don't drop non-prevailing LinkOnceAny or WeakAny to available_externally in thinLTOResolveWeakForLinkerGUID, but I suppose we could since although they are not guaranteed to be identical (as in the ODR case), we know which is prevailing and it can't be inlined anyway (isInterposableLinkage).
• We can't always drop to available_externally, e.g. in the case where this is an alias or aliasee.
• The original case that motivated my looking into this was more complicated, and in fact we did drop the non-prevailing copies. In that case we had 2 linkonce_odr copies, and both were in comdats. We dropped the non-prevailing copy to available_externally, but it was first in the static library so currently linked first in the native link. The problem was that the comdat group in the module with the non-prevailing copy was still non-empty, it looked like:

COMDAT group section [ 238] `.group' [_ZN4foo_E] contains 2 sections:

[Index]    Name
[  239]   .ctors
[  240]   .rela.ctors

With the wrong object ordering on the final link, this partial comdat group was selected and the one containing the intended prevailing copies was completely removed. (I don't have the final IR handy anymore, but the symbol was originally in the llvm.global_ctors list so presumably that's why we still end up with a comdat group like that?)

Perhaps there is a way to fix my original issue by removing the comdat and all of its constituents when we mark a symbol as available_externally in the backend, but I haven't thought through this too much since discovering the weak symbol issue in the test case here that is also related to the final native link order issue. Fixing that issue by dropping the non-prevailing weak symbol requires also fixing the comdat issue, as well as addressing the limitation we have on dropping non-prevailing copies that are involved with aliases (requires duplication of the aliased definition I believe).

In general, it seems like we're asking for trouble by performing the final native link in a different order than the linker decided on during the thin link. That being said, I don't love this solution, but I didn't think of a better way to determine that ordering.

[tejohnson]

After discussions on IRC, we've decided to pursue a different set of fixes for this and related issues. Essentially forcing the second link to have the same resolution, by aggressively dropping any non-prevailing defs. This will require a few fixes, such as enabling dropping non-prevailing non-odr weak/linkonce, enabling dropping non-prevailing weak involved in an alias, and ensuring comdats with non-prevailing copies are removed. The first new patch relates to the last issue (D28737).

include/llvm/LTO/LTO.h

private:
 
   struct ThinLTOState {
     ThinLTOState(ThinBackend Backend);
 
     ThinBackend Backend;
     ModuleSummaryIndex CombinedIndex;
     MapVector<StringRef, BitcodeModule> ModuleMap;
     DenseMap<GlobalValue::GUID, StringRef> PrevailingModuleForGUID;
+    /// Performs a stable topological sort of the ModuleMap that ensures
+    /// modules with prevailing weak symbols are ordered before any modules
+    /// containing non-prevailing weak defs of those symbols.
+    void sortModuleMap(
+        function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
+        isPrevailing);
   } ThinLTO;
 
   // The global resolution for a particular (mangled) symbol name. This is in
   // particular necessary to track whether each symbol can be internalized.
   // Because any input file may introduce a new cross-partition reference, we
   // cannot make any final internalization decisions until all input files have
   // been added and the client has called run(). During run() we apply
   // internalization decisions either directly to the module (for regular LTO)

lib/LTO/LTO.cpp

 //===-LTO.cpp - LLVM Link Time Optimizer ----------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements functions and classes used to support LTO.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/LTO/LTO.h"
+#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/Bitcode/BitcodeWriter.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/IR/AutoUpgrade.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/LegacyPassManager.h"
return [=](Config &Conf, ModuleSummaryIndex &CombinedIndex,
              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
              AddStreamFn AddStream, NativeObjectCache Cache) {
     return llvm::make_unique<WriteIndexesThinBackend>(
         Conf, CombinedIndex, ModuleToDefinedGVSummaries, OldPrefix, NewPrefix,
         ShouldEmitImportsFiles, LinkedObjectsFile);
   };
 }
 
+// Sort the ModuleMap before launching the backends. This is necessary
+// to ensure that the linker is provided the resulting object files in
+// an order where objects containing prevailing copies of weak symbols are
+// before any that contain non-prevailing copies of those weak symbols.
+// This ensures that the final native link selects the same copy as
+// prevailing. This issue occurs when the weak definitions are in static
+// libraries, where the linker may select an object listed later in the
+// archive (and therefore its weak symbols as the prevailing copies) and
+// later select an object listed earlier in the archive (whose copies of
+// the same weak symbols would then be non-prevailing). Because the linker
+// (e.g. gold) does not provide this ordering to the plugin (the plugin
+// only has the original ordering of the objects in the library which is
+// the order the plugin originally saw them), we need to correct the
+// ModuleMap ordering.
+//
+// We can compute a partial ordering by consulting the combined index
+// to find weak symbols that have multiple copies, and recording that
+// the prevailing copy's module must be before all other non-prevailing copies'
+// modules. Because this is only a partial ordering, we need to do a
+// topological sort. Here we do a stable topological sort, to ensure the
+// rest of the modules stay in their original order.
+void LTO::ThinLTOState::sortModuleMap(
+    function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
+    isPrevailing) {
+  // First collect maps of modules with prevailing symbols to any modules
+  // containing non-prevailing copies of those symbols, and vice versa.
+  std::map<StringRef, std::set<StringRef>> PrevailingToNonPrevailingMods;
+  std::map<StringRef, std::set<StringRef>> NonPrevailingToPrevailingMods;
+  for (auto &I : CombinedIndex) {
+    // Only need to look at weak symbols with more than one copy.
+    if (I.second.size() == 1)
+      continue;
+    // Local symbols can have multiple copies in certain circumstances
+    // (same named local in same named source files each compiled in
+    // their own directory without the relative path). However, the
+    // index is formed by prepending the source file name and therefore
+    // the list will only contain local symbols, so we can skip it.
+    if (GlobalValue::isLocalLinkage(I.second[0]->linkage()))
+      continue;
+    assert(GlobalValue::isWeakForLinker(I.second[0]->linkage()) &&
+           "Index contains multiple copies of non-weak symbols");
+
+    // Find the module with the prevailing copy
+    StringRef PrevailingMod;
+    for (auto &S : I.second) {
+      if (!isPrevailing(I.first, S.get()))
+        continue;
+      PrevailingMod = S->modulePath();
+    }
+    // None of the copies in the ThinLTO objects are prevailing, no need
+    // to reorder them.
+    if (PrevailingMod.empty())
+      continue;
+
+    // Now add to the map entries for the prevailing and non-prevailing
+    // modules to identify the relative ordering.
+    std::set<StringRef> &NonPrevailingMods = PrevailingToNonPrevailingMods[PrevailingMod];
+    for (auto &S : I.second) {
+      if (isPrevailing(I.first, S.get()))
+        continue;
+      assert(!PrevailingToNonPrevailingMods[S->modulePath()].count(PrevailingMod) && "Unexpected circular dependence of modules with prevailing copies");
+      NonPrevailingMods.insert(S->modulePath());
+      NonPrevailingToPrevailingMods[S->modulePath()].insert(PrevailingMod);
+    }
+  }
+
+#if 0
+  errs() << "Before sort\n";
+  for (auto &ModPair : ModuleMap)
+    errs() << ModPair.first << "\n";
+#endif
+
+  // Next construct a priority queue where the priority is the inverse of
+  // the original ordering in the ModuleMap (this is to ensure the ordering
+  // is stable). A Module is entered in the queue when all modules containing
+  // prevailing copies of its weak symbols have been sorted.
+  struct CompareOrigPosition {
+    bool operator()(const std::pair<StringRef, unsigned> &A,
+                    const std::pair<StringRef, unsigned> &B) const {
+      return A.second > B.second;
+    }
+  };
+  PriorityQueue<std::pair<StringRef, unsigned>, std::vector<std::pair<StringRef, unsigned>>, CompareOrigPosition> Ready;
+
+  unsigned Pos = 0;
+  DenseMap<StringRef, unsigned> OrigPositionMap;
+
+  // Initialize the priority queue with modules that don't have any
+  // non-prevailing weak symbols.
+  for (auto &ModPair : ModuleMap) {
+    if (!NonPrevailingToPrevailingMods.count(ModPair.first))
+      Ready.push(std::make_pair(ModPair.first, ++Pos));
+    else
+      // FIXME: Could avoid this if we add an operator< to MapVector
+      OrigPositionMap[ModPair.first] = ++Pos;
+  }
+
+  // Now process the queue, adding any ready modules in their original
+  // ordering to the new ModuleMap.
+  MapVector<StringRef, BitcodeModule> NewModuleMap;
+  //errs() << "After sort\n";
+  while (!Ready.empty()) {
+    StringRef ModPath;
+    std::tie(ModPath, std::ignore) = Ready.top();
+    Ready.pop();
+    //errs() << ModPath << "\n";
+    auto MMI = ModuleMap.find(ModPath);
+    assert(MMI != ModuleMap.end() && "Module missing from ModuleMap");
+    NewModuleMap.insert({ModPath, MMI->second});
+
+    // Now remove this module from the dependent sets for non-prevailing
+    // modules. If any of those ends up with an empty dependent set (all
+    // prevailing modules for its weak symbols are empty), then add them
+    // to the ready queue.
+    auto NonPrevailingMods = PrevailingToNonPrevailingMods.find(ModPath);
+    if (NonPrevailingMods == PrevailingToNonPrevailingMods.end())
+      continue;
+    for (auto &NonPrevailingMod : NonPrevailingMods->second) {
+      auto &PrevailingMods = NonPrevailingToPrevailingMods[NonPrevailingMod];
+      assert(PrevailingMods.count(ModPath) && "Expected to find prevailing module in set for non-prevailing modules");
+      PrevailingMods.erase(ModPath);
+      if (!PrevailingMods.size())
+        Ready.push(std::make_pair(NonPrevailingMod, OrigPositionMap[NonPrevailingMod]));
+    }
+  }
+
+  ModuleMap.swap(NewModuleMap);
+}
+
 Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
                       bool HasRegularLTO) {
   if (ThinLTO.ModuleMap.empty())
     return Error::success();
 
   if (Conf.CombinedIndexHook && !Conf.CombinedIndexHook(ThinLTO.CombinedIndex))
     return Error::success();
 
auto DeadSymbols =
       computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
 
   StringMap<FunctionImporter::ImportMapTy> ImportLists(
       ThinLTO.ModuleMap.size());
   StringMap<FunctionImporter::ExportSetTy> ExportLists(
       ThinLTO.ModuleMap.size());
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 
+  auto isPrevailing = [&](GlobalValue::GUID GUID,
+                          const GlobalValueSummary *S) {
+    return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath();
+  };
+
   if (Conf.OptLevel > 0) {
     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
                              ImportLists, ExportLists, &DeadSymbols);
 
     std::set<GlobalValue::GUID> ExportedGUIDs;
     for (auto &Res : GlobalResolutions) {
       // First check if the symbol was flagged as having external references.
       if (Res.second.Partition != GlobalResolution::External)
         continue;
       // IRName will be defined if we have seen the prevailing copy of
       // this value. If not, no need to mark as exported from a ThinLTO
       // partition (and we can't get the GUID).
       if (Res.second.IRName.empty())
         continue;
       auto GUID = GlobalValue::getGUID(Res.second.IRName);
       // Mark exported unless index-based analysis determined it to be dead.
       if (!DeadSymbols.count(GUID))
         ExportedGUIDs.insert(GlobalValue::getGUID(Res.second.IRName));
     }
 
-    auto isPrevailing = [&](GlobalValue::GUID GUID,
-                            const GlobalValueSummary *S) {
-      return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath();
-    };
     auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
       const auto &ExportList = ExportLists.find(ModuleIdentifier);
       return (ExportList != ExportLists.end() &&
               ExportList->second.count(GUID)) ||
              ExportedGUIDs.count(GUID);
     };
     thinLTOInternalizeAndPromoteInIndex(ThinLTO.CombinedIndex, isExported);
 
     auto recordNewLinkage = [&](StringRef ModuleIdentifier,
                                 GlobalValue::GUID GUID,
                                 GlobalValue::LinkageTypes NewLinkage) {
       ResolvedODR[ModuleIdentifier][GUID] = NewLinkage;
     };
 
     thinLTOResolveWeakForLinkerInIndex(ThinLTO.CombinedIndex, isPrevailing,
                                        recordNewLinkage);
   }
 
+  ThinLTO.sortModuleMap(isPrevailing);
+
   std::unique_ptr<ThinBackendProc> BackendProc =
       ThinLTO.Backend(Conf, ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
                       AddStream, Cache);
 
   // Task numbers start at ParallelCodeGenParallelismLevel if an LTO
   // module is present, as tasks 0 through ParallelCodeGenParallelismLevel-1
   // are reserved for parallel code generation partitions.
   unsigned Task =

test/tools/gold/X86/Inputs/thinlto_weak_library1.ll

+; ModuleID = 'thinlto_weak_library1.c'
+source_filename = "thinlto_weak_library1.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define weak i32 @f() local_unnamed_addr {
+entry:
+  ret i32 1
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define void @test1() local_unnamed_addr {
+entry:
+  ret void
+}

test/tools/gold/X86/Inputs/thinlto_weak_library2.ll

+; ModuleID = 'thinlto_weak_library2.c'
+source_filename = "thinlto_weak_library2.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define weak i32 @f() local_unnamed_addr {
+entry:
+  ret i32 2
+}
+
+; Function Attrs: nounwind uwtable
+define void @test2() local_unnamed_addr {
+entry:
+  tail call void (...) @test1()
+  tail call i32 @f()
+  ret void
+}
+
+declare void @test1(...) local_unnamed_addr

test/tools/gold/X86/thinlto_weak_library.ll

+; Test to ensure that ThinLTO sorts the modules before passing to the
+; final native link based on the linker's determination of which
+; object within a static library contains the prevailing def of a symbol.
+
+; First generate bitcode with a module summary index for each file
+; RUN: opt -module-summary %s -o %t.o
+; RUN: opt -module-summary %p/Inputs/thinlto_weak_library1.ll -o %t2.o
+; RUN: opt -module-summary %p/Inputs/thinlto_weak_library2.ll -o %t3.o
+
+; Although the objects are ordered "%t2.o %t3.o" in the library, the
+; linker selects %t3.o first since it satisfies a strong reference from
+; %t.o. It later selects %t2.o based on the strong ref from %t3.o.
+; Therefore, %t3.o's copy of @f is prevailing, and we need to link
+; %t3.o before %t2.o in the final native link.
+; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
+; RUN:    --plugin-opt=thinlto \
+; RUN:    -m elf_x86_64 \
+; RUN:    -o %t4 \
+; RUN:    %t.o \
+; RUN:    --start-lib %t2.o %t3.o --end-lib
+
+; Make sure linker selected the copy from thinlto_weak_library2.ll (%t3.o)
+; RUN: llvm-objdump -d %t4 | FileCheck %s
+; CHECK: f:
+; CHECK-NEXT: $2,
+
+; Now check the distributed case, where the objects should be emitted
+; into %t5 in the correct order.
+; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
+; RUN:    --plugin-opt=thinlto \
+; RUN:    --plugin-opt=thinlto-index-only=%t5 \
+; RUN:    -m elf_x86_64 \
+; RUN:    -o %t4 \
+; RUN:    %t.o \
+; RUN:    --start-lib %t2.o %t3.o --end-lib
+
+; RUN: cat %t5 | FileCheck %s --check-prefix=OBJECTLIST
+; OBJECTLIST: thinlto_weak_library.ll.tmp.o
+; OBJECTLIST-NEXT: thinlto_weak_library.ll.tmp3.o
+; OBJECTLIST-NEXT: thinlto_weak_library.ll.tmp2.o
+
+; ModuleID = 'thinlto_weak_library.c'
+source_filename = "thinlto_weak_library.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @main() local_unnamed_addr {
+entry:
+  tail call void (...) @test2()
+  ret i32 0
+}
+
+declare void @test2(...) local_unnamed_addr