Linking opaque types

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Linking opaque types

Anton Lokhmotov
There is an issue with representing opaque types in LLVM IR modules: if two
modules are using the same opaque type (which is only going to be
specialised at some later stage), it is only identified by its name.  But
the current module linker "resolves" this as if there is a name clash, and
one of that opaque types is renamed.  It contradicts an intuitively expected
identifier behaviour and makes it literally impossible to use opaque types
for identifying underspecified types across different modules.

Our position is that structure type names should be treated as proper
identifiers, as long as types are structurally equivalent, and all the
opaque types are structurally equivalent unless they're specialised.

Could anyone familiar with the linker comment please?

Many thanks,
Anton.




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Talin-3
On Mon, Jul 25, 2011 at 8:52 AM, Anton Lokhmotov <[hidden email]> wrote:
There is an issue with representing opaque types in LLVM IR modules: if two
modules are using the same opaque type (which is only going to be
specialised at some later stage), it is only identified by its name.  But
the current module linker "resolves" this as if there is a name clash, and
one of that opaque types is renamed.  It contradicts an intuitively expected
identifier behaviour and makes it literally impossible to use opaque types
for identifying underspecified types across different modules.

Our position is that structure type names should be treated as proper
identifiers, as long as types are structurally equivalent, and all the
opaque types are structurally equivalent unless they're specialised.

Could anyone familiar with the linker comment please?

This is the problem I am having as well.
 
Many thanks,
Anton.




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Chris Lattner-2
In reply to this post by Anton Lokhmotov
On Jul 25, 2011, at 8:52 AM, Anton Lokhmotov wrote:

> There is an issue with representing opaque types in LLVM IR modules: if two
> modules are using the same opaque type (which is only going to be
> specialised at some later stage), it is only identified by its name.  But
> the current module linker "resolves" this as if there is a name clash, and
> one of that opaque types is renamed.  It contradicts an intuitively expected
> identifier behaviour and makes it literally impossible to use opaque types
> for identifying underspecified types across different modules.
>
> Our position is that structure type names should be treated as proper
> identifiers, as long as types are structurally equivalent, and all the
> opaque types are structurally equivalent unless they're specialised.
>
> Could anyone familiar with the linker comment please?

Hi Anton,

In the new-world-order, the identity of a named structure type is based on the name, but just like before, types have no linkage.

This means that when linking:

%A = type { i32 }
and
%A = type opaque

that these two types are not necessarily unioned.  There are several reasons for this, including that it is completely valid IR to link these two modules:

%A = type { i32 }
@G = external global %A
... and ...
%A = type { float}
%G = global %A { float 1.0 }

Even though the two globals *do* have type linkage and the types are contradictory.


To handle the fact that types do not (and can not, at least as long as we intend to support obscure languages like "C" :) have linkage, the the linker uses a "best effort" approach.  It attempts to merge types and rewrite IR to use the merged types where it can, but it doesn't make any guarantees.

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Talin-3
On Mon, Jul 25, 2011 at 9:36 PM, Chris Lattner <[hidden email]> wrote:
On Jul 25, 2011, at 8:52 AM, Anton Lokhmotov wrote:
> There is an issue with representing opaque types in LLVM IR modules: if two
> modules are using the same opaque type (which is only going to be
> specialised at some later stage), it is only identified by its name.  But
> the current module linker "resolves" this as if there is a name clash, and
> one of that opaque types is renamed.  It contradicts an intuitively expected
> identifier behaviour and makes it literally impossible to use opaque types
> for identifying underspecified types across different modules.
>
> Our position is that structure type names should be treated as proper
> identifiers, as long as types are structurally equivalent, and all the
> opaque types are structurally equivalent unless they're specialised.
>
> Could anyone familiar with the linker comment please?

Hi Anton,

In the new-world-order, the identity of a named structure type is based on the name, but just like before, types have no linkage.

This means that when linking:

%A = type { i32 }
and
%A = type opaque

that these two types are not necessarily unioned.  There are several reasons for this, including that it is completely valid IR to link these two modules:

%A = type { i32 }
@G = external global %A
... and ...
%A = type { float}
%G = global %A { float 1.0 }

Even though the two globals *do* have type linkage and the types are contradictory.


To handle the fact that types do not (and can not, at least as long as we intend to support obscure languages like "C" :) have linkage, the the linker uses a "best effort" approach.  It attempts to merge types and rewrite IR to use the merged types where it can, but it doesn't make any guarantees.

I want to add an additional detail into this mix: That the frontend generating all of this code is making a best effort to insure that the types are in fact compatible -- and it isn't working.

One of the painful things about the old type system was that you were forced to specify every type in excruciating detail - so if I had a type A which had a data member of type B*, I had to include the complete definition of B in my module, even if the module never dereferenced that field - because otherwise my definition of A wouldn't be compatible with another module's definition of A. And if B contained a C* which in turn contained a D*, all of those had to be specified as well, even if the module never used types C or D.

One of the benefits I had hoped to get out of the new system was to be able to "forward declare" a type without giving a definition for it - so if I have my definition of A containing a B*, I only need to declare B as an opaque type instead of giving all the details.

However, it sounds like what you are saying is that if I do this, I can't depend on the linker being able to merge the definition of forward-declared B with fully-specified B, nor A from module 1 (containing forward-declared B*) with A from module 2 (containing fully-specified B*).

If that's true, then it means that we're back to the case where every type has to be fully defined down to the leaf level.

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Chris Lattner-2
On Jul 25, 2011, at 10:58 PM, Talin wrote:
To handle the fact that types do not (and can not, at least as long as we intend to support obscure languages like "C" :) have linkage, the the linker uses a "best effort" approach.  It attempts to merge types and rewrite IR to use the merged types where it can, but it doesn't make any guarantees.

I want to add an additional detail into this mix: That the frontend generating all of this code is making a best effort to insure that the types are in fact compatible -- and it isn't working.

One of the painful things about the old type system was that you were forced to specify every type in excruciating detail - so if I had a type A which had a data member of type B*, I had to include the complete definition of B in my module, even if the module never dereferenced that field - because otherwise my definition of A wouldn't be compatible with another module's definition of A. And if B contained a C* which in turn contained a D*, all of those had to be specified as well, even if the module never used types C or D.

One of the benefits I had hoped to get out of the new system was to be able to "forward declare" a type without giving a definition for it - so if I have my definition of A containing a B*, I only need to declare B as an opaque type instead of giving all the details.

However, it sounds like what you are saying is that if I do this, I can't depend on the linker being able to merge the definition of forward-declared B with fully-specified B, nor A from module 1 (containing forward-declared B*) with A from module 2 (containing fully-specified B*).

If that's true, then it means that we're back to the case where every type has to be fully defined down to the leaf level.

I'm not sure what you mean.  LLVM is perfectly fine with opaque structs so long as you don't "deference" them, GEP into them, need their size, etc.

-Chris


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Talin-3
On Mon, Jul 25, 2011 at 11:16 PM, Chris Lattner <[hidden email]> wrote:
On Jul 25, 2011, at 10:58 PM, Talin wrote:
To handle the fact that types do not (and can not, at least as long as we intend to support obscure languages like "C" :) have linkage, the the linker uses a "best effort" approach.  It attempts to merge types and rewrite IR to use the merged types where it can, but it doesn't make any guarantees.

I want to add an additional detail into this mix: That the frontend generating all of this code is making a best effort to insure that the types are in fact compatible -- and it isn't working.

One of the painful things about the old type system was that you were forced to specify every type in excruciating detail - so if I had a type A which had a data member of type B*, I had to include the complete definition of B in my module, even if the module never dereferenced that field - because otherwise my definition of A wouldn't be compatible with another module's definition of A. And if B contained a C* which in turn contained a D*, all of those had to be specified as well, even if the module never used types C or D.

One of the benefits I had hoped to get out of the new system was to be able to "forward declare" a type without giving a definition for it - so if I have my definition of A containing a B*, I only need to declare B as an opaque type instead of giving all the details.

However, it sounds like what you are saying is that if I do this, I can't depend on the linker being able to merge the definition of forward-declared B with fully-specified B, nor A from module 1 (containing forward-declared B*) with A from module 2 (containing fully-specified B*).

If that's true, then it means that we're back to the case where every type has to be fully defined down to the leaf level.

I'm not sure what you mean.  LLVM is perfectly fine with opaque structs so long as you don't "deference" them, GEP into them, need their size, etc.

Let me try with another example: Let's say Module A and Module B both import class Exception. Class Exception has a "message" field which is a pointer to type String. Now, let's say Module A dereferences the Exception.message field by printing the message. The compiler sees this dereference, and automatically loads the String module. Type String is added to Module A as a fully-resolved struct type.

In Module B, on the other hand, there is no dereference of the message field. So the compiler includes the definition of Exception, but the definition of String is opaque, because no code in Module B ever referred to any of the fields of class String. In fact the compiler never even loaded the definition of String because it wasn't needed.

Now we attempt to link together a bunch of modules including A and B. The linker sees that there are two types named "Exception" and renamed one of them. It also sees that there are two types named "String" and renames one of those as well. At this point, the linker fails because of a type mismatch. At least, this is the behavior that I am seeing.

--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Chris Lattner-2

On Jul 26, 2011, at 8:11 AM, Talin wrote:


If that's true, then it means that we're back to the case where every type has to be fully defined down to the leaf level.

I'm not sure what you mean.  LLVM is perfectly fine with opaque structs so long as you don't "deference" them, GEP into them, need their size, etc.

Let me try with another example: Let's say Module A and Module B both import class Exception. Class Exception has a "message" field which is a pointer to type String. Now, let's say Module A dereferences the Exception.message field by printing the message. The compiler sees this dereference, and automatically loads the String module. Type String is added to Module A as a fully-resolved struct type.

In Module B, on the other hand, there is no dereference of the message field. So the compiler includes the definition of Exception, but the definition of String is opaque, because no code in Module B ever referred to any of the fields of class String. In fact the compiler never even loaded the definition of String because it wasn't needed.

Now we attempt to link together a bunch of modules including A and B. The linker sees that there are two types named "Exception" and renamed one of them. It also sees that there are two types named "String" and renames one of those as well. At this point, the linker fails because of a type mismatch. At least, this is the behavior that I am seeing.

What do you mean "the linker fails"? Type mismatches should not cause the linker to fail.  In any case, this example should link, please provide a minimal example of two .ll files that repros what you're seeing with llvm-link.  Thanks,

-Chris

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Talin-3


On Tue, Jul 26, 2011 at 11:01 PM, Chris Lattner <[hidden email]> wrote:

On Jul 26, 2011, at 8:11 AM, Talin wrote:


If that's true, then it means that we're back to the case where every type has to be fully defined down to the leaf level.

I'm not sure what you mean.  LLVM is perfectly fine with opaque structs so long as you don't "deference" them, GEP into them, need their size, etc.

Let me try with another example: Let's say Module A and Module B both import class Exception. Class Exception has a "message" field which is a pointer to type String. Now, let's say Module A dereferences the Exception.message field by printing the message. The compiler sees this dereference, and automatically loads the String module. Type String is added to Module A as a fully-resolved struct type.

In Module B, on the other hand, there is no dereference of the message field. So the compiler includes the definition of Exception, but the definition of String is opaque, because no code in Module B ever referred to any of the fields of class String. In fact the compiler never even loaded the definition of String because it wasn't needed.

Now we attempt to link together a bunch of modules including A and B. The linker sees that there are two types named "Exception" and renamed one of them. It also sees that there are two types named "String" and renames one of those as well. At this point, the linker fails because of a type mismatch. At least, this is the behavior that I am seeing.

What do you mean "the linker fails"? Type mismatches should not cause the linker to fail.  In any case, this example should link, please provide a minimal example of two .ll files that repros what you're seeing with llvm-link.  Thanks,

It's llvm-ld that asserts here:

Assertion failed: (N < NumContainedTys && "Element number out of range!"), function getElementType, file /Users/talin/Projects/llvm/include/llvm/DerivedTypes.h, line 268.

5  0x0000000100158f27 in llvm::StructType::getElementType (this=0x10180f310, N=0) at DerivedTypes.h:268
#6  0x00000001001b8b54 in llvm::BitcodeReader::ParseConstants (this=0x101813800) at /Users/talin/Projects/llvm/lib/Bitcode/Reader/BitcodeReader.cpp:1256
#7  0x00000001001be481 in llvm::BitcodeReader::ParseModule (this=0x101813800) at /Users/talin/Projects/llvm/lib/Bitcode/Reader/BitcodeReader.cpp:1578
#8  0x00000001001bf8fb in llvm::BitcodeReader::ParseBitcodeInto (this=0x101813800, M=0x101605dd0) at /Users/talin/Projects/llvm/lib/Bitcode/Reader/BitcodeReader.cpp:1848
#9  0x00000001001bf9ea in llvm::getLazyBitcodeModule (Buffer=0x10181b800, Context=@0x101600290, ErrMsg=0x7fff5fbfc8f0) at /Users/talin/Projects/llvm/lib/Bitcode/Reader/BitcodeReader.cpp:2776
#10 0x00000001001bfa7b in llvm::ParseBitcodeFile (Buffer=0x10181b800, Context=@0x101600290, ErrMsg=0x7fff5fbfc8f0) at /Users/talin/Projects/llvm/lib/Bitcode/Reader/BitcodeReader.cpp:2792
#11 0x000000010006cf52 in llvm::Linker::LoadObject (this=0x7fff5fbfcd50, FN=@0x101801a28) at /Users/talin/Projects/llvm/lib/Linker/Linker.cpp:107
#12 0x000000010006494e in llvm::Linker::LinkInFile (this=0x7fff5fbfcd50, File=@0x101801a28, is_native=@0x7fff5fbfcb7f) at /Users/talin/Projects/llvm/lib/Linker/LinkItems.cpp:199
#13 0x0000000100064c5e in llvm::Linker::LinkInFiles (this=0x7fff5fbfcd50, Files=@0x7fff5fbfce30) at /Users/talin/Projects/llvm/lib/Linker/LinkItems.cpp:238
#14 0x0000000100007c1f in main (argc=130, argv=0x7fff5fbfd1f0, envp=0x7fff5fbfd608) at /Users/talin/Projects/llvm/tools/llvm-ld/llvm-ld.cpp:582

I'll get you a reproducible test case in the next day or so.
 
-Chris

--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Chris Lattner-2

On Jul 27, 2011, at 12:41 AM, Talin wrote:

What do you mean "the linker fails"? Type mismatches should not cause the linker to fail.  In any case, this example should link, please provide a minimal example of two .ll files that repros what you're seeing with llvm-link.  Thanks,

It's llvm-ld that asserts here:

Assertion failed: (N < NumContainedTys && "Element number out of range!"), function getElementType, file /Users/talin/Projects/llvm/include/llvm/DerivedTypes.h, line 268.


Sounds like a bug, thanks.

-Chris

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Talin-3
On Wed, Jul 27, 2011 at 8:02 AM, Chris Lattner <[hidden email]> wrote:

On Jul 27, 2011, at 12:41 AM, Talin wrote:

What do you mean "the linker fails"? Type mismatches should not cause the linker to fail.  In any case, this example should link, please provide a minimal example of two .ll files that repros what you're seeing with llvm-link.  Thanks,

It's llvm-ld that asserts here:

Assertion failed: (N < NumContainedTys && "Element number out of range!"), function getElementType, file /Users/talin/Projects/llvm/include/llvm/DerivedTypes.h, line 268.


Sounds like a bug, thanks.

I figured out the problem - it was a case where a static constant had an unnamed struct type:

%tart.text.encodings.UTF8 = type opaque

@tart.text.encodings.Codecs.UTF_8 = global %tart.text.encodings.UTF8 { %tart.core.Object { %tart.core.TypeInfoBlock* undef, i64 0 }, i32 1 }

That being said - I would feel safer if invalid IR like this would assert at the time it was generated, rather than causing an error when attempting to read in the file. 

-Chris



--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Linking opaque types

Talin-3
In reply to this post by Chris Lattner-2
I'm not sure what you mean.  LLVM is perfectly fine with opaque structs so long as you don't "deference" them, GEP into them, need their size, etc.

Now that I've actually got my library to link, let's look at the result - here's a small section of the llvm-dis output (I've sorted the lines to make my point):

%"tart.collections.Collection[tart.core.Attribute]" = type { %"tart.core.Iterable[tart.core.Attribute]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.core.Object]" = type { %"tart.core.Iterable[tart.core.Object]", %tart.core.TypeInfoBlock* }
%"tart.collections.Collection[tart.core.Object].1358" = type { %"tart.core.Iterable[tart.core.Object].1357", %tart.core.TypeInfoBlock.1372* }
%"tart.collections.Collection[tart.core.Object].145" = type { %"tart.core.Iterable[tart.core.Object].144", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.core.Object].1664" = type { %"tart.core.Iterable[tart.core.Object].1663", %tart.core.TypeInfoBlock.1678* }
%"tart.collections.Collection[tart.core.Object].1890" = type { %"tart.core.Iterable[tart.core.Object].1889", %tart.core.TypeInfoBlock.1904* }
%"tart.collections.Collection[tart.core.Object].220" = type { %"tart.core.Iterable[tart.core.Object].219", %tart.core.TypeInfoBlock.234* }
%"tart.collections.Collection[tart.core.Object].32" = type { %"tart.core.Iterable[tart.core.Object].31", %tart.core.TypeInfoBlock.46* }
%"tart.collections.Collection[tart.core.Object].3359" = type { %"tart.core.Iterable[tart.core.Object].3358", %tart.core.TypeInfoBlock.3373* }
%"tart.collections.Collection[tart.core.Object].427" = type { %"tart.core.Iterable[tart.core.Object].426", %tart.core.TypeInfoBlock.441* }
%"tart.collections.Collection[tart.core.Object].454" = type { %"tart.core.Iterable[tart.core.Object].453", %tart.core.TypeInfoBlock.468* }
%"tart.collections.Collection[tart.core.Object].5" = type { %"tart.core.Iterable[tart.core.Object].4", %tart.core.TypeInfoBlock.19* }
%"tart.collections.Collection[tart.core.Object].59" = type { %"tart.core.Iterable[tart.core.Object].58", %tart.core.TypeInfoBlock.73* }
%"tart.collections.Collection[tart.core.Object].716" = type { %"tart.core.Iterable[tart.core.Object].715", %tart.core.TypeInfoBlock.730* }
%"tart.collections.Collection[tart.core.Object].796" = type { %"tart.core.Iterable[tart.core.Object].795", %tart.core.TypeInfoBlock.810* }
%"tart.collections.Collection[tart.core.Object].86" = type { %"tart.core.Iterable[tart.core.Object].85", %tart.core.TypeInfoBlock.100* }
%"tart.collections.Collection[tart.core.String]" = type { %"tart.core.Iterable[tart.core.String]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.core.String|Null]" = type { %"tart.core.Iterable[tart.core.String|Null]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Field]" = type { %"tart.core.Iterable[tart.reflect.Field]", %tart.core.TypeInfoBlock* }
%"tart.collections.Collection[tart.reflect.Field].1361" = type { %"tart.core.Iterable[tart.reflect.Field].1360", %tart.core.TypeInfoBlock.1372* }
%"tart.collections.Collection[tart.reflect.Field].148" = type { %"tart.core.Iterable[tart.reflect.Field].147", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Field].1667" = type { %"tart.core.Iterable[tart.reflect.Field].1666", %tart.core.TypeInfoBlock.1678* }
%"tart.collections.Collection[tart.reflect.Field].1893" = type { %"tart.core.Iterable[tart.reflect.Field].1892", %tart.core.TypeInfoBlock.1904* }
%"tart.collections.Collection[tart.reflect.Field].223" = type { %"tart.core.Iterable[tart.reflect.Field].222", %tart.core.TypeInfoBlock.234* }
%"tart.collections.Collection[tart.reflect.Field].3362" = type { %"tart.core.Iterable[tart.reflect.Field].3361", %tart.core.TypeInfoBlock.3373* }
%"tart.collections.Collection[tart.reflect.Field].35" = type { %"tart.core.Iterable[tart.reflect.Field].34", %tart.core.TypeInfoBlock.46* }
%"tart.collections.Collection[tart.reflect.Field].430" = type { %"tart.core.Iterable[tart.reflect.Field].429", %tart.core.TypeInfoBlock.441* }
%"tart.collections.Collection[tart.reflect.Field].457" = type { %"tart.core.Iterable[tart.reflect.Field].456", %tart.core.TypeInfoBlock.468* }
%"tart.collections.Collection[tart.reflect.Field].62" = type { %"tart.core.Iterable[tart.reflect.Field].61", %tart.core.TypeInfoBlock.73* }
%"tart.collections.Collection[tart.reflect.Field].719" = type { %"tart.core.Iterable[tart.reflect.Field].718", %tart.core.TypeInfoBlock.730* }
%"tart.collections.Collection[tart.reflect.Field].799" = type { %"tart.core.Iterable[tart.reflect.Field].798", %tart.core.TypeInfoBlock.810* }
%"tart.collections.Collection[tart.reflect.Field].8" = type { %"tart.core.Iterable[tart.reflect.Field].7", %tart.core.TypeInfoBlock.19* }
%"tart.collections.Collection[tart.reflect.Field].89" = type { %"tart.core.Iterable[tart.reflect.Field].88", %tart.core.TypeInfoBlock.100* }
%"tart.collections.Collection[tart.reflect.Method]" = type { %"tart.core.Iterable[tart.reflect.Method]", %tart.core.TypeInfoBlock* }
%"tart.collections.Collection[tart.reflect.Method].1367" = type { %"tart.core.Iterable[tart.reflect.Method].1366", %tart.core.TypeInfoBlock.1372* }
%"tart.collections.Collection[tart.reflect.Method].14" = type { %"tart.core.Iterable[tart.reflect.Method].13", %tart.core.TypeInfoBlock.19* }
%"tart.collections.Collection[tart.reflect.Method].154" = type { %"tart.core.Iterable[tart.reflect.Method].153", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Method].1673" = type { %"tart.core.Iterable[tart.reflect.Method].1672", %tart.core.TypeInfoBlock.1678* }
%"tart.collections.Collection[tart.reflect.Method].1899" = type { %"tart.core.Iterable[tart.reflect.Method].1898", %tart.core.TypeInfoBlock.1904* }
%"tart.collections.Collection[tart.reflect.Method].229" = type { %"tart.core.Iterable[tart.reflect.Method].228", %tart.core.TypeInfoBlock.234* }
%"tart.collections.Collection[tart.reflect.Method].3368" = type { %"tart.core.Iterable[tart.reflect.Method].3367", %tart.core.TypeInfoBlock.3373* }
%"tart.collections.Collection[tart.reflect.Method].41" = type { %"tart.core.Iterable[tart.reflect.Method].40", %tart.core.TypeInfoBlock.46* }
%"tart.collections.Collection[tart.reflect.Method].436" = type { %"tart.core.Iterable[tart.reflect.Method].435", %tart.core.TypeInfoBlock.441* }
%"tart.collections.Collection[tart.reflect.Method].463" = type { %"tart.core.Iterable[tart.reflect.Method].462", %tart.core.TypeInfoBlock.468* }
%"tart.collections.Collection[tart.reflect.Method].68" = type { %"tart.core.Iterable[tart.reflect.Method].67", %tart.core.TypeInfoBlock.73* }
%"tart.collections.Collection[tart.reflect.Method].725" = type { %"tart.core.Iterable[tart.reflect.Method].724", %tart.core.TypeInfoBlock.730* }
%"tart.collections.Collection[tart.reflect.Method].805" = type { %"tart.core.Iterable[tart.reflect.Method].804", %tart.core.TypeInfoBlock.810* }
%"tart.collections.Collection[tart.reflect.Method].95" = type { %"tart.core.Iterable[tart.reflect.Method].94", %tart.core.TypeInfoBlock.100* }
%"tart.collections.Collection[tart.reflect.Module]" = type { %"tart.core.Iterable[tart.reflect.Module]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.NameTable.CompoundName]" = type { %"tart.core.Iterable[tart.reflect.NameTable.CompoundName]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Package]" = type { %"tart.core.Iterable[tart.reflect.Package]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Parameter]" = type { %"tart.core.Iterable[tart.reflect.Parameter]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Property]" = type { %"tart.core.Iterable[tart.reflect.Property]", %tart.core.TypeInfoBlock* }
%"tart.collections.Collection[tart.reflect.Property].11" = type { %"tart.core.Iterable[tart.reflect.Property].10", %tart.core.TypeInfoBlock.19* }
%"tart.collections.Collection[tart.reflect.Property].1364" = type { %"tart.core.Iterable[tart.reflect.Property].1363", %tart.core.TypeInfoBlock.1372* }
%"tart.collections.Collection[tart.reflect.Property].151" = type { %"tart.core.Iterable[tart.reflect.Property].150", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Property].1670" = type { %"tart.core.Iterable[tart.reflect.Property].1669", %tart.core.TypeInfoBlock.1678* }
%"tart.collections.Collection[tart.reflect.Property].1896" = type { %"tart.core.Iterable[tart.reflect.Property].1895", %tart.core.TypeInfoBlock.1904* }
%"tart.collections.Collection[tart.reflect.Property].226" = type { %"tart.core.Iterable[tart.reflect.Property].225", %tart.core.TypeInfoBlock.234* }
%"tart.collections.Collection[tart.reflect.Property].3365" = type { %"tart.core.Iterable[tart.reflect.Property].3364", %tart.core.TypeInfoBlock.3373* }
%"tart.collections.Collection[tart.reflect.Property].38" = type { %"tart.core.Iterable[tart.reflect.Property].37", %tart.core.TypeInfoBlock.46* }
%"tart.collections.Collection[tart.reflect.Property].433" = type { %"tart.core.Iterable[tart.reflect.Property].432", %tart.core.TypeInfoBlock.441* }
%"tart.collections.Collection[tart.reflect.Property].460" = type { %"tart.core.Iterable[tart.reflect.Property].459", %tart.core.TypeInfoBlock.468* }
%"tart.collections.Collection[tart.reflect.Property].65" = type { %"tart.core.Iterable[tart.reflect.Property].64", %tart.core.TypeInfoBlock.73* }
%"tart.collections.Collection[tart.reflect.Property].722" = type { %"tart.core.Iterable[tart.reflect.Property].721", %tart.core.TypeInfoBlock.730* }
%"tart.collections.Collection[tart.reflect.Property].802" = type { %"tart.core.Iterable[tart.reflect.Property].801", %tart.core.TypeInfoBlock.810* }
%"tart.collections.Collection[tart.reflect.Property].92" = type { %"tart.core.Iterable[tart.reflect.Property].91", %tart.core.TypeInfoBlock.100* }
%"tart.collections.Collection[tart.reflect.Type]" = type { %"tart.core.Iterable[tart.reflect.Type]", %tart.core.TypeInfoBlock* }
%"tart.collections.Collection[tart.reflect.Type].1355" = type { %"tart.core.Iterable[tart.reflect.Type].1354", %tart.core.TypeInfoBlock.1372* }
%"tart.collections.Collection[tart.reflect.Type].142" = type { %"tart.core.Iterable[tart.reflect.Type].141", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Collection[tart.reflect.Type].1661" = type { %"tart.core.Iterable[tart.reflect.Type].1660", %tart.core.TypeInfoBlock.1678* }
%"tart.collections.Collection[tart.reflect.Type].1887" = type { %"tart.core.Iterable[tart.reflect.Type].1886", %tart.core.TypeInfoBlock.1904* }
%"tart.collections.Collection[tart.reflect.Type].2" = type { %"tart.core.Iterable[tart.reflect.Type].1", %tart.core.TypeInfoBlock.19* }
%"tart.collections.Collection[tart.reflect.Type].217" = type { %"tart.core.Iterable[tart.reflect.Type].216", %tart.core.TypeInfoBlock.234* }
%"tart.collections.Collection[tart.reflect.Type].29" = type { %"tart.core.Iterable[tart.reflect.Type].28", %tart.core.TypeInfoBlock.46* }
%"tart.collections.Collection[tart.reflect.Type].3356" = type { %"tart.core.Iterable[tart.reflect.Type].3355", %tart.core.TypeInfoBlock.3373* }
%"tart.collections.Collection[tart.reflect.Type].424" = type { %"tart.core.Iterable[tart.reflect.Type].423", %tart.core.TypeInfoBlock.441* }
%"tart.collections.Collection[tart.reflect.Type].451" = type { %"tart.core.Iterable[tart.reflect.Type].450", %tart.core.TypeInfoBlock.468* }
%"tart.collections.Collection[tart.reflect.Type].56" = type { %"tart.core.Iterable[tart.reflect.Type].55", %tart.core.TypeInfoBlock.73* }
%"tart.collections.Collection[tart.reflect.Type].713" = type { %"tart.core.Iterable[tart.reflect.Type].712", %tart.core.TypeInfoBlock.730* }
%"tart.collections.Collection[tart.reflect.Type].793" = type { %"tart.core.Iterable[tart.reflect.Type].792", %tart.core.TypeInfoBlock.810* }
%"tart.collections.Collection[tart.reflect.Type].83" = type { %"tart.core.Iterable[tart.reflect.Type].82", %tart.core.TypeInfoBlock.100* }
%"tart.collections.Collection[uint8]" = type { %"tart.core.Iterable[uint8]", %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[char]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[int8]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.core.Attribute]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.core.Object]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.core.String]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.core.String].2484" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.core.String|Null]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.reflect.Module]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.reflect.NameTable.CompoundName]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[tart.reflect.Package]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.Copyable[uint8]" = type { %tart.core.TypeInfoBlock.122* }
%"tart.collections.ImmutableList[tart.core.String]" = type { %tart.core.Object, %"tart.core.String[]"* }
%"tart.collections.ImmutableList[tart.core.String].103" = type { %tart.core.Object.101, %"tart.core.String[].102"* }
%"tart.collections.ImmutableList[tart.core.String].110" = type { %tart.core.Object.108, %"tart.core.String[].135"* }
%"tart.collections.ImmutableList[tart.core.String].1269" = type opaque
%"tart.collections.ImmutableList[tart.core.String].128" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1375" = type { %tart.core.Object.1373, %"tart.core.String[].1374"* }
%"tart.collections.ImmutableList[tart.core.String].1425" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1434" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1443" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1491" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1500" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1509" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1518" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1527" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1611" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1620" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1629" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1638" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1647" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1681" = type { %tart.core.Object.1679, %"tart.core.String[].1680"* }
%"tart.collections.ImmutableList[tart.core.String].172" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1762" = type opaque
%"tart.collections.ImmutableList[tart.core.String].1907" = type { %tart.core.Object.1905, %"tart.core.String[].1906"* }
%"tart.collections.ImmutableList[tart.core.String].2081" = type opaque
%"tart.collections.ImmutableList[tart.core.String].2098" = type opaque
%"tart.collections.ImmutableList[tart.core.String].2107" = type opaque
%"tart.collections.ImmutableList[tart.core.String].22" = type { %tart.core.Object.20, %"tart.core.String[].21"* }
%"tart.collections.ImmutableList[tart.core.String].237" = type { %tart.core.Object.235, %"tart.core.String[].236"* }
%"tart.collections.ImmutableList[tart.core.String].282" = type opaque
%"tart.collections.ImmutableList[tart.core.String].3376" = type { %tart.core.Object.3374, %"tart.core.String[].3375"* }
%"tart.collections.ImmutableList[tart.core.String].3506" = type opaque
%"tart.collections.ImmutableList[tart.core.String].3523" = type opaque
%"tart.collections.ImmutableList[tart.core.String].3559" = type opaque
%"tart.collections.ImmutableList[tart.core.String].444" = type { %tart.core.Object.442, %"tart.core.String[].443"* }
%"tart.collections.ImmutableList[tart.core.String].471" = type { %tart.core.Object.469, %"tart.core.String[].470"* }
%"tart.collections.ImmutableList[tart.core.String].481" = type opaque
%"tart.collections.ImmutableList[tart.core.String].49" = type { %tart.core.Object.47, %"tart.core.String[].48"* }
%"tart.collections.ImmutableList[tart.core.String].689" = type opaque
%"tart.collections.ImmutableList[tart.core.String].698" = type opaque
%"tart.collections.ImmutableList[tart.core.String].707" = type opaque
%"tart.collections.ImmutableList[tart.core.String].733" = type { %tart.core.Object.731, %"tart.core.String[].732"* }
%"tart.collections.ImmutableList[tart.core.String].743" = type opaque
%"tart.collections.ImmutableList[tart.core.String].76" = type { %tart.core.Object.74, %"tart.core.String[].75"* }
%"tart.collections.ImmutableList[tart.core.String].787" = type opaque
%"tart.collections.ImmutableList[tart.core.String].813" = type { %tart.core.Object.811, %"tart.core.String[].812"* }
%"tart.collections.ImmutableList[tart.core.String].969" = type opaque

As you can see, for each original source type, there are generally around 10-30 duplicates. This tells me that the IR is far less clear or compact than it ought to be. In fact it looks like an explosion of type names.

For example, as you can see there are a ton of definitions of "tart.core.ImmutableList[String]", many of which are opaque - why was the linker not able to merge these?

Bear in mind that this is a "headerless" language, like Java and Python, where there is a mapping between the directory structure containing the source files, and the type naming hierarchy within the language. What this basically means is that for any given type name, there is one true definition of that type, and it's generally impossible, or at least very difficult, to have two incompatible definitions of the same type.

This does not mean, however, that the compiler emits identical definitions for a particular type name in every module. In order to prevent the problem I was talking about with the previous type system - where the compiler is forced to "drill down" through pointer fields - the compiler only does a StructType.setBody() when it is actually needed. If a given pointer field is never dereferenced, then the type that is pointed to remains opaque.

However, I would expect that two types which have the same name and the similar structure to be merged - even if some of the fields of the two types are pointers to opaque types, as long as the type name of the field is the same in both cases.

--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev