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