tools/lto-bugpoint/LTOBugPoint.cpp

   1 //===- LTOBugPoint.cpp - Top-Level LTO BugPoint class ---------------------===//
   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 class contains all of the shared state and information that is used by
  11 // the LTO BugPoint tool to track down bit code files that cause errors.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "LTOBugPoint.h"
  16 #include "llvm/PassManager.h"
  17 #include "llvm/ModuleProvider.h"
  18 #include "llvm/CodeGen/FileWriters.h"
  19 #include "llvm/Target/SubtargetFeature.h"
  20 #include "llvm/Target/TargetOptions.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Target/TargetData.h"
  23 #include "llvm/Target/TargetAsmInfo.h"
  24 #include "llvm/Target/TargetMachineRegistry.h"
  25 #include "llvm/Support/SystemUtils.h"
  26 #include "llvm/Support/MemoryBuffer.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include "llvm/Bitcode/ReaderWriter.h"
  29 #include "llvm/Config/config.h"
  30 #include <fstream>
  31 #include <iostream>
  32
  33 using namespace llvm;
  34 using namespace Reloc;
  35
  36 /// printBitVector - Helper function.
  37 static void printBitVector(BitVector &BV, const char *Title) {
  38   std::cerr << Title;
  39   for (unsigned i = 0, e = BV.size(); i < e; i++) {
  40     if (BV[i])
  41       std::cerr << " " << i;
  42   }
  43   std::cerr << "\n";
  44 }
  45
  46 /// printBitVector - Helper function.
  47 static void printBitVectorFiles(BitVector &BV, const char *Title,
  48                                 SmallVector<std::string, 16> &InFiles) {
  49   std::cerr << Title << "\n";
  50   for (unsigned i = 0, e = BV.size(); i < e; i++) {
  51     if (BV[i])
  52       std::cerr << "\t" << InFiles[i] << "\n";
  53   }
  54 }
  55
  56 /// LTOBugPoint -- Constructor. Popuate list of linker options and
  57 /// list of linker input files.
  58 LTOBugPoint::LTOBugPoint(std::istream &args, std::istream &ins) {
  59
  60   // Read linker options. Order is important here.
  61   std::string option;
  62   while (getline(args, option))
  63     LinkerOptions.push_back(option);
  64
  65   // Read linker input files. Order is important here.
  66   std::string inFile;
  67   while(getline(ins, inFile))
  68     LinkerInputFiles.push_back(inFile);
  69
  70   TempDir = sys::Path::GetTemporaryDirectory();
  71
  72   // FIXME - Use command line option to set this.
  73   findLinkingFailure = true;
  74 }
  75
  76 LTOBugPoint::~LTOBugPoint() {
  77   TempDir.eraseFromDisk(true);
  78 }
  79
  80 /// findTroubleMakers - Find minimum set of input files that causes error
  81 /// identified by the script.
  82 bool
  83 LTOBugPoint::findTroubleMakers(SmallVector<std::string, 4> &TroubleMakers,
  84                                std::string &Script) {
  85
  86   // Reproduce original error.
  87   if (!relinkProgram(LinkerInputFiles) && !findLinkingFailure) {
  88     ErrMsg = " Unable to reproduce original error!";
  89     return false;
  90   }
  91
  92   if (!findLinkingFailure && !reproduceProgramError(Script)) {
  93     ErrMsg = " Unable to reproduce original error!";
  94     return false;
  95   }
  96
  97   // Build native object files set.
  98   unsigned Size = LinkerInputFiles.size();
  99   BCFiles.resize(Size);
 100   ConfirmedClean.resize(Size);
 101   ConfirmedGuilty.resize(Size);
 102   for (unsigned I = 0; I < Size; ++I) {
 103     std::string &FileName = LinkerInputFiles[I];
 104     sys::Path InputFile(FileName.c_str());
 105     if (InputFile.isDynamicLibrary() || InputFile.isArchive()) {
 106       ErrMsg = "Unable to handle input file " + FileName;
 107       return false;
 108     }
 109     else if (InputFile.isBitcodeFile()) {
 110       BCFiles.set(I);
 111       if (getNativeObjectFile(FileName) == false)
 112         return false;
 113     }
 114     else {
 115       // Original native object input files are always clean.
 116       ConfirmedClean.set(I);
 117       NativeInputFiles.push_back(FileName);
 118     }
 119   }
 120
 121   if (BCFiles.none()) {
 122     ErrMsg = "Unable to help!";
 123     ErrMsg = " Need at least one input file that contains llvm bitcode";
 124     return false;
 125   }
 126
 127   // Try to reproduce error using native object files first. If the error
 128   // occurs then this is not a LTO error.
 129   if (!relinkProgram(NativeInputFiles))  {
 130     ErrMsg = " Unable to link the program using all native object files!";
 131     return false;
 132   }
 133   if (!findLinkingFailure && reproduceProgramError(Script) == true) {
 134     ErrMsg = " Unable to fix program error using all native object files!";
 135     return false;
 136   }
 137
 138   printBitVector(BCFiles, "Initial set of llvm bitcode files");
 139   identifyTroubleMakers(BCFiles);
 140   printBitVectorFiles(ConfirmedGuilty,
 141                       "Identified minimal set of bitcode files!",
 142                       LinkerInputFiles);
 143   return true;
 144 }
 145
 146 /// getFeatureString - Return a string listing the features associated with the
 147 /// target triple.
 148 ///
 149 /// FIXME: This is an inelegant way of specifying the features of a
 150 /// subtarget. It would be better if we could encode this information into the
 151 /// IR.
 152 std::string LTOBugPoint::getFeatureString(const char *TargetTriple) {
 153   SubtargetFeatures Features;
 154
 155   if (strncmp(TargetTriple, "powerpc-apple-", 14) == 0) {
 156     Features.AddFeature("altivec", true);
 157   } else if (strncmp(TargetTriple, "powerpc64-apple-", 16) == 0) {
 158     Features.AddFeature("64bit", true);
 159     Features.AddFeature("altivec", true);
 160   }
 161
 162   return Features.getString();
 163 }
 164
 165 /// assembleBitcode - Generate assembly code from the module. Return false
 166 /// in case of an error.
 167 bool LTOBugPoint::assembleBitcode(llvm::Module *M, const char *AsmFileName) {
 168   std::string TargetTriple = M->getTargetTriple();
 169   std::string FeatureStr =
 170     getFeatureString(TargetTriple.c_str());
 171
 172   const TargetMachineRegistry::entry* Registry =
 173     TargetMachineRegistry::getClosestStaticTargetForModule(
 174                                                        *M, ErrMsg);
 175   if ( Registry == NULL )
 176     return false;
 177
 178   TargetMachine *Target = Registry->CtorFn(*M, FeatureStr.c_str());
 179
 180   // If target supports exception handling then enable it now.
 181   if (Target->getTargetAsmInfo()->doesSupportExceptionHandling())
 182     ExceptionHandling = true;
 183
 184   // FIXME
 185   Target->setRelocationModel(Reloc::PIC_);
 186
 187   FunctionPassManager* CGPasses =
 188     new FunctionPassManager(new ExistingModuleProvider(M));
 189
 190   CGPasses->add(new TargetData(*Target->getTargetData()));
 191   MachineCodeEmitter* mce = NULL;
 192
 193   std::string error;
 194   raw_ostream *Out = new raw_fd_ostream(AsmFileName, error);
 195   if (!error.empty()) {
 196     std::cerr << error << '\n';
 197     delete Out;
 198     return false;
 199   }
 200
 201   switch (Target->addPassesToEmitFile(*CGPasses, *Out,
 202                                       TargetMachine::AssemblyFile, true)) {
 203   case FileModel::MachOFile:
 204     mce = AddMachOWriter(*CGPasses, *Out, *Target);
 205     break;
 206   case FileModel::ElfFile:
 207     mce = AddELFWriter(*CGPasses, *Out, *Target);
 208     break;
 209   case FileModel::AsmFile:
 210     break;
 211   case FileModel::Error:
 212   case FileModel::None:
 213     ErrMsg = "target file type not supported";
 214     return false;
 215   }
 216
 217   if (Target->addPassesToEmitFileFinish(*CGPasses, mce, true)) {
 218     ErrMsg = "target does not support generation of this file type";
 219     return false;
 220   }
 221
 222   CGPasses->doInitialization();
 223   for (Module::iterator
 224          it = M->begin(), e = M->end(); it != e; ++it)
 225     if (!it->isDeclaration())
 226       CGPasses->run(*it);
 227   CGPasses->doFinalization();
 228   delete Out;
 229   return true;
 230 }
 231
 232 /// getNativeObjectFile - Generate native object file based from llvm
 233 /// bitcode file. Return false in case of an error.
 234 bool LTOBugPoint::getNativeObjectFile(std::string &FileName) {
 235
 236   std::auto_ptr<Module> M;
 237   MemoryBuffer *Buffer
 238     = MemoryBuffer::getFile(FileName.c_str(), &ErrMsg);
 239   if (!Buffer) {
 240     ErrMsg = "Unable to read " + FileName;
 241     return false;
 242   }
 243   M.reset(ParseBitcodeFile(Buffer, &ErrMsg));
 244   std::string TargetTriple = M->getTargetTriple();
 245
 246   sys::Path AsmFile(TempDir);
 247   if(AsmFile.createTemporaryFileOnDisk(false, &ErrMsg))
 248     return false;
 249
 250   if (assembleBitcode(M.get(), AsmFile.c_str()) == false) {
 251     AsmFile.eraseFromDisk();
 252     return false;
 253   }
 254
 255   sys::Path NativeFile(TempDir);
 256   if(NativeFile.createTemporaryFileOnDisk(false, &ErrMsg)) {
 257     AsmFile.eraseFromDisk();
 258     return false;
 259   }
 260
 261   // find compiler driver
 262   const sys::Path gcc = sys::Program::FindProgramByName("gcc");
 263   if ( gcc.isEmpty() ) {
 264     ErrMsg = "can't locate gcc";
 265     AsmFile.eraseFromDisk();
 266     NativeFile.eraseFromDisk();
 267     return false;
 268   }
 269
 270   // build argument list
 271   std::vector<const char*> args;
 272   args.push_back(gcc.c_str());
 273   if ( TargetTriple.find("darwin") != TargetTriple.size() ) {
 274     if (strncmp(TargetTriple.c_str(), "i686-apple-", 11) == 0) {
 275       args.push_back("-arch");
 276       args.push_back("i386");
 277     }
 278     else if (strncmp(TargetTriple.c_str(), "x86_64-apple-", 13) == 0) {
 279       args.push_back("-arch");
 280       args.push_back("x86_64");
 281     }
 282     else if (strncmp(TargetTriple.c_str(), "powerpc-apple-", 14) == 0) {
 283       args.push_back("-arch");
 284       args.push_back("ppc");
 285     }
 286     else if (strncmp(TargetTriple.c_str(), "powerpc64-apple-", 16) == 0) {
 287       args.push_back("-arch");
 288       args.push_back("ppc64");
 289     }
 290   }
 291   args.push_back("-c");
 292   args.push_back("-x");
 293   args.push_back("assembler");
 294   args.push_back("-o");
 295   args.push_back(NativeFile.c_str());
 296   args.push_back(AsmFile.c_str());
 297   args.push_back(0);
 298
 299   // invoke assembler
 300   if (sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 0, 0, &ErrMsg)) {
 301     ErrMsg = "error in assembly";
 302     AsmFile.eraseFromDisk();
 303     NativeFile.eraseFromDisk();
 304     return false;
 305   }
 306
 307   AsmFile.eraseFromDisk();
 308   NativeInputFiles.push_back(NativeFile.c_str());
 309   return true;
 310 }
 311
 312 /// relinkProgram - Relink program. Return false if linking fails.
 313 bool LTOBugPoint::relinkProgram(llvm::SmallVector<std::string, 16> &InFiles) {
 314   if (InFiles.empty())
 315     return false;
 316
 317   // Atleast three options: linker path, -o and output file name.
 318   if (LinkerOptions.size() < 3)
 319     return false;
 320
 321   const sys::Path linker = sys::Program::FindProgramByName(LinkerOptions[0]);
 322   if (linker.isEmpty()) {
 323     ErrMsg = "can't locate linker";
 324     return false;
 325   }
 326
 327   std::vector<const char*> Args;
 328   for (unsigned i = 0, e = LinkerOptions.size(); i < e; ++i)
 329     Args.push_back(LinkerOptions[i].c_str());
 330
 331   for (unsigned i = 0, e = InFiles.size(); i < e; ++i)
 332     Args.push_back(InFiles[i].c_str());
 333
 334   Args.push_back(0);
 335
 336   if (sys::Program::ExecuteAndWait(linker, &Args[0], 0, 0, 0, 0, &ErrMsg)) {
 337       ErrMsg = "error while linking program";
 338       return false;
 339   }
 340   return true;
 341 }
 342
 343 /// reproduceProgramError - Validate program using user provided script.
 344 /// Return true if program error is reproduced.
 345 bool LTOBugPoint::reproduceProgramError(std::string &Script) {
 346
 347   const sys::Path validator = sys::Program::FindProgramByName(Script);
 348   if (validator.isEmpty()) {
 349     ErrMsg = "can't locate validation script";
 350     return false;
 351   }
 352
 353   std::vector<const char*> Args;
 354   Args.push_back(Script.c_str());
 355   Args.push_back(0);
 356
 357   int result =
 358     sys::Program::ExecuteAndWait(validator, &Args[0], 0, 0, 0, 0, &ErrMsg);
 359
 360   // Validation scrip returns non-zero if the error is reproduced.
 361   if (result > 0)
 362     // Able to reproduce program error.
 363     return true;
 364
 365   else if (result < 0)
 366     // error occured while running validation script. ErrMsg contains error
 367     // description.
 368     return false;
 369
 370   return false;
 371 }
 372
 373 /// identifyTroubleMakers - Identify set of bit code files that are causing
 374 /// the error. This is a recursive function.
 375 void LTOBugPoint::identifyTroubleMakers(llvm::BitVector &In) {
 376
 377   assert (In.size() == LinkerInputFiles.size()
 378           && "Invalid identifyTroubleMakers input!\n");
 379
 380   printBitVector(In, "Processing files ");
 381   BitVector CandidateVector;
 382   CandidateVector.resize(LinkerInputFiles.size());
 383
 384   // Process first half
 385   unsigned count = 0;
 386   for (unsigned i = 0, e =  In.size(); i < e; ++i) {
 387     if (!ConfirmedClean[i]) {
 388       count++;
 389       CandidateVector.set(i);
 390     }
 391     if (count >= In.count()/2)
 392       break;
 393   }
 394
 395   if (CandidateVector.none())
 396     return;
 397
 398   printBitVector(CandidateVector, "Candidate vector ");
 399
 400   // Reproduce the error using native object files for candidate files.
 401   SmallVector<std::string, 16> CandidateFiles;
 402   for (unsigned i = 0, e = CandidateVector.size(); i < e; ++i) {
 403     if (CandidateVector[i] || ConfirmedClean[i])
 404       CandidateFiles.push_back(NativeInputFiles[i]);
 405     else
 406       CandidateFiles.push_back(LinkerInputFiles[i]);
 407   }
 408
 409   bool result = relinkProgram(CandidateFiles);
 410   if (findLinkingFailure) {
 411     if (result == true) {
 412       // Candidate files are suspected.
 413       if (CandidateVector.count() == 1) {
 414         ConfirmedGuilty.set(CandidateVector.find_first());
 415         return;
 416       }
 417       else
 418         identifyTroubleMakers(CandidateVector);
 419     } else {
 420       // Candidate files are not causing this error.
 421       for (unsigned i = 0, e = CandidateVector.size(); i < e; ++i) {
 422         if (CandidateVector[i])
 423           ConfirmedClean.set(i);
 424       }
 425     }
 426   } else {
 427     std::cerr << "FIXME : Not yet implemented!\n";
 428   }
 429
 430   // Process remaining cadidates
 431   CandidateVector.clear();
 432   CandidateVector.resize(LinkerInputFiles.size());
 433   for (unsigned i = 0, e = LinkerInputFiles.size(); i < e; ++i) {
 434     if (!ConfirmedClean[i] && !ConfirmedGuilty[i])
 435       CandidateVector.set(i);
 436   }
 437   identifyTroubleMakers(CandidateVector);
 438 }