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

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

506–507

Range-based for loop?

521–522

Range-based for loops?

524

auto *

539

Range-based for loops?

540

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

565

Range-based for loop?

566

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

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

Space before the {

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);
+  for (auto *BB : Unreachable) {
+    BB->dropAllReferences();
+    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 (unsigned i = 0, e = BBs.size(); i != e; ++i)
+    Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
+
+  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 (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
+    for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB)
+      if (!Blocks.count(&*BB)) {
+        BranchInst *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());
+
+  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
+    SmallVector<BasicBlock *, 16> BBs;
+    for (auto &BB : *I)
+      if (!Blocks.count(&BB))
+        BBs.push_back(&BB);
+    simpleSimplifyCfg(*I, BBs);
+  }
+  // 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 (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
+      Function *F = cast<Function>(GST.lookup(BlockInfo[i].first));
+      ValueSymbolTable &ST = F->getValueSymbolTable();
+      Value *V = ST.lookup(BlockInfo[i].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())