Page MenuHomePhabricator

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

Authored by steven_wu on Mar 29 2021, 3:35 PM.

Details

Summary

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

This doesn't work for comdat yet.

Diff Detail

Unit TestsFailed

TimeTest
50 msx64 debian > LLVM.LTO/Resolution/X86::comdat.ll
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/llvm-project/build/bin/llvm-as /mnt/disks/ssd0/agent/llvm-project/llvm/test/LTO/Resolution/X86/comdat.ll -o /mnt/disks/ssd0/agent/llvm-project/build/test/LTO/Resolution/X86/Output/comdat.ll.tmp.o
20 msx64 debian > LLVM.Linker::comdat16.ll
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/llvm-project/build/bin/llvm-link -S -o - /mnt/disks/ssd0/agent/llvm-project/llvm/test/Linker/comdat16.ll /mnt/disks/ssd0/agent/llvm-project/llvm/test/Linker/Inputs/comdat16.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Linker/comdat16.ll
110 msx64 windows > LLVM.LTO/Resolution/X86::comdat.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\llvm-as.exe C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\LTO\Resolution\X86\comdat.ll -o C:\ws\w16c2-1\llvm-project\premerge-checks\build\test\LTO\Resolution\X86\Output\comdat.ll.tmp.o
50 msx64 windows > LLVM.Linker::comdat16.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\llvm-link.exe -S -o - C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\Linker\comdat16.ll C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\Linker/Inputs/comdat16.ll | c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\Linker\comdat16.ll

Event Timeline

steven_wu created this revision.Mar 29 2021, 3:35 PM
steven_wu requested review of this revision.Mar 29 2021, 3:35 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 29 2021, 3:35 PM

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

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 added inline comments.Mar 29 2021, 3:50 PM
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 updated this revision to Diff 334014.Mar 29 2021, 4:42 PM

Update testcase.

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

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

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

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 added inline comments.Apr 27 2021, 5:22 PM
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

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

I'll post an alternate patch in a moment.

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

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

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 abandoned this revision.Apr 29 2021, 8:55 AM

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

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