1 //===- lib/Linker/LinkArchives.cpp - Link LLVM objects and libraries ------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains routines to handle linking together LLVM bitcode files, 11 // and to handle annoying things like static libraries. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Linker.h" 16 #include "llvm/Module.h" 17 #include "llvm/ADT/SetOperations.h" 18 #include "llvm/Bitcode/Archive.h" 19 #include <memory> 20 #include <set> 21 using namespace llvm; 22 23 /// GetAllUndefinedSymbols - calculates the set of undefined symbols that still 24 /// exist in an LLVM module. This is a bit tricky because there may be two 25 /// symbols with the same name but different LLVM types that will be resolved to 26 /// each other but aren't currently (thus we need to treat it as resolved). 27 /// 28 /// Inputs: 29 /// M - The module in which to find undefined symbols. 30 /// 31 /// Outputs: 32 /// UndefinedSymbols - A set of C++ strings containing the name of all 33 /// undefined symbols. 34 /// 35 static void 36 GetAllUndefinedSymbols(Module *M, std::set<std::string> &UndefinedSymbols) { 37 std::set<std::string> DefinedSymbols; 38 UndefinedSymbols.clear(); 39 40 // If the program doesn't define a main, try pulling one in from a .a file. 41 // This is needed for programs where the main function is defined in an 42 // archive, such f2c'd programs. 43 Function *Main = M->getFunction("main"); 44 if (Main == 0 || Main->isDeclaration()) 45 UndefinedSymbols.insert("main"); 46 47 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 48 if (I->hasName()) { 49 if (I->isDeclaration()) 50 UndefinedSymbols.insert(I->getName()); 51 else if (!I->hasLocalLinkage()) { 52 assert(!I->hasDLLImportLinkage() 53 && "Found dllimported non-external symbol!"); 54 DefinedSymbols.insert(I->getName()); 55 } 56 } 57 58 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 59 I != E; ++I) 60 if (I->hasName()) { 61 if (I->isDeclaration()) 62 UndefinedSymbols.insert(I->getName()); 63 else if (!I->hasLocalLinkage()) { 64 assert(!I->hasDLLImportLinkage() 65 && "Found dllimported non-external symbol!"); 66 DefinedSymbols.insert(I->getName()); 67 } 68 } 69 70 for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end(); 71 I != E; ++I) 72 if (I->hasName()) 73 DefinedSymbols.insert(I->getName()); 74 75 // Prune out any defined symbols from the undefined symbols set... 76 for (std::set<std::string>::iterator I = UndefinedSymbols.begin(); 77 I != UndefinedSymbols.end(); ) 78 if (DefinedSymbols.count(*I)) 79 UndefinedSymbols.erase(I++); // This symbol really is defined! 80 else 81 ++I; // Keep this symbol in the undefined symbols list 82 } 83 84 /// LinkInArchive - opens an archive library and link in all objects which 85 /// provide symbols that are currently undefined. 86 /// 87 /// Inputs: 88 /// Filename - The pathname of the archive. 89 /// 90 /// Return Value: 91 /// TRUE - An error occurred. 92 /// FALSE - No errors. 93 bool 94 Linker::LinkInArchive(const sys::Path &Filename, bool &is_native) { 95 // Make sure this is an archive file we're dealing with 96 if (!Filename.isArchive()) 97 return error("File '" + Filename.str() + "' is not an archive."); 98 99 // Open the archive file 100 verbose("Linking archive file '" + Filename.str() + "'"); 101 102 // Find all of the symbols currently undefined in the bitcode program. 103 // If all the symbols are defined, the program is complete, and there is 104 // no reason to link in any archive files. 105 std::set<std::string> UndefinedSymbols; 106 GetAllUndefinedSymbols(Composite, UndefinedSymbols); 107 108 if (UndefinedSymbols.empty()) { 109 verbose("No symbols undefined, skipping library '" + Filename.str() + "'"); 110 return false; // No need to link anything in! 111 } 112 113 std::string ErrMsg; 114 std::auto_ptr<Archive> AutoArch ( 115 Archive::OpenAndLoadSymbols(Filename, Context, &ErrMsg)); 116 117 Archive* arch = AutoArch.get(); 118 119 if (!arch) 120 return error("Cannot read archive '" + Filename.str() + 121 "': " + ErrMsg); 122 if (!arch->isBitcodeArchive()) { 123 is_native = true; 124 return false; 125 } 126 is_native = false; 127 128 // Save a set of symbols that are not defined by the archive. Since we're 129 // entering a loop, there's no point searching for these multiple times. This 130 // variable is used to "set_subtract" from the set of undefined symbols. 131 std::set<std::string> NotDefinedByArchive; 132 133 // Save the current set of undefined symbols, because we may have to make 134 // multiple passes over the archive: 135 std::set<std::string> CurrentlyUndefinedSymbols; 136 137 do { 138 CurrentlyUndefinedSymbols = UndefinedSymbols; 139 140 // Find the modules we need to link into the target module. Note that arch 141 // keeps ownership of these modules and may return the same Module* from a 142 // subsequent call. 143 SmallVector<Module*, 16> Modules; 144 if (!arch->findModulesDefiningSymbols(UndefinedSymbols, Modules, &ErrMsg)) 145 return error("Cannot find symbols in '" + Filename.str() + 146 "': " + ErrMsg); 147 148 // If we didn't find any more modules to link this time, we are done 149 // searching this archive. 150 if (Modules.empty()) 151 break; 152 153 // Any symbols remaining in UndefinedSymbols after 154 // findModulesDefiningSymbols are ones that the archive does not define. So 155 // we add them to the NotDefinedByArchive variable now. 156 NotDefinedByArchive.insert(UndefinedSymbols.begin(), 157 UndefinedSymbols.end()); 158 159 // Loop over all the Modules that we got back from the archive 160 for (SmallVectorImpl<Module*>::iterator I=Modules.begin(), E=Modules.end(); 161 I != E; ++I) { 162 163 // Get the module we must link in. 164 std::string moduleErrorMsg; 165 Module* aModule = *I; 166 if (aModule != NULL) { 167 if (aModule->MaterializeAll(&moduleErrorMsg)) 168 return error("Could not load a module: " + moduleErrorMsg); 169 170 verbose(" Linking in module: " + aModule->getModuleIdentifier()); 171 172 // Link it in 173 if (LinkInModule(aModule, &moduleErrorMsg)) 174 return error("Cannot link in module '" + 175 aModule->getModuleIdentifier() + "': " + moduleErrorMsg); 176 } 177 } 178 179 // Get the undefined symbols from the aggregate module. This recomputes the 180 // symbols we still need after the new modules have been linked in. 181 GetAllUndefinedSymbols(Composite, UndefinedSymbols); 182 183 // At this point we have two sets of undefined symbols: UndefinedSymbols 184 // which holds the undefined symbols from all the modules, and 185 // NotDefinedByArchive which holds symbols we know the archive doesn't 186 // define. There's no point searching for symbols that we won't find in the 187 // archive so we subtract these sets. 188 set_subtract(UndefinedSymbols, NotDefinedByArchive); 189 190 // If there's no symbols left, no point in continuing to search the 191 // archive. 192 if (UndefinedSymbols.empty()) 193 break; 194 } while (CurrentlyUndefinedSymbols != UndefinedSymbols); 195 196 return false; 197 } 198