Miscompilation.cpp revision 8be3291f5942e3ae4a5d66c480e7aabe2f771031 
1//===- Miscompilation.cpp - Debug program miscompilations -----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements optimizer and code generation miscompilation debugging
11// support.
12//
13//===----------------------------------------------------------------------===//
14
15#include "BugDriver.h"
16#include "ListReducer.h"
17#include "ToolRunner.h"
18#include "llvm/Constants.h"
19#include "llvm/DerivedTypes.h"
20#include "llvm/Instructions.h"
21#include "llvm/Linker.h"
22#include "llvm/Module.h"
23#include "llvm/Pass.h"
24#include "llvm/Analysis/Verifier.h"
25#include "llvm/Transforms/Utils/Cloning.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/FileUtilities.h"
28#include "llvm/Config/config.h"   // for HAVE_LINK_R
29using namespace llvm;
30
31namespace llvm {
32  extern cl::opt<std::string> OutputPrefix;
33  extern cl::list<std::string> InputArgv;
34}
35
36namespace {
37  static llvm::cl::opt<bool>
38    DisableLoopExtraction("disable-loop-extraction",
39        cl::desc("Don't extract loops when searching for miscompilations"),
40        cl::init(false));
41  static llvm::cl::opt<bool>
42    DisableBlockExtraction("disable-block-extraction",
43        cl::desc("Don't extract blocks when searching for miscompilations"),
44        cl::init(false));
45
46  class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> {
47    BugDriver &BD;
48  public:
49    ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {}
50
51    virtual TestResult doTest(std::vector<const PassInfo*> &Prefix,
52                              std::vector<const PassInfo*> &Suffix,
53                              std::string &Error);
54  };
55}
56
57/// TestResult - After passes have been split into a test group and a control
58/// group, see if they still break the program.
59///
60ReduceMiscompilingPasses::TestResult
61ReduceMiscompilingPasses::doTest(std::vector<const PassInfo*> &Prefix,
62                                 std::vector<const PassInfo*> &Suffix,
63                                 std::string &Error) {
64  // First, run the program with just the Suffix passes.  If it is still broken
65  // with JUST the kept passes, discard the prefix passes.
66  outs() << "Checking to see if '" << getPassesString(Suffix)
67         << "' compiles correctly: ";
68
69  std::string BitcodeResult;
70  if (BD.runPasses(Suffix, BitcodeResult, false/*delete*/, true/*quiet*/)) {
71    errs() << " Error running this sequence of passes"
72           << " on the input program!\n";
73    BD.setPassesToRun(Suffix);
74    BD.EmitProgressBitcode("pass-error",  false);
75    exit(BD.debugOptimizerCrash());
76  }
77
78  // Check to see if the finished program matches the reference output...
79  bool Diff = BD.diffProgram(BitcodeResult, "", true /*delete bitcode*/,
80                             &Error);
81  if (!Error.empty())
82    return InternalError;
83  if (Diff) {
84    outs() << " nope.\n";
85    if (Suffix.empty()) {
86      errs() << BD.getToolName() << ": I'm confused: the test fails when "
87             << "no passes are run, nondeterministic program?\n";
88      exit(1);
89    }
90    return KeepSuffix;         // Miscompilation detected!
91  }
92  outs() << " yup.\n";      // No miscompilation!
93
94  if (Prefix.empty()) return NoFailure;
95
96  // Next, see if the program is broken if we run the "prefix" passes first,
97  // then separately run the "kept" passes.
98  outs() << "Checking to see if '" << getPassesString(Prefix)
99         << "' compiles correctly: ";
100
101  // If it is not broken with the kept passes, it's possible that the prefix
102  // passes must be run before the kept passes to break it.  If the program
103  // WORKS after the prefix passes, but then fails if running the prefix AND
104  // kept passes, we can update our bitcode file to include the result of the
105  // prefix passes, then discard the prefix passes.
106  //
107  if (BD.runPasses(Prefix, BitcodeResult, false/*delete*/, true/*quiet*/)) {
108    errs() << " Error running this sequence of passes"
109           << " on the input program!\n";
110    BD.setPassesToRun(Prefix);
111    BD.EmitProgressBitcode("pass-error",  false);
112    exit(BD.debugOptimizerCrash());
113  }
114
115  // If the prefix maintains the predicate by itself, only keep the prefix!
116  Diff = BD.diffProgram(BitcodeResult, "", false, &Error);
117  if (!Error.empty())
118    return InternalError;
119  if (Diff) {
120    outs() << " nope.\n";
121    sys::Path(BitcodeResult).eraseFromDisk();
122    return KeepPrefix;
123  }
124  outs() << " yup.\n";      // No miscompilation!
125
126  // Ok, so now we know that the prefix passes work, try running the suffix
127  // passes on the result of the prefix passes.
128  //
129  OwningPtr<Module> PrefixOutput(ParseInputFile(BitcodeResult,
130                                                BD.getContext()));
131  if (PrefixOutput == 0) {
132    errs() << BD.getToolName() << ": Error reading bitcode file '"
133           << BitcodeResult << "'!\n";
134    exit(1);
135  }
136  sys::Path(BitcodeResult).eraseFromDisk();  // No longer need the file on disk
137
138  // Don't check if there are no passes in the suffix.
139  if (Suffix.empty())
140    return NoFailure;
141
142  outs() << "Checking to see if '" << getPassesString(Suffix)
143            << "' passes compile correctly after the '"
144            << getPassesString(Prefix) << "' passes: ";
145
146  OwningPtr<Module> OriginalInput(BD.swapProgramIn(PrefixOutput.take()));
147  if (BD.runPasses(Suffix, BitcodeResult, false/*delete*/, true/*quiet*/)) {
148    errs() << " Error running this sequence of passes"
149           << " on the input program!\n";
150    BD.setPassesToRun(Suffix);
151    BD.EmitProgressBitcode("pass-error",  false);
152    exit(BD.debugOptimizerCrash());
153  }
154
155  // Run the result...
156  Diff = BD.diffProgram(BitcodeResult, "", true /*delete bitcode*/, &Error);
157  if (!Error.empty())
158    return InternalError;
159  if (Diff) {
160    outs() << " nope.\n";
161    return KeepSuffix;
162  }
163
164  // Otherwise, we must not be running the bad pass anymore.
165  outs() << " yup.\n";      // No miscompilation!
166  // Restore orig program & free test.
167  delete BD.swapProgramIn(OriginalInput.take());
168  return NoFailure;
169}
170
171namespace {
172  class ReduceMiscompilingFunctions : public ListReducer<Function*> {
173    BugDriver &BD;
174    bool (*TestFn)(BugDriver &, Module *, Module *, std::string &);
175  public:
176    ReduceMiscompilingFunctions(BugDriver &bd,
177                                bool (*F)(BugDriver &, Module *, Module *,
178                                          std::string &))
179      : BD(bd), TestFn(F) {}
180
181    virtual TestResult doTest(std::vector<Function*> &Prefix,
182                              std::vector<Function*> &Suffix,
183                              std::string &Error) {
184      if (!Suffix.empty()) {
185        bool Ret = TestFuncs(Suffix, Error);
186        if (!Error.empty())
187          return InternalError;
188        if (Ret)
189          return KeepSuffix;
190      }
191      if (!Prefix.empty()) {
192        bool Ret = TestFuncs(Prefix, Error);
193        if (!Error.empty())
194          return InternalError;
195        if (Ret)
196          return KeepPrefix;
197      }
198      return NoFailure;
199    }
200
201    int TestFuncs(const std::vector<Function*> &Prefix, std::string &Error);
202  };
203}
204
205/// TestMergedProgram - Given two modules, link them together and run the
206/// program, checking to see if the program matches the diff.  If the diff
207/// matches, return false, otherwise return true.  If the DeleteInputs argument
208/// is set to true then this function deletes both input modules before it
209/// returns.
210///
211static bool TestMergedProgram(BugDriver &BD, Module *M1, Module *M2,
212                              bool DeleteInputs, std::string &Error) {
213  // Link the two portions of the program back to together.
214  std::string ErrorMsg;
215  if (!DeleteInputs) {
216    M1 = CloneModule(M1);
217    M2 = CloneModule(M2);
218  }
219  if (Linker::LinkModules(M1, M2, &ErrorMsg)) {
220    errs() << BD.getToolName() << ": Error linking modules together:"
221           << ErrorMsg << '\n';
222    exit(1);
223  }
224  delete M2;   // We are done with this module.
225
226  OwningPtr<Module> OldProgram(BD.swapProgramIn(M1));
227
228  // Execute the program.  If it does not match the expected output, we must
229  // return true.
230  bool Broken = BD.diffProgram("", "", false, &Error);
231  if (!Error.empty()) {
232    // Delete the linked module & restore the original
233    delete BD.swapProgramIn(OldProgram.take());
234  }
235  return Broken;
236}
237
238/// TestFuncs - split functions in a Module into two groups: those that are
239/// under consideration for miscompilation vs. those that are not, and test
240/// accordingly. Each group of functions becomes a separate Module.
241///
242int ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*> &Funcs,
243                                           std::string &Error) {
244  // Test to see if the function is misoptimized if we ONLY run it on the
245  // functions listed in Funcs.
246  outs() << "Checking to see if the program is misoptimized when "
247         << (Funcs.size()==1 ? "this function is" : "these functions are")
248         << " run through the pass"
249         << (BD.getPassesToRun().size() == 1 ? "" : "es") << ":";
250  PrintFunctionList(Funcs);
251  outs() << '\n';
252
253  // Split the module into the two halves of the program we want.
254  ValueMap<const Value*, Value*> VMap;
255  Module *ToNotOptimize = CloneModule(BD.getProgram(), VMap);
256  Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, Funcs,
257                                                 VMap);
258
259  // Run the predicate, note that the predicate will delete both input modules.
260  return TestFn(BD, ToOptimize, ToNotOptimize, Error);
261}
262
263/// DisambiguateGlobalSymbols - Give anonymous global values names.
264///
265static void DisambiguateGlobalSymbols(Module *M) {
266  for (Module::global_iterator I = M->global_begin(), E = M->global_end();
267       I != E; ++I)
268    if (!I->hasName())
269      I->setName("anon_global");
270  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
271    if (!I->hasName())
272      I->setName("anon_fn");
273}
274
275/// ExtractLoops - Given a reduced list of functions that still exposed the bug,
276/// check to see if we can extract the loops in the region without obscuring the
277/// bug.  If so, it reduces the amount of code identified.
278///
279static bool ExtractLoops(BugDriver &BD,
280                         bool (*TestFn)(BugDriver &, Module *, Module *,
281                                        std::string &),
282                         std::vector<Function*> &MiscompiledFunctions,
283                         std::string &Error) {
284  bool MadeChange = false;
285  while (1) {
286    if (BugpointIsInterrupted) return MadeChange;
287
288    ValueMap<const Value*, Value*> VMap;
289    Module *ToNotOptimize = CloneModule(BD.getProgram(), VMap);
290    Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
291                                                   MiscompiledFunctions,
292                                                   VMap);
293    Module *ToOptimizeLoopExtracted = BD.ExtractLoop(ToOptimize);
294    if (!ToOptimizeLoopExtracted) {
295      // If the loop extractor crashed or if there were no extractible loops,
296      // then this chapter of our odyssey is over with.
297      delete ToNotOptimize;
298      delete ToOptimize;
299      return MadeChange;
300    }
301
302    errs() << "Extracted a loop from the breaking portion of the program.\n";
303
304    // Bugpoint is intentionally not very trusting of LLVM transformations.  In
305    // particular, we're not going to assume that the loop extractor works, so
306    // we're going to test the newly loop extracted program to make sure nothing
307    // has broken.  If something broke, then we'll inform the user and stop
308    // extraction.
309    AbstractInterpreter *AI = BD.switchToSafeInterpreter();
310    bool Failure = TestMergedProgram(BD, ToOptimizeLoopExtracted, ToNotOptimize,
311                                     false, Error);
312    if (!Error.empty())
313      return false;
314    if (Failure) {
315      BD.switchToInterpreter(AI);
316
317      // Merged program doesn't work anymore!
318      errs() << "  *** ERROR: Loop extraction broke the program. :("
319             << " Please report a bug!\n";
320      errs() << "      Continuing on with un-loop-extracted version.\n";
321
322      BD.writeProgramToFile(OutputPrefix + "-loop-extract-fail-tno.bc",
323                            ToNotOptimize);
324      BD.writeProgramToFile(OutputPrefix + "-loop-extract-fail-to.bc",
325                            ToOptimize);
326      BD.writeProgramToFile(OutputPrefix + "-loop-extract-fail-to-le.bc",
327                            ToOptimizeLoopExtracted);
328
329      errs() << "Please submit the "
330             << OutputPrefix << "-loop-extract-fail-*.bc files.\n";
331      delete ToOptimize;
332      delete ToNotOptimize;
333      delete ToOptimizeLoopExtracted;
334      return MadeChange;
335    }
336    delete ToOptimize;
337    BD.switchToInterpreter(AI);
338
339    outs() << "  Testing after loop extraction:\n";
340    // Clone modules, the tester function will free them.
341    Module *TOLEBackup = CloneModule(ToOptimizeLoopExtracted);
342    Module *TNOBackup  = CloneModule(ToNotOptimize);
343    Failure = TestFn(BD, ToOptimizeLoopExtracted, ToNotOptimize, Error);
344    if (!Error.empty())
345      return false;
346    if (!Failure) {
347      outs() << "*** Loop extraction masked the problem.  Undoing.\n";
348      // If the program is not still broken, then loop extraction did something
349      // that masked the error.  Stop loop extraction now.
350      delete TOLEBackup;
351      delete TNOBackup;
352      return MadeChange;
353    }
354    ToOptimizeLoopExtracted = TOLEBackup;
355    ToNotOptimize = TNOBackup;
356
357    outs() << "*** Loop extraction successful!\n";
358
359    std::vector<std::pair<std::string, const FunctionType*> > MisCompFunctions;
360    for (Module::iterator I = ToOptimizeLoopExtracted->begin(),
361           E = ToOptimizeLoopExtracted->end(); I != E; ++I)
362      if (!I->isDeclaration())
363        MisCompFunctions.push_back(std::make_pair(I->getName(),
364                                                  I->getFunctionType()));
365
366    // Okay, great!  Now we know that we extracted a loop and that loop
367    // extraction both didn't break the program, and didn't mask the problem.
368    // Replace the current program with the loop extracted version, and try to
369    // extract another loop.
370    std::string ErrorMsg;
371    if (Linker::LinkModules(ToNotOptimize, ToOptimizeLoopExtracted, &ErrorMsg)){
372      errs() << BD.getToolName() << ": Error linking modules together:"
373             << ErrorMsg << '\n';
374      exit(1);
375    }
376    delete ToOptimizeLoopExtracted;
377
378    // All of the Function*'s in the MiscompiledFunctions list are in the old
379    // module.  Update this list to include all of the functions in the
380    // optimized and loop extracted module.
381    MiscompiledFunctions.clear();
382    for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) {
383      Function *NewF = ToNotOptimize->getFunction(MisCompFunctions[i].first);
384
385      assert(NewF && "Function not found??");
386      assert(NewF->getFunctionType() == MisCompFunctions[i].second &&
387             "found wrong function type?");
388      MiscompiledFunctions.push_back(NewF);
389    }
390
391    BD.setNewProgram(ToNotOptimize);
392    MadeChange = true;
393  }
394}
395
396namespace {
397  class ReduceMiscompiledBlocks : public ListReducer<BasicBlock*> {
398    BugDriver &BD;
399    bool (*TestFn)(BugDriver &, Module *, Module *, std::string &);
400    std::vector<Function*> FunctionsBeingTested;
401  public:
402    ReduceMiscompiledBlocks(BugDriver &bd,
403                            bool (*F)(BugDriver &, Module *, Module *,
404                                      std::string &),
405                            const std::vector<Function*> &Fns)
406      : BD(bd), TestFn(F), FunctionsBeingTested(Fns) {}
407
408    virtual TestResult doTest(std::vector<BasicBlock*> &Prefix,
409                              std::vector<BasicBlock*> &Suffix,
410                              std::string &Error) {
411      if (!Suffix.empty()) {
412        bool Ret = TestFuncs(Suffix, Error);
413        if (!Error.empty())
414          return InternalError;
415        if (Ret)
416          return KeepSuffix;
417      }
418      if (!Prefix.empty()) {
419        bool Ret = TestFuncs(Prefix, Error);
420        if (!Error.empty())
421          return InternalError;
422        if (Ret)
423          return KeepPrefix;
424      }
425      return NoFailure;
426    }
427
428    bool TestFuncs(const std::vector<BasicBlock*> &BBs, std::string &Error);
429  };
430}
431
432/// TestFuncs - Extract all blocks for the miscompiled functions except for the
433/// specified blocks.  If the problem still exists, return true.
434///
435bool ReduceMiscompiledBlocks::TestFuncs(const std::vector<BasicBlock*> &BBs,
436                                        std::string &Error) {
437  // Test to see if the function is misoptimized if we ONLY run it on the
438  // functions listed in Funcs.
439  outs() << "Checking to see if the program is misoptimized when all ";
440  if (!BBs.empty()) {
441    outs() << "but these " << BBs.size() << " blocks are extracted: ";
442    for (unsigned i = 0, e = BBs.size() < 10 ? BBs.size() : 10; i != e; ++i)
443      outs() << BBs[i]->getName() << " ";
444    if (BBs.size() > 10) outs() << "...";
445  } else {
446    outs() << "blocks are extracted.";
447  }
448  outs() << '\n';
449
450  // Split the module into the two halves of the program we want.
451  ValueMap<const Value*, Value*> VMap;
452  Module *ToNotOptimize = CloneModule(BD.getProgram(), VMap);
453  Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
454                                                 FunctionsBeingTested,
455                                                 VMap);
456
457  // Try the extraction.  If it doesn't work, then the block extractor crashed
458  // or something, in which case bugpoint can't chase down this possibility.
459  if (Module *New = BD.ExtractMappedBlocksFromModule(BBs, ToOptimize)) {
460    delete ToOptimize;
461    // Run the predicate, not that the predicate will delete both input modules.
462    return TestFn(BD, New, ToNotOptimize, Error);
463  }
464  delete ToOptimize;
465  delete ToNotOptimize;
466  return false;
467}
468
469
470/// ExtractBlocks - Given a reduced list of functions that still expose the bug,
471/// extract as many basic blocks from the region as possible without obscuring
472/// the bug.
473///
474static bool ExtractBlocks(BugDriver &BD,
475                          bool (*TestFn)(BugDriver &, Module *, Module *,
476                                         std::string &),
477                          std::vector<Function*> &MiscompiledFunctions,
478                          std::string &Error) {
479  if (BugpointIsInterrupted) return false;
480
481  std::vector<BasicBlock*> Blocks;
482  for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i)
483    for (Function::iterator I = MiscompiledFunctions[i]->begin(),
484           E = MiscompiledFunctions[i]->end(); I != E; ++I)
485      Blocks.push_back(I);
486
487  // Use the list reducer to identify blocks that can be extracted without
488  // obscuring the bug.  The Blocks list will end up containing blocks that must
489  // be retained from the original program.
490  unsigned OldSize = Blocks.size();
491
492  // Check to see if all blocks are extractible first.
493  bool Ret = ReduceMiscompiledBlocks(BD, TestFn, MiscompiledFunctions)
494                                  .TestFuncs(std::vector<BasicBlock*>(), Error);
495  if (!Error.empty())
496    return false;
497  if (Ret) {
498    Blocks.clear();
499  } else {
500    ReduceMiscompiledBlocks(BD, TestFn,
501                            MiscompiledFunctions).reduceList(Blocks, Error);
502    if (!Error.empty())
503      return false;
504    if (Blocks.size() == OldSize)
505      return false;
506  }
507
508  ValueMap<const Value*, Value*> VMap;
509  Module *ProgClone = CloneModule(BD.getProgram(), VMap);
510  Module *ToExtract = SplitFunctionsOutOfModule(ProgClone,
511                                                MiscompiledFunctions,
512                                                VMap);
513  Module *Extracted = BD.ExtractMappedBlocksFromModule(Blocks, ToExtract);
514  if (Extracted == 0) {
515    // Weird, extraction should have worked.
516    errs() << "Nondeterministic problem extracting blocks??\n";
517    delete ProgClone;
518    delete ToExtract;
519    return false;
520  }
521
522  // Otherwise, block extraction succeeded.  Link the two program fragments back
523  // together.
524  delete ToExtract;
525
526  std::vector<std::pair<std::string, const FunctionType*> > MisCompFunctions;
527  for (Module::iterator I = Extracted->begin(), E = Extracted->end();
528       I != E; ++I)
529    if (!I->isDeclaration())
530      MisCompFunctions.push_back(std::make_pair(I->getName(),
531                                                I->getFunctionType()));
532
533  std::string ErrorMsg;
534  if (Linker::LinkModules(ProgClone, Extracted, &ErrorMsg)) {
535    errs() << BD.getToolName() << ": Error linking modules together:"
536           << ErrorMsg << '\n';
537    exit(1);
538  }
539  delete Extracted;
540
541  // Set the new program and delete the old one.
542  BD.setNewProgram(ProgClone);
543
544  // Update the list of miscompiled functions.
545  MiscompiledFunctions.clear();
546
547  for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) {
548    Function *NewF = ProgClone->getFunction(MisCompFunctions[i].first);
549    assert(NewF && "Function not found??");
550    assert(NewF->getFunctionType() == MisCompFunctions[i].second &&
551           "Function has wrong type??");
552    MiscompiledFunctions.push_back(NewF);
553  }
554
555  return true;
556}
557
558
559/// DebugAMiscompilation - This is a generic driver to narrow down
560/// miscompilations, either in an optimization or a code generator.
561///
562static std::vector<Function*>
563DebugAMiscompilation(BugDriver &BD,
564                     bool (*TestFn)(BugDriver &, Module *, Module *,
565                                    std::string &),
566                     std::string &Error) {
567  // Okay, now that we have reduced the list of passes which are causing the
568  // failure, see if we can pin down which functions are being
569  // miscompiled... first build a list of all of the non-external functions in
570  // the program.
571  std::vector<Function*> MiscompiledFunctions;
572  Module *Prog = BD.getProgram();
573  for (Module::iterator I = Prog->begin(), E = Prog->end(); I != E; ++I)
574    if (!I->isDeclaration())
575      MiscompiledFunctions.push_back(I);
576
577  // Do the reduction...
578  if (!BugpointIsInterrupted)
579    ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions,
580                                                       Error);
581  if (!Error.empty())
582    return MiscompiledFunctions;
583
584  outs() << "\n*** The following function"
585         << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
586         << " being miscompiled: ";
587  PrintFunctionList(MiscompiledFunctions);
588  outs() << '\n';
589
590  // See if we can rip any loops out of the miscompiled functions and still
591  // trigger the problem.
592
593  if (!BugpointIsInterrupted && !DisableLoopExtraction) {
594    bool Ret = ExtractLoops(BD, TestFn, MiscompiledFunctions, Error);
595    if (!Error.empty())
596      return MiscompiledFunctions;
597    if (Ret) {
598      // Okay, we extracted some loops and the problem still appears.  See if
599      // we can eliminate some of the created functions from being candidates.
600      DisambiguateGlobalSymbols(BD.getProgram());
601
602      // Do the reduction...
603      if (!BugpointIsInterrupted)
604        ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions,
605                                                           Error);
606      if (!Error.empty())
607        return MiscompiledFunctions;
608
609      outs() << "\n*** The following function"
610             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
611             << " being miscompiled: ";
612      PrintFunctionList(MiscompiledFunctions);
613      outs() << '\n';
614    }
615  }
616
617  if (!BugpointIsInterrupted && !DisableBlockExtraction) {
618    bool Ret = ExtractBlocks(BD, TestFn, MiscompiledFunctions, Error);
619    if (!Error.empty())
620      return MiscompiledFunctions;
621    if (Ret) {
622      // Okay, we extracted some blocks and the problem still appears.  See if
623      // we can eliminate some of the created functions from being candidates.
624      DisambiguateGlobalSymbols(BD.getProgram());
625
626      // Do the reduction...
627      ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions,
628                                                         Error);
629      if (!Error.empty())
630        return MiscompiledFunctions;
631
632      outs() << "\n*** The following function"
633             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
634             << " being miscompiled: ";
635      PrintFunctionList(MiscompiledFunctions);
636      outs() << '\n';
637    }
638  }
639
640  return MiscompiledFunctions;
641}
642
643/// TestOptimizer - This is the predicate function used to check to see if the
644/// "Test" portion of the program is misoptimized.  If so, return true.  In any
645/// case, both module arguments are deleted.
646///
647static bool TestOptimizer(BugDriver &BD, Module *Test, Module *Safe,
648                          std::string &Error) {
649  // Run the optimization passes on ToOptimize, producing a transformed version
650  // of the functions being tested.
651  outs() << "  Optimizing functions being tested: ";
652  Module *Optimized = BD.runPassesOn(Test, BD.getPassesToRun(),
653                                     /*AutoDebugCrashes*/true);
654  outs() << "done.\n";
655  delete Test;
656
657  outs() << "  Checking to see if the merged program executes correctly: ";
658  bool Broken = TestMergedProgram(BD, Optimized, Safe, true, Error);
659  if (Error.empty()) outs() << (Broken ? " nope.\n" : " yup.\n");
660  return Broken;
661}
662
663
664/// debugMiscompilation - This method is used when the passes selected are not
665/// crashing, but the generated output is semantically different from the
666/// input.
667///
668void BugDriver::debugMiscompilation(std::string *Error) {
669  // Make sure something was miscompiled...
670  if (!BugpointIsInterrupted)
671    if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun, *Error)) {
672      if (Error->empty())
673        errs() << "*** Optimized program matches reference output!  No problem"
674               << " detected...\nbugpoint can't help you with your problem!\n";
675      return;
676    }
677
678  outs() << "\n*** Found miscompiling pass"
679         << (getPassesToRun().size() == 1 ? "" : "es") << ": "
680         << getPassesString(getPassesToRun()) << '\n';
681  EmitProgressBitcode("passinput");
682
683  std::vector<Function *> MiscompiledFunctions =
684    DebugAMiscompilation(*this, TestOptimizer, *Error);
685  if (!Error->empty())
686    return;
687
688  // Output a bunch of bitcode files for the user...
689  outs() << "Outputting reduced bitcode files which expose the problem:\n";
690  ValueMap<const Value*, Value*> VMap;
691  Module *ToNotOptimize = CloneModule(getProgram(), VMap);
692  Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
693                                                 MiscompiledFunctions,
694                                                 VMap);
695
696  outs() << "  Non-optimized portion: ";
697  ToNotOptimize = swapProgramIn(ToNotOptimize);
698  EmitProgressBitcode("tonotoptimize", true);
699  setNewProgram(ToNotOptimize);   // Delete hacked module.
700
701  outs() << "  Portion that is input to optimizer: ";
702  ToOptimize = swapProgramIn(ToOptimize);
703  EmitProgressBitcode("tooptimize");
704  setNewProgram(ToOptimize);      // Delete hacked module.
705
706  return;
707}
708
709/// CleanupAndPrepareModules - Get the specified modules ready for code
710/// generator testing.
711///
712static void CleanupAndPrepareModules(BugDriver &BD, Module *&Test,
713                                     Module *Safe) {
714  // Clean up the modules, removing extra cruft that we don't need anymore...
715  Test = BD.performFinalCleanups(Test);
716
717  // If we are executing the JIT, we have several nasty issues to take care of.
718  if (!BD.isExecutingJIT()) return;
719
720  // First, if the main function is in the Safe module, we must add a stub to
721  // the Test module to call into it.  Thus, we create a new function `main'
722  // which just calls the old one.
723  if (Function *oldMain = Safe->getFunction("main"))
724    if (!oldMain->isDeclaration()) {
725      // Rename it
726      oldMain->setName("llvm_bugpoint_old_main");
727      // Create a NEW `main' function with same type in the test module.
728      Function *newMain = Function::Create(oldMain->getFunctionType(),
729                                           GlobalValue::ExternalLinkage,
730                                           "main", Test);
731      // Create an `oldmain' prototype in the test module, which will
732      // corresponds to the real main function in the same module.
733      Function *oldMainProto = Function::Create(oldMain->getFunctionType(),
734                                                GlobalValue::ExternalLinkage,
735                                                oldMain->getName(), Test);
736      // Set up and remember the argument list for the main function.
737      std::vector<Value*> args;
738      for (Function::arg_iterator
739             I = newMain->arg_begin(), E = newMain->arg_end(),
740             OI = oldMain->arg_begin(); I != E; ++I, ++OI) {
741        I->setName(OI->getName());    // Copy argument names from oldMain
742        args.push_back(I);
743      }
744
745      // Call the old main function and return its result
746      BasicBlock *BB = BasicBlock::Create(Safe->getContext(), "entry", newMain);
747      CallInst *call = CallInst::Create(oldMainProto, args.begin(), args.end(),
748                                        "", BB);
749
750      // If the type of old function wasn't void, return value of call
751      ReturnInst::Create(Safe->getContext(), call, BB);
752    }
753
754  // The second nasty issue we must deal with in the JIT is that the Safe
755  // module cannot directly reference any functions defined in the test
756  // module.  Instead, we use a JIT API call to dynamically resolve the
757  // symbol.
758
759  // Add the resolver to the Safe module.
760  // Prototype: void *getPointerToNamedFunction(const char* Name)
761  Constant *resolverFunc =
762    Safe->getOrInsertFunction("getPointerToNamedFunction",
763                    Type::getInt8PtrTy(Safe->getContext()),
764                    Type::getInt8PtrTy(Safe->getContext()),
765                       (Type *)0);
766
767  // Use the function we just added to get addresses of functions we need.
768  for (Module::iterator F = Safe->begin(), E = Safe->end(); F != E; ++F) {
769    if (F->isDeclaration() && !F->use_empty() && &*F != resolverFunc &&
770        !F->isIntrinsic() /* ignore intrinsics */) {
771      Function *TestFn = Test->getFunction(F->getName());
772
773      // Don't forward functions which are external in the test module too.
774      if (TestFn && !TestFn->isDeclaration()) {
775        // 1. Add a string constant with its name to the global file
776        Constant *InitArray = ConstantArray::get(F->getContext(), F->getName());
777        GlobalVariable *funcName =
778          new GlobalVariable(*Safe, InitArray->getType(), true /*isConstant*/,
779                             GlobalValue::InternalLinkage, InitArray,
780                             F->getName() + "_name");
781
782        // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an
783        // sbyte* so it matches the signature of the resolver function.
784
785        // GetElementPtr *funcName, ulong 0, ulong 0
786        std::vector<Constant*> GEPargs(2,
787                     Constant::getNullValue(Type::getInt32Ty(F->getContext())));
788        Value *GEP =
789                ConstantExpr::getGetElementPtr(funcName, &GEPargs[0], 2);
790        std::vector<Value*> ResolverArgs;
791        ResolverArgs.push_back(GEP);
792
793        // Rewrite uses of F in global initializers, etc. to uses of a wrapper
794        // function that dynamically resolves the calls to F via our JIT API
795        if (!F->use_empty()) {
796          // Create a new global to hold the cached function pointer.
797          Constant *NullPtr = ConstantPointerNull::get(F->getType());
798          GlobalVariable *Cache =
799            new GlobalVariable(*F->getParent(), F->getType(),
800                               false, GlobalValue::InternalLinkage,
801                               NullPtr,F->getName()+".fpcache");
802
803          // Construct a new stub function that will re-route calls to F
804          const FunctionType *FuncTy = F->getFunctionType();
805          Function *FuncWrapper = Function::Create(FuncTy,
806                                                   GlobalValue::InternalLinkage,
807                                                   F->getName() + "_wrapper",
808                                                   F->getParent());
809          BasicBlock *EntryBB  = BasicBlock::Create(F->getContext(),
810                                                    "entry", FuncWrapper);
811          BasicBlock *DoCallBB = BasicBlock::Create(F->getContext(),
812                                                    "usecache", FuncWrapper);
813          BasicBlock *LookupBB = BasicBlock::Create(F->getContext(),
814                                                    "lookupfp", FuncWrapper);
815
816          // Check to see if we already looked up the value.
817          Value *CachedVal = new LoadInst(Cache, "fpcache", EntryBB);
818          Value *IsNull = new ICmpInst(*EntryBB, ICmpInst::ICMP_EQ, CachedVal,
819                                       NullPtr, "isNull");
820          BranchInst::Create(LookupBB, DoCallBB, IsNull, EntryBB);
821
822          // Resolve the call to function F via the JIT API:
823          //
824          // call resolver(GetElementPtr...)
825          CallInst *Resolver =
826            CallInst::Create(resolverFunc, ResolverArgs.begin(),
827                             ResolverArgs.end(), "resolver", LookupBB);
828
829          // Cast the result from the resolver to correctly-typed function.
830          CastInst *CastedResolver =
831            new BitCastInst(Resolver,
832                            PointerType::getUnqual(F->getFunctionType()),
833                            "resolverCast", LookupBB);
834
835          // Save the value in our cache.
836          new StoreInst(CastedResolver, Cache, LookupBB);
837          BranchInst::Create(DoCallBB, LookupBB);
838
839          PHINode *FuncPtr = PHINode::Create(NullPtr->getType(),
840                                             "fp", DoCallBB);
841          FuncPtr->addIncoming(CastedResolver, LookupBB);
842          FuncPtr->addIncoming(CachedVal, EntryBB);
843
844          // Save the argument list.
845          std::vector<Value*> Args;
846          for (Function::arg_iterator i = FuncWrapper->arg_begin(),
847                 e = FuncWrapper->arg_end(); i != e; ++i)
848            Args.push_back(i);
849
850          // Pass on the arguments to the real function, return its result
851          if (F->getReturnType()->isVoidTy()) {
852            CallInst::Create(FuncPtr, Args.begin(), Args.end(), "", DoCallBB);
853            ReturnInst::Create(F->getContext(), DoCallBB);
854          } else {
855            CallInst *Call = CallInst::Create(FuncPtr, Args.begin(), Args.end(),
856                                              "retval", DoCallBB);
857            ReturnInst::Create(F->getContext(),Call, DoCallBB);
858          }
859
860          // Use the wrapper function instead of the old function
861          F->replaceAllUsesWith(FuncWrapper);
862        }
863      }
864    }
865  }
866
867  if (verifyModule(*Test) || verifyModule(*Safe)) {
868    errs() << "Bugpoint has a bug, which corrupted a module!!\n";
869    abort();
870  }
871}
872
873
874
875/// TestCodeGenerator - This is the predicate function used to check to see if
876/// the "Test" portion of the program is miscompiled by the code generator under
877/// test.  If so, return true.  In any case, both module arguments are deleted.
878///
879static bool TestCodeGenerator(BugDriver &BD, Module *Test, Module *Safe,
880                              std::string &Error) {
881  CleanupAndPrepareModules(BD, Test, Safe);
882
883  sys::Path TestModuleBC("bugpoint.test.bc");
884  std::string ErrMsg;
885  if (TestModuleBC.makeUnique(true, &ErrMsg)) {
886    errs() << BD.getToolName() << "Error making unique filename: "
887           << ErrMsg << "\n";
888    exit(1);
889  }
890  if (BD.writeProgramToFile(TestModuleBC.str(), Test)) {
891    errs() << "Error writing bitcode to `" << TestModuleBC.str()
892           << "'\nExiting.";
893    exit(1);
894  }
895  delete Test;
896
897  FileRemover TestModuleBCRemover(TestModuleBC, !SaveTemps);
898
899  // Make the shared library
900  sys::Path SafeModuleBC("bugpoint.safe.bc");
901  if (SafeModuleBC.makeUnique(true, &ErrMsg)) {
902    errs() << BD.getToolName() << "Error making unique filename: "
903           << ErrMsg << "\n";
904    exit(1);
905  }
906
907  if (BD.writeProgramToFile(SafeModuleBC.str(), Safe)) {
908    errs() << "Error writing bitcode to `" << SafeModuleBC.str()
909           << "'\nExiting.";
910    exit(1);
911  }
912
913  FileRemover SafeModuleBCRemover(SafeModuleBC, !SaveTemps);
914
915  std::string SharedObject = BD.compileSharedObject(SafeModuleBC.str(), Error);
916  if (!Error.empty())
917    return false;
918  delete Safe;
919
920  FileRemover SharedObjectRemover(sys::Path(SharedObject), !SaveTemps);
921
922  // Run the code generator on the `Test' code, loading the shared library.
923  // The function returns whether or not the new output differs from reference.
924  bool Result = BD.diffProgram(TestModuleBC.str(), SharedObject, false, &Error);
925  if (!Error.empty())
926    return false;
927
928  if (Result)
929    errs() << ": still failing!\n";
930  else
931    errs() << ": didn't fail.\n";
932
933  return Result;
934}
935
936
937/// debugCodeGenerator - debug errors in LLC, LLI, or CBE.
938///
939bool BugDriver::debugCodeGenerator(std::string *Error) {
940  if ((void*)SafeInterpreter == (void*)Interpreter) {
941    std::string Result = executeProgramSafely("bugpoint.safe.out", Error);
942    if (Error->empty()) {
943      outs() << "\n*** The \"safe\" i.e. 'known good' backend cannot match "
944             << "the reference diff.  This may be due to a\n    front-end "
945             << "bug or a bug in the original program, but this can also "
946             << "happen if bugpoint isn't running the program with the "
947             << "right flags or input.\n    I left the result of executing "
948             << "the program with the \"safe\" backend in this file for "
949             << "you: '"
950             << Result << "'.\n";
951    }
952    return true;
953  }
954
955  DisambiguateGlobalSymbols(Program);
956
957  std::vector<Function*> Funcs = DebugAMiscompilation(*this, TestCodeGenerator,
958                                                      *Error);
959  if (!Error->empty())
960    return true;
961
962  // Split the module into the two halves of the program we want.
963  ValueMap<const Value*, Value*> VMap;
964  Module *ToNotCodeGen = CloneModule(getProgram(), VMap);
965  Module *ToCodeGen = SplitFunctionsOutOfModule(ToNotCodeGen, Funcs, VMap);
966
967  // Condition the modules
968  CleanupAndPrepareModules(*this, ToCodeGen, ToNotCodeGen);
969
970  sys::Path TestModuleBC("bugpoint.test.bc");
971  std::string ErrMsg;
972  if (TestModuleBC.makeUnique(true, &ErrMsg)) {
973    errs() << getToolName() << "Error making unique filename: "
974           << ErrMsg << "\n";
975    exit(1);
976  }
977
978  if (writeProgramToFile(TestModuleBC.str(), ToCodeGen)) {
979    errs() << "Error writing bitcode to `" << TestModuleBC.str()
980           << "'\nExiting.";
981    exit(1);
982  }
983  delete ToCodeGen;
984
985  // Make the shared library
986  sys::Path SafeModuleBC("bugpoint.safe.bc");
987  if (SafeModuleBC.makeUnique(true, &ErrMsg)) {
988    errs() << getToolName() << "Error making unique filename: "
989           << ErrMsg << "\n";
990    exit(1);
991  }
992
993  if (writeProgramToFile(SafeModuleBC.str(), ToNotCodeGen)) {
994    errs() << "Error writing bitcode to `" << SafeModuleBC.str()
995           << "'\nExiting.";
996    exit(1);
997  }
998  std::string SharedObject = compileSharedObject(SafeModuleBC.str(), *Error);
999  if (!Error->empty())
1000    return true;
1001  delete ToNotCodeGen;
1002
1003  outs() << "You can reproduce the problem with the command line: \n";
1004  if (isExecutingJIT()) {
1005    outs() << "  lli -load " << SharedObject << " " << TestModuleBC.str();
1006  } else {
1007    outs() << "  llc " << TestModuleBC.str() << " -o " << TestModuleBC.str()
1008           << ".s\n";
1009    outs() << "  gcc " << SharedObject << " " << TestModuleBC.str()
1010              << ".s -o " << TestModuleBC.str() << ".exe";
1011#if defined (HAVE_LINK_R)
1012    outs() << " -Wl,-R.";
1013#endif
1014    outs() << "\n";
1015    outs() << "  " << TestModuleBC.str() << ".exe";
1016  }
1017  for (unsigned i = 0, e = InputArgv.size(); i != e; ++i)
1018    outs() << " " << InputArgv[i];
1019  outs() << '\n';
1020  outs() << "The shared object was created with:\n  llc -march=c "
1021         << SafeModuleBC.str() << " -o temporary.c\n"
1022         << "  gcc -xc temporary.c -O2 -o " << SharedObject;
1023  if (TargetTriple.getArch() == Triple::sparc)
1024    outs() << " -G";              // Compile a shared library, `-G' for Sparc
1025  else
1026    outs() << " -fPIC -shared";   // `-shared' for Linux/X86, maybe others
1027
1028  outs() << " -fno-strict-aliasing\n";
1029
1030  return false;
1031}
1032