xref: /openbsd-src/gnu/llvm/llvm/tools/llvm-reduce/deltas/Delta.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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 "ReducerWorkItem.h"
17 #include "TestRunner.h"
18 #include "Utils.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
21 #include "llvm/Analysis/ProfileSummaryInfo.h"
22 #include "llvm/Bitcode/BitcodeReader.h"
23 #include "llvm/Bitcode/BitcodeWriter.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/Verifier.h"
27 #include "llvm/MC/TargetRegistry.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/MemoryBufferRef.h"
30 #include "llvm/Support/ThreadPool.h"
31 #include <fstream>
32 #include <set>
33 
34 using namespace llvm;
35 
36 extern cl::OptionCategory LLVMReduceOptions;
37 
38 static cl::opt<bool> AbortOnInvalidReduction(
39     "abort-on-invalid-reduction",
40     cl::desc("Abort if any reduction results in invalid IR"),
41     cl::cat(LLVMReduceOptions));
42 
43 static cl::opt<unsigned int> StartingGranularityLevel(
44     "starting-granularity-level",
45     cl::desc("Number of times to divide chunks prior to first test"),
46     cl::cat(LLVMReduceOptions));
47 
48 #ifdef LLVM_ENABLE_THREADS
49 static cl::opt<unsigned> NumJobs(
50     "j",
51     cl::desc("Maximum number of threads to use to process chunks. Set to 1 to "
52              "disable parallelism."),
53     cl::init(1), cl::cat(LLVMReduceOptions));
54 #else
55 unsigned NumJobs = 1;
56 #endif
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   if (Verbose)
62     errs() << "Increasing granularity...";
63   std::vector<Chunk> NewChunks;
64   bool SplitAny = false;
65 
66   for (Chunk C : Chunks) {
67     if (C.End - C.Begin == 0)
68       NewChunks.push_back(C);
69     else {
70       int Half = (C.Begin + C.End) / 2;
71       NewChunks.push_back({C.Begin, Half});
72       NewChunks.push_back({Half + 1, C.End});
73       SplitAny = true;
74     }
75   }
76   if (SplitAny) {
77     Chunks = NewChunks;
78     if (Verbose) {
79       errs() << "Success! " << NewChunks.size() << " New Chunks:\n";
80       for (auto C : Chunks) {
81         errs() << '\t';
82         C.print();
83         errs() << '\n';
84       }
85     }
86   }
87   return SplitAny;
88 }
89 
90 // Check if \p ChunkToCheckForUninterestingness is interesting. Returns the
91 // modified module if the chunk resulted in a reduction.
92 static std::unique_ptr<ReducerWorkItem>
CheckChunk(const Chunk ChunkToCheckForUninterestingness,std::unique_ptr<ReducerWorkItem> Clone,const TestRunner & Test,ReductionFunc ExtractChunksFromModule,const DenseSet<Chunk> & UninterestingChunks,const std::vector<Chunk> & ChunksStillConsideredInteresting)93 CheckChunk(const Chunk ChunkToCheckForUninterestingness,
94            std::unique_ptr<ReducerWorkItem> Clone, const TestRunner &Test,
95            ReductionFunc ExtractChunksFromModule,
96            const DenseSet<Chunk> &UninterestingChunks,
97            const std::vector<Chunk> &ChunksStillConsideredInteresting) {
98   // Take all of ChunksStillConsideredInteresting chunks, except those we've
99   // already deemed uninteresting (UninterestingChunks) but didn't remove
100   // from ChunksStillConsideredInteresting yet, and additionally ignore
101   // ChunkToCheckForUninterestingness chunk.
102   std::vector<Chunk> CurrentChunks;
103   CurrentChunks.reserve(ChunksStillConsideredInteresting.size() -
104                         UninterestingChunks.size() - 1);
105   copy_if(ChunksStillConsideredInteresting, std::back_inserter(CurrentChunks),
106           [&](const Chunk &C) {
107             return C != ChunkToCheckForUninterestingness &&
108                    !UninterestingChunks.count(C);
109           });
110 
111   // Generate Module with only Targets inside Current Chunks
112   Oracle O(CurrentChunks);
113   ExtractChunksFromModule(O, *Clone);
114 
115   // Some reductions may result in invalid IR. Skip such reductions.
116   if (Clone->verify(&errs())) {
117     if (AbortOnInvalidReduction) {
118       errs() << "Invalid reduction, aborting.\n";
119       Clone->print(errs());
120       exit(1);
121     }
122     if (Verbose) {
123       errs() << " **** WARNING | reduction resulted in invalid module, "
124                 "skipping\n";
125     }
126     return nullptr;
127   }
128 
129   if (Verbose) {
130     errs() << "Ignoring: ";
131     ChunkToCheckForUninterestingness.print();
132     for (const Chunk &C : UninterestingChunks)
133       C.print();
134     errs() << "\n";
135   }
136 
137   if (!Clone->isReduced(Test)) {
138     // Program became non-reduced, so this chunk appears to be interesting.
139     if (Verbose)
140       errs() << "\n";
141     return nullptr;
142   }
143   return Clone;
144 }
145 
ProcessChunkFromSerializedBitcode(const Chunk ChunkToCheckForUninterestingness,const TestRunner & Test,ReductionFunc ExtractChunksFromModule,const DenseSet<Chunk> & UninterestingChunks,ArrayRef<Chunk> ChunksStillConsideredInteresting,StringRef OriginalBC,std::atomic<bool> & AnyReduced)146 static SmallString<0> ProcessChunkFromSerializedBitcode(
147     const Chunk ChunkToCheckForUninterestingness, const TestRunner &Test,
148     ReductionFunc ExtractChunksFromModule,
149     const DenseSet<Chunk> &UninterestingChunks,
150     ArrayRef<Chunk> ChunksStillConsideredInteresting, StringRef OriginalBC,
151     std::atomic<bool> &AnyReduced) {
152   LLVMContext Ctx;
153   auto CloneMMM = std::make_unique<ReducerWorkItem>();
154   MemoryBufferRef Data(OriginalBC, "<bc file>");
155   CloneMMM->readBitcode(Data, Ctx, Test.getToolName());
156 
157   SmallString<0> Result;
158   if (std::unique_ptr<ReducerWorkItem> ChunkResult =
159           CheckChunk(ChunkToCheckForUninterestingness, std::move(CloneMMM),
160                      Test, ExtractChunksFromModule, UninterestingChunks,
161                      ChunksStillConsideredInteresting)) {
162     raw_svector_ostream BCOS(Result);
163     ChunkResult->writeBitcode(BCOS);
164     // Communicate that the task reduced a chunk.
165     AnyReduced = true;
166   }
167   return Result;
168 }
169 
170 using SharedTaskQueue = std::deque<std::shared_future<SmallString<0>>>;
171 
waitAndDiscardResultsBarrier(SharedTaskQueue & TaskQueue)172 static void waitAndDiscardResultsBarrier(SharedTaskQueue &TaskQueue) {
173   while (!TaskQueue.empty()) {
174     auto &Future = TaskQueue.front();
175     Future.wait();
176     TaskQueue.pop_front();
177   }
178 }
179 
180 /// Runs the Delta Debugging algorithm, splits the code into chunks and
181 /// reduces the amount of chunks that are considered interesting by the
182 /// given test. The number of chunks is determined by a preliminary run of the
183 /// reduction pass where no change must be made to the module.
runDeltaPass(TestRunner & Test,ReductionFunc ExtractChunksFromModule,StringRef Message)184 void llvm::runDeltaPass(TestRunner &Test, ReductionFunc ExtractChunksFromModule,
185                         StringRef Message) {
186   assert(!Test.getProgram().verify(&errs()) &&
187          "input module is broken before making changes");
188   errs() << "*** " << Message << "...\n";
189 
190   int Targets;
191   {
192     // Count the number of chunks by counting the number of calls to
193     // Oracle::shouldKeep() but always returning true so no changes are
194     // made.
195     std::vector<Chunk> AllChunks = {{0, INT_MAX}};
196     Oracle Counter(AllChunks);
197     ExtractChunksFromModule(Counter, Test.getProgram());
198     Targets = Counter.count();
199 
200     assert(!Test.getProgram().verify(&errs()) &&
201            "input module is broken after counting chunks");
202     assert(Test.getProgram().isReduced(Test) &&
203            "input module no longer interesting after counting chunks");
204 
205 #ifndef NDEBUG
206     // Make sure that the number of chunks does not change as we reduce.
207     std::vector<Chunk> NoChunks = {{0, INT_MAX}};
208     Oracle NoChunksCounter(NoChunks);
209     std::unique_ptr<ReducerWorkItem> Clone =
210       Test.getProgram().clone(Test.getTargetMachine());
211     ExtractChunksFromModule(NoChunksCounter, *Clone);
212     assert(Targets == NoChunksCounter.count() &&
213            "number of chunks changes when reducing");
214 #endif
215   }
216   if (!Targets) {
217     if (Verbose)
218       errs() << "\nNothing to reduce\n";
219     errs() << "----------------------------\n";
220     return;
221   }
222 
223   std::vector<Chunk> ChunksStillConsideredInteresting = {{0, Targets - 1}};
224   std::unique_ptr<ReducerWorkItem> ReducedProgram;
225 
226   for (unsigned int Level = 0; Level < StartingGranularityLevel; Level++) {
227     increaseGranularity(ChunksStillConsideredInteresting);
228   }
229 
230   std::atomic<bool> AnyReduced;
231   std::unique_ptr<ThreadPool> ChunkThreadPoolPtr;
232   if (NumJobs > 1)
233     ChunkThreadPoolPtr =
234         std::make_unique<ThreadPool>(hardware_concurrency(NumJobs));
235 
236   bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity;
237   do {
238     FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false;
239 
240     DenseSet<Chunk> UninterestingChunks;
241 
242     // When running with more than one thread, serialize the original bitcode
243     // to OriginalBC.
244     SmallString<0> OriginalBC;
245     if (NumJobs > 1) {
246       raw_svector_ostream BCOS(OriginalBC);
247       Test.getProgram().writeBitcode(BCOS);
248     }
249 
250     SharedTaskQueue TaskQueue;
251     for (auto I = ChunksStillConsideredInteresting.rbegin(),
252               E = ChunksStillConsideredInteresting.rend();
253          I != E; ++I) {
254       std::unique_ptr<ReducerWorkItem> Result = nullptr;
255       unsigned WorkLeft = std::distance(I, E);
256 
257       // Run in parallel mode, if the user requested more than one thread and
258       // there are at least a few chunks to process.
259       if (NumJobs > 1 && WorkLeft > 1) {
260         unsigned NumInitialTasks = std::min(WorkLeft, unsigned(NumJobs));
261         unsigned NumChunksProcessed = 0;
262 
263         ThreadPool &ChunkThreadPool = *ChunkThreadPoolPtr;
264         TaskQueue.clear();
265 
266         AnyReduced = false;
267         // Queue jobs to process NumInitialTasks chunks in parallel using
268         // ChunkThreadPool. When the tasks are added to the pool, parse the
269         // original module from OriginalBC with a fresh LLVMContext object. This
270         // ensures that the cloned module of each task uses an independent
271         // LLVMContext object. If a task reduces the input, serialize the result
272         // back in the corresponding Result element.
273         for (unsigned J = 0; J < NumInitialTasks; ++J) {
274           Chunk ChunkToCheck = *(I + J);
275           TaskQueue.emplace_back(ChunkThreadPool.async(
276               ProcessChunkFromSerializedBitcode, ChunkToCheck, std::ref(Test),
277               ExtractChunksFromModule, UninterestingChunks,
278               ChunksStillConsideredInteresting, OriginalBC,
279               std::ref(AnyReduced)));
280         }
281 
282         // Start processing results of the queued tasks. We wait for the first
283         // task in the queue to finish. If it reduced a chunk, we parse the
284         // result and exit the loop.
285         //  Otherwise we will try to schedule a new task, if
286         //  * no other pending job reduced a chunk and
287         //  * we have not reached the end of the chunk.
288         while (!TaskQueue.empty()) {
289           auto &Future = TaskQueue.front();
290           Future.wait();
291 
292           NumChunksProcessed++;
293           SmallString<0> Res = Future.get();
294           TaskQueue.pop_front();
295           if (Res.empty()) {
296             unsigned NumScheduledTasks = NumChunksProcessed + TaskQueue.size();
297             if (!AnyReduced && I + NumScheduledTasks != E) {
298               Chunk ChunkToCheck = *(I + NumScheduledTasks);
299               TaskQueue.emplace_back(ChunkThreadPool.async(
300                   ProcessChunkFromSerializedBitcode, ChunkToCheck,
301                   std::ref(Test), ExtractChunksFromModule, UninterestingChunks,
302                   ChunksStillConsideredInteresting, OriginalBC,
303                   std::ref(AnyReduced)));
304             }
305             continue;
306           }
307 
308           Result = std::make_unique<ReducerWorkItem>();
309           MemoryBufferRef Data(StringRef(Res), "<bc file>");
310           Result->readBitcode(Data, Test.getProgram().M->getContext(),
311                               Test.getToolName());
312           break;
313         }
314 
315         // If we broke out of the loop, we still need to wait for everything to
316         // avoid race access to the chunk set.
317         //
318         // TODO: Create a way to kill remaining items we're ignoring; they could
319         // take a long time.
320         waitAndDiscardResultsBarrier(TaskQueue);
321 
322         // Forward I to the last chunk processed in parallel.
323         I += NumChunksProcessed - 1;
324       } else {
325         Result =
326             CheckChunk(*I, Test.getProgram().clone(Test.getTargetMachine()),
327                        Test, ExtractChunksFromModule, UninterestingChunks,
328                        ChunksStillConsideredInteresting);
329       }
330 
331       if (!Result)
332         continue;
333 
334       const Chunk ChunkToCheckForUninterestingness = *I;
335       FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true;
336       UninterestingChunks.insert(ChunkToCheckForUninterestingness);
337       ReducedProgram = std::move(Result);
338 
339       // FIXME: Report meaningful progress info
340       Test.writeOutput(" **** SUCCESS | Saved new best reduction to ");
341     }
342     // Delete uninteresting chunks
343     erase_if(ChunksStillConsideredInteresting,
344              [&UninterestingChunks](const Chunk &C) {
345                return UninterestingChunks.count(C);
346              });
347   } while (!ChunksStillConsideredInteresting.empty() &&
348            (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity ||
349             increaseGranularity(ChunksStillConsideredInteresting)));
350 
351   // If we reduced the testcase replace it
352   if (ReducedProgram)
353     Test.setProgram(std::move(ReducedProgram));
354   if (Verbose)
355     errs() << "Couldn't increase anymore.\n";
356   errs() << "----------------------------\n";
357 }
358