tools/llvm-reduce/deltas/Delta.h

   1 //===- Delta.h - 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 #ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
  16 #define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
  17
  18 #include "../TestRunner.h"
  19 #include "llvm/IR/Verifier.h"
  20 #include "llvm/Support/FileSystem.h"
  21 #include "llvm/Support/Path.h"
  22 #include "llvm/Support/ScopedPrinter.h"
  23 #include "llvm/Support/ToolOutputFile.h"
  24 #include "llvm/Transforms/Utils/Cloning.h"
  25 #include <fstream>
  26 #include <set>
  27 #include <vector>
  28
  29 using namespace llvm;
  30
  31 struct Chunk {
  32   unsigned begin;
  33   unsigned end;
  34
  35   /// Helper function to verify if a given Target-index is inside the Chunk
  36   bool contains(unsigned Index) const { return Index >= begin && Index <= end; }
  37
  38   void print() const {
  39     errs() << "[" << begin;
  40     if (end - begin != 0)
  41       errs() << "," << end;
  42     errs() << "]";
  43   }
  44
  45   /// Operator when populating CurrentChunks in Generic Delta Pass
  46   friend bool operator!=(const Chunk &C1, const Chunk &C2) {
  47     return C1.begin != C2.begin || C1.end != C2.end;
  48   }
  49
  50   /// Operator used for sets
  51   friend bool operator<(const Chunk &C1, const Chunk &C2) {
  52     return std::tie(C1.begin, C1.end) < std::tie(C2.begin, C2.end);
  53   }
  54 };
  55
  56 namespace llvm {
  57
  58 /// This function implements the Delta Debugging algorithm, it receives a
  59 /// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
  60 /// splits them in half; these chunks of targets are then tested while ignoring
  61 /// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
  62 /// it is removed from consideration. The algorithm will attempt to split the
  63 /// Chunks in half and start the process again until it can't split chunks
  64 /// anymore.
  65 ///
  66 /// This function is intended to be called by each specialized delta pass (e.g.
  67 /// RemoveFunctions) and receives three key parameters:
  68 /// * Test: The main TestRunner instance which is used to run the provided
  69 /// interesting-ness test, as well as to store and access the reduced Program.
  70 /// * Targets: The amount of Targets that are going to be reduced by the
  71 /// algorithm, for example, the RemoveGlobalVars pass would send the amount of
  72 /// initialized GVs.
  73 /// * ExtractChunksFromModule: A function used to tailor the main program so it
  74 /// only contains Targets that are inside Chunks of the given iteration.
  75 /// Note: This function is implemented by each specialized Delta pass
  76 ///
  77 /// Other implementations of the Delta Debugging algorithm can also be found in
  78 /// the CReduce, Delta, and Lithium projects.
  79 void runDeltaPass(TestRunner &Test, unsigned Targets,
  80                   std::function<void(const std::vector<Chunk> &, Module *)>
  81                       ExtractChunksFromModule);
  82 } // namespace llvm
  83
  84 #endif