[llvm][ValueMap] Share the value map between MappingContext

[steven_wu]

Summary

Share the ValueMap for different mapping context to avoid scheduling the
same value twice.

This doesn't work for comdat yet.

[steven_wu]

@pcc @tejohnson I tried to fix the assertion failure shown in the test case (reduced from actual code generated from swift compiler) by simplifying the ValueMapper but I couldn't quite get the comdat tests to pass. I think comdat is relying on some of the indirect symbol that doesn't appear in the ValueMap for the normal context but I couldn't quite figure out how that works. Any suggestion?

[dexonsmith]

Note this somewhat convoluted mapping context code was added in f0d73f95c15f909c6034f1735632695248bb75a8 to deal with comdats, but it has been long enough I don't remember precisely why the comdat tests failed without it. It'd be great to simplify this if we can...

llvm/test/Linker/global-alias-value-map.ll

7

Please simplify the symbol names in the testcase; I'd suggest something like:

@dsolocal = ...
@alias = ...
@constant1 = ...
@constant2 = ...
define @function(...) { ... }
declare @external(...)

11–13

I wonder, can this be reduced further by inlining the second constant into the first?

[steven_wu]

llvm/test/Linker/global-alias-value-map.ll

7

Sure. Those were the original symbol name from libswiftCore. Kept it here for some context.

11–13

No, the second constant needs to be referenced by one alias and another normal GV.

[steven_wu]

Update testcase.

[steven_wu]

FYI, for the broken comdat, see the unit tests breaks

[steven_wu]

Ping. I still couldn't figure the algorithm used here and what semantics does the comdat have. Need some help here.

[dexonsmith]

In D99546#2657116, @steven_wu wrote:

@pcc @tejohnson I tried to fix the assertion failure shown in the test case (reduced from actual code generated from swift compiler) by simplifying the ValueMapper but I couldn't quite get the comdat tests to pass. I think comdat is relying on some of the indirect symbol that doesn't appear in the ValueMap for the normal context but I couldn't quite figure out how that works. Any suggestion?

@pcc or @tejohnson (or maybe @MaskRay from the lld side), any chance you could help explain why the testcases llvm/test/Linker/comdat16.ll and llvm/test/LTO/Resolution/X86/comdat16.ll rely on a separate value map? Or do you have a suggestion for someone else that could help?

Restating the context, maybe with a bit more detail:

• The IR in the testcase attached to the patch is reduced IR from the Swift compiler.
• It triggers an assertion in the IRLinker, which was added ~when Metadata was split out of the Value class hierarchy:

void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
                                          unsigned MCID) {
  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");

• The MCID is a mapping context ID. There are two mapping contexts in the IRMover: one for most values, and separate one for aliases / indirect symbols. scheduleMapGlobalInitializer() is adding GV to a worklist, used to break an otherwise-deep recursion between IRMover and ValueMapper. The assertion fails because the symbol is being scheduled in *both* contexts.
• Steven's proposed fix (removing IndirectSymbolValueMap but keeping the materializer) fixes the testcase above. However, it's incomplete, as it breaks the two comdat testcases.

I don't remember much about this code, although I'm trying to page it back in; IIRC, when I broke the recursion I tried removing the second value map; that broke these same testcases, and I created this "mapping context" ID in order to make progress, but I'm not sure I fully investigated what it was for.

I'm hoping someone that knows more about comdats can help us piece together the motivation here: why do comdats need a separate value map for aliases? (Maybe there's even a simpler/cleaner way to model the requirement.)

[steven_wu]

A bit more information is that the GV that triggers the assertion now is being materialized from both Global and Local (Indirect?) Materializer because of the complexity of the GV and Alias in the module.

On the other side, a non-assert build of the linker doesn't produce any invalid or broken module just because how the materializer is written right now will ignore a GV that is already initialized, even though it is scheduled to be initialized twice.

[dexonsmith]

llvm/test/Linker/global-alias-value-map.ll

1

This seems like enough to reproduce:

; RUN: llvm-link %s -o /dev/null

@gv0 = constant i64* @alias
@gv1 = constant i64 ptrtoint (i64* @gv1 to i64)

@alias = alias i64, i64* @gv1

[dexonsmith]

@steven_wu , I think this bug is a dual of http://reviews.llvm.org/D20586, and the correct fix is something like:

--- a/llvm/lib/Linker/IRMover.cpp
+++ b/llvm/lib/Linker/IRMover.cpp
@@ -602,20 +602,24 @@ Value *IRLinker::materialize(Value *V, bool ForIndirectSymbol) {
       return New;
   }
 
-  // When linking a global for an indirect symbol, it will always be linked.
-  // However we need to check if it was not already scheduled to satisfy a
-  // reference from a regular global value initializer. We know if it has been
-  // schedule if the "New" GlobalValue that is mapped here for the indirect
-  // symbol is the same as the one already mapped. If there is an entry in the
-  // ValueMap but the value is different, it means that the value already had a
-  // definition in the destination module (linkonce for instance), but we need a
-  // new definition for the indirect symbol ("New" will be different.
-  if (ForIndirectSymbol && ValueMap.lookup(SGV) == New)
+  // Decide whether the body should be linked, which is always true when
+  // linking a global for an indirect symbol.
+  if (!ForIndirectSymbol && !shouldLink(New, *SGV))
     return New;
 
-  if (ForIndirectSymbol || shouldLink(New, *SGV))
-    setError(linkGlobalValueBody(*New, *SGV));
+  // If the global is being linked for an indirect symbol, it may have already
+  // been scheduled to satisfy a regular symbol. Similarly, a global being linked
+  // for a regular symbol may have already been scheduled for an indirect
+  // symbol. Check for these cases by looking in the dual value map and
+  // confirming the same value has been scheduled.  If there is an entry in the
+  // ValueMap but the value is different, it means that the value already had a
+  // definition in the destination module (linkonce for instance), but we need
+  // a new definition for the indirect symbol ("New" will be different).
+  if ((ForIndirectSymbol && ValueMap.lookup(SGV) == New) ||
+      (!ForIndirectSymbol && IndirectSymbolValueMap.lookup(SGV) == New))
+    return New;
 
+  setError(linkGlobalValueBody(*New, *SGV));
   return New;
 }

I'll post an alternate patch in a moment.

Others: it'd still be useful to better understand why two value maps are needed for comdats. It'd be great to get that documented in the code.

[dexonsmith]

In D99546#2721427, @dexonsmith wrote:

I'll post an alternate patch in a moment.

Posted as https://reviews.llvm.org/D101419.

[tejohnson]

In D99546#2721266, @dexonsmith wrote:

In D99546#2657116, @steven_wu wrote:

@pcc @tejohnson I tried to fix the assertion failure shown in the test case (reduced from actual code generated from swift compiler) by simplifying the ValueMapper but I couldn't quite get the comdat tests to pass. I think comdat is relying on some of the indirect symbol that doesn't appear in the ValueMap for the normal context but I couldn't quite figure out how that works. Any suggestion?

@pcc or @tejohnson (or maybe @MaskRay from the lld side), any chance you could help explain why the testcases llvm/test/Linker/comdat16.ll and llvm/test/LTO/Resolution/X86/comdat16.ll rely on a separate value map? Or do you have a suggestion for someone else that could help?

I'm afraid I'm not going to be much help, at least not without more investigation. The 2 comdat tests mentioned above (I think the second one is supposed to be llvm/test/LTO/Resolution/X86/comdat.ll?) were added after the separate value map for aliases already existed, and weren't related to any value mapper changes afaict. I just did some archeology and found that the separate map exists as far back as when the IRMover code was introduced by @respindola in 2015, being split from older IR linking code, which also seems to have had a separate value map for aliases (didn't look any further back though, the code was structured quite differently).

In what way do they break with this change?

Restating the context, maybe with a bit more detail:

• The IR in the testcase attached to the patch is reduced IR from the Swift compiler.
• It triggers an assertion in the IRLinker, which was added ~when Metadata was split out of the Value class hierarchy:

void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
                                          unsigned MCID) {
  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");

• The MCID is a mapping context ID. There are two mapping contexts in the IRMover: one for most values, and separate one for aliases / indirect symbols. scheduleMapGlobalInitializer() is adding GV to a worklist, used to break an otherwise-deep recursion between IRMover and ValueMapper. The assertion fails because the symbol is being scheduled in *both* contexts.
• Steven's proposed fix (removing IndirectSymbolValueMap but keeping the materializer) fixes the testcase above. However, it's incomplete, as it breaks the two comdat testcases.

I don't remember much about this code, although I'm trying to page it back in; IIRC, when I broke the recursion I tried removing the second value map; that broke these same testcases, and I created this "mapping context" ID in order to make progress, but I'm not sure I fully investigated what it was for.

I'm hoping someone that knows more about comdats can help us piece together the motivation here: why do comdats need a separate value map for aliases? (Maybe there's even a simpler/cleaner way to model the requirement.)

[dexonsmith]

In D99546#2721573, @tejohnson wrote:

I'm afraid I'm not going to be much help, at least not without more investigation. The 2 comdat tests mentioned above (I think the second one is supposed to be llvm/test/LTO/Resolution/X86/comdat.ll?) were added after the separate value map for aliases already existed, and weren't related to any value mapper changes afaict. I just did some archeology and found that the separate map exists as far back as when the IRMover code was introduced by @respindola in 2015, being split from older IR linking code, which also seems to have had a separate value map for aliases (didn't look any further back though, the code was structured quite differently).

In what way do they break with this change?

Yeah, I noticed that too — this test seems to incidentally catch a problem. The breakage is that comdat $c2 does not get linked in.

[steven_wu]

Thanks @dexonsmith and @tejohnson . I will just abandon this one.

[dexonsmith]

I agree abandoning the change makes sense, but it would be great if we could somehow collectively understand (and document) why we need a second ValueMap for comdats...

llvm/include/llvm/Transforms/Utils/ValueMapper.h

public:
   ValueMapper &operator=(const ValueMapper &) = delete;
   ~ValueMapper();
 
   /// Register an alternate mapping context.
   ///
   /// Returns a MappingContextID that can be used with the various schedule*()
   /// API to switch in a different value map on-the-fly.
   unsigned
-  registerAlternateMappingContext(ValueToValueMapTy &VM,
-                                  ValueMaterializer *Materializer = nullptr);
+  registerAlternateMappingContext(ValueMaterializer *Materializer = nullptr);
 
   /// Add to the current \a RemapFlags.
   ///
   /// \note Like the top-level mapping functions, \a addFlags() must be called
   /// at the top level, not during a callback in a \a ValueMaterializer.
   void addFlags(RemapFlags Flags);
 
   Metadata *mapMetadata(const Metadata &MD);

llvm/lib/Linker/IRMover.cpp

class IRLinker {
   /// A metadata map that's shared between IRLinker instances.
   MDMapT &SharedMDs;
 
   /// Mapping of values from what they used to be in Src, to what they are now
   /// 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 IndirectSymbolValueMap;
 
   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);
IRLinker(Module &DstM, MDMapT &SharedMDs,
            ArrayRef<GlobalValue *> ValuesToLink,
            std::function<void(GlobalValue &, IRMover::ValueAdder)> AddLazyFor,
            bool IsPerformingImport)
       : DstM(DstM), SrcM(std::move(SrcM)), AddLazyFor(std::move(AddLazyFor)),
         TypeMap(Set), GValMaterializer(*this), LValMaterializer(*this),
         SharedMDs(SharedMDs), IsPerformingImport(IsPerformingImport),
         Mapper(ValueMap, RF_ReuseAndMutateDistinctMDs | RF_IgnoreMissingLocals,
                &TypeMap, &GValMaterializer),
-        IndirectSymbolMCID(Mapper.registerAlternateMappingContext(
-            IndirectSymbolValueMap, &LValMaterializer)) {
+        IndirectSymbolMCID(
+            Mapper.registerAlternateMappingContext(&LValMaterializer)) {
     ValueMap.getMDMap() = std::move(SharedMDs);
     for (GlobalValue *GV : ValuesToLink)
       maybeAdd(GV);
     if (IsPerformingImport)
       prepareCompileUnitsForImport();
   }
   ~IRLinker() { SharedMDs = std::move(*ValueMap.getMDMap()); }
 
Expected<Constant *> IRLinker::linkGlobalValueProto(GlobalValue *SGV,
 
   bool ShouldLink = shouldLink(DGV, *SGV);
 
   // just missing from map
   if (ShouldLink) {
     auto I = ValueMap.find(SGV);
     if (I != ValueMap.end())
       return cast<Constant>(I->second);
-
-    I = IndirectSymbolValueMap.find(SGV);
-    if (I != IndirectSymbolValueMap.end())
-      return cast<Constant>(I->second);
   }
 
   if (!ShouldLink && ForIndirectSymbol)
     DGV = nullptr;
 
   // Handle the ultra special appending linkage case first.
   if (SGV->hasAppendingLinkage() || (DGV && DGV->hasAppendingLinkage()))
     return linkAppendingVarProto(cast_or_null<GlobalVariable>(DGV),
Error IRLinker::run() {
   computeTypeMapping();
 
   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())
+    if (ValueMap.find(GV) != ValueMap.end())
       continue;
 
     assert(!GV->isDeclaration());
     Mapper.mapValue(*GV);
     if (FoundError)
       return std::move(*FoundError);
     flushRAUWWorklist();
   }

llvm/lib/Transforms/Utils/ValueMapper.cpp

struct WorklistEntry {
   union {
     GVInitTy GVInit;
     AppendingGVTy AppendingGV;
     GlobalIndirectSymbolTy GlobalIndirectSymbol;
     Function *RemapF;
   } Data;
 };
 
-struct MappingContext {
-  ValueToValueMapTy *VM;
-  ValueMaterializer *Materializer = nullptr;
-
-  /// Construct a MappingContext with a value map and materializer.
-  explicit MappingContext(ValueToValueMapTy &VM,
-                          ValueMaterializer *Materializer = nullptr)
-      : VM(&VM), Materializer(Materializer) {}
-};
-
 class Mapper {
   friend class MDNodeMapper;
 
-#ifndef NDEBUG
-  DenseSet<GlobalValue *> AlreadyScheduled;
-#endif
-
   RemapFlags Flags;
   ValueMapTypeRemapper *TypeMapper;
+  ValueToValueMapTy &VM;
   unsigned CurrentMCID = 0;
-  SmallVector<MappingContext, 2> MCs;
+  SmallVector<ValueMaterializer *, 2> MCs;
   SmallVector<WorklistEntry, 4> Worklist;
   SmallVector<DelayedBasicBlock, 1> DelayedBBs;
   SmallVector<Constant *, 16> AppendingInits;
 
 public:
   Mapper(ValueToValueMapTy &VM, RemapFlags Flags,
          ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer)
-      : Flags(Flags), TypeMapper(TypeMapper),
-        MCs(1, MappingContext(VM, Materializer)) {}
+      : Flags(Flags), TypeMapper(TypeMapper), VM(VM), MCs(1, Materializer) {}
 
   /// ValueMapper should explicitly call \a flush() before destruction.
   ~Mapper() { assert(!hasWorkToDo() && "Expected to be flushed"); }
 
   bool hasWorkToDo() const { return !Worklist.empty(); }
 
   unsigned
-  registerAlternateMappingContext(ValueToValueMapTy &VM,
-                                  ValueMaterializer *Materializer = nullptr) {
-    MCs.push_back(MappingContext(VM, Materializer));
+  registerAlternateMappingContext(ValueMaterializer *Materializer = nullptr) {
+    MCs.push_back(Materializer);
     return MCs.size() - 1;
   }
 
   void addFlags(RemapFlags Flags);
 
   void remapGlobalObjectMetadata(GlobalObject &GO);
 
   Value *mapValue(const Value *V);
public:
 
   void flush();
 
 private:
   void mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
                             bool IsOldCtorDtor,
                             ArrayRef<Constant *> NewMembers);
 
-  ValueToValueMapTy &getVM() { return *MCs[CurrentMCID].VM; }
-  ValueMaterializer *getMaterializer() { return MCs[CurrentMCID].Materializer; }
+  ValueToValueMapTy &getVM() { return VM; }
+  ValueMaterializer *getMaterializer() { return MCs[CurrentMCID]; }
 
   Value *mapBlockAddress(const BlockAddress &BA);
 
   /// Map metadata that doesn't require visiting operands.
   Optional<Metadata *> mapSimpleMetadata(const Metadata *MD);
 
   Metadata *mapToMetadata(const Metadata *Key, Metadata *Val);
   Metadata *mapToSelf(const Metadata *MD);
void Mapper::mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
   }
 
   GV.setInitializer(ConstantArray::get(
       cast<ArrayType>(GV.getType()->getElementType()), Elements));
 }
 
 void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
                                           unsigned MCID) {
-  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
   assert(MCID < MCs.size() && "Invalid mapping context");
 
   WorklistEntry WE;
   WE.Kind = WorklistEntry::MapGlobalInit;
   WE.MCID = MCID;
   WE.Data.GVInit.GV = &GV;
   WE.Data.GVInit.Init = &Init;
   Worklist.push_back(WE);
 }
 
 void Mapper::scheduleMapAppendingVariable(GlobalVariable &GV,
                                           Constant *InitPrefix,
                                           bool IsOldCtorDtor,
                                           ArrayRef<Constant *> NewMembers,
                                           unsigned MCID) {
-  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
   assert(MCID < MCs.size() && "Invalid mapping context");
 
   WorklistEntry WE;
   WE.Kind = WorklistEntry::MapAppendingVar;
   WE.MCID = MCID;
   WE.Data.AppendingGV.GV = &GV;
   WE.Data.AppendingGV.InitPrefix = InitPrefix;
   WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
   WE.AppendingGVNumNewMembers = NewMembers.size();
   Worklist.push_back(WE);
   AppendingInits.append(NewMembers.begin(), NewMembers.end());
 }
 
 void Mapper::scheduleMapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS,
                                              Constant &Target, unsigned MCID) {
-  assert(AlreadyScheduled.insert(&GIS).second && "Should not reschedule");
   assert(MCID < MCs.size() && "Invalid mapping context");
 
   WorklistEntry WE;
   WE.Kind = WorklistEntry::MapGlobalIndirectSymbol;
   WE.MCID = MCID;
   WE.Data.GlobalIndirectSymbol.GIS = &GIS;
   WE.Data.GlobalIndirectSymbol.Target = &Target;
   Worklist.push_back(WE);
 }
 
 void Mapper::scheduleRemapFunction(Function &F, unsigned MCID) {
-  assert(AlreadyScheduled.insert(&F).second && "Should not reschedule");
   assert(MCID < MCs.size() && "Invalid mapping context");
 
   WorklistEntry WE;
   WE.Kind = WorklistEntry::RemapFunction;
   WE.MCID = MCID;
   WE.Data.RemapF = &F;
   Worklist.push_back(WE);
 }

 ValueMapper::ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags,
                          ValueMapTypeRemapper *TypeMapper,
                          ValueMaterializer *Materializer)
     : pImpl(new Mapper(VM, Flags, TypeMapper, Materializer)) {}
 
 ValueMapper::~ValueMapper() { delete getAsMapper(pImpl); }
 
 unsigned
-ValueMapper::registerAlternateMappingContext(ValueToValueMapTy &VM,
-                                             ValueMaterializer *Materializer) {
-  return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
+ValueMapper::registerAlternateMappingContext(ValueMaterializer *Materializer) {
+  return getAsMapper(pImpl)->registerAlternateMappingContext(Materializer);
 }
 
 void ValueMapper::addFlags(RemapFlags Flags) {
   FlushingMapper(pImpl)->addFlags(Flags);
 }
 
 Value *ValueMapper::mapValue(const Value &V) {
   return FlushingMapper(pImpl)->mapValue(&V);

llvm/test/Linker/global-alias-value-map.ll

+; RUN: llvm-link %s -o /dev/null
+
+@gv0 = constant i8* bitcast (void ()* @function to i8*)
+
+@alias = alias i32, getelementptr (i32, i32* getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @gv1, i32 0, i32 0), i32 0)
+
+@gv1 = constant <{ i32, i32 }> <{ i32 0, i32 trunc (i64 sub (i64 ptrtoint (<{ i32, i32 }>* @gv2 to i64), i64 ptrtoint (i32* getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @gv1, i32 0, i32 0) to i64)) to i32)}>
+
+@gv2 = constant <{ i32, i32 }> <{ i32 0, i32 0 }>
+
+define linkonce_odr hidden void @function() {
+  %1 = call i8** @external(i32* @alias)
+  ret void
+}
+
+declare i8** @external(i32*)