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