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/ModuleProvider.h"
  21 #include "llvm/ADT/OwningPtr.h"
  22 #include "llvm/ADT/Triple.h"
  23 #include "llvm/Bitcode/ReaderWriter.h"
  24 #include "llvm/Support/SystemUtils.h"
  25 #include "llvm/Support/MemoryBuffer.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/System/Host.h"
  28 #include "llvm/System/Path.h"
  29 #include "llvm/System/Process.h"
  30 #include "llvm/Target/Mangler.h"
  31 #include "llvm/Target/SubtargetFeature.h"
  32 #include "llvm/MC/MCAsmInfo.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<ModuleProvider> mp(getBitcodeModuleProvider(buffer,
  73                                                           getGlobalContext()));
  74     // on success, mp owns buffer and both are deleted at end of this method
  75     if (!mp) {
  76         delete buffer;
  77         return false;
  78     }
  79     std::string actualTarget = mp->getModule()->getTargetTriple();
  80     return (strncmp(actualTarget.c_str(), triplePrefix,
  81                     strlen(triplePrefix)) == 0);
  82 }
  83
  84
  85 LTOModule::LTOModule(Module* m, TargetMachine* t)
  86  : _module(m), _target(t), _symbolsParsed(false)
  87 {
  88 }
  89
  90 LTOModule* LTOModule::makeLTOModule(const char* path,
  91                                     std::string& errMsg)
  92 {
  93     OwningPtr<MemoryBuffer> buffer(MemoryBuffer::getFile(path, &errMsg));
  94     if (!buffer)
  95         return NULL;
  96     return makeLTOModule(buffer.get(), errMsg);
  97 }
  98
  99 /// makeBuffer - create a MemoryBuffer from a memory range.
 100 /// MemoryBuffer requires the byte past end of the buffer to be a zero.
 101 /// We might get lucky and already be that way, otherwise make a copy.
 102 /// Also if next byte is on a different page, don't assume it is readable.
 103 MemoryBuffer* LTOModule::makeBuffer(const void* mem, size_t length)
 104 {
 105     const char* startPtr = (char*)mem;
 106     const char* endPtr = startPtr+length;
 107     if ((((uintptr_t)endPtr & (sys::Process::GetPageSize()-1)) == 0)
 108         || (*endPtr != 0))
 109         return MemoryBuffer::getMemBufferCopy(startPtr, endPtr);
 110     else
 111         return MemoryBuffer::getMemBuffer(startPtr, endPtr);
 112 }
 113
 114
 115 LTOModule* LTOModule::makeLTOModule(const void* mem, size_t length,
 116                                     std::string& errMsg)
 117 {
 118     OwningPtr<MemoryBuffer> buffer(makeBuffer(mem, length));
 119     if (!buffer)
 120         return NULL;
 121     return makeLTOModule(buffer.get(), errMsg);
 122 }
 123
 124 LTOModule* LTOModule::makeLTOModule(MemoryBuffer* buffer,
 125                                     std::string& errMsg)
 126 {
 127     InitializeAllTargets();
 128
 129     // parse bitcode buffer
 130     OwningPtr<Module> m(ParseBitcodeFile(buffer, getGlobalContext(), &errMsg));
 131     if (!m)
 132         return NULL;
 133
 134     std::string Triple = m->getTargetTriple();
 135     if (Triple.empty())
 136       Triple = sys::getHostTriple();
 137
 138     // find machine architecture for this module
 139     const Target* march = TargetRegistry::lookupTarget(Triple, errMsg);
 140     if (!march)
 141         return NULL;
 142
 143     // construct LTModule, hand over ownership of module and target
 144     const std::string FeatureStr =
 145         SubtargetFeatures::getDefaultSubtargetFeatures(llvm::Triple(Triple));
 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         Mangler mangler(*_target->getMCAsmInfo());
 443
 444         // add functions
 445         for (Module::iterator f = _module->begin(); f != _module->end(); ++f) {
 446             if (f->isDeclaration())
 447                 addPotentialUndefinedSymbol(f, mangler);
 448             else
 449                 addDefinedFunctionSymbol(f, mangler);
 450         }
 451
 452         // add data
 453         for (Module::global_iterator v = _module->global_begin(),
 454                                     e = _module->global_end(); v !=  e; ++v) {
 455             if (v->isDeclaration())
 456                 addPotentialUndefinedSymbol(v, mangler);
 457             else
 458                 addDefinedDataSymbol(v, mangler);
 459         }
 460
 461         // add asm globals
 462         const std::string &inlineAsm = _module->getModuleInlineAsm();
 463         const std::string glbl = ".globl";
 464         std::string asmSymbolName;
 465         std::string::size_type pos = inlineAsm.find(glbl, 0);
 466         while (pos != std::string::npos) {
 467           // eat .globl
 468           pos = pos + 6;
 469
 470           // skip white space between .globl and symbol name
 471           std::string::size_type pbegin = inlineAsm.find_first_not_of(' ', pos);
 472           if (pbegin == std::string::npos)
 473             break;
 474
 475           // find end-of-line
 476           std::string::size_type pend = inlineAsm.find_first_of('\n', pbegin);
 477           if (pend == std::string::npos)
 478             break;
 479
 480           asmSymbolName.assign(inlineAsm, pbegin, pend - pbegin);
 481           addAsmGlobalSymbol(asmSymbolName.c_str());
 482
 483           // search next .globl
 484           pos = inlineAsm.find(glbl, pend);
 485         }
 486
 487         // make symbols for all undefines
 488         for (StringMap<NameAndAttributes>::iterator it=_undefines.begin();
 489                                                 it != _undefines.end(); ++it) {
 490             // if this symbol also has a definition, then don't make an undefine
 491             // because it is a tentative definition
 492             if (_defines.count(it->getKey()) == 0) {
 493               NameAndAttributes info = it->getValue();
 494               _symbols.push_back(info);
 495             }
 496         }
 497     }
 498 }
 499
 500
 501 uint32_t LTOModule::getSymbolCount()
 502 {
 503     lazyParseSymbols();
 504     return _symbols.size();
 505 }
 506
 507
 508 lto_symbol_attributes LTOModule::getSymbolAttributes(uint32_t index)
 509 {
 510     lazyParseSymbols();
 511     if (index < _symbols.size())
 512         return _symbols[index].attributes;
 513     else
 514         return lto_symbol_attributes(0);
 515 }
 516
 517 const char* LTOModule::getSymbolName(uint32_t index)
 518 {
 519     lazyParseSymbols();
 520     if (index < _symbols.size())
 521         return _symbols[index].name;
 522     else
 523         return NULL;
 524 }