Alias to Linkonce global / canonical representation for Aliases

[joker-eph]

Bugzilla Link	27866
Version	trunk
OS	All
CC	@majnemer,@dexonsmith,@rjmccall,@rnk,@yuanfang-chen

Extended Description

I spent some time with Duncan today trying to understand aliases and we came to the conclusion that:

@​a = global i32 0 @​b = alias @​a

should be equivalent to:

@​0 = private i32 0 @​a = alias @​0 @​b = alias @​0

We may even consider this as a canonical representation of aliases and have global-opt actually take care of doing this transformation.

However some behavior is unexpected, right now running llvm-link with the following IR:

@​A = linkonce_odr global i8 1 @​B = alias i8, i8* @​A

will generate the same IR. It means that linking @​B actually introduce the symbol @​A as if the alias is an actual use of the other name. Running globalopt/global-dce does not change the IR.

However if we "canonicalize" to:

@​0 = private global i8 1 @​A = linkonce_odr alias i8, i8 @​0 @​B = alias i8, i8 @​0

Then llvm-link generates:

@​0 = private global i8 1 @​B = alias i8, i8* @​0

In this case the symbol @​A will not be pulled in. Also, if instead of running llvm-link we run globaldce, we end up with the same result (@A is dropped). Finally globalopt is able to turn this IR into:

@​B = constant i8 1

[rjmccall]

Okay. In that case, I agree that the right semantic model is that an alias always references the module's own definition of the aliasee.

[llvmbot]

I don't believe this will be a good canonical representation because the two forms are not equivalent for COFF.

the following: @​a = linkonce_odr global i32 0 @​b = alias i32, i32* @​a

produces: [ 4](sec 3)(fl 0x00)(ty 0)(scl 3) (nx 1) 0x00000000 .bss [ 7](sec 3)(fl 0x00)(ty 0)(scl 2) (nx 0) 0x00000000 _a [ 8](sec 3)(fl 0x00)(ty 0)(scl 2) (nx 0) 0x00000000 _b

however, the following: @​0 = private global i32 0 @​a = linkonce_odr alias i32, i32 @​0 @​b = alias i32, i32 @​0

produces: [ 4](sec 3)(fl 0x00)(ty 0)(scl 3) (nx 1) 0x00000000 .bss [ 7](sec 0)(fl 0x00)(ty 0)(scl 69) (nx 1) 0x00000000 _a [10](sec 3)(fl 0x00)(ty 0)(scl 2) (nx 0) 0x00000000 _b

With r270906 we now match gas. The first IR produces

Symbol { Name: a Value: 0 Section: .bss (3) BaseType: Null (0x0) ComplexType: Null (0x0) StorageClass: External (0x2) AuxSymbolCount: 0 } Symbol { Name: b Value: 0 Section: .bss (3) BaseType: Null (0x0) ComplexType: Null (0x0) StorageClass: External (0x2) AuxSymbolCount: 0 }

The second one produces

Symbol { Name: a Value: 0 Section: IMAGE_SYM_UNDEFINED (0) BaseType: Null (0x0) ComplexType: Null (0x0) StorageClass: WeakExternal (0x69) AuxSymbolCount: 1 AuxWeakExternal { Linked: .weak.a.default (9) Search: Library (0x2) } } Symbol { Name: .weak.a.default Value: 0 Section: .bss (3) BaseType: Null (0x0) ComplexType: Null (0x0) StorageClass: External (0x2) AuxSymbolCount: 0 } Symbol { Name: b Value: 0 Section: .bss (3) BaseType: Null (0x0) ComplexType: Null (0x0) StorageClass: External (0x2) AuxSymbolCount: 0 }

which should be equivalent.

[llvmbot]

Oh, you're just saying that a "weak" definition doesn't use the COMDAT mechanism at all. Okay. Do you only get COMDATs if you specifically ask for one in IR?

Correct.

[llvmbot]

Well, ok, I definitely do not understand ELF.

BTW, coff will print exactly the same if we teach llc to handle weak.

If I edit the test2.s to have ".weak a" instead of ".global a" I can link an executable with link.exe and it print "43 42" too.

The linking model is:

• Use the comdats to decide which sections to keep
• Perform symbol resolution

The first part is trivial since there are no comdats: we keep everything. In this case that means the .text section from test1.o and the .data sections from test2.o and test3.o.

Now for symbol resolution:

• test1.o has undefined "a" and "b"
• test2.o has a weak "a" and a strong "b"
• test3.o has a strong "a"

the result is that we "a" from test3.o and "b" from test2.o win, hence "43 42".

Note that from the linker's point of view there are no aliases, just symbols. The fact that two of those symbols are in the same position in the section is irrelevant. For the linker, resolution would work just the same if test2.ll was

@​a = weak global i32 42 @​b = global i32 42

[rjmccall]

Oh, you're just saying that a "weak" definition doesn't use the COMDAT mechanism at all. Okay. Do you only get COMDATs if you specifically ask for one in IR?

[rjmccall]

Well, ok, I definitely do not understand ELF.

[llvmbot]

testcase this test will print "43 42" on elf.

[llvmbot]

It seems to me that a "symbolic" model, where a global alias is a request to define one symbol as exactly some other constant, would be much easier to reason about and also give better results. (Not all values for the other constant are implementable, of course, but that's a typical problem for IR.) It would also be more consistent with what I assume ELF linker behavior is, which is that aliases into COMDATs will naturally end up pointing into the merged COMDAT instead of pointing to some otherwise-unreferenced atom.

No. The easiest way to think of alias in ELF is: There are no aliases. There are only two symbols. When given

@​a = alias @​b

ELF will have two symbols at the same point in the section. There is no way of knowing if a was an alias to b or the other way around.

I understand this. However, those two symbols will be defined in a COMDAT section named 'b'.

No. Those symbols are not in a comdat. Comdat and symbol resolution are independent on ELF. I will attach a testcase that should make this clear.

[rjmccall]

It seems to me that a "symbolic" model, where a global alias is a request to define one symbol as exactly some other constant, would be much easier to reason about and also give better results. (Not all values for the other constant are implementable, of course, but that's a typical problem for IR.) It would also be more consistent with what I assume ELF linker behavior is, which is that aliases into COMDATs will naturally end up pointing into the merged COMDAT instead of pointing to some otherwise-unreferenced atom.

No. The easiest way to think of alias in ELF is: There are no aliases. There are only two symbols. When given

@​a = alias @​b

ELF will have two symbols at the same point in the section. There is no way of knowing if a was an alias to b or the other way around.

I understand this. However, those two symbols will be defined in a COMDAT section named 'b'. If the linker chooses a different 'b' section than this, and that section doesn't define 'a', we don't somehow still end up with a second copy of this section; we just completely lose the definition of 'a'. I would describe that as following the symbolic model with a restriction about how aliases to weak symbols work.

[llvmbot]

It seems to me that a "symbolic" model, where a global alias is a request to define one symbol as exactly some other constant, would be much easier to reason about and also give better results. (Not all values for the other constant are implementable, of course, but that's a typical problem for IR.) It would also be more consistent with what I assume ELF linker behavior is, which is that aliases into COMDATs will naturally end up pointing into the merged COMDAT instead of pointing to some otherwise-unreferenced atom.

No. The easiest way to think of alias in ELF is: There are no aliases. There are only two symbols. When given

@​a = alias @​b

ELF will have two symbols at the same point in the section. There is no way of knowing if a was an alias to b or the other way around.

[joker-eph]

Some examples I discussed with John below.

Module A: @​b = weak global i32 42 @​a = alias i32, i32* @​b

Module B: @​b = weak global i32 42 @​c = alias i32, i32* @​b

And running: llvm-link A.ll B.ll -o - S, we get:

@​b = weak global i32 42 @​b.1 = internal global i32 42 @​a = alias i32, i32 @​b @​c = alias i32, i32 @​b.1

The IR semantic question is whether the original Module A and B above should lead to @​a and @​c to share the same address, even though they are not weak themselve (but their aliasee is).

Alternatively, making the alias itself weak and not the aliasee:

Module A: @​a = weak alias i32, i32* @​c @​c = global i32 42

Module B: @​a = weak alias i32, i32* @​b @​b = global i32 42

running: llvm-link A.ll B.ll -o - S, we get:

@​b = global i32 42 @​c = global i32 42 @​a = weak alias i32, i32* @​b

Here again the address identity in Module A between @​a and @​c is lost.

[rjmccall]

Mehdi came by to explain that LLVM uses a model already in the IR linker where global aliases to weak symbols are aliases to the module's private definition of the symbol. This unsurprisingly causes a huge amount of grief for the IR linker, which actually imports both definitions using different names.

It seems to me that a "symbolic" model, where a global alias is a request to define one symbol as exactly some other constant, would be much easier to reason about and also give better results. (Not all values for the other constant are implementable, of course, but that's a typical problem for IR.) It would also be more consistent with what I assume ELF linker behavior is, which is that aliases into COMDATs will naturally end up pointing into the merged COMDAT instead of pointing to some otherwise-unreferenced atom.

[rjmccall]

The value of a symbol is the address it resolves to.

[joker-eph]

I guess I didn't actually give an opinion above.

I think the better semantic model is that a weak_odr or linkonce_odr alias semantically guarantees the value of the symbol, which means that Mehdi's equivalence is not innate, which means that this is not a valid canonicalization in all cases.

I'm not sure I get it, what do you mean by "the value of the symbol"?

I don't expect the equivalence I posted to change anything related to linkonce_odr symbol, i.e.

Module A:

@​a = linkonce_odr i32 42 @​c = global alias i32 @​a

Module B:

@​b = global i32 42 @​a = linkonce_odr alias i32 @​b

When I link Module A and Module B, I expect every references to @​a to point to the same address, wherever module they come from. And it may or may not be the same location as @​b. Also, I don't expect any guarantee on @​c sharing the same location as @​a.

[rnk]

But now the linkage of 'A' has had it's properties changed. Is this OK?

Well, if we were still implicitly putting linkonce_odr things in comdats, then there would be no semantic change. @​A really should've been in a comdat to start with.

We should probably consider rejecting all weak-for-linker symbol definitions that aren't in comdats on COFF, given that we lower them to normal external symbols.

[rjmccall]

I guess I didn't actually give an opinion above.

I think the better semantic model is that a weak_odr or linkonce_odr alias semantically guarantees the value of the symbol, which means that Mehdi's equivalence is not innate, which means that this is not a valid canonicalization in all cases.

[991901f3-cc14-4404-b340-165691b62a58]

Reid, do you have anything to add?

Maybe the problem is that for COFF, weak symbols aren't as much of a real thing. I mean, mingw GCC implements attribute((weak)) with weak aliases. =P

Maybe this should be the new canonicalization:

@​A = linkonce_odr global i8 1 @​B = alias i8, i8* @​A

->

@​0 = private global i8 1 comdat(@A) @​A = alias i8, i8 @​A @​B = alias i8, i8 @​A

This is much more like what we use for MS ABI vftables with RTTI:

rnk@RNK3-W /src/llvm/build $ echo 'struct A { virtual void f(); } a;' | clang -x c++ - -S -emit-llvm -o

• | grep _7A $"\01??_7A@@6B@" = comdat largest @​0 = private unnamed_addr constant [2 x i8] [i8 bitcast (%rtti.CompleteObjectLocator @"\01??_R4A@@6B@" to i8), i8 bitcast (void (%struct.A) @"\01?f@A@@UEAAXXZ" to i8)], comdat($"\01??_7A@@6B@") @"\01?a@@3UA@@A" = global { i8 } { i8 @"\01??_7A@@6B@" }, align 8 @"\01??_7A@@6B@" = unnamed_addr alias i8, getelementptr inbounds ([2 x i8], [2 x i8] @​0, i32 0, i32 1)

But now the linkage of 'A' has had it's properties changed. Is this OK?

[rnk]

Reid, do you have anything to add?

Maybe the problem is that for COFF, weak symbols aren't as much of a real thing. I mean, mingw GCC implements attribute((weak)) with weak aliases. =P

Maybe this should be the new canonicalization:

@​A = linkonce_odr global i8 1 @​B = alias i8, i8* @​A

->

@​0 = private global i8 1 comdat(@A) @​A = alias i8, i8 @​A @​B = alias i8, i8 @​A

This is much more like what we use for MS ABI vftables with RTTI:

rnk@RNK3-W /src/llvm/build $ echo 'struct A { virtual void f(); } a;' | clang -x c++ - -S -emit-llvm -o - | grep _7A $"\01??_7A@@6B@" = comdat largest @​0 = private unnamed_addr constant [2 x i8] [i8 bitcast (%rtti.CompleteObjectLocator @"\01??_R4A@@6B@" to i8), i8 bitcast (void (%struct.A) @"\01?f@A@@UEAAXXZ" to i8)], comdat($"\01??_7A@@6B@") @"\01?a@@3UA@@A" = global { i8 } { i8 @"\01??_7A@@6B@" }, align 8 @"\01??_7A@@6B@" = unnamed_addr alias i8, getelementptr inbounds ([2 x i8], [2 x i8] @​0, i32 0, i32 1)

[rjmccall]

I think there are two plausible semantic models here, distinguished basically by whether Mehdi's equivalence is innate or just deducible.

Global aliases (1) sometimes create a symbol definition and (2) sometimes give us semantic guarantees about the value of the dynamic symbol definition. (We don't allow global alias "declarations", so the only case where (1) is not true is an available_externally global alias, which I'm not sure we permit. But I think it's helpful here to think about what it would mean if we did permit them.) In many cases, the dynamic symbol definition has to be the symbol definition being locally created; in these cases, Mehdi's equivalence clearly holds. But that's not always true: in particular, it wouldn't be true for available_externally aliases, and it's not necessarily true for replaceable aliases (i.e. weak, linkonce, preemptable), even if they make an ODR guarantee.

So another way of looking at the difference between the two semantic models is: what exactly is guaranteed by an ODR-like semantic guarantee on a global alias that won't necessarily be the dynamic symbol definition?

If it guarantees that the dynamic value will be the exact value of the pointee, then Mehdi's equivalence is not innate. (It's still deducible for non-replaceable definitions, of course.) In this model, something like a linkonce_odr alias to a private global is almost inherently a semantic violation; it would be valid if this alias were only defined in one translation unit, I guess. However, this model does permit the optimizer to simplify references to ODR-defined global aliases to just directly use their aliasee.

If instead it only guarantees that the dynamic value will have the general properties of the aliasee (other than its address), then Mehdi's equivalence is innate. But in this model, you cannot always simplify a reference to an ODR-defined global alias to its aliasee; you can only do this if e.g. the aliasee is immutable and the reference does not depend on the address.

[991901f3-cc14-4404-b340-165691b62a58]

I don't believe this will be a good canonical representation because the two forms are not equivalent for COFF.

the following: @​a = linkonce_odr global i32 0 @​b = alias i32, i32* @​a

produces: [ 4](sec 3)(fl 0x00)(ty 0)(scl 3) (nx 1) 0x00000000 .bss [ 7](sec 3)(fl 0x00)(ty 0)(scl 2) (nx 0) 0x00000000 _a [ 8](sec 3)(fl 0x00)(ty 0)(scl 2) (nx 0) 0x00000000 _b

however, the following: @​0 = private global i32 0 @​a = linkonce_odr alias i32, i32 @​0 @​b = alias i32, i32 @​0

produces: [ 4](sec 3)(fl 0x00)(ty 0)(scl 3) (nx 1) 0x00000000 .bss [ 7](sec 0)(fl 0x00)(ty 0)(scl 69) (nx 1) 0x00000000 _a [10](sec 3)(fl 0x00)(ty 0)(scl 2) (nx 0) 0x00000000 _b

Note that '_a' is now in section 0 instead of section '3'. This is because it is now a weak alias.

Symbol { Name: _a Value: 0 Section: IMAGE_SYM_UNDEFINED (0) BaseType: Null (0x0) ComplexType: Null (0x0) StorageClass: WeakExternal (0x69) AuxSymbolCount: 1 AuxWeakExternal { Linked: L___unnamed_1 (9) Search: Library (0x2) } }

Because of this, I do not believe the first IR is equivalent to the second.

Reid, do you have anything to add?

[llvmbot]

I spent some time with Duncan today trying to understand aliases and we came to the conclusion that:

@​a = global i32 0 @​b = alias @​a

should be equivalent to:

@​0 = private i32 0 @​a = alias @​0 @​b = alias @​0

Correct, a and be are quest names to a given location.

We may even consider this as a canonical representation of aliases and have global-opt actually take care of doing this transformation.

I would go further with the definition of what is "canonical". Since aliases are really just a name for a position in the file, I think the correct way to represent aliases is

• They can only point on a GlobalObject plus offset. The offset is just a uint64_t.
• The GlobalObject has to be private.

I implemented first part a long time ago, but it was reverted in 210062 because John didn't like it.

Having the two properties above would dramatically simplify the linking process. Since private values naturally don't take part in resolution, linking would just work without any extra logic for handling aliasee expressions. That is, we would have a single map.

However some behavior is unexpected, right now running llvm-link with the following IR:

@​A = linkonce_odr global i8 1 @​B = alias i8, i8* @​A

will generate the same IR. It means that linking @​B actually introduce the symbol @​A as if the alias is an actual use of the other name. Running globalopt/global-dce does not change the IR.

However if we "canonicalize" to:

@​0 = private global i8 1 @​A = linkonce_odr alias i8, i8 @​0 @​B = alias i8, i8 @​0

Then llvm-link generates:

@​0 = private global i8 1 @​B = alias i8, i8* @​0

I would say the current behaviour is a bug in llvm-link.

In this case the symbol @​A will not be pulled in. Also, if instead of running llvm-link we run globaldce, we end up with the same result (@A is dropped). Finally globalopt is able to turn this IR into:

@​B = constant i8 1

These are missing optimization with the current representation.