Linking modules in different order produces different results

[Quuxplusone]

Bugzilla Link	PR14235
Status	NEW
Importance	P normal
Reported by	xiao_yi_guo@yahoo.com
Reported on	2012-11-01 13:45:10 -0700
Last modified on	2013-03-18 14:40:32 -0700
Version	trunk
Hardware	PC All
CC	baldrick@free.fr, geek4civic@gmail.com, llvm-bugs@lists.llvm.org, pawel@32bitmicro.com, rafael@espindo.la, wenhan.gu@gmail.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

Given three modules:
-----------------------------------------------------------------
s1.ll:

%0 = type <{ i32, i32 }>

define void @s1(%0* byval %myStruct) nounwind {
return:
  ret void
}
-----------------------------------------------------------------
s2.ll:

%0 = type <{ i32, i32 }>

define void @s2(%0* byval %myStruct) nounwind {
return:
  ret void
}
-----------------------------------------------------------------
s3.ll:
%0 = type <{ i32, i32 }>

declare void @s1(%0* byval) nounwind readonly declare void @s2(%0* byval)
nounwind readonly

define  void @s3(%0* byval %myStruct) nounwind {
    call void @s1(%0* %myStruct) nounwind
    call void @s2(%0* %myStruct) nounwind
    ret void
}
-----------------------------------------------------------------
If they are linked in one order:
$ llvm-link -o s.bc s1.ll s2.ll s3.ll
The linked IR is:

%0 = type <{ i32, i32 }>
%1 = type <{ i32, i32 }>

define  void @s1(%0* byval %myStruct) nounwind {
return:
  ret void
}

define  void @s2(%1* byval %myStruct) nounwind {
return:
  ret void
}

define  void @s3(%0* byval %myStruct) nounwind {
  call  void @s1(%0* %myStruct) nounwind
  call  void bitcast (void (%1*)* @s2 to void (%0*)*)(%0* %myStruct) nounwind
  ret void
}

-----------------------------------------------------------------
If they are linked in a different order:
$ llvm-link -o s.bc s3.ll s1.ll s2.ll
The linked IR is:

%0 = type <{ i32, i32 }>

define  void @s3(%0* byval %myStruct) nounwind {
  call  void @s1(%0* %myStruct) nounwind
  call  void @s2(%0* %myStruct) nounwind
  ret void
}

define  void @s1(%0* byval %myStruct) nounwind {
return:
  ret void
}

define  void @s2(%0* byval %myStruct) nounwind {
return:
  ret void
}

-----------------------------------------------------------------
The second linked IR should be generated regardless of the order the modules
are linked in.

[Quuxplusone]

Hi Xiao Yi Guo,

I think this is not a bug, which is just one implementation approach.
The final native result can run normally and nothing error, didn't it?
Although the final native result might look different, but no one guarantees
the IR will be the same.

Please correct me if I'm wrong. :)

Thanks.

[Quuxplusone]

I think maybe the type merging is wrong.  Why does one linked module get these
two types

%0 = type <{ i32, i32 }>
%1 = type <{ i32, i32 }>

but not the other one?

[Quuxplusone]

I understand how it happened:

If modules are linked in the s1, s2, s3 order:
1. Link s2 to s1.
   %0 from s1 and %0 from s2 are not merged. %0 from s2 got renamed to %1.
2. Link with s3.
   @s1() from s3 is mapped to @s1() from linked module. So %0 from s3 is mapped to %0 in linked module.
   @s2() from s3 is mapped to @s2() from linked module. So %0 from s3 is mapped to %1 in linked module.

If modules are linked in the s3, s1, s2 order:
1. Link s1 to s3.
   @s1() from s1 is mapped to @s1() from s3. So %0 from s1 is mapped to %0 from s3.
2. Link with s2.
   @s2() from s2 is mapped to @s2() from linked module. So %0 from s2 is mapped to %0 in linked module.

That's how one linked module ended up with one type while the other linked
module ended up with two types.

You can argue that both linked modules work. But at least this is not ideal.

There are two issues here:
1. Result should be the same regardless of the link order.
2. In s3.ll it is declared that s1(), s2() and s3() all have the same arg type.
Calls from s3() to s2() don't need a cast. But in one linked module they have
different arg types and call from s3() to s2() needs a cast.

It is not a bug in the implementation, but the result of the design of the
algorithm.

So I don't know whether this result is intentional by the original design, or
if there is a flaw in the algorithm. To fix this, seems that a fundamental
change is needed to the type mapping algorithm.