1 //===- Delta.cpp - Delta Debugging Algorithm Implementation ---------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains the implementation for the Delta Debugging Algorithm: 10 // it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.) 11 // into chunks and tries to reduce the number chunks that are interesting. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "Delta.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/Support/ToolOutputFile.h" 18 #include "llvm/Transforms/Utils/Cloning.h" 19 #include <fstream> 20 #include <set> 21 22 using namespace llvm; 23 24 bool IsReduced(Module &M, TestRunner &Test, SmallString<128> &CurrentFilepath) { 25 // Write Module to tmp file 26 int FD; 27 std::error_code EC = 28 sys::fs::createTemporaryFile("llvm-reduce", "ll", FD, CurrentFilepath); 29 if (EC) { 30 errs() << "Error making unique filename: " << EC.message() << "!\n"; 31 exit(1); 32 } 33 34 ToolOutputFile Out(CurrentFilepath, FD); 35 M.print(Out.os(), /*AnnotationWriter=*/nullptr); 36 Out.os().close(); 37 if (Out.os().has_error()) { 38 errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n"; 39 exit(1); 40 } 41 42 // Current Chunks aren't interesting 43 return Test.run(CurrentFilepath); 44 } 45 46 /// Counts the amount of lines for a given file 47 static int getLines(StringRef Filepath) { 48 int Lines = 0; 49 std::string CurrLine; 50 std::ifstream FileStream(Filepath); 51 52 while (std::getline(FileStream, CurrLine)) 53 ++Lines; 54 55 return Lines; 56 } 57 58 /// Splits Chunks in half and prints them. 59 /// If unable to split (when chunk size is 1) returns false. 60 static bool increaseGranularity(std::vector<Chunk> &Chunks) { 61 errs() << "Increasing granularity..."; 62 std::vector<Chunk> NewChunks; 63 bool SplitOne = false; 64 65 for (auto &C : Chunks) { 66 if (C.end - C.begin == 0) 67 NewChunks.push_back(C); 68 else { 69 int Half = (C.begin + C.end) / 2; 70 NewChunks.push_back({C.begin, Half}); 71 NewChunks.push_back({Half + 1, C.end}); 72 SplitOne = true; 73 } 74 } 75 if (SplitOne) { 76 Chunks = NewChunks; 77 errs() << "Success! New Chunks:\n"; 78 for (auto C : Chunks) { 79 errs() << '\t'; 80 C.print(); 81 errs() << '\n'; 82 } 83 } 84 return SplitOne; 85 } 86 87 /// Runs the Delta Debugging algorithm, splits the code into chunks and 88 /// reduces the amount of chunks that are considered interesting by the 89 /// given test. 90 void llvm::runDeltaPass( 91 TestRunner &Test, int Targets, 92 std::function<void(const std::vector<Chunk> &, Module *)> 93 ExtractChunksFromModule) { 94 assert(Targets >= 0); 95 if (!Targets) { 96 errs() << "\nNothing to reduce\n"; 97 return; 98 } 99 100 if (Module *Program = Test.getProgram()) { 101 SmallString<128> CurrentFilepath; 102 if (!IsReduced(*Program, Test, CurrentFilepath)) { 103 errs() << "\nInput isn't interesting! Verify interesting-ness test\n"; 104 exit(1); 105 } 106 } 107 108 std::vector<Chunk> Chunks = {{1, Targets}}; 109 std::set<Chunk> UninterestingChunks; 110 std::unique_ptr<Module> ReducedProgram; 111 112 if (!increaseGranularity(Chunks)) { 113 errs() << "\nAlready at minimum size. Cannot reduce anymore.\n"; 114 return; 115 } 116 117 do { 118 UninterestingChunks = {}; 119 for (int I = Chunks.size() - 1; I >= 0; --I) { 120 std::vector<Chunk> CurrentChunks; 121 122 for (auto C : Chunks) 123 if (!UninterestingChunks.count(C) && C != Chunks[I]) 124 CurrentChunks.push_back(C); 125 126 if (CurrentChunks.empty()) 127 continue; 128 129 // Clone module before hacking it up.. 130 std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram()); 131 // Generate Module with only Targets inside Current Chunks 132 ExtractChunksFromModule(CurrentChunks, Clone.get()); 133 134 errs() << "Ignoring: "; 135 Chunks[I].print(); 136 for (auto C : UninterestingChunks) 137 C.print(); 138 139 140 141 SmallString<128> CurrentFilepath; 142 if (!IsReduced(*Clone, Test, CurrentFilepath)) { 143 errs() << "\n"; 144 continue; 145 } 146 147 UninterestingChunks.insert(Chunks[I]); 148 ReducedProgram = std::move(Clone); 149 errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n"; 150 } 151 // Delete uninteresting chunks 152 erase_if(Chunks, [&UninterestingChunks](const Chunk &C) { 153 return UninterestingChunks.count(C); 154 }); 155 156 } while (!UninterestingChunks.empty() || increaseGranularity(Chunks)); 157 158 // If we reduced the testcase replace it 159 if (ReducedProgram) 160 Test.setProgram(std::move(ReducedProgram)); 161 errs() << "Couldn't increase anymore.\n"; 162 } 163