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