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 24 namespace llvm { 25 26 class TestRunner; 27 28 struct Chunk { 29 int Begin; 30 int End; 31 32 /// Helper function to verify if a given Target-index is inside the Chunk containsChunk33 bool contains(int Index) const { return Index >= Begin && Index <= End; } 34 printChunk35 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(C1.Begin, C1.End) < std::tie(C2.Begin, C2.End); 54 } 55 }; 56 57 template<> 58 struct DenseMapInfo<Chunk> { 59 static inline Chunk getEmptyKey() { 60 return {DenseMapInfo<int>::getEmptyKey(), 61 DenseMapInfo<int>::getEmptyKey()}; 62 } 63 64 static inline Chunk getTombstoneKey() { 65 return {DenseMapInfo<int>::getTombstoneKey(), 66 DenseMapInfo<int>::getTombstoneKey()}; 67 } 68 69 static unsigned getHashValue(const Chunk Val) { 70 std::pair<int, int> PairVal = std::make_pair(Val.Begin, 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. 82 class 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 91 public: 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 117 using 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. 137 void runDeltaPass(TestRunner &Test, ReductionFunc ExtractChunksFromModule, 138 StringRef Message); 139 } // namespace llvm 140 141 #endif 142