lib/Linker/LinkArchives.cpp

   1 //===- gccld.cpp - LLVM 'ld' compatible linker ----------------------------===//
   2 //
   3 // This utility is intended to be compatible with GCC, and follows standard
   4 // system 'ld' conventions.  As such, the default output file is ./a.out.
   5 // Additionally, this program outputs a shell script that is used to invoke LLI
   6 // to execute the program.  In this manner, the generated executable (a.out for
   7 // example), is directly executable, whereas the bytecode file actually lives in
   8 // the a.out.bc file generated by this program.  Also, Force is on by default.
   9 //
  10 // Note that if someone (or a script) deletes the executable program generated,
  11 // the .bc file will be left around.  Considering that this is a temporary hack,
  12 // I'm not too worried about this.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Utils/Linker.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/PassManager.h"
  19 #include "llvm/Bytecode/Reader.h"
  20 #include "llvm/Bytecode/WriteBytecodePass.h"
  21 #include "llvm/Target/TargetData.h"
  22 #include "llvm/Transforms/IPO.h"
  23 #include "llvm/Transforms/Scalar.h"
  24 #include "Support/FileUtilities.h"
  25 #include "Support/SystemUtils.h"
  26 #include "Support/CommandLine.h"
  27 #include "Support/Signals.h"
  28 #include "Config/stdlib.h"
  29 #include "gccld.h"
  30
  31 #include <fstream>
  32 #include <memory>
  33 #include <set>
  34 #include <algorithm>
  35
  36 //
  37 // Function: FileExists ()
  38 //
  39 // Description:
  40 //  Determine if the specified filename exists and is readable.
  41 //
  42 // Inputs:
  43 //  FN - The name of the file.
  44 //
  45 // Outputs:
  46 //  None.
  47 //
  48 // Return Value:
  49 //  TRUE - The file exists and is readable.
  50 //  FALSE - The file does not exist or is unreadable.
  51 //
  52 static inline bool
  53 FileExists(const std::string &FN)
  54 {
  55   return access(FN.c_str(), R_OK | F_OK) != -1;
  56 }
  57
  58 //
  59 // Function: IsArchive ()
  60 //
  61 // Description:
  62 //  Determine if the specified file is an ar archive.  It determines this by
  63 //  checking the magic string at the beginning of the file.
  64 //
  65 // Inputs:
  66 //  filename - A C++ string containing the name of the file.
  67 //
  68 // Outputs:
  69 //  None.
  70 //
  71 // Return value:
  72 //  TRUE  - The file is an archive.
  73 //  FALSE - The file is not an archive.
  74 //
  75 static inline bool
  76 IsArchive (const std::string &filename)
  77 {
  78   std::string ArchiveMagic("!<arch>\012");
  79   char buf[1 + ArchiveMagic.size()];
  80
  81   std::ifstream f(filename.c_str());
  82   f.read(buf, ArchiveMagic.size());
  83   buf[ArchiveMagic.size()] = '\0';
  84   return ArchiveMagic == buf;
  85 }
  86
  87 //
  88 // Function: FindLib ()
  89 //
  90 // Description:
  91 //  This function locates a particular library.  It will prepend and append
  92 //  various directories, prefixes, and suffixes until it can find the library.
  93 //
  94 // Inputs:
  95 //  Filename  - Name of the file to find.
  96 //  Paths     - List of directories to search.
  97 //
  98 // Outputs:
  99 //  None.
 100 //
 101 // Return value:
 102 //  The name of the file is returned.
 103 //  If the file is not found, an empty string is returned.
 104 //
 105 static std::string
 106 FindLib (const std::string & Filename, const std::vector<std::string> & Paths)
 107 {
 108   //
 109   // Determine if the pathname can be found as it stands.
 110   //
 111   if (FileExists (Filename))
 112   {
 113     return Filename;
 114   }
 115
 116   //
 117   // If that doesn't work, convert the name into a library name.
 118   //
 119   std::string LibName = "lib" + Filename;
 120
 121   //
 122   // Iterate over the directories in Paths to see if we can find the library
 123   // there.
 124   //
 125   for (unsigned Index = 0; Index != Paths.size(); ++Index)
 126   {
 127     std::string Directory = Paths[Index] + "/";
 128
 129     if (FileExists (Directory + LibName + ".bc"))
 130     {
 131       return Directory + LibName + ".bc";
 132     }
 133
 134     if (FileExists (Directory + LibName + ".so"))
 135     {
 136       return Directory + LibName + ".so";
 137     }
 138
 139     if (FileExists (Directory + LibName + ".a"))
 140     {
 141       return Directory + LibName + ".a";
 142     }
 143   }
 144
 145   //
 146   // One last hope: Check LLVM_LIB_SEARCH_PATH.
 147   //
 148   char *SearchPath = getenv("LLVM_LIB_SEARCH_PATH");
 149   if (SearchPath == NULL)
 150   {
 151         return std::string();
 152   }
 153
 154   LibName = std::string(SearchPath) + "/" + LibName;
 155   if (FileExists (LibName))
 156   {
 157     return LibName;
 158   }
 159
 160   return std::string();
 161 }
 162
 163 //
 164 // Function: GetAllDefinedSymbols ()
 165 //
 166 // Description:
 167 //  Find all of the defined symbols in the specified module.
 168 //
 169 // Inputs:
 170 //  M - The module in which to find defined symbols.
 171 //
 172 // Outputs:
 173 //  DefinedSymbols - A set of C++ strings that will contain the name of all
 174 //                   defined symbols.
 175 //
 176 // Return value:
 177 //  None.
 178 //
 179 void
 180 GetAllDefinedSymbols (Module *M, std::set<std::string> &DefinedSymbols)
 181 {
 182   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 183     if (I->hasName() && !I->isExternal() && !I->hasInternalLinkage())
 184       DefinedSymbols.insert(I->getName());
 185   for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I)
 186     if (I->hasName() && !I->isExternal() && !I->hasInternalLinkage())
 187       DefinedSymbols.insert(I->getName());
 188 }
 189
 190 //
 191 // Function: GetAllUndefinedSymbols ()
 192 //
 193 // Description:
 194 //  This calculates the set of undefined symbols that still exist in an LLVM
 195 //  module.  This is a bit tricky because there may be two symbols with the
 196 //  same name but different LLVM types that will be resolved to each other but
 197 //  aren't currently (thus we need to treat it as resolved).
 198 //
 199 // Inputs:
 200 //  M - The module in which to find undefined symbols.
 201 //
 202 // Outputs:
 203 //  UndefinedSymbols - A set of C++ strings containing the name of all
 204 //                     undefined symbols.
 205 //
 206 // Return value:
 207 //  None.
 208 //
 209 void
 210 GetAllUndefinedSymbols(Module *M, std::set<std::string> &UndefinedSymbols)
 211 {
 212   std::set<std::string> DefinedSymbols;
 213   UndefinedSymbols.clear();   // Start out empty
 214
 215   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 216     if (I->hasName()) {
 217       if (I->isExternal())
 218         UndefinedSymbols.insert(I->getName());
 219       else if (!I->hasInternalLinkage())
 220         DefinedSymbols.insert(I->getName());
 221     }
 222   for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I)
 223     if (I->hasName()) {
 224       if (I->isExternal())
 225         UndefinedSymbols.insert(I->getName());
 226       else if (!I->hasInternalLinkage())
 227         DefinedSymbols.insert(I->getName());
 228     }
 229
 230   // Prune out any defined symbols from the undefined symbols set...
 231   for (std::set<std::string>::iterator I = UndefinedSymbols.begin();
 232        I != UndefinedSymbols.end(); )
 233     if (DefinedSymbols.count(*I))
 234       UndefinedSymbols.erase(I++);  // This symbol really is defined!
 235     else
 236       ++I; // Keep this symbol in the undefined symbols list
 237 }
 238
 239
 240 //
 241 // Function: LoadObject ()
 242 //
 243 // Description:
 244 //  Read the specified bytecode object file.
 245 //
 246 // Inputs:
 247 //  FN - The name of the file to load.
 248 //
 249 // Outputs:
 250 //  OutErrorMessage - The error message to give back to the caller.
 251 //
 252 // Return Value:
 253 //  A pointer to a module represening the bytecode file is returned.
 254 //  If an error occurs, the pointer is 0.
 255 //
 256 std::auto_ptr<Module>
 257 LoadObject (const std::string & FN, std::string &OutErrorMessage)
 258 {
 259   std::string ErrorMessage;
 260   Module *Result = ParseBytecodeFile(FN, &ErrorMessage);
 261   if (Result) return std::auto_ptr<Module>(Result);
 262
 263   OutErrorMessage = "Bytecode file '" + FN + "' corrupt!";
 264   if (ErrorMessage.size()) OutErrorMessage += ": " + ErrorMessage;
 265   return std::auto_ptr<Module>();
 266 }
 267
 268 //
 269 // Function: LinkInArchive ()
 270 //
 271 // Description:
 272 //  This function will open an archive library and link in all objects which
 273 //  provide symbols that are currently undefined.
 274 //
 275 // Inputs:
 276 //  M        - The module in which to link the archives.
 277 //  Filename - The pathname of the archive.
 278 //  Verbose  - Flags whether verbose messages should be printed.
 279 //
 280 // Outputs:
 281 //  ErrorMessage - A C++ string detailing what error occurred, if any.
 282 //
 283 // Return Value:
 284 //  TRUE  - An error occurred.
 285 //  FALSE - No errors.
 286 //
 287 static bool
 288 LinkInArchive (Module * M,
 289                const std::string & Filename,
 290                std::string & ErrorMessage,
 291                bool Verbose)
 292 {
 293   //
 294   // Find all of the symbols currently undefined in the bytecode program.
 295   // If all the symbols are defined, the program is complete, and there is
 296   // no reason to link in any archive files.
 297   //
 298   std::set<std::string> UndefinedSymbols;
 299   GetAllUndefinedSymbols (M, UndefinedSymbols);
 300   if (UndefinedSymbols.empty())
 301   {
 302     if (Verbose) std::cerr << "  No symbols undefined, don't link library!\n";
 303     return false;  // No need to link anything in!
 304   }
 305
 306   //
 307   // Load in the archive objects.
 308   //
 309   if (Verbose) std::cerr << "  Loading '" << Filename << "'\n";
 310   std::vector<Module*> Objects;
 311   if (ReadArchiveFile (Filename, Objects, &ErrorMessage))
 312   {
 313     return true;
 314   }
 315
 316   //
 317   // Figure out which symbols are defined by all of the modules in the archive.
 318   //
 319   std::vector<std::set<std::string> > DefinedSymbols;
 320   DefinedSymbols.resize (Objects.size());
 321   for (unsigned i = 0; i != Objects.size(); ++i)
 322   {
 323     GetAllDefinedSymbols(Objects[i], DefinedSymbols[i]);
 324   }
 325
 326   // While we are linking in object files, loop.
 327   bool Linked = true;
 328   while (Linked)
 329   {
 330     Linked = false;
 331
 332     for (unsigned i = 0; i != Objects.size(); ++i) {
 333       // Consider whether we need to link in this module...  we only need to
 334       // link it in if it defines some symbol which is so far undefined.
 335       //
 336       const std::set<std::string> &DefSymbols = DefinedSymbols[i];
 337
 338       bool ObjectRequired = false;
 339       for (std::set<std::string>::iterator I = UndefinedSymbols.begin(),
 340              E = UndefinedSymbols.end(); I != E; ++I)
 341         if (DefSymbols.count(*I)) {
 342           if (Verbose)
 343             std::cerr << "  Found object providing symbol '" << *I << "'...\n";
 344           ObjectRequired = true;
 345           break;
 346         }
 347
 348       // We DO need to link this object into the program...
 349       if (ObjectRequired) {
 350         if (LinkModules(M, Objects[i], &ErrorMessage))
 351           return true;   // Couldn't link in the right object file...
 352
 353         // Since we have linked in this object, delete it from the list of
 354         // objects to consider in this archive file.
 355         std::swap(Objects[i], Objects.back());
 356         std::swap(DefinedSymbols[i], DefinedSymbols.back());
 357         Objects.pop_back();
 358         DefinedSymbols.pop_back();
 359         --i;   // Do not skip an entry
 360
 361         // The undefined symbols set should have shrunk.
 362         GetAllUndefinedSymbols(M, UndefinedSymbols);
 363         Linked = true;  // We have linked something in!
 364       }
 365     }
 366   }
 367
 368   return false;
 369 }
 370
 371 //
 372 // Function: LinkInFile ()
 373 //
 374 // Description:
 375 //  This function will open an archive library and link in all objects which
 376 //  provide symbols that are currently undefined.
 377 //
 378 // Inputs:
 379 //  HeadModule - The module in which to link the archives.
 380 //  Filename   - The pathname of the archive.
 381 //  Verbose    - Flags whether verbose messages should be printed.
 382 //
 383 // Outputs:
 384 //  ErrorMessage - A C++ string detailing what error occurred, if any.
 385 //
 386 // Return Value:
 387 //  TRUE  - An error occurred.
 388 //  FALSE - No errors.
 389 //
 390 static bool
 391 LinkInFile (Module * HeadModule,
 392             const std::string & Filename,
 393             std::string & ErrorMessage,
 394             bool Verbose)
 395 {
 396   std::auto_ptr<Module> M(LoadObject(Filename, ErrorMessage));
 397   if (M.get() == 0)
 398   {
 399     return true;
 400   }
 401
 402   if (Verbose) std::cerr << "Linking in '" << Filename << "'\n";
 403
 404   return (LinkModules (HeadModule, M.get(), &ErrorMessage));
 405 }
 406
 407 //
 408 // Function: LinkFiles ()
 409 //
 410 // Description:
 411 //  This function takes a module and a list of files and links them all
 412 //  together.  It locates the file either in the current directory, as it's
 413 //  absolute or relative pathname, or as a file somewhere in
 414 //  LLVM_LIB_SEARCH_PATH.
 415 //
 416 // Inputs:
 417 //  progname   - The name of the program (infamous argv[0]).
 418 //  HeadModule - The module under which all files will be linked.
 419 //  Files      - A vector of C++ strings indicating the LLVM bytecode filenames
 420 //               to be linked.  The names can refer to a mixture of pure LLVM
 421 //               bytecode files and archive (ar) formatted files.
 422 //  Verbose    - Flags whether verbose output should be printed while linking.
 423 //
 424 // Outputs:
 425 //  HeadModule - The module will have the specified LLVM bytecode files linked
 426 //               in.
 427 //
 428 // Return value:
 429 //  FALSE - No errors.
 430 //  TRUE  - Some error occurred.
 431 //
 432 bool
 433 LinkFiles (const char * progname,
 434            Module * HeadModule,
 435            const std::vector<std::string> & Files,
 436            bool Verbose)
 437 {
 438   // String in which to receive error messages.
 439   std::string ErrorMessage;
 440
 441   // Full pathname of the file
 442   std::string Pathname;
 443
 444   // Get the library search path from the environment
 445   char *SearchPath = getenv("LLVM_LIB_SEARCH_PATH");
 446
 447   for (unsigned i = 1; i < Files.size(); ++i)
 448   {
 449     //
 450     // Determine where this file lives.
 451     //
 452     if (FileExists (Files[i]))
 453     {
 454       Pathname = Files[i];
 455     }
 456     else
 457     {
 458       if (SearchPath == NULL)
 459       {
 460         std::cerr << "Cannot find " << Files[i];
 461         return true;
 462       }
 463
 464       Pathname = std::string(SearchPath)+"/"+Files[i];
 465       if (!FileExists (Pathname))
 466       {
 467         std::cerr << "Cannot find " << Files[i];
 468         return true;
 469       }
 470     }
 471
 472     //
 473     // A user may specify an ar archive without -l, perhaps because it
 474     // is not installed as a library. Detect that and link the library.
 475     //
 476     if (IsArchive(Pathname))
 477     {
 478       if (Verbose)
 479       {
 480         std::cerr << "Linking archive '" << Files[i] << "'\n";
 481       }
 482
 483       if (LinkInArchive (HeadModule, Pathname, ErrorMessage, Verbose))
 484       {
 485         PrintAndReturn(progname, ErrorMessage,
 486                               ": Error linking in '" + Files[i] + "'");
 487         return true;
 488       }
 489     }
 490     else
 491     {
 492       if (Verbose)
 493       {
 494         std::cerr << "Linking file '" << Files[i] << "'\n";
 495       }
 496
 497       if (LinkInFile (HeadModule, Pathname, ErrorMessage, Verbose))
 498       {
 499         PrintAndReturn(progname, ErrorMessage,
 500                               ": error linking in '" + Files[i] + "'");
 501         return true;
 502       }
 503     }
 504   }
 505
 506   return false;
 507 }
 508
 509 //
 510 // Function: LinkLibraries ()
 511 //
 512 // Description:
 513 //  This function takes the specified library files and links them into the
 514 //  main bytecode object file.
 515 //
 516 // Inputs:
 517 //  progname   - The name of the program (infamous argv[0]).
 518 //  HeadModule - The module into which all necessary libraries will be linked.
 519 //  Libraries  - The list of libraries to link into the module.
 520 //  LibPaths   - The list of library paths in which to find libraries.
 521 //  Verbose    - Flags whether verbose messages should be printed.
 522 //  Native     - Flags whether native code is being generated.
 523 //
 524 // Outputs:
 525 //  HeadModule - The module will have all necessary libraries linked in.
 526 //
 527 // Return value:
 528 //  FALSE - No error.
 529 //  TRUE  - Error.
 530 //
 531 bool
 532 LinkLibraries (const char * progname,
 533                Module * HeadModule,
 534                const std::vector<std::string> & Libraries,
 535                const std::vector<std::string> & LibPaths,
 536                bool Verbose,
 537                bool Native)
 538 {
 539   // String in which to receive error messages.
 540   std::string ErrorMessage;
 541
 542   for (unsigned i = 1; i < Libraries.size(); ++i)
 543   {
 544     //
 545     // Determine where this library lives.
 546     //
 547     std::string Pathname = FindLib (Libraries[i], LibPaths);
 548     if (Pathname.empty())
 549     {
 550       //
 551       // If the pathname does not exist, then continue to the next one if
 552       // we're doing a native link and give an error if we're doing a bytecode
 553       // link.
 554       //
 555       if (Native)
 556       {
 557         continue;
 558       }
 559       else
 560       {
 561         PrintAndReturn (progname, "Cannot find " + Libraries[i]);
 562         return true;
 563       }
 564     }
 565
 566     //
 567     // A user may specify an ar archive without -l, perhaps because it
 568     // is not installed as a library. Detect that and link the library.
 569     //
 570     if (IsArchive(Pathname))
 571     {
 572       if (Verbose)
 573       {
 574         std::cerr << "Linking archive '" << Libraries[i] << "'\n";
 575       }
 576
 577       if (LinkInArchive (HeadModule, Pathname, ErrorMessage, Verbose))
 578       {
 579         PrintAndReturn(progname, ErrorMessage,
 580                               ": Error linking in '" + Libraries[i] + "'");
 581         return true;
 582       }
 583     }
 584     else
 585     {
 586       if (Verbose)
 587       {
 588         std::cerr << "Linking file '" << Libraries[i] << "'\n";
 589       }
 590
 591       if (LinkInFile (HeadModule, Pathname, ErrorMessage, Verbose))
 592       {
 593         PrintAndReturn(progname, ErrorMessage,
 594                               ": error linking in '" + Libraries[i] + "'");
 595         return true;
 596       }
 597     }
 598   }
 599
 600   return false;
 601 }