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