1 //===- CodeGeneratorBug.cpp - Debug code generation bugs ------------------===//
3 // This file implements program code generation debugging support.
5 //===----------------------------------------------------------------------===//
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"
27 class ReduceMisCodegenFunctions : public ListReducer<Function*> {
30 ReduceMisCodegenFunctions(BugDriver &bd) : BD(bd) {}
32 virtual TestResult doTest(std::vector<Function*> &Prefix,
33 std::vector<Function*> &Suffix) {
34 if (!Prefix.empty() && TestFuncs(Prefix))
36 if (!Suffix.empty() && TestFuncs(Suffix))
41 bool TestFuncs(const std::vector<Function*> &CodegenTest,
42 bool KeepFiles = false);
44 void DisambiguateGlobalSymbols(Module *M);
48 bool ReduceMisCodegenFunctions::TestFuncs(const std::vector<Function*> &Funcs,
51 DEBUG(std::cerr << "Test functions are:\n");
52 for (std::vector<Function*>::const_iterator I = Funcs.begin(),E = Funcs.end();
54 DEBUG(std::cerr << "\t" << (*I)->getName() << "\n");
56 // Clone the module for the two halves of the program we want.
57 Module *SafeModule = CloneModule(BD.Program);
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);
66 DisambiguateGlobalSymbols(SafeModule);
67 Module *TestModule = CloneModule(SafeModule);
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
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!
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();
86 if (I->getName() == (*F)->getName()) funcFound = true;
88 if (!funcFound && !(BD.isExecutingJIT() && I->getName() == "main"))
89 DeleteFunctionBody(I);
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);
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,
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
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),
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);
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
142 // Insert code at the beginning of the function
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
148 ConstantExpr::getGetElementPtr(ConstantPointerRef::get(funcName),
150 std::vector<Value*> ResolverArgs;
151 ResolverArgs.push_back(GEP);
152 // call resolver(GetElementPtr...)
153 CallInst *resolve = new CallInst(resolverFunc, ResolverArgs,
155 // cast the result from the resolver to correctly-typed function
156 CastInst *castResolver =
157 new CastInst(resolve, PointerType::get(F->getFunctionType()),
159 // actually use the resolved function
160 Inst->replaceUsesOfWith(F, castResolver);
162 //BasicBlock::iterator ii(Inst);
163 //ReplaceInstWithValue(Inst->getParent()->getInstList(),
164 // ii, ResolverResult);
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");
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");
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";
189 if (BD.writeProgramToFile(SafeModuleBC, SafeModule)) {
190 std::cerr << "Error writing bytecode to `" << SafeModuleBC << "'\nExiting.";
194 // Make a shared library
195 std::string SharedObject;
196 BD.compileSharedObject(SafeModuleBC, SharedObject);
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.
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);
211 std::string TestModuleBC = getUniqueFilename("bugpoint.test.bc");
212 if (verifyModule(*TestModule)) {
213 std::cerr << "Bytecode file corrupted!\n";
216 if (BD.writeProgramToFile(TestModuleBC, TestModule)) {
217 std::cerr << "Error writing bytecode to `" << SafeModuleBC << "'\nExiting.";
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);
228 std::cout << "You can reproduce the problem with the command line: \n"
229 << "lli (or llc) -load " << SharedObject << " " << TestModuleBC
232 removeFile(TestModuleBC);
233 removeFile(SafeModuleBC);
234 removeFile(SharedObject);
240 struct Disambiguator {
241 std::set<std::string> SymbolNames;
242 std::set<GlobalValue*> Symbols;
243 uint64_t uniqueCounter;
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;
254 std::string SymName = V.getName();
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] == '.') {
264 if (SymbolNames.count(SymName) == 0) {
265 DEBUG(std::cerr << "Disambiguator: adding " << SymName
266 << ", no conflicts.\n");
267 SymbolNames.insert(SymName);
269 // Mangle name before adding
272 newName = SymName + "_" + utostr(uniqueCounter);
273 if (SymbolNames.count(newName) == 0) break;
274 else ++uniqueCounter;
276 //while (SymbolNames.count(V->getName()+utostr(uniqueCounter++))==0);
277 DEBUG(std::cerr << "Disambiguator: conflict: " << SymName
278 << ", adding: " << newName << "\n");
280 SymbolNames.insert(newName);
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.
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);
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);
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);
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");
322 oldMain->setName("old_main");
323 // Create a NEW `main' function with same type
324 Function *newMain = new Function(oldMain->getFunctionType(),
325 GlobalValue::InternalLinkage,
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)
332 CallInst *call = new CallInst(oldMain, args);
333 BB->getInstList().push_back(call);
335 // if the type of old function wasn't void, return value of call
337 if (oldMain->getReturnType() != Type::VoidTy) {
338 ret = new ReturnInst(call);
340 ret = new ReturnInst();
343 // Add the return instruction to the BasicBlock
344 BB->getInstList().push_back(ret);
348 // Do the reduction...
349 ReduceMisCodegenFunctions(*this).reduceList(MisCodegenFunctions);
351 std::cout << "\n*** The following functions are being miscompiled: ";
352 PrintFunctionList(MisCodegenFunctions);
355 // Output a bunch of bytecode files for the user...
356 ReduceMisCodegenFunctions(*this).TestFuncs(MisCodegenFunctions, true);