lib/Linker/LinkModules.cpp

   1 //===- Linker.cpp - Module Linker Implementation --------------------------===//
   2 //
   3 // This file implements the LLVM module linker.
   4 //
   5 // Specifically, this:
   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
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Transforms/Linker.h"
  13 #include "llvm/Module.h"
  14 #include "llvm/Function.h"
  15 #include "llvm/BasicBlock.h"
  16 #include "llvm/GlobalVariable.h"
  17 #include "llvm/SymbolTable.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/iOther.h"
  20 #include "llvm/ConstantVals.h"
  21 #include <iostream>
  22 using std::cerr;
  23 using std::string;
  24 using std::map;
  25
  26 // Error - Simple wrapper function to conditionally assign to E and return true.
  27 // This just makes error return conditions a little bit simpler...
  28 //
  29 static inline bool Error(string *E, string Message) {
  30   if (E) *E = Message;
  31   return true;
  32 }
  33
  34 #include "llvm/Assembly/Writer.h" // TODO: REMOVE
  35
  36
  37 // LinkTypes - Go through the symbol table of the Src module and see if any
  38 // types are named in the src module that are not named in the Dst module.
  39 // Make sure there are no type name conflicts.
  40 //
  41 static bool LinkTypes(Module *Dest, const Module *Src, string *Err = 0) {
  42   // No symbol table?  Can't have named types.
  43   if (!Src->hasSymbolTable()) return false;
  44
  45   SymbolTable       *DestST = Dest->getSymbolTableSure();
  46   const SymbolTable *SrcST  = Src->getSymbolTable();
  47
  48   // Look for a type plane for Type's...
  49   SymbolTable::const_iterator PI = SrcST->find(Type::TypeTy);
  50   if (PI == SrcST->end()) return false;  // No named types, do nothing.
  51
  52   const SymbolTable::VarMap &VM = PI->second;
  53   for (SymbolTable::type_const_iterator I = VM.begin(), E = VM.end();
  54        I != E; ++I) {
  55     const string &Name = I->first;
  56     const Type *RHS = cast<Type>(I->second);
  57
  58     // Check to see if this type name is already in the dest module...
  59     const Type *Entry = cast_or_null<Type>(DestST->lookup(Type::TypeTy, Name));
  60     if (Entry) {     // Yup, the value already exists...
  61       if (Entry != RHS)            // If it's the same, noop.  Otherwise, error.
  62         return Error(Err, "Type named '" + Name +
  63                      "' of different shape in modules.\n  Src='" +
  64                      Entry->getDescription() + "'.\n  Dst='" +
  65                      RHS->getDescription() + "'");
  66     } else {                       // Type not in dest module.  Add it now.
  67       // TODO: FIXME WHEN TYPES AREN'T CONST
  68       DestST->insert(Name, const_cast<Type*>(RHS));
  69     }
  70   }
  71   return false;
  72 }
  73
  74 static void PrintMap(const map<const Value*, Value*> &M) {
  75   for (map<const Value*, Value*>::const_iterator I = M.begin(), E = M.end();
  76        I != E; ++I) {
  77     cerr << " Fr: " << (void*)I->first << " " << I->first
  78          << " To: " << (void*)I->second << " " << I->second << "\n";
  79   }
  80 }
  81
  82
  83 // RemapOperand - Use LocalMap and GlobalMap to convert references from one
  84 // module to another.  This is somewhat sophisticated in that it can
  85 // automatically handle constant references correctly as well...
  86 //
  87 static Value *RemapOperand(const Value *In, map<const Value*, Value*> &LocalMap,
  88                            const map<const Value*, Value*> *GlobalMap = 0) {
  89   map<const Value*,Value*>::const_iterator I = LocalMap.find(In);
  90   if (I != LocalMap.end()) return I->second;
  91
  92   if (GlobalMap) {
  93     I = GlobalMap->find(In);
  94     if (I != GlobalMap->end()) return I->second;
  95   }
  96
  97   // Check to see if it's a constant that we are interesting in transforming...
  98   if (Constant *CPV = dyn_cast<Constant>(In)) {
  99     if (!isa<DerivedType>(CPV->getType()))
 100       return CPV;              // Simple constants stay identical...
 101
 102     Constant *Result = 0;
 103
 104     if (ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) {
 105       const std::vector<Use> &Ops = CPA->getValues();
 106       std::vector<Constant*> Operands(Ops.size());
 107       for (unsigned i = 0; i < Ops.size(); ++i)
 108         Operands[i] =
 109           cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
 110       Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands);
 111     } else if (ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) {
 112       const std::vector<Use> &Ops = CPS->getValues();
 113       std::vector<Constant*> Operands(Ops.size());
 114       for (unsigned i = 0; i < Ops.size(); ++i)
 115         Operands[i] =
 116           cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
 117       Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands);
 118     } else if (isa<ConstantPointerNull>(CPV)) {
 119       Result = CPV;
 120     } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(CPV)) {
 121       Value *V = RemapOperand(CPR->getValue(), LocalMap, GlobalMap);
 122       Result = ConstantPointerRef::get(cast<GlobalValue>(V));
 123     } else {
 124       assert(0 && "Unknown type of derived type constant value!");
 125     }
 126
 127     // Cache the mapping in our local map structure...
 128     LocalMap.insert(std::make_pair(In, CPV));
 129     return Result;
 130   }
 131
 132   cerr << "XXX LocalMap: \n";
 133   PrintMap(LocalMap);
 134
 135   if (GlobalMap) {
 136     cerr << "XXX GlobalMap: \n";
 137     PrintMap(*GlobalMap);
 138   }
 139
 140   cerr << "Couldn't remap value: " << (void*)In << " " << In << "\n";
 141   assert(0 && "Couldn't remap value!");
 142   return 0;
 143 }
 144
 145
 146 // LinkGlobals - Loop through the global variables in the src module and merge
 147 // them into the dest module...
 148 //
 149 static bool LinkGlobals(Module *Dest, const Module *Src,
 150                         map<const Value*, Value*> &ValueMap, string *Err = 0) {
 151   // We will need a module level symbol table if the src module has a module
 152   // level symbol table...
 153   SymbolTable *ST = Src->getSymbolTable() ? Dest->getSymbolTableSure() : 0;
 154
 155   // Loop over all of the globals in the src module, mapping them over as we go
 156   //
 157   for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
 158     const GlobalVariable *SGV = *I;
 159     Value *V;
 160
 161     // If the global variable has a name, and that name is already in use in the
 162     // Dest module, make sure that the name is a compatible global variable...
 163     //
 164     if (SGV->hasExternalLinkage() && SGV->hasName() &&
 165         (V = ST->lookup(SGV->getType(), SGV->getName())) &&
 166         cast<GlobalVariable>(V)->hasExternalLinkage()) {
 167       // The same named thing is a global variable, because the only two things
 168       // that may be in a module level symbol table are Global Vars and
 169       // Functions, and they both have distinct, nonoverlapping, possible types.
 170       //
 171       GlobalVariable *DGV = cast<GlobalVariable>(V);
 172
 173       // Check to see if the two GV's have the same Const'ness...
 174       if (SGV->isConstant() != DGV->isConstant())
 175         return Error(Err, "Global Variable Collision on '" +
 176                      SGV->getType()->getDescription() + "':%" + SGV->getName() +
 177                      " - Global variables differ in const'ness");
 178
 179       // Okay, everything is cool, remember the mapping...
 180       ValueMap.insert(std::make_pair(SGV, DGV));
 181     } else {
 182       // No linking to be performed, simply create an identical version of the
 183       // symbol over in the dest module... the initializer will be filled in
 184       // later by LinkGlobalInits...
 185       //
 186       GlobalVariable *DGV =
 187         new GlobalVariable(SGV->getType()->getElementType(), SGV->isConstant(),
 188                            SGV->hasInternalLinkage(), 0, SGV->getName());
 189
 190       // Add the new global to the dest module
 191       Dest->getGlobalList().push_back(DGV);
 192
 193       // Make sure to remember this mapping...
 194       ValueMap.insert(std::make_pair(SGV, DGV));
 195     }
 196   }
 197   return false;
 198 }
 199
 200
 201 // LinkGlobalInits - Update the initializers in the Dest module now that all
 202 // globals that may be referenced are in Dest.
 203 //
 204 static bool LinkGlobalInits(Module *Dest, const Module *Src,
 205                             map<const Value*, Value*> &ValueMap,
 206                             string *Err = 0) {
 207
 208   // Loop over all of the globals in the src module, mapping them over as we go
 209   //
 210   for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
 211     const GlobalVariable *SGV = *I;
 212
 213     if (SGV->hasInitializer()) {      // Only process initialized GV's
 214       // Figure out what the initializer looks like in the dest module...
 215       Constant *DInit =
 216         cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap));
 217
 218       GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]);
 219       if (DGV->hasInitializer() && SGV->hasExternalLinkage() &&
 220           DGV->hasExternalLinkage()) {
 221         if (DGV->getInitializer() != DInit)
 222           return Error(Err, "Global Variable Collision on '" +
 223                        SGV->getType()->getDescription() + "':%" +SGV->getName()+
 224                        " - Global variables have different initializers");
 225       } else {
 226         // Copy the initializer over now...
 227         DGV->setInitializer(DInit);
 228       }
 229     }
 230   }
 231   return false;
 232 }
 233
 234 // LinkFunctionProtos - Link the functions together between the two modules,
 235 // without doing method bodies... this just adds external method prototypes to
 236 // the Dest function...
 237 //
 238 static bool LinkFunctionProtos(Module *Dest, const Module *Src,
 239                                map<const Value*, Value*> &ValueMap,
 240                                string *Err = 0) {
 241   // We will need a module level symbol table if the src module has a module
 242   // level symbol table...
 243   SymbolTable *ST = Src->getSymbolTable() ? Dest->getSymbolTableSure() : 0;
 244
 245   // Loop over all of the methods in the src module, mapping them over as we go
 246   //
 247   for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
 248     const Function *SM = *I;   // SrcFunction
 249     Value *V;
 250
 251     // If the method has a name, and that name is already in use in the
 252     // Dest module, make sure that the name is a compatible method...
 253     //
 254     if (SM->hasExternalLinkage() && SM->hasName() &&
 255         (V = ST->lookup(SM->getType(), SM->getName())) &&
 256         cast<Function>(V)->hasExternalLinkage()) {
 257       // The same named thing is a Function, because the only two things
 258       // that may be in a module level symbol table are Global Vars and
 259       // Functions, and they both have distinct, nonoverlapping, possible types.
 260       //
 261       Function *DM = cast<Function>(V);   // DestFunction
 262
 263       // Check to make sure the method is not defined in both modules...
 264       if (!SM->isExternal() && !DM->isExternal())
 265         return Error(Err, "Function '" +
 266                      SM->getMethodType()->getDescription() + "':\"" +
 267                      SM->getName() + "\" - Function is already defined!");
 268
 269       // Otherwise, just remember this mapping...
 270       ValueMap.insert(std::make_pair(SM, DM));
 271     } else {
 272       // Function does not already exist, simply insert an external method
 273       // signature identical to SM into the dest module...
 274       Function *DM = new Function(SM->getMethodType(), SM->hasInternalLinkage(),
 275                                   SM->getName());
 276
 277       // Add the method signature to the dest module...
 278       Dest->getFunctionList().push_back(DM);
 279
 280       // ... and remember this mapping...
 281       ValueMap.insert(std::make_pair(SM, DM));
 282     }
 283   }
 284   return false;
 285 }
 286
 287 // LinkFunctionBody - Copy the source method over into the dest method
 288 // and fix up references to values.  At this point we know that Dest
 289 // is an external method, and that Src is not.
 290 //
 291 static bool LinkFunctionBody(Function *Dest, const Function *Src,
 292                              const map<const Value*, Value*> &GlobalMap,
 293                              string *Err = 0) {
 294   assert(Src && Dest && Dest->isExternal() && !Src->isExternal());
 295   map<const Value*, Value*> LocalMap;   // Map for method local values
 296
 297   // Go through and convert method arguments over...
 298   for (Function::ArgumentListType::const_iterator
 299          I = Src->getArgumentList().begin(),
 300          E = Src->getArgumentList().end(); I != E; ++I) {
 301     const FunctionArgument *SMA = *I;
 302
 303     // Create the new method argument and add to the dest method...
 304     FunctionArgument *DMA = new FunctionArgument(SMA->getType(),SMA->getName());
 305     Dest->getArgumentList().push_back(DMA);
 306
 307     // Add a mapping to our local map
 308     LocalMap.insert(std::make_pair(SMA, DMA));
 309   }
 310
 311   // Loop over all of the basic blocks, copying the instructions over...
 312   //
 313   for (Function::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
 314     const BasicBlock *SBB = *I;
 315
 316     // Create new basic block and add to mapping and the Dest method...
 317     BasicBlock *DBB = new BasicBlock(SBB->getName(), Dest);
 318     LocalMap.insert(std::make_pair(SBB, DBB));
 319
 320     // Loop over all of the instructions in the src basic block, copying them
 321     // over.  Note that this is broken in a strict sense because the cloned
 322     // instructions will still be referencing values in the Src module, not
 323     // the remapped values.  In our case, however, we will not get caught and
 324     // so we can delay patching the values up until later...
 325     //
 326     for (BasicBlock::const_iterator II = SBB->begin(), IE = SBB->end();
 327          II != IE; ++II) {
 328       const Instruction *SI = *II;
 329       Instruction *DI = SI->clone();
 330       DI->setName(SI->getName());
 331       DBB->getInstList().push_back(DI);
 332       LocalMap.insert(std::make_pair(SI, DI));
 333     }
 334   }
 335
 336   // At this point, all of the instructions and values of the method are now
 337   // copied over.  The only problem is that they are still referencing values
 338   // in the Source method as operands.  Loop through all of the operands of the
 339   // methods and patch them up to point to the local versions...
 340   //
 341   for (Function::iterator BI = Dest->begin(), BE = Dest->end();
 342        BI != BE; ++BI) {
 343     BasicBlock *BB = *BI;
 344     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 345       Instruction *Inst = *I;
 346
 347       for (Instruction::op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
 348            OI != OE; ++OI)
 349         *OI = RemapOperand(*OI, LocalMap, &GlobalMap);
 350     }
 351   }
 352
 353   return false;
 354 }
 355
 356
 357 // LinkFunctionBodies - Link in the method bodies that are defined in the source
 358 // module into the DestModule.  This consists basically of copying the method
 359 // over and fixing up references to values.
 360 //
 361 static bool LinkFunctionBodies(Module *Dest, const Module *Src,
 362                                map<const Value*, Value*> &ValueMap,
 363                                string *Err = 0) {
 364
 365   // Loop over all of the methods in the src module, mapping them over as we go
 366   //
 367   for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
 368     const Function *SM = *I;                   // Source Function
 369     if (!SM->isExternal()) {                   // No body if method is external
 370       Function *DM = cast<Function>(ValueMap[SM]); // Destination method
 371
 372       // DM not external SM external?
 373       if (!DM->isExternal()) {
 374         if (Err)
 375           *Err = "Function '" + (SM->hasName() ? SM->getName() : string("")) +
 376                  "' body multiply defined!";
 377         return true;
 378       }
 379
 380       if (LinkFunctionBody(DM, SM, ValueMap, Err)) return true;
 381     }
 382   }
 383   return false;
 384 }
 385
 386
 387
 388 // LinkModules - This function links two modules together, with the resulting
 389 // left module modified to be the composite of the two input modules.  If an
 390 // error occurs, true is returned and ErrorMsg (if not null) is set to indicate
 391 // the problem.  Upon failure, the Dest module could be in a modified state, and
 392 // shouldn't be relied on to be consistent.
 393 //
 394 bool LinkModules(Module *Dest, const Module *Src, string *ErrorMsg = 0) {
 395
 396   // LinkTypes - Go through the symbol table of the Src module and see if any
 397   // types are named in the src module that are not named in the Dst module.
 398   // Make sure there are no type name conflicts.
 399   //
 400   if (LinkTypes(Dest, Src, ErrorMsg)) return true;
 401
 402   // ValueMap - Mapping of values from what they used to be in Src, to what they
 403   // are now in Dest.
 404   //
 405   map<const Value*, Value*> ValueMap;
 406
 407   // Insert all of the globals in src into the Dest module... without
 408   // initializers
 409   if (LinkGlobals(Dest, Src, ValueMap, ErrorMsg)) return true;
 410
 411   // Update the initializers in the Dest module now that all globals that may
 412   // be referenced are in Dest.
 413   //
 414   if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true;
 415
 416   // Link the methods together between the two modules, without doing method
 417   // bodies... this just adds external method prototypes to the Dest method...
 418   // We do this so that when we begin processing method bodies, all of the
 419   // global values that may be referenced are available in our ValueMap.
 420   //
 421   if (LinkFunctionProtos(Dest, Src, ValueMap, ErrorMsg)) return true;
 422
 423   // Link in the method bodies that are defined in the source module into the
 424   // DestModule.  This consists basically of copying the method over and fixing
 425   // up references to values.
 426   //
 427   if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true;
 428
 429   return false;
 430 }
 431