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