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 using namespace llvm;
  34
  35 namespace llvm {
  36   extern cl::list<std::string> InputArgv;
  37
  38   class ReduceMisCodegenFunctions : public ListReducer<Function*> {
  39     BugDriver &BD;
  40   public:
  41     ReduceMisCodegenFunctions(BugDriver &bd) : BD(bd) {}
  42
  43     virtual TestResult doTest(std::vector<Function*> &Prefix,
  44                               std::vector<Function*> &Suffix) {
  45       if (!Prefix.empty() && TestFuncs(Prefix))
  46         return KeepPrefix;
  47       if (!Suffix.empty() && TestFuncs(Suffix))
  48         return KeepSuffix;
  49       return NoFailure;
  50     }
  51
  52     bool TestFuncs(const std::vector<Function*> &CodegenTest,
  53                    bool KeepFiles = false);
  54   };
  55 }
  56
  57 bool ReduceMisCodegenFunctions::TestFuncs(const std::vector<Function*> &Funcs,
  58                                           bool KeepFiles) {
  59   std::cout << "Testing functions: ";
  60   PrintFunctionList(Funcs);
  61   std::cout << "\t";
  62
  63   // Clone the module for the two halves of the program we want.
  64   Module *SafeModule = CloneModule(BD.getProgram());
  65
  66   // The JIT must extract the 'main' function.
  67   std::vector<Function*> RealFuncs(Funcs);
  68   if (BD.isExecutingJIT()) {
  69     if (Function *F = BD.Program->getMainFunction())
  70       RealFuncs.push_back(F);
  71   }
  72   Module *TestModule = SplitFunctionsOutOfModule(SafeModule, RealFuncs);
  73
  74   // This is only applicable if we are debugging the JIT:
  75   // Find all external functions in the Safe modules that are actually used
  76   // (called or taken address of), and make them call the JIT wrapper instead
  77   if (BD.isExecutingJIT()) {
  78     // Must delete `main' from Safe module if it has it
  79     Function *safeMain = SafeModule->getNamedFunction("main");
  80     assert(safeMain && "`main' function not found in safe module!");
  81     DeleteFunctionBody(safeMain);
  82
  83     // Add an external function "getPointerToNamedFunction" that JIT provides
  84     // Prototype: void *getPointerToNamedFunction(const char* Name)
  85     std::vector<const Type*> Params;
  86     Params.push_back(PointerType::get(Type::SByteTy)); // std::string&
  87     FunctionType *resolverTy = FunctionType::get(PointerType::get(Type::VoidTy),
  88                                                  Params, false /* isVarArg */);
  89     Function *resolverFunc = new Function(resolverTy,
  90                                           GlobalValue::ExternalLinkage,
  91                                           "getPointerToNamedFunction",
  92                                           SafeModule);
  93
  94     // Use the function we just added to get addresses of functions we need
  95     // Iterate over the global declarations in the Safe module
  96     for (Module::iterator F=SafeModule->begin(),E=SafeModule->end(); F!=E; ++F){
  97       if (F->isExternal() && !F->use_empty() && &*F != resolverFunc &&
  98           F->getIntrinsicID() == 0 /* ignore intrinsics */ &&
  99           // Don't forward functions which are external in the test module too.
 100           !TestModule->getNamedFunction(F->getName())->isExternal()) {
 101         // If it has a non-zero use list,
 102         // 1. Add a string constant with its name to the global file
 103         Constant *InitArray = ConstantArray::get(F->getName());
 104         GlobalVariable *funcName =
 105           new GlobalVariable(InitArray->getType(), true /* isConstant */,
 106                              GlobalValue::InternalLinkage, InitArray,
 107                              F->getName() + "_name", SafeModule);
 108
 109         // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an
 110         // sbyte* so it matches the signature of the resolver function.
 111         std::vector<Constant*> GEPargs(2, Constant::getNullValue(Type::IntTy));
 112
 113         // 3. Replace all uses of `func' with calls to resolver by:
 114         // (a) Iterating through the list of uses of this function
 115         // (b) Insert a cast instruction in front of each use
 116         // (c) Replace use of old call with new call
 117
 118         // GetElementPtr *funcName, ulong 0, ulong 0
 119         Value *GEP =
 120           ConstantExpr::getGetElementPtr(ConstantPointerRef::get(funcName),
 121                                          GEPargs);
 122         std::vector<Value*> ResolverArgs;
 123         ResolverArgs.push_back(GEP);
 124
 125         // Insert code at the beginning of the function
 126         while (!F->use_empty())
 127           if (Instruction *Inst = dyn_cast<Instruction>(F->use_back())) {
 128             // call resolver(GetElementPtr...)
 129             CallInst *resolve = new CallInst(resolverFunc, ResolverArgs,
 130                                              "resolver", Inst);
 131             // cast the result from the resolver to correctly-typed function
 132             CastInst *castResolver =
 133               new CastInst(resolve, PointerType::get(F->getFunctionType()),
 134                            "resolverCast", Inst);
 135             // actually use the resolved function
 136             Inst->replaceUsesOfWith(F, castResolver);
 137           } else {
 138             // FIXME: need to take care of cases where a function is used by
 139             // something other than an instruction; e.g., global variable
 140             // initializers and constant expressions.
 141             std::cerr << "UNSUPPORTED: Non-instruction is using an external "
 142                       << "function, " << F->getName() << "().\n";
 143             abort();
 144           }
 145       }
 146     }
 147   }
 148
 149   if (verifyModule(*SafeModule) || verifyModule(*TestModule)) {
 150     std::cerr << "Bugpoint has a bug, an corrupted a module!!\n";
 151     abort();
 152   }
 153
 154   // Remove all functions from the Test module EXCEPT for the ones specified in
 155   // Funcs.  We know which ones these are because they are non-external in
 156   // ToOptimize, but external in ToNotOptimize.
 157   //
 158   for (Module::iterator I = TestModule->begin(), E = TestModule->end();I!=E;++I)
 159     if (!I->isExternal()) {
 160       Function *TNOF = SafeModule->getFunction(I->getName(),
 161                                                I->getFunctionType());
 162       assert(TNOF && "Function doesn't exist in ToNotOptimize module??");
 163       if (!TNOF->isExternal())
 164         DeleteFunctionBody(I);
 165     }
 166
 167   // Clean up the modules, removing extra cruft that we don't need anymore...
 168   TestModule = BD.performFinalCleanups(TestModule);
 169
 170   std::string TestModuleBC = getUniqueFilename("bugpoint.test.bc");
 171   if (BD.writeProgramToFile(TestModuleBC, TestModule)) {
 172     std::cerr << "Error writing bytecode to `" << TestModuleBC << "'\nExiting.";
 173     exit(1);
 174   }
 175   delete TestModule;
 176
 177   // Make the shared library
 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   std::string SharedObject = BD.compileSharedObject(SafeModuleBC);
 185   delete SafeModule;
 186
 187   // Run the code generator on the `Test' code, loading the shared library.
 188   // The function returns whether or not the new output differs from reference.
 189   int Result = BD.diffProgram(TestModuleBC, SharedObject, false);
 190
 191   if (Result)
 192     std::cerr << ": still failing!\n";
 193   else
 194     std::cerr << ": didn't fail.\n";
 195
 196   if (KeepFiles) {
 197     std::cout << "You can reproduce the problem with the command line: \n";
 198     if (BD.isExecutingJIT()) {
 199       std::cout << "  lli -load " << SharedObject << " " << TestModuleBC;
 200     } else {
 201       std::cout << "  llc " << TestModuleBC << " -o " << TestModuleBC << ".s\n";
 202       std::cout << "  gcc " << SharedObject << " " << TestModuleBC
 203                 << ".s -o " << TestModuleBC << ".exe -Wl,-R.\n";
 204       std::cout << "  " << TestModuleBC << ".exe";
 205     }
 206     for (unsigned i=0, e = InputArgv.size(); i != e; ++i)
 207       std::cout << " " << InputArgv[i];
 208     std::cout << "\n";
 209     std::cout << "The shared object was created with:\n  llc -march=c "
 210               << SafeModuleBC << " -o temporary.c\n"
 211               << "  gcc -xc temporary.c -O2 -o " << SharedObject
 212 #if defined(sparc) || defined(__sparc__) || defined(__sparcv9)
 213               << " -G"            // Compile a shared library, `-G' for Sparc
 214 #else
 215               << " -shared"       // `-shared' for Linux/X86, maybe others
 216 #endif
 217               << " -fno-strict-aliasing\n";
 218   } else {
 219     removeFile(TestModuleBC);
 220     removeFile(SafeModuleBC);
 221     removeFile(SharedObject);
 222   }
 223   return Result;
 224 }
 225
 226 static void DisambiguateGlobalSymbols(Module *M) {
 227   // Try not to cause collisions by minimizing chances of renaming an
 228   // already-external symbol, so take in external globals and functions as-is.
 229   // The code should work correctly without disambiguation (assuming the same
 230   // mangler is used by the two code generators), but having symbols with the
 231   // same name causes warnings to be emitted by the code generator.
 232   Mangler Mang(*M);
 233   DEBUG(std::cerr << "Disambiguating globals (external-only)\n");
 234   for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I)
 235     I->setName(Mang.getValueName(I));
 236   DEBUG(std::cerr << "Disambiguating functions (external-only)\n");
 237   for (Module::iterator  I = M->begin(),  E = M->end();  I != E; ++I)
 238     I->setName(Mang.getValueName(I));
 239 }
 240
 241
 242 bool BugDriver::debugCodeGenerator() {
 243   if ((void*)cbe == (void*)Interpreter) {
 244     std::string Result = executeProgramWithCBE("bugpoint.cbe.out");
 245     std::cout << "\n*** The C backend cannot match the reference diff, but it "
 246               << "is used as the 'known good'\n    code generator, so I can't"
 247               << " debug it.  Perhaps you have a front-end problem?\n    As a"
 248               << " sanity check, I left the result of executing the program "
 249               << "with the C backend\n    in this file for you: '"
 250               << Result << "'.\n";
 251     return true;
 252   }
 253
 254   // See if we can pin down which functions are being miscompiled...
 255   // First, build a list of all of the non-external functions in the program.
 256   std::vector<Function*> MisCodegenFunctions;
 257   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 258     if (!I->isExternal())
 259       MisCodegenFunctions.push_back(I);
 260
 261   // If we are executing the JIT, we *must* keep the function `main' in the
 262   // module that is passed in, and not the shared library. However, we still
 263   // want to be able to debug the `main' function alone. Thus, we create a new
 264   // function `main' which just calls the old one.
 265   if (isExecutingJIT()) {
 266     // Get the `main' function
 267     Function *oldMain = Program->getNamedFunction("main");
 268     assert(oldMain && "`main' function not found in program!");
 269     // Rename it
 270     oldMain->setName("llvm_old_main");
 271     // Create a NEW `main' function with same type
 272     Function *newMain = new Function(oldMain->getFunctionType(),
 273                                      GlobalValue::ExternalLinkage,
 274                                      "main", Program);
 275     // Call the old main function and return its result
 276     BasicBlock *BB = new BasicBlock("entry", newMain);
 277     std::vector<Value*> args;
 278     for (Function::aiterator I = newMain->abegin(), E = newMain->aend(),
 279            OI = oldMain->abegin(); I != E; ++I, ++OI) {
 280       I->setName(OI->getName());    // Copy argument names from oldMain
 281       args.push_back(I);
 282     }
 283     CallInst *call = new CallInst(oldMain, args);
 284     BB->getInstList().push_back(call);
 285
 286     // if the type of old function wasn't void, return value of call
 287     if (oldMain->getReturnType() != Type::VoidTy) {
 288       new ReturnInst(call, BB);
 289     } else {
 290       new ReturnInst(0, BB);
 291     }
 292   }
 293
 294   DisambiguateGlobalSymbols(Program);
 295
 296   // Do the reduction...
 297   if (!ReduceMisCodegenFunctions(*this).reduceList(MisCodegenFunctions)) {
 298     std::cerr << "*** Execution matches reference output! "
 299               << "bugpoint can't help you with your problem!\n";
 300     return false;
 301   }
 302
 303   std::cout << "\n*** The following functions are being miscompiled: ";
 304   PrintFunctionList(MisCodegenFunctions);
 305   std::cout << "\n";
 306
 307   // Output a bunch of bytecode files for the user...
 308   ReduceMisCodegenFunctions(*this).TestFuncs(MisCodegenFunctions, true);
 309
 310   return false;
 311 }