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_LLVMREDUCE_LLVMREDUCE_DELTA_H
16 #define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_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? 1-based!
56   int Index = 1;
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_)
64       : ChunksToKeep(ChunksToKeep_) {}
65 
66   /// Should be called for each feature on which we are operating.
67   /// Name is self-explanatory - if returns true, then it should be preserved.
shouldKeep()68   bool shouldKeep() {
69     if (ChunksToKeep.empty())
70       return false; // All further features are to be discarded.
71 
72     // Does the current (front) chunk contain such a feature?
73     bool ShouldKeep = ChunksToKeep.front().contains(Index);
74     auto _ = make_scope_exit([&]() { ++Index; }); // Next time - next feature.
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     return ShouldKeep;
81   }
82 };
83 
84 /// This function implements the Delta Debugging algorithm, it receives a
85 /// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
86 /// splits them in half; these chunks of targets are then tested while ignoring
87 /// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
88 /// it is removed from consideration. The algorithm will attempt to split the
89 /// Chunks in half and start the process again until it can't split chunks
90 /// anymore.
91 ///
92 /// This function is intended to be called by each specialized delta pass (e.g.
93 /// RemoveFunctions) and receives three key parameters:
94 /// * Test: The main TestRunner instance which is used to run the provided
95 /// interesting-ness test, as well as to store and access the reduced Program.
96 /// * Targets: The amount of Targets that are going to be reduced by the
97 /// algorithm, for example, the RemoveGlobalVars pass would send the amount of
98 /// initialized GVs.
99 /// * ExtractChunksFromModule: A function used to tailor the main program so it
100 /// only contains Targets that are inside Chunks of the given iteration.
101 /// Note: This function is implemented by each specialized Delta pass
102 ///
103 /// Other implementations of the Delta Debugging algorithm can also be found in
104 /// the CReduce, Delta, and Lithium projects.
105 void runDeltaPass(TestRunner &Test, int Targets,
106                   std::function<void(const std::vector<Chunk> &, Module *)>
107                       ExtractChunksFromModule);
108 } // namespace llvm
109 
110 #endif
111