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