Make bugpoint transform conditional jumps into unconditional jumps.

dberlin · dberlin · commit 271ca4011898 · 2016-07-27T16:13:25.000Z
Summary: Add a pass to bugpoint to make it transform conditional jumps into unconditional jumps. Often, bugpoint generates output that has large numbers of br undef jumps, where one side is dead. What is happening is two fold: 1. It never tries to just pick a direction for the jump, and just see what happens <<<< this patch 2. SimplifyCFG no longer is a good match for bugpoint's usecase. It does too much. Even things in SimplifyCFG, like removeUnreachableBlocks, go to great lengths to transform undefined behavior into blocks and kill large parts of the CFG. This is great for regular code, not so much for bugpoint, which often generates UB on purpose (store undef is a great example). <<<< a followup patch that is coming, to move simplifycfg into a separate reduction pass, and move the existing reduceCrashingBlocks pass to use simpleSimplifyCFG. Both of these patches significantly reduce the size and complexity of bugpoint generated testcases. Reviewers: chandlerc, majnemer Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22841 llvm-svn: 276884
diff --git a/llvm/tools/bugpoint/CrashDebugger.cpp b/llvm/tools/bugpoint/CrashDebugger.cpp
@@ -28,7 +28,9 @@
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileUtilities.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <set>
 using namespace llvm;
 
@@ -430,6 +432,158 @@ bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock*> &BBs) {
   return false;
 }
 
+namespace {
+/// Simplify the CFG without completely destroying it.
+/// This is not well defined, but basically comes down to "try to eliminate
+/// unreachable blocks and constant fold terminators without deciding that
+/// certain undefined behavior cuts off the program at the legs".
+void simpleSimplifyCfg(Function &F, SmallVectorImpl<BasicBlock *> &BBs) {
+  if (F.empty())
+    return;
+
+  for (auto *BB : BBs) {
+    ConstantFoldTerminator(BB);
+    MergeBlockIntoPredecessor(BB);
+  }
+
+  // Remove unreachable blocks
+  // removeUnreachableBlocks can't be used here, it will turn various
+  // undefined behavior into unreachables, but bugpoint was the thing that
+  // generated the undefined behavior, and we don't want it to kill the entire
+  // program.
+  SmallPtrSet<BasicBlock *, 16> Visited;
+  for (auto *BB : depth_first(&F.getEntryBlock()))
+    Visited.insert(BB);
+
+  SmallVector<BasicBlock *, 16> Unreachable;
+  for (auto &BB : F)
+    if (!Visited.count(&BB))
+      Unreachable.push_back(&BB);
+
+  // The dead BB's may be in a dead cycle or otherwise have references to each
+  // other.  Because of this, we have to drop all references first, then delete
+  // them all at once.
+  for (auto *BB : Unreachable)  {
+    for (BasicBlock *Successor : successors(&*BB))
+      if (Visited.count(Successor))
+        Successor->removePredecessor(&*BB);
+    BB->dropAllReferences();
+  }
+  for (auto *BB : Unreachable)
+    BB->eraseFromParent();
+}
+
+/// ReduceCrashingConditionals reducer - This works by changing
+/// conditional branches to unconditional ones, then simplifying the CFG
+/// This has the effect of chopping up the CFG really fast which can reduce
+/// large functions quickly.
+///
+class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
+  BugDriver &BD;
+  bool (*TestFn)(const BugDriver &, Module *);
+  bool Direction;
+
+public:
+  ReduceCrashingConditionals(BugDriver &bd,
+                             bool (*testFn)(const BugDriver &, Module *),
+                             bool Direction)
+      : BD(bd), TestFn(testFn), Direction(Direction) {}
+
+  TestResult doTest(std::vector<const BasicBlock *> &Prefix,
+                    std::vector<const BasicBlock *> &Kept,
+                    std::string &Error) override {
+    if (!Kept.empty() && TestBlocks(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestBlocks(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
+};
+}
+
+bool ReduceCrashingConditionals::TestBlocks(
+    std::vector<const BasicBlock *> &BBs) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  Module *M = CloneModule(BD.getProgram(), VMap).release();
+
+  // Convert list to set for fast lookup...
+  SmallPtrSet<const BasicBlock *, 8> Blocks;
+  for (const auto *BB: BBs)
+    Blocks.insert(cast<BasicBlock>(VMap[BB]));
+
+  outs() << "Checking for crash with changing conditionals to always jump to "
+         << (Direction ? "true" : "false") << ":";
+  unsigned NumPrint = Blocks.size();
+  if (NumPrint > 10)
+    NumPrint = 10;
+  for (unsigned i = 0, e = NumPrint; i != e; ++i)
+    outs() << " " << BBs[i]->getName();
+  if (NumPrint < Blocks.size())
+    outs() << "... <" << Blocks.size() << " total>";
+  outs() << ": ";
+
+  // Loop over and delete any hack up any blocks that are not listed...
+  for (auto &F: *M)
+    for (auto &BB : F)
+      if (!Blocks.count(&BB)) {
+        auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
+        if (!BR || !BR->isConditional())
+          continue;
+        if (Direction)
+          BR->setCondition(ConstantInt::getTrue(BR->getContext()));
+        else
+          BR->setCondition(ConstantInt::getFalse(BR->getContext()));
+      }
+
+  // The following may destroy some blocks, so we save them first
+  std::vector<std::pair<std::string, std::string>> BlockInfo;
+
+  for (const BasicBlock *BB : Blocks)
+    BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
+
+  SmallVector<BasicBlock *, 16> ToProcess;
+  for (auto &F :*M) {
+    for (auto &BB : F)
+      if (!Blocks.count(&BB))
+        ToProcess.push_back(&BB);
+    simpleSimplifyCfg(F, ToProcess);
+    ToProcess.clear();
+  }
+  // Verify we didn't break anything
+  std::vector<std::string> Passes;
+  Passes.push_back("verify");
+  std::unique_ptr<Module> New = BD.runPassesOn(M, Passes);
+  delete M;
+  if (!New) {
+    errs() << "verify failed!\n";
+    exit(1);
+  }
+  M = New.release();
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M)) {
+    BD.setNewProgram(M); // It crashed, keep the trimmed version...
+
+    // Make sure to use basic block pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    BBs.clear();
+    const ValueSymbolTable &GST = M->getValueSymbolTable();
+    for (auto &BI : BlockInfo) {
+      auto *F = cast<Function>(GST.lookup(BI.first));
+      ValueSymbolTable &ST = F->getValueSymbolTable();
+      Value *V = ST.lookup(BI.second);
+      if (V && V->getType() == Type::getLabelTy(V->getContext()))
+        BBs.push_back(cast<BasicBlock>(V));
+    }
+    return true;
+  }
+  delete M; // It didn't crash, try something else.
+  return false;
+}
+
 namespace {
   /// ReduceCrashingInstructions reducer - This works by removing the specified
   /// non-terminator instructions and replacing them with undef.
@@ -813,6 +967,20 @@ static bool DebugACrash(BugDriver &BD,
       BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
   }
 
+  // Attempt to change conditional branches into unconditional branches to
+  // eliminate blocks.
+  if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
+    std::vector<const BasicBlock*> Blocks;
+    for (Function &F : *BD.getProgram())
+      for (BasicBlock &BB : F)
+        Blocks.push_back(&BB);
+    unsigned OldSize = Blocks.size();
+    ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks, Error);
+    ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks, Error);
+    if (Blocks.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
+  }
+
   // Attempt to delete entire basic blocks at a time to speed up
   // convergence... this actually works by setting the terminator of the blocks
   // to a return instruction then running simplifycfg, which can potentially
