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 "llvm/ADT/STLExtras.h"
  17
  18 /// Writes IR code to the given Filepath
  19 static bool writeProgramToFile(StringRef Filepath, int FD, const Module &M) {
  20   ToolOutputFile Out(Filepath, FD);
  21   M.print(Out.os(), /*AnnotationWriter=*/nullptr);
  22   Out.os().close();
  23
  24   if (!Out.os().has_error()) {
  25     Out.keep();
  26     return false;
  27   }
  28   return true;
  29 }
  30
  31 /// Creates a temporary (and unique) file inside the tmp folder and writes
  32 /// the given module IR.
  33 static SmallString<128> createTmpFile(Module *M, StringRef TmpDir) {
  34   SmallString<128> UniqueFilepath;
  35   int UniqueFD;
  36
  37   SmallString<128> TmpFilepath;
  38   sys::path::append(TmpFilepath, TmpDir, "tmp-%%%.ll");
  39   std::error_code EC =
  40       sys::fs::createUniqueFile(TmpFilepath, UniqueFD, UniqueFilepath);
  41   if (EC) {
  42     errs() << "Error making unique filename: " << EC.message() << "!\n";
  43     exit(1);
  44   }
  45
  46   if (writeProgramToFile(UniqueFilepath, UniqueFD, *M)) {
  47     errs() << "Error emitting bitcode to file '" << UniqueFilepath << "'!\n";
  48     exit(1);
  49   }
  50   return UniqueFilepath;
  51 }
  52
  53 /// Counts the amount of lines for a given file
  54 static unsigned getLines(StringRef Filepath) {
  55   unsigned Lines = 0;
  56   std::string CurrLine;
  57   std::ifstream FileStream(Filepath);
  58
  59   while (std::getline(FileStream, CurrLine))
  60     ++Lines;
  61
  62   return Lines;
  63 }
  64
  65 /// Splits Chunks in half and prints them.
  66 /// If unable to split (when chunk size is 1) returns false.
  67 static bool increaseGranularity(std::vector<Chunk> &Chunks) {
  68   errs() << "Increasing granularity...";
  69   std::vector<Chunk> NewChunks;
  70   bool SplitOne = false;
  71
  72   for (auto &C : Chunks) {
  73     if (C.end - C.begin == 0)
  74       NewChunks.push_back(C);
  75     else {
  76       unsigned Half = (C.begin + C.end) / 2;
  77       NewChunks.push_back({C.begin, Half});
  78       NewChunks.push_back({Half + 1, C.end});
  79       SplitOne = true;
  80     }
  81   }
  82   if (SplitOne) {
  83     Chunks = NewChunks;
  84     errs() << "Success! New Chunks:\n";
  85     for (auto C : Chunks) {
  86       errs() << '\t';
  87       C.print();
  88       errs() << '\n';
  89     }
  90   }
  91   return SplitOne;
  92 }
  93
  94 /// Runs the Delta Debugging algorithm, splits the code into chunks and
  95 /// reduces the amount of chunks that are considered interesting by the
  96 /// given test.
  97 void llvm::runDeltaPass(
  98     TestRunner &Test, unsigned Targets,
  99     std::function<void(const std::vector<Chunk> &, Module *)>
 100         ExtractChunksFromModule) {
 101   if (!Targets) {
 102     errs() << "\nNothing to reduce\n";
 103     return;
 104   }
 105   if (!Test.run(Test.getReducedFilepath())) {
 106     errs() << "\nInput isn't interesting! Verify interesting-ness test\n";
 107     exit(1);
 108   }
 109
 110   std::vector<Chunk> Chunks = {{1, Targets}};
 111   std::set<Chunk> UninterestingChunks;
 112   std::unique_ptr<Module> ReducedProgram;
 113
 114   if (!increaseGranularity(Chunks)) {
 115     errs() << "\nAlready at minimum size. Cannot reduce anymore.\n";
 116     return;
 117   }
 118
 119   do {
 120     UninterestingChunks = {};
 121     for (int I = Chunks.size() - 1; I >= 0; --I) {
 122       std::vector<Chunk> CurrentChunks;
 123
 124       for (auto C : Chunks)
 125         if (!UninterestingChunks.count(C) && C != Chunks[I])
 126           CurrentChunks.push_back(C);
 127
 128       if (CurrentChunks.empty())
 129         continue;
 130
 131       // Clone module before hacking it up..
 132       std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram());
 133       // Generate Module with only Targets inside Current Chunks
 134       ExtractChunksFromModule(CurrentChunks, Clone.get());
 135       // Write Module to tmp file
 136       SmallString<128> CurrentFilepath =
 137           createTmpFile(Clone.get(), Test.getTmpDir());
 138
 139       errs() << "Ignoring: ";
 140       Chunks[I].print();
 141       for (auto C : UninterestingChunks)
 142         C.print();
 143
 144       errs() << " | " << sys::path::filename(CurrentFilepath);
 145
 146       // Current Chunks aren't interesting
 147       if (!Test.run(CurrentFilepath)) {
 148         errs() << "\n";
 149         continue;
 150       }
 151
 152       UninterestingChunks.insert(Chunks[I]);
 153       Test.setReducedFilepath(CurrentFilepath);
 154       ReducedProgram = std::move(Clone);
 155       errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n";
 156     }
 157     // Delete uninteresting chunks
 158     erase_if(Chunks, [&UninterestingChunks](const Chunk &C) {
 159       return UninterestingChunks.count(C);
 160     });
 161
 162   } while (!UninterestingChunks.empty() || increaseGranularity(Chunks));
 163
 164   // If we reduced the testcase replace it
 165   if (ReducedProgram)
 166     Test.setProgram(std::move(ReducedProgram));
 167   errs() << "Couldn't increase anymore.\n";
 168 }