lto.cpp revision 5e563c326490207ebd58d47935fb9efda7638aa2
1//===-lto.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 "llvm/Module.h" 16#include "llvm/PassManager.h" 17#include "llvm/Linker.h" 18#include "llvm/Constants.h" 19#include "llvm/DerivedTypes.h" 20#include "llvm/ModuleProvider.h" 21#include "llvm/Bitcode/ReaderWriter.h" 22#include "llvm/Support/CommandLine.h" 23#include "llvm/Support/FileUtilities.h" 24#include "llvm/Support/SystemUtils.h" 25#include "llvm/Support/Mangler.h" 26#include "llvm/Support/MemoryBuffer.h" 27#include "llvm/System/Program.h" 28#include "llvm/System/Signals.h" 29#include "llvm/Analysis/Passes.h" 30#include "llvm/Analysis/LoopPass.h" 31#include "llvm/Analysis/Verifier.h" 32#include "llvm/CodeGen/FileWriters.h" 33#include "llvm/Target/SubtargetFeature.h" 34#include "llvm/Target/TargetData.h" 35#include "llvm/Target/TargetMachine.h" 36#include "llvm/Target/TargetMachineRegistry.h" 37#include "llvm/Target/TargetAsmInfo.h" 38#include "llvm/Transforms/IPO.h" 39#include "llvm/Transforms/Scalar.h" 40#include "llvm/Analysis/LoadValueNumbering.h" 41#include "llvm/Support/MathExtras.h" 42#include "llvm/LinkTimeOptimizer.h" 43#include <fstream> 44#include <ostream> 45using namespace llvm; 46 47extern "C" 48llvm::LinkTimeOptimizer *createLLVMOptimizer(unsigned VERSION) 49{ 50 // Linker records LLVM_LTO_VERSION based on llvm optimizer available 51 // during linker build. Match linker's recorded LTO VERSION number 52 // with installed llvm optimizer version. If these numbers do not match 53 // then linker may not be able to use llvm optimizer dynamically. 54 if (VERSION != LLVM_LTO_VERSION) 55 return NULL; 56 57 llvm::LTO *l = new llvm::LTO(); 58 return l; 59} 60 61/// If symbol is not used then make it internal and let optimizer takes 62/// care of it. 63void LLVMSymbol::mayBeNotUsed() { 64 gv->setLinkage(GlobalValue::InternalLinkage); 65} 66 67// Map LLVM LinkageType to LTO LinakgeType 68static LTOLinkageTypes 69getLTOLinkageType(GlobalValue *v) 70{ 71 LTOLinkageTypes lt; 72 if (v->hasExternalLinkage()) 73 lt = LTOExternalLinkage; 74 else if (v->hasLinkOnceLinkage()) 75 lt = LTOLinkOnceLinkage; 76 else if (v->hasWeakLinkage()) 77 lt = LTOWeakLinkage; 78 else 79 // Otherwise it is internal linkage for link time optimizer 80 lt = LTOInternalLinkage; 81 return lt; 82} 83 84// MAP LLVM VisibilityType to LTO VisibilityType 85static LTOVisibilityTypes 86getLTOVisibilityType(GlobalValue *v) 87{ 88 LTOVisibilityTypes vis; 89 if (v->hasHiddenVisibility()) 90 vis = LTOHiddenVisibility; 91 else if (v->hasProtectedVisibility()) 92 vis = LTOProtectedVisibility; 93 else 94 vis = LTODefaultVisibility; 95 return vis; 96} 97 98// Find exeternal symbols referenced by VALUE. This is a recursive function. 99static void 100findExternalRefs(Value *value, std::set<std::string> &references, 101 Mangler &mangler) { 102 103 if (GlobalValue *gv = dyn_cast<GlobalValue>(value)) { 104 LTOLinkageTypes lt = getLTOLinkageType(gv); 105 if (lt != LTOInternalLinkage && strncmp (gv->getName().c_str(), "llvm.", 5)) 106 references.insert(mangler.getValueName(gv)); 107 } 108 109 // GlobalValue, even with InternalLinkage type, may have operands with 110 // ExternalLinkage type. Do not ignore these operands. 111 if (Constant *c = dyn_cast<Constant>(value)) 112 // Handle ConstantExpr, ConstantStruct, ConstantArry etc.. 113 for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i) 114 findExternalRefs(c->getOperand(i), references, mangler); 115} 116 117/// If Module with InputFilename is available then remove it from allModules 118/// and call delete on it. 119void 120LTO::removeModule (const std::string &InputFilename) 121{ 122 NameToModuleMap::iterator pos = allModules.find(InputFilename.c_str()); 123 if (pos == allModules.end()) 124 return; 125 126 Module *m = pos->second; 127 allModules.erase(pos); 128 delete m; 129} 130 131/// InputFilename is a LLVM bitcode file. If Module with InputFilename is 132/// available then return it. Otherwise parseInputFilename. 133Module * 134LTO::getModule(const std::string &InputFilename) 135{ 136 Module *m = NULL; 137 138 NameToModuleMap::iterator pos = allModules.find(InputFilename.c_str()); 139 if (pos != allModules.end()) 140 m = allModules[InputFilename.c_str()]; 141 else { 142 if (MemoryBuffer *Buffer 143 = MemoryBuffer::getFile(&InputFilename[0], InputFilename.size())) { 144 m = ParseBitcodeFile(Buffer); 145 delete Buffer; 146 } 147 allModules[InputFilename.c_str()] = m; 148 } 149 return m; 150} 151 152/// InputFilename is a LLVM bitcode file. Reade this bitcode file and 153/// set corresponding target triplet string. 154void 155LTO::getTargetTriple(const std::string &InputFilename, 156 std::string &targetTriple) 157{ 158 Module *m = getModule(InputFilename); 159 if (m) 160 targetTriple = m->getTargetTriple(); 161} 162 163/// InputFilename is a LLVM bitcode file. Read it using bitcode reader. 164/// Collect global functions and symbol names in symbols vector. 165/// Collect external references in references vector. 166/// Return LTO_READ_SUCCESS if there is no error. 167enum LTOStatus 168LTO::readLLVMObjectFile(const std::string &InputFilename, 169 NameToSymbolMap &symbols, 170 std::set<std::string> &references) 171{ 172 Module *m = getModule(InputFilename); 173 if (!m) 174 return LTO_READ_FAILURE; 175 176 // Collect Target info 177 getTarget(m); 178 179 if (!Target) 180 return LTO_READ_FAILURE; 181 182 // Use mangler to add GlobalPrefix to names to match linker names. 183 // FIXME : Instead of hard coding "-" use GlobalPrefix. 184 Mangler mangler(*m, Target->getTargetAsmInfo()->getGlobalPrefix()); 185 modules.push_back(m); 186 187 for (Module::iterator f = m->begin(), e = m->end(); f != e; ++f) { 188 LTOLinkageTypes lt = getLTOLinkageType(f); 189 LTOVisibilityTypes vis = getLTOVisibilityType(f); 190 if (!f->isDeclaration() && lt != LTOInternalLinkage 191 && strncmp (f->getName().c_str(), "llvm.", 5)) { 192 int alignment = ( 16 > f->getAlignment() ? 16 : f->getAlignment()); 193 LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, f, f->getName(), 194 mangler.getValueName(f), 195 Log2_32(alignment)); 196 symbols[newSymbol->getMangledName()] = newSymbol; 197 allSymbols[newSymbol->getMangledName()] = newSymbol; 198 } 199 200 // Collect external symbols referenced by this function. 201 for (Function::iterator b = f->begin(), fe = f->end(); b != fe; ++b) 202 for (BasicBlock::iterator i = b->begin(), be = b->end(); 203 i != be; ++i) { 204 for (unsigned count = 0, total = i->getNumOperands(); 205 count != total; ++count) 206 findExternalRefs(i->getOperand(count), references, mangler); 207 } 208 } 209 210 for (Module::global_iterator v = m->global_begin(), e = m->global_end(); 211 v != e; ++v) { 212 LTOLinkageTypes lt = getLTOLinkageType(v); 213 LTOVisibilityTypes vis = getLTOVisibilityType(v); 214 if (!v->isDeclaration() && lt != LTOInternalLinkage 215 && strncmp (v->getName().c_str(), "llvm.", 5)) { 216 const TargetData *TD = Target->getTargetData(); 217 LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, v, v->getName(), 218 mangler.getValueName(v), 219 TD->getPreferredAlignmentLog(v)); 220 symbols[newSymbol->getMangledName()] = newSymbol; 221 allSymbols[newSymbol->getMangledName()] = newSymbol; 222 223 for (unsigned count = 0, total = v->getNumOperands(); 224 count != total; ++count) 225 findExternalRefs(v->getOperand(count), references, mangler); 226 227 } 228 } 229 230 return LTO_READ_SUCCESS; 231} 232 233/// Get TargetMachine. 234/// Use module M to find appropriate Target. 235void 236LTO::getTarget (Module *M) { 237 238 if (Target) 239 return; 240 241 std::string Err; 242 const TargetMachineRegistry::entry* March = 243 TargetMachineRegistry::getClosestStaticTargetForModule(*M, Err); 244 245 if (March == 0) 246 return; 247 248 // Create target 249 std::string Features; 250 Target = March->CtorFn(*M, Features); 251} 252 253/// Optimize module M using various IPO passes. Use exportList to 254/// internalize selected symbols. Target platform is selected 255/// based on information available to module M. No new target 256/// features are selected. 257enum LTOStatus 258LTO::optimize(Module *M, std::ostream &Out, 259 std::vector<const char *> &exportList) 260{ 261 // Instantiate the pass manager to organize the passes. 262 PassManager Passes; 263 264 // Collect Target info 265 getTarget(M); 266 267 if (!Target) 268 return LTO_NO_TARGET; 269 270 // Start off with a verification pass. 271 Passes.add(createVerifierPass()); 272 273 // Add an appropriate TargetData instance for this module... 274 Passes.add(new TargetData(*Target->getTargetData())); 275 276 // Internalize symbols if export list is nonemty 277 if (!exportList.empty()) 278 Passes.add(createInternalizePass(exportList)); 279 280 // Now that we internalized some globals, see if we can hack on them! 281 Passes.add(createGlobalOptimizerPass()); 282 283 // Linking modules together can lead to duplicated global constants, only 284 // keep one copy of each constant... 285 Passes.add(createConstantMergePass()); 286 287 // If the -s command line option was specified, strip the symbols out of the 288 // resulting program to make it smaller. -s is a GLD option that we are 289 // supporting. 290 Passes.add(createStripSymbolsPass()); 291 292 // Propagate constants at call sites into the functions they call. 293 Passes.add(createIPConstantPropagationPass()); 294 295 // Remove unused arguments from functions... 296 Passes.add(createDeadArgEliminationPass()); 297 298 Passes.add(createFunctionInliningPass()); // Inline small functions 299 300 Passes.add(createPruneEHPass()); // Remove dead EH info 301 302 Passes.add(createGlobalDCEPass()); // Remove dead functions 303 304 // If we didn't decide to inline a function, check to see if we can 305 // transform it to pass arguments by value instead of by reference. 306 Passes.add(createArgumentPromotionPass()); 307 308 // The IPO passes may leave cruft around. Clean up after them. 309 Passes.add(createInstructionCombiningPass()); 310 311 Passes.add(createScalarReplAggregatesPass()); // Break up allocas 312 313 // Run a few AA driven optimizations here and now, to cleanup the code. 314 Passes.add(createGlobalsModRefPass()); // IP alias analysis 315 316 Passes.add(createLICMPass()); // Hoist loop invariants 317 Passes.add(createLoadValueNumberingPass()); // GVN for load instrs 318 Passes.add(createGCSEPass()); // Remove common subexprs 319 Passes.add(createDeadStoreEliminationPass()); // Nuke dead stores 320 321 // Cleanup and simplify the code after the scalar optimizations. 322 Passes.add(createInstructionCombiningPass()); 323 324 // Delete basic blocks, which optimization passes may have killed... 325 Passes.add(createCFGSimplificationPass()); 326 327 // Now that we have optimized the program, discard unreachable functions... 328 Passes.add(createGlobalDCEPass()); 329 330 // Make sure everything is still good. 331 Passes.add(createVerifierPass()); 332 333 FunctionPassManager *CodeGenPasses = 334 new FunctionPassManager(new ExistingModuleProvider(M)); 335 336 CodeGenPasses->add(new TargetData(*Target->getTargetData())); 337 338 MachineCodeEmitter *MCE = 0; 339 340 switch (Target->addPassesToEmitFile(*CodeGenPasses, Out, 341 TargetMachine::AssemblyFile, true)) { 342 default: 343 case FileModel::Error: 344 return LTO_WRITE_FAILURE; 345 case FileModel::AsmFile: 346 break; 347 case FileModel::MachOFile: 348 MCE = AddMachOWriter(*CodeGenPasses, Out, *Target); 349 break; 350 case FileModel::ElfFile: 351 MCE = AddELFWriter(*CodeGenPasses, Out, *Target); 352 break; 353 } 354 355 if (Target->addPassesToEmitFileFinish(*CodeGenPasses, MCE, true)) 356 return LTO_WRITE_FAILURE; 357 358 // Run our queue of passes all at once now, efficiently. 359 Passes.run(*M); 360 361 // Run the code generator, if present. 362 CodeGenPasses->doInitialization(); 363 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) { 364 if (!I->isDeclaration()) 365 CodeGenPasses->run(*I); 366 } 367 CodeGenPasses->doFinalization(); 368 369 return LTO_OPT_SUCCESS; 370} 371 372///Link all modules together and optimize them using IPO. Generate 373/// native object file using OutputFilename 374/// Return appropriate LTOStatus. 375enum LTOStatus 376LTO::optimizeModules(const std::string &OutputFilename, 377 std::vector<const char *> &exportList, 378 std::string &targetTriple, 379 bool saveTemps, const char *FinalOutputFilename) 380{ 381 if (modules.empty()) 382 return LTO_NO_WORK; 383 384 std::ios::openmode io_mode = 385 std::ios::out | std::ios::trunc | std::ios::binary; 386 std::string *errMsg = NULL; 387 Module *bigOne = modules[0]; 388 Linker theLinker("LinkTimeOptimizer", bigOne, false); 389 for (unsigned i = 1, e = modules.size(); i != e; ++i) 390 if (theLinker.LinkModules(bigOne, modules[i], errMsg)) 391 return LTO_MODULE_MERGE_FAILURE; 392 // all modules have been handed off to the linker. 393 modules.clear(); 394 395 sys::Path FinalOutputPath(FinalOutputFilename); 396 FinalOutputPath.eraseSuffix(); 397 398 switch(CGModel) { 399 case LTO_CGM_Dynamic: 400 Target->setRelocationModel(Reloc::PIC_); 401 break; 402 case LTO_CGM_DynamicNoPIC: 403 Target->setRelocationModel(Reloc::DynamicNoPIC); 404 break; 405 case LTO_CGM_Static: 406 Target->setRelocationModel(Reloc::Static); 407 break; 408 } 409 410 if (saveTemps) { 411 std::string tempFileName(FinalOutputPath.c_str()); 412 tempFileName += "0.bc"; 413 std::ofstream Out(tempFileName.c_str(), io_mode); 414 WriteBitcodeToFile(bigOne, Out); 415 } 416 417 // Strip leading underscore because it was added to match names 418 // seen by linker. 419 for (unsigned i = 0, e = exportList.size(); i != e; ++i) { 420 const char *name = exportList[i]; 421 NameToSymbolMap::iterator itr = allSymbols.find(name); 422 if (itr != allSymbols.end()) 423 exportList[i] = allSymbols[name]->getName(); 424 } 425 426 427 std::string ErrMsg; 428 sys::Path TempDir = sys::Path::GetTemporaryDirectory(&ErrMsg); 429 if (TempDir.isEmpty()) { 430 cerr << "lto: " << ErrMsg << "\n"; 431 return LTO_WRITE_FAILURE; 432 } 433 sys::Path tmpAsmFilePath(TempDir); 434 if (!tmpAsmFilePath.appendComponent("lto")) { 435 cerr << "lto: " << ErrMsg << "\n"; 436 TempDir.eraseFromDisk(true); 437 return LTO_WRITE_FAILURE; 438 } 439 if (tmpAsmFilePath.createTemporaryFileOnDisk(true, &ErrMsg)) { 440 cerr << "lto: " << ErrMsg << "\n"; 441 TempDir.eraseFromDisk(true); 442 return LTO_WRITE_FAILURE; 443 } 444 sys::RemoveFileOnSignal(tmpAsmFilePath); 445 446 std::ofstream asmFile(tmpAsmFilePath.c_str(), io_mode); 447 if (!asmFile.is_open() || asmFile.bad()) { 448 if (tmpAsmFilePath.exists()) { 449 tmpAsmFilePath.eraseFromDisk(); 450 TempDir.eraseFromDisk(true); 451 } 452 return LTO_WRITE_FAILURE; 453 } 454 455 enum LTOStatus status = optimize(bigOne, asmFile, exportList); 456 asmFile.close(); 457 if (status != LTO_OPT_SUCCESS) { 458 tmpAsmFilePath.eraseFromDisk(); 459 TempDir.eraseFromDisk(true); 460 return status; 461 } 462 463 if (saveTemps) { 464 std::string tempFileName(FinalOutputPath.c_str()); 465 tempFileName += "1.bc"; 466 std::ofstream Out(tempFileName.c_str(), io_mode); 467 WriteBitcodeToFile(bigOne, Out); 468 } 469 470 targetTriple = bigOne->getTargetTriple(); 471 472 // Run GCC to assemble and link the program into native code. 473 // 474 // Note: 475 // We can't just assemble and link the file with the system assembler 476 // and linker because we don't know where to put the _start symbol. 477 // GCC mysteriously knows how to do it. 478 const sys::Path gcc = sys::Program::FindProgramByName("gcc"); 479 if (gcc.isEmpty()) { 480 tmpAsmFilePath.eraseFromDisk(); 481 TempDir.eraseFromDisk(true); 482 return LTO_ASM_FAILURE; 483 } 484 485 std::vector<const char*> args; 486 args.push_back(gcc.c_str()); 487 args.push_back("-c"); 488 args.push_back("-x"); 489 args.push_back("assembler"); 490 args.push_back("-o"); 491 args.push_back(OutputFilename.c_str()); 492 args.push_back(tmpAsmFilePath.c_str()); 493 args.push_back(0); 494 495 if (sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 1, 0, &ErrMsg)) { 496 cerr << "lto: " << ErrMsg << "\n"; 497 return LTO_ASM_FAILURE; 498 } 499 500 tmpAsmFilePath.eraseFromDisk(); 501 TempDir.eraseFromDisk(true); 502 503 return LTO_OPT_SUCCESS; 504} 505 506void LTO::printVersion() { 507 cl::PrintVersionMessage(); 508} 509 510/// Unused pure-virtual destructor. Must remain empty. 511LinkTimeOptimizer::~LinkTimeOptimizer() {} 512 513/// Destruct LTO. Delete all modules, symbols and target. 514LTO::~LTO() { 515 516 for (std::vector<Module *>::iterator itr = modules.begin(), e = modules.end(); 517 itr != e; ++itr) 518 delete *itr; 519 520 modules.clear(); 521 522 for (NameToSymbolMap::iterator itr = allSymbols.begin(), e = allSymbols.end(); 523 itr != e; ++itr) 524 delete itr->second; 525 526 allSymbols.clear(); 527 528 delete Target; 529} 530