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