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