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