tools/bugpoint/CodeGeneratorBug.cpp

   1 //===- CodeGeneratorBug.cpp - Debug code generation bugs ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements program code generation debugging support.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "BugDriver.h"
  15 #include "ListReducer.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/GlobalValue.h"
  19 #include "llvm/iMemory.h"
  20 #include "llvm/iTerminators.h"
  21 #include "llvm/iOther.h"
  22 #include "llvm/Module.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Analysis/Verifier.h"
  25 #include "llvm/Support/Mangler.h"
  26 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  27 #include "llvm/Transforms/Utils/Cloning.h"
  28 #include "llvm/Transforms/Utils/Linker.h"
  29 #include "Support/CommandLine.h"
  30 #include "Support/Debug.h"
  31 #include "Support/StringExtras.h"
  32 #include "Support/FileUtilities.h"
  33 #include <algorithm>
  34 #include <set>
  35
  36 namespace llvm {
  37
  38 extern cl::list<std::string> InputArgv;
  39
  40 class ReduceMisCodegenFunctions : public ListReducer<Function*> {
  41   BugDriver &BD;
  42 public:
  43   ReduceMisCodegenFunctions(BugDriver &bd) : BD(bd) {}
  44
  45   virtual TestResult doTest(std::vector<Function*> &Prefix,
  46                             std::vector<Function*> &Suffix) {
  47     if (!Prefix.empty() && TestFuncs(Prefix))
  48       return KeepPrefix;
  49     if (!Suffix.empty() && TestFuncs(Suffix))
  50       return KeepSuffix;
  51     return NoFailure;
  52   }
  53
  54   bool TestFuncs(const std::vector<Function*> &CodegenTest,
  55                  bool KeepFiles = false);
  56 };
  57
  58
  59 bool ReduceMisCodegenFunctions::TestFuncs(const std::vector<Function*> &Funcs,
  60                                           bool KeepFiles) {
  61   std::cout << "Testing functions: ";
  62   BD.PrintFunctionList(Funcs);
  63   std::cout << "\t";
  64
  65   // Clone the module for the two halves of the program we want.
  66   Module *SafeModule = CloneModule(BD.Program);
  67
  68   // Make sure functions & globals are all external so that linkage
  69   // between the two modules will work.
  70   for (Module::iterator I = SafeModule->begin(), E = SafeModule->end();I!=E;++I)
  71     I->setLinkage(GlobalValue::ExternalLinkage);
  72   for (Module::giterator I=SafeModule->gbegin(),E = SafeModule->gend();I!=E;++I)
  73     I->setLinkage(GlobalValue::ExternalLinkage);
  74
  75   Module *TestModule = CloneModule(SafeModule);
  76
  77   // Make sure global initializers exist only in the safe module (CBE->.so)
  78   for (Module::giterator I=TestModule->gbegin(),E = TestModule->gend();I!=E;++I)
  79     I->setInitializer(0);  // Delete the initializer to make it external
  80
  81   // Remove the Test functions from the Safe module
  82   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
  83     Function *TNOF = SafeModule->getFunction(Funcs[i]->getName(),
  84                                              Funcs[i]->getFunctionType());
  85     DEBUG(std::cerr << "Removing function " << Funcs[i]->getName() << "\n");
  86     assert(TNOF && "Function doesn't exist in module!");
  87     DeleteFunctionBody(TNOF);       // Function is now external in this module!
  88   }
  89
  90   // Remove the Safe functions from the Test module
  91   for (Module::iterator I=TestModule->begin(),E=TestModule->end(); I!=E; ++I) {
  92     bool funcFound = false;
  93     for (std::vector<Function*>::const_iterator F=Funcs.begin(),Fe=Funcs.end();
  94          F != Fe; ++F)
  95       if (I->getName() == (*F)->getName()) funcFound = true;
  96
  97     if (!funcFound && !(BD.isExecutingJIT() && I->getName() == "main"))
  98       DeleteFunctionBody(I);
  99   }
 100
 101   // This is only applicable if we are debugging the JIT:
 102   // Find all external functions in the Safe modules that are actually used
 103   // (called or taken address of), and make them call the JIT wrapper instead
 104   if (BD.isExecutingJIT()) {
 105     // Must delete `main' from Safe module if it has it
 106     Function *safeMain = SafeModule->getNamedFunction("main");
 107     assert(safeMain && "`main' function not found in safe module!");
 108     DeleteFunctionBody(safeMain);
 109
 110     // Add an external function "getPointerToNamedFunction" that JIT provides
 111     // Prototype: void *getPointerToNamedFunction(const char* Name)
 112     std::vector<const Type*> Params;
 113     Params.push_back(PointerType::get(Type::SByteTy)); // std::string&
 114     FunctionType *resolverTy = FunctionType::get(PointerType::get(Type::VoidTy),
 115                                                  Params, false /* isVarArg */);
 116     Function *resolverFunc = new Function(resolverTy,
 117                                           GlobalValue::ExternalLinkage,
 118                                           "getPointerToNamedFunction",
 119                                           SafeModule);
 120
 121     // Use the function we just added to get addresses of functions we need
 122     // Iterate over the global declarations in the Safe module
 123     for (Module::iterator F=SafeModule->begin(),E=SafeModule->end(); F!=E; ++F){
 124       if (F->isExternal() && !F->use_empty() && &*F != resolverFunc &&
 125           F->getIntrinsicID() == 0 /* ignore intrinsics */ &&
 126           // Don't forward functions which are external in the test module too.
 127           !TestModule->getNamedFunction(F->getName())->isExternal()) {
 128         // If it has a non-zero use list,
 129         // 1. Add a string constant with its name to the global file
 130         // The correct type is `const [ NUM x sbyte ]' where NUM is length of
 131         // function name + 1
 132         const std::string &Name = F->getName();
 133         GlobalVariable *funcName =
 134           new GlobalVariable(ArrayType::get(Type::SByteTy, Name.length()+1),
 135                              true /* isConstant */,
 136                              GlobalValue::InternalLinkage,
 137                              ConstantArray::get(Name),
 138                              Name + "_name",
 139                              SafeModule);
 140
 141         // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an
 142         // sbyte* so it matches the signature of the resolver function.
 143         std::vector<Constant*> GEPargs(2, Constant::getNullValue(Type::LongTy));
 144
 145         // 3. Replace all uses of `func' with calls to resolver by:
 146         // (a) Iterating through the list of uses of this function
 147         // (b) Insert a cast instruction in front of each use
 148         // (c) Replace use of old call with new call
 149
 150         // GetElementPtr *funcName, ulong 0, ulong 0
 151         Value *GEP =
 152           ConstantExpr::getGetElementPtr(ConstantPointerRef::get(funcName),
 153                                          GEPargs);
 154         std::vector<Value*> ResolverArgs;
 155         ResolverArgs.push_back(GEP);
 156
 157         // Insert code at the beginning of the function
 158         while (!F->use_empty())
 159           if (Instruction *Inst = dyn_cast<Instruction>(F->use_back())) {
 160             // call resolver(GetElementPtr...)
 161             CallInst *resolve = new CallInst(resolverFunc, ResolverArgs,
 162                                              "resolver", Inst);
 163             // cast the result from the resolver to correctly-typed function
 164             CastInst *castResolver =
 165               new CastInst(resolve, PointerType::get(F->getFunctionType()),
 166                            "resolverCast", Inst);
 167             // actually use the resolved function
 168             Inst->replaceUsesOfWith(F, castResolver);
 169           } else {
 170             // FIXME: need to take care of cases where a function is used that
 171             // is not an instruction, e.g. global variable initializer...
 172             std::cerr <<
 173               "UNSUPPORTED: External function used as global initializer!\n";
 174             abort();
 175           }
 176       }
 177     }
 178   }
 179
 180   if (verifyModule(*SafeModule) || verifyModule(*TestModule)) {
 181     std::cerr << "Bugpoint has a bug, an corrupted a module!!\n";
 182     abort();
 183   }
 184
 185   DEBUG(std::cerr << "Safe module:\n";
 186         typedef Module::iterator MI;
 187         typedef Module::giterator MGI;
 188
 189         for (MI I = SafeModule->begin(), E = SafeModule->end(); I != E; ++I)
 190           if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
 191         for (MGI I = SafeModule->gbegin(), E = SafeModule->gend(); I!=E; ++I)
 192           if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
 193
 194         std::cerr << "Test module:\n";
 195         for (MI I = TestModule->begin(), E = TestModule->end(); I != E; ++I)
 196           if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
 197         for (MGI I=TestModule->gbegin(),E = TestModule->gend(); I!= E; ++I)
 198           if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
 199         );
 200
 201   // Write out the bytecode to be sent to CBE
 202   std::string SafeModuleBC = getUniqueFilename("bugpoint.safe.bc");
 203
 204   if (BD.writeProgramToFile(SafeModuleBC, SafeModule)) {
 205     std::cerr << "Error writing bytecode to `" << SafeModuleBC << "'\nExiting.";
 206     exit(1);
 207   }
 208
 209   // Remove all functions from the Test module EXCEPT for the ones specified in
 210   // Funcs.  We know which ones these are because they are non-external in
 211   // ToOptimize, but external in ToNotOptimize.
 212   //
 213   for (Module::iterator I = TestModule->begin(), E = TestModule->end();I!=E;++I)
 214     if (!I->isExternal()) {
 215       Function *TNOF = SafeModule->getFunction(I->getName(),
 216                                                I->getFunctionType());
 217       assert(TNOF && "Function doesn't exist in ToNotOptimize module??");
 218       if (!TNOF->isExternal())
 219         DeleteFunctionBody(I);
 220     }
 221
 222   std::string TestModuleBC = getUniqueFilename("bugpoint.test.bc");
 223   if (verifyModule(*TestModule)) {
 224     std::cerr << "Bytecode file corrupted!\n";
 225     exit(1);
 226   }
 227
 228   // Clean up the modules, removing extra cruft that we don't need anymore...
 229   SafeModule = BD.performFinalCleanups(SafeModule);
 230   TestModule = BD.performFinalCleanups(TestModule);
 231
 232   if (BD.writeProgramToFile(TestModuleBC, TestModule)) {
 233     std::cerr << "Error writing bytecode to `" << SafeModuleBC << "'\nExiting.";
 234     exit(1);
 235   }
 236
 237   // Make a shared library
 238   std::string SharedObject = BD.compileSharedObject(SafeModuleBC);
 239
 240   delete SafeModule;
 241   delete TestModule;
 242
 243   // Run the code generator on the `Test' code, loading the shared library.
 244   // The function returns whether or not the new output differs from reference.
 245   int Result = BD.diffProgram(TestModuleBC, SharedObject, false);
 246
 247   if (Result)
 248     std::cerr << ": still failing!\n";
 249   else
 250     std::cerr << ": didn't fail.\n";
 251
 252   if (KeepFiles) {
 253     std::cout << "You can reproduce the problem with the command line: \n";
 254     if (BD.isExecutingJIT()) {
 255       std::cout << "  lli -load " << SharedObject << " " << TestModuleBC;
 256     } else {
 257       std::cout << "  llc " << TestModuleBC << " -o " << TestModuleBC << ".s\n";
 258       std::cout << "  gcc " << SharedObject << " " << TestModuleBC
 259                 << ".s -o " << TestModuleBC << ".exe -Wl,-R.\n";
 260       std::cout << "  " << TestModuleBC << ".exe";
 261     }
 262     for (unsigned i=0, e = InputArgv.size(); i != e; ++i)
 263       std::cout << " " << InputArgv[i];
 264     std::cout << "\n";
 265     std::cout << "The shared object was created with:\n  llvm-dis -c "
 266               << SafeModuleBC << " -o temporary.c\n"
 267               << "  gcc -xc temporary.c -O2 -o " << SharedObject
 268 #if defined(sparc) || defined(__sparc__) || defined(__sparcv9)
 269               << " -G"            // Compile a shared library, `-G' for Sparc
 270 #else
 271               << " -shared"       // `-shared' for Linux/X86, maybe others
 272 #endif
 273               << " -fno-strict-aliasing\n";
 274   } else {
 275     removeFile(TestModuleBC);
 276     removeFile(SafeModuleBC);
 277     removeFile(SharedObject);
 278   }
 279   return Result;
 280 }
 281
 282 namespace {
 283   struct Disambiguator {
 284     std::set<std::string>  SymbolNames;
 285     std::set<GlobalValue*> Symbols;
 286     uint64_t uniqueCounter;
 287     bool externalOnly;
 288   public:
 289     Disambiguator() : uniqueCounter(0), externalOnly(true) {}
 290     void setExternalOnly(bool value) { externalOnly = value; }
 291     void add(GlobalValue &V) {
 292       // If we're only processing externals and this isn't external, bail
 293       if (externalOnly && !V.isExternal()) return;
 294       // If we're already processed this symbol, don't add it again
 295       if (Symbols.count(&V) != 0) return;
 296       // Ignore intrinsic functions
 297       if (Function *F = dyn_cast<Function>(&V))
 298         if (F->getIntrinsicID() != 0)
 299           return;
 300
 301       std::string SymName = V.getName();
 302
 303       // Use the Mangler facility to make symbol names that will be valid in
 304       // shared objects.
 305       SymName = Mangler::makeNameProper(SymName);
 306       V.setName(SymName);
 307
 308       if (SymbolNames.count(SymName) == 0) {
 309         DEBUG(std::cerr << "Disambiguator: adding " << SymName
 310                         << ", no conflicts.\n");
 311         SymbolNames.insert(SymName);
 312       } else {
 313         // Mangle name before adding
 314         std::string newName;
 315         do {
 316           newName = SymName + "_" + utostr(uniqueCounter);
 317           if (SymbolNames.count(newName) == 0) break;
 318           else ++uniqueCounter;
 319         } while (1);
 320         //while (SymbolNames.count(V->getName()+utostr(uniqueCounter++))==0);
 321         DEBUG(std::cerr << "Disambiguator: conflict: " << SymName
 322                         << ", adding: " << newName << "\n");
 323         V.setName(newName);
 324         SymbolNames.insert(newName);
 325       }
 326       Symbols.insert(&V);
 327     }
 328   };
 329 }
 330
 331 void DisambiguateGlobalSymbols(Module *M) {
 332   // First, try not to cause collisions by minimizing chances of renaming an
 333   // already-external symbol, so take in external globals and functions as-is.
 334   Disambiguator D;
 335   DEBUG(std::cerr << "Disambiguating globals (external-only)\n");
 336   for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) D.add(*I);
 337   DEBUG(std::cerr << "Disambiguating functions (external-only)\n");
 338   for (Module::iterator  I = M->begin(),  E = M->end();  I != E; ++I) D.add(*I);
 339
 340   // Now just rename functions and globals as necessary, keeping what's already
 341   // in the set unique.
 342   D.setExternalOnly(false);
 343   DEBUG(std::cerr << "Disambiguating globals\n");
 344   for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) D.add(*I);
 345   DEBUG(std::cerr << "Disambiguating globals\n");
 346   for (Module::iterator  I = M->begin(),  E = M->end();  I != E; ++I) D.add(*I);
 347 }
 348
 349
 350 bool BugDriver::debugCodeGenerator() {
 351   // See if we can pin down which functions are being miscompiled...
 352   //First, build a list of all of the non-external functions in the program.
 353   std::vector<Function*> MisCodegenFunctions;
 354   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 355     if (!I->isExternal())
 356       MisCodegenFunctions.push_back(I);
 357
 358   // If we are executing the JIT, we *must* keep the function `main' in the
 359   // module that is passed in, and not the shared library. However, we still
 360   // want to be able to debug the `main' function alone. Thus, we create a new
 361   // function `main' which just calls the old one.
 362   if (isExecutingJIT()) {
 363     // Get the `main' function
 364     Function *oldMain = Program->getNamedFunction("main");
 365     assert(oldMain && "`main' function not found in program!");
 366     // Rename it
 367     oldMain->setName("llvm_old_main");
 368     // Create a NEW `main' function with same type
 369     Function *newMain = new Function(oldMain->getFunctionType(),
 370                                      GlobalValue::ExternalLinkage,
 371                                      "main", Program);
 372     // Call the old main function and return its result
 373     BasicBlock *BB = new BasicBlock("entry", newMain);
 374     std::vector<Value*> args;
 375     for (Function::aiterator I = newMain->abegin(), E = newMain->aend(),
 376            OI = oldMain->abegin(); I != E; ++I, ++OI) {
 377       I->setName(OI->getName());    // Copy argument names from oldMain
 378       args.push_back(I);
 379     }
 380     CallInst *call = new CallInst(oldMain, args);
 381     BB->getInstList().push_back(call);
 382
 383     // if the type of old function wasn't void, return value of call
 384     ReturnInst *ret;
 385     if (oldMain->getReturnType() != Type::VoidTy) {
 386       ret = new ReturnInst(call);
 387     } else {
 388       ret = new ReturnInst();
 389     }
 390
 391     // Add the return instruction to the BasicBlock
 392     BB->getInstList().push_back(ret);
 393   }
 394
 395   DisambiguateGlobalSymbols(Program);
 396
 397   // Do the reduction...
 398   if (!ReduceMisCodegenFunctions(*this).reduceList(MisCodegenFunctions)) {
 399     std::cerr << "*** Execution matches reference output! "
 400               << "bugpoint can't help you with your problem!\n";
 401     return false;
 402   }
 403
 404   std::cout << "\n*** The following functions are being miscompiled: ";
 405   PrintFunctionList(MisCodegenFunctions);
 406   std::cout << "\n";
 407
 408   // Output a bunch of bytecode files for the user...
 409   ReduceMisCodegenFunctions(*this).TestFuncs(MisCodegenFunctions, true);
 410
 411   return false;
 412 }
 413
 414 } // End llvm namespace