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