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/Config/llvm-config.h" // for LLVM_ENABLE_THREADS 26 #include "llvm/IR/Module.h" 27 #include "llvm/IR/Verifier.h" 28 #include "llvm/MC/TargetRegistry.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/MemoryBufferRef.h" 31 #include "llvm/Support/ThreadPool.h" 32 #include <fstream> 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. 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> 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 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 172 /// Runs the Delta Debugging algorithm, splits the code into chunks and 173 /// reduces the amount of chunks that are considered interesting by the 174 /// given test. The number of chunks is determined by a preliminary run of the 175 /// reduction pass where no change must be made to the module. 176 void llvm::runDeltaPass(TestRunner &Test, ReductionFunc ExtractChunksFromModule, 177 StringRef Message) { 178 assert(!Test.getProgram().verify(&errs()) && 179 "input module is broken before making changes"); 180 errs() << "*** " << Message << "...\n"; 181 182 int Targets; 183 { 184 // Count the number of chunks by counting the number of calls to 185 // Oracle::shouldKeep() but always returning true so no changes are 186 // made. 187 std::vector<Chunk> AllChunks = {{0, INT_MAX}}; 188 Oracle Counter(AllChunks); 189 ExtractChunksFromModule(Counter, Test.getProgram()); 190 Targets = Counter.count(); 191 192 assert(!Test.getProgram().verify(&errs()) && 193 "input module is broken after counting chunks"); 194 assert(Test.getProgram().isReduced(Test) && 195 "input module no longer interesting after counting chunks"); 196 197 #ifndef NDEBUG 198 // Make sure that the number of chunks does not change as we reduce. 199 std::vector<Chunk> NoChunks = {{0, INT_MAX}}; 200 Oracle NoChunksCounter(NoChunks); 201 std::unique_ptr<ReducerWorkItem> Clone = 202 Test.getProgram().clone(Test.getTargetMachine()); 203 ExtractChunksFromModule(NoChunksCounter, *Clone); 204 assert(Targets == NoChunksCounter.count() && 205 "number of chunks changes when reducing"); 206 #endif 207 } 208 if (!Targets) { 209 if (Verbose) 210 errs() << "\nNothing to reduce\n"; 211 errs() << "----------------------------\n"; 212 return; 213 } 214 215 std::vector<Chunk> ChunksStillConsideredInteresting = {{0, Targets - 1}}; 216 std::unique_ptr<ReducerWorkItem> ReducedProgram; 217 218 for (unsigned int Level = 0; Level < StartingGranularityLevel; Level++) { 219 increaseGranularity(ChunksStillConsideredInteresting); 220 } 221 222 std::atomic<bool> AnyReduced; 223 std::unique_ptr<ThreadPoolInterface> ChunkThreadPoolPtr; 224 if (NumJobs > 1) 225 ChunkThreadPoolPtr = 226 std::make_unique<DefaultThreadPool>(hardware_concurrency(NumJobs)); 227 228 bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity; 229 do { 230 FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false; 231 232 DenseSet<Chunk> UninterestingChunks; 233 234 // When running with more than one thread, serialize the original bitcode 235 // to OriginalBC. 236 SmallString<0> OriginalBC; 237 if (NumJobs > 1) { 238 raw_svector_ostream BCOS(OriginalBC); 239 Test.getProgram().writeBitcode(BCOS); 240 } 241 242 SharedTaskQueue TaskQueue; 243 for (auto I = ChunksStillConsideredInteresting.rbegin(), 244 E = ChunksStillConsideredInteresting.rend(); 245 I != E; ++I) { 246 std::unique_ptr<ReducerWorkItem> Result = nullptr; 247 unsigned WorkLeft = std::distance(I, E); 248 249 // Run in parallel mode, if the user requested more than one thread and 250 // there are at least a few chunks to process. 251 if (NumJobs > 1 && WorkLeft > 1) { 252 unsigned NumInitialTasks = std::min(WorkLeft, unsigned(NumJobs)); 253 unsigned NumChunksProcessed = 0; 254 255 ThreadPoolInterface &ChunkThreadPool = *ChunkThreadPoolPtr; 256 assert(TaskQueue.empty()); 257 258 AnyReduced = false; 259 // Queue jobs to process NumInitialTasks chunks in parallel using 260 // ChunkThreadPool. When the tasks are added to the pool, parse the 261 // original module from OriginalBC with a fresh LLVMContext object. This 262 // ensures that the cloned module of each task uses an independent 263 // LLVMContext object. If a task reduces the input, serialize the result 264 // back in the corresponding Result element. 265 for (unsigned J = 0; J < NumInitialTasks; ++J) { 266 Chunk ChunkToCheck = *(I + J); 267 TaskQueue.emplace_back(ChunkThreadPool.async( 268 ProcessChunkFromSerializedBitcode, ChunkToCheck, std::ref(Test), 269 ExtractChunksFromModule, UninterestingChunks, 270 ChunksStillConsideredInteresting, OriginalBC, 271 std::ref(AnyReduced))); 272 } 273 274 // Start processing results of the queued tasks. We wait for the first 275 // task in the queue to finish. If it reduced a chunk, we parse the 276 // result and exit the loop. 277 // Otherwise we will try to schedule a new task, if 278 // * no other pending job reduced a chunk and 279 // * we have not reached the end of the chunk. 280 while (!TaskQueue.empty()) { 281 auto &Future = TaskQueue.front(); 282 Future.wait(); 283 284 NumChunksProcessed++; 285 SmallString<0> Res = Future.get(); 286 TaskQueue.pop_front(); 287 if (Res.empty()) { 288 unsigned NumScheduledTasks = NumChunksProcessed + TaskQueue.size(); 289 if (!AnyReduced && I + NumScheduledTasks != E) { 290 Chunk ChunkToCheck = *(I + NumScheduledTasks); 291 TaskQueue.emplace_back(ChunkThreadPool.async( 292 ProcessChunkFromSerializedBitcode, ChunkToCheck, 293 std::ref(Test), ExtractChunksFromModule, UninterestingChunks, 294 ChunksStillConsideredInteresting, OriginalBC, 295 std::ref(AnyReduced))); 296 } 297 continue; 298 } 299 300 Result = std::make_unique<ReducerWorkItem>(); 301 MemoryBufferRef Data(StringRef(Res), "<bc file>"); 302 Result->readBitcode(Data, Test.getProgram().M->getContext(), 303 Test.getToolName()); 304 break; 305 } 306 307 // If we broke out of the loop, we still need to wait for everything to 308 // avoid race access to the chunk set. 309 // 310 // TODO: Create a way to kill remaining items we're ignoring; they could 311 // take a long time. 312 ChunkThreadPoolPtr->wait(); 313 TaskQueue.clear(); 314 315 // Forward I to the last chunk processed in parallel. 316 I += NumChunksProcessed - 1; 317 } else { 318 Result = 319 CheckChunk(*I, Test.getProgram().clone(Test.getTargetMachine()), 320 Test, ExtractChunksFromModule, UninterestingChunks, 321 ChunksStillConsideredInteresting); 322 } 323 324 if (!Result) 325 continue; 326 327 const Chunk ChunkToCheckForUninterestingness = *I; 328 FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true; 329 UninterestingChunks.insert(ChunkToCheckForUninterestingness); 330 ReducedProgram = std::move(Result); 331 } 332 // Delete uninteresting chunks 333 erase_if(ChunksStillConsideredInteresting, 334 [&UninterestingChunks](const Chunk &C) { 335 return UninterestingChunks.count(C); 336 }); 337 } while (!ChunksStillConsideredInteresting.empty() && 338 (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity || 339 increaseGranularity(ChunksStillConsideredInteresting))); 340 341 // If we reduced the testcase replace it 342 if (ReducedProgram) { 343 Test.setProgram(std::move(ReducedProgram)); 344 // FIXME: Report meaningful progress info 345 Test.writeOutput(" **** SUCCESS | Saved new best reduction to "); 346 } 347 if (Verbose) 348 errs() << "Couldn't increase anymore.\n"; 349 errs() << "----------------------------\n"; 350 } 351