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