+namespace {
+ class ReduceMiscompiledBlocks : public ListReducer<BasicBlock*> {
+ BugDriver &BD;
+ bool (*TestFn)(BugDriver &, Module *, Module *);
+ std::vector<Function*> FunctionsBeingTested;
+ public:
+ ReduceMiscompiledBlocks(BugDriver &bd,
+ bool (*F)(BugDriver &, Module *, Module *),
+ const std::vector<Function*> &Fns)
+ : BD(bd), TestFn(F), FunctionsBeingTested(Fns) {}
+
+ virtual TestResult doTest(std::vector<BasicBlock*> &Prefix,
+ std::vector<BasicBlock*> &Suffix) {
+ if (!Suffix.empty() && TestFuncs(Suffix))
+ return KeepSuffix;
+ if (TestFuncs(Prefix))
+ return KeepPrefix;
+ return NoFailure;
+ }
+
+ bool TestFuncs(const std::vector<BasicBlock*> &Prefix);
+ };
+}
+
+/// TestFuncs - Extract all blocks for the miscompiled functions except for the
+/// specified blocks. If the problem still exists, return true.
+///
+bool ReduceMiscompiledBlocks::TestFuncs(const std::vector<BasicBlock*> &BBs) {
+ // Test to see if the function is misoptimized if we ONLY run it on the
+ // functions listed in Funcs.
+ outs() << "Checking to see if the program is misoptimized when all ";
+ if (!BBs.empty()) {
+ outs() << "but these " << BBs.size() << " blocks are extracted: ";
+ for (unsigned i = 0, e = BBs.size() < 10 ? BBs.size() : 10; i != e; ++i)
+ outs() << BBs[i]->getName() << " ";
+ if (BBs.size() > 10) outs() << "...";
+ } else {
+ outs() << "blocks are extracted.";
+ }
+ outs() << '\n';
+
+ // Split the module into the two halves of the program we want.
+ DenseMap<const Value*, Value*> ValueMap;
+ Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap);
+ Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
+ FunctionsBeingTested,
+ ValueMap);
+
+ // Try the extraction. If it doesn't work, then the block extractor crashed
+ // or something, in which case bugpoint can't chase down this possibility.
+ if (Module *New = BD.ExtractMappedBlocksFromModule(BBs, ToOptimize)) {
+ delete ToOptimize;
+ // Run the predicate, not that the predicate will delete both input modules.
+ return TestFn(BD, New, ToNotOptimize);
+ }
+ delete ToOptimize;
+ delete ToNotOptimize;
+ return false;
+}
+
+
+/// ExtractBlocks - Given a reduced list of functions that still expose the bug,
+/// extract as many basic blocks from the region as possible without obscuring
+/// the bug.
+///
+static bool ExtractBlocks(BugDriver &BD,
+ bool (*TestFn)(BugDriver &, Module *, Module *),
+ std::vector<Function*> &MiscompiledFunctions) {
+ if (BugpointIsInterrupted) return false;
+
+ std::vector<BasicBlock*> Blocks;
+ for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i)
+ for (Function::iterator I = MiscompiledFunctions[i]->begin(),
+ E = MiscompiledFunctions[i]->end(); I != E; ++I)
+ Blocks.push_back(I);
+
+ // Use the list reducer to identify blocks that can be extracted without
+ // obscuring the bug. The Blocks list will end up containing blocks that must
+ // be retained from the original program.
+ unsigned OldSize = Blocks.size();
+
+ // Check to see if all blocks are extractible first.
+ if (ReduceMiscompiledBlocks(BD, TestFn,
+ MiscompiledFunctions).TestFuncs(std::vector<BasicBlock*>())) {
+ Blocks.clear();
+ } else {
+ ReduceMiscompiledBlocks(BD, TestFn,MiscompiledFunctions).reduceList(Blocks);
+ if (Blocks.size() == OldSize)
+ return false;
+ }
+
+ DenseMap<const Value*, Value*> ValueMap;
+ Module *ProgClone = CloneModule(BD.getProgram(), ValueMap);
+ Module *ToExtract = SplitFunctionsOutOfModule(ProgClone,
+ MiscompiledFunctions,
+ ValueMap);
+ Module *Extracted = BD.ExtractMappedBlocksFromModule(Blocks, ToExtract);
+ if (Extracted == 0) {
+ // Weird, extraction should have worked.
+ errs() << "Nondeterministic problem extracting blocks??\n";
+ delete ProgClone;
+ delete ToExtract;
+ return false;
+ }
+
+ // Otherwise, block extraction succeeded. Link the two program fragments back
+ // together.
+ delete ToExtract;
+
+ std::vector<std::pair<std::string, const FunctionType*> > MisCompFunctions;
+ for (Module::iterator I = Extracted->begin(), E = Extracted->end();
+ I != E; ++I)
+ if (!I->isDeclaration())
+ MisCompFunctions.push_back(std::make_pair(I->getName(),
+ I->getFunctionType()));
+
+ std::string ErrorMsg;
+ if (Linker::LinkModules(ProgClone, Extracted, &ErrorMsg)) {
+ errs() << BD.getToolName() << ": Error linking modules together:"
+ << ErrorMsg << '\n';
+ exit(1);
+ }
+ delete Extracted;
+
+ // Set the new program and delete the old one.
+ BD.setNewProgram(ProgClone);
+
+ // Update the list of miscompiled functions.
+ MiscompiledFunctions.clear();
+
+ for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) {
+ Function *NewF = ProgClone->getFunction(MisCompFunctions[i].first);
+ assert(NewF && "Function not found??");
+ assert(NewF->getFunctionType() == MisCompFunctions[i].second &&
+ "Function has wrong type??");
+ MiscompiledFunctions.push_back(NewF);
+ }
+
+ return true;
+}
+
+