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