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
IsReduced(Module & M,TestRunner & Test,SmallString<128> & CurrentFilepath)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
getLines(StringRef Filepath)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.
increaseGranularity(std::vector<Chunk> & Chunks)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.
runDeltaPass(TestRunner & Test,int Targets,std::function<void (const std::vector<Chunk> &,Module *)> ExtractChunksFromModule)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