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