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