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