1//===- lib/Linker/IRMover.cpp ---------------------------------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include "llvm/Linker/IRMover.h" 10#include "LinkDiagnosticInfo.h" 11#include "llvm/ADT/SetVector.h" 12#include "llvm/ADT/SmallString.h" 13#include "llvm/ADT/Triple.h" 14#include "llvm/IR/Constants.h" 15#include "llvm/IR/DebugInfo.h" 16#include "llvm/IR/DiagnosticPrinter.h" 17#include "llvm/IR/GVMaterializer.h" 18#include "llvm/IR/Intrinsics.h" 19#include "llvm/IR/TypeFinder.h" 20#include "llvm/Object/ModuleSymbolTable.h" 21#include "llvm/Support/Error.h" 22#include "llvm/Transforms/Utils/Cloning.h" 23#include <utility> 24using namespace llvm; 25 26//===----------------------------------------------------------------------===// 27// TypeMap implementation. 28//===----------------------------------------------------------------------===// 29 30namespace { 31class TypeMapTy : public ValueMapTypeRemapper { 32 /// This is a mapping from a source type to a destination type to use. 33 DenseMap<Type *, Type *> MappedTypes; 34 35 /// When checking to see if two subgraphs are isomorphic, we speculatively 36 /// add types to MappedTypes, but keep track of them here in case we need to 37 /// roll back. 38 SmallVector<Type *, 16> SpeculativeTypes; 39 40 SmallVector<StructType *, 16> SpeculativeDstOpaqueTypes; 41 42 /// This is a list of non-opaque structs in the source module that are mapped 43 /// to an opaque struct in the destination module. 44 SmallVector<StructType *, 16> SrcDefinitionsToResolve; 45 46 /// This is the set of opaque types in the destination modules who are 47 /// getting a body from the source module. 48 SmallPtrSet<StructType *, 16> DstResolvedOpaqueTypes; 49 50public: 51 TypeMapTy(IRMover::IdentifiedStructTypeSet &DstStructTypesSet) 52 : DstStructTypesSet(DstStructTypesSet) {} 53 54 IRMover::IdentifiedStructTypeSet &DstStructTypesSet; 55 /// Indicate that the specified type in the destination module is conceptually 56 /// equivalent to the specified type in the source module. 57 void addTypeMapping(Type *DstTy, Type *SrcTy); 58 59 /// Produce a body for an opaque type in the dest module from a type 60 /// definition in the source module. 61 void linkDefinedTypeBodies(); 62 63 /// Return the mapped type to use for the specified input type from the 64 /// source module. 65 Type *get(Type *SrcTy); 66 Type *get(Type *SrcTy, SmallPtrSet<StructType *, 8> &Visited); 67 68 void finishType(StructType *DTy, StructType *STy, ArrayRef<Type *> ETypes); 69 70 FunctionType *get(FunctionType *T) { 71 return cast<FunctionType>(get((Type *)T)); 72 } 73 74private: 75 Type *remapType(Type *SrcTy) override { return get(SrcTy); } 76 77 bool areTypesIsomorphic(Type *DstTy, Type *SrcTy); 78}; 79} 80 81void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) { 82 assert(SpeculativeTypes.empty()); 83 assert(SpeculativeDstOpaqueTypes.empty()); 84 85 // Check to see if these types are recursively isomorphic and establish a 86 // mapping between them if so. 87 if (!areTypesIsomorphic(DstTy, SrcTy)) { 88 // Oops, they aren't isomorphic. Just discard this request by rolling out 89 // any speculative mappings we've established. 90 for (Type *Ty : SpeculativeTypes) 91 MappedTypes.erase(Ty); 92 93 SrcDefinitionsToResolve.resize(SrcDefinitionsToResolve.size() - 94 SpeculativeDstOpaqueTypes.size()); 95 for (StructType *Ty : SpeculativeDstOpaqueTypes) 96 DstResolvedOpaqueTypes.erase(Ty); 97 } else { 98 // SrcTy and DstTy are recursively ismorphic. We clear names of SrcTy 99 // and all its descendants to lower amount of renaming in LLVM context 100 // Renaming occurs because we load all source modules to the same context 101 // and declaration with existing name gets renamed (i.e Foo -> Foo.42). 102 // As a result we may get several different types in the destination 103 // module, which are in fact the same. 104 for (Type *Ty : SpeculativeTypes) 105 if (auto *STy = dyn_cast<StructType>(Ty)) 106 if (STy->hasName()) 107 STy->setName(""); 108 } 109 SpeculativeTypes.clear(); 110 SpeculativeDstOpaqueTypes.clear(); 111} 112 113/// Recursively walk this pair of types, returning true if they are isomorphic, 114/// false if they are not. 115bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) { 116 // Two types with differing kinds are clearly not isomorphic. 117 if (DstTy->getTypeID() != SrcTy->getTypeID()) 118 return false; 119 120 // If we have an entry in the MappedTypes table, then we have our answer. 121 Type *&Entry = MappedTypes[SrcTy]; 122 if (Entry) 123 return Entry == DstTy; 124 125 // Two identical types are clearly isomorphic. Remember this 126 // non-speculatively. 127 if (DstTy == SrcTy) { 128 Entry = DstTy; 129 return true; 130 } 131 132 // Okay, we have two types with identical kinds that we haven't seen before. 133 134 // If this is an opaque struct type, special case it. 135 if (StructType *SSTy = dyn_cast<StructType>(SrcTy)) { 136 // Mapping an opaque type to any struct, just keep the dest struct. 137 if (SSTy->isOpaque()) { 138 Entry = DstTy; 139 SpeculativeTypes.push_back(SrcTy); 140 return true; 141 } 142 143 // Mapping a non-opaque source type to an opaque dest. If this is the first 144 // type that we're mapping onto this destination type then we succeed. Keep 145 // the dest, but fill it in later. If this is the second (different) type 146 // that we're trying to map onto the same opaque type then we fail. 147 if (cast<StructType>(DstTy)->isOpaque()) { 148 // We can only map one source type onto the opaque destination type. 149 if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)).second) 150 return false; 151 SrcDefinitionsToResolve.push_back(SSTy); 152 SpeculativeTypes.push_back(SrcTy); 153 SpeculativeDstOpaqueTypes.push_back(cast<StructType>(DstTy)); 154 Entry = DstTy; 155 return true; 156 } 157 } 158 159 // If the number of subtypes disagree between the two types, then we fail. 160 if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes()) 161 return false; 162 163 // Fail if any of the extra properties (e.g. array size) of the type disagree. 164 if (isa<IntegerType>(DstTy)) 165 return false; // bitwidth disagrees. 166 if (PointerType *PT = dyn_cast<PointerType>(DstTy)) { 167 if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace()) 168 return false; 169 } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) { 170 if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg()) 171 return false; 172 } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) { 173 StructType *SSTy = cast<StructType>(SrcTy); 174 if (DSTy->isLiteral() != SSTy->isLiteral() || 175 DSTy->isPacked() != SSTy->isPacked()) 176 return false; 177 } else if (auto *DArrTy = dyn_cast<ArrayType>(DstTy)) { 178 if (DArrTy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements()) 179 return false; 180 } else if (auto *DVecTy = dyn_cast<VectorType>(DstTy)) { 181 if (DVecTy->getElementCount() != cast<VectorType>(SrcTy)->getElementCount()) 182 return false; 183 } 184 185 // Otherwise, we speculate that these two types will line up and recursively 186 // check the subelements. 187 Entry = DstTy; 188 SpeculativeTypes.push_back(SrcTy); 189 190 for (unsigned I = 0, E = SrcTy->getNumContainedTypes(); I != E; ++I) 191 if (!areTypesIsomorphic(DstTy->getContainedType(I), 192 SrcTy->getContainedType(I))) 193 return false; 194 195 // If everything seems to have lined up, then everything is great. 196 return true; 197} 198 199void TypeMapTy::linkDefinedTypeBodies() { 200 SmallVector<Type *, 16> Elements; 201 for (StructType *SrcSTy : SrcDefinitionsToResolve) { 202 StructType *DstSTy = cast<StructType>(MappedTypes[SrcSTy]); 203 assert(DstSTy->isOpaque()); 204 205 // Map the body of the source type over to a new body for the dest type. 206 Elements.resize(SrcSTy->getNumElements()); 207 for (unsigned I = 0, E = Elements.size(); I != E; ++I) 208 Elements[I] = get(SrcSTy->getElementType(I)); 209 210 DstSTy->setBody(Elements, SrcSTy->isPacked()); 211 DstStructTypesSet.switchToNonOpaque(DstSTy); 212 } 213 SrcDefinitionsToResolve.clear(); 214 DstResolvedOpaqueTypes.clear(); 215} 216 217void TypeMapTy::finishType(StructType *DTy, StructType *STy, 218 ArrayRef<Type *> ETypes) { 219 DTy->setBody(ETypes, STy->isPacked()); 220 221 // Steal STy's name. 222 if (STy->hasName()) { 223 SmallString<16> TmpName = STy->getName(); 224 STy->setName(""); 225 DTy->setName(TmpName); 226 } 227 228 DstStructTypesSet.addNonOpaque(DTy); 229} 230 231Type *TypeMapTy::get(Type *Ty) { 232 SmallPtrSet<StructType *, 8> Visited; 233 return get(Ty, Visited); 234} 235 236Type *TypeMapTy::get(Type *Ty, SmallPtrSet<StructType *, 8> &Visited) { 237 // If we already have an entry for this type, return it. 238 Type **Entry = &MappedTypes[Ty]; 239 if (*Entry) 240 return *Entry; 241 242 // These are types that LLVM itself will unique. 243 bool IsUniqued = !isa<StructType>(Ty) || cast<StructType>(Ty)->isLiteral(); 244 245 if (!IsUniqued) { 246#ifndef NDEBUG 247 for (auto &Pair : MappedTypes) { 248 assert(!(Pair.first != Ty && Pair.second == Ty) && 249 "mapping to a source type"); 250 } 251#endif 252 253 if (!Visited.insert(cast<StructType>(Ty)).second) { 254 StructType *DTy = StructType::create(Ty->getContext()); 255 return *Entry = DTy; 256 } 257 } 258 259 // If this is not a recursive type, then just map all of the elements and 260 // then rebuild the type from inside out. 261 SmallVector<Type *, 4> ElementTypes; 262 263 // If there are no element types to map, then the type is itself. This is 264 // true for the anonymous {} struct, things like 'float', integers, etc. 265 if (Ty->getNumContainedTypes() == 0 && IsUniqued) 266 return *Entry = Ty; 267 268 // Remap all of the elements, keeping track of whether any of them change. 269 bool AnyChange = false; 270 ElementTypes.resize(Ty->getNumContainedTypes()); 271 for (unsigned I = 0, E = Ty->getNumContainedTypes(); I != E; ++I) { 272 ElementTypes[I] = get(Ty->getContainedType(I), Visited); 273 AnyChange |= ElementTypes[I] != Ty->getContainedType(I); 274 } 275 276 // If we found our type while recursively processing stuff, just use it. 277 Entry = &MappedTypes[Ty]; 278 if (*Entry) { 279 if (auto *DTy = dyn_cast<StructType>(*Entry)) { 280 if (DTy->isOpaque()) { 281 auto *STy = cast<StructType>(Ty); 282 finishType(DTy, STy, ElementTypes); 283 } 284 } 285 return *Entry; 286 } 287 288 // If all of the element types mapped directly over and the type is not 289 // a named struct, then the type is usable as-is. 290 if (!AnyChange && IsUniqued) 291 return *Entry = Ty; 292 293 // Otherwise, rebuild a modified type. 294 switch (Ty->getTypeID()) { 295 default: 296 llvm_unreachable("unknown derived type to remap"); 297 case Type::ArrayTyID: 298 return *Entry = ArrayType::get(ElementTypes[0], 299 cast<ArrayType>(Ty)->getNumElements()); 300 case Type::ScalableVectorTyID: 301 case Type::FixedVectorTyID: 302 return *Entry = VectorType::get(ElementTypes[0], 303 cast<VectorType>(Ty)->getElementCount()); 304 case Type::PointerTyID: 305 return *Entry = PointerType::get(ElementTypes[0], 306 cast<PointerType>(Ty)->getAddressSpace()); 307 case Type::FunctionTyID: 308 return *Entry = FunctionType::get(ElementTypes[0], 309 makeArrayRef(ElementTypes).slice(1), 310 cast<FunctionType>(Ty)->isVarArg()); 311 case Type::StructTyID: { 312 auto *STy = cast<StructType>(Ty); 313 bool IsPacked = STy->isPacked(); 314 if (IsUniqued) 315 return *Entry = StructType::get(Ty->getContext(), ElementTypes, IsPacked); 316 317 // If the type is opaque, we can just use it directly. 318 if (STy->isOpaque()) { 319 DstStructTypesSet.addOpaque(STy); 320 return *Entry = Ty; 321 } 322 323 if (StructType *OldT = 324 DstStructTypesSet.findNonOpaque(ElementTypes, IsPacked)) { 325 STy->setName(""); 326 return *Entry = OldT; 327 } 328 329 if (!AnyChange) { 330 DstStructTypesSet.addNonOpaque(STy); 331 return *Entry = Ty; 332 } 333 334 StructType *DTy = StructType::create(Ty->getContext()); 335 finishType(DTy, STy, ElementTypes); 336 return *Entry = DTy; 337 } 338 } 339} 340 341LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity, 342 const Twine &Msg) 343 : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {} 344void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; } 345 346//===----------------------------------------------------------------------===// 347// IRLinker implementation. 348//===----------------------------------------------------------------------===// 349 350namespace { 351class IRLinker; 352 353/// Creates prototypes for functions that are lazily linked on the fly. This 354/// speeds up linking for modules with many/ lazily linked functions of which 355/// few get used. 356class GlobalValueMaterializer final : public ValueMaterializer { 357 IRLinker &TheIRLinker; 358 359public: 360 GlobalValueMaterializer(IRLinker &TheIRLinker) : TheIRLinker(TheIRLinker) {} 361 Value *materialize(Value *V) override; 362}; 363 364class LocalValueMaterializer final : public ValueMaterializer { 365 IRLinker &TheIRLinker; 366 367public: 368 LocalValueMaterializer(IRLinker &TheIRLinker) : TheIRLinker(TheIRLinker) {} 369 Value *materialize(Value *V) override; 370}; 371 372/// Type of the Metadata map in \a ValueToValueMapTy. 373typedef DenseMap<const Metadata *, TrackingMDRef> MDMapT; 374 375/// This is responsible for keeping track of the state used for moving data 376/// from SrcM to DstM. 377class IRLinker { 378 Module &DstM; 379 std::unique_ptr<Module> SrcM; 380 381 /// See IRMover::move(). 382 std::function<void(GlobalValue &, IRMover::ValueAdder)> AddLazyFor; 383 384 TypeMapTy TypeMap; 385 GlobalValueMaterializer GValMaterializer; 386 LocalValueMaterializer LValMaterializer; 387 388 /// A metadata map that's shared between IRLinker instances. 389 MDMapT &SharedMDs; 390 391 /// Mapping of values from what they used to be in Src, to what they are now 392 /// in DstM. ValueToValueMapTy is a ValueMap, which involves some overhead 393 /// due to the use of Value handles which the Linker doesn't actually need, 394 /// but this allows us to reuse the ValueMapper code. 395 ValueToValueMapTy ValueMap; 396 ValueToValueMapTy IndirectSymbolValueMap; 397 398 DenseSet<GlobalValue *> ValuesToLink; 399 std::vector<GlobalValue *> Worklist; 400 std::vector<std::pair<GlobalValue *, Value*>> RAUWWorklist; 401 402 void maybeAdd(GlobalValue *GV) { 403 if (ValuesToLink.insert(GV).second) 404 Worklist.push_back(GV); 405 } 406 407 /// Whether we are importing globals for ThinLTO, as opposed to linking the 408 /// source module. If this flag is set, it means that we can rely on some 409 /// other object file to define any non-GlobalValue entities defined by the 410 /// source module. This currently causes us to not link retained types in 411 /// debug info metadata and module inline asm. 412 bool IsPerformingImport; 413 414 /// Set to true when all global value body linking is complete (including 415 /// lazy linking). Used to prevent metadata linking from creating new 416 /// references. 417 bool DoneLinkingBodies = false; 418 419 /// The Error encountered during materialization. We use an Optional here to 420 /// avoid needing to manage an unconsumed success value. 421 Optional<Error> FoundError; 422 void setError(Error E) { 423 if (E) 424 FoundError = std::move(E); 425 } 426 427 /// Most of the errors produced by this module are inconvertible StringErrors. 428 /// This convenience function lets us return one of those more easily. 429 Error stringErr(const Twine &T) { 430 return make_error<StringError>(T, inconvertibleErrorCode()); 431 } 432 433 /// Entry point for mapping values and alternate context for mapping aliases. 434 ValueMapper Mapper; 435 unsigned IndirectSymbolMCID; 436 437 /// Handles cloning of a global values from the source module into 438 /// the destination module, including setting the attributes and visibility. 439 GlobalValue *copyGlobalValueProto(const GlobalValue *SGV, bool ForDefinition); 440 441 void emitWarning(const Twine &Message) { 442 SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Warning, Message)); 443 } 444 445 /// Given a global in the source module, return the global in the 446 /// destination module that is being linked to, if any. 447 GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) { 448 // If the source has no name it can't link. If it has local linkage, 449 // there is no name match-up going on. 450 if (!SrcGV->hasName() || SrcGV->hasLocalLinkage()) 451 return nullptr; 452 453 // Otherwise see if we have a match in the destination module's symtab. 454 GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName()); 455 if (!DGV) 456 return nullptr; 457 458 // If we found a global with the same name in the dest module, but it has 459 // internal linkage, we are really not doing any linkage here. 460 if (DGV->hasLocalLinkage()) 461 return nullptr; 462 463 // If we found an intrinsic declaration with mismatching prototypes, we 464 // probably had a nameclash. Don't use that version. 465 if (auto *FDGV = dyn_cast<Function>(DGV)) 466 if (FDGV->isIntrinsic()) 467 if (const auto *FSrcGV = dyn_cast<Function>(SrcGV)) 468 if (FDGV->getFunctionType() != TypeMap.get(FSrcGV->getFunctionType())) 469 return nullptr; 470 471 // Otherwise, we do in fact link to the destination global. 472 return DGV; 473 } 474 475 void computeTypeMapping(); 476 477 Expected<Constant *> linkAppendingVarProto(GlobalVariable *DstGV, 478 const GlobalVariable *SrcGV); 479 480 /// Given the GlobaValue \p SGV in the source module, and the matching 481 /// GlobalValue \p DGV (if any), return true if the linker will pull \p SGV 482 /// into the destination module. 483 /// 484 /// Note this code may call the client-provided \p AddLazyFor. 485 bool shouldLink(GlobalValue *DGV, GlobalValue &SGV); 486 Expected<Constant *> linkGlobalValueProto(GlobalValue *GV, 487 bool ForIndirectSymbol); 488 489 Error linkModuleFlagsMetadata(); 490 491 void linkGlobalVariable(GlobalVariable &Dst, GlobalVariable &Src); 492 Error linkFunctionBody(Function &Dst, Function &Src); 493 void linkIndirectSymbolBody(GlobalIndirectSymbol &Dst, 494 GlobalIndirectSymbol &Src); 495 Error linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src); 496 497 /// Replace all types in the source AttributeList with the 498 /// corresponding destination type. 499 AttributeList mapAttributeTypes(LLVMContext &C, AttributeList Attrs); 500 501 /// Functions that take care of cloning a specific global value type 502 /// into the destination module. 503 GlobalVariable *copyGlobalVariableProto(const GlobalVariable *SGVar); 504 Function *copyFunctionProto(const Function *SF); 505 GlobalValue *copyGlobalIndirectSymbolProto(const GlobalIndirectSymbol *SGIS); 506 507 /// Perform "replace all uses with" operations. These work items need to be 508 /// performed as part of materialization, but we postpone them to happen after 509 /// materialization is done. The materializer called by ValueMapper is not 510 /// expected to delete constants, as ValueMapper is holding pointers to some 511 /// of them, but constant destruction may be indirectly triggered by RAUW. 512 /// Hence, the need to move this out of the materialization call chain. 513 void flushRAUWWorklist(); 514 515 /// When importing for ThinLTO, prevent importing of types listed on 516 /// the DICompileUnit that we don't need a copy of in the importing 517 /// module. 518 void prepareCompileUnitsForImport(); 519 void linkNamedMDNodes(); 520 521public: 522 IRLinker(Module &DstM, MDMapT &SharedMDs, 523 IRMover::IdentifiedStructTypeSet &Set, std::unique_ptr<Module> SrcM, 524 ArrayRef<GlobalValue *> ValuesToLink, 525 std::function<void(GlobalValue &, IRMover::ValueAdder)> AddLazyFor, 526 bool IsPerformingImport) 527 : DstM(DstM), SrcM(std::move(SrcM)), AddLazyFor(std::move(AddLazyFor)), 528 TypeMap(Set), GValMaterializer(*this), LValMaterializer(*this), 529 SharedMDs(SharedMDs), IsPerformingImport(IsPerformingImport), 530 Mapper(ValueMap, RF_ReuseAndMutateDistinctMDs | RF_IgnoreMissingLocals, 531 &TypeMap, &GValMaterializer), 532 IndirectSymbolMCID(Mapper.registerAlternateMappingContext( 533 IndirectSymbolValueMap, &LValMaterializer)) { 534 ValueMap.getMDMap() = std::move(SharedMDs); 535 for (GlobalValue *GV : ValuesToLink) 536 maybeAdd(GV); 537 if (IsPerformingImport) 538 prepareCompileUnitsForImport(); 539 } 540 ~IRLinker() { SharedMDs = std::move(*ValueMap.getMDMap()); } 541 542 Error run(); 543 Value *materialize(Value *V, bool ForIndirectSymbol); 544}; 545} 546 547/// The LLVM SymbolTable class autorenames globals that conflict in the symbol 548/// table. This is good for all clients except for us. Go through the trouble 549/// to force this back. 550static void forceRenaming(GlobalValue *GV, StringRef Name) { 551 // If the global doesn't force its name or if it already has the right name, 552 // there is nothing for us to do. 553 if (GV->hasLocalLinkage() || GV->getName() == Name) 554 return; 555 556 Module *M = GV->getParent(); 557 558 // If there is a conflict, rename the conflict. 559 if (GlobalValue *ConflictGV = M->getNamedValue(Name)) { 560 GV->takeName(ConflictGV); 561 ConflictGV->setName(Name); // This will cause ConflictGV to get renamed 562 assert(ConflictGV->getName() != Name && "forceRenaming didn't work"); 563 } else { 564 GV->setName(Name); // Force the name back 565 } 566} 567 568Value *GlobalValueMaterializer::materialize(Value *SGV) { 569 return TheIRLinker.materialize(SGV, false); 570} 571 572Value *LocalValueMaterializer::materialize(Value *SGV) { 573 return TheIRLinker.materialize(SGV, true); 574} 575 576Value *IRLinker::materialize(Value *V, bool ForIndirectSymbol) { 577 auto *SGV = dyn_cast<GlobalValue>(V); 578 if (!SGV) 579 return nullptr; 580 581 // When linking a global from other modules than source & dest, skip 582 // materializing it because it would be mapped later when its containing 583 // module is linked. Linking it now would potentially pull in many types that 584 // may not be mapped properly. 585 if (SGV->getParent() != &DstM && SGV->getParent() != SrcM.get()) 586 return nullptr; 587 588 Expected<Constant *> NewProto = linkGlobalValueProto(SGV, ForIndirectSymbol); 589 if (!NewProto) { 590 setError(NewProto.takeError()); 591 return nullptr; 592 } 593 if (!*NewProto) 594 return nullptr; 595 596 GlobalValue *New = dyn_cast<GlobalValue>(*NewProto); 597 if (!New) 598 return *NewProto; 599 600 // If we already created the body, just return. 601 if (auto *F = dyn_cast<Function>(New)) { 602 if (!F->isDeclaration()) 603 return New; 604 } else if (auto *V = dyn_cast<GlobalVariable>(New)) { 605 if (V->hasInitializer() || V->hasAppendingLinkage()) 606 return New; 607 } else { 608 auto *IS = cast<GlobalIndirectSymbol>(New); 609 if (IS->getIndirectSymbol()) 610 return New; 611 } 612 613 // If the global is being linked for an indirect symbol, it may have already 614 // been scheduled to satisfy a regular symbol. Similarly, a global being linked 615 // for a regular symbol may have already been scheduled for an indirect 616 // symbol. Check for these cases by looking in the other value map and 617 // confirming the same value has been scheduled. If there is an entry in the 618 // ValueMap but the value is different, it means that the value already had a 619 // definition in the destination module (linkonce for instance), but we need a 620 // new definition for the indirect symbol ("New" will be different). 621 if ((ForIndirectSymbol && ValueMap.lookup(SGV) == New) || 622 (!ForIndirectSymbol && IndirectSymbolValueMap.lookup(SGV) == New)) 623 return New; 624 625 if (ForIndirectSymbol || shouldLink(New, *SGV)) 626 setError(linkGlobalValueBody(*New, *SGV)); 627 628 return New; 629} 630 631/// Loop through the global variables in the src module and merge them into the 632/// dest module. 633GlobalVariable *IRLinker::copyGlobalVariableProto(const GlobalVariable *SGVar) { 634 // No linking to be performed or linking from the source: simply create an 635 // identical version of the symbol over in the dest module... the 636 // initializer will be filled in later by LinkGlobalInits. 637 GlobalVariable *NewDGV = 638 new GlobalVariable(DstM, TypeMap.get(SGVar->getValueType()), 639 SGVar->isConstant(), GlobalValue::ExternalLinkage, 640 /*init*/ nullptr, SGVar->getName(), 641 /*insertbefore*/ nullptr, SGVar->getThreadLocalMode(), 642 SGVar->getAddressSpace()); 643 NewDGV->setAlignment(MaybeAlign(SGVar->getAlignment())); 644 NewDGV->copyAttributesFrom(SGVar); 645 return NewDGV; 646} 647 648AttributeList IRLinker::mapAttributeTypes(LLVMContext &C, AttributeList Attrs) { 649 for (unsigned i = 0; i < Attrs.getNumAttrSets(); ++i) { 650 for (Attribute::AttrKind TypedAttr : 651 {Attribute::ByVal, Attribute::StructRet, Attribute::ByRef, 652 Attribute::InAlloca}) { 653 if (Attrs.hasAttribute(i, TypedAttr)) { 654 if (Type *Ty = Attrs.getAttribute(i, TypedAttr).getValueAsType()) { 655 Attrs = Attrs.replaceAttributeType(C, i, TypedAttr, TypeMap.get(Ty)); 656 break; 657 } 658 } 659 } 660 } 661 return Attrs; 662} 663 664/// Link the function in the source module into the destination module if 665/// needed, setting up mapping information. 666Function *IRLinker::copyFunctionProto(const Function *SF) { 667 // If there is no linkage to be performed or we are linking from the source, 668 // bring SF over. 669 auto *F = Function::Create(TypeMap.get(SF->getFunctionType()), 670 GlobalValue::ExternalLinkage, 671 SF->getAddressSpace(), SF->getName(), &DstM); 672 F->copyAttributesFrom(SF); 673 F->setAttributes(mapAttributeTypes(F->getContext(), F->getAttributes())); 674 return F; 675} 676 677/// Set up prototypes for any indirect symbols that come over from the source 678/// module. 679GlobalValue * 680IRLinker::copyGlobalIndirectSymbolProto(const GlobalIndirectSymbol *SGIS) { 681 // If there is no linkage to be performed or we're linking from the source, 682 // bring over SGA. 683 auto *Ty = TypeMap.get(SGIS->getValueType()); 684 GlobalIndirectSymbol *GIS; 685 if (isa<GlobalAlias>(SGIS)) 686 GIS = GlobalAlias::create(Ty, SGIS->getAddressSpace(), 687 GlobalValue::ExternalLinkage, SGIS->getName(), 688 &DstM); 689 else 690 GIS = GlobalIFunc::create(Ty, SGIS->getAddressSpace(), 691 GlobalValue::ExternalLinkage, SGIS->getName(), 692 nullptr, &DstM); 693 GIS->copyAttributesFrom(SGIS); 694 return GIS; 695} 696 697GlobalValue *IRLinker::copyGlobalValueProto(const GlobalValue *SGV, 698 bool ForDefinition) { 699 GlobalValue *NewGV; 700 if (auto *SGVar = dyn_cast<GlobalVariable>(SGV)) { 701 NewGV = copyGlobalVariableProto(SGVar); 702 } else if (auto *SF = dyn_cast<Function>(SGV)) { 703 NewGV = copyFunctionProto(SF); 704 } else { 705 if (ForDefinition) 706 NewGV = copyGlobalIndirectSymbolProto(cast<GlobalIndirectSymbol>(SGV)); 707 else if (SGV->getValueType()->isFunctionTy()) 708 NewGV = 709 Function::Create(cast<FunctionType>(TypeMap.get(SGV->getValueType())), 710 GlobalValue::ExternalLinkage, SGV->getAddressSpace(), 711 SGV->getName(), &DstM); 712 else 713 NewGV = 714 new GlobalVariable(DstM, TypeMap.get(SGV->getValueType()), 715 /*isConstant*/ false, GlobalValue::ExternalLinkage, 716 /*init*/ nullptr, SGV->getName(), 717 /*insertbefore*/ nullptr, 718 SGV->getThreadLocalMode(), SGV->getAddressSpace()); 719 } 720 721 if (ForDefinition) 722 NewGV->setLinkage(SGV->getLinkage()); 723 else if (SGV->hasExternalWeakLinkage()) 724 NewGV->setLinkage(GlobalValue::ExternalWeakLinkage); 725 726 if (auto *NewGO = dyn_cast<GlobalObject>(NewGV)) { 727 // Metadata for global variables and function declarations is copied eagerly. 728 if (isa<GlobalVariable>(SGV) || SGV->isDeclaration()) 729 NewGO->copyMetadata(cast<GlobalObject>(SGV), 0); 730 } 731 732 // Remove these copied constants in case this stays a declaration, since 733 // they point to the source module. If the def is linked the values will 734 // be mapped in during linkFunctionBody. 735 if (auto *NewF = dyn_cast<Function>(NewGV)) { 736 NewF->setPersonalityFn(nullptr); 737 NewF->setPrefixData(nullptr); 738 NewF->setPrologueData(nullptr); 739 } 740 741 return NewGV; 742} 743 744static StringRef getTypeNamePrefix(StringRef Name) { 745 size_t DotPos = Name.rfind('.'); 746 return (DotPos == 0 || DotPos == StringRef::npos || Name.back() == '.' || 747 !isdigit(static_cast<unsigned char>(Name[DotPos + 1]))) 748 ? Name 749 : Name.substr(0, DotPos); 750} 751 752/// Loop over all of the linked values to compute type mappings. For example, 753/// if we link "extern Foo *x" and "Foo *x = NULL", then we have two struct 754/// types 'Foo' but one got renamed when the module was loaded into the same 755/// LLVMContext. 756void IRLinker::computeTypeMapping() { 757 for (GlobalValue &SGV : SrcM->globals()) { 758 GlobalValue *DGV = getLinkedToGlobal(&SGV); 759 if (!DGV) 760 continue; 761 762 if (!DGV->hasAppendingLinkage() || !SGV.hasAppendingLinkage()) { 763 TypeMap.addTypeMapping(DGV->getType(), SGV.getType()); 764 continue; 765 } 766 767 // Unify the element type of appending arrays. 768 ArrayType *DAT = cast<ArrayType>(DGV->getValueType()); 769 ArrayType *SAT = cast<ArrayType>(SGV.getValueType()); 770 TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType()); 771 } 772 773 for (GlobalValue &SGV : *SrcM) 774 if (GlobalValue *DGV = getLinkedToGlobal(&SGV)) { 775 if (DGV->getType() == SGV.getType()) { 776 // If the types of DGV and SGV are the same, it means that DGV is from 777 // the source module and got added to DstM from a shared metadata. We 778 // shouldn't map this type to itself in case the type's components get 779 // remapped to a new type from DstM (for instance, during the loop over 780 // SrcM->getIdentifiedStructTypes() below). 781 continue; 782 } 783 784 TypeMap.addTypeMapping(DGV->getType(), SGV.getType()); 785 } 786 787 for (GlobalValue &SGV : SrcM->aliases()) 788 if (GlobalValue *DGV = getLinkedToGlobal(&SGV)) 789 TypeMap.addTypeMapping(DGV->getType(), SGV.getType()); 790 791 // Incorporate types by name, scanning all the types in the source module. 792 // At this point, the destination module may have a type "%foo = { i32 }" for 793 // example. When the source module got loaded into the same LLVMContext, if 794 // it had the same type, it would have been renamed to "%foo.42 = { i32 }". 795 std::vector<StructType *> Types = SrcM->getIdentifiedStructTypes(); 796 for (StructType *ST : Types) { 797 if (!ST->hasName()) 798 continue; 799 800 if (TypeMap.DstStructTypesSet.hasType(ST)) { 801 // This is actually a type from the destination module. 802 // getIdentifiedStructTypes() can have found it by walking debug info 803 // metadata nodes, some of which get linked by name when ODR Type Uniquing 804 // is enabled on the Context, from the source to the destination module. 805 continue; 806 } 807 808 auto STTypePrefix = getTypeNamePrefix(ST->getName()); 809 if (STTypePrefix.size() == ST->getName().size()) 810 continue; 811 812 // Check to see if the destination module has a struct with the prefix name. 813 StructType *DST = StructType::getTypeByName(ST->getContext(), STTypePrefix); 814 if (!DST) 815 continue; 816 817 // Don't use it if this actually came from the source module. They're in 818 // the same LLVMContext after all. Also don't use it unless the type is 819 // actually used in the destination module. This can happen in situations 820 // like this: 821 // 822 // Module A Module B 823 // -------- -------- 824 // %Z = type { %A } %B = type { %C.1 } 825 // %A = type { %B.1, [7 x i8] } %C.1 = type { i8* } 826 // %B.1 = type { %C } %A.2 = type { %B.3, [5 x i8] } 827 // %C = type { i8* } %B.3 = type { %C.1 } 828 // 829 // When we link Module B with Module A, the '%B' in Module B is 830 // used. However, that would then use '%C.1'. But when we process '%C.1', 831 // we prefer to take the '%C' version. So we are then left with both 832 // '%C.1' and '%C' being used for the same types. This leads to some 833 // variables using one type and some using the other. 834 if (TypeMap.DstStructTypesSet.hasType(DST)) 835 TypeMap.addTypeMapping(DST, ST); 836 } 837 838 // Now that we have discovered all of the type equivalences, get a body for 839 // any 'opaque' types in the dest module that are now resolved. 840 TypeMap.linkDefinedTypeBodies(); 841} 842 843static void getArrayElements(const Constant *C, 844 SmallVectorImpl<Constant *> &Dest) { 845 unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements(); 846 847 for (unsigned i = 0; i != NumElements; ++i) 848 Dest.push_back(C->getAggregateElement(i)); 849} 850 851/// If there were any appending global variables, link them together now. 852Expected<Constant *> 853IRLinker::linkAppendingVarProto(GlobalVariable *DstGV, 854 const GlobalVariable *SrcGV) { 855 // Check that both variables have compatible properties. 856 if (DstGV && !DstGV->isDeclaration() && !SrcGV->isDeclaration()) { 857 if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage()) 858 return stringErr( 859 "Linking globals named '" + SrcGV->getName() + 860 "': can only link appending global with another appending " 861 "global!"); 862 863 if (DstGV->isConstant() != SrcGV->isConstant()) 864 return stringErr("Appending variables linked with different const'ness!"); 865 866 if (DstGV->getAlignment() != SrcGV->getAlignment()) 867 return stringErr( 868 "Appending variables with different alignment need to be linked!"); 869 870 if (DstGV->getVisibility() != SrcGV->getVisibility()) 871 return stringErr( 872 "Appending variables with different visibility need to be linked!"); 873 874 if (DstGV->hasGlobalUnnamedAddr() != SrcGV->hasGlobalUnnamedAddr()) 875 return stringErr( 876 "Appending variables with different unnamed_addr need to be linked!"); 877 878 if (DstGV->getSection() != SrcGV->getSection()) 879 return stringErr( 880 "Appending variables with different section name need to be linked!"); 881 } 882 883 // Do not need to do anything if source is a declaration. 884 if (SrcGV->isDeclaration()) 885 return DstGV; 886 887 Type *EltTy = cast<ArrayType>(TypeMap.get(SrcGV->getValueType())) 888 ->getElementType(); 889 890 // FIXME: This upgrade is done during linking to support the C API. Once the 891 // old form is deprecated, we should move this upgrade to 892 // llvm::UpgradeGlobalVariable() and simplify the logic here and in 893 // Mapper::mapAppendingVariable() in ValueMapper.cpp. 894 StringRef Name = SrcGV->getName(); 895 bool IsNewStructor = false; 896 bool IsOldStructor = false; 897 if (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") { 898 if (cast<StructType>(EltTy)->getNumElements() == 3) 899 IsNewStructor = true; 900 else 901 IsOldStructor = true; 902 } 903 904 PointerType *VoidPtrTy = Type::getInt8Ty(SrcGV->getContext())->getPointerTo(); 905 if (IsOldStructor) { 906 auto &ST = *cast<StructType>(EltTy); 907 Type *Tys[3] = {ST.getElementType(0), ST.getElementType(1), VoidPtrTy}; 908 EltTy = StructType::get(SrcGV->getContext(), Tys, false); 909 } 910 911 uint64_t DstNumElements = 0; 912 if (DstGV && !DstGV->isDeclaration()) { 913 ArrayType *DstTy = cast<ArrayType>(DstGV->getValueType()); 914 DstNumElements = DstTy->getNumElements(); 915 916 // Check to see that they two arrays agree on type. 917 if (EltTy != DstTy->getElementType()) 918 return stringErr("Appending variables with different element types!"); 919 } 920 921 SmallVector<Constant *, 16> SrcElements; 922 getArrayElements(SrcGV->getInitializer(), SrcElements); 923 924 if (IsNewStructor) { 925 erase_if(SrcElements, [this](Constant *E) { 926 auto *Key = 927 dyn_cast<GlobalValue>(E->getAggregateElement(2)->stripPointerCasts()); 928 if (!Key) 929 return false; 930 GlobalValue *DGV = getLinkedToGlobal(Key); 931 return !shouldLink(DGV, *Key); 932 }); 933 } 934 uint64_t NewSize = DstNumElements + SrcElements.size(); 935 ArrayType *NewType = ArrayType::get(EltTy, NewSize); 936 937 // Create the new global variable. 938 GlobalVariable *NG = new GlobalVariable( 939 DstM, NewType, SrcGV->isConstant(), SrcGV->getLinkage(), 940 /*init*/ nullptr, /*name*/ "", DstGV, SrcGV->getThreadLocalMode(), 941 SrcGV->getAddressSpace()); 942 943 NG->copyAttributesFrom(SrcGV); 944 forceRenaming(NG, SrcGV->getName()); 945 946 Constant *Ret = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType())); 947 948 Mapper.scheduleMapAppendingVariable( 949 *NG, 950 (DstGV && !DstGV->isDeclaration()) ? DstGV->getInitializer() : nullptr, 951 IsOldStructor, SrcElements); 952 953 // Replace any uses of the two global variables with uses of the new 954 // global. 955 if (DstGV) { 956 RAUWWorklist.push_back( 957 std::make_pair(DstGV, ConstantExpr::getBitCast(NG, DstGV->getType()))); 958 } 959 960 return Ret; 961} 962 963bool IRLinker::shouldLink(GlobalValue *DGV, GlobalValue &SGV) { 964 if (ValuesToLink.count(&SGV) || SGV.hasLocalLinkage()) 965 return true; 966 967 if (DGV && !DGV->isDeclarationForLinker()) 968 return false; 969 970 if (SGV.isDeclaration() || DoneLinkingBodies) 971 return false; 972 973 // Callback to the client to give a chance to lazily add the Global to the 974 // list of value to link. 975 bool LazilyAdded = false; 976 AddLazyFor(SGV, [this, &LazilyAdded](GlobalValue &GV) { 977 maybeAdd(&GV); 978 LazilyAdded = true; 979 }); 980 return LazilyAdded; 981} 982 983Expected<Constant *> IRLinker::linkGlobalValueProto(GlobalValue *SGV, 984 bool ForIndirectSymbol) { 985 GlobalValue *DGV = getLinkedToGlobal(SGV); 986 987 bool ShouldLink = shouldLink(DGV, *SGV); 988 989 // just missing from map 990 if (ShouldLink) { 991 auto I = ValueMap.find(SGV); 992 if (I != ValueMap.end()) 993 return cast<Constant>(I->second); 994 995 I = IndirectSymbolValueMap.find(SGV); 996 if (I != IndirectSymbolValueMap.end()) 997 return cast<Constant>(I->second); 998 } 999 1000 if (!ShouldLink && ForIndirectSymbol) 1001 DGV = nullptr; 1002 1003 // Handle the ultra special appending linkage case first. 1004 if (SGV->hasAppendingLinkage() || (DGV && DGV->hasAppendingLinkage())) 1005 return linkAppendingVarProto(cast_or_null<GlobalVariable>(DGV), 1006 cast<GlobalVariable>(SGV)); 1007 1008 bool NeedsRenaming = false; 1009 GlobalValue *NewGV; 1010 if (DGV && !ShouldLink) { 1011 NewGV = DGV; 1012 } else { 1013 // If we are done linking global value bodies (i.e. we are performing 1014 // metadata linking), don't link in the global value due to this 1015 // reference, simply map it to null. 1016 if (DoneLinkingBodies) 1017 return nullptr; 1018 1019 NewGV = copyGlobalValueProto(SGV, ShouldLink || ForIndirectSymbol); 1020 if (ShouldLink || !ForIndirectSymbol) 1021 NeedsRenaming = true; 1022 } 1023 1024 // Overloaded intrinsics have overloaded types names as part of their 1025 // names. If we renamed overloaded types we should rename the intrinsic 1026 // as well. 1027 if (Function *F = dyn_cast<Function>(NewGV)) 1028 if (auto Remangled = Intrinsic::remangleIntrinsicFunction(F)) { 1029 NewGV->eraseFromParent(); 1030 NewGV = Remangled.getValue(); 1031 NeedsRenaming = false; 1032 } 1033 1034 if (NeedsRenaming) 1035 forceRenaming(NewGV, SGV->getName()); 1036 1037 if (ShouldLink || ForIndirectSymbol) { 1038 if (const Comdat *SC = SGV->getComdat()) { 1039 if (auto *GO = dyn_cast<GlobalObject>(NewGV)) { 1040 Comdat *DC = DstM.getOrInsertComdat(SC->getName()); 1041 DC->setSelectionKind(SC->getSelectionKind()); 1042 GO->setComdat(DC); 1043 } 1044 } 1045 } 1046 1047 if (!ShouldLink && ForIndirectSymbol) 1048 NewGV->setLinkage(GlobalValue::InternalLinkage); 1049 1050 Constant *C = NewGV; 1051 // Only create a bitcast if necessary. In particular, with 1052 // DebugTypeODRUniquing we may reach metadata in the destination module 1053 // containing a GV from the source module, in which case SGV will be 1054 // the same as DGV and NewGV, and TypeMap.get() will assert since it 1055 // assumes it is being invoked on a type in the source module. 1056 if (DGV && NewGV != SGV) { 1057 C = ConstantExpr::getPointerBitCastOrAddrSpaceCast( 1058 NewGV, TypeMap.get(SGV->getType())); 1059 } 1060 1061 if (DGV && NewGV != DGV) { 1062 // Schedule "replace all uses with" to happen after materializing is 1063 // done. It is not safe to do it now, since ValueMapper may be holding 1064 // pointers to constants that will get deleted if RAUW runs. 1065 RAUWWorklist.push_back(std::make_pair( 1066 DGV, 1067 ConstantExpr::getPointerBitCastOrAddrSpaceCast(NewGV, DGV->getType()))); 1068 } 1069 1070 return C; 1071} 1072 1073/// Update the initializers in the Dest module now that all globals that may be 1074/// referenced are in Dest. 1075void IRLinker::linkGlobalVariable(GlobalVariable &Dst, GlobalVariable &Src) { 1076 // Figure out what the initializer looks like in the dest module. 1077 Mapper.scheduleMapGlobalInitializer(Dst, *Src.getInitializer()); 1078} 1079 1080/// Copy the source function over into the dest function and fix up references 1081/// to values. At this point we know that Dest is an external function, and 1082/// that Src is not. 1083Error IRLinker::linkFunctionBody(Function &Dst, Function &Src) { 1084 assert(Dst.isDeclaration() && !Src.isDeclaration()); 1085 1086 // Materialize if needed. 1087 if (Error Err = Src.materialize()) 1088 return Err; 1089 1090 // Link in the operands without remapping. 1091 if (Src.hasPrefixData()) 1092 Dst.setPrefixData(Src.getPrefixData()); 1093 if (Src.hasPrologueData()) 1094 Dst.setPrologueData(Src.getPrologueData()); 1095 if (Src.hasPersonalityFn()) 1096 Dst.setPersonalityFn(Src.getPersonalityFn()); 1097 1098 // Copy over the metadata attachments without remapping. 1099 Dst.copyMetadata(&Src, 0); 1100 1101 // Steal arguments and splice the body of Src into Dst. 1102 Dst.stealArgumentListFrom(Src); 1103 Dst.getBasicBlockList().splice(Dst.end(), Src.getBasicBlockList()); 1104 1105 // Everything has been moved over. Remap it. 1106 Mapper.scheduleRemapFunction(Dst); 1107 return Error::success(); 1108} 1109 1110void IRLinker::linkIndirectSymbolBody(GlobalIndirectSymbol &Dst, 1111 GlobalIndirectSymbol &Src) { 1112 Mapper.scheduleMapGlobalIndirectSymbol(Dst, *Src.getIndirectSymbol(), 1113 IndirectSymbolMCID); 1114} 1115 1116Error IRLinker::linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src) { 1117 if (auto *F = dyn_cast<Function>(&Src)) 1118 return linkFunctionBody(cast<Function>(Dst), *F); 1119 if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) { 1120 linkGlobalVariable(cast<GlobalVariable>(Dst), *GVar); 1121 return Error::success(); 1122 } 1123 linkIndirectSymbolBody(cast<GlobalIndirectSymbol>(Dst), cast<GlobalIndirectSymbol>(Src)); 1124 return Error::success(); 1125} 1126 1127void IRLinker::flushRAUWWorklist() { 1128 for (const auto &Elem : RAUWWorklist) { 1129 GlobalValue *Old; 1130 Value *New; 1131 std::tie(Old, New) = Elem; 1132 1133 Old->replaceAllUsesWith(New); 1134 Old->eraseFromParent(); 1135 } 1136 RAUWWorklist.clear(); 1137} 1138 1139void IRLinker::prepareCompileUnitsForImport() { 1140 NamedMDNode *SrcCompileUnits = SrcM->getNamedMetadata("llvm.dbg.cu"); 1141 if (!SrcCompileUnits) 1142 return; 1143 // When importing for ThinLTO, prevent importing of types listed on 1144 // the DICompileUnit that we don't need a copy of in the importing 1145 // module. They will be emitted by the originating module. 1146 for (unsigned I = 0, E = SrcCompileUnits->getNumOperands(); I != E; ++I) { 1147 auto *CU = cast<DICompileUnit>(SrcCompileUnits->getOperand(I)); 1148 assert(CU && "Expected valid compile unit"); 1149 // Enums, macros, and retained types don't need to be listed on the 1150 // imported DICompileUnit. This means they will only be imported 1151 // if reached from the mapped IR. 1152 CU->replaceEnumTypes(nullptr); 1153 CU->replaceMacros(nullptr); 1154 CU->replaceRetainedTypes(nullptr); 1155 1156 // The original definition (or at least its debug info - if the variable is 1157 // internalized and optimized away) will remain in the source module, so 1158 // there's no need to import them. 1159 // If LLVM ever does more advanced optimizations on global variables 1160 // (removing/localizing write operations, for instance) that can track 1161 // through debug info, this decision may need to be revisited - but do so 1162 // with care when it comes to debug info size. Emitting small CUs containing 1163 // only a few imported entities into every destination module may be very 1164 // size inefficient. 1165 CU->replaceGlobalVariables(nullptr); 1166 1167 // Imported entities only need to be mapped in if they have local 1168 // scope, as those might correspond to an imported entity inside a 1169 // function being imported (any locally scoped imported entities that 1170 // don't end up referenced by an imported function will not be emitted 1171 // into the object). Imported entities not in a local scope 1172 // (e.g. on the namespace) only need to be emitted by the originating 1173 // module. Create a list of the locally scoped imported entities, and 1174 // replace the source CUs imported entity list with the new list, so 1175 // only those are mapped in. 1176 // FIXME: Locally-scoped imported entities could be moved to the 1177 // functions they are local to instead of listing them on the CU, and 1178 // we would naturally only link in those needed by function importing. 1179 SmallVector<TrackingMDNodeRef, 4> AllImportedModules; 1180 bool ReplaceImportedEntities = false; 1181 for (auto *IE : CU->getImportedEntities()) { 1182 DIScope *Scope = IE->getScope(); 1183 assert(Scope && "Invalid Scope encoding!"); 1184 if (isa<DILocalScope>(Scope)) 1185 AllImportedModules.emplace_back(IE); 1186 else 1187 ReplaceImportedEntities = true; 1188 } 1189 if (ReplaceImportedEntities) { 1190 if (!AllImportedModules.empty()) 1191 CU->replaceImportedEntities(MDTuple::get( 1192 CU->getContext(), 1193 SmallVector<Metadata *, 16>(AllImportedModules.begin(), 1194 AllImportedModules.end()))); 1195 else 1196 // If there were no local scope imported entities, we can map 1197 // the whole list to nullptr. 1198 CU->replaceImportedEntities(nullptr); 1199 } 1200 } 1201} 1202 1203/// Insert all of the named MDNodes in Src into the Dest module. 1204void IRLinker::linkNamedMDNodes() { 1205 const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata(); 1206 for (const NamedMDNode &NMD : SrcM->named_metadata()) { 1207 // Don't link module flags here. Do them separately. 1208 if (&NMD == SrcModFlags) 1209 continue; 1210 NamedMDNode *DestNMD = DstM.getOrInsertNamedMetadata(NMD.getName()); 1211 // Add Src elements into Dest node. 1212 for (const MDNode *Op : NMD.operands()) 1213 DestNMD->addOperand(Mapper.mapMDNode(*Op)); 1214 } 1215} 1216 1217/// Merge the linker flags in Src into the Dest module. 1218Error IRLinker::linkModuleFlagsMetadata() { 1219 // If the source module has no module flags, we are done. 1220 const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata(); 1221 if (!SrcModFlags) 1222 return Error::success(); 1223 1224 // If the destination module doesn't have module flags yet, then just copy 1225 // over the source module's flags. 1226 NamedMDNode *DstModFlags = DstM.getOrInsertModuleFlagsMetadata(); 1227 if (DstModFlags->getNumOperands() == 0) { 1228 for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) 1229 DstModFlags->addOperand(SrcModFlags->getOperand(I)); 1230 1231 return Error::success(); 1232 } 1233 1234 // First build a map of the existing module flags and requirements. 1235 DenseMap<MDString *, std::pair<MDNode *, unsigned>> Flags; 1236 SmallSetVector<MDNode *, 16> Requirements; 1237 for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) { 1238 MDNode *Op = DstModFlags->getOperand(I); 1239 ConstantInt *Behavior = mdconst::extract<ConstantInt>(Op->getOperand(0)); 1240 MDString *ID = cast<MDString>(Op->getOperand(1)); 1241 1242 if (Behavior->getZExtValue() == Module::Require) { 1243 Requirements.insert(cast<MDNode>(Op->getOperand(2))); 1244 } else { 1245 Flags[ID] = std::make_pair(Op, I); 1246 } 1247 } 1248 1249 // Merge in the flags from the source module, and also collect its set of 1250 // requirements. 1251 for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) { 1252 MDNode *SrcOp = SrcModFlags->getOperand(I); 1253 ConstantInt *SrcBehavior = 1254 mdconst::extract<ConstantInt>(SrcOp->getOperand(0)); 1255 MDString *ID = cast<MDString>(SrcOp->getOperand(1)); 1256 MDNode *DstOp; 1257 unsigned DstIndex; 1258 std::tie(DstOp, DstIndex) = Flags.lookup(ID); 1259 unsigned SrcBehaviorValue = SrcBehavior->getZExtValue(); 1260 1261 // If this is a requirement, add it and continue. 1262 if (SrcBehaviorValue == Module::Require) { 1263 // If the destination module does not already have this requirement, add 1264 // it. 1265 if (Requirements.insert(cast<MDNode>(SrcOp->getOperand(2)))) { 1266 DstModFlags->addOperand(SrcOp); 1267 } 1268 continue; 1269 } 1270 1271 // If there is no existing flag with this ID, just add it. 1272 if (!DstOp) { 1273 Flags[ID] = std::make_pair(SrcOp, DstModFlags->getNumOperands()); 1274 DstModFlags->addOperand(SrcOp); 1275 continue; 1276 } 1277 1278 // Otherwise, perform a merge. 1279 ConstantInt *DstBehavior = 1280 mdconst::extract<ConstantInt>(DstOp->getOperand(0)); 1281 unsigned DstBehaviorValue = DstBehavior->getZExtValue(); 1282 1283 auto overrideDstValue = [&]() { 1284 DstModFlags->setOperand(DstIndex, SrcOp); 1285 Flags[ID].first = SrcOp; 1286 }; 1287 1288 // If either flag has override behavior, handle it first. 1289 if (DstBehaviorValue == Module::Override) { 1290 // Diagnose inconsistent flags which both have override behavior. 1291 if (SrcBehaviorValue == Module::Override && 1292 SrcOp->getOperand(2) != DstOp->getOperand(2)) 1293 return stringErr("linking module flags '" + ID->getString() + 1294 "': IDs have conflicting override values in '" + 1295 SrcM->getModuleIdentifier() + "' and '" + 1296 DstM.getModuleIdentifier() + "'"); 1297 continue; 1298 } else if (SrcBehaviorValue == Module::Override) { 1299 // Update the destination flag to that of the source. 1300 overrideDstValue(); 1301 continue; 1302 } 1303 1304 // Diagnose inconsistent merge behavior types. 1305 if (SrcBehaviorValue != DstBehaviorValue) { 1306 bool MaxAndWarn = (SrcBehaviorValue == Module::Max && 1307 DstBehaviorValue == Module::Warning) || 1308 (DstBehaviorValue == Module::Max && 1309 SrcBehaviorValue == Module::Warning); 1310 if (!MaxAndWarn) 1311 return stringErr("linking module flags '" + ID->getString() + 1312 "': IDs have conflicting behaviors in '" + 1313 SrcM->getModuleIdentifier() + "' and '" + 1314 DstM.getModuleIdentifier() + "'"); 1315 } 1316 1317 auto replaceDstValue = [&](MDNode *New) { 1318 Metadata *FlagOps[] = {DstOp->getOperand(0), ID, New}; 1319 MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps); 1320 DstModFlags->setOperand(DstIndex, Flag); 1321 Flags[ID].first = Flag; 1322 }; 1323 1324 // Emit a warning if the values differ and either source or destination 1325 // request Warning behavior. 1326 if ((DstBehaviorValue == Module::Warning || 1327 SrcBehaviorValue == Module::Warning) && 1328 SrcOp->getOperand(2) != DstOp->getOperand(2)) { 1329 std::string Str; 1330 raw_string_ostream(Str) 1331 << "linking module flags '" << ID->getString() 1332 << "': IDs have conflicting values ('" << *SrcOp->getOperand(2) 1333 << "' from " << SrcM->getModuleIdentifier() << " with '" 1334 << *DstOp->getOperand(2) << "' from " << DstM.getModuleIdentifier() 1335 << ')'; 1336 emitWarning(Str); 1337 } 1338 1339 // Choose the maximum if either source or destination request Max behavior. 1340 if (DstBehaviorValue == Module::Max || SrcBehaviorValue == Module::Max) { 1341 ConstantInt *DstValue = 1342 mdconst::extract<ConstantInt>(DstOp->getOperand(2)); 1343 ConstantInt *SrcValue = 1344 mdconst::extract<ConstantInt>(SrcOp->getOperand(2)); 1345 1346 // The resulting flag should have a Max behavior, and contain the maximum 1347 // value from between the source and destination values. 1348 Metadata *FlagOps[] = { 1349 (DstBehaviorValue != Module::Max ? SrcOp : DstOp)->getOperand(0), ID, 1350 (SrcValue->getZExtValue() > DstValue->getZExtValue() ? SrcOp : DstOp) 1351 ->getOperand(2)}; 1352 MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps); 1353 DstModFlags->setOperand(DstIndex, Flag); 1354 Flags[ID].first = Flag; 1355 continue; 1356 } 1357 1358 // Perform the merge for standard behavior types. 1359 switch (SrcBehaviorValue) { 1360 case Module::Require: 1361 case Module::Override: 1362 llvm_unreachable("not possible"); 1363 case Module::Error: { 1364 // Emit an error if the values differ. 1365 if (SrcOp->getOperand(2) != DstOp->getOperand(2)) 1366 return stringErr("linking module flags '" + ID->getString() + 1367 "': IDs have conflicting values in '" + 1368 SrcM->getModuleIdentifier() + "' and '" + 1369 DstM.getModuleIdentifier() + "'"); 1370 continue; 1371 } 1372 case Module::Warning: { 1373 break; 1374 } 1375 case Module::Max: { 1376 break; 1377 } 1378 case Module::Append: { 1379 MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2)); 1380 MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2)); 1381 SmallVector<Metadata *, 8> MDs; 1382 MDs.reserve(DstValue->getNumOperands() + SrcValue->getNumOperands()); 1383 MDs.append(DstValue->op_begin(), DstValue->op_end()); 1384 MDs.append(SrcValue->op_begin(), SrcValue->op_end()); 1385 1386 replaceDstValue(MDNode::get(DstM.getContext(), MDs)); 1387 break; 1388 } 1389 case Module::AppendUnique: { 1390 SmallSetVector<Metadata *, 16> Elts; 1391 MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2)); 1392 MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2)); 1393 Elts.insert(DstValue->op_begin(), DstValue->op_end()); 1394 Elts.insert(SrcValue->op_begin(), SrcValue->op_end()); 1395 1396 replaceDstValue(MDNode::get(DstM.getContext(), 1397 makeArrayRef(Elts.begin(), Elts.end()))); 1398 break; 1399 } 1400 } 1401 1402 } 1403 1404 // Check all of the requirements. 1405 for (unsigned I = 0, E = Requirements.size(); I != E; ++I) { 1406 MDNode *Requirement = Requirements[I]; 1407 MDString *Flag = cast<MDString>(Requirement->getOperand(0)); 1408 Metadata *ReqValue = Requirement->getOperand(1); 1409 1410 MDNode *Op = Flags[Flag].first; 1411 if (!Op || Op->getOperand(2) != ReqValue) 1412 return stringErr("linking module flags '" + Flag->getString() + 1413 "': does not have the required value"); 1414 } 1415 return Error::success(); 1416} 1417 1418/// Return InlineAsm adjusted with target-specific directives if required. 1419/// For ARM and Thumb, we have to add directives to select the appropriate ISA 1420/// to support mixing module-level inline assembly from ARM and Thumb modules. 1421static std::string adjustInlineAsm(const std::string &InlineAsm, 1422 const Triple &Triple) { 1423 if (Triple.getArch() == Triple::thumb || Triple.getArch() == Triple::thumbeb) 1424 return ".text\n.balign 2\n.thumb\n" + InlineAsm; 1425 if (Triple.getArch() == Triple::arm || Triple.getArch() == Triple::armeb) 1426 return ".text\n.balign 4\n.arm\n" + InlineAsm; 1427 return InlineAsm; 1428} 1429 1430Error IRLinker::run() { 1431 // Ensure metadata materialized before value mapping. 1432 if (SrcM->getMaterializer()) 1433 if (Error Err = SrcM->getMaterializer()->materializeMetadata()) 1434 return Err; 1435 1436 // Inherit the target data from the source module if the destination module 1437 // doesn't have one already. 1438 if (DstM.getDataLayout().isDefault()) 1439 DstM.setDataLayout(SrcM->getDataLayout()); 1440 1441 if (SrcM->getDataLayout() != DstM.getDataLayout()) { 1442 emitWarning("Linking two modules of different data layouts: '" + 1443 SrcM->getModuleIdentifier() + "' is '" + 1444 SrcM->getDataLayoutStr() + "' whereas '" + 1445 DstM.getModuleIdentifier() + "' is '" + 1446 DstM.getDataLayoutStr() + "'\n"); 1447 } 1448 1449 // Copy the target triple from the source to dest if the dest's is empty. 1450 if (DstM.getTargetTriple().empty() && !SrcM->getTargetTriple().empty()) 1451 DstM.setTargetTriple(SrcM->getTargetTriple()); 1452 1453 Triple SrcTriple(SrcM->getTargetTriple()), DstTriple(DstM.getTargetTriple()); 1454 1455 if (!SrcM->getTargetTriple().empty()&& 1456 !SrcTriple.isCompatibleWith(DstTriple)) 1457 emitWarning("Linking two modules of different target triples: '" + 1458 SrcM->getModuleIdentifier() + "' is '" + 1459 SrcM->getTargetTriple() + "' whereas '" + 1460 DstM.getModuleIdentifier() + "' is '" + DstM.getTargetTriple() + 1461 "'\n"); 1462 1463 DstM.setTargetTriple(SrcTriple.merge(DstTriple)); 1464 1465 // Loop over all of the linked values to compute type mappings. 1466 computeTypeMapping(); 1467 1468 std::reverse(Worklist.begin(), Worklist.end()); 1469 while (!Worklist.empty()) { 1470 GlobalValue *GV = Worklist.back(); 1471 Worklist.pop_back(); 1472 1473 // Already mapped. 1474 if (ValueMap.find(GV) != ValueMap.end() || 1475 IndirectSymbolValueMap.find(GV) != IndirectSymbolValueMap.end()) 1476 continue; 1477 1478 assert(!GV->isDeclaration()); 1479 Mapper.mapValue(*GV); 1480 if (FoundError) 1481 return std::move(*FoundError); 1482 flushRAUWWorklist(); 1483 } 1484 1485 // Note that we are done linking global value bodies. This prevents 1486 // metadata linking from creating new references. 1487 DoneLinkingBodies = true; 1488 Mapper.addFlags(RF_NullMapMissingGlobalValues); 1489 1490 // Remap all of the named MDNodes in Src into the DstM module. We do this 1491 // after linking GlobalValues so that MDNodes that reference GlobalValues 1492 // are properly remapped. 1493 linkNamedMDNodes(); 1494 1495 if (!IsPerformingImport && !SrcM->getModuleInlineAsm().empty()) { 1496 // Append the module inline asm string. 1497 DstM.appendModuleInlineAsm(adjustInlineAsm(SrcM->getModuleInlineAsm(), 1498 SrcTriple)); 1499 } else if (IsPerformingImport) { 1500 // Import any symver directives for symbols in DstM. 1501 ModuleSymbolTable::CollectAsmSymvers(*SrcM, 1502 [&](StringRef Name, StringRef Alias) { 1503 if (DstM.getNamedValue(Name)) { 1504 SmallString<256> S(".symver "); 1505 S += Name; 1506 S += ", "; 1507 S += Alias; 1508 DstM.appendModuleInlineAsm(S); 1509 } 1510 }); 1511 } 1512 1513 // Reorder the globals just added to the destination module to match their 1514 // original order in the source module. 1515 Module::GlobalListType &Globals = DstM.getGlobalList(); 1516 for (GlobalVariable &GV : SrcM->globals()) { 1517 if (GV.hasAppendingLinkage()) 1518 continue; 1519 Value *NewValue = Mapper.mapValue(GV); 1520 if (NewValue) { 1521 auto *NewGV = dyn_cast<GlobalVariable>(NewValue->stripPointerCasts()); 1522 if (NewGV) 1523 Globals.splice(Globals.end(), Globals, NewGV->getIterator()); 1524 } 1525 } 1526 1527 // Merge the module flags into the DstM module. 1528 return linkModuleFlagsMetadata(); 1529} 1530 1531IRMover::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P) 1532 : ETypes(E), IsPacked(P) {} 1533 1534IRMover::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST) 1535 : ETypes(ST->elements()), IsPacked(ST->isPacked()) {} 1536 1537bool IRMover::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const { 1538 return IsPacked == That.IsPacked && ETypes == That.ETypes; 1539} 1540 1541bool IRMover::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const { 1542 return !this->operator==(That); 1543} 1544 1545StructType *IRMover::StructTypeKeyInfo::getEmptyKey() { 1546 return DenseMapInfo<StructType *>::getEmptyKey(); 1547} 1548 1549StructType *IRMover::StructTypeKeyInfo::getTombstoneKey() { 1550 return DenseMapInfo<StructType *>::getTombstoneKey(); 1551} 1552 1553unsigned IRMover::StructTypeKeyInfo::getHashValue(const KeyTy &Key) { 1554 return hash_combine(hash_combine_range(Key.ETypes.begin(), Key.ETypes.end()), 1555 Key.IsPacked); 1556} 1557 1558unsigned IRMover::StructTypeKeyInfo::getHashValue(const StructType *ST) { 1559 return getHashValue(KeyTy(ST)); 1560} 1561 1562bool IRMover::StructTypeKeyInfo::isEqual(const KeyTy &LHS, 1563 const StructType *RHS) { 1564 if (RHS == getEmptyKey() || RHS == getTombstoneKey()) 1565 return false; 1566 return LHS == KeyTy(RHS); 1567} 1568 1569bool IRMover::StructTypeKeyInfo::isEqual(const StructType *LHS, 1570 const StructType *RHS) { 1571 if (RHS == getEmptyKey() || RHS == getTombstoneKey()) 1572 return LHS == RHS; 1573 return KeyTy(LHS) == KeyTy(RHS); 1574} 1575 1576void IRMover::IdentifiedStructTypeSet::addNonOpaque(StructType *Ty) { 1577 assert(!Ty->isOpaque()); 1578 NonOpaqueStructTypes.insert(Ty); 1579} 1580 1581void IRMover::IdentifiedStructTypeSet::switchToNonOpaque(StructType *Ty) { 1582 assert(!Ty->isOpaque()); 1583 NonOpaqueStructTypes.insert(Ty); 1584 bool Removed = OpaqueStructTypes.erase(Ty); 1585 (void)Removed; 1586 assert(Removed); 1587} 1588 1589void IRMover::IdentifiedStructTypeSet::addOpaque(StructType *Ty) { 1590 assert(Ty->isOpaque()); 1591 OpaqueStructTypes.insert(Ty); 1592} 1593 1594StructType * 1595IRMover::IdentifiedStructTypeSet::findNonOpaque(ArrayRef<Type *> ETypes, 1596 bool IsPacked) { 1597 IRMover::StructTypeKeyInfo::KeyTy Key(ETypes, IsPacked); 1598 auto I = NonOpaqueStructTypes.find_as(Key); 1599 return I == NonOpaqueStructTypes.end() ? nullptr : *I; 1600} 1601 1602bool IRMover::IdentifiedStructTypeSet::hasType(StructType *Ty) { 1603 if (Ty->isOpaque()) 1604 return OpaqueStructTypes.count(Ty); 1605 auto I = NonOpaqueStructTypes.find(Ty); 1606 return I == NonOpaqueStructTypes.end() ? false : *I == Ty; 1607} 1608 1609IRMover::IRMover(Module &M) : Composite(M) { 1610 TypeFinder StructTypes; 1611 StructTypes.run(M, /* OnlyNamed */ false); 1612 for (StructType *Ty : StructTypes) { 1613 if (Ty->isOpaque()) 1614 IdentifiedStructTypes.addOpaque(Ty); 1615 else 1616 IdentifiedStructTypes.addNonOpaque(Ty); 1617 } 1618 // Self-map metadatas in the destination module. This is needed when 1619 // DebugTypeODRUniquing is enabled on the LLVMContext, since metadata in the 1620 // destination module may be reached from the source module. 1621 for (auto *MD : StructTypes.getVisitedMetadata()) { 1622 SharedMDs[MD].reset(const_cast<MDNode *>(MD)); 1623 } 1624} 1625 1626Error IRMover::move( 1627 std::unique_ptr<Module> Src, ArrayRef<GlobalValue *> ValuesToLink, 1628 std::function<void(GlobalValue &, ValueAdder Add)> AddLazyFor, 1629 bool IsPerformingImport) { 1630 IRLinker TheIRLinker(Composite, SharedMDs, IdentifiedStructTypes, 1631 std::move(Src), ValuesToLink, std::move(AddLazyFor), 1632 IsPerformingImport); 1633 Error E = TheIRLinker.run(); 1634 Composite.dropTriviallyDeadConstantArrays(); 1635 return E; 1636} 1637