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
24namespace llvm {
25
26class TestRunner;
27
28struct 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(args: C1.Begin, args: C1.End) < std::tie(args: C2.Begin, args: C2.End);
54 }
55};
56
57template<>
58struct DenseMapInfo<Chunk> {
59 static inline Chunk getEmptyKey() {
60 return {.Begin: DenseMapInfo<int>::getEmptyKey(),
61 .End: DenseMapInfo<int>::getEmptyKey()};
62 }
63
64 static inline Chunk getTombstoneKey() {
65 return {.Begin: DenseMapInfo<int>::getTombstoneKey(),
66 .End: DenseMapInfo<int>::getTombstoneKey()};
67 }
68
69 static unsigned getHashValue(const Chunk Val) {
70 std::pair<int, int> PairVal = std::make_pair(x: Val.Begin, y: 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.
82class 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
91public:
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
117using 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.
137void runDeltaPass(TestRunner &Test, ReductionFunc ExtractChunksFromModule,
138 StringRef Message);
139} // namespace llvm
140
141#endif
142