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