tools/lto/LTOModule.cpp

   1 //===-- LTOModule.cpp - LLVM Link Time Optimizer --------------------------===//
   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 implements the Link Time Optimization library. This library is
  11 // intended to be used by linker to optimize code at link time.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "LTOModule.h"
  16
  17 #include "llvm/Constants.h"
  18 #include "llvm/LLVMContext.h"
  19 #include "llvm/Module.h"
  20 #include "llvm/ADT/OwningPtr.h"
  21 #include "llvm/ADT/Triple.h"
  22 #include "llvm/Bitcode/ReaderWriter.h"
  23 #include "llvm/Support/SystemUtils.h"
  24 #include "llvm/Support/MemoryBuffer.h"
  25 #include "llvm/Support/MathExtras.h"
  26 #include "llvm/System/Host.h"
  27 #include "llvm/System/Path.h"
  28 #include "llvm/System/Process.h"
  29 #include "llvm/Target/Mangler.h"
  30 #include "llvm/Target/SubtargetFeature.h"
  31 #include "llvm/MC/MCAsmInfo.h"
  32 #include "llvm/MC/MCContext.h"
  33 #include "llvm/Target/TargetMachine.h"
  34 #include "llvm/Target/TargetRegistry.h"
  35 #include "llvm/Target/TargetSelect.h"
  36
  37 using namespace llvm;
  38
  39 bool LTOModule::isBitcodeFile(const void *mem, size_t length) {
  40   return llvm::sys::IdentifyFileType((char*)mem, length)
  41     == llvm::sys::Bitcode_FileType;
  42 }
  43
  44 bool LTOModule::isBitcodeFile(const char *path) {
  45   return llvm::sys::Path(path).isBitcodeFile();
  46 }
  47
  48 bool LTOModule::isBitcodeFileForTarget(const void *mem, size_t length,
  49                                        const char *triplePrefix) {
  50   MemoryBuffer *buffer = makeBuffer(mem, length);
  51   if (!buffer)
  52     return false;
  53   return isTargetMatch(buffer, triplePrefix);
  54 }
  55
  56
  57 bool LTOModule::isBitcodeFileForTarget(const char *path,
  58                                        const char *triplePrefix) {
  59   MemoryBuffer *buffer = MemoryBuffer::getFile(path);
  60   if (buffer == NULL)
  61     return false;
  62   return isTargetMatch(buffer, triplePrefix);
  63 }
  64
  65 // Takes ownership of buffer.
  66 bool LTOModule::isTargetMatch(MemoryBuffer *buffer, const char *triplePrefix) {
  67   std::string Triple = getBitcodeTargetTriple(buffer, getGlobalContext());
  68   delete buffer;
  69   return (strncmp(Triple.c_str(), triplePrefix,
  70                   strlen(triplePrefix)) == 0);
  71 }
  72
  73
  74 LTOModule::LTOModule(Module *m, TargetMachine *t)
  75   : _module(m), _target(t), _symbolsParsed(false)
  76 {
  77 }
  78
  79 LTOModule *LTOModule::makeLTOModule(const char *path,
  80                                     std::string &errMsg) {
  81   OwningPtr<MemoryBuffer> buffer(MemoryBuffer::getFile(path, &errMsg));
  82   if (!buffer)
  83     return NULL;
  84   return makeLTOModule(buffer.get(), errMsg);
  85 }
  86
  87 /// makeBuffer - Create a MemoryBuffer from a memory range.  MemoryBuffer
  88 /// requires the byte past end of the buffer to be a zero.  We might get lucky
  89 /// and already be that way, otherwise make a copy.  Also if next byte is on a
  90 /// different page, don't assume it is readable.
  91 MemoryBuffer *LTOModule::makeBuffer(const void *mem, size_t length) {
  92   const char *startPtr = (char*)mem;
  93   const char *endPtr = startPtr+length;
  94   if (((uintptr_t)endPtr & (sys::Process::GetPageSize()-1)) == 0 ||
  95       *endPtr != 0)
  96     return MemoryBuffer::getMemBufferCopy(StringRef(startPtr, length));
  97
  98   return MemoryBuffer::getMemBuffer(StringRef(startPtr, length));
  99 }
 100
 101
 102 LTOModule *LTOModule::makeLTOModule(const void *mem, size_t length,
 103                                     std::string &errMsg) {
 104   OwningPtr<MemoryBuffer> buffer(makeBuffer(mem, length));
 105   if (!buffer)
 106     return NULL;
 107   return makeLTOModule(buffer.get(), errMsg);
 108 }
 109
 110 LTOModule *LTOModule::makeLTOModule(MemoryBuffer *buffer,
 111                                     std::string &errMsg) {
 112   InitializeAllTargets();
 113
 114   // parse bitcode buffer
 115   OwningPtr<Module> m(ParseBitcodeFile(buffer, getGlobalContext(), &errMsg));
 116   if (!m)
 117     return NULL;
 118
 119   std::string Triple = m->getTargetTriple();
 120   if (Triple.empty())
 121     Triple = sys::getHostTriple();
 122
 123   // find machine architecture for this module
 124   const Target *march = TargetRegistry::lookupTarget(Triple, errMsg);
 125   if (!march)
 126     return NULL;
 127
 128   // construct LTModule, hand over ownership of module and target
 129   SubtargetFeatures Features;
 130   Features.getDefaultSubtargetFeatures("" /* cpu */, llvm::Triple(Triple));
 131   std::string FeatureStr = Features.getString();
 132   TargetMachine *target = march->createTargetMachine(Triple, FeatureStr);
 133   return new LTOModule(m.take(), target);
 134 }
 135
 136
 137 const char *LTOModule::getTargetTriple() {
 138   return _module->getTargetTriple().c_str();
 139 }
 140
 141 void LTOModule::setTargetTriple(const char *triple) {
 142   _module->setTargetTriple(triple);
 143 }
 144
 145 void LTOModule::addDefinedFunctionSymbol(Function *f, Mangler &mangler) {
 146   // add to list of defined symbols
 147   addDefinedSymbol(f, mangler, true);
 148
 149   // add external symbols referenced by this function.
 150   for (Function::iterator b = f->begin(); b != f->end(); ++b) {
 151     for (BasicBlock::iterator i = b->begin(); i != b->end(); ++i) {
 152       for (unsigned count = 0, total = i->getNumOperands();
 153            count != total; ++count) {
 154         findExternalRefs(i->getOperand(count), mangler);
 155       }
 156     }
 157   }
 158 }
 159
 160 // Get string that data pointer points to.
 161 bool LTOModule::objcClassNameFromExpression(Constant *c, std::string &name) {
 162   if (ConstantExpr *ce = dyn_cast<ConstantExpr>(c)) {
 163     Constant *op = ce->getOperand(0);
 164     if (GlobalVariable *gvn = dyn_cast<GlobalVariable>(op)) {
 165       Constant *cn = gvn->getInitializer();
 166       if (ConstantArray *ca = dyn_cast<ConstantArray>(cn)) {
 167         if (ca->isCString()) {
 168           name = ".objc_class_name_" + ca->getAsString();
 169           return true;
 170         }
 171       }
 172     }
 173   }
 174   return false;
 175 }
 176
 177 // Parse i386/ppc ObjC class data structure.
 178 void LTOModule::addObjCClass(GlobalVariable *clgv) {
 179   if (ConstantStruct *c = dyn_cast<ConstantStruct>(clgv->getInitializer())) {
 180     // second slot in __OBJC,__class is pointer to superclass name
 181     std::string superclassName;
 182     if (objcClassNameFromExpression(c->getOperand(1), superclassName)) {
 183       NameAndAttributes info;
 184       if (_undefines.find(superclassName.c_str()) == _undefines.end()) {
 185         const char *symbolName = ::strdup(superclassName.c_str());
 186         info.name = symbolName;
 187         info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 188         // string is owned by _undefines
 189         _undefines[info.name] = info;
 190       }
 191     }
 192     // third slot in __OBJC,__class is pointer to class name
 193     std::string className;
 194     if (objcClassNameFromExpression(c->getOperand(2), className)) {
 195       const char *symbolName = ::strdup(className.c_str());
 196       NameAndAttributes info;
 197       info.name = symbolName;
 198       info.attributes = (lto_symbol_attributes)
 199         (LTO_SYMBOL_PERMISSIONS_DATA |
 200          LTO_SYMBOL_DEFINITION_REGULAR |
 201          LTO_SYMBOL_SCOPE_DEFAULT);
 202       _symbols.push_back(info);
 203       _defines[info.name] = 1;
 204     }
 205   }
 206 }
 207
 208
 209 // Parse i386/ppc ObjC category data structure.
 210 void LTOModule::addObjCCategory(GlobalVariable *clgv) {
 211   if (ConstantStruct *c = dyn_cast<ConstantStruct>(clgv->getInitializer())) {
 212     // second slot in __OBJC,__category is pointer to target class name
 213     std::string targetclassName;
 214     if (objcClassNameFromExpression(c->getOperand(1), targetclassName)) {
 215       NameAndAttributes info;
 216       if (_undefines.find(targetclassName.c_str()) == _undefines.end()) {
 217         const char *symbolName = ::strdup(targetclassName.c_str());
 218         info.name = symbolName;
 219         info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 220         // string is owned by _undefines
 221         _undefines[info.name] = info;
 222       }
 223     }
 224   }
 225 }
 226
 227
 228 // Parse i386/ppc ObjC class list data structure.
 229 void LTOModule::addObjCClassRef(GlobalVariable *clgv) {
 230   std::string targetclassName;
 231   if (objcClassNameFromExpression(clgv->getInitializer(), targetclassName)) {
 232     NameAndAttributes info;
 233     if (_undefines.find(targetclassName.c_str()) == _undefines.end()) {
 234       const char *symbolName = ::strdup(targetclassName.c_str());
 235       info.name = symbolName;
 236       info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 237       // string is owned by _undefines
 238       _undefines[info.name] = info;
 239     }
 240   }
 241 }
 242
 243
 244 void LTOModule::addDefinedDataSymbol(GlobalValue *v, Mangler &mangler) {
 245   // Add to list of defined symbols.
 246   addDefinedSymbol(v, mangler, false);
 247
 248   // Special case i386/ppc ObjC data structures in magic sections:
 249   // The issue is that the old ObjC object format did some strange
 250   // contortions to avoid real linker symbols.  For instance, the
 251   // ObjC class data structure is allocated statically in the executable
 252   // that defines that class.  That data structures contains a pointer to
 253   // its superclass.  But instead of just initializing that part of the
 254   // struct to the address of its superclass, and letting the static and
 255   // dynamic linkers do the rest, the runtime works by having that field
 256   // instead point to a C-string that is the name of the superclass.
 257   // At runtime the objc initialization updates that pointer and sets
 258   // it to point to the actual super class.  As far as the linker
 259   // knows it is just a pointer to a string.  But then someone wanted the
 260   // linker to issue errors at build time if the superclass was not found.
 261   // So they figured out a way in mach-o object format to use an absolute
 262   // symbols (.objc_class_name_Foo = 0) and a floating reference
 263   // (.reference .objc_class_name_Bar) to cause the linker into erroring when
 264   // a class was missing.
 265   // The following synthesizes the implicit .objc_* symbols for the linker
 266   // from the ObjC data structures generated by the front end.
 267   if (v->hasSection() /* && isTargetDarwin */) {
 268     // special case if this data blob is an ObjC class definition
 269     if (v->getSection().compare(0, 15, "__OBJC,__class,") == 0) {
 270       if (GlobalVariable *gv = dyn_cast<GlobalVariable>(v)) {
 271         addObjCClass(gv);
 272       }
 273     }
 274
 275     // special case if this data blob is an ObjC category definition
 276     else if (v->getSection().compare(0, 18, "__OBJC,__category,") == 0) {
 277       if (GlobalVariable *gv = dyn_cast<GlobalVariable>(v)) {
 278         addObjCCategory(gv);
 279       }
 280     }
 281
 282     // special case if this data blob is the list of referenced classes
 283     else if (v->getSection().compare(0, 18, "__OBJC,__cls_refs,") == 0) {
 284       if (GlobalVariable *gv = dyn_cast<GlobalVariable>(v)) {
 285         addObjCClassRef(gv);
 286       }
 287     }
 288   }
 289
 290   // add external symbols referenced by this data.
 291   for (unsigned count = 0, total = v->getNumOperands();
 292        count != total; ++count) {
 293     findExternalRefs(v->getOperand(count), mangler);
 294   }
 295 }
 296
 297
 298 void LTOModule::addDefinedSymbol(GlobalValue *def, Mangler &mangler,
 299                                  bool isFunction) {
 300   // ignore all llvm.* symbols
 301   if (def->getName().startswith("llvm."))
 302     return;
 303
 304   // string is owned by _defines
 305   const char *symbolName = ::strdup(mangler.getNameWithPrefix(def).c_str());
 306
 307   // set alignment part log2() can have rounding errors
 308   uint32_t align = def->getAlignment();
 309   uint32_t attr = align ? CountTrailingZeros_32(def->getAlignment()) : 0;
 310
 311   // set permissions part
 312   if (isFunction)
 313     attr |= LTO_SYMBOL_PERMISSIONS_CODE;
 314   else {
 315     GlobalVariable *gv = dyn_cast<GlobalVariable>(def);
 316     if (gv && gv->isConstant())
 317       attr |= LTO_SYMBOL_PERMISSIONS_RODATA;
 318     else
 319       attr |= LTO_SYMBOL_PERMISSIONS_DATA;
 320   }
 321
 322   // set definition part
 323   if (def->hasWeakLinkage() || def->hasLinkOnceLinkage() ||
 324       def->hasLinkerPrivateWeakLinkage() ||
 325       def->hasLinkerPrivateWeakDefAutoLinkage())
 326     attr |= LTO_SYMBOL_DEFINITION_WEAK;
 327   else if (def->hasCommonLinkage())
 328     attr |= LTO_SYMBOL_DEFINITION_TENTATIVE;
 329   else
 330     attr |= LTO_SYMBOL_DEFINITION_REGULAR;
 331
 332   // set scope part
 333   if (def->hasHiddenVisibility())
 334     attr |= LTO_SYMBOL_SCOPE_HIDDEN;
 335   else if (def->hasProtectedVisibility())
 336     attr |= LTO_SYMBOL_SCOPE_PROTECTED;
 337   else if (def->hasExternalLinkage() || def->hasWeakLinkage() ||
 338            def->hasLinkOnceLinkage() || def->hasCommonLinkage() ||
 339            def->hasLinkerPrivateWeakLinkage())
 340     attr |= LTO_SYMBOL_SCOPE_DEFAULT;
 341   else if (def->hasLinkerPrivateWeakDefAutoLinkage())
 342     attr |= LTO_SYMBOL_SCOPE_DEFAULT_CAN_BE_HIDDEN;
 343   else
 344     attr |= LTO_SYMBOL_SCOPE_INTERNAL;
 345
 346   // add to table of symbols
 347   NameAndAttributes info;
 348   info.name = symbolName;
 349   info.attributes = (lto_symbol_attributes)attr;
 350   _symbols.push_back(info);
 351   _defines[info.name] = 1;
 352 }
 353
 354 void LTOModule::addAsmGlobalSymbol(const char *name) {
 355   // only add new define if not already defined
 356   if (_defines.count(name))
 357     return;
 358
 359   // string is owned by _defines
 360   const char *symbolName = ::strdup(name);
 361   uint32_t attr = LTO_SYMBOL_DEFINITION_REGULAR;
 362   attr |= LTO_SYMBOL_SCOPE_DEFAULT;
 363   NameAndAttributes info;
 364   info.name = symbolName;
 365   info.attributes = (lto_symbol_attributes)attr;
 366   _symbols.push_back(info);
 367   _defines[info.name] = 1;
 368 }
 369
 370 void LTOModule::addPotentialUndefinedSymbol(GlobalValue *decl,
 371                                             Mangler &mangler) {
 372   // ignore all llvm.* symbols
 373   if (decl->getName().startswith("llvm."))
 374     return;
 375
 376   // ignore all aliases
 377   if (isa<GlobalAlias>(decl))
 378     return;
 379
 380   std::string name = mangler.getNameWithPrefix(decl);
 381
 382   // we already have the symbol
 383   if (_undefines.find(name) != _undefines.end())
 384     return;
 385
 386   NameAndAttributes info;
 387   // string is owned by _undefines
 388   info.name = ::strdup(name.c_str());
 389   if (decl->hasExternalWeakLinkage())
 390     info.attributes = LTO_SYMBOL_DEFINITION_WEAKUNDEF;
 391   else
 392     info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 393   _undefines[name] = info;
 394 }
 395
 396
 397
 398 // Find external symbols referenced by VALUE. This is a recursive function.
 399 void LTOModule::findExternalRefs(Value *value, Mangler &mangler) {
 400   if (GlobalValue *gv = dyn_cast<GlobalValue>(value)) {
 401     if (!gv->hasExternalLinkage())
 402       addPotentialUndefinedSymbol(gv, mangler);
 403     // If this is a variable definition, do not recursively process
 404     // initializer.  It might contain a reference to this variable
 405     // and cause an infinite loop.  The initializer will be
 406     // processed in addDefinedDataSymbol().
 407     return;
 408   }
 409
 410   // GlobalValue, even with InternalLinkage type, may have operands with
 411   // ExternalLinkage type. Do not ignore these operands.
 412   if (Constant *c = dyn_cast<Constant>(value)) {
 413     // Handle ConstantExpr, ConstantStruct, ConstantArry etc.
 414     for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i)
 415       findExternalRefs(c->getOperand(i), mangler);
 416   }
 417 }
 418
 419 void LTOModule::lazyParseSymbols() {
 420   if (_symbolsParsed)
 421     return;
 422
 423   _symbolsParsed = true;
 424
 425   // Use mangler to add GlobalPrefix to names to match linker names.
 426   MCContext Context(*_target->getMCAsmInfo());
 427   Mangler mangler(Context, *_target->getTargetData());
 428
 429   // add functions
 430   for (Module::iterator f = _module->begin(); f != _module->end(); ++f) {
 431     if (f->isDeclaration())
 432       addPotentialUndefinedSymbol(f, mangler);
 433     else
 434       addDefinedFunctionSymbol(f, mangler);
 435   }
 436
 437   // add data
 438   for (Module::global_iterator v = _module->global_begin(),
 439          e = _module->global_end(); v !=  e; ++v) {
 440     if (v->isDeclaration())
 441       addPotentialUndefinedSymbol(v, mangler);
 442     else
 443       addDefinedDataSymbol(v, mangler);
 444   }
 445
 446   // add asm globals
 447   const std::string &inlineAsm = _module->getModuleInlineAsm();
 448   const std::string glbl = ".globl";
 449   std::string asmSymbolName;
 450   std::string::size_type pos = inlineAsm.find(glbl, 0);
 451   while (pos != std::string::npos) {
 452     // eat .globl
 453     pos = pos + 6;
 454
 455     // skip white space between .globl and symbol name
 456     std::string::size_type pbegin = inlineAsm.find_first_not_of(' ', pos);
 457     if (pbegin == std::string::npos)
 458       break;
 459
 460     // find end-of-line
 461     std::string::size_type pend = inlineAsm.find_first_of('\n', pbegin);
 462     if (pend == std::string::npos)
 463       break;
 464
 465     asmSymbolName.assign(inlineAsm, pbegin, pend - pbegin);
 466     addAsmGlobalSymbol(asmSymbolName.c_str());
 467
 468     // search next .globl
 469     pos = inlineAsm.find(glbl, pend);
 470   }
 471
 472   // make symbols for all undefines
 473   for (StringMap<NameAndAttributes>::iterator it=_undefines.begin();
 474        it != _undefines.end(); ++it) {
 475     // if this symbol also has a definition, then don't make an undefine
 476     // because it is a tentative definition
 477     if (_defines.count(it->getKey()) == 0) {
 478       NameAndAttributes info = it->getValue();
 479       _symbols.push_back(info);
 480     }
 481   }
 482 }
 483
 484
 485 uint32_t LTOModule::getSymbolCount() {
 486   lazyParseSymbols();
 487   return _symbols.size();
 488 }
 489
 490
 491 lto_symbol_attributes LTOModule::getSymbolAttributes(uint32_t index) {
 492   lazyParseSymbols();
 493   if (index < _symbols.size())
 494     return _symbols[index].attributes;
 495   else
 496     return lto_symbol_attributes(0);
 497 }
 498
 499 const char *LTOModule::getSymbolName(uint32_t index) {
 500   lazyParseSymbols();
 501   if (index < _symbols.size())
 502     return _symbols[index].name;
 503   else
 504     return NULL;
 505 }