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