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