tools/bugpoint/CodeGeneratorBug.cpp

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