Implement basic block extraction for the miscompilation debugger. This still needs

two things: the FIXME in ExtractBlocks needs to be implemented, and the basic block
extractor itself needs to have enough bugs fixed for this to be more or less
useful.

Until the time that this is generally useful, it is hidden behind the new bugpoint
-enable-block-extraction option.  I hope to get the FIXME done tonight.

Also of note, this patch adds a -extract-bbs option to bugpoint which can be used
to debug the block extractor.  (hint hint Misha :)


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13471 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 188 insertions, 0 deletions

diff --git a/tools/bugpoint/BugDriver.h b/tools/bugpoint/BugDriver.h
index 92fdb7c0a1..5e78145b6f 100644
--- a/tools/bugpoint/BugDriver.h
+++ b/tools/bugpoint/BugDriver.h
@@ -24,6 +24,7 @@ namespace llvm {
 class PassInfo;
 class Module;
 class Function;
+class BasicBlock;
 class AbstractInterpreter;
 class Instruction;
 
@@ -200,6 +201,14 @@ public:
   /// program or if the loop extractor crashes.
   Module *ExtractLoop(Module *M);
 
+  /// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks
+  /// into their own functions.  The only detail is that M is actually a module
+  /// cloned from the one the BBs are in, so some mapping needs to be performed.
+  /// If this operation fails for some reason (ie the implementation is buggy),
+  /// this function should return null, otherwise it returns a new Module.
+  Module *ExtractMappedBlocksFromModule(const std::vector<BasicBlock*> &BBs,
+                                        Module *M);
+
   /// runPassesOn - Carefully run the specified set of pass on the specified
   /// module, returning the transformed module on success, or a null pointer on
   /// failure.  If AutoDebugCrashes is set to true, then bugpoint will
diff --git a/tools/bugpoint/ExtractFunction.cpp b/tools/bugpoint/ExtractFunction.cpp
index 9f8dca8abd..ecc2652556 100644
--- a/tools/bugpoint/ExtractFunction.cpp
+++ b/tools/bugpoint/ExtractFunction.cpp
@@ -22,6 +22,7 @@
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/FunctionUtils.h"
 #include "llvm/Target/TargetData.h"
 #include "Support/CommandLine.h"
 #include "Support/Debug.h"
@@ -199,3 +200,69 @@ Module *llvm::SplitFunctionsOutOfModule(Module *M,
       DeleteFunctionBody(I);
   return New;
 }
+
+//===----------------------------------------------------------------------===//
+// Basic Block Extraction Code
+//===----------------------------------------------------------------------===//
+
+namespace {
+  std::vector<BasicBlock*> BlocksToNotExtract;
+
+  /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks
+  /// from the module into their own functions except for those specified by the
+  /// BlocksToNotExtract list.
+  class BlockExtractorPass : public Pass {
+    bool run(Module &M);
+  };
+  RegisterOpt<BlockExtractorPass>
+  XX("extract-bbs", "Extract Basic Blocks From Module (for bugpoint use)");
+}
+
+bool BlockExtractorPass::run(Module &M) {
+  std::set<BasicBlock*> TranslatedBlocksToNotExtract;
+  for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) {
+    BasicBlock *BB = BlocksToNotExtract[i];
+    Function *F = BB->getParent();
+
+    // Map the corresponding function in this module.
+    Function *MF = M.getFunction(F->getName(), F->getFunctionType());
+
+    // Figure out which index the basic block is in its function.
+    Function::iterator BBI = MF->begin();
+    std::advance(BBI, std::distance(F->begin(), Function::iterator(BB)));
+    TranslatedBlocksToNotExtract.insert(BBI);
+  }
+
+  // Now that we know which blocks to not extract, figure out which ones we WANT
+  // to extract.
+  std::vector<BasicBlock*> BlocksToExtract;
+  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
+    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
+      if (!TranslatedBlocksToNotExtract.count(BB))
+        BlocksToExtract.push_back(BB);
+
+  for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i)
+    ExtractBasicBlock(BlocksToExtract[i]);
+  
+  return !BlocksToExtract.empty();
+}
+
+/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks
+/// into their own functions.  The only detail is that M is actually a module
+/// cloned from the one the BBs are in, so some mapping needs to be performed.
+/// If this operation fails for some reason (ie the implementation is buggy),
+/// this function should return null, otherwise it returns a new Module.
+Module *BugDriver::ExtractMappedBlocksFromModule(const
+                                                 std::vector<BasicBlock*> &BBs,
+                                                 Module *M) {
+  // Set the global list so that pass will be able to access it.
+  BlocksToNotExtract = BBs;
+
+  std::vector<const PassInfo*> PI;
+  PI.push_back(getPI(new BlockExtractorPass()));
+  Module *Ret = runPassesOn(M, PI);
+  BlocksToNotExtract.clear();
+  if (Ret == 0)
+    std::cout << "*** Basic Block extraction failed, please report a bug!\n";
+  return Ret;
+}
diff --git a/tools/bugpoint/Miscompilation.cpp b/tools/bugpoint/Miscompilation.cpp
index 3e532226b9..adbc62d3eb 100644
--- a/tools/bugpoint/Miscompilation.cpp
+++ b/tools/bugpoint/Miscompilation.cpp
@@ -29,6 +29,10 @@ using namespace llvm;
 
 namespace llvm {
   extern cl::list<std::string> InputArgv;
+  cl::opt<bool>
+  EnableBlockExtraction("enable-block-extraction",
+                        cl::desc("Enable basic block extraction for "
+                                 "miscompilation debugging (experimental)"));
 }
 
 namespace {
@@ -320,6 +324,95 @@ static bool ExtractLoops(BugDriver &BD,
   }
 }
 
+namespace {
+  class ReduceMiscompiledBlocks : public ListReducer<BasicBlock*> {
+    BugDriver &BD;
+    bool (*TestFn)(BugDriver &, Module *, Module *);
+    std::vector<Function*> FunctionsBeingTested;
+  public:
+    ReduceMiscompiledBlocks(BugDriver &bd,
+                            bool (*F)(BugDriver &, Module *, Module *),
+                            const std::vector<Function*> &Fns)
+      : BD(bd), TestFn(F), FunctionsBeingTested(Fns) {}
+    
+    virtual TestResult doTest(std::vector<BasicBlock*> &Prefix,
+                              std::vector<BasicBlock*> &Suffix) {
+      if (!Suffix.empty() && TestFuncs(Suffix))
+        return KeepSuffix;
+      if (TestFuncs(Prefix))
+        return KeepPrefix;
+      return NoFailure;
+    }
+    
+    bool TestFuncs(const std::vector<BasicBlock*> &Prefix);
+  };
+}
+
+/// TestFuncs - Extract all blocks for the miscompiled functions except for the
+/// specified blocks.  If the problem still exists, return true.
+///
+bool ReduceMiscompiledBlocks::TestFuncs(const std::vector<BasicBlock*> &BBs) {
+  // Test to see if the function is misoptimized if we ONLY run it on the
+  // functions listed in Funcs.
+  std::cout << "Checking to see if the program is misoptimized when all but "
+            << "these " << BBs.size() << " blocks are extracted: ";
+  for (unsigned i = 0, e = BBs.size() < 10 ? BBs.size() : 10; i != e; ++i)
+    std::cout << BBs[i]->getName() << " ";
+  if (BBs.size() > 10) std::cout << "...";
+  std::cout << "\n";
+
+  // Split the module into the two halves of the program we want.
+  Module *ToNotOptimize = CloneModule(BD.getProgram());
+  Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
+                                                 FunctionsBeingTested);
+
+  // Try the extraction.  If it doesn't work, then the block extractor crashed
+  // or something, in which case bugpoint can't chase down this possibility.
+  if (Module *New = BD.ExtractMappedBlocksFromModule(BBs, ToOptimize)) {
+    delete ToOptimize;
+    // Run the predicate, not that the predicate will delete both input modules.
+    return TestFn(BD, New, ToNotOptimize);
+  }
+  delete ToOptimize;
+  delete ToNotOptimize;
+  return false;
+}
+
+
+/// ExtractBlocks - Given a reduced list of functions that still expose the bug,
+/// extract as many basic blocks from the region as possible without obscuring
+/// the bug.
+///
+static bool ExtractBlocks(BugDriver &BD,
+                          bool (*TestFn)(BugDriver &, Module *, Module *),
+                          std::vector<Function*> &MiscompiledFunctions) {
+  // Not enabled??
+  if (!EnableBlockExtraction) return false;
+
+  std::vector<BasicBlock*> Blocks;
+  for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i)
+    for (Function::iterator I = MiscompiledFunctions[i]->begin(),
+           E = MiscompiledFunctions[i]->end(); I != E; ++I)
+      Blocks.push_back(I);
+
+  // Use the list reducer to identify blocks that can be extracted without
+  // obscuring the bug.  The Blocks list will end up containing blocks that must
+  // be retained from the original program.
+  unsigned OldSize = Blocks.size();
+  ReduceMiscompiledBlocks(BD, TestFn, MiscompiledFunctions).reduceList(Blocks);
+  if (Blocks.size() == OldSize)
+    return false;
+
+
+
+  // FIXME: This should actually update the module in the bugdriver!
+
+
+
+  return false;
+}
+
+
 /// DebugAMiscompilation - This is a generic driver to narrow down
 /// miscompilations, either in an optimization or a code generator.
 ///
@@ -366,6 +459,25 @@ DebugAMiscompilation(BugDriver &BD,
     std::cout << "\n";
   }
 
+  if (ExtractBlocks(BD, TestFn, MiscompiledFunctions)) {
+    // Okay, we extracted some blocks and the problem still appears.  See if we
+    // can eliminate some of the created functions from being candidates.
+
+    // Block extraction can introduce functions with the same name (foo_code).
+    // Make sure to disambiguate the symbols so that when the program is split
+    // apart that we can link it back together again.
+    DisambiguateGlobalSymbols(BD.getProgram());
+
+    // Do the reduction...
+    ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions);
+    
+    std::cout << "\n*** The following function"
+              << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
+              << " being miscompiled: ";
+    PrintFunctionList(MiscompiledFunctions);
+    std::cout << "\n";
+  }
+
   return MiscompiledFunctions;
 }