IRMover: Avoid accidentally mapping types from the destination module (PR30799)

[hans]

Summary

During an LTO build of Chromium, I ran into the "mapping to a source type" assert.

During Module linking, it's possible for SrcM->getIdentifiedStructTypes(); to return types that are actually defined in the destination module (DstM). Depending on how the bitcode file was read, getIdentifiedStructTypes() might do a walk over all values, including metadata nodes, looking for types. In my case, a debug info metadata node was shared between the two modules, and it referred to a type defined in the destination module (see test case).

[inglorion]

test/LTO/X86/type-mapping-bug.ll

23 ↗

(On Diff #76621)

This explains what happens without the above change to IRMover.cpp, but it doesn't explain what happens after you make that change and why that behavior is correct. Could you add that information here? Other than that, looks good - thanks for fixing this!

[pcc]

test/LTO/X86/type-mapping-bug.ll

3 ↗

(On Diff #76621)

Would it be possible to write this test with llvm-link instead of llvm-lto?

[mehdi_amini]

test/LTO/X86/type-mapping-bug.ll

3 ↗

(On Diff #76621)

Likely not. I fixed a similar issues in r280599 / D23841 and it requires the LLVMContext to be initialized with ODR type uniquing, which only happens in LTO. (We may be able to add an option to llvm-link, but we can't really test it as it is supposed to be "NFC").

[hans]

test/LTO/X86/type-mapping-bug.ll

3 ↗

(On Diff #76621)

Sadly, I wasn't able to reproduce this with llvm-link, only with llvm-lto.

Some code path must be different. While I think it should be possible to trigger the same problem there, I couldn't figure out how to do it.

23 ↗

(On Diff #76621)

Thanks, updating the comment.

[hans]

Updating comment.

[hans]

test/LTO/X86/type-mapping-bug.ll

3 ↗

(On Diff #76621)

Thanks for the pointer! Yes, that must be it.
I'm kind of happy to see someone else has run into this. I thought I was about to go mad debugging it :-)

[mehdi_amini]

During Module linking, it's possible for SrcM->getIdentifiedStructTypes(); to return types that are actually defined in the destination module (DstM).

That's very surprising to me and I'd like to understand it a bit more (We're supposed to only ODR metadata).
getIdentifiedStructTypes() isn't even documented in the Module header unfortunately. It is not clear off-hand it the issue should be handled in the IRMover or in getIdentifiedStructTypes itself.

[mehdi_amini]

test/LTO/X86/type-mapping-bug.ll

3 ↗

(On Diff #76621)

ODR type uniquing was introduced in the 3.9 release, so it can still be a bit rough around the edges...
(I'm debugging an infinite recursion in metadata in the IRMover when linking Webkit with ThinLTO these days)

[hans]

In D26212#585258, @mehdi_amini wrote:

During Module linking, it's possible for SrcM->getIdentifiedStructTypes(); to return types that are actually defined in the destination module (DstM).

That's very surprising to me and I'd like to understand it a bit more (We're supposed to only ODR metadata).

Yes, but the metadata can refer to values, which getIdentifiedStructTypes() will walk when hunting for types. It was very surprising to me too :-)

getIdentifiedStructTypes() isn't even documented in the Module header unfortunately. It is not clear off-hand it the issue should be handled in the IRMover or in getIdentifiedStructTypes itself.

I'm not sure how we'd change getIdentifiedStructTypes() though. Once we've ODR'd the metadata, the module now refers to a value with this type, and it makes sense that getIdentifiedStructTypes() finds it.

[mehdi_amini]

getIdentifiedStructTypes() isn't even documented in the Module header unfortunately. It is not clear off-hand it the issue should be handled in the IRMover or in getIdentifiedStructTypes itself.

I'm not sure how we'd change getIdentifiedStructTypes() though. Once we've ODR'd the metadata, the module now refers to a value with this type, and it makes sense that getIdentifiedStructTypes() finds it.

To begin with: in what situation walking the metadata graph can find a named typed that can't be found by walking only the IR?

[inglorion]

Thanks for updating the comment, @hans. I'll give @mehdi_amini some time to look into getIdentifiedStructTypes() and whether or not it is supposed to be this way. For what it's worth, my first instinct was that it shouldn't give us the types that this diff skips over, but after a cursory glance at the implementation (since there is no documentation), I concluded that this is ok. There may be a follow-up diff in our future to clarify the intended behavior of getIdentifiedStructTypes()...

[hans]

In D26212#585290, @mehdi_amini wrote:

getIdentifiedStructTypes() isn't even documented in the Module header unfortunately. It is not clear off-hand it the issue should be handled in the IRMover or in getIdentifiedStructTypes itself.

I'm not sure how we'd change getIdentifiedStructTypes() though. Once we've ODR'd the metadata, the module now refers to a value with this type, and it makes sense that getIdentifiedStructTypes() finds it.

To begin with: in what situation walking the metadata graph can find a named typed that can't be found by walking only the IR?

I think my test case shows that: when the DI node looks like this:

!11 = !DITemplateValueParameter(type: !12, value: %Tricky.1* bitcast (i8* @templateValueParam to %Tricky.1*))

The non-MD IR doesn't refer to %Tricky.1, but this node has a constant expression that does.

TypeFinder::incorporateMDNode does:

if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
  incorporateValue(C->getValue());

which hits:

/// incorporateValue - This method is used to walk operand lists finding types
/// hiding in constant expressions and other operands that won't be walked in
/// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
/// all explicitly enumerated.
void TypeFinder::incorporateValue(const Value *V) {

[hans]

Mehdi: ping?

[mehdi_amini]

LGTM.

I looked into how to put named type on Modules, but that has large implication (for example cloning a function from one module to another would now require special handling to remap named types).
Also before LLVM 3.0 type didn't have name, the names were kept on the side in a hash table on the module, having the current behavior has been a careful choice: http://blog.llvm.org/2011/11/llvm-30-type-system-rewrite.html

lib/Linker/IRMover.cpp

707 ↗

(On Diff #76637)

some of which get linked by name add when ODR Type Uniquing is enabled on the Context

[mehdi_amini]

Ping?

I think this should go in 3.9.1, so it'd be great to land it ASAP.

[hans]

In D26212#599346, @mehdi_amini wrote:

Ping?

I think this should go in 3.9.1, so it'd be great to land it ASAP.

Sorry, I got distracted by other stuff. Committing now.

As for 3.9.1, we should ask Tom (now cc'd) what he thinks.

lib/Linker/IRMover.cpp

707 ↗

(On Diff #76637)

Done.

llvm/trunk/lib/Linker/IRMover.cpp

void IRLinker::computeTypeMapping() {
   // At this point, the destination module may have a type "%foo = { i32 }" for
   // example.  When the source module got loaded into the same LLVMContext, if
   // it had the same type, it would have been renamed to "%foo.42 = { i32 }".
   std::vector<StructType *> Types = SrcM->getIdentifiedStructTypes();
   for (StructType *ST : Types) {
     if (!ST->hasName())
       continue;
 
+    if (TypeMap.DstStructTypesSet.hasType(ST)) {
+      // This is actually a type from the destination module.
+      // getIdentifiedStructTypes() can have found it by walking debug info
+      // metadata nodes, some of which get linked by name when ODR Type Uniquing
+      // is enabled on the Context, from the source to the destination module.
+      continue;
+    }
+
     // Check to see if there is a dot in the name followed by a digit.
     size_t DotPos = ST->getName().rfind('.');
     if (DotPos == 0 || DotPos == StringRef::npos ||
         ST->getName().back() == '.' ||
         !isdigit(static_cast<unsigned char>(ST->getName()[DotPos + 1])))
       continue;
 
     // Check to see if the destination module has a struct with the prefix name.

llvm/trunk/test/LTO/X86/Inputs/type-mapping-src.ll

+target triple = "x86_64-pc-windows-msvc18.0.0"
+
+%SrcType = type { i8 }
+@x = external global %SrcType
+
+%CommonStruct = type opaque
+@bar = internal global %CommonStruct* null, !dbg !0
+
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!12}
+!0 = distinct !DIGlobalVariable(name: "bar", linkageName: "bar", scope: !1, file: !2, line: 2, type: !5, isLocal: false, isDefinition: true)
+!1 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !2, producer: "", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !3, globals: !4)
+!2 = !DIFile(filename: "b", directory: "/")
+!3 = !{}
+!4 = !{!0}
+!5 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !6, size: 64)
+!6 = !DICompositeType(tag: DW_TAG_structure_type, name: "S", file: !2, line: 1, flags: DIFlagFwdDecl, identifier: ".?AUS@@")
+!12 = !{i32 2, !"Debug Info Version", i32 3}
+

llvm/trunk/test/LTO/X86/type-mapping-bug.ll

+; RUN: llvm-as -o %t.dst.bc %s
+; RUN: llvm-as -o %t.src.bc %S/Inputs/type-mapping-src.ll
+; RUN: llvm-lto %t.dst.bc %t.src.bc -o=/dev/null
+
+target triple = "x86_64-pc-windows-msvc18.0.0"
+
+; @x in Src will be linked with this @x, causing SrcType in Src to be mapped
+; to %DstType.
+%DstType = type { i8 }
+@x = global %DstType zeroinitializer
+
+; The Src module will re-use our DINode for this type.
+%CommonStruct = type { i32 }
+@foo = internal global %CommonStruct zeroinitializer, !dbg !5
+
+; That DINode will refer to this value, casted to %Tricky.1* (!11),
+; which will then show up in Src's getIdentifiedStructTypes().
+@templateValueParam = global i8 zeroinitializer
+
+; Because of the names, we would try to map %Tricky.1 to %Tricky --
+; mapping a Dst type to another Dst type! This would assert when
+; getting a mapping from %DstType, which has previously used as
+; a destination type. Since these types are not in the source module,
+; there should be no attempt to create a mapping involving them;
+; both types should be left as they are.
+%Tricky = type opaque
+%Tricky.1 = type { %DstType* }
+
+
+; Mark %Tricky used.
+@use = global %Tricky* zeroinitializer
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!19}
+!1 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !2, producer: "", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !3, globals: !4)
+!2 = !DIFile(filename: "a", directory: "/")
+!3 = !{}
+!4 = !{!5}
+!5 = distinct !DIGlobalVariable(name: "foo", linkageName: "foo", scope: !1, file: !2, line: 5, type: !6, isLocal: false, isDefinition: true)
+!6 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "S", file: !2, line: 5, size: 8, elements: !7, identifier: ".?AUS@@")
+!7 = !{!8}
+!8 = !DIDerivedType(tag: DW_TAG_inheritance, scope: !6, baseType: !9)
+!9 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "Template<&x>", file: !2, line: 3, size: 8, elements: !3, templateParams: !10, identifier: ".?AU?$Template@$1?x@@3UX@@A@@")
+!10 = !{!11}
+
+!11 = !DITemplateValueParameter(type: !12, value: %Tricky.1* bitcast (i8* @templateValueParam to %Tricky.1*))
+
+!12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !13, size: 64)
+!13 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "X", file: !2, line: 1, size: 8, elements: !3, identifier: ".?AUX@@")
+!19 = !{i32 2, !"Debug Info Version", i32 3}