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 "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.
  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<ThreadPool> ChunkThreadPoolPtr;
 224   if (NumJobs > 1)
 225     ChunkThreadPoolPtr =
 226         std::make_unique<ThreadPool>(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         ThreadPool &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 }