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