| 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 |