Index: tools/bugpoint/CrashDebugger.cpp =================================================================== --- tools/bugpoint/CrashDebugger.cpp +++ tools/bugpoint/CrashDebugger.cpp @@ -14,6 +14,7 @@ #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" @@ -28,7 +29,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 using namespace llvm; @@ -320,6 +323,45 @@ 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 &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 Visited; + for (auto *BB : depth_first(&F.getEntryBlock())) + Visited.insert(BB); + + SmallVector 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 @@ -396,19 +438,26 @@ for (BasicBlock *BB : Blocks) BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName()); - - // Now run the CFG simplify pass on the function... + + SmallVector 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 Passes; - Passes.push_back("simplifycfg"); Passes.push_back("verify"); std::unique_ptr 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... @@ -431,6 +480,217 @@ } namespace { +/// 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 { + 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 &Prefix, + std::vector &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 &Prefix); +}; +} + +bool ReduceCrashingConditionals::TestBlocks( + std::vector &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 Blocks; + for (const auto *BB: BBs) + Blocks.insert(cast(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(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> BlockInfo; + + for (const BasicBlock *BB : Blocks) + BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName()); + + SmallVector 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 Passes; + Passes.push_back("verify"); + std::unique_ptr 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(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(V)); + } + 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 { + 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 &Prefix, + std::vector &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 &Prefix); +}; +} + +bool ReduceSimplifyCFG::TestBlocks( + std::vector &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 Blocks; + for (const auto *BB: BBs) + Blocks.insert(cast(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> 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 Passes; + Passes.push_back("verify"); + std::unique_ptr 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(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(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 +1073,20 @@ BD.EmitProgressBitcode(BD.getProgram(), "reduced-function"); } + // Attempt to change conditional branches into unconditional branches to + // eliminate blocks. + if (!DisableSimplifyCFG && !BugpointIsInterrupted) { + std::vector 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 @@ -829,6 +1103,17 @@ BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks"); } + if (!DisableSimplifyCFG & !BugpointIsInterrupted) { + std::vector 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)