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 void writeOutput(llvm::Module *M, llvm::StringRef Message); 25 26 bool IsReduced(Module &M, TestRunner &Test, SmallString<128> &CurrentFilepath) { 27 // Write Module to tmp file 28 int FD; 29 std::error_code EC = 30 sys::fs::createTemporaryFile("llvm-reduce", "ll", FD, CurrentFilepath); 31 if (EC) { 32 errs() << "Error making unique filename: " << EC.message() << "!\n"; 33 exit(1); 34 } 35 36 ToolOutputFile Out(CurrentFilepath, FD); 37 M.print(Out.os(), /*AnnotationWriter=*/nullptr); 38 Out.os().close(); 39 if (Out.os().has_error()) { 40 errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n"; 41 exit(1); 42 } 43 44 // Current Chunks aren't interesting 45 return Test.run(CurrentFilepath); 46 } 47 48 /// Counts the amount of lines for a given file 49 static int getLines(StringRef Filepath) { 50 int Lines = 0; 51 std::string CurrLine; 52 std::ifstream FileStream{std::string(Filepath)}; 53 54 while (std::getline(FileStream, CurrLine)) 55 ++Lines; 56 57 return Lines; 58 } 59 60 /// Splits Chunks in half and prints them. 61 /// If unable to split (when chunk size is 1) returns false. 62 static bool increaseGranularity(std::vector<Chunk> &Chunks) { 63 errs() << "Increasing granularity..."; 64 std::vector<Chunk> NewChunks; 65 bool SplitOne = false; 66 67 for (auto &C : Chunks) { 68 if (C.end - C.begin == 0) 69 NewChunks.push_back(C); 70 else { 71 int Half = (C.begin + C.end) / 2; 72 NewChunks.push_back({C.begin, Half}); 73 NewChunks.push_back({Half + 1, C.end}); 74 SplitOne = true; 75 } 76 } 77 if (SplitOne) { 78 Chunks = NewChunks; 79 errs() << "Success! New Chunks:\n"; 80 for (auto C : Chunks) { 81 errs() << '\t'; 82 C.print(); 83 errs() << '\n'; 84 } 85 } 86 return SplitOne; 87 } 88 89 /// Runs the Delta Debugging algorithm, splits the code into chunks and 90 /// reduces the amount of chunks that are considered interesting by the 91 /// given test. 92 void llvm::runDeltaPass( 93 TestRunner &Test, int Targets, 94 std::function<void(const std::vector<Chunk> &, Module *)> 95 ExtractChunksFromModule) { 96 assert(Targets >= 0); 97 if (!Targets) { 98 errs() << "\nNothing to reduce\n"; 99 return; 100 } 101 102 if (Module *Program = Test.getProgram()) { 103 SmallString<128> CurrentFilepath; 104 if (!IsReduced(*Program, Test, CurrentFilepath)) { 105 errs() << "\nInput isn't interesting! Verify interesting-ness test\n"; 106 exit(1); 107 } 108 } 109 110 std::vector<Chunk> ChunksStillConsideredInteresting = {{1, Targets}}; 111 std::unique_ptr<Module> ReducedProgram; 112 113 bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity; 114 do { 115 FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false; 116 117 std::set<Chunk> UninterestingChunks; 118 for (Chunk &ChunkToCheckForUninterestingness : 119 reverse(ChunksStillConsideredInteresting)) { 120 // Take all of ChunksStillConsideredInteresting chunks, except those we've 121 // already deemed uninteresting (UninterestingChunks) but didn't remove 122 // from ChunksStillConsideredInteresting yet, and additionally ignore 123 // ChunkToCheckForUninterestingness chunk. 124 std::vector<Chunk> CurrentChunks; 125 CurrentChunks.reserve(ChunksStillConsideredInteresting.size() - 126 UninterestingChunks.size() - 1); 127 copy_if(ChunksStillConsideredInteresting, 128 std::back_inserter(CurrentChunks), [&](const Chunk &C) { 129 return !UninterestingChunks.count(C) && 130 C != ChunkToCheckForUninterestingness; 131 }); 132 133 // Clone module before hacking it up.. 134 std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram()); 135 // Generate Module with only Targets inside Current Chunks 136 ExtractChunksFromModule(CurrentChunks, Clone.get()); 137 138 errs() << "Ignoring: "; 139 ChunkToCheckForUninterestingness.print(); 140 for (const Chunk &C : UninterestingChunks) 141 C.print(); 142 143 SmallString<128> CurrentFilepath; 144 if (!IsReduced(*Clone, Test, CurrentFilepath)) { 145 // Program became non-reduced, so this chunk appears to be interesting. 146 errs() << "\n"; 147 continue; 148 } 149 150 FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true; 151 UninterestingChunks.insert(ChunkToCheckForUninterestingness); 152 ReducedProgram = std::move(Clone); 153 errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n"; 154 writeOutput(ReducedProgram.get(), "Saved new best reduction to "); 155 } 156 // Delete uninteresting chunks 157 erase_if(ChunksStillConsideredInteresting, 158 [&UninterestingChunks](const Chunk &C) { 159 return UninterestingChunks.count(C); 160 }); 161 } while (!ChunksStillConsideredInteresting.empty() && 162 (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity || 163 increaseGranularity(ChunksStillConsideredInteresting))); 164 165 // If we reduced the testcase replace it 166 if (ReducedProgram) 167 Test.setProgram(std::move(ReducedProgram)); 168 errs() << "Couldn't increase anymore.\n"; 169 } 170