| //===- Delta.h - Delta Debugging Algorithm Implementation -----------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file contains the implementation for the Delta Debugging Algorithm: |
| // it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.) |
| // into chunks and tries to reduce the number chunks that are interesting. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H |
| #define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H |
| |
| #include "TestRunner.h" |
| #include <vector> |
| #include <utility> |
| #include <functional> |
| |
| namespace llvm { |
| |
| struct Chunk { |
| int begin; |
| int end; |
| |
| /// Helper function to verify if a given Target-index is inside the Chunk |
| bool contains(int Index) const { return Index >= begin && Index <= end; } |
| |
| void print() const { |
| errs() << "[" << begin; |
| if (end - begin != 0) |
| errs() << "," << end; |
| errs() << "]"; |
| } |
| |
| /// Operator when populating CurrentChunks in Generic Delta Pass |
| friend bool operator!=(const Chunk &C1, const Chunk &C2) { |
| return C1.begin != C2.begin || C1.end != C2.end; |
| } |
| |
| /// Operator used for sets |
| friend bool operator<(const Chunk &C1, const Chunk &C2) { |
| return std::tie(C1.begin, C1.end) < std::tie(C2.begin, C2.end); |
| } |
| }; |
| |
| /// This function implements the Delta Debugging algorithm, it receives a |
| /// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and |
| /// splits them in half; these chunks of targets are then tested while ignoring |
| /// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test) |
| /// it is removed from consideration. The algorithm will attempt to split the |
| /// Chunks in half and start the process again until it can't split chunks |
| /// anymore. |
| /// |
| /// This function is intended to be called by each specialized delta pass (e.g. |
| /// RemoveFunctions) and receives three key parameters: |
| /// * Test: The main TestRunner instance which is used to run the provided |
| /// interesting-ness test, as well as to store and access the reduced Program. |
| /// * Targets: The amount of Targets that are going to be reduced by the |
| /// algorithm, for example, the RemoveGlobalVars pass would send the amount of |
| /// initialized GVs. |
| /// * ExtractChunksFromModule: A function used to tailor the main program so it |
| /// only contains Targets that are inside Chunks of the given iteration. |
| /// Note: This function is implemented by each specialized Delta pass |
| /// |
| /// Other implementations of the Delta Debugging algorithm can also be found in |
| /// the CReduce, Delta, and Lithium projects. |
| void runDeltaPass(TestRunner &Test, int Targets, |
| std::function<void(const std::vector<Chunk> &, Module *)> |
| ExtractChunksFromModule); |
| } // namespace llvm |
| |
| #endif |