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