1 //===- CodeGeneratorBug.cpp - Debug code generation bugs ------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file implements program code generation debugging support.
12 //===----------------------------------------------------------------------===//
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"
36 extern cl::list<std::string> InputArgv;
38 class ReduceMisCodegenFunctions : public ListReducer<Function*> {
41 ReduceMisCodegenFunctions(BugDriver &bd) : BD(bd) {}
43 virtual TestResult doTest(std::vector<Function*> &Prefix,
44 std::vector<Function*> &Suffix) {
45 if (!Prefix.empty() && TestFuncs(Prefix))
47 if (!Suffix.empty() && TestFuncs(Suffix))
52 bool TestFuncs(const std::vector<Function*> &CodegenTest,
53 bool KeepFiles = false);
57 bool ReduceMisCodegenFunctions::TestFuncs(const std::vector<Function*> &Funcs,
59 std::cout << "Testing functions: ";
60 BD.PrintFunctionList(Funcs);
63 // Clone the module for the two halves of the program we want.
64 Module *SafeModule = CloneModule(BD.Program);
66 // Make sure functions & globals are all external so that linkage
67 // between the two modules will work.
68 for (Module::iterator I = SafeModule->begin(), E = SafeModule->end();I!=E;++I)
69 I->setLinkage(GlobalValue::ExternalLinkage);
70 for (Module::giterator I=SafeModule->gbegin(),E = SafeModule->gend();I!=E;++I)
71 I->setLinkage(GlobalValue::ExternalLinkage);
73 Module *TestModule = CloneModule(SafeModule);
75 // Make sure global initializers exist only in the safe module (CBE->.so)
76 for (Module::giterator I=TestModule->gbegin(),E = TestModule->gend();I!=E;++I)
77 I->setInitializer(0); // Delete the initializer to make it external
79 // Remove the Test functions from the Safe module
80 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
81 Function *TNOF = SafeModule->getFunction(Funcs[i]->getName(),
82 Funcs[i]->getFunctionType());
83 DEBUG(std::cerr << "Removing function " << Funcs[i]->getName() << "\n");
84 assert(TNOF && "Function doesn't exist in module!");
85 DeleteFunctionBody(TNOF); // Function is now external in this module!
88 // Remove the Safe functions from the Test module
89 for (Module::iterator I=TestModule->begin(),E=TestModule->end(); I!=E; ++I) {
90 bool funcFound = false;
91 for (std::vector<Function*>::const_iterator F=Funcs.begin(),Fe=Funcs.end();
93 if (I->getName() == (*F)->getName()) funcFound = true;
95 if (!funcFound && !(BD.isExecutingJIT() && I->getName() == "main"))
96 DeleteFunctionBody(I);
99 // This is only applicable if we are debugging the JIT:
100 // Find all external functions in the Safe modules that are actually used
101 // (called or taken address of), and make them call the JIT wrapper instead
102 if (BD.isExecutingJIT()) {
103 // Must delete `main' from Safe module if it has it
104 Function *safeMain = SafeModule->getNamedFunction("main");
105 assert(safeMain && "`main' function not found in safe module!");
106 DeleteFunctionBody(safeMain);
108 // Add an external function "getPointerToNamedFunction" that JIT provides
109 // Prototype: void *getPointerToNamedFunction(const char* Name)
110 std::vector<const Type*> Params;
111 Params.push_back(PointerType::get(Type::SByteTy)); // std::string&
112 FunctionType *resolverTy = FunctionType::get(PointerType::get(Type::VoidTy),
113 Params, false /* isVarArg */);
114 Function *resolverFunc = new Function(resolverTy,
115 GlobalValue::ExternalLinkage,
116 "getPointerToNamedFunction",
119 // Use the function we just added to get addresses of functions we need
120 // Iterate over the global declarations in the Safe module
121 for (Module::iterator F=SafeModule->begin(),E=SafeModule->end(); F!=E; ++F){
122 if (F->isExternal() && !F->use_empty() && &*F != resolverFunc &&
123 F->getIntrinsicID() == 0 /* ignore intrinsics */ &&
124 // Don't forward functions which are external in the test module too.
125 !TestModule->getNamedFunction(F->getName())->isExternal()) {
126 // If it has a non-zero use list,
127 // 1. Add a string constant with its name to the global file
128 // The correct type is `const [ NUM x sbyte ]' where NUM is length of
130 const std::string &Name = F->getName();
131 GlobalVariable *funcName =
132 new GlobalVariable(ArrayType::get(Type::SByteTy, Name.length()+1),
133 true /* isConstant */,
134 GlobalValue::InternalLinkage,
135 ConstantArray::get(Name),
139 // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an
140 // sbyte* so it matches the signature of the resolver function.
141 std::vector<Constant*> GEPargs(2, Constant::getNullValue(Type::LongTy));
143 // 3. Replace all uses of `func' with calls to resolver by:
144 // (a) Iterating through the list of uses of this function
145 // (b) Insert a cast instruction in front of each use
146 // (c) Replace use of old call with new call
148 // GetElementPtr *funcName, ulong 0, ulong 0
150 ConstantExpr::getGetElementPtr(ConstantPointerRef::get(funcName),
152 std::vector<Value*> ResolverArgs;
153 ResolverArgs.push_back(GEP);
155 // Insert code at the beginning of the function
156 while (!F->use_empty())
157 if (Instruction *Inst = dyn_cast<Instruction>(F->use_back())) {
158 // call resolver(GetElementPtr...)
159 CallInst *resolve = new CallInst(resolverFunc, ResolverArgs,
161 // cast the result from the resolver to correctly-typed function
162 CastInst *castResolver =
163 new CastInst(resolve, PointerType::get(F->getFunctionType()),
164 "resolverCast", Inst);
165 // actually use the resolved function
166 Inst->replaceUsesOfWith(F, castResolver);
168 // FIXME: need to take care of cases where a function is used that
169 // is not an instruction, e.g. global variable initializer...
170 std::cerr << "Non-instruction is using an external function!\n";
177 if (verifyModule(*SafeModule) || verifyModule(*TestModule)) {
178 std::cerr << "Bugpoint has a bug, an corrupted a module!!\n";
182 DEBUG(std::cerr << "Safe module:\n";
183 typedef Module::iterator MI;
184 typedef Module::giterator MGI;
186 for (MI I = SafeModule->begin(), E = SafeModule->end(); I != E; ++I)
187 if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
188 for (MGI I = SafeModule->gbegin(), E = SafeModule->gend(); I!=E; ++I)
189 if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
191 std::cerr << "Test module:\n";
192 for (MI I = TestModule->begin(), E = TestModule->end(); I != E; ++I)
193 if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
194 for (MGI I=TestModule->gbegin(),E = TestModule->gend(); I!= E; ++I)
195 if (!I->isExternal()) std::cerr << "\t" << I->getName() << "\n";
198 // Write out the bytecode to be sent to CBE
199 std::string SafeModuleBC = getUniqueFilename("bugpoint.safe.bc");
201 if (BD.writeProgramToFile(SafeModuleBC, SafeModule)) {
202 std::cerr << "Error writing bytecode to `" << SafeModuleBC << "'\nExiting.";
206 // Remove all functions from the Test module EXCEPT for the ones specified in
207 // Funcs. We know which ones these are because they are non-external in
208 // ToOptimize, but external in ToNotOptimize.
210 for (Module::iterator I = TestModule->begin(), E = TestModule->end();I!=E;++I)
211 if (!I->isExternal()) {
212 Function *TNOF = SafeModule->getFunction(I->getName(),
213 I->getFunctionType());
214 assert(TNOF && "Function doesn't exist in ToNotOptimize module??");
215 if (!TNOF->isExternal())
216 DeleteFunctionBody(I);
219 std::string TestModuleBC = getUniqueFilename("bugpoint.test.bc");
220 if (verifyModule(*TestModule)) {
221 std::cerr << "Bytecode file corrupted!\n";
225 // Clean up the modules, removing extra cruft that we don't need anymore...
226 SafeModule = BD.performFinalCleanups(SafeModule);
227 TestModule = BD.performFinalCleanups(TestModule);
229 if (BD.writeProgramToFile(TestModuleBC, TestModule)) {
230 std::cerr << "Error writing bytecode to `" << SafeModuleBC << "'\nExiting.";
234 // Make a shared library
235 std::string SharedObject = BD.compileSharedObject(SafeModuleBC);
240 // Run the code generator on the `Test' code, loading the shared library.
241 // The function returns whether or not the new output differs from reference.
242 int Result = BD.diffProgram(TestModuleBC, SharedObject, false);
245 std::cerr << ": still failing!\n";
247 std::cerr << ": didn't fail.\n";
250 std::cout << "You can reproduce the problem with the command line: \n";
251 if (BD.isExecutingJIT()) {
252 std::cout << " lli -load " << SharedObject << " " << TestModuleBC;
254 std::cout << " llc " << TestModuleBC << " -o " << TestModuleBC << ".s\n";
255 std::cout << " gcc " << SharedObject << " " << TestModuleBC
256 << ".s -o " << TestModuleBC << ".exe -Wl,-R.\n";
257 std::cout << " " << TestModuleBC << ".exe";
259 for (unsigned i=0, e = InputArgv.size(); i != e; ++i)
260 std::cout << " " << InputArgv[i];
262 std::cout << "The shared object was created with:\n llvm-dis -c "
263 << SafeModuleBC << " -o temporary.c\n"
264 << " gcc -xc temporary.c -O2 -o " << SharedObject
265 #if defined(sparc) || defined(__sparc__) || defined(__sparcv9)
266 << " -G" // Compile a shared library, `-G' for Sparc
268 << " -shared" // `-shared' for Linux/X86, maybe others
270 << " -fno-strict-aliasing\n";
272 removeFile(TestModuleBC);
273 removeFile(SafeModuleBC);
274 removeFile(SharedObject);
280 struct Disambiguator {
281 std::set<std::string> SymbolNames;
282 std::set<GlobalValue*> Symbols;
283 uint64_t uniqueCounter;
286 Disambiguator() : uniqueCounter(0), externalOnly(true) {}
287 void setExternalOnly(bool value) { externalOnly = value; }
288 void add(GlobalValue &V) {
289 // If we're only processing externals and this isn't external, bail
290 if (externalOnly && !V.isExternal()) return;
291 // If we're already processed this symbol, don't add it again
292 if (Symbols.count(&V) != 0) return;
293 // Ignore intrinsic functions
294 if (Function *F = dyn_cast<Function>(&V))
295 if (F->getIntrinsicID() != 0)
298 std::string SymName = V.getName();
300 // Use the Mangler facility to make symbol names that will be valid in
302 SymName = Mangler::makeNameProper(SymName);
305 if (SymbolNames.count(SymName) == 0) {
306 DEBUG(std::cerr << "Disambiguator: adding " << SymName
307 << ", no conflicts.\n");
308 SymbolNames.insert(SymName);
310 // Mangle name before adding
313 newName = SymName + "_" + utostr(uniqueCounter);
314 if (SymbolNames.count(newName) == 0) break;
315 else ++uniqueCounter;
317 //while (SymbolNames.count(V->getName()+utostr(uniqueCounter++))==0);
318 DEBUG(std::cerr << "Disambiguator: conflict: " << SymName
319 << ", adding: " << newName << "\n");
321 SymbolNames.insert(newName);
328 void DisambiguateGlobalSymbols(Module *M) {
329 // First, try not to cause collisions by minimizing chances of renaming an
330 // already-external symbol, so take in external globals and functions as-is.
332 DEBUG(std::cerr << "Disambiguating globals (external-only)\n");
333 for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) D.add(*I);
334 DEBUG(std::cerr << "Disambiguating functions (external-only)\n");
335 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) D.add(*I);
337 // Now just rename functions and globals as necessary, keeping what's already
338 // in the set unique.
339 D.setExternalOnly(false);
340 DEBUG(std::cerr << "Disambiguating globals\n");
341 for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) D.add(*I);
342 DEBUG(std::cerr << "Disambiguating globals\n");
343 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) D.add(*I);
347 bool BugDriver::debugCodeGenerator() {
348 // See if we can pin down which functions are being miscompiled...
349 //First, build a list of all of the non-external functions in the program.
350 std::vector<Function*> MisCodegenFunctions;
351 for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
352 if (!I->isExternal())
353 MisCodegenFunctions.push_back(I);
355 // If we are executing the JIT, we *must* keep the function `main' in the
356 // module that is passed in, and not the shared library. However, we still
357 // want to be able to debug the `main' function alone. Thus, we create a new
358 // function `main' which just calls the old one.
359 if (isExecutingJIT()) {
360 // Get the `main' function
361 Function *oldMain = Program->getNamedFunction("main");
362 assert(oldMain && "`main' function not found in program!");
364 oldMain->setName("llvm_old_main");
365 // Create a NEW `main' function with same type
366 Function *newMain = new Function(oldMain->getFunctionType(),
367 GlobalValue::ExternalLinkage,
369 // Call the old main function and return its result
370 BasicBlock *BB = new BasicBlock("entry", newMain);
371 std::vector<Value*> args;
372 for (Function::aiterator I = newMain->abegin(), E = newMain->aend(),
373 OI = oldMain->abegin(); I != E; ++I, ++OI) {
374 I->setName(OI->getName()); // Copy argument names from oldMain
377 CallInst *call = new CallInst(oldMain, args);
378 BB->getInstList().push_back(call);
380 // if the type of old function wasn't void, return value of call
382 if (oldMain->getReturnType() != Type::VoidTy) {
383 ret = new ReturnInst(call);
385 ret = new ReturnInst();
388 // Add the return instruction to the BasicBlock
389 BB->getInstList().push_back(ret);
392 DisambiguateGlobalSymbols(Program);
394 // Do the reduction...
395 if (!ReduceMisCodegenFunctions(*this).reduceList(MisCodegenFunctions)) {
396 std::cerr << "*** Execution matches reference output! "
397 << "bugpoint can't help you with your problem!\n";
401 std::cout << "\n*** The following functions are being miscompiled: ";
402 PrintFunctionList(MisCodegenFunctions);
405 // Output a bunch of bytecode files for the user...
406 ReduceMisCodegenFunctions(*this).TestFuncs(MisCodegenFunctions, true);