From 286921e8d21d4f0655905ed278d0e140829c7d1f Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 24 Apr 2003 23:51:38 +0000 Subject: [PATCH] Speed up convergence significantly and also reduce the size of testcases by making large portions of a function's CFG dead at a time. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5915 91177308-0d34-0410-b5e6-96231b3b80d8 --- tools/bugpoint/BugDriver.h | 2 + tools/bugpoint/CrashDebugger.cpp | 124 ++++++++++++++++++++++++++++++- 2 files changed, 123 insertions(+), 3 deletions(-) diff --git a/tools/bugpoint/BugDriver.h b/tools/bugpoint/BugDriver.h index 79319894a7b..05d4108824a 100644 --- a/tools/bugpoint/BugDriver.h +++ b/tools/bugpoint/BugDriver.h @@ -21,6 +21,7 @@ class DebugCrashes; class ReduceMiscompilingPasses; class ReduceMiscompilingFunctions; class ReduceCrashingFunctions; +class ReduceCrashingBlocks; class BugDriver { const std::string ToolName; // Name of bugpoint @@ -33,6 +34,7 @@ class BugDriver { friend class ReduceMiscompilingPasses; friend class ReduceMiscompilingFunctions; friend class ReduceCrashingFunctions; + friend class ReduceCrashingBlocks; public: BugDriver(const char *toolname) : ToolName(toolname), Program(0), Interpreter(0) {} diff --git a/tools/bugpoint/CrashDebugger.cpp b/tools/bugpoint/CrashDebugger.cpp index f3b2dc2bdf8..2d224f3fbad 100644 --- a/tools/bugpoint/CrashDebugger.cpp +++ b/tools/bugpoint/CrashDebugger.cpp @@ -8,9 +8,17 @@ #include "SystemUtils.h" #include "ListReducer.h" #include "llvm/Module.h" +#include "llvm/PassManager.h" +#include "llvm/Pass.h" +#include "llvm/Constant.h" +#include "llvm/iTerminators.h" +#include "llvm/Type.h" +#include "llvm/SymbolTable.h" +#include "llvm/Support/CFG.h" +#include "llvm/Analysis/Verifier.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Bytecode/Writer.h" -#include "llvm/Pass.h" #include #include @@ -117,6 +125,108 @@ bool ReduceCrashingFunctions::TestFuncs(std::vector &Funcs) { } +/// 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 { + BugDriver &BD; +public: + ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) { + if (TestBlocks(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestBlocks(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestBlocks(std::vector &Prefix); +}; + +bool ReduceCrashingBlocks::TestBlocks(std::vector &BBs) { + // Clone the program to try hacking it appart... + Module *M = CloneModule(BD.Program); + + // Convert list to set for fast lookup... + std::set Blocks; + for (unsigned i = 0, e = BBs.size(); i != e; ++i) { + // Convert the basic block from the original module to the new module... + Function *F = BBs[i]->getParent(); + Function *CMF = M->getFunction(F->getName(), F->getFunctionType()); + assert(CMF && "Function not in module?!"); + + // Get the mapped basic block... + Function::iterator CBI = CMF->begin(); + std::advance(CBI, std::distance(F->begin(), Function::iterator(BBs[i]))); + Blocks.insert(CBI); + } + + std::cout << "Checking for crash with only these blocks:"; + for (unsigned i = 0, e = Blocks.size(); i != e; ++i) + std::cout << " " << BBs[i]->getName(); + std::cout << ": "; + + // 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) && !isa(BB->getTerminator())) { + // Loop over all of the successors of this block, deleting any PHI nodes + // that might include it. + for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) + (*SI)->removePredecessor(BB); + + // Delete the old terminator instruction... + BB->getInstList().pop_back(); + + // Add a new return instruction of the appropriate type... + const Type *RetTy = BB->getParent()->getReturnType(); + ReturnInst *RI = new ReturnInst(RetTy == Type::VoidTy ? 0 : + Constant::getNullValue(RetTy)); + BB->getInstList().push_back(RI); + } + + // The CFG Simplifier pass may delete one of the basic blocks we are + // interested in. If it does we need to take the block out of the list. Make + // a "persistent mapping" by turning basic blocks into pairs. + // This won't work well if blocks are unnamed, but that is just the risk we + // have to take. + std::vector > BlockInfo; + + for (std::set::iterator I = Blocks.begin(), E = Blocks.end(); + I != E; ++I) + BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName())); + + // Now run the CFG simplify pass on the function... + PassManager Passes; + Passes.add(createCFGSimplificationPass()); + Passes.add(createVerifierPass()); + Passes.run(*M); + + // Try running on the hacked up program... + std::swap(BD.Program, M); + if (BD.runPasses(BD.PassesToRun)) { + delete 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(); + for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { + SymbolTable &ST = BlockInfo[i].first->getSymbolTable(); + SymbolTable::iterator I = ST.find(Type::LabelTy); + if (I != ST.end() && I->second.count(BlockInfo[i].second)) + BBs.push_back(cast(I->second[BlockInfo[i].second])); + } + return true; + } + delete BD.Program; // It didn't crash, revert... + BD.Program = M; + return false; +} + /// debugCrash - This method is called when some pass crashes on input. It /// attempts to prune down the testcase to something reasonable, and figure /// out exactly which pass is crashing. @@ -154,8 +264,16 @@ bool BugDriver::debugCrash() { } } - // FIXME: This should attempt to delete entire basic blocks at a time to speed - // up convergence... + // 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 + // + std::vector Blocks; + for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) + for (Function::iterator FI = I->begin(), E = I->end(); FI != E; ++FI) + Blocks.push_back(FI); + ReduceCrashingBlocks(*this).reduceList(Blocks); // FIXME: This should use the list reducer to converge faster by deleting // larger chunks of instructions at a time! -- 2.34.1