llvm/tools/llvm-reduce/deltas/Delta.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-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 "llvm/ADT/STLExtras.h"
  18 #include "llvm/Bitcode/BitcodeReader.h"
  19 #include "llvm/Bitcode/BitcodeWriter.h"
  20 #include "llvm/IR/Verifier.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/ThreadPool.h"
  23 #include "llvm/Support/ToolOutputFile.h"
  24 #include <fstream>
  25 #include <set>
  26
  27 using namespace llvm;
  28
  29 static cl::opt<bool> AbortOnInvalidReduction(
  30     "abort-on-invalid-reduction",
  31     cl::desc("Abort if any reduction results in invalid IR"));
  32
  33 static cl::opt<unsigned int> StartingGranularityLevel(
  34     "starting-granularity-level",
  35     cl::desc("Number of times to divide chunks prior to first test"));
  36
  37 static cl::opt<bool> TmpFilesAsBitcode(
  38     "write-tmp-files-as-bitcode",
  39     cl::desc("Write temporary files as bitcode, instead of textual IR"),
  40     cl::init(false));
  41
  42 #ifdef LLVM_ENABLE_THREADS
  43 static cl::opt<unsigned> NumJobs(
  44     "j",
  45     cl::desc("Maximum number of threads to use to process chunks. Set to 1 to "
  46              "disables parallelism."),
  47     cl::init(1));
  48 #else
  49 unsigned NumJobs = 1;
  50 #endif
  51
  52 void writeOutput(ReducerWorkItem &M, llvm::StringRef Message);
  53
  54 bool isReduced(ReducerWorkItem &M, TestRunner &Test,
  55                SmallString<128> &CurrentFilepath) {
  56   // Write ReducerWorkItem to tmp file
  57   int FD;
  58   std::error_code EC = sys::fs::createTemporaryFile(
  59       "llvm-reduce", M.isMIR() ? "mir" : (TmpFilesAsBitcode ? "bc" : "ll"), FD,
  60       CurrentFilepath);
  61   if (EC) {
  62     errs() << "Error making unique filename: " << EC.message() << "!\n";
  63     exit(1);
  64   }
  65
  66   if (TmpFilesAsBitcode) {
  67     llvm::raw_fd_ostream OutStream(FD, true);
  68     WriteBitcodeToFile(M, OutStream);
  69     OutStream.close();
  70     if (OutStream.has_error()) {
  71       errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n";
  72       sys::fs::remove(CurrentFilepath);
  73       exit(1);
  74     }
  75     bool Res = Test.run(CurrentFilepath);
  76     sys::fs::remove(CurrentFilepath);
  77     return Res;
  78   }
  79   ToolOutputFile Out(CurrentFilepath, FD);
  80   M.print(Out.os(), /*AnnotationWriter=*/nullptr);
  81   Out.os().close();
  82   if (Out.os().has_error()) {
  83     errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n";
  84     exit(1);
  85   }
  86
  87   // Current Chunks aren't interesting
  88   return Test.run(CurrentFilepath);
  89 }
  90
  91 /// Counts the amount of lines for a given file
  92 static int getLines(StringRef Filepath) {
  93   int Lines = 0;
  94   std::string CurrLine;
  95   std::ifstream FileStream{std::string(Filepath)};
  96
  97   while (std::getline(FileStream, CurrLine))
  98     ++Lines;
  99
 100   return Lines;
 101 }
 102
 103 /// Splits Chunks in half and prints them.
 104 /// If unable to split (when chunk size is 1) returns false.
 105 static bool increaseGranularity(std::vector<Chunk> &Chunks) {
 106   errs() << "Increasing granularity...";
 107   std::vector<Chunk> NewChunks;
 108   bool SplitOne = false;
 109
 110   for (auto &C : Chunks) {
 111     if (C.End - C.Begin == 0)
 112       NewChunks.push_back(C);
 113     else {
 114       int Half = (C.Begin + C.End) / 2;
 115       NewChunks.push_back({C.Begin, Half});
 116       NewChunks.push_back({Half + 1, C.End});
 117       SplitOne = true;
 118     }
 119   }
 120   if (SplitOne) {
 121     Chunks = NewChunks;
 122     errs() << "Success! New Chunks:\n";
 123     for (auto C : Chunks) {
 124       errs() << '\t';
 125       C.print();
 126       errs() << '\n';
 127     }
 128   }
 129   return SplitOne;
 130 }
 131 // Check if \p ChunkToCheckForUninterestingness is interesting. Returns the
 132 // modified module if the chunk resulted in a reduction.
 133 template <typename T>
 134 static std::unique_ptr<ReducerWorkItem>
 135 CheckChunk(Chunk &ChunkToCheckForUninterestingness,
 136            std::unique_ptr<ReducerWorkItem> Clone, TestRunner &Test,
 137            function_ref<void(Oracle &, T &)> ExtractChunksFromModule,
 138            std::set<Chunk> &UninterestingChunks,
 139            std::vector<Chunk> &ChunksStillConsideredInteresting) {
 140   // Take all of ChunksStillConsideredInteresting chunks, except those we've
 141   // already deemed uninteresting (UninterestingChunks) but didn't remove
 142   // from ChunksStillConsideredInteresting yet, and additionally ignore
 143   // ChunkToCheckForUninterestingness chunk.
 144   std::vector<Chunk> CurrentChunks;
 145   CurrentChunks.reserve(ChunksStillConsideredInteresting.size() -
 146                         UninterestingChunks.size() - 1);
 147   copy_if(ChunksStillConsideredInteresting, std::back_inserter(CurrentChunks),
 148           [&](const Chunk &C) {
 149             return !UninterestingChunks.count(C) &&
 150                    C != ChunkToCheckForUninterestingness;
 151           });
 152
 153   // Generate Module with only Targets inside Current Chunks
 154   Oracle O(CurrentChunks);
 155   ExtractChunksFromModule(O, *Clone);
 156
 157   // Some reductions may result in invalid IR. Skip such reductions.
 158   if (verifyReducerWorkItem(*Clone, &errs())) {
 159     if (AbortOnInvalidReduction) {
 160       errs() << "Invalid reduction\n";
 161       exit(1);
 162     }
 163     errs() << " **** WARNING | reduction resulted in invalid module, "
 164               "skipping\n";
 165     return nullptr;
 166   }
 167
 168   errs() << "Ignoring: ";
 169   ChunkToCheckForUninterestingness.print();
 170   for (const Chunk &C : UninterestingChunks)
 171     C.print();
 172
 173   SmallString<128> CurrentFilepath;
 174   if (!isReduced(*Clone, Test, CurrentFilepath)) {
 175     // Program became non-reduced, so this chunk appears to be interesting.
 176     errs() << "\n";
 177     return nullptr;
 178   }
 179   return Clone;
 180 }
 181
 182 template <typename T>
 183 SmallString<0> ProcessChunkFromSerializedBitcode(
 184     Chunk &ChunkToCheckForUninterestingness, TestRunner &Test,
 185     function_ref<void(Oracle &, T &)> ExtractChunksFromModule,
 186     std::set<Chunk> &UninterestingChunks,
 187     std::vector<Chunk> &ChunksStillConsideredInteresting,
 188     SmallString<0> &OriginalBC, std::atomic<bool> &AnyReduced) {
 189   LLVMContext Ctx;
 190   Expected<std::unique_ptr<Module>> MOrErr = parseBitcodeFile(
 191       MemoryBufferRef(StringRef(OriginalBC.data(), OriginalBC.size()),
 192                       "<llvm-reduce tmp module>"),
 193       Ctx);
 194   if (!MOrErr)
 195     report_fatal_error("Failed to read bitcode");
 196   auto CloneMMM = std::make_unique<ReducerWorkItem>();
 197   CloneMMM->M = std::move(MOrErr.get());
 198
 199   SmallString<0> Result;
 200   if (std::unique_ptr<ReducerWorkItem> ChunkResult =
 201           CheckChunk(ChunkToCheckForUninterestingness, std::move(CloneMMM),
 202                      Test, ExtractChunksFromModule, UninterestingChunks,
 203                      ChunksStillConsideredInteresting)) {
 204     raw_svector_ostream BCOS(Result);
 205     WriteBitcodeToFile(*ChunkResult->M, BCOS);
 206     // Communicate that the task reduced a chunk.
 207     AnyReduced = true;
 208   }
 209   return Result;
 210 }
 211
 212 /// Runs the Delta Debugging algorithm, splits the code into chunks and
 213 /// reduces the amount of chunks that are considered interesting by the
 214 /// given test. The number of chunks is determined by a preliminary run of the
 215 /// reduction pass where no change must be made to the module.
 216 template <typename T>
 217 void runDeltaPassInt(
 218     TestRunner &Test,
 219     function_ref<void(Oracle &, T &)> ExtractChunksFromModule) {
 220   assert(!verifyReducerWorkItem(Test.getProgram(), &errs()) &&
 221          "input module is broken before making changes");
 222
 223   SmallString<128> CurrentFilepath;
 224   if (!isReduced(Test.getProgram(), Test, CurrentFilepath)) {
 225     errs() << "\nInput isn't interesting! Verify interesting-ness test\n";
 226     exit(1);
 227   }
 228
 229   int Targets;
 230   {
 231     // Count the number of chunks by counting the number of calls to
 232     // Oracle::shouldKeep() but always returning true so no changes are
 233     // made.
 234     std::vector<Chunk> AllChunks = {{0, INT_MAX}};
 235     Oracle Counter(AllChunks);
 236     ExtractChunksFromModule(Counter, Test.getProgram());
 237     Targets = Counter.count();
 238
 239     assert(!verifyReducerWorkItem(Test.getProgram(), &errs()) &&
 240            "input module is broken after counting chunks");
 241     assert(isReduced(Test.getProgram(), Test, CurrentFilepath) &&
 242            "input module no longer interesting after counting chunks");
 243
 244 #ifndef NDEBUG
 245     // Make sure that the number of chunks does not change as we reduce.
 246     std::vector<Chunk> NoChunks;
 247     Oracle NoChunksCounter(NoChunks);
 248     std::unique_ptr<ReducerWorkItem> Clone =
 249         cloneReducerWorkItem(Test.getProgram());
 250     ExtractChunksFromModule(NoChunksCounter, *Clone);
 251     assert(Targets == NoChunksCounter.count() &&
 252            "number of chunks changes when reducing");
 253 #endif
 254   }
 255   if (!Targets) {
 256     errs() << "\nNothing to reduce\n";
 257     return;
 258   }
 259
 260   std::vector<Chunk> ChunksStillConsideredInteresting = {{0, Targets - 1}};
 261   std::unique_ptr<ReducerWorkItem> ReducedProgram;
 262
 263   for (unsigned int Level = 0; Level < StartingGranularityLevel; Level++) {
 264     increaseGranularity(ChunksStillConsideredInteresting);
 265   }
 266
 267   std::atomic<bool> AnyReduced;
 268   std::unique_ptr<ThreadPool> ChunkThreadPoolPtr;
 269   if (NumJobs > 1)
 270     ChunkThreadPoolPtr =
 271         std::make_unique<ThreadPool>(hardware_concurrency(NumJobs));
 272
 273   bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity;
 274   do {
 275     FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false;
 276
 277     std::set<Chunk> UninterestingChunks;
 278
 279     // When running with more than one thread, serialize the original bitcode
 280     // to OriginalBC.
 281     SmallString<0> OriginalBC;
 282     if (NumJobs > 1) {
 283       raw_svector_ostream BCOS(OriginalBC);
 284       WriteBitcodeToFile(*Test.getProgram().M, BCOS);
 285     }
 286
 287     std::deque<std::shared_future<SmallString<0>>> TaskQueue;
 288     for (auto I = ChunksStillConsideredInteresting.rbegin(),
 289               E = ChunksStillConsideredInteresting.rend();
 290          I != E; ++I) {
 291       std::unique_ptr<ReducerWorkItem> Result = nullptr;
 292       unsigned WorkLeft = std::distance(I, E);
 293
 294       // Run in parallel mode, if the user requested more than one thread and
 295       // there are at least a few chunks to process.
 296       if (NumJobs > 1 && WorkLeft > 1) {
 297         unsigned NumInitialTasks = std::min(WorkLeft, unsigned(NumJobs));
 298         unsigned NumChunksProcessed = 0;
 299
 300         ThreadPool &ChunkThreadPool = *ChunkThreadPoolPtr;
 301         TaskQueue.clear();
 302
 303         AnyReduced = false;
 304         // Queue jobs to process NumInitialTasks chunks in parallel using
 305         // ChunkThreadPool. When the tasks are added to the pool, parse the
 306         // original module from OriginalBC with a fresh LLVMContext object. This
 307         // ensures that the cloned module of each task uses an independent
 308         // LLVMContext object. If a task reduces the input, serialize the result
 309         // back in the corresponding Result element.
 310         for (unsigned J = 0; J < NumInitialTasks; ++J) {
 311           TaskQueue.emplace_back(ChunkThreadPool.async(
 312               [J, I, &Test, &ExtractChunksFromModule, &UninterestingChunks,
 313                &ChunksStillConsideredInteresting, &OriginalBC, &AnyReduced]() {
 314                 return ProcessChunkFromSerializedBitcode(
 315                     *(I + J), Test, ExtractChunksFromModule,
 316                     UninterestingChunks, ChunksStillConsideredInteresting,
 317                     OriginalBC, AnyReduced);
 318               }));
 319         }
 320
 321         // Start processing results of the queued tasks. We wait for the first
 322         // task in the queue to finish. If it reduced a chunk, we parse the
 323         // result and exit the loop.
 324         //  Otherwise we will try to schedule a new task, if
 325         //  * no other pending job reduced a chunk and
 326         //  * we have not reached the end of the chunk.
 327         while (!TaskQueue.empty()) {
 328           auto &Future = TaskQueue.front();
 329           Future.wait();
 330
 331           NumChunksProcessed++;
 332           SmallString<0> Res = Future.get();
 333           TaskQueue.pop_front();
 334           if (Res.empty()) {
 335             unsigned NumScheduledTasks = NumChunksProcessed + TaskQueue.size();
 336             if (!AnyReduced && I + NumScheduledTasks != E) {
 337               Chunk &ChunkToCheck = *(I + NumScheduledTasks);
 338               TaskQueue.emplace_back(ChunkThreadPool.async(
 339                   [&Test, &ExtractChunksFromModule, &UninterestingChunks,
 340                    &ChunksStillConsideredInteresting, &OriginalBC,
 341                    &ChunkToCheck, &AnyReduced]() {
 342                     return ProcessChunkFromSerializedBitcode(
 343                         ChunkToCheck, Test, ExtractChunksFromModule,
 344                         UninterestingChunks, ChunksStillConsideredInteresting,
 345                         OriginalBC, AnyReduced);
 346                   }));
 347             }
 348             continue;
 349           }
 350
 351           Expected<std::unique_ptr<Module>> MOrErr = parseBitcodeFile(
 352               MemoryBufferRef(StringRef(Res.data(), Res.size()),
 353                               "<llvm-reduce tmp module>"),
 354               Test.getProgram().M->getContext());
 355           if (!MOrErr)
 356             report_fatal_error("Failed to read bitcode");
 357           Result = std::make_unique<ReducerWorkItem>();
 358           Result->M = std::move(MOrErr.get());
 359           break;
 360         }
 361         // Forward I to the last chunk processed in parallel.
 362         I += NumChunksProcessed - 1;
 363       } else {
 364         Result = CheckChunk(*I, cloneReducerWorkItem(Test.getProgram()), Test,
 365                             ExtractChunksFromModule, UninterestingChunks,
 366                             ChunksStillConsideredInteresting);
 367       }
 368
 369       if (!Result)
 370         continue;
 371
 372       Chunk &ChunkToCheckForUninterestingness = *I;
 373       FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true;
 374       UninterestingChunks.insert(ChunkToCheckForUninterestingness);
 375       ReducedProgram = std::move(Result);
 376       errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n";
 377       writeOutput(*ReducedProgram, "Saved new best reduction to ");
 378     }
 379     // Delete uninteresting chunks
 380     erase_if(ChunksStillConsideredInteresting,
 381              [&UninterestingChunks](const Chunk &C) {
 382                return UninterestingChunks.count(C);
 383              });
 384   } while (!ChunksStillConsideredInteresting.empty() &&
 385            (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity ||
 386             increaseGranularity(ChunksStillConsideredInteresting)));
 387
 388   // If we reduced the testcase replace it
 389   if (ReducedProgram)
 390     Test.setProgram(std::move(ReducedProgram));
 391   errs() << "Couldn't increase anymore.\n";
 392 }
 393
 394 void llvm::runDeltaPass(
 395     TestRunner &Test,
 396     function_ref<void(Oracle &, Module &)> ExtractChunksFromModule) {
 397   runDeltaPassInt<Module>(Test, ExtractChunksFromModule);
 398 }
 399
 400 void llvm::runDeltaPass(
 401     TestRunner &Test,
 402     function_ref<void(Oracle &, MachineFunction &)> ExtractChunksFromModule) {
 403   runDeltaPassInt<MachineFunction>(Test, ExtractChunksFromModule);
 404 }