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
|
//===- Delta.h - Delta Debugging Algorithm Implementation -----------------===//
//
// 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 "TestRunner.h"
#include "llvm/ADT/ScopeExit.h"
#include <functional>
#include <utility>
#include <vector>
namespace llvm {
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;
}
/// 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);
}
};
/// 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; }
};
/// 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,
function_ref<void(Oracle &, Module &)> ExtractChunksFromModule);
void runDeltaPass(
TestRunner &Test,
function_ref<void(Oracle &, MachineFunction &)> ExtractChunksFromModule);
} // namespace llvm
#endif
|
