[Linker] Fix crash handling appending linkage

[rafauler]

Summary

When linking two llvm.used arrays, if the resulting merged
array ends up with duplicated elements (with the same name) but with
different types, the IRLinker was crashing. This was supposed to be
legal, as the IRLinker bitcasts elements to match types in these
situations.

This bug was exposed by D56928 in clang to support attribute used
in member functions of class templates. Crash happened when self-hosting
with LTO. Since LLVM depends on attribute used to generate code
for the dump() method, ubiquitous in the code base, many input bc
had a definition of this method referenced in their llvm.used array.
Some of these classes got optimized, changing the type of the first
parameter (this) in the dump method, leading to a scenario with a
pool of valid definitions but some with a different type, triggering
this bug.

This is a memory bug: ValueMapper depends on (calls) the materializer
provided by IRLinker, and this materializer was freely calling RAUW
methods whenever a global definition was updated in the temporary merged
output file. However, replaceAllUsesWith may or may not destroy
constants that use this global. If the linked definition has a type
mismatch regarding the new def and the old def, the materializer would
bitcast the old type to the new type and the elements of the llvm.used
array, which already uses bitcast to i8*, would end up with elements
cascading two bitcasts. RAUW would then indirectly call the
constantfolder to update the constant to the new ref, which would,
instead of updating the constant, destroy it to be able to create
a new constant that folds the two bitcasts into one. The problem is that
ValueMapper works with pointers to the same constants that may be
getting destroyed by RAUW. Obviously, RAUW can update references in the
Module to do not use the old destroyed constant, but it can't update
ValueMapper's internal pointers to these constants, which are now
invalid.

The approach here is to move the task of RAUWing old definitions
outside of the materializer.

Test Plan:
Added LIT test case, tested clang self-hosting with D56928 and
verified it works

[efriedma]

lib/Linker/IRMover.cpp

1059 ↗

(On Diff #191346)

Why is the call to std::reverse() necessary? There shouldn't be any other code touching the worklist, so you can just iterate over it normally.

1067 ↗

(On Diff #191346)

ValueMap and AliasValueMap use raw pointers for keys. Do we need to update them if one of those pointers is deleted?

1396 ↗

(On Diff #191346)

I guess you can just flush the worklist here because the mapValue() invariant only applies inside a single call?

[rafauler]

Thanks for your feedback, Eli

lib/Linker/IRMover.cpp

1059 ↗

(On Diff #191346)

Indeed, I'll fix this

1067 ↗

(On Diff #191346)

This is handled in Value's destructor

1396 ↗

(On Diff #191346)

That's correct

[rafauler]

Eli's suggestions

[efriedma]

lib/Linker/IRMover.cpp

1067 ↗

(On Diff #191346)

I don't follow; how could ~Value() possibly find the key of a ValueMap? (The values are ValueHandles, but that's separate.)

[rafauler]

lib/Linker/IRMover.cpp

1067 ↗

(On Diff #191346)

Isn't it the opposite: the values are arbitrary, and the keys are ValueHandles? From ValueMap.h:179:

auto MapResult = Map.insert(std::make_pair(Wrap(KV.first), KV.second));

Wrap() installs the callback paraphernalia that updates the map on deletions/ RAUWs at ValueMapCallbackVH::allUsesReplacedWith / deleted

[efriedma]

LGTM

lib/Linker/IRMover.cpp

1067 ↗

(On Diff #191346)

You're right, sorry, I misread the code.

llvm/trunk/lib/Linker/IRMover.cpp

class IRLinker {
   /// in DstM.  ValueToValueMapTy is a ValueMap, which involves some overhead
   /// due to the use of Value handles which the Linker doesn't actually need,
   /// but this allows us to reuse the ValueMapper code.
   ValueToValueMapTy ValueMap;
   ValueToValueMapTy AliasValueMap;
 
   DenseSet<GlobalValue *> ValuesToLink;
   std::vector<GlobalValue *> Worklist;
+  std::vector<std::pair<GlobalValue *, Value*>> RAUWWorklist;
 
   void maybeAdd(GlobalValue *GV) {
     if (ValuesToLink.insert(GV).second)
       Worklist.push_back(GV);
   }
 
   /// Whether we are importing globals for ThinLTO, as opposed to linking the
   /// source module. If this flag is set, it means that we can rely on some
class IRLinker {
   Error linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src);
 
   /// Functions that take care of cloning a specific global value type
   /// into the destination module.
   GlobalVariable *copyGlobalVariableProto(const GlobalVariable *SGVar);
   Function *copyFunctionProto(const Function *SF);
   GlobalValue *copyGlobalAliasProto(const GlobalAlias *SGA);
 
+  /// Perform "replace all uses with" operations. These work items need to be
+  /// performed as part of materialization, but we postpone them to happen after
+  /// materialization is done. The materializer called by ValueMapper is not
+  /// expected to delete constants, as ValueMapper is holding pointers to some
+  /// of them, but constant destruction may be indirectly triggered by RAUW.
+  /// Hence, the need to move this out of the materialization call chain.
+  void flushRAUWWorklist();
+
   /// When importing for ThinLTO, prevent importing of types listed on
   /// the DICompileUnit that we don't need a copy of in the importing
   /// module.
   void prepareCompileUnitsForImport();
   void linkNamedMDNodes();
 
 public:
   IRLinker(Module &DstM, MDMapT &SharedMDs,
IRLinker::linkAppendingVarProto(GlobalVariable *DstGV,
 
   Mapper.scheduleMapAppendingVariable(*NG,
                                       DstGV ? DstGV->getInitializer() : nullptr,
                                       IsOldStructor, SrcElements);
 
   // Replace any uses of the two global variables with uses of the new
   // global.
   if (DstGV) {
-    DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType()));
-    DstGV->eraseFromParent();
+    RAUWWorklist.push_back(
+        std::make_pair(DstGV, ConstantExpr::getBitCast(NG, DstGV->getType())));
   }
 
   return Ret;
 }
 
 bool IRLinker::shouldLink(GlobalValue *DGV, GlobalValue &SGV) {
   if (ValuesToLink.count(&SGV) || SGV.hasLocalLinkage())
     return true;
Expected<Constant *> IRLinker::linkGlobalValueProto(GlobalValue *SGV,
   // the same as DGV and NewGV, and TypeMap.get() will assert since it
   // assumes it is being invoked on a type in the source module.
   if (DGV && NewGV != SGV) {
     C = ConstantExpr::getPointerBitCastOrAddrSpaceCast(
       NewGV, TypeMap.get(SGV->getType()));
   }
 
   if (DGV && NewGV != DGV) {
-    DGV->replaceAllUsesWith(
-      ConstantExpr::getPointerBitCastOrAddrSpaceCast(NewGV, DGV->getType()));
-    DGV->eraseFromParent();
+    // Schedule "replace all uses with" to happen after materializing is
+    // done. It is not safe to do it now, since ValueMapper may be holding
+    // pointers to constants that will get deleted if RAUW runs.
+    RAUWWorklist.push_back(std::make_pair(
+        DGV,
+        ConstantExpr::getPointerBitCastOrAddrSpaceCast(NewGV, DGV->getType())));
   }
 
   return C;
 }
 
 /// Update the initializers in the Dest module now that all globals that may be
 /// referenced are in Dest.
 void IRLinker::linkGlobalVariable(GlobalVariable &Dst, GlobalVariable &Src) {
Error IRLinker::linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src) {
   if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) {
     linkGlobalVariable(cast<GlobalVariable>(Dst), *GVar);
     return Error::success();
   }
   linkAliasBody(cast<GlobalAlias>(Dst), cast<GlobalAlias>(Src));
   return Error::success();
 }
 
+void IRLinker::flushRAUWWorklist() {
+  for (const auto Elem : RAUWWorklist) {
+    GlobalValue *Old;
+    Value *New;
+    std::tie(Old, New) = Elem;
+
+    Old->replaceAllUsesWith(New);
+    Old->eraseFromParent();
+  }
+  RAUWWorklist.clear();
+}
+
 void IRLinker::prepareCompileUnitsForImport() {
   NamedMDNode *SrcCompileUnits = SrcM->getNamedMetadata("llvm.dbg.cu");
   if (!SrcCompileUnits)
     return;
   // When importing for ThinLTO, prevent importing of types listed on
   // the DICompileUnit that we don't need a copy of in the importing
   // module. They will be emitted by the originating module.
   for (unsigned I = 0, E = SrcCompileUnits->getNumOperands(); I != E; ++I) {
while (!Worklist.empty()) {
     if (ValueMap.find(GV) != ValueMap.end() ||
         AliasValueMap.find(GV) != AliasValueMap.end())
       continue;
 
     assert(!GV->isDeclaration());
     Mapper.mapValue(*GV);
     if (FoundError)
       return std::move(*FoundError);
+    flushRAUWWorklist();
   }
 
   // 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

llvm/trunk/test/LTO/Resolution/X86/Inputs/appending-var-2.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"foo" = type { i8 }
+
[e-mail] = appending global [1 x i8*] [i8* bitcast (i32 (%"foo"*)* @bar to i8*)], section "llvm.metadata"
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @bar(%"foo"* nocapture readnone %this) align 2 !type !0 {
+entry:
+  ret i32 0
+}
+
+!0 = !{i64 0, !"typeid1"}

llvm/trunk/test/LTO/Resolution/X86/appending-var.ll

+; Check we don't crash when linking a global variable with appending linkage
+; if the types in their elements don't have a straightforward mapping, forcing
+; us to use bitcasts.
+
+; RUN: opt %s -o %t1.o
+; RUN: opt %p/Inputs/appending-var-2.ll -o %t2.o
+
+; RUN: llvm-lto2 run -o %t3.o %t1.o %t2.o -r %t1.o,bar, -r %t2.o,bar,px
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"foo.1" = type { i8, i8 }
+declare dso_local i32 @bar(%"foo.1"* nocapture readnone %this) local_unnamed_addr
+
[e-mail] = appending global [1 x i8*] [i8* bitcast (i32 (%"foo.1"*)* @bar to i8*)], section "llvm.metadata"