1 //===- Linker.cpp - Module Linker Implementation --------------------------===//
3 // This file implements the LLVM module linker.
6 // * Merges global variables between the two modules
7 // * Uninit + Uninit = Init, Init + Uninit = Init, Init + Init = Error if !=
8 // * Merges methods between two modules
10 //===----------------------------------------------------------------------===//
12 #include "llvm/Transforms/Linker.h"
13 #include "llvm/Module.h"
14 #include "llvm/Method.h"
15 #include "llvm/GlobalVariable.h"
16 #include "llvm/SymbolTable.h"
17 #include "llvm/DerivedTypes.h"
18 #include "llvm/iOther.h"
19 #include "llvm/ConstantVals.h"
25 // Error - Simple wrapper function to conditionally assign to E and return true.
26 // This just makes error return conditions a little bit simpler...
28 static inline bool Error(string *E, string Message) {
33 #include "llvm/Assembly/Writer.h" // TODO: REMOVE
36 // LinkTypes - Go through the symbol table of the Src module and see if any
37 // types are named in the src module that are not named in the Dst module.
38 // Make sure there are no type name conflicts.
40 static bool LinkTypes(Module *Dest, const Module *Src, string *Err = 0) {
41 // No symbol table? Can't have named types.
42 if (!Src->hasSymbolTable()) return false;
44 SymbolTable *DestST = Dest->getSymbolTableSure();
45 const SymbolTable *SrcST = Src->getSymbolTable();
47 // Look for a type plane for Type's...
48 SymbolTable::const_iterator PI = SrcST->find(Type::TypeTy);
49 if (PI == SrcST->end()) return false; // No named types, do nothing.
51 const SymbolTable::VarMap &VM = PI->second;
52 for (SymbolTable::type_const_iterator I = VM.begin(), E = VM.end();
54 const string &Name = I->first;
55 const Type *RHS = cast<Type>(I->second);
57 // Check to see if this type name is already in the dest module...
58 const Type *Entry = cast_or_null<Type>(DestST->lookup(Type::TypeTy, Name));
59 if (Entry) { // Yup, the value already exists...
60 if (Entry != RHS) // If it's the same, noop. Otherwise, error.
61 return Error(Err, "Type named '" + Name +
62 "' of different shape in modules.\n Src='" +
63 Entry->getDescription() + "'. Dest='" +
64 RHS->getDescription() + "'");
65 } else { // Type not in dest module. Add it now.
66 // TODO: FIXME WHEN TYPES AREN'T CONST
67 DestST->insert(Name, const_cast<Type*>(RHS));
73 static void PrintMap(const map<const Value*, Value*> &M) {
74 for (map<const Value*, Value*>::const_iterator I = M.begin(), E = M.end();
76 cerr << " Fr: " << (void*)I->first << " " << I->first
77 << " To: " << (void*)I->second << " " << I->second << "\n";
82 // RemapOperand - Use LocalMap and GlobalMap to convert references from one
83 // module to another. This is somewhat sophisticated in that it can
84 // automatically handle constant references correctly as well...
86 static Value *RemapOperand(const Value *In, map<const Value*, Value*> &LocalMap,
87 const map<const Value*, Value*> *GlobalMap = 0) {
88 map<const Value*,Value*>::const_iterator I = LocalMap.find(In);
89 if (I != LocalMap.end()) return I->second;
92 I = GlobalMap->find(In);
93 if (I != GlobalMap->end()) return I->second;
96 // Check to see if it's a constant that we are interesting in transforming...
97 if (Constant *CPV = dyn_cast<Constant>(In)) {
98 if (!isa<DerivedType>(CPV->getType()))
99 return CPV; // Simple constants stay identical...
101 Constant *Result = 0;
103 if (ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) {
104 const std::vector<Use> &Ops = CPA->getValues();
105 std::vector<Constant*> Operands(Ops.size());
106 for (unsigned i = 0; i < Ops.size(); ++i)
108 cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
109 Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands);
110 } else if (ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) {
111 const std::vector<Use> &Ops = CPS->getValues();
112 std::vector<Constant*> Operands(Ops.size());
113 for (unsigned i = 0; i < Ops.size(); ++i)
115 cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
116 Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands);
117 } else if (isa<ConstantPointerNull>(CPV)) {
119 } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(CPV)) {
120 Value *V = RemapOperand(CPR->getValue(), LocalMap, GlobalMap);
121 Result = ConstantPointerRef::get(cast<GlobalValue>(V));
123 assert(0 && "Unknown type of derived type constant value!");
126 // Cache the mapping in our local map structure...
127 LocalMap.insert(std::make_pair(In, CPV));
131 cerr << "XXX LocalMap: \n";
135 cerr << "XXX GlobalMap: \n";
136 PrintMap(*GlobalMap);
139 cerr << "Couldn't remap value: " << (void*)In << " " << In << "\n";
140 assert(0 && "Couldn't remap value!");
145 // LinkGlobals - Loop through the global variables in the src module and merge
146 // them into the dest module...
148 static bool LinkGlobals(Module *Dest, const Module *Src,
149 map<const Value*, Value*> &ValueMap, string *Err = 0) {
150 // We will need a module level symbol table if the src module has a module
151 // level symbol table...
152 SymbolTable *ST = Src->getSymbolTable() ? Dest->getSymbolTableSure() : 0;
154 // Loop over all of the globals in the src module, mapping them over as we go
156 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
157 const GlobalVariable *SGV = *I;
160 // If the global variable has a name, and that name is already in use in the
161 // Dest module, make sure that the name is a compatible global variable...
163 if (SGV->hasExternalLinkage() && SGV->hasName() &&
164 (V = ST->lookup(SGV->getType(), SGV->getName())) &&
165 cast<GlobalVariable>(V)->hasExternalLinkage()) {
166 // The same named thing is a global variable, because the only two things
167 // that may be in a module level symbol table are Global Vars and Methods,
168 // and they both have distinct, nonoverlapping, possible types.
170 GlobalVariable *DGV = cast<GlobalVariable>(V);
172 // Check to see if the two GV's have the same Const'ness...
173 if (SGV->isConstant() != DGV->isConstant())
174 return Error(Err, "Global Variable Collision on '" +
175 SGV->getType()->getDescription() + "':%" + SGV->getName() +
176 " - Global variables differ in const'ness");
178 // Okay, everything is cool, remember the mapping...
179 ValueMap.insert(std::make_pair(SGV, DGV));
181 // No linking to be performed, simply create an identical version of the
182 // symbol over in the dest module... the initializer will be filled in
183 // later by LinkGlobalInits...
185 GlobalVariable *DGV =
186 new GlobalVariable(SGV->getType()->getElementType(), SGV->isConstant(),
187 SGV->hasInternalLinkage(), 0, SGV->getName());
189 // Add the new global to the dest module
190 Dest->getGlobalList().push_back(DGV);
192 // Make sure to remember this mapping...
193 ValueMap.insert(std::make_pair(SGV, DGV));
200 // LinkGlobalInits - Update the initializers in the Dest module now that all
201 // globals that may be referenced are in Dest.
203 static bool LinkGlobalInits(Module *Dest, const Module *Src,
204 map<const Value*, Value*> &ValueMap,
207 // Loop over all of the globals in the src module, mapping them over as we go
209 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
210 const GlobalVariable *SGV = *I;
212 if (SGV->hasInitializer()) { // Only process initialized GV's
213 // Figure out what the initializer looks like in the dest module...
215 cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap));
217 GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]);
218 if (DGV->hasInitializer() && SGV->hasExternalLinkage() &&
219 DGV->hasExternalLinkage()) {
220 if (DGV->getInitializer() != DInit)
221 return Error(Err, "Global Variable Collision on '" +
222 SGV->getType()->getDescription() + "':%" +SGV->getName()+
223 " - Global variables have different initializers");
225 // Copy the initializer over now...
226 DGV->setInitializer(DInit);
233 // LinkMethodProtos - Link the methods together between the two modules, without
234 // doing method bodies... this just adds external method prototypes to the Dest
237 static bool LinkMethodProtos(Module *Dest, const Module *Src,
238 map<const Value*, Value*> &ValueMap,
240 // We will need a module level symbol table if the src module has a module
241 // level symbol table...
242 SymbolTable *ST = Src->getSymbolTable() ? Dest->getSymbolTableSure() : 0;
244 // Loop over all of the methods in the src module, mapping them over as we go
246 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
247 const Method *SM = *I; // SrcMethod
250 // If the method has a name, and that name is already in use in the
251 // Dest module, make sure that the name is a compatible method...
253 if (SM->hasExternalLinkage() && SM->hasName() &&
254 (V = ST->lookup(SM->getType(), SM->getName())) &&
255 cast<Method>(V)->hasExternalLinkage()) {
256 // The same named thing is a Method, because the only two things
257 // that may be in a module level symbol table are Global Vars and Methods,
258 // and they both have distinct, nonoverlapping, possible types.
260 Method *DM = cast<Method>(V); // DestMethod
262 // Check to make sure the method is not defined in both modules...
263 if (!SM->isExternal() && !DM->isExternal())
264 return Error(Err, "Method '" +
265 SM->getMethodType()->getDescription() + "':\"" +
266 SM->getName() + "\" - Method is already defined!");
268 // Otherwise, just remember this mapping...
269 ValueMap.insert(std::make_pair(SM, DM));
271 // Method does not already exist, simply insert an external method
272 // signature identical to SM into the dest module...
273 Method *DM = new Method(SM->getMethodType(), SM->hasInternalLinkage(),
276 // Add the method signature to the dest module...
277 Dest->getMethodList().push_back(DM);
279 // ... and remember this mapping...
280 ValueMap.insert(std::make_pair(SM, DM));
286 // LinkMethodBody - Copy the source method over into the dest method and fix up
287 // references to values. At this point we know that Dest is an external method,
288 // and that Src is not.
290 static bool LinkMethodBody(Method *Dest, const Method *Src,
291 const map<const Value*, Value*> &GlobalMap,
293 assert(Src && Dest && Dest->isExternal() && !Src->isExternal());
294 map<const Value*, Value*> LocalMap; // Map for method local values
296 // Go through and convert method arguments over...
297 for (Method::ArgumentListType::const_iterator
298 I = Src->getArgumentList().begin(),
299 E = Src->getArgumentList().end(); I != E; ++I) {
300 const MethodArgument *SMA = *I;
302 // Create the new method argument and add to the dest method...
303 MethodArgument *DMA = new MethodArgument(SMA->getType(), SMA->getName());
304 Dest->getArgumentList().push_back(DMA);
306 // Add a mapping to our local map
307 LocalMap.insert(std::make_pair(SMA, DMA));
310 // Loop over all of the basic blocks, copying the instructions over...
312 for (Method::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
313 const BasicBlock *SBB = *I;
315 // Create new basic block and add to mapping and the Dest method...
316 BasicBlock *DBB = new BasicBlock(SBB->getName(), Dest);
317 LocalMap.insert(std::make_pair(SBB, DBB));
319 // Loop over all of the instructions in the src basic block, copying them
320 // over. Note that this is broken in a strict sense because the cloned
321 // instructions will still be referencing values in the Src module, not
322 // the remapped values. In our case, however, we will not get caught and
323 // so we can delay patching the values up until later...
325 for (BasicBlock::const_iterator II = SBB->begin(), IE = SBB->end();
327 const Instruction *SI = *II;
328 Instruction *DI = SI->clone();
329 DI->setName(SI->getName());
330 DBB->getInstList().push_back(DI);
331 LocalMap.insert(std::make_pair(SI, DI));
335 // At this point, all of the instructions and values of the method are now
336 // copied over. The only problem is that they are still referencing values
337 // in the Source method as operands. Loop through all of the operands of the
338 // methods and patch them up to point to the local versions...
340 for (Method::inst_iterator I = Dest->inst_begin(), E = Dest->inst_end();
342 Instruction *Inst = *I;
344 for (Instruction::op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
346 *OI = RemapOperand(*OI, LocalMap, &GlobalMap);
353 // LinkMethodBodies - Link in the method bodies that are defined in the source
354 // module into the DestModule. This consists basically of copying the method
355 // over and fixing up references to values.
357 static bool LinkMethodBodies(Module *Dest, const Module *Src,
358 map<const Value*, Value*> &ValueMap,
361 // Loop over all of the methods in the src module, mapping them over as we go
363 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
364 const Method *SM = *I; // Source Method
365 if (!SM->isExternal()) { // No body if method is external
366 Method *DM = cast<Method>(ValueMap[SM]); // Destination method
368 // DM not external SM external?
369 if (!DM->isExternal()) {
371 *Err = "Method '" + (SM->hasName() ? SM->getName() : string("")) +
372 "' body multiply defined!";
376 if (LinkMethodBody(DM, SM, ValueMap, Err)) return true;
384 // LinkModules - This function links two modules together, with the resulting
385 // left module modified to be the composite of the two input modules. If an
386 // error occurs, true is returned and ErrorMsg (if not null) is set to indicate
387 // the problem. Upon failure, the Dest module could be in a modified state, and
388 // shouldn't be relied on to be consistent.
390 bool LinkModules(Module *Dest, const Module *Src, string *ErrorMsg = 0) {
392 // LinkTypes - Go through the symbol table of the Src module and see if any
393 // types are named in the src module that are not named in the Dst module.
394 // Make sure there are no type name conflicts.
396 if (LinkTypes(Dest, Src, ErrorMsg)) return true;
398 // ValueMap - Mapping of values from what they used to be in Src, to what they
401 map<const Value*, Value*> ValueMap;
403 // Insert all of the globals in src into the Dest module... without
405 if (LinkGlobals(Dest, Src, ValueMap, ErrorMsg)) return true;
407 // Update the initializers in the Dest module now that all globals that may
408 // be referenced are in Dest.
410 if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true;
412 // Link the methods together between the two modules, without doing method
413 // bodies... this just adds external method prototypes to the Dest method...
414 // We do this so that when we begin processing method bodies, all of the
415 // global values that may be referenced are available in our ValueMap.
417 if (LinkMethodProtos(Dest, Src, ValueMap, ErrorMsg)) return true;
419 // Link in the method bodies that are defined in the source module into the
420 // DestModule. This consists basically of copying the method over and fixing
421 // up references to values.
423 if (LinkMethodBodies(Dest, Src, ValueMap, ErrorMsg)) return true;