diff options
| -rw-r--r-- | llvm/tools/bugpoint/CrashDebugger.cpp | 168 |
1 files changed, 168 insertions, 0 deletions
diff --git a/llvm/tools/bugpoint/CrashDebugger.cpp b/llvm/tools/bugpoint/CrashDebugger.cpp index b25e6ecec19..2555224fde8 100644 --- 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; @@ -431,6 +433,158 @@ bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock*> &BBs) { } 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 |
