Rework CFG simplification in bugpoint

[• dberlin]

Summary

Depends on D22841

We now use a much simpler CFG simplification routine for bugpoint,
because SimplifyCFG is no longer a good match for what bugpoint wants
to do.

At the same time, to make sure we don't lose anything valuable it was doing,
SimplifyCFG is now run as a per-BB reduction pass.

With this and D22841 combined, bugpoint operates both much faster on
the large testcases i have, and reduces them to pretty much minimal
testcases (in one case, bugpoint used to leave about 6000 useless blocks, and
now it leaves 3 ...)

[• dberlin]

(arc seems to have messed up on the diff of the diff, i'll fix it)

[• dberlin]

Fixing ARC diff

[majnemer]

LGTM

tools/bugpoint/CrashDebugger.cpp

604–605 ↗

(On Diff #65664)

I'd use BD and TestFn here, the lookup rules inside the initializers will find the right one.

llvm/trunk/tools/bugpoint/CrashDebugger.cpp

 //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the bugpoint internals that narrow down compilation crashes
 //
 //===----------------------------------------------------------------------===//
 
 #include "BugDriver.h"
 #include "ListReducer.h"
 #include "ToolRunner.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Module.h"
if (TestFn(BD, M)) {
     // module.
     Funcs.assign(Functions.begin(), Functions.end());
     return true;
   }
   delete M;
   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();
+}
   /// ReduceCrashingBlocks reducer - This works by setting the terminators of
   /// all terminators except the specified basic blocks to a 'ret' instruction,
   /// then running the simplify-cfg pass.  This has the effect of chopping up
   /// the CFG really fast which can reduce large functions quickly.
   ///
   class ReduceCrashingBlocks : public ListReducer<const BasicBlock*> {
     BugDriver &BD;
     bool (*TestFn)(const BugDriver &, Module *);
   public:
-    ReduceCrashingBlocks(BugDriver &bd,
+    ReduceCrashingBlocks(BugDriver &BD,
                          bool (*testFn)(const BugDriver &, Module *))
-      : BD(bd), TestFn(testFn) {}
+      : BD(BD), TestFn(testFn) {}
 
     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;
bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock*> &BBs) {
   // interested in.  If it does we need to take the block out of the list.  Make
   // a "persistent mapping" by turning basic blocks into <function, name> pairs.
   // This won't work well if blocks are unnamed, but that is just the risk we
   // have to take.
   std::vector<std::pair<std::string, std::string> > BlockInfo;
 
   for (BasicBlock *BB : Blocks)
     BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
   
-  // Now run the CFG simplify pass on the function...
+  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("simplifycfg");
   Passes.push_back("verify");
   std::unique_ptr<Module> New = BD.runPassesOn(M, Passes);
   delete M;
   if (!New) {
-    errs() << "simplifycfg failed!\n";
+    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 {
-/// 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 *);
if (TestFn(BD, M)) {
     }
     return true;
   }
   delete M; // It didn't crash, try something else.
   return false;
 }
 
 namespace {
+/// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
+/// in the program.
+
+class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
+  BugDriver &BD;
+  bool (*TestFn)(const BugDriver &, Module *);
+  TargetTransformInfo TTI;
+  
+public:
+  ReduceSimplifyCFG(BugDriver &bd,
+                    bool (*testFn)(const BugDriver &, Module *))
+      : BD(bd), TestFn(testFn), TTI(bd.getProgram()->getDataLayout())
+  {}
+
+  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 ReduceSimplifyCFG::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 CFG simplifying:";
+  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() << ": ";
+
+    // 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());
+
+
+  // Loop over and delete any hack up any blocks that are not listed...
+  for (auto &F: *M) 
+     // Loop over all of the basic blocks and remove them if they are unneeded.
+     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
+       if (!Blocks.count(&*BBIt)) {
+         ++BBIt;
+         continue;
+       }
+       SimplifyCFG(&*BBIt++, TTI, 1);
+     }
+  // 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,
for (Function &F : *BD.getProgram())
       for (BasicBlock &BB : F)
         Blocks.push_back(&BB);
     unsigned OldSize = Blocks.size();
     ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks, Error);
     if (Blocks.size() < OldSize)
       BD.EmitProgressBitcode(BD.getProgram(), "reduced-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();
+    ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks, Error);
+    if (Blocks.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
+  }
+  
   // Attempt to delete instructions using bisection. This should help out nasty
   // cases with large basic blocks where the problem is at one end.
   if (!BugpointIsInterrupted)
     ReduceInsts(BD, TestFn, Error);
 
   if (!NoNamedMDRM) {
     if (!BugpointIsInterrupted) {
       // Try to reduce the amount of global metadata (particularly debug info),