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::setTargetTriple(const char *triple)
 157 {
 158     _module->setTargetTriple(triple);
 159 }
 160
 161 void LTOModule::addDefinedFunctionSymbol(Function* f, Mangler &mangler)
 162 {
 163     // add to list of defined symbols
 164     addDefinedSymbol(f, mangler, true);
 165
 166     // add external symbols referenced by this function.
 167     for (Function::iterator b = f->begin(); b != f->end(); ++b) {
 168         for (BasicBlock::iterator i = b->begin(); i != b->end(); ++i) {
 169             for (unsigned count = 0, total = i->getNumOperands();
 170                                         count != total; ++count) {
 171                 findExternalRefs(i->getOperand(count), mangler);
 172             }
 173         }
 174     }
 175 }
 176
 177 // get string that data pointer points to
 178 bool LTOModule::objcClassNameFromExpression(Constant* c, std::string& name)
 179 {
 180     if (ConstantExpr* ce = dyn_cast<ConstantExpr>(c)) {
 181         Constant* op = ce->getOperand(0);
 182         if (GlobalVariable* gvn = dyn_cast<GlobalVariable>(op)) {
 183             Constant* cn = gvn->getInitializer();
 184             if (ConstantArray* ca = dyn_cast<ConstantArray>(cn)) {
 185                 if (ca->isCString()) {
 186                     name = ".objc_class_name_" + ca->getAsString();
 187                     return true;
 188                 }
 189             }
 190         }
 191     }
 192     return false;
 193 }
 194
 195 // parse i386/ppc ObjC class data structure
 196 void LTOModule::addObjCClass(GlobalVariable* clgv)
 197 {
 198     if (ConstantStruct* c = dyn_cast<ConstantStruct>(clgv->getInitializer())) {
 199         // second slot in __OBJC,__class is pointer to superclass name
 200         std::string superclassName;
 201         if (objcClassNameFromExpression(c->getOperand(1), superclassName)) {
 202             NameAndAttributes info;
 203             if (_undefines.find(superclassName.c_str()) == _undefines.end()) {
 204                 const char* symbolName = ::strdup(superclassName.c_str());
 205                 info.name = ::strdup(symbolName);
 206                 info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 207                 // string is owned by _undefines
 208                 _undefines[info.name] = info;
 209             }
 210         }
 211         // third slot in __OBJC,__class is pointer to class name
 212         std::string className;
 213          if (objcClassNameFromExpression(c->getOperand(2), className)) {
 214             const char* symbolName = ::strdup(className.c_str());
 215             NameAndAttributes info;
 216             info.name = symbolName;
 217             info.attributes = (lto_symbol_attributes)
 218                 (LTO_SYMBOL_PERMISSIONS_DATA |
 219                  LTO_SYMBOL_DEFINITION_REGULAR |
 220                  LTO_SYMBOL_SCOPE_DEFAULT);
 221             _symbols.push_back(info);
 222             _defines[info.name] = 1;
 223          }
 224     }
 225 }
 226
 227
 228 // parse i386/ppc ObjC category data structure
 229 void LTOModule::addObjCCategory(GlobalVariable* clgv)
 230 {
 231     if (ConstantStruct* c = dyn_cast<ConstantStruct>(clgv->getInitializer())) {
 232         // second slot in __OBJC,__category is pointer to target class name
 233         std::string targetclassName;
 234         if (objcClassNameFromExpression(c->getOperand(1), targetclassName)) {
 235             NameAndAttributes info;
 236             if (_undefines.find(targetclassName.c_str()) == _undefines.end()) {
 237                 const char* symbolName = ::strdup(targetclassName.c_str());
 238                 info.name = ::strdup(symbolName);
 239                 info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 240                 // string is owned by _undefines
 241                _undefines[info.name] = info;
 242             }
 243         }
 244     }
 245 }
 246
 247
 248 // parse i386/ppc ObjC class list data structure
 249 void LTOModule::addObjCClassRef(GlobalVariable* clgv)
 250 {
 251     std::string targetclassName;
 252     if (objcClassNameFromExpression(clgv->getInitializer(), targetclassName)) {
 253         NameAndAttributes info;
 254         if (_undefines.find(targetclassName.c_str()) == _undefines.end()) {
 255             const char* symbolName = ::strdup(targetclassName.c_str());
 256             info.name = ::strdup(symbolName);
 257             info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 258             // string is owned by _undefines
 259             _undefines[info.name] = info;
 260         }
 261     }
 262 }
 263
 264
 265 void LTOModule::addDefinedDataSymbol(GlobalValue* v, Mangler& mangler)
 266 {
 267     // add to list of defined symbols
 268     addDefinedSymbol(v, mangler, false);
 269
 270     // Special case i386/ppc ObjC data structures in magic sections:
 271     // The issue is that the old ObjC object format did some strange
 272     // contortions to avoid real linker symbols.  For instance, the
 273     // ObjC class data structure is allocated statically in the executable
 274     // that defines that class.  That data structures contains a pointer to
 275     // its superclass.  But instead of just initializing that part of the
 276     // struct to the address of its superclass, and letting the static and
 277     // dynamic linkers do the rest, the runtime works by having that field
 278     // instead point to a C-string that is the name of the superclass.
 279     // At runtime the objc initialization updates that pointer and sets
 280     // it to point to the actual super class.  As far as the linker
 281     // knows it is just a pointer to a string.  But then someone wanted the
 282     // linker to issue errors at build time if the superclass was not found.
 283     // So they figured out a way in mach-o object format to use an absolute
 284     // symbols (.objc_class_name_Foo = 0) and a floating reference
 285     // (.reference .objc_class_name_Bar) to cause the linker into erroring when
 286     // a class was missing.
 287     // The following synthesizes the implicit .objc_* symbols for the linker
 288     // from the ObjC data structures generated by the front end.
 289     if (v->hasSection() /* && isTargetDarwin */) {
 290         // special case if this data blob is an ObjC class definition
 291         if (v->getSection().compare(0, 15, "__OBJC,__class,") == 0) {
 292             if (GlobalVariable* gv = dyn_cast<GlobalVariable>(v)) {
 293                 addObjCClass(gv);
 294             }
 295         }
 296
 297         // special case if this data blob is an ObjC category definition
 298         else if (v->getSection().compare(0, 18, "__OBJC,__category,") == 0) {
 299             if (GlobalVariable* gv = dyn_cast<GlobalVariable>(v)) {
 300                 addObjCCategory(gv);
 301             }
 302         }
 303
 304         // special case if this data blob is the list of referenced classes
 305         else if (v->getSection().compare(0, 18, "__OBJC,__cls_refs,") == 0) {
 306             if (GlobalVariable* gv = dyn_cast<GlobalVariable>(v)) {
 307                 addObjCClassRef(gv);
 308             }
 309         }
 310     }
 311
 312     // add external symbols referenced by this data.
 313     for (unsigned count = 0, total = v->getNumOperands();
 314                                                 count != total; ++count) {
 315         findExternalRefs(v->getOperand(count), mangler);
 316     }
 317 }
 318
 319
 320 void LTOModule::addDefinedSymbol(GlobalValue* def, Mangler &mangler,
 321                                  bool isFunction)
 322 {
 323     // ignore all llvm.* symbols
 324     if (def->getName().startswith("llvm."))
 325         return;
 326
 327     // string is owned by _defines
 328     const char* symbolName = ::strdup(mangler.getNameWithPrefix(def).c_str());
 329
 330     // set alignment part log2() can have rounding errors
 331     uint32_t align = def->getAlignment();
 332     uint32_t attr = align ? CountTrailingZeros_32(def->getAlignment()) : 0;
 333
 334     // set permissions part
 335     if (isFunction)
 336         attr |= LTO_SYMBOL_PERMISSIONS_CODE;
 337     else {
 338         GlobalVariable* gv = dyn_cast<GlobalVariable>(def);
 339         if (gv && gv->isConstant())
 340             attr |= LTO_SYMBOL_PERMISSIONS_RODATA;
 341         else
 342             attr |= LTO_SYMBOL_PERMISSIONS_DATA;
 343     }
 344
 345     // set definition part
 346     if (def->hasWeakLinkage() || def->hasLinkOnceLinkage()) {
 347         attr |= LTO_SYMBOL_DEFINITION_WEAK;
 348     }
 349     else if (def->hasCommonLinkage()) {
 350         attr |= LTO_SYMBOL_DEFINITION_TENTATIVE;
 351     }
 352     else {
 353         attr |= LTO_SYMBOL_DEFINITION_REGULAR;
 354     }
 355
 356     // set scope part
 357     if (def->hasHiddenVisibility())
 358         attr |= LTO_SYMBOL_SCOPE_HIDDEN;
 359     else if (def->hasProtectedVisibility())
 360         attr |= LTO_SYMBOL_SCOPE_PROTECTED;
 361     else if (def->hasExternalLinkage() || def->hasWeakLinkage()
 362              || def->hasLinkOnceLinkage() || def->hasCommonLinkage())
 363         attr |= LTO_SYMBOL_SCOPE_DEFAULT;
 364     else
 365         attr |= LTO_SYMBOL_SCOPE_INTERNAL;
 366
 367     // add to table of symbols
 368     NameAndAttributes info;
 369     info.name = symbolName;
 370     info.attributes = (lto_symbol_attributes)attr;
 371     _symbols.push_back(info);
 372     _defines[info.name] = 1;
 373 }
 374
 375 void LTOModule::addAsmGlobalSymbol(const char *name) {
 376     // only add new define if not already defined
 377     if (_defines.count(name) == 0)
 378         return;
 379
 380     // string is owned by _defines
 381     const char *symbolName = ::strdup(name);
 382     uint32_t attr = LTO_SYMBOL_DEFINITION_REGULAR;
 383     attr |= LTO_SYMBOL_SCOPE_DEFAULT;
 384     NameAndAttributes info;
 385     info.name = symbolName;
 386     info.attributes = (lto_symbol_attributes)attr;
 387     _symbols.push_back(info);
 388     _defines[info.name] = 1;
 389 }
 390
 391 void LTOModule::addPotentialUndefinedSymbol(GlobalValue* decl, Mangler &mangler)
 392 {
 393     // ignore all llvm.* symbols
 394     if (decl->getName().startswith("llvm."))
 395         return;
 396
 397     // ignore all aliases
 398     if (isa<GlobalAlias>(decl))
 399         return;
 400
 401     std::string name = mangler.getNameWithPrefix(decl);
 402
 403     // we already have the symbol
 404     if (_undefines.find(name) != _undefines.end())
 405       return;
 406
 407     NameAndAttributes info;
 408     // string is owned by _undefines
 409     info.name = ::strdup(name.c_str());
 410     if (decl->hasExternalWeakLinkage())
 411       info.attributes = LTO_SYMBOL_DEFINITION_WEAKUNDEF;
 412     else
 413       info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 414     _undefines[name] = info;
 415 }
 416
 417
 418
 419 // Find external symbols referenced by VALUE. This is a recursive function.
 420 void LTOModule::findExternalRefs(Value* value, Mangler &mangler) {
 421
 422     if (GlobalValue* gv = dyn_cast<GlobalValue>(value)) {
 423         if (!gv->hasExternalLinkage())
 424             addPotentialUndefinedSymbol(gv, mangler);
 425         // If this is a variable definition, do not recursively process
 426         // initializer.  It might contain a reference to this variable
 427         // and cause an infinite loop.  The initializer will be
 428         // processed in addDefinedDataSymbol().
 429         return;
 430     }
 431
 432     // GlobalValue, even with InternalLinkage type, may have operands with
 433     // ExternalLinkage type. Do not ignore these operands.
 434     if (Constant* c = dyn_cast<Constant>(value)) {
 435         // Handle ConstantExpr, ConstantStruct, ConstantArry etc.
 436         for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i)
 437             findExternalRefs(c->getOperand(i), mangler);
 438     }
 439 }
 440
 441 void LTOModule::lazyParseSymbols()
 442 {
 443     if (!_symbolsParsed) {
 444         _symbolsParsed = true;
 445
 446         // Use mangler to add GlobalPrefix to names to match linker names.
 447         MCContext Context(*_target->getMCAsmInfo());
 448         Mangler mangler(Context, *_target->getTargetData());
 449
 450         // add functions
 451         for (Module::iterator f = _module->begin(); f != _module->end(); ++f) {
 452             if (f->isDeclaration())
 453                 addPotentialUndefinedSymbol(f, mangler);
 454             else
 455                 addDefinedFunctionSymbol(f, mangler);
 456         }
 457
 458         // add data
 459         for (Module::global_iterator v = _module->global_begin(),
 460                                     e = _module->global_end(); v !=  e; ++v) {
 461             if (v->isDeclaration())
 462                 addPotentialUndefinedSymbol(v, mangler);
 463             else
 464                 addDefinedDataSymbol(v, mangler);
 465         }
 466
 467         // add asm globals
 468         const std::string &inlineAsm = _module->getModuleInlineAsm();
 469         const std::string glbl = ".globl";
 470         std::string asmSymbolName;
 471         std::string::size_type pos = inlineAsm.find(glbl, 0);
 472         while (pos != std::string::npos) {
 473           // eat .globl
 474           pos = pos + 6;
 475
 476           // skip white space between .globl and symbol name
 477           std::string::size_type pbegin = inlineAsm.find_first_not_of(' ', pos);
 478           if (pbegin == std::string::npos)
 479             break;
 480
 481           // find end-of-line
 482           std::string::size_type pend = inlineAsm.find_first_of('\n', pbegin);
 483           if (pend == std::string::npos)
 484             break;
 485
 486           asmSymbolName.assign(inlineAsm, pbegin, pend - pbegin);
 487           addAsmGlobalSymbol(asmSymbolName.c_str());
 488
 489           // search next .globl
 490           pos = inlineAsm.find(glbl, pend);
 491         }
 492
 493         // make symbols for all undefines
 494         for (StringMap<NameAndAttributes>::iterator it=_undefines.begin();
 495                                                 it != _undefines.end(); ++it) {
 496             // if this symbol also has a definition, then don't make an undefine
 497             // because it is a tentative definition
 498             if (_defines.count(it->getKey()) == 0) {
 499               NameAndAttributes info = it->getValue();
 500               _symbols.push_back(info);
 501             }
 502         }
 503     }
 504 }
 505
 506
 507 uint32_t LTOModule::getSymbolCount()
 508 {
 509     lazyParseSymbols();
 510     return _symbols.size();
 511 }
 512
 513
 514 lto_symbol_attributes LTOModule::getSymbolAttributes(uint32_t index)
 515 {
 516     lazyParseSymbols();
 517     if (index < _symbols.size())
 518         return _symbols[index].attributes;
 519     else
 520         return lto_symbol_attributes(0);
 521 }
 522
 523 const char* LTOModule::getSymbolName(uint32_t index)
 524 {
 525     lazyParseSymbols();
 526     if (index < _symbols.size())
 527         return _symbols[index].name;
 528     else
 529         return NULL;
 530 }