Allow the C API users to keep relying on the OutMessages parameter.
[oota-llvm.git] / lib / Linker / LinkModules.cpp
1 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LLVM module linker.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Linker/Linker.h"
15 #include "llvm-c/Linker.h"
16 #include "llvm/ADT/Optional.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DiagnosticInfo.h"
21 #include "llvm/IR/DiagnosticPrinter.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/TypeFinder.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 #include <cctype>
30 #include <tuple>
31 using namespace llvm;
32
33
34 //===----------------------------------------------------------------------===//
35 // TypeMap implementation.
36 //===----------------------------------------------------------------------===//
37
38 namespace {
39   typedef SmallPtrSet<StructType*, 32> TypeSet;
40
41 class TypeMapTy : public ValueMapTypeRemapper {
42   /// MappedTypes - This is a mapping from a source type to a destination type
43   /// to use.
44   DenseMap<Type*, Type*> MappedTypes;
45
46   /// SpeculativeTypes - When checking to see if two subgraphs are isomorphic,
47   /// we speculatively add types to MappedTypes, but keep track of them here in
48   /// case we need to roll back.
49   SmallVector<Type*, 16> SpeculativeTypes;
50
51   /// SrcDefinitionsToResolve - This is a list of non-opaque structs in the
52   /// source module that are mapped to an opaque struct in the destination
53   /// module.
54   SmallVector<StructType*, 16> SrcDefinitionsToResolve;
55
56   /// DstResolvedOpaqueTypes - This is the set of opaque types in the
57   /// destination modules who are getting a body from the source module.
58   SmallPtrSet<StructType*, 16> DstResolvedOpaqueTypes;
59
60 public:
61   TypeMapTy(TypeSet &Set) : DstStructTypesSet(Set) {}
62
63   TypeSet &DstStructTypesSet;
64   /// addTypeMapping - Indicate that the specified type in the destination
65   /// module is conceptually equivalent to the specified type in the source
66   /// module.
67   void addTypeMapping(Type *DstTy, Type *SrcTy);
68
69   /// linkDefinedTypeBodies - Produce a body for an opaque type in the dest
70   /// module from a type definition in the source module.
71   void linkDefinedTypeBodies();
72
73   /// get - Return the mapped type to use for the specified input type from the
74   /// source module.
75   Type *get(Type *SrcTy);
76
77   FunctionType *get(FunctionType *T) {return cast<FunctionType>(get((Type*)T));}
78
79   /// dump - Dump out the type map for debugging purposes.
80   void dump() const {
81     for (DenseMap<Type*, Type*>::const_iterator
82            I = MappedTypes.begin(), E = MappedTypes.end(); I != E; ++I) {
83       dbgs() << "TypeMap: ";
84       I->first->print(dbgs());
85       dbgs() << " => ";
86       I->second->print(dbgs());
87       dbgs() << '\n';
88     }
89   }
90
91 private:
92   Type *getImpl(Type *T);
93   /// remapType - Implement the ValueMapTypeRemapper interface.
94   Type *remapType(Type *SrcTy) override {
95     return get(SrcTy);
96   }
97
98   bool areTypesIsomorphic(Type *DstTy, Type *SrcTy);
99 };
100 }
101
102 void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) {
103   Type *&Entry = MappedTypes[SrcTy];
104   if (Entry) return;
105
106   if (DstTy == SrcTy) {
107     Entry = DstTy;
108     return;
109   }
110
111   // Check to see if these types are recursively isomorphic and establish a
112   // mapping between them if so.
113   if (!areTypesIsomorphic(DstTy, SrcTy)) {
114     // Oops, they aren't isomorphic.  Just discard this request by rolling out
115     // any speculative mappings we've established.
116     for (unsigned i = 0, e = SpeculativeTypes.size(); i != e; ++i)
117       MappedTypes.erase(SpeculativeTypes[i]);
118   }
119   SpeculativeTypes.clear();
120 }
121
122 /// areTypesIsomorphic - Recursively walk this pair of types, returning true
123 /// if they are isomorphic, false if they are not.
124 bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) {
125   // Two types with differing kinds are clearly not isomorphic.
126   if (DstTy->getTypeID() != SrcTy->getTypeID()) return false;
127
128   // If we have an entry in the MappedTypes table, then we have our answer.
129   Type *&Entry = MappedTypes[SrcTy];
130   if (Entry)
131     return Entry == DstTy;
132
133   // Two identical types are clearly isomorphic.  Remember this
134   // non-speculatively.
135   if (DstTy == SrcTy) {
136     Entry = DstTy;
137     return true;
138   }
139
140   // Okay, we have two types with identical kinds that we haven't seen before.
141
142   // If this is an opaque struct type, special case it.
143   if (StructType *SSTy = dyn_cast<StructType>(SrcTy)) {
144     // Mapping an opaque type to any struct, just keep the dest struct.
145     if (SSTy->isOpaque()) {
146       Entry = DstTy;
147       SpeculativeTypes.push_back(SrcTy);
148       return true;
149     }
150
151     // Mapping a non-opaque source type to an opaque dest.  If this is the first
152     // type that we're mapping onto this destination type then we succeed.  Keep
153     // the dest, but fill it in later.  This doesn't need to be speculative.  If
154     // this is the second (different) type that we're trying to map onto the
155     // same opaque type then we fail.
156     if (cast<StructType>(DstTy)->isOpaque()) {
157       // We can only map one source type onto the opaque destination type.
158       if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)))
159         return false;
160       SrcDefinitionsToResolve.push_back(SSTy);
161       Entry = DstTy;
162       return true;
163     }
164   }
165
166   // If the number of subtypes disagree between the two types, then we fail.
167   if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes())
168     return false;
169
170   // Fail if any of the extra properties (e.g. array size) of the type disagree.
171   if (isa<IntegerType>(DstTy))
172     return false;  // bitwidth disagrees.
173   if (PointerType *PT = dyn_cast<PointerType>(DstTy)) {
174     if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace())
175       return false;
176
177   } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) {
178     if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg())
179       return false;
180   } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) {
181     StructType *SSTy = cast<StructType>(SrcTy);
182     if (DSTy->isLiteral() != SSTy->isLiteral() ||
183         DSTy->isPacked() != SSTy->isPacked())
184       return false;
185   } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) {
186     if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements())
187       return false;
188   } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) {
189     if (DVTy->getNumElements() != cast<VectorType>(SrcTy)->getNumElements())
190       return false;
191   }
192
193   // Otherwise, we speculate that these two types will line up and recursively
194   // check the subelements.
195   Entry = DstTy;
196   SpeculativeTypes.push_back(SrcTy);
197
198   for (unsigned i = 0, e = SrcTy->getNumContainedTypes(); i != e; ++i)
199     if (!areTypesIsomorphic(DstTy->getContainedType(i),
200                             SrcTy->getContainedType(i)))
201       return false;
202
203   // If everything seems to have lined up, then everything is great.
204   return true;
205 }
206
207 /// linkDefinedTypeBodies - Produce a body for an opaque type in the dest
208 /// module from a type definition in the source module.
209 void TypeMapTy::linkDefinedTypeBodies() {
210   SmallVector<Type*, 16> Elements;
211   SmallString<16> TmpName;
212
213   // Note that processing entries in this loop (calling 'get') can add new
214   // entries to the SrcDefinitionsToResolve vector.
215   while (!SrcDefinitionsToResolve.empty()) {
216     StructType *SrcSTy = SrcDefinitionsToResolve.pop_back_val();
217     StructType *DstSTy = cast<StructType>(MappedTypes[SrcSTy]);
218
219     // TypeMap is a many-to-one mapping, if there were multiple types that
220     // provide a body for DstSTy then previous iterations of this loop may have
221     // already handled it.  Just ignore this case.
222     if (!DstSTy->isOpaque()) continue;
223     assert(!SrcSTy->isOpaque() && "Not resolving a definition?");
224
225     // Map the body of the source type over to a new body for the dest type.
226     Elements.resize(SrcSTy->getNumElements());
227     for (unsigned i = 0, e = Elements.size(); i != e; ++i)
228       Elements[i] = getImpl(SrcSTy->getElementType(i));
229
230     DstSTy->setBody(Elements, SrcSTy->isPacked());
231
232     // If DstSTy has no name or has a longer name than STy, then viciously steal
233     // STy's name.
234     if (!SrcSTy->hasName()) continue;
235     StringRef SrcName = SrcSTy->getName();
236
237     if (!DstSTy->hasName() || DstSTy->getName().size() > SrcName.size()) {
238       TmpName.insert(TmpName.end(), SrcName.begin(), SrcName.end());
239       SrcSTy->setName("");
240       DstSTy->setName(TmpName.str());
241       TmpName.clear();
242     }
243   }
244
245   DstResolvedOpaqueTypes.clear();
246 }
247
248 /// get - Return the mapped type to use for the specified input type from the
249 /// source module.
250 Type *TypeMapTy::get(Type *Ty) {
251   Type *Result = getImpl(Ty);
252
253   // If this caused a reference to any struct type, resolve it before returning.
254   if (!SrcDefinitionsToResolve.empty())
255     linkDefinedTypeBodies();
256   return Result;
257 }
258
259 /// getImpl - This is the recursive version of get().
260 Type *TypeMapTy::getImpl(Type *Ty) {
261   // If we already have an entry for this type, return it.
262   Type **Entry = &MappedTypes[Ty];
263   if (*Entry) return *Entry;
264
265   // If this is not a named struct type, then just map all of the elements and
266   // then rebuild the type from inside out.
267   if (!isa<StructType>(Ty) || cast<StructType>(Ty)->isLiteral()) {
268     // If there are no element types to map, then the type is itself.  This is
269     // true for the anonymous {} struct, things like 'float', integers, etc.
270     if (Ty->getNumContainedTypes() == 0)
271       return *Entry = Ty;
272
273     // Remap all of the elements, keeping track of whether any of them change.
274     bool AnyChange = false;
275     SmallVector<Type*, 4> ElementTypes;
276     ElementTypes.resize(Ty->getNumContainedTypes());
277     for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i) {
278       ElementTypes[i] = getImpl(Ty->getContainedType(i));
279       AnyChange |= ElementTypes[i] != Ty->getContainedType(i);
280     }
281
282     // If we found our type while recursively processing stuff, just use it.
283     Entry = &MappedTypes[Ty];
284     if (*Entry) return *Entry;
285
286     // If all of the element types mapped directly over, then the type is usable
287     // as-is.
288     if (!AnyChange)
289       return *Entry = Ty;
290
291     // Otherwise, rebuild a modified type.
292     switch (Ty->getTypeID()) {
293     default: llvm_unreachable("unknown derived type to remap");
294     case Type::ArrayTyID:
295       return *Entry = ArrayType::get(ElementTypes[0],
296                                      cast<ArrayType>(Ty)->getNumElements());
297     case Type::VectorTyID:
298       return *Entry = VectorType::get(ElementTypes[0],
299                                       cast<VectorType>(Ty)->getNumElements());
300     case Type::PointerTyID:
301       return *Entry = PointerType::get(ElementTypes[0],
302                                       cast<PointerType>(Ty)->getAddressSpace());
303     case Type::FunctionTyID:
304       return *Entry = FunctionType::get(ElementTypes[0],
305                                         makeArrayRef(ElementTypes).slice(1),
306                                         cast<FunctionType>(Ty)->isVarArg());
307     case Type::StructTyID:
308       // Note that this is only reached for anonymous structs.
309       return *Entry = StructType::get(Ty->getContext(), ElementTypes,
310                                       cast<StructType>(Ty)->isPacked());
311     }
312   }
313
314   // Otherwise, this is an unmapped named struct.  If the struct can be directly
315   // mapped over, just use it as-is.  This happens in a case when the linked-in
316   // module has something like:
317   //   %T = type {%T*, i32}
318   //   @GV = global %T* null
319   // where T does not exist at all in the destination module.
320   //
321   // The other case we watch for is when the type is not in the destination
322   // module, but that it has to be rebuilt because it refers to something that
323   // is already mapped.  For example, if the destination module has:
324   //  %A = type { i32 }
325   // and the source module has something like
326   //  %A' = type { i32 }
327   //  %B = type { %A'* }
328   //  @GV = global %B* null
329   // then we want to create a new type: "%B = type { %A*}" and have it take the
330   // pristine "%B" name from the source module.
331   //
332   // To determine which case this is, we have to recursively walk the type graph
333   // speculating that we'll be able to reuse it unmodified.  Only if this is
334   // safe would we map the entire thing over.  Because this is an optimization,
335   // and is not required for the prettiness of the linked module, we just skip
336   // it and always rebuild a type here.
337   StructType *STy = cast<StructType>(Ty);
338
339   // If the type is opaque, we can just use it directly.
340   if (STy->isOpaque()) {
341     // A named structure type from src module is used. Add it to the Set of
342     // identified structs in the destination module.
343     DstStructTypesSet.insert(STy);
344     return *Entry = STy;
345   }
346
347   // Otherwise we create a new type and resolve its body later.  This will be
348   // resolved by the top level of get().
349   SrcDefinitionsToResolve.push_back(STy);
350   StructType *DTy = StructType::create(STy->getContext());
351   // A new identified structure type was created. Add it to the set of
352   // identified structs in the destination module.
353   DstStructTypesSet.insert(DTy);
354   DstResolvedOpaqueTypes.insert(DTy);
355   return *Entry = DTy;
356 }
357
358 //===----------------------------------------------------------------------===//
359 // ModuleLinker implementation.
360 //===----------------------------------------------------------------------===//
361
362 namespace {
363   class ModuleLinker;
364
365   /// ValueMaterializerTy - Creates prototypes for functions that are lazily
366   /// linked on the fly. This speeds up linking for modules with many
367   /// lazily linked functions of which few get used.
368   class ValueMaterializerTy : public ValueMaterializer {
369     TypeMapTy &TypeMap;
370     Module *DstM;
371     std::vector<Function*> &LazilyLinkFunctions;
372   public:
373     ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
374                         std::vector<Function*> &LazilyLinkFunctions) :
375       ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
376       LazilyLinkFunctions(LazilyLinkFunctions) {
377     }
378
379     Value *materializeValueFor(Value *V) override;
380   };
381
382   namespace {
383   class LinkDiagnosticInfo : public DiagnosticInfo {
384     const Twine &Msg;
385
386   public:
387     LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg);
388     void print(DiagnosticPrinter &DP) const override;
389   };
390   LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity,
391                                          const Twine &Msg)
392       : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {}
393   void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; }
394   }
395
396   /// ModuleLinker - This is an implementation class for the LinkModules
397   /// function, which is the entrypoint for this file.
398   class ModuleLinker {
399     Module *DstM, *SrcM;
400
401     TypeMapTy TypeMap;
402     ValueMaterializerTy ValMaterializer;
403
404     /// ValueMap - Mapping of values from what they used to be in Src, to what
405     /// they are now in DstM.  ValueToValueMapTy is a ValueMap, which involves
406     /// some overhead due to the use of Value handles which the Linker doesn't
407     /// actually need, but this allows us to reuse the ValueMapper code.
408     ValueToValueMapTy ValueMap;
409
410     struct AppendingVarInfo {
411       GlobalVariable *NewGV;  // New aggregate global in dest module.
412       Constant *DstInit;      // Old initializer from dest module.
413       Constant *SrcInit;      // Old initializer from src module.
414     };
415
416     std::vector<AppendingVarInfo> AppendingVars;
417
418     unsigned Mode; // Mode to treat source module.
419
420     // Set of items not to link in from source.
421     SmallPtrSet<const Value*, 16> DoNotLinkFromSource;
422
423     // Vector of functions to lazily link in.
424     std::vector<Function*> LazilyLinkFunctions;
425
426   public:
427     ModuleLinker(Module *dstM, TypeSet &Set, Module *srcM, unsigned mode)
428         : DstM(dstM), SrcM(srcM), TypeMap(Set),
429           ValMaterializer(TypeMap, DstM, LazilyLinkFunctions), Mode(mode) {}
430
431     bool run();
432
433   private:
434     bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
435                               const GlobalValue &Src);
436
437     /// Helper method for setting a message and returning an error code.
438     bool emitError(const Twine &Message) {
439       DstM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));
440       return true;
441     }
442
443     void emitWarning(const Twine &Message) {
444       DstM->getContext().diagnose(LinkDiagnosticInfo(DS_Warning, Message));
445     }
446
447     bool getComdatLeader(Module *M, StringRef ComdatName,
448                          const GlobalVariable *&GVar);
449     bool computeResultingSelectionKind(StringRef ComdatName,
450                                        Comdat::SelectionKind Src,
451                                        Comdat::SelectionKind Dst,
452                                        Comdat::SelectionKind &Result,
453                                        bool &LinkFromSrc);
454     std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
455         ComdatsChosen;
456     bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
457                          bool &LinkFromSrc);
458
459     /// getLinkageResult - This analyzes the two global values and determines
460     /// what the result will look like in the destination module.
461     bool getLinkageResult(GlobalValue *Dest, const GlobalValue *Src,
462                           GlobalValue::LinkageTypes &LT,
463                           GlobalValue::VisibilityTypes &Vis,
464                           bool &LinkFromSrc);
465
466     /// getLinkedToGlobal - Given a global in the source module, return the
467     /// global in the destination module that is being linked to, if any.
468     GlobalValue *getLinkedToGlobal(GlobalValue *SrcGV) {
469       // If the source has no name it can't link.  If it has local linkage,
470       // there is no name match-up going on.
471       if (!SrcGV->hasName() || SrcGV->hasLocalLinkage())
472         return nullptr;
473
474       // Otherwise see if we have a match in the destination module's symtab.
475       GlobalValue *DGV = DstM->getNamedValue(SrcGV->getName());
476       if (!DGV) return nullptr;
477
478       // If we found a global with the same name in the dest module, but it has
479       // internal linkage, we are really not doing any linkage here.
480       if (DGV->hasLocalLinkage())
481         return nullptr;
482
483       // Otherwise, we do in fact link to the destination global.
484       return DGV;
485     }
486
487     void computeTypeMapping();
488
489     void upgradeMismatchedGlobalArray(StringRef Name);
490     void upgradeMismatchedGlobals();
491
492     bool linkAppendingVarProto(GlobalVariable *DstGV, GlobalVariable *SrcGV);
493     bool linkGlobalProto(GlobalVariable *SrcGV);
494     bool linkFunctionProto(Function *SrcF);
495     bool linkAliasProto(GlobalAlias *SrcA);
496     bool linkModuleFlagsMetadata();
497
498     void linkAppendingVarInit(const AppendingVarInfo &AVI);
499     void linkGlobalInits();
500     void linkFunctionBody(Function *Dst, Function *Src);
501     void linkAliasBodies();
502     void linkNamedMDNodes();
503   };
504 }
505
506 /// forceRenaming - The LLVM SymbolTable class autorenames globals that conflict
507 /// in the symbol table.  This is good for all clients except for us.  Go
508 /// through the trouble to force this back.
509 static void forceRenaming(GlobalValue *GV, StringRef Name) {
510   // If the global doesn't force its name or if it already has the right name,
511   // there is nothing for us to do.
512   if (GV->hasLocalLinkage() || GV->getName() == Name)
513     return;
514
515   Module *M = GV->getParent();
516
517   // If there is a conflict, rename the conflict.
518   if (GlobalValue *ConflictGV = M->getNamedValue(Name)) {
519     GV->takeName(ConflictGV);
520     ConflictGV->setName(Name);    // This will cause ConflictGV to get renamed
521     assert(ConflictGV->getName() != Name && "forceRenaming didn't work");
522   } else {
523     GV->setName(Name);              // Force the name back
524   }
525 }
526
527 /// copyGVAttributes - copy additional attributes (those not needed to construct
528 /// a GlobalValue) from the SrcGV to the DestGV.
529 static void copyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) {
530   // Use the maximum alignment, rather than just copying the alignment of SrcGV.
531   auto *DestGO = dyn_cast<GlobalObject>(DestGV);
532   unsigned Alignment;
533   if (DestGO)
534     Alignment = std::max(DestGO->getAlignment(), SrcGV->getAlignment());
535
536   DestGV->copyAttributesFrom(SrcGV);
537
538   if (DestGO)
539     DestGO->setAlignment(Alignment);
540
541   forceRenaming(DestGV, SrcGV->getName());
542 }
543
544 static bool isLessConstraining(GlobalValue::VisibilityTypes a,
545                                GlobalValue::VisibilityTypes b) {
546   if (a == GlobalValue::HiddenVisibility)
547     return false;
548   if (b == GlobalValue::HiddenVisibility)
549     return true;
550   if (a == GlobalValue::ProtectedVisibility)
551     return false;
552   if (b == GlobalValue::ProtectedVisibility)
553     return true;
554   return false;
555 }
556
557 Value *ValueMaterializerTy::materializeValueFor(Value *V) {
558   Function *SF = dyn_cast<Function>(V);
559   if (!SF)
560     return nullptr;
561
562   Function *DF = Function::Create(TypeMap.get(SF->getFunctionType()),
563                                   SF->getLinkage(), SF->getName(), DstM);
564   copyGVAttributes(DF, SF);
565
566   if (Comdat *SC = SF->getComdat()) {
567     Comdat *DC = DstM->getOrInsertComdat(SC->getName());
568     DF->setComdat(DC);
569   }
570
571   LazilyLinkFunctions.push_back(SF);
572   return DF;
573 }
574
575 bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName,
576                                    const GlobalVariable *&GVar) {
577   const GlobalValue *GVal = M->getNamedValue(ComdatName);
578   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
579     GVal = GA->getBaseObject();
580     if (!GVal)
581       // We cannot resolve the size of the aliasee yet.
582       return emitError("Linking COMDATs named '" + ComdatName +
583                        "': COMDAT key involves incomputable alias size.");
584   }
585
586   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
587   if (!GVar)
588     return emitError(
589         "Linking COMDATs named '" + ComdatName +
590         "': GlobalVariable required for data dependent selection!");
591
592   return false;
593 }
594
595 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
596                                                  Comdat::SelectionKind Src,
597                                                  Comdat::SelectionKind Dst,
598                                                  Comdat::SelectionKind &Result,
599                                                  bool &LinkFromSrc) {
600   // The ability to mix Comdat::SelectionKind::Any with
601   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
602   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
603                          Dst == Comdat::SelectionKind::Largest;
604   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
605                          Src == Comdat::SelectionKind::Largest;
606   if (DstAnyOrLargest && SrcAnyOrLargest) {
607     if (Dst == Comdat::SelectionKind::Largest ||
608         Src == Comdat::SelectionKind::Largest)
609       Result = Comdat::SelectionKind::Largest;
610     else
611       Result = Comdat::SelectionKind::Any;
612   } else if (Src == Dst) {
613     Result = Dst;
614   } else {
615     return emitError("Linking COMDATs named '" + ComdatName +
616                      "': invalid selection kinds!");
617   }
618
619   switch (Result) {
620   case Comdat::SelectionKind::Any:
621     // Go with Dst.
622     LinkFromSrc = false;
623     break;
624   case Comdat::SelectionKind::NoDuplicates:
625     return emitError("Linking COMDATs named '" + ComdatName +
626                      "': noduplicates has been violated!");
627   case Comdat::SelectionKind::ExactMatch:
628   case Comdat::SelectionKind::Largest:
629   case Comdat::SelectionKind::SameSize: {
630     const GlobalVariable *DstGV;
631     const GlobalVariable *SrcGV;
632     if (getComdatLeader(DstM, ComdatName, DstGV) ||
633         getComdatLeader(SrcM, ComdatName, SrcGV))
634       return true;
635
636     const DataLayout *DstDL = DstM->getDataLayout();
637     const DataLayout *SrcDL = SrcM->getDataLayout();
638     if (!DstDL || !SrcDL) {
639       return emitError(
640           "Linking COMDATs named '" + ComdatName +
641           "': can't do size dependent selection without DataLayout!");
642     }
643     uint64_t DstSize =
644         DstDL->getTypeAllocSize(DstGV->getType()->getPointerElementType());
645     uint64_t SrcSize =
646         SrcDL->getTypeAllocSize(SrcGV->getType()->getPointerElementType());
647     if (Result == Comdat::SelectionKind::ExactMatch) {
648       if (SrcGV->getInitializer() != DstGV->getInitializer())
649         return emitError("Linking COMDATs named '" + ComdatName +
650                          "': ExactMatch violated!");
651       LinkFromSrc = false;
652     } else if (Result == Comdat::SelectionKind::Largest) {
653       LinkFromSrc = SrcSize > DstSize;
654     } else if (Result == Comdat::SelectionKind::SameSize) {
655       if (SrcSize != DstSize)
656         return emitError("Linking COMDATs named '" + ComdatName +
657                          "': SameSize violated!");
658       LinkFromSrc = false;
659     } else {
660       llvm_unreachable("unknown selection kind");
661     }
662     break;
663   }
664   }
665
666   return false;
667 }
668
669 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
670                                    Comdat::SelectionKind &Result,
671                                    bool &LinkFromSrc) {
672   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
673   StringRef ComdatName = SrcC->getName();
674   Module::ComdatSymTabType &ComdatSymTab = DstM->getComdatSymbolTable();
675   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
676
677   if (DstCI == ComdatSymTab.end()) {
678     // Use the comdat if it is only available in one of the modules.
679     LinkFromSrc = true;
680     Result = SSK;
681     return false;
682   }
683
684   const Comdat *DstC = &DstCI->second;
685   Comdat::SelectionKind DSK = DstC->getSelectionKind();
686   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
687                                        LinkFromSrc);
688 }
689
690 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
691                                         const GlobalValue &Dest,
692                                         const GlobalValue &Src) {
693   bool SrcIsDeclaration = Src.isDeclarationForLinker();
694   bool DestIsDeclaration = Dest.isDeclarationForLinker();
695
696   // FIXME: Make datalayout mandatory and just use getDataLayout().
697   DataLayout DL(Dest.getParent());
698
699   if (SrcIsDeclaration) {
700     // If Src is external or if both Src & Dest are external..  Just link the
701     // external globals, we aren't adding anything.
702     if (Src.hasDLLImportStorageClass()) {
703       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
704       LinkFromSrc = DestIsDeclaration;
705       return false;
706     }
707     // If the Dest is weak, use the source linkage.
708     LinkFromSrc = Dest.hasExternalWeakLinkage();
709     return false;
710   }
711
712   if (DestIsDeclaration) {
713     // If Dest is external but Src is not:
714     LinkFromSrc = true;
715     return false;
716   }
717
718   if (Src.hasCommonLinkage()) {
719     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
720       LinkFromSrc = true;
721       return false;
722     }
723
724     if (!Dest.hasCommonLinkage()) {
725       LinkFromSrc = false;
726       return false;
727     }
728
729     uint64_t DestSize = DL.getTypeAllocSize(Dest.getType()->getElementType());
730     uint64_t SrcSize = DL.getTypeAllocSize(Src.getType()->getElementType());
731     LinkFromSrc = SrcSize > DestSize;
732     return false;
733   }
734
735   if (Src.isWeakForLinker()) {
736     assert(!Dest.hasExternalWeakLinkage());
737     assert(!Dest.hasAvailableExternallyLinkage());
738
739     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
740       LinkFromSrc = true;
741       return false;
742     }
743
744     LinkFromSrc = false;
745     return false;
746   }
747
748   if (Dest.isWeakForLinker()) {
749     assert(Src.hasExternalLinkage());
750     LinkFromSrc = true;
751     return false;
752   }
753
754   assert(!Src.hasExternalWeakLinkage());
755   assert(!Dest.hasExternalWeakLinkage());
756   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
757          "Unexpected linkage type!");
758   return emitError("Linking globals named '" + Src.getName() +
759                    "': symbol multiply defined!");
760 }
761
762 /// This analyzes the two global values and determines what the result will look
763 /// like in the destination module. In particular, it computes the resultant
764 /// linkage type and visibility, computes whether the global in the source
765 /// should be copied over to the destination (replacing the existing one), and
766 /// computes whether this linkage is an error or not.
767 bool ModuleLinker::getLinkageResult(GlobalValue *Dest, const GlobalValue *Src,
768                                     GlobalValue::LinkageTypes &LT,
769                                     GlobalValue::VisibilityTypes &Vis,
770                                     bool &LinkFromSrc) {
771   assert(Dest && "Must have two globals being queried");
772   assert(!Src->hasLocalLinkage() &&
773          "If Src has internal linkage, Dest shouldn't be set!");
774
775   if (shouldLinkFromSource(LinkFromSrc, *Dest, *Src))
776     return true;
777
778   if (LinkFromSrc)
779     LT = Src->getLinkage();
780   else
781     LT = Dest->getLinkage();
782
783   // Compute the visibility. We follow the rules in the System V Application
784   // Binary Interface.
785   assert(!GlobalValue::isLocalLinkage(LT) &&
786          "Symbols with local linkage should not be merged");
787   Vis = isLessConstraining(Src->getVisibility(), Dest->getVisibility()) ?
788     Dest->getVisibility() : Src->getVisibility();
789   return false;
790 }
791
792 /// computeTypeMapping - Loop over all of the linked values to compute type
793 /// mappings.  For example, if we link "extern Foo *x" and "Foo *x = NULL", then
794 /// we have two struct types 'Foo' but one got renamed when the module was
795 /// loaded into the same LLVMContext.
796 void ModuleLinker::computeTypeMapping() {
797   // Incorporate globals.
798   for (Module::global_iterator I = SrcM->global_begin(),
799        E = SrcM->global_end(); I != E; ++I) {
800     GlobalValue *DGV = getLinkedToGlobal(I);
801     if (!DGV) continue;
802
803     if (!DGV->hasAppendingLinkage() || !I->hasAppendingLinkage()) {
804       TypeMap.addTypeMapping(DGV->getType(), I->getType());
805       continue;
806     }
807
808     // Unify the element type of appending arrays.
809     ArrayType *DAT = cast<ArrayType>(DGV->getType()->getElementType());
810     ArrayType *SAT = cast<ArrayType>(I->getType()->getElementType());
811     TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType());
812   }
813
814   // Incorporate functions.
815   for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I) {
816     if (GlobalValue *DGV = getLinkedToGlobal(I))
817       TypeMap.addTypeMapping(DGV->getType(), I->getType());
818   }
819
820   // Incorporate types by name, scanning all the types in the source module.
821   // At this point, the destination module may have a type "%foo = { i32 }" for
822   // example.  When the source module got loaded into the same LLVMContext, if
823   // it had the same type, it would have been renamed to "%foo.42 = { i32 }".
824   TypeFinder SrcStructTypes;
825   SrcStructTypes.run(*SrcM, true);
826   SmallPtrSet<StructType*, 32> SrcStructTypesSet(SrcStructTypes.begin(),
827                                                  SrcStructTypes.end());
828
829   for (unsigned i = 0, e = SrcStructTypes.size(); i != e; ++i) {
830     StructType *ST = SrcStructTypes[i];
831     if (!ST->hasName()) continue;
832
833     // Check to see if there is a dot in the name followed by a digit.
834     size_t DotPos = ST->getName().rfind('.');
835     if (DotPos == 0 || DotPos == StringRef::npos ||
836         ST->getName().back() == '.' ||
837         !isdigit(static_cast<unsigned char>(ST->getName()[DotPos+1])))
838       continue;
839
840     // Check to see if the destination module has a struct with the prefix name.
841     if (StructType *DST = DstM->getTypeByName(ST->getName().substr(0, DotPos)))
842       // Don't use it if this actually came from the source module. They're in
843       // the same LLVMContext after all. Also don't use it unless the type is
844       // actually used in the destination module. This can happen in situations
845       // like this:
846       //
847       //      Module A                         Module B
848       //      --------                         --------
849       //   %Z = type { %A }                %B = type { %C.1 }
850       //   %A = type { %B.1, [7 x i8] }    %C.1 = type { i8* }
851       //   %B.1 = type { %C }              %A.2 = type { %B.3, [5 x i8] }
852       //   %C = type { i8* }               %B.3 = type { %C.1 }
853       //
854       // When we link Module B with Module A, the '%B' in Module B is
855       // used. However, that would then use '%C.1'. But when we process '%C.1',
856       // we prefer to take the '%C' version. So we are then left with both
857       // '%C.1' and '%C' being used for the same types. This leads to some
858       // variables using one type and some using the other.
859       if (!SrcStructTypesSet.count(DST) && TypeMap.DstStructTypesSet.count(DST))
860         TypeMap.addTypeMapping(DST, ST);
861   }
862
863   // Don't bother incorporating aliases, they aren't generally typed well.
864
865   // Now that we have discovered all of the type equivalences, get a body for
866   // any 'opaque' types in the dest module that are now resolved.
867   TypeMap.linkDefinedTypeBodies();
868 }
869
870 static void upgradeGlobalArray(GlobalVariable *GV) {
871   ArrayType *ATy = cast<ArrayType>(GV->getType()->getElementType());
872   StructType *OldTy = cast<StructType>(ATy->getElementType());
873   assert(OldTy->getNumElements() == 2 && "Expected to upgrade from 2 elements");
874
875   // Get the upgraded 3 element type.
876   PointerType *VoidPtrTy = Type::getInt8Ty(GV->getContext())->getPointerTo();
877   Type *Tys[3] = {OldTy->getElementType(0), OldTy->getElementType(1),
878                   VoidPtrTy};
879   StructType *NewTy = StructType::get(GV->getContext(), Tys, false);
880
881   // Build new constants with a null third field filled in.
882   Constant *OldInitC = GV->getInitializer();
883   ConstantArray *OldInit = dyn_cast<ConstantArray>(OldInitC);
884   if (!OldInit && !isa<ConstantAggregateZero>(OldInitC))
885     // Invalid initializer; give up.
886     return;
887   std::vector<Constant *> Initializers;
888   if (OldInit && OldInit->getNumOperands()) {
889     Value *Null = Constant::getNullValue(VoidPtrTy);
890     for (Use &U : OldInit->operands()) {
891       ConstantStruct *Init = cast<ConstantStruct>(U.get());
892       Initializers.push_back(ConstantStruct::get(
893           NewTy, Init->getOperand(0), Init->getOperand(1), Null, nullptr));
894     }
895   }
896   assert(Initializers.size() == ATy->getNumElements() &&
897          "Failed to copy all array elements");
898
899   // Replace the old GV with a new one.
900   ATy = ArrayType::get(NewTy, Initializers.size());
901   Constant *NewInit = ConstantArray::get(ATy, Initializers);
902   GlobalVariable *NewGV = new GlobalVariable(
903       *GV->getParent(), ATy, GV->isConstant(), GV->getLinkage(), NewInit, "",
904       GV, GV->getThreadLocalMode(), GV->getType()->getAddressSpace(),
905       GV->isExternallyInitialized());
906   NewGV->copyAttributesFrom(GV);
907   NewGV->takeName(GV);
908   assert(GV->use_empty() && "program cannot use initializer list");
909   GV->eraseFromParent();
910 }
911
912 void ModuleLinker::upgradeMismatchedGlobalArray(StringRef Name) {
913   // Look for the global arrays.
914   auto *DstGV = dyn_cast_or_null<GlobalVariable>(DstM->getNamedValue(Name));
915   if (!DstGV)
916     return;
917   auto *SrcGV = dyn_cast_or_null<GlobalVariable>(SrcM->getNamedValue(Name));
918   if (!SrcGV)
919     return;
920
921   // Check if the types already match.
922   auto *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
923   auto *SrcTy =
924       cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
925   if (DstTy == SrcTy)
926     return;
927
928   // Grab the element types.  We can only upgrade an array of a two-field
929   // struct.  Only bother if the other one has three-fields.
930   auto *DstEltTy = cast<StructType>(DstTy->getElementType());
931   auto *SrcEltTy = cast<StructType>(SrcTy->getElementType());
932   if (DstEltTy->getNumElements() == 2 && SrcEltTy->getNumElements() == 3) {
933     upgradeGlobalArray(DstGV);
934     return;
935   }
936   if (DstEltTy->getNumElements() == 3 && SrcEltTy->getNumElements() == 2)
937     upgradeGlobalArray(SrcGV);
938
939   // We can't upgrade any other differences.
940 }
941
942 void ModuleLinker::upgradeMismatchedGlobals() {
943   upgradeMismatchedGlobalArray("llvm.global_ctors");
944   upgradeMismatchedGlobalArray("llvm.global_dtors");
945 }
946
947 /// linkAppendingVarProto - If there were any appending global variables, link
948 /// them together now.  Return true on error.
949 bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV,
950                                          GlobalVariable *SrcGV) {
951
952   if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage())
953     return emitError("Linking globals named '" + SrcGV->getName() +
954            "': can only link appending global with another appending global!");
955
956   ArrayType *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
957   ArrayType *SrcTy =
958     cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
959   Type *EltTy = DstTy->getElementType();
960
961   // Check to see that they two arrays agree on type.
962   if (EltTy != SrcTy->getElementType())
963     return emitError("Appending variables with different element types!");
964   if (DstGV->isConstant() != SrcGV->isConstant())
965     return emitError("Appending variables linked with different const'ness!");
966
967   if (DstGV->getAlignment() != SrcGV->getAlignment())
968     return emitError(
969              "Appending variables with different alignment need to be linked!");
970
971   if (DstGV->getVisibility() != SrcGV->getVisibility())
972     return emitError(
973             "Appending variables with different visibility need to be linked!");
974
975   if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr())
976     return emitError(
977         "Appending variables with different unnamed_addr need to be linked!");
978
979   if (StringRef(DstGV->getSection()) != SrcGV->getSection())
980     return emitError(
981           "Appending variables with different section name need to be linked!");
982
983   uint64_t NewSize = DstTy->getNumElements() + SrcTy->getNumElements();
984   ArrayType *NewType = ArrayType::get(EltTy, NewSize);
985
986   // Create the new global variable.
987   GlobalVariable *NG =
988     new GlobalVariable(*DstGV->getParent(), NewType, SrcGV->isConstant(),
989                        DstGV->getLinkage(), /*init*/nullptr, /*name*/"", DstGV,
990                        DstGV->getThreadLocalMode(),
991                        DstGV->getType()->getAddressSpace());
992
993   // Propagate alignment, visibility and section info.
994   copyGVAttributes(NG, DstGV);
995
996   AppendingVarInfo AVI;
997   AVI.NewGV = NG;
998   AVI.DstInit = DstGV->getInitializer();
999   AVI.SrcInit = SrcGV->getInitializer();
1000   AppendingVars.push_back(AVI);
1001
1002   // Replace any uses of the two global variables with uses of the new
1003   // global.
1004   ValueMap[SrcGV] = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType()));
1005
1006   DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType()));
1007   DstGV->eraseFromParent();
1008
1009   // Track the source variable so we don't try to link it.
1010   DoNotLinkFromSource.insert(SrcGV);
1011
1012   return false;
1013 }
1014
1015 /// linkGlobalProto - Loop through the global variables in the src module and
1016 /// merge them into the dest module.
1017 bool ModuleLinker::linkGlobalProto(GlobalVariable *SGV) {
1018   GlobalValue *DGV = getLinkedToGlobal(SGV);
1019   llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
1020   bool HasUnnamedAddr = SGV->hasUnnamedAddr();
1021   unsigned Alignment = SGV->getAlignment();
1022
1023   bool LinkFromSrc = false;
1024   Comdat *DC = nullptr;
1025   if (const Comdat *SC = SGV->getComdat()) {
1026     Comdat::SelectionKind SK;
1027     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
1028     DC = DstM->getOrInsertComdat(SC->getName());
1029     DC->setSelectionKind(SK);
1030   }
1031
1032   if (DGV) {
1033     if (!DC) {
1034       // Concatenation of appending linkage variables is magic and handled later.
1035       if (DGV->hasAppendingLinkage() || SGV->hasAppendingLinkage())
1036         return linkAppendingVarProto(cast<GlobalVariable>(DGV), SGV);
1037
1038       // Determine whether linkage of these two globals follows the source
1039       // module's definition or the destination module's definition.
1040       GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
1041       GlobalValue::VisibilityTypes NV;
1042       if (getLinkageResult(DGV, SGV, NewLinkage, NV, LinkFromSrc))
1043         return true;
1044       NewVisibility = NV;
1045       HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
1046       if (DGV->hasCommonLinkage() && SGV->hasCommonLinkage())
1047         Alignment = std::max(Alignment, DGV->getAlignment());
1048       else if (!LinkFromSrc)
1049         Alignment = DGV->getAlignment();
1050
1051       // If we're not linking from the source, then keep the definition that we
1052       // have.
1053       if (!LinkFromSrc) {
1054         // Special case for const propagation.
1055         if (GlobalVariable *DGVar = dyn_cast<GlobalVariable>(DGV)) {
1056           DGVar->setAlignment(Alignment);
1057
1058           if (DGVar->isDeclaration() && SGV->isConstant() &&
1059               !DGVar->isConstant())
1060             DGVar->setConstant(true);
1061         }
1062
1063         // Set calculated linkage, visibility and unnamed_addr.
1064         DGV->setLinkage(NewLinkage);
1065         DGV->setVisibility(*NewVisibility);
1066         DGV->setUnnamedAddr(HasUnnamedAddr);
1067       }
1068     }
1069
1070     if (!LinkFromSrc) {
1071       // Make sure to remember this mapping.
1072       ValueMap[SGV] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGV->getType()));
1073
1074       // Track the source global so that we don't attempt to copy it over when
1075       // processing global initializers.
1076       DoNotLinkFromSource.insert(SGV);
1077
1078       return false;
1079     }
1080   }
1081
1082   // If the Comdat this variable was inside of wasn't selected, skip it.
1083   if (DC && !DGV && !LinkFromSrc) {
1084     DoNotLinkFromSource.insert(SGV);
1085     return false;
1086   }
1087
1088   // No linking to be performed or linking from the source: simply create an
1089   // identical version of the symbol over in the dest module... the
1090   // initializer will be filled in later by LinkGlobalInits.
1091   GlobalVariable *NewDGV =
1092     new GlobalVariable(*DstM, TypeMap.get(SGV->getType()->getElementType()),
1093                        SGV->isConstant(), SGV->getLinkage(), /*init*/nullptr,
1094                        SGV->getName(), /*insertbefore*/nullptr,
1095                        SGV->getThreadLocalMode(),
1096                        SGV->getType()->getAddressSpace());
1097   // Propagate alignment, visibility and section info.
1098   copyGVAttributes(NewDGV, SGV);
1099   NewDGV->setAlignment(Alignment);
1100   if (NewVisibility)
1101     NewDGV->setVisibility(*NewVisibility);
1102   NewDGV->setUnnamedAddr(HasUnnamedAddr);
1103
1104   if (DC)
1105     NewDGV->setComdat(DC);
1106
1107   if (DGV) {
1108     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDGV, DGV->getType()));
1109     DGV->eraseFromParent();
1110   }
1111
1112   // Make sure to remember this mapping.
1113   ValueMap[SGV] = NewDGV;
1114   return false;
1115 }
1116
1117 /// linkFunctionProto - Link the function in the source module into the
1118 /// destination module if needed, setting up mapping information.
1119 bool ModuleLinker::linkFunctionProto(Function *SF) {
1120   GlobalValue *DGV = getLinkedToGlobal(SF);
1121   llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
1122   bool HasUnnamedAddr = SF->hasUnnamedAddr();
1123
1124   bool LinkFromSrc = false;
1125   Comdat *DC = nullptr;
1126   if (const Comdat *SC = SF->getComdat()) {
1127     Comdat::SelectionKind SK;
1128     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
1129     DC = DstM->getOrInsertComdat(SC->getName());
1130     DC->setSelectionKind(SK);
1131   }
1132
1133   if (DGV) {
1134     if (!DC) {
1135       GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
1136       GlobalValue::VisibilityTypes NV;
1137       if (getLinkageResult(DGV, SF, NewLinkage, NV, LinkFromSrc))
1138         return true;
1139       NewVisibility = NV;
1140       HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
1141
1142       if (!LinkFromSrc) {
1143         // Set calculated linkage
1144         DGV->setLinkage(NewLinkage);
1145         DGV->setVisibility(*NewVisibility);
1146         DGV->setUnnamedAddr(HasUnnamedAddr);
1147       }
1148     }
1149
1150     if (!LinkFromSrc) {
1151       // Make sure to remember this mapping.
1152       ValueMap[SF] = ConstantExpr::getBitCast(DGV, TypeMap.get(SF->getType()));
1153
1154       // Track the function from the source module so we don't attempt to remap
1155       // it.
1156       DoNotLinkFromSource.insert(SF);
1157
1158       return false;
1159     }
1160   }
1161
1162   // If the function is to be lazily linked, don't create it just yet.
1163   // The ValueMaterializerTy will deal with creating it if it's used.
1164   if (!DGV && (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() ||
1165                SF->hasAvailableExternallyLinkage())) {
1166     DoNotLinkFromSource.insert(SF);
1167     return false;
1168   }
1169
1170   // If the Comdat this function was inside of wasn't selected, skip it.
1171   if (DC && !DGV && !LinkFromSrc) {
1172     DoNotLinkFromSource.insert(SF);
1173     return false;
1174   }
1175
1176   // If there is no linkage to be performed or we are linking from the source,
1177   // bring SF over.
1178   Function *NewDF = Function::Create(TypeMap.get(SF->getFunctionType()),
1179                                      SF->getLinkage(), SF->getName(), DstM);
1180   copyGVAttributes(NewDF, SF);
1181   if (NewVisibility)
1182     NewDF->setVisibility(*NewVisibility);
1183   NewDF->setUnnamedAddr(HasUnnamedAddr);
1184
1185   if (DC)
1186     NewDF->setComdat(DC);
1187
1188   if (DGV) {
1189     // Any uses of DF need to change to NewDF, with cast.
1190     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDF, DGV->getType()));
1191     DGV->eraseFromParent();
1192   }
1193
1194   ValueMap[SF] = NewDF;
1195   return false;
1196 }
1197
1198 /// LinkAliasProto - Set up prototypes for any aliases that come over from the
1199 /// source module.
1200 bool ModuleLinker::linkAliasProto(GlobalAlias *SGA) {
1201   GlobalValue *DGV = getLinkedToGlobal(SGA);
1202   llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
1203   bool HasUnnamedAddr = SGA->hasUnnamedAddr();
1204
1205   bool LinkFromSrc = false;
1206   Comdat *DC = nullptr;
1207   if (const Comdat *SC = SGA->getComdat()) {
1208     Comdat::SelectionKind SK;
1209     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
1210     DC = DstM->getOrInsertComdat(SC->getName());
1211     DC->setSelectionKind(SK);
1212   }
1213
1214   if (DGV) {
1215     if (!DC) {
1216       GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
1217       GlobalValue::VisibilityTypes NV;
1218       if (getLinkageResult(DGV, SGA, NewLinkage, NV, LinkFromSrc))
1219         return true;
1220       NewVisibility = NV;
1221       HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
1222
1223       if (!LinkFromSrc) {
1224         // Set calculated linkage.
1225         DGV->setLinkage(NewLinkage);
1226         DGV->setVisibility(*NewVisibility);
1227         DGV->setUnnamedAddr(HasUnnamedAddr);
1228       }
1229     }
1230
1231     if (!LinkFromSrc) {
1232       // Make sure to remember this mapping.
1233       ValueMap[SGA] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGA->getType()));
1234
1235       // Track the alias from the source module so we don't attempt to remap it.
1236       DoNotLinkFromSource.insert(SGA);
1237
1238       return false;
1239     }
1240   }
1241
1242   // If the Comdat this alias was inside of wasn't selected, skip it.
1243   if (DC && !DGV && !LinkFromSrc) {
1244     DoNotLinkFromSource.insert(SGA);
1245     return false;
1246   }
1247
1248   // If there is no linkage to be performed or we're linking from the source,
1249   // bring over SGA.
1250   auto *PTy = cast<PointerType>(TypeMap.get(SGA->getType()));
1251   auto *NewDA =
1252       GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
1253                           SGA->getLinkage(), SGA->getName(), DstM);
1254   copyGVAttributes(NewDA, SGA);
1255   if (NewVisibility)
1256     NewDA->setVisibility(*NewVisibility);
1257   NewDA->setUnnamedAddr(HasUnnamedAddr);
1258
1259   if (DGV) {
1260     // Any uses of DGV need to change to NewDA, with cast.
1261     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDA, DGV->getType()));
1262     DGV->eraseFromParent();
1263   }
1264
1265   ValueMap[SGA] = NewDA;
1266   return false;
1267 }
1268
1269 static void getArrayElements(Constant *C, SmallVectorImpl<Constant*> &Dest) {
1270   unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements();
1271
1272   for (unsigned i = 0; i != NumElements; ++i)
1273     Dest.push_back(C->getAggregateElement(i));
1274 }
1275
1276 void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) {
1277   // Merge the initializer.
1278   SmallVector<Constant *, 16> DstElements;
1279   getArrayElements(AVI.DstInit, DstElements);
1280
1281   SmallVector<Constant *, 16> SrcElements;
1282   getArrayElements(AVI.SrcInit, SrcElements);
1283
1284   ArrayType *NewType = cast<ArrayType>(AVI.NewGV->getType()->getElementType());
1285
1286   StringRef Name = AVI.NewGV->getName();
1287   bool IsNewStructor =
1288       (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") &&
1289       cast<StructType>(NewType->getElementType())->getNumElements() == 3;
1290
1291   for (auto *V : SrcElements) {
1292     if (IsNewStructor) {
1293       Constant *Key = V->getAggregateElement(2);
1294       if (DoNotLinkFromSource.count(Key))
1295         continue;
1296     }
1297     DstElements.push_back(
1298         MapValue(V, ValueMap, RF_None, &TypeMap, &ValMaterializer));
1299   }
1300   if (IsNewStructor) {
1301     NewType = ArrayType::get(NewType->getElementType(), DstElements.size());
1302     AVI.NewGV->mutateType(PointerType::get(NewType, 0));
1303   }
1304
1305   AVI.NewGV->setInitializer(ConstantArray::get(NewType, DstElements));
1306 }
1307
1308 /// linkGlobalInits - Update the initializers in the Dest module now that all
1309 /// globals that may be referenced are in Dest.
1310 void ModuleLinker::linkGlobalInits() {
1311   // Loop over all of the globals in the src module, mapping them over as we go
1312   for (Module::const_global_iterator I = SrcM->global_begin(),
1313        E = SrcM->global_end(); I != E; ++I) {
1314
1315     // Only process initialized GV's or ones not already in dest.
1316     if (!I->hasInitializer() || DoNotLinkFromSource.count(I)) continue;
1317
1318     // Grab destination global variable.
1319     GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[I]);
1320     // Figure out what the initializer looks like in the dest module.
1321     DGV->setInitializer(MapValue(I->getInitializer(), ValueMap,
1322                                  RF_None, &TypeMap, &ValMaterializer));
1323   }
1324 }
1325
1326 /// linkFunctionBody - Copy the source function over into the dest function and
1327 /// fix up references to values.  At this point we know that Dest is an external
1328 /// function, and that Src is not.
1329 void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) {
1330   assert(Src && Dst && Dst->isDeclaration() && !Src->isDeclaration());
1331
1332   // Go through and convert function arguments over, remembering the mapping.
1333   Function::arg_iterator DI = Dst->arg_begin();
1334   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1335        I != E; ++I, ++DI) {
1336     DI->setName(I->getName());  // Copy the name over.
1337
1338     // Add a mapping to our mapping.
1339     ValueMap[I] = DI;
1340   }
1341
1342   if (Mode == Linker::DestroySource) {
1343     // Splice the body of the source function into the dest function.
1344     Dst->getBasicBlockList().splice(Dst->end(), Src->getBasicBlockList());
1345
1346     // At this point, all of the instructions and values of the function are now
1347     // copied over.  The only problem is that they are still referencing values in
1348     // the Source function as operands.  Loop through all of the operands of the
1349     // functions and patch them up to point to the local versions.
1350     for (Function::iterator BB = Dst->begin(), BE = Dst->end(); BB != BE; ++BB)
1351       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
1352         RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries,
1353                          &TypeMap, &ValMaterializer);
1354
1355   } else {
1356     // Clone the body of the function into the dest function.
1357     SmallVector<ReturnInst*, 8> Returns; // Ignore returns.
1358     CloneFunctionInto(Dst, Src, ValueMap, false, Returns, "", nullptr,
1359                       &TypeMap, &ValMaterializer);
1360   }
1361
1362   // There is no need to map the arguments anymore.
1363   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1364        I != E; ++I)
1365     ValueMap.erase(I);
1366
1367 }
1368
1369 /// linkAliasBodies - Insert all of the aliases in Src into the Dest module.
1370 void ModuleLinker::linkAliasBodies() {
1371   for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end();
1372        I != E; ++I) {
1373     if (DoNotLinkFromSource.count(I))
1374       continue;
1375     if (Constant *Aliasee = I->getAliasee()) {
1376       GlobalAlias *DA = cast<GlobalAlias>(ValueMap[I]);
1377       Constant *Val =
1378           MapValue(Aliasee, ValueMap, RF_None, &TypeMap, &ValMaterializer);
1379       DA->setAliasee(Val);
1380     }
1381   }
1382 }
1383
1384 /// linkNamedMDNodes - Insert all of the named MDNodes in Src into the Dest
1385 /// module.
1386 void ModuleLinker::linkNamedMDNodes() {
1387   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
1388   for (Module::const_named_metadata_iterator I = SrcM->named_metadata_begin(),
1389        E = SrcM->named_metadata_end(); I != E; ++I) {
1390     // Don't link module flags here. Do them separately.
1391     if (&*I == SrcModFlags) continue;
1392     NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(I->getName());
1393     // Add Src elements into Dest node.
1394     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1395       DestNMD->addOperand(MapValue(I->getOperand(i), ValueMap,
1396                                    RF_None, &TypeMap, &ValMaterializer));
1397   }
1398 }
1399
1400 /// linkModuleFlagsMetadata - Merge the linker flags in Src into the Dest
1401 /// module.
1402 bool ModuleLinker::linkModuleFlagsMetadata() {
1403   // If the source module has no module flags, we are done.
1404   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
1405   if (!SrcModFlags) return false;
1406
1407   // If the destination module doesn't have module flags yet, then just copy
1408   // over the source module's flags.
1409   NamedMDNode *DstModFlags = DstM->getOrInsertModuleFlagsMetadata();
1410   if (DstModFlags->getNumOperands() == 0) {
1411     for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I)
1412       DstModFlags->addOperand(SrcModFlags->getOperand(I));
1413
1414     return false;
1415   }
1416
1417   // First build a map of the existing module flags and requirements.
1418   DenseMap<MDString*, MDNode*> Flags;
1419   SmallSetVector<MDNode*, 16> Requirements;
1420   for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) {
1421     MDNode *Op = DstModFlags->getOperand(I);
1422     ConstantInt *Behavior = cast<ConstantInt>(Op->getOperand(0));
1423     MDString *ID = cast<MDString>(Op->getOperand(1));
1424
1425     if (Behavior->getZExtValue() == Module::Require) {
1426       Requirements.insert(cast<MDNode>(Op->getOperand(2)));
1427     } else {
1428       Flags[ID] = Op;
1429     }
1430   }
1431
1432   // Merge in the flags from the source module, and also collect its set of
1433   // requirements.
1434   bool HasErr = false;
1435   for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) {
1436     MDNode *SrcOp = SrcModFlags->getOperand(I);
1437     ConstantInt *SrcBehavior = cast<ConstantInt>(SrcOp->getOperand(0));
1438     MDString *ID = cast<MDString>(SrcOp->getOperand(1));
1439     MDNode *DstOp = Flags.lookup(ID);
1440     unsigned SrcBehaviorValue = SrcBehavior->getZExtValue();
1441
1442     // If this is a requirement, add it and continue.
1443     if (SrcBehaviorValue == Module::Require) {
1444       // If the destination module does not already have this requirement, add
1445       // it.
1446       if (Requirements.insert(cast<MDNode>(SrcOp->getOperand(2)))) {
1447         DstModFlags->addOperand(SrcOp);
1448       }
1449       continue;
1450     }
1451
1452     // If there is no existing flag with this ID, just add it.
1453     if (!DstOp) {
1454       Flags[ID] = SrcOp;
1455       DstModFlags->addOperand(SrcOp);
1456       continue;
1457     }
1458
1459     // Otherwise, perform a merge.
1460     ConstantInt *DstBehavior = cast<ConstantInt>(DstOp->getOperand(0));
1461     unsigned DstBehaviorValue = DstBehavior->getZExtValue();
1462
1463     // If either flag has override behavior, handle it first.
1464     if (DstBehaviorValue == Module::Override) {
1465       // Diagnose inconsistent flags which both have override behavior.
1466       if (SrcBehaviorValue == Module::Override &&
1467           SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1468         HasErr |= emitError("linking module flags '" + ID->getString() +
1469                             "': IDs have conflicting override values");
1470       }
1471       continue;
1472     } else if (SrcBehaviorValue == Module::Override) {
1473       // Update the destination flag to that of the source.
1474       DstOp->replaceOperandWith(0, SrcBehavior);
1475       DstOp->replaceOperandWith(2, SrcOp->getOperand(2));
1476       continue;
1477     }
1478
1479     // Diagnose inconsistent merge behavior types.
1480     if (SrcBehaviorValue != DstBehaviorValue) {
1481       HasErr |= emitError("linking module flags '" + ID->getString() +
1482                           "': IDs have conflicting behaviors");
1483       continue;
1484     }
1485
1486     // Perform the merge for standard behavior types.
1487     switch (SrcBehaviorValue) {
1488     case Module::Require:
1489     case Module::Override: llvm_unreachable("not possible");
1490     case Module::Error: {
1491       // Emit an error if the values differ.
1492       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1493         HasErr |= emitError("linking module flags '" + ID->getString() +
1494                             "': IDs have conflicting values");
1495       }
1496       continue;
1497     }
1498     case Module::Warning: {
1499       // Emit a warning if the values differ.
1500       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1501         emitWarning("linking module flags '" + ID->getString() +
1502                     "': IDs have conflicting values");
1503       }
1504       continue;
1505     }
1506     case Module::Append: {
1507       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1508       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1509       unsigned NumOps = DstValue->getNumOperands() + SrcValue->getNumOperands();
1510       Value **VP, **Values = VP = new Value*[NumOps];
1511       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i, ++VP)
1512         *VP = DstValue->getOperand(i);
1513       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i, ++VP)
1514         *VP = SrcValue->getOperand(i);
1515       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
1516                                                ArrayRef<Value*>(Values,
1517                                                                 NumOps)));
1518       delete[] Values;
1519       break;
1520     }
1521     case Module::AppendUnique: {
1522       SmallSetVector<Value*, 16> Elts;
1523       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1524       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1525       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i)
1526         Elts.insert(DstValue->getOperand(i));
1527       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i)
1528         Elts.insert(SrcValue->getOperand(i));
1529       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
1530                                                ArrayRef<Value*>(Elts.begin(),
1531                                                                 Elts.end())));
1532       break;
1533     }
1534     }
1535   }
1536
1537   // Check all of the requirements.
1538   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
1539     MDNode *Requirement = Requirements[I];
1540     MDString *Flag = cast<MDString>(Requirement->getOperand(0));
1541     Value *ReqValue = Requirement->getOperand(1);
1542
1543     MDNode *Op = Flags[Flag];
1544     if (!Op || Op->getOperand(2) != ReqValue) {
1545       HasErr |= emitError("linking module flags '" + Flag->getString() +
1546                           "': does not have the required value");
1547       continue;
1548     }
1549   }
1550
1551   return HasErr;
1552 }
1553
1554 bool ModuleLinker::run() {
1555   assert(DstM && "Null destination module");
1556   assert(SrcM && "Null source module");
1557
1558   // Inherit the target data from the source module if the destination module
1559   // doesn't have one already.
1560   if (!DstM->getDataLayout() && SrcM->getDataLayout())
1561     DstM->setDataLayout(SrcM->getDataLayout());
1562
1563   // Copy the target triple from the source to dest if the dest's is empty.
1564   if (DstM->getTargetTriple().empty() && !SrcM->getTargetTriple().empty())
1565     DstM->setTargetTriple(SrcM->getTargetTriple());
1566
1567   if (SrcM->getDataLayout() && DstM->getDataLayout() &&
1568       *SrcM->getDataLayout() != *DstM->getDataLayout()) {
1569     emitWarning("Linking two modules of different data layouts: '" +
1570                 SrcM->getModuleIdentifier() + "' is '" +
1571                 SrcM->getDataLayoutStr() + "' whereas '" +
1572                 DstM->getModuleIdentifier() + "' is '" +
1573                 DstM->getDataLayoutStr() + "'\n");
1574   }
1575   if (!SrcM->getTargetTriple().empty() &&
1576       DstM->getTargetTriple() != SrcM->getTargetTriple()) {
1577     emitWarning("Linking two modules of different target triples: " +
1578                 SrcM->getModuleIdentifier() + "' is '" +
1579                 SrcM->getTargetTriple() + "' whereas '" +
1580                 DstM->getModuleIdentifier() + "' is '" +
1581                 DstM->getTargetTriple() + "'\n");
1582   }
1583
1584   // Append the module inline asm string.
1585   if (!SrcM->getModuleInlineAsm().empty()) {
1586     if (DstM->getModuleInlineAsm().empty())
1587       DstM->setModuleInlineAsm(SrcM->getModuleInlineAsm());
1588     else
1589       DstM->setModuleInlineAsm(DstM->getModuleInlineAsm()+"\n"+
1590                                SrcM->getModuleInlineAsm());
1591   }
1592
1593   // Loop over all of the linked values to compute type mappings.
1594   computeTypeMapping();
1595
1596   ComdatsChosen.clear();
1597   for (const StringMapEntry<llvm::Comdat> &SMEC : SrcM->getComdatSymbolTable()) {
1598     const Comdat &C = SMEC.getValue();
1599     if (ComdatsChosen.count(&C))
1600       continue;
1601     Comdat::SelectionKind SK;
1602     bool LinkFromSrc;
1603     if (getComdatResult(&C, SK, LinkFromSrc))
1604       return true;
1605     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
1606   }
1607
1608   // Upgrade mismatched global arrays.
1609   upgradeMismatchedGlobals();
1610
1611   // Insert all of the globals in src into the DstM module... without linking
1612   // initializers (which could refer to functions not yet mapped over).
1613   for (Module::global_iterator I = SrcM->global_begin(),
1614        E = SrcM->global_end(); I != E; ++I)
1615     if (linkGlobalProto(I))
1616       return true;
1617
1618   // Link the functions together between the two modules, without doing function
1619   // bodies... this just adds external function prototypes to the DstM
1620   // function...  We do this so that when we begin processing function bodies,
1621   // all of the global values that may be referenced are available in our
1622   // ValueMap.
1623   for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I)
1624     if (linkFunctionProto(I))
1625       return true;
1626
1627   // If there were any aliases, link them now.
1628   for (Module::alias_iterator I = SrcM->alias_begin(),
1629        E = SrcM->alias_end(); I != E; ++I)
1630     if (linkAliasProto(I))
1631       return true;
1632
1633   for (unsigned i = 0, e = AppendingVars.size(); i != e; ++i)
1634     linkAppendingVarInit(AppendingVars[i]);
1635
1636   // Link in the function bodies that are defined in the source module into
1637   // DstM.
1638   for (Module::iterator SF = SrcM->begin(), E = SrcM->end(); SF != E; ++SF) {
1639     // Skip if not linking from source.
1640     if (DoNotLinkFromSource.count(SF)) continue;
1641
1642     Function *DF = cast<Function>(ValueMap[SF]);
1643     if (SF->hasPrefixData()) {
1644       // Link in the prefix data.
1645       DF->setPrefixData(MapValue(
1646           SF->getPrefixData(), ValueMap, RF_None, &TypeMap, &ValMaterializer));
1647     }
1648
1649     // Materialize if needed.
1650     if (SF->isMaterializable()) {
1651       if (std::error_code EC = SF->materialize())
1652         return emitError(EC.message());
1653     }
1654
1655     // Skip if no body (function is external).
1656     if (SF->isDeclaration())
1657       continue;
1658
1659     linkFunctionBody(DF, SF);
1660     SF->Dematerialize();
1661   }
1662
1663   // Resolve all uses of aliases with aliasees.
1664   linkAliasBodies();
1665
1666   // Remap all of the named MDNodes in Src into the DstM module. We do this
1667   // after linking GlobalValues so that MDNodes that reference GlobalValues
1668   // are properly remapped.
1669   linkNamedMDNodes();
1670
1671   // Merge the module flags into the DstM module.
1672   if (linkModuleFlagsMetadata())
1673     return true;
1674
1675   // Update the initializers in the DstM module now that all globals that may
1676   // be referenced are in DstM.
1677   linkGlobalInits();
1678
1679   // Process vector of lazily linked in functions.
1680   bool LinkedInAnyFunctions;
1681   do {
1682     LinkedInAnyFunctions = false;
1683
1684     for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
1685         E = LazilyLinkFunctions.end(); I != E; ++I) {
1686       Function *SF = *I;
1687       if (!SF)
1688         continue;
1689
1690       Function *DF = cast<Function>(ValueMap[SF]);
1691       if (SF->hasPrefixData()) {
1692         // Link in the prefix data.
1693         DF->setPrefixData(MapValue(SF->getPrefixData(),
1694                                    ValueMap,
1695                                    RF_None,
1696                                    &TypeMap,
1697                                    &ValMaterializer));
1698       }
1699
1700       // Materialize if needed.
1701       if (SF->isMaterializable()) {
1702         if (std::error_code EC = SF->materialize())
1703           return emitError(EC.message());
1704       }
1705
1706       // Skip if no body (function is external).
1707       if (SF->isDeclaration())
1708         continue;
1709
1710       // Erase from vector *before* the function body is linked - linkFunctionBody could
1711       // invalidate I.
1712       LazilyLinkFunctions.erase(I);
1713
1714       // Link in function body.
1715       linkFunctionBody(DF, SF);
1716       SF->Dematerialize();
1717
1718       // Set flag to indicate we may have more functions to lazily link in
1719       // since we linked in a function.
1720       LinkedInAnyFunctions = true;
1721       break;
1722     }
1723   } while (LinkedInAnyFunctions);
1724
1725   // Now that all of the types from the source are used, resolve any structs
1726   // copied over to the dest that didn't exist there.
1727   TypeMap.linkDefinedTypeBodies();
1728
1729   return false;
1730 }
1731
1732 Linker::Linker(Module *M) : Composite(M) {
1733   TypeFinder StructTypes;
1734   StructTypes.run(*M, true);
1735   IdentifiedStructTypes.insert(StructTypes.begin(), StructTypes.end());
1736 }
1737
1738 Linker::~Linker() {
1739 }
1740
1741 void Linker::deleteModule() {
1742   delete Composite;
1743   Composite = nullptr;
1744 }
1745
1746 bool Linker::linkInModule(Module *Src, unsigned Mode) {
1747   ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src, Mode);
1748   return TheLinker.run();
1749 }
1750
1751 //===----------------------------------------------------------------------===//
1752 // LinkModules entrypoint.
1753 //===----------------------------------------------------------------------===//
1754
1755 /// LinkModules - This function links two modules together, with the resulting
1756 /// Dest module modified to be the composite of the two input modules.  If an
1757 /// error occurs, true is returned and ErrorMsg (if not null) is set to indicate
1758 /// the problem.  Upon failure, the Dest module could be in a modified state,
1759 /// and shouldn't be relied on to be consistent.
1760 bool Linker::LinkModules(Module *Dest, Module *Src, unsigned Mode) {
1761   Linker L(Dest);
1762   return L.linkInModule(Src, Mode);
1763 }
1764
1765 //===----------------------------------------------------------------------===//
1766 // C API.
1767 //===----------------------------------------------------------------------===//
1768
1769 static void bindingDiagnosticHandler(const llvm::DiagnosticInfo &DI,
1770                                      void *Context) {
1771   if (DI.getSeverity() != DS_Error)
1772     return;
1773
1774   std::string *Message = (std::string *)Context;
1775   {
1776     raw_string_ostream Stream(*Message);
1777     DiagnosticPrinterRawOStream DP(Stream);
1778     DI.print(DP);
1779   }
1780 }
1781
1782
1783 LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src,
1784                          LLVMLinkerMode Mode, char **OutMessages) {
1785   Module *D = unwrap(Dest);
1786   LLVMContext &Ctx = D->getContext();
1787
1788   LLVMContext::DiagnosticHandlerTy OldHandler = Ctx.getDiagnosticHandler();
1789   void *OldDiagnosticContext = Ctx.getDiagnosticContext();
1790   std::string Message;
1791   Ctx.setDiagnosticHandler(bindingDiagnosticHandler, &Message);
1792   LLVMBool Result = Linker::LinkModules(D, unwrap(Src), Mode);
1793   Ctx.setDiagnosticHandler(OldHandler, OldDiagnosticContext);
1794
1795   if (OutMessages && Result)
1796     *OutMessages = strdup(Message.c_str());
1797   return Result;
1798 }