371 lines · cpp
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-exception6//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_THREADS25#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_THREADS54static 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(1), cl::cat(LLVMReduceOptions));59#else60unsigned NumJobs = 1;61#endif62 63static StringLiteral SeparatorLine =64 "--------------------------------------------------------------------------"65 "------\n";66 67/// Splits Chunks in half and prints them.68/// If unable to split (when chunk size is 1) returns false.69static bool increaseGranularity(std::vector<Chunk> &Chunks) {70 if (Verbose)71 errs() << "Increasing granularity...";72 std::vector<Chunk> NewChunks;73 bool SplitAny = false;74 75 for (Chunk C : Chunks) {76 if (C.End - C.Begin == 0)77 NewChunks.push_back(C);78 else {79 int Half = (C.Begin + C.End) / 2;80 NewChunks.push_back({C.Begin, Half});81 NewChunks.push_back({Half + 1, C.End});82 SplitAny = true;83 }84 }85 if (SplitAny) {86 Chunks = NewChunks;87 if (Verbose) {88 errs() << "Success! " << NewChunks.size() << " New Chunks:\n";89 for (auto C : Chunks) {90 errs() << '\t';91 C.print();92 errs() << '\n';93 }94 }95 }96 return SplitAny;97}98 99// Check if \p ChunkToCheckForUninterestingness is interesting. Returns the100// modified module if the chunk resulted in a reduction.101static std::unique_ptr<ReducerWorkItem>102CheckChunk(const Chunk ChunkToCheckForUninterestingness,103 std::unique_ptr<ReducerWorkItem> Clone, const TestRunner &Test,104 ReductionFunc ExtractChunksFromModule,105 const DenseSet<Chunk> &UninterestingChunks,106 const std::vector<Chunk> &ChunksStillConsideredInteresting) {107 // Take all of ChunksStillConsideredInteresting chunks, except those we've108 // already deemed uninteresting (UninterestingChunks) but didn't remove109 // from ChunksStillConsideredInteresting yet, and additionally ignore110 // ChunkToCheckForUninterestingness chunk.111 std::vector<Chunk> CurrentChunks;112 CurrentChunks.reserve(ChunksStillConsideredInteresting.size() -113 UninterestingChunks.size() - 1);114 copy_if(ChunksStillConsideredInteresting, std::back_inserter(CurrentChunks),115 [&](const Chunk &C) {116 return C != ChunkToCheckForUninterestingness &&117 !UninterestingChunks.count(C);118 });119 120 // Generate Module with only Targets inside Current Chunks121 Oracle O(CurrentChunks);122 ExtractChunksFromModule(O, *Clone);123 124 // Some reductions may result in invalid IR. Skip such reductions.125 if (Clone->verify(&errs())) {126 if (AbortOnInvalidReduction) {127 errs() << "Invalid reduction, aborting.\n";128 Clone->print(errs());129 exit(1);130 }131 if (Verbose) {132 errs() << " **** WARNING | reduction resulted in invalid module, "133 "skipping\n";134 }135 return nullptr;136 }137 138 if (Verbose) {139 errs() << "Ignoring: ";140 ChunkToCheckForUninterestingness.print();141 for (const Chunk &C : UninterestingChunks)142 C.print();143 errs() << "\n";144 }145 146 if (!Clone->isReduced(Test)) {147 // Program became non-reduced, so this chunk appears to be interesting.148 if (Verbose)149 errs() << "\n";150 return nullptr;151 }152 return Clone;153}154 155static SmallString<0> ProcessChunkFromSerializedBitcode(156 const Chunk ChunkToCheckForUninterestingness, const TestRunner &Test,157 ReductionFunc ExtractChunksFromModule,158 const DenseSet<Chunk> &UninterestingChunks,159 ArrayRef<Chunk> ChunksStillConsideredInteresting, StringRef OriginalBC,160 std::atomic<bool> &AnyReduced) {161 LLVMContext Ctx;162 auto CloneMMM = std::make_unique<ReducerWorkItem>();163 MemoryBufferRef Data(OriginalBC, "<bc file>");164 CloneMMM->readBitcode(Data, Ctx, Test.getToolName());165 166 SmallString<0> Result;167 if (std::unique_ptr<ReducerWorkItem> ChunkResult =168 CheckChunk(ChunkToCheckForUninterestingness, std::move(CloneMMM),169 Test, ExtractChunksFromModule, UninterestingChunks,170 ChunksStillConsideredInteresting)) {171 raw_svector_ostream BCOS(Result);172 ChunkResult->writeBitcode(BCOS);173 // Communicate that the task reduced a chunk.174 AnyReduced = true;175 }176 return Result;177}178 179using SharedTaskQueue = std::deque<std::shared_future<SmallString<0>>>;180 181/// Runs the Delta Debugging algorithm, splits the code into chunks and182/// reduces the amount of chunks that are considered interesting by the183/// given test. The number of chunks is determined by a preliminary run of the184/// reduction pass where no change must be made to the module.185void llvm::runDeltaPass(TestRunner &Test, const DeltaPass &Pass) {186 assert(!Test.getProgram().verify(&errs()) &&187 "input module is broken before making changes");188 errs() << "*** " << Pass.Desc << " (" << Pass.Name << ")...\n";189 190 int Targets;191 {192 // Count the number of chunks by counting the number of calls to193 // Oracle::shouldKeep() but always returning true so no changes are194 // made.195 std::vector<Chunk> AllChunks = {{0, INT_MAX}};196 Oracle Counter(AllChunks);197 Pass.Func(Counter, Test.getProgram());198 Targets = Counter.count();199 200 assert(!Test.getProgram().verify(&errs()) &&201 "input module is broken after counting chunks");202 203 if (!SkipVerifyAfterCountingChunks && !Test.getProgram().isReduced(Test)) {204 WithColor::warning()205 << "input module no longer interesting after counting chunks\n";206 WithColor::note() << "the interestingness test may be flaky, or there "207 "may be an llvm-reduce bug\n";208 WithColor::note()209 << "use -skip-verify-interesting-after-counting-chunks to "210 "suppress this warning\n";211 }212 213#ifndef NDEBUG214 {215 // Make sure that the number of chunks does not change as we reduce.216 std::vector<Chunk> NoChunks = {{0, INT_MAX}};217 Oracle NoChunksCounter(NoChunks);218 std::unique_ptr<ReducerWorkItem> Clone =219 Test.getProgram().clone(Test.getTargetMachine());220 Pass.Func(NoChunksCounter, *Clone);221 assert(Targets == NoChunksCounter.count() &&222 "number of chunks changes when reducing");223 }224#endif225 }226 if (!Targets) {227 if (Verbose)228 errs() << "\nNothing to reduce\n";229 errs() << SeparatorLine;230 return;231 }232 233 std::vector<Chunk> ChunksStillConsideredInteresting = {{0, Targets - 1}};234 std::unique_ptr<ReducerWorkItem> ReducedProgram;235 236 for (unsigned int Level = 0; Level < StartingGranularityLevel; Level++) {237 increaseGranularity(ChunksStillConsideredInteresting);238 }239 240 std::atomic<bool> AnyReduced;241 std::unique_ptr<ThreadPoolInterface> ChunkThreadPoolPtr;242 if (NumJobs > 1)243 ChunkThreadPoolPtr =244 std::make_unique<DefaultThreadPool>(hardware_concurrency(NumJobs));245 246 SmallString<0> OriginalBC;247 DenseSet<Chunk> UninterestingChunks;248 UninterestingChunks.reserve(Targets);249 250 bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity;251 do {252 FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false;253 254 UninterestingChunks.clear();255 256 // When running with more than one thread, serialize the original bitcode257 // to OriginalBC.258 if (NumJobs > 1) {259 OriginalBC.clear();260 raw_svector_ostream BCOS(OriginalBC);261 Test.getProgram().writeBitcode(BCOS);262 }263 264 SharedTaskQueue TaskQueue;265 for (auto I = ChunksStillConsideredInteresting.rbegin(),266 E = ChunksStillConsideredInteresting.rend();267 I != E; ++I) {268 std::unique_ptr<ReducerWorkItem> Result = nullptr;269 unsigned WorkLeft = std::distance(I, E);270 271 // Run in parallel mode, if the user requested more than one thread and272 // there are at least a few chunks to process.273 if (NumJobs > 1 && WorkLeft > 1) {274 unsigned NumInitialTasks = std::min(WorkLeft, unsigned(NumJobs));275 unsigned NumChunksProcessed = 0;276 277 ThreadPoolInterface &ChunkThreadPool = *ChunkThreadPoolPtr;278 assert(TaskQueue.empty());279 280 AnyReduced = false;281 // Queue jobs to process NumInitialTasks chunks in parallel using282 // ChunkThreadPool. When the tasks are added to the pool, parse the283 // original module from OriginalBC with a fresh LLVMContext object. This284 // ensures that the cloned module of each task uses an independent285 // LLVMContext object. If a task reduces the input, serialize the result286 // back in the corresponding Result element.287 for (unsigned J = 0; J < NumInitialTasks; ++J) {288 Chunk ChunkToCheck = *(I + J);289 TaskQueue.emplace_back(ChunkThreadPool.async(290 ProcessChunkFromSerializedBitcode, ChunkToCheck, std::ref(Test),291 Pass.Func, UninterestingChunks, ChunksStillConsideredInteresting,292 OriginalBC, std::ref(AnyReduced)));293 }294 295 // Start processing results of the queued tasks. We wait for the first296 // task in the queue to finish. If it reduced a chunk, we parse the297 // result and exit the loop.298 // Otherwise we will try to schedule a new task, if299 // * no other pending job reduced a chunk and300 // * we have not reached the end of the chunk.301 while (!TaskQueue.empty()) {302 auto &Future = TaskQueue.front();303 Future.wait();304 305 NumChunksProcessed++;306 SmallString<0> Res = Future.get();307 TaskQueue.pop_front();308 if (Res.empty()) {309 unsigned NumScheduledTasks = NumChunksProcessed + TaskQueue.size();310 if (!AnyReduced && I + NumScheduledTasks != E) {311 Chunk ChunkToCheck = *(I + NumScheduledTasks);312 TaskQueue.emplace_back(ChunkThreadPool.async(313 ProcessChunkFromSerializedBitcode, ChunkToCheck,314 std::ref(Test), Pass.Func, UninterestingChunks,315 ChunksStillConsideredInteresting, OriginalBC,316 std::ref(AnyReduced)));317 }318 continue;319 }320 321 Result = std::make_unique<ReducerWorkItem>();322 MemoryBufferRef Data(StringRef(Res), "<bc file>");323 Result->readBitcode(Data, Test.getProgram().M->getContext(),324 Test.getToolName());325 break;326 }327 328 // If we broke out of the loop, we still need to wait for everything to329 // avoid race access to the chunk set.330 //331 // TODO: Create a way to kill remaining items we're ignoring; they could332 // take a long time.333 ChunkThreadPoolPtr->wait();334 TaskQueue.clear();335 336 // Forward I to the last chunk processed in parallel.337 I += NumChunksProcessed - 1;338 } else {339 Result = CheckChunk(340 *I, Test.getProgram().clone(Test.getTargetMachine()), Test,341 Pass.Func, UninterestingChunks, ChunksStillConsideredInteresting);342 }343 344 if (!Result)345 continue;346 347 const Chunk ChunkToCheckForUninterestingness = *I;348 FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true;349 UninterestingChunks.insert(ChunkToCheckForUninterestingness);350 ReducedProgram = std::move(Result);351 }352 // Delete uninteresting chunks353 erase_if(ChunksStillConsideredInteresting,354 [&UninterestingChunks](const Chunk &C) {355 return UninterestingChunks.count(C);356 });357 } while (!ChunksStillConsideredInteresting.empty() &&358 (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity ||359 increaseGranularity(ChunksStillConsideredInteresting)));360 361 // If we reduced the testcase replace it362 if (ReducedProgram) {363 Test.setProgram(std::move(ReducedProgram));364 // FIXME: Report meaningful progress info365 Test.writeOutput(" **** SUCCESS | Saved new best reduction to ");366 }367 if (Verbose)368 errs() << "Couldn't increase anymore.\n";369 errs() << SeparatorLine;370}371