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