Add a pass to bugpoint to make it transform conditional jumps into unconditional jumps.

[• dberlin]

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.

[majnemer]

tools/bugpoint/CrashDebugger.cpp

446 ↗

(On Diff #65640)

Is it possible for MergeBlockIntoPredecessor to destroy a block that we haven't yet processed in BBs?

506–507 ↗

(On Diff #65640)

Range-based for loop?

521–522 ↗

(On Diff #65640)

Range-based for loops?

524 ↗

(On Diff #65640)

auto *

539 ↗

(On Diff #65640)

Range-based for loops?

540 ↗

(On Diff #65640)

Hoist this out of the loop and clear on every iteration?

565 ↗

(On Diff #65640)

Range-based for loop?

566 ↗

(On Diff #65640)

auto *

[silvas]

This would have really helped reducing https://llvm.org/bugs/show_bug.cgi?id=28608
Thanks for doing this!

[• dberlin]

tools/bugpoint/CrashDebugger.cpp

446 ↗

(On Diff #65640)

As far as i can tell: No.
It only can destroy block we are processing.

[• dberlin]

• Update for review comments

[majnemer]

LGTM with a nit fixed.

tools/bugpoint/CrashDebugger.cpp

566 ↗

(On Diff #65648)

Space before the {

llvm/trunk/tools/bugpoint/CrashDebugger.cpp

 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Pass.h"
 #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;
 
 namespace {
   cl::opt<bool>
   KeepMain("keep-main",
            cl::desc("Force function reduction to keep main"),
            cl::init(false));
if (TestFn(BD, M)) {
     }
     return true;
   }
   delete M;  // It didn't crash, try something else.
   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.
   ///
   class ReduceCrashingInstructions : public ListReducer<const Instruction*> {
     BugDriver &BD;
     bool (*TestFn)(const BugDriver &, Module *);
   public:
     ReduceCrashingInstructions(BugDriver &bd,
if (Functions.size() > 1 && !BugpointIsInterrupted) {
 
     unsigned OldSize = Functions.size();
     ReduceCrashingFunctions(BD, TestFn).reduceList(Functions, Error);
 
     if (Functions.size() < OldSize)
       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
   // shrinks the code dramatically quickly
   //
   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
     std::vector<const BasicBlock*> Blocks;
     for (Function &F : *BD.getProgram())