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(startPtr, endPtr);
 109     else
 110         return MemoryBuffer::getMemBuffer(startPtr, endPtr);
 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     const std::string FeatureStr =
 144         SubtargetFeatures::getDefaultSubtargetFeatures(llvm::Triple(Triple));
 145     TargetMachine* target = march->createTargetMachine(Triple, FeatureStr);
 146     return new LTOModule(m.take(), target);
 147 }
 148
 149
 150 const char* LTOModule::getTargetTriple()
 151 {
 152     return _module->getTargetTriple().c_str();
 153 }
 154
 155 void LTOModule::addDefinedFunctionSymbol(Function* f, Mangler &mangler)
 156 {
 157     // add to list of defined symbols
 158     addDefinedSymbol(f, mangler, true);
 159
 160     // add external symbols referenced by this function.
 161     for (Function::iterator b = f->begin(); b != f->end(); ++b) {
 162         for (BasicBlock::iterator i = b->begin(); i != b->end(); ++i) {
 163             for (unsigned count = 0, total = i->getNumOperands();
 164                                         count != total; ++count) {
 165                 findExternalRefs(i->getOperand(count), mangler);
 166             }
 167         }
 168     }
 169 }
 170
 171 // get string that data pointer points to
 172 bool LTOModule::objcClassNameFromExpression(Constant* c, std::string& name)
 173 {
 174     if (ConstantExpr* ce = dyn_cast<ConstantExpr>(c)) {
 175         Constant* op = ce->getOperand(0);
 176         if (GlobalVariable* gvn = dyn_cast<GlobalVariable>(op)) {
 177             Constant* cn = gvn->getInitializer();
 178             if (ConstantArray* ca = dyn_cast<ConstantArray>(cn)) {
 179                 if (ca->isCString()) {
 180                     name = ".objc_class_name_" + ca->getAsString();
 181                     return true;
 182                 }
 183             }
 184         }
 185     }
 186     return false;
 187 }
 188
 189 // parse i386/ppc ObjC class data structure
 190 void LTOModule::addObjCClass(GlobalVariable* clgv)
 191 {
 192     if (ConstantStruct* c = dyn_cast<ConstantStruct>(clgv->getInitializer())) {
 193         // second slot in __OBJC,__class is pointer to superclass name
 194         std::string superclassName;
 195         if (objcClassNameFromExpression(c->getOperand(1), superclassName)) {
 196             NameAndAttributes info;
 197             if (_undefines.find(superclassName.c_str()) == _undefines.end()) {
 198                 const char* symbolName = ::strdup(superclassName.c_str());
 199                 info.name = ::strdup(symbolName);
 200                 info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 201                 // string is owned by _undefines
 202                 _undefines[info.name] = info;
 203             }
 204         }
 205         // third slot in __OBJC,__class is pointer to class name
 206         std::string className;
 207          if (objcClassNameFromExpression(c->getOperand(2), className)) {
 208             const char* symbolName = ::strdup(className.c_str());
 209             NameAndAttributes info;
 210             info.name = symbolName;
 211             info.attributes = (lto_symbol_attributes)
 212                 (LTO_SYMBOL_PERMISSIONS_DATA |
 213                  LTO_SYMBOL_DEFINITION_REGULAR |
 214                  LTO_SYMBOL_SCOPE_DEFAULT);
 215             _symbols.push_back(info);
 216             _defines[info.name] = 1;
 217          }
 218     }
 219 }
 220
 221
 222 // parse i386/ppc ObjC category data structure
 223 void LTOModule::addObjCCategory(GlobalVariable* clgv)
 224 {
 225     if (ConstantStruct* c = dyn_cast<ConstantStruct>(clgv->getInitializer())) {
 226         // second slot in __OBJC,__category is pointer to target class name
 227         std::string targetclassName;
 228         if (objcClassNameFromExpression(c->getOperand(1), targetclassName)) {
 229             NameAndAttributes info;
 230             if (_undefines.find(targetclassName.c_str()) == _undefines.end()) {
 231                 const char* symbolName = ::strdup(targetclassName.c_str());
 232                 info.name = ::strdup(symbolName);
 233                 info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 234                 // string is owned by _undefines
 235                _undefines[info.name] = info;
 236             }
 237         }
 238     }
 239 }
 240
 241
 242 // parse i386/ppc ObjC class list data structure
 243 void LTOModule::addObjCClassRef(GlobalVariable* clgv)
 244 {
 245     std::string targetclassName;
 246     if (objcClassNameFromExpression(clgv->getInitializer(), targetclassName)) {
 247         NameAndAttributes info;
 248         if (_undefines.find(targetclassName.c_str()) == _undefines.end()) {
 249             const char* symbolName = ::strdup(targetclassName.c_str());
 250             info.name = ::strdup(symbolName);
 251             info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 252             // string is owned by _undefines
 253             _undefines[info.name] = info;
 254         }
 255     }
 256 }
 257
 258
 259 void LTOModule::addDefinedDataSymbol(GlobalValue* v, Mangler& mangler)
 260 {
 261     // add to list of defined symbols
 262     addDefinedSymbol(v, mangler, false);
 263
 264     // Special case i386/ppc ObjC data structures in magic sections:
 265     // The issue is that the old ObjC object format did some strange
 266     // contortions to avoid real linker symbols.  For instance, the
 267     // ObjC class data structure is allocated statically in the executable
 268     // that defines that class.  That data structures contains a pointer to
 269     // its superclass.  But instead of just initializing that part of the
 270     // struct to the address of its superclass, and letting the static and
 271     // dynamic linkers do the rest, the runtime works by having that field
 272     // instead point to a C-string that is the name of the superclass.
 273     // At runtime the objc initialization updates that pointer and sets
 274     // it to point to the actual super class.  As far as the linker
 275     // knows it is just a pointer to a string.  But then someone wanted the
 276     // linker to issue errors at build time if the superclass was not found.
 277     // So they figured out a way in mach-o object format to use an absolute
 278     // symbols (.objc_class_name_Foo = 0) and a floating reference
 279     // (.reference .objc_class_name_Bar) to cause the linker into erroring when
 280     // a class was missing.
 281     // The following synthesizes the implicit .objc_* symbols for the linker
 282     // from the ObjC data structures generated by the front end.
 283     if (v->hasSection() /* && isTargetDarwin */) {
 284         // special case if this data blob is an ObjC class definition
 285         if (v->getSection().compare(0, 15, "__OBJC,__class,") == 0) {
 286             if (GlobalVariable* gv = dyn_cast<GlobalVariable>(v)) {
 287                 addObjCClass(gv);
 288             }
 289         }
 290
 291         // special case if this data blob is an ObjC category definition
 292         else if (v->getSection().compare(0, 18, "__OBJC,__category,") == 0) {
 293             if (GlobalVariable* gv = dyn_cast<GlobalVariable>(v)) {
 294                 addObjCCategory(gv);
 295             }
 296         }
 297
 298         // special case if this data blob is the list of referenced classes
 299         else if (v->getSection().compare(0, 18, "__OBJC,__cls_refs,") == 0) {
 300             if (GlobalVariable* gv = dyn_cast<GlobalVariable>(v)) {
 301                 addObjCClassRef(gv);
 302             }
 303         }
 304     }
 305
 306     // add external symbols referenced by this data.
 307     for (unsigned count = 0, total = v->getNumOperands();
 308                                                 count != total; ++count) {
 309         findExternalRefs(v->getOperand(count), mangler);
 310     }
 311 }
 312
 313
 314 void LTOModule::addDefinedSymbol(GlobalValue* def, Mangler &mangler,
 315                                  bool isFunction)
 316 {
 317     // ignore all llvm.* symbols
 318     if (def->getName().startswith("llvm."))
 319         return;
 320
 321     // string is owned by _defines
 322     const char* symbolName = ::strdup(mangler.getNameWithPrefix(def).c_str());
 323
 324     // set alignment part log2() can have rounding errors
 325     uint32_t align = def->getAlignment();
 326     uint32_t attr = align ? CountTrailingZeros_32(def->getAlignment()) : 0;
 327
 328     // set permissions part
 329     if (isFunction)
 330         attr |= LTO_SYMBOL_PERMISSIONS_CODE;
 331     else {
 332         GlobalVariable* gv = dyn_cast<GlobalVariable>(def);
 333         if (gv && gv->isConstant())
 334             attr |= LTO_SYMBOL_PERMISSIONS_RODATA;
 335         else
 336             attr |= LTO_SYMBOL_PERMISSIONS_DATA;
 337     }
 338
 339     // set definition part
 340     if (def->hasWeakLinkage() || def->hasLinkOnceLinkage()) {
 341         attr |= LTO_SYMBOL_DEFINITION_WEAK;
 342     }
 343     else if (def->hasCommonLinkage()) {
 344         attr |= LTO_SYMBOL_DEFINITION_TENTATIVE;
 345     }
 346     else {
 347         attr |= LTO_SYMBOL_DEFINITION_REGULAR;
 348     }
 349
 350     // set scope part
 351     if (def->hasHiddenVisibility())
 352         attr |= LTO_SYMBOL_SCOPE_HIDDEN;
 353     else if (def->hasProtectedVisibility())
 354         attr |= LTO_SYMBOL_SCOPE_PROTECTED;
 355     else if (def->hasExternalLinkage() || def->hasWeakLinkage()
 356              || def->hasLinkOnceLinkage() || def->hasCommonLinkage())
 357         attr |= LTO_SYMBOL_SCOPE_DEFAULT;
 358     else
 359         attr |= LTO_SYMBOL_SCOPE_INTERNAL;
 360
 361     // add to table of symbols
 362     NameAndAttributes info;
 363     info.name = symbolName;
 364     info.attributes = (lto_symbol_attributes)attr;
 365     _symbols.push_back(info);
 366     _defines[info.name] = 1;
 367 }
 368
 369 void LTOModule::addAsmGlobalSymbol(const char *name) {
 370     // only add new define if not already defined
 371     if (_defines.count(name) == 0)
 372         return;
 373
 374     // string is owned by _defines
 375     const char *symbolName = ::strdup(name);
 376     uint32_t attr = LTO_SYMBOL_DEFINITION_REGULAR;
 377     attr |= LTO_SYMBOL_SCOPE_DEFAULT;
 378     NameAndAttributes info;
 379     info.name = symbolName;
 380     info.attributes = (lto_symbol_attributes)attr;
 381     _symbols.push_back(info);
 382     _defines[info.name] = 1;
 383 }
 384
 385 void LTOModule::addPotentialUndefinedSymbol(GlobalValue* decl, Mangler &mangler)
 386 {
 387     // ignore all llvm.* symbols
 388     if (decl->getName().startswith("llvm."))
 389         return;
 390
 391     // ignore all aliases
 392     if (isa<GlobalAlias>(decl))
 393         return;
 394
 395     std::string name = mangler.getNameWithPrefix(decl);
 396
 397     // we already have the symbol
 398     if (_undefines.find(name) != _undefines.end())
 399       return;
 400
 401     NameAndAttributes info;
 402     // string is owned by _undefines
 403     info.name = ::strdup(name.c_str());
 404     if (decl->hasExternalWeakLinkage())
 405       info.attributes = LTO_SYMBOL_DEFINITION_WEAKUNDEF;
 406     else
 407       info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
 408     _undefines[name] = info;
 409 }
 410
 411
 412
 413 // Find external symbols referenced by VALUE. This is a recursive function.
 414 void LTOModule::findExternalRefs(Value* value, Mangler &mangler) {
 415
 416     if (GlobalValue* gv = dyn_cast<GlobalValue>(value)) {
 417         if (!gv->hasExternalLinkage())
 418             addPotentialUndefinedSymbol(gv, mangler);
 419         // If this is a variable definition, do not recursively process
 420         // initializer.  It might contain a reference to this variable
 421         // and cause an infinite loop.  The initializer will be
 422         // processed in addDefinedDataSymbol().
 423         return;
 424     }
 425
 426     // GlobalValue, even with InternalLinkage type, may have operands with
 427     // ExternalLinkage type. Do not ignore these operands.
 428     if (Constant* c = dyn_cast<Constant>(value)) {
 429         // Handle ConstantExpr, ConstantStruct, ConstantArry etc.
 430         for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i)
 431             findExternalRefs(c->getOperand(i), mangler);
 432     }
 433 }
 434
 435 void LTOModule::lazyParseSymbols()
 436 {
 437     if (!_symbolsParsed) {
 438         _symbolsParsed = true;
 439
 440         // Use mangler to add GlobalPrefix to names to match linker names.
 441         MCContext Context(*_target->getMCAsmInfo());
 442         Mangler mangler(Context, *_target->getTargetData());
 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 }