llvm/tools/llvm-reduce/deltas/Delta.h

   1 //===- Delta.h - Delta Debugging Algorithm Implementation -------*- C++ -*-===//
   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_LLVM_REDUCE_DELTAS_DELTA_H
  16 #define LLVM_TOOLS_LLVM_REDUCE_DELTAS_DELTA_H
  17
  18 #include "ReducerWorkItem.h"
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 #include <functional>
  22 #include <utility>
  23
  24 namespace llvm {
  25
  26 class TestRunner;
  27
  28 struct Chunk {
  29   int Begin;
  30   int End;
  31
  32   /// Helper function to verify if a given Target-index is inside the Chunk
  33   bool contains(int Index) const { return Index >= Begin && Index <= End; }
  34
  35   void print() const {
  36     errs() << '[' << Begin;
  37     if (End - Begin != 0)
  38       errs() << ',' << End;
  39     errs() << ']';
  40   }
  41
  42   /// Operator when populating CurrentChunks in Generic Delta Pass
  43   friend bool operator!=(const Chunk &C1, const Chunk &C2) {
  44     return C1.Begin != C2.Begin || C1.End != C2.End;
  45   }
  46
  47   friend bool operator==(const Chunk &C1, const Chunk &C2) {
  48     return C1.Begin == C2.Begin && C1.End == C2.End;
  49   }
  50
  51   /// Operator used for sets
  52   friend bool operator<(const Chunk &C1, const Chunk &C2) {
  53     return std::tie(C1.Begin, C1.End) < std::tie(C2.Begin, C2.End);
  54   }
  55 };
  56
  57 template<>
  58 struct DenseMapInfo<Chunk> {
  59   static inline Chunk getEmptyKey() {
  60     return {DenseMapInfo<int>::getEmptyKey(),
  61             DenseMapInfo<int>::getEmptyKey()};
  62   }
  63
  64   static inline Chunk getTombstoneKey() {
  65     return {DenseMapInfo<int>::getTombstoneKey(),
  66             DenseMapInfo<int>::getTombstoneKey()};
  67   }
  68
  69   static unsigned getHashValue(const Chunk Val) {
  70     std::pair<int, int> PairVal = std::make_pair(Val.Begin, Val.End);
  71     return DenseMapInfo<std::pair<int, int>>::getHashValue(PairVal);
  72   }
  73
  74   static bool isEqual(const Chunk LHS, const Chunk RHS) {
  75     return LHS == RHS;
  76   }
  77 };
  78
  79
  80 /// Provides opaque interface for querying into ChunksToKeep without having to
  81 /// actually understand what is going on.
  82 class Oracle {
  83   /// Out of all the features that we promised to be,
  84   /// how many have we already processed?
  85   int Index = 0;
  86
  87   /// The actual workhorse, contains the knowledge whether or not
  88   /// some particular feature should be preserved this time.
  89   ArrayRef<Chunk> ChunksToKeep;
  90
  91 public:
  92   explicit Oracle(ArrayRef<Chunk> ChunksToKeep) : ChunksToKeep(ChunksToKeep) {}
  93
  94   /// Should be called for each feature on which we are operating.
  95   /// Name is self-explanatory - if returns true, then it should be preserved.
  96   bool shouldKeep() {
  97     if (ChunksToKeep.empty()) {
  98       ++Index;
  99       return false; // All further features are to be discarded.
 100     }
 101
 102     // Does the current (front) chunk contain such a feature?
 103     bool ShouldKeep = ChunksToKeep.front().contains(Index);
 104
 105     // Is this the last feature in the chunk?
 106     if (ChunksToKeep.front().End == Index)
 107       ChunksToKeep = ChunksToKeep.drop_front(); // Onto next chunk.
 108
 109     ++Index;
 110
 111     return ShouldKeep;
 112   }
 113
 114   int count() { return Index; }
 115 };
 116
 117 using ReductionFunc = function_ref<void(Oracle &, ReducerWorkItem &)>;
 118
 119 /// This function implements the Delta Debugging algorithm, it receives a
 120 /// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
 121 /// splits them in half; these chunks of targets are then tested while ignoring
 122 /// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
 123 /// it is removed from consideration. The algorithm will attempt to split the
 124 /// Chunks in half and start the process again until it can't split chunks
 125 /// anymore.
 126 ///
 127 /// This function is intended to be called by each specialized delta pass (e.g.
 128 /// RemoveFunctions) and receives three key parameters:
 129 /// * Test: The main TestRunner instance which is used to run the provided
 130 /// interesting-ness test, as well as to store and access the reduced Program.
 131 /// * ExtractChunksFromModule: A function used to tailor the main program so it
 132 /// only contains Targets that are inside Chunks of the given iteration.
 133 /// Note: This function is implemented by each specialized Delta pass
 134 ///
 135 /// Other implementations of the Delta Debugging algorithm can also be found in
 136 /// the CReduce, Delta, and Lithium projects.
 137 void runDeltaPass(TestRunner &Test, ReductionFunc ExtractChunksFromModule,
 138                   StringRef Message);
 139 } // namespace llvm
 140
 141 #endif