From d4d00ae6a254f6ee42a044cf5c7b804fd1ec60b2 Mon Sep 17 00:00:00 2001 From: Diego Trevino Ferrer Date: Wed, 7 Aug 2019 21:51:54 +0000 Subject: [PATCH] Revert Added Delta IR Reduction Tool This reverts r368071 (git commit a2584978f5bb41973d65a145b0d9459b81e3ac6d) llvm-svn: 368217 --- llvm/docs/BugpointRedesign.md | 105 ----------- llvm/test/Reduce/Inputs/remove-funcs.sh | 10 -- llvm/test/Reduce/remove-funcs.ll | 34 ---- llvm/tools/LLVMBuild.txt | 1 - llvm/tools/llvm-reduce/CMakeLists.txt | 24 --- llvm/tools/llvm-reduce/DeltaManager.h | 25 --- llvm/tools/llvm-reduce/LLVMBuild.txt | 24 --- llvm/tools/llvm-reduce/TestRunner.cpp | 60 ------- llvm/tools/llvm-reduce/TestRunner.h | 56 ------ llvm/tools/llvm-reduce/deltas/Delta.cpp | 203 ---------------------- llvm/tools/llvm-reduce/deltas/Delta.h | 89 ---------- llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp | 80 --------- llvm/tools/llvm-reduce/deltas/ReduceFunctions.h | 20 --- llvm/tools/llvm-reduce/llvm-reduce.cpp | 105 ----------- 14 files changed, 836 deletions(-) delete mode 100644 llvm/docs/BugpointRedesign.md delete mode 100755 llvm/test/Reduce/Inputs/remove-funcs.sh delete mode 100644 llvm/test/Reduce/remove-funcs.ll delete mode 100644 llvm/tools/llvm-reduce/CMakeLists.txt delete mode 100644 llvm/tools/llvm-reduce/DeltaManager.h delete mode 100644 llvm/tools/llvm-reduce/LLVMBuild.txt delete mode 100644 llvm/tools/llvm-reduce/TestRunner.cpp delete mode 100644 llvm/tools/llvm-reduce/TestRunner.h delete mode 100644 llvm/tools/llvm-reduce/deltas/Delta.cpp delete mode 100644 llvm/tools/llvm-reduce/deltas/Delta.h delete mode 100644 llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp delete mode 100644 llvm/tools/llvm-reduce/deltas/ReduceFunctions.h delete mode 100644 llvm/tools/llvm-reduce/llvm-reduce.cpp diff --git a/llvm/docs/BugpointRedesign.md b/llvm/docs/BugpointRedesign.md deleted file mode 100644 index 98a271f..0000000 --- a/llvm/docs/BugpointRedesign.md +++ /dev/null @@ -1,105 +0,0 @@ -# Bugpoint Redesign -Author: Diego Treviño (diegotf@google.com) - -Date: 2019-06-05 - -Status: Draft - - -## Introduction -As use of bugpoint has grown several areas of improvement have been identified -through years of use: confusing to use, slow, it doesn’t always produce high -quality test cases, etc. This document proposes a new approach with a narrower -focus: minimization of IR test cases. - - -## Proposed New Design - - -### Narrow focus: test-case reduction -The main focus will be a code reduction strategy to obtain much smaller test -cases that still have the same property as the original one. This will be done -via classic delta debugging and by adding some IR-specific reductions (e.g. -replacing globals, removing unused instructions, etc), similar to what -already exists, but with more in-depth minimization. - - -Granted, if the community differs on this proposal, the legacy code could still -be present in the tool, but with the caveat of still being documented and -designed towards delta reduction. - - -### Command-Line Options -We are proposing to reduce the plethora of bugpoint’s options to just two: an -interesting-ness test and the arguments for said test, similar to other delta -reduction tools such as CReduce, Delta, and Lithium; the tool should feel less - cluttered, and there should also be no uncertainty about how to operate it. - - -The interesting-ness test that’s going to be run to reduce the code is given -by name: - `--test=` -If a `--test` option is not given, the program exits; this option is similar -to bugpoint’s current `-compile-custom` option, which lets the user run a -custom script. - - -The interesting-ness test would be defined as a script that returns 0 when the -IR achieves a user-defined behaviour (e.g. failure to compile on clang) and a -nonzero value when otherwise. Leaving the user the freedom to determine what is -and isn’t interesting to the tool, and thus, streamlining the process of -reducing a test-case. - - -If the test accepts any arguments (excluding the input ll/bc file), they are -given via the following flag: - `--test_args=` -If unspecified, the test is run as given. It’s worth noting that the input file -would be passed as a parameter to the test, similar how `-compile-custom` -currently operates. - - -### Implementation -The tool would behave similar to CReduce’s functionality in that it would have a -list of passes that try to minimize the given test-case. We should be able to -modularize the tool’s behavior, as well as making it easier to maintain and -expand. - - -The first version of this redesign would try to: - - -* Discard functions, instructions and metadata that don’t influence the - interesting-ness test -* Remove unused parameters from functions -* Eliminate unvisited conditional paths -* Rename variables to more regular ones (such as “a”, “b”, “c”, etc.) - - -Once these passes are implemented, more meaningful reductions (such as type -reduction) would be added to the tool, to even further reduce IR. - - -## Background on historical bugpoint issues - - -### Root Cause Analysis -Presently, bugpoint takes a long time to find the source problem in a given IR -file, mainly due to the fact that it tries to debug the input by running -various strategies to classify the bug, which in turn run multiple optimizer -and compilation passes over the input, taking up a lot of time. Furthermore, -when the IR crashes, it tries to reduce it by performing some sub-optimal -passes (e.g. a lot of unreachable blocks), and sometimes even fails to minimize -at all. - - -### "Quirky" Interface -Bugpoint’s current interface overwhelms and confuses the user, the help screen -alone ends up confusing rather providing guidance, as seen below: - -![Bugpoint's help option showcase](https://lh6.googleusercontent.com/sbpaSVHzpVVZKKAgHL9gvfzTWdgh3ju0KiDYql6WmWZfDYrdauOJMcuo9PP_V1dq8JQfMHOSKTv3lJcSpVytUyU8r5tJ2KTlGB0b2ve7jsZ3nVX8K8ItAbsA0JWkFKw67VJnq99m) - -And, not only are there numerous features and options, but some of them also -work in unexpected ways and most of the time the user ends up using a custom -script. Pruning and simplifying the interface will be worth considering in -order to make the tool more useful in the general case and easier to maintain. diff --git a/llvm/test/Reduce/Inputs/remove-funcs.sh b/llvm/test/Reduce/Inputs/remove-funcs.sh deleted file mode 100755 index 1b0bb53..0000000 --- a/llvm/test/Reduce/Inputs/remove-funcs.sh +++ /dev/null @@ -1,10 +0,0 @@ -#!/bin/sh -set -e - -matches=$(cat $1 | grep "@interesting" | wc -l) - -if [[ $matches > 0 ]]; then - exit 0 -else - exit 1 -fi diff --git a/llvm/test/Reduce/remove-funcs.ll b/llvm/test/Reduce/remove-funcs.ll deleted file mode 100644 index 6125f7f..0000000 --- a/llvm/test/Reduce/remove-funcs.ll +++ /dev/null @@ -1,34 +0,0 @@ -; Test that llvm-reduce can remove uninteresting functions as well as -; their InstCalls. -; -; RUN: llvm-reduce --test %p/Inputs/remove-funcs.sh %s -; RUN: cat reduced.ll | FileCheck %s -; REQUIRES: plugins, shell - -; CHECK-NOT: uninteresting1() -define i32 @uninteresting1() { -entry: - ret i32 0 -} - -; CHECK: interesting() -define i32 @interesting() { -entry: - ; CHECK: call i32 @interesting() - %call2 = call i32 @interesting() - ; CHECK-NOT: call i32 @uninteresting1() - %call = call i32 @uninteresting1() - ret i32 5 -} - -; CHECK-NOT: uninteresting2() -define i32 @uninteresting2() { -entry: - ret i32 0 -} - -; CHECK-NOT: uninteresting3() -define i32 @uninteresting3() { -entry: - ret i32 10 -} diff --git a/llvm/tools/LLVMBuild.txt b/llvm/tools/LLVMBuild.txt index b5c14b9..03a6975 100644 --- a/llvm/tools/LLVMBuild.txt +++ b/llvm/tools/LLVMBuild.txt @@ -48,7 +48,6 @@ subdirectories = llvm-pdbutil llvm-profdata llvm-rc - llvm-reduce llvm-rtdyld llvm-size llvm-split diff --git a/llvm/tools/llvm-reduce/CMakeLists.txt b/llvm/tools/llvm-reduce/CMakeLists.txt deleted file mode 100644 index 1de3a9a..0000000 --- a/llvm/tools/llvm-reduce/CMakeLists.txt +++ /dev/null @@ -1,24 +0,0 @@ -set(LLVM_LINK_COMPONENTS - AllTargetsAsmParsers - AllTargetsCodeGens - AllTargetsDescs - AllTargetsInfos - IRReader - Support - Target - TransformUtils - ) - -# Support plugins. -set(LLVM_NO_DEAD_STRIP 1) - -add_llvm_tool(llvm-reduce - llvm-reduce.cpp - TestRunner.cpp - deltas/Delta.cpp - deltas/ReduceFunctions.cpp - - DEPENDS - intrinsics_gen - ) -export_executable_symbols(llvm-reduce) diff --git a/llvm/tools/llvm-reduce/DeltaManager.h b/llvm/tools/llvm-reduce/DeltaManager.h deleted file mode 100644 index 28d1cd9..0000000 --- a/llvm/tools/llvm-reduce/DeltaManager.h +++ /dev/null @@ -1,25 +0,0 @@ -//===- DeltaManager.h - Runs Delta Passes to reduce Input -----------------===// -// -// 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 calls each specialized Delta pass in order to reduce the input IR -// file. -// -//===----------------------------------------------------------------------===// - -#include "TestRunner.h" -#include "deltas/Delta.h" -#include "deltas/ReduceFunctions.h" - -namespace llvm { - -inline void runDeltaPasses(TestRunner &Tester) { - reduceFunctionsDeltaPass(Tester); - // TODO: Implement the remaining Delta Passes -} - -} // namespace llvm diff --git a/llvm/tools/llvm-reduce/LLVMBuild.txt b/llvm/tools/llvm-reduce/LLVMBuild.txt deleted file mode 100644 index 7928f05..0000000 --- a/llvm/tools/llvm-reduce/LLVMBuild.txt +++ /dev/null @@ -1,24 +0,0 @@ -;===- ./tools/llvm-reduce/LLVMBuild.txt ------------------------*- Conf -*--===; -; -; 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 is an LLVMBuild description file for the components in this subdirectory. -; -; For more information on the LLVMBuild system, please see: -; -; http://llvm.org/docs/LLVMBuild.html -; -;===------------------------------------------------------------------------===; - -[component_0] -type = Tool -name = llvm-reduce -parent = Tools -required_libraries = - BitReader - IRReader - all-targets diff --git a/llvm/tools/llvm-reduce/TestRunner.cpp b/llvm/tools/llvm-reduce/TestRunner.cpp deleted file mode 100644 index 06fb4da..0000000 --- a/llvm/tools/llvm-reduce/TestRunner.cpp +++ /dev/null @@ -1,60 +0,0 @@ -//===-- TestRunner.cpp ----------------------------------------------------===// -// -// 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 -// -//===----------------------------------------------------------------------===// - -#include "TestRunner.h" -#include - -using namespace llvm; - -/// Gets Current Working Directory and tries to create a Tmp Directory -static SmallString<128> initializeTmpDirectory() { - SmallString<128> CWD; - if (std::error_code EC = sys::fs::current_path(CWD)) { - errs() << "Error getting current directory: " << EC.message() << "!\n"; - exit(1); - } - - SmallString<128> TmpDirectory; - sys::path::append(TmpDirectory, CWD, "tmp"); - if (std::error_code EC = sys::fs::create_directory(TmpDirectory)) - errs() << "Error creating tmp directory: " << EC.message() << "!\n"; - - return TmpDirectory; -} - -TestRunner::TestRunner(StringRef TestName, std::vector TestArgs, - StringRef ReducedFilepath) - : TestName(TestName), TestArgs(std::move(TestArgs)), - ReducedFilepath(ReducedFilepath) { - TmpDirectory = initializeTmpDirectory(); -} - -/// Runs the interestingness test, passes file to be tested as first argument -/// and other specified test arguments after that. -int TestRunner::run(StringRef Filename) { - std::vector ProgramArgs; - ProgramArgs.push_back(TestName); - ProgramArgs.push_back(Filename); - - for (auto Arg : TestArgs) - ProgramArgs.push_back(Arg.c_str()); - for (unsigned I = 0, E = ProgramArgs.size(); I != E; ++I) - outs() << ProgramArgs[I] << "\n"; - StringRef SR = ""; - Optional Redirects[3] = {SR, SR, SR}; // STDIN, STDOUT, STDERR - int Result = sys::ExecuteAndWait(TestName, ProgramArgs, None, Redirects); - - if (Result < 0) { - Error E = make_error("Error running interesting-ness test\n", - inconvertibleErrorCode()); - outs() << toString(std::move(E)); - exit(1); - } - - return !Result; -} diff --git a/llvm/tools/llvm-reduce/TestRunner.h b/llvm/tools/llvm-reduce/TestRunner.h deleted file mode 100644 index 4d5b5bb..0000000 --- a/llvm/tools/llvm-reduce/TestRunner.h +++ /dev/null @@ -1,56 +0,0 @@ -//===-- tools/llvm-reduce/TestRunner.h ---------------------------*- C++ -*-===/ -// -// 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 -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H -#define LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H - -#include "llvm/ADT/SmallString.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/Error.h" -#include "llvm/Support/FileSystem.h" -#include "llvm/Support/Path.h" -#include "llvm/Support/Program.h" -#include - -namespace llvm { - -// This class contains all the info necessary for running the provided -// interesting-ness test, as well as the most reduced module and its -// respective filename. -class TestRunner { -public: - TestRunner(StringRef TestName, std::vector TestArgs, - StringRef ReducedFilepath); - - /// Runs the interesting-ness test for the specified file - /// @returns 0 if test was successful, 1 if otherwise - int run(StringRef Filename); - - /// Filename to the most reduced testcase - StringRef getReducedFilepath() const { return ReducedFilepath; } - /// Directory where tmp files are created - StringRef getTmpDir() const { return TmpDirectory; } - /// Returns the most reduced version of the original testcase - Module *getProgram() const { return Program.get(); } - - void setReducedFilepath(SmallString<128> F) { - ReducedFilepath = std::move(F); - } - void setProgram(std::unique_ptr P) { Program = std::move(P); } - -private: - SmallString<128> TestName; - std::vector TestArgs; - SmallString<128> ReducedFilepath; - SmallString<128> TmpDirectory; - std::unique_ptr Program; -}; - -} // namespace llvm - -#endif diff --git a/llvm/tools/llvm-reduce/deltas/Delta.cpp b/llvm/tools/llvm-reduce/deltas/Delta.cpp deleted file mode 100644 index 9ff0a78..0000000 --- a/llvm/tools/llvm-reduce/deltas/Delta.cpp +++ /dev/null @@ -1,203 +0,0 @@ -//===- Delta.cpp - 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. -// -//===----------------------------------------------------------------------===// - -#include "Delta.h" -#include "llvm/Transforms/Utils/Cloning.h" - -/// Writes IR code to the given Filepath -static bool writeProgramToFile(StringRef Filepath, int FD, const Module &M) { - ToolOutputFile Out(Filepath, FD); - M.print(Out.os(), /*AnnotationWriter=*/nullptr); - Out.os().close(); - - if (!Out.os().has_error()) { - Out.keep(); - return false; - } - return true; -} - -/// Creates a temporary (and unique) file inside the tmp folder and writes -/// the given module IR. -static SmallString<128> createTmpFile(Module *M, StringRef TmpDir) { - SmallString<128> UniqueFilepath; - int UniqueFD; - - std::error_code EC = sys::fs::createUniqueFile(TmpDir + "/tmp-%%%.ll", - UniqueFD, UniqueFilepath); - if (EC) { - errs() << "Error making unique filename: " << EC.message() << "!\n"; - exit(1); - } - - if (writeProgramToFile(UniqueFilepath, UniqueFD, *M)) { - errs() << "Error emitting bitcode to file '" << UniqueFilepath << "'!\n"; - exit(1); - } - return UniqueFilepath; -} - -/// Prints the Chunk Indexes with the following format: [start, end], if -/// chunk is at minimum size (1), then it just displays [start]. -static void printChunks(std::vector Chunks, bool Oneline = false) { - if (Chunks.empty()) { - outs() << "No Chunks"; - return; - } - - for (auto C : Chunks) { - if (!Oneline) - outs() << '\t'; - C.print(); - if (!Oneline) - outs() << '\n'; - } -} - -/// Counts the amount of lines for a given file -static unsigned getLines(StringRef Filepath) { - unsigned Lines = 0; - std::string CurrLine; - std::ifstream FileStream(Filepath); - - while (std::getline(FileStream, CurrLine)) - ++Lines; - - return Lines; -} - -/// Splits Chunks in half and prints them. -/// If unable to split (when chunk size is 1) returns false. -static bool increaseGranularity(std::vector &Chunks) { - outs() << "Increasing granularity..."; - std::vector NewChunks; - bool SplitOne = false; - - for (auto &C : Chunks) { - if (C.end - C.begin == 0) - NewChunks.push_back(C); - else { - unsigned Half = (C.begin + C.end) / 2; - NewChunks.push_back({C.begin, Half}); - NewChunks.push_back({Half + 1, C.end}); - SplitOne = true; - } - } - if (SplitOne) { - Chunks = NewChunks; - outs() << "Success! New Chunks:\n"; - printChunks(Chunks); - } - return SplitOne; -} - -bool llvm::runTestWithoutChunks( - TestRunner &Test, std::function &, Module *)> - ExtractChunksFromModule) { - std::unique_ptr Clone = CloneModule(*Test.getProgram()); - - // Generate Module with only Targets inside Current Chunks - ExtractChunksFromModule({}, Clone.get()); - // Write Module to tmp file - SmallString<128> CurrentFilepath = - createTmpFile(Clone.get(), Test.getTmpDir()); - outs() << " | " << sys::path::filename(CurrentFilepath); - - // Completely reduced Program isn't interesting - if (!Test.run(CurrentFilepath)) - return false; - - // Hooray! We reduced the testcase completely - Test.setReducedFilepath(CurrentFilepath); - Test.setProgram(std::move(Clone)); - return true; -} - -/// Runs the Delta Debugging algorithm, splits the code into chunks and -/// reduces the amount of chunks that are considered interesting by the -/// given test. -void llvm::runDeltaPass( - TestRunner &Test, unsigned Targets, - std::function &, Module *)> - ExtractChunksFromModule) { - if (!Targets) - return; - - std::vector Chunks = {{1, Targets}}; - std::set UninterestingChunks; - std::unique_ptr ReducedProgram; - - if (!Test.run(Test.getReducedFilepath())) { - outs() << "\nInput isn't interesting! Verify interesting-ness test\n"; - outs() << "----------------------------\n"; - return; - } - - if (!increaseGranularity(Chunks)) { - outs() << "\nCan't reduce anymore\n"; - outs() << "----------------------------\n"; - return; - } - - do { - UninterestingChunks = {}; - for (int I = Chunks.size() - 1; I >= 0; --I) { - std::vector CurrentChunks; - - for (auto C : Chunks) - if (!UninterestingChunks.count(C) && C != Chunks[I]) - CurrentChunks.push_back(C); - - if (CurrentChunks.empty()) - continue; - - // Clone module before hacking it up.. - std::unique_ptr CurrentProgram = CloneModule(*Test.getProgram()); - // Generate Module with only Targets inside Current Chunks - ExtractChunksFromModule(CurrentChunks, CurrentProgram.get()); - // Write Module to tmp file - SmallString<128> CurrentFilepath = - createTmpFile(CurrentProgram.get(), Test.getTmpDir()); - - outs() << "Testing with: "; - printChunks(CurrentChunks, /*Oneline=*/true); - outs() << " | " << sys::path::filename(CurrentFilepath); - - // Current Chunks aren't interesting - if (!Test.run(CurrentFilepath)) { - outs() << "\n"; - continue; - } - - UninterestingChunks.insert(Chunks[I]); - Test.setReducedFilepath(CurrentFilepath); - ReducedProgram = std::move(CurrentProgram); - outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n"; - } - // Delete uninteresting chunks - auto UnwantedChunks = Chunks.end(); - UnwantedChunks = std::remove_if(Chunks.begin(), Chunks.end(), - [UninterestingChunks](const Chunk &C) { - return UninterestingChunks.count(C); - }); - Chunks.erase(UnwantedChunks, Chunks.end()); - - } while (!UninterestingChunks.empty() || increaseGranularity(Chunks)); - - // If we reduced the testcase replace it - if (ReducedProgram) - Test.setProgram(std::move(ReducedProgram)); - outs() << "Couldn't increase anymore.\n"; - outs() << "----------------------------\n"; -} \ No newline at end of file diff --git a/llvm/tools/llvm-reduce/deltas/Delta.h b/llvm/tools/llvm-reduce/deltas/Delta.h deleted file mode 100644 index 9078ebd..0000000 --- a/llvm/tools/llvm-reduce/deltas/Delta.h +++ /dev/null @@ -1,89 +0,0 @@ -//===- 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 "llvm/IR/Verifier.h" -#include "llvm/Support/FileSystem.h" -#include "llvm/Support/Path.h" -#include "llvm/Support/ScopedPrinter.h" -#include "llvm/Support/ToolOutputFile.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include -#include -#include - -using namespace llvm; - -struct Chunk { - unsigned begin; - unsigned end; - - /// Helper function to verify if a given Target-index is inside the Chunk - bool contains(unsigned Index) const { return Index >= begin && Index <= end; } - - void print() const { - outs() << "[" << begin; - if (end - begin != 0) - outs() << "," << end; - outs() << "]"; - } - - /// 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); - } -}; - -namespace llvm { - -/// 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, unsigned Targets, - std::function &, Module *)> - ExtractChunksFromModule); - -bool runTestWithoutChunks( - TestRunner &Test, std::function &, Module *)> - ExtractChunksFromModule); - -} // namespace llvm - -#endif diff --git a/llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp b/llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp deleted file mode 100644 index bf0e07f..0000000 --- a/llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp +++ /dev/null @@ -1,80 +0,0 @@ -//===- ReduceFunctions.cpp - Specialized Delta Pass -----------------------===// -// -// 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 implements a function which calls the Generic Delta pass in order -// to reduce functions (and any instruction that calls it) in the provided -// Module. -// -//===----------------------------------------------------------------------===// - -#include "ReduceFunctions.h" - -/// Removes all the Defined Functions (as well as their calls) -/// that aren't inside any of the desired Chunks. -/// @returns the Module stripped of out-of-chunk functions -static void extractFunctionsFromModule(const std::vector &ChunksToKeep, - Module *Program) { - // Get functions inside desired chunks - std::set FuncsToKeep; - unsigned I = 0, FunctionCount = 0; - for (auto &F : *Program) { - if (!F.isDeclaration() && I < ChunksToKeep.size()) { - if (ChunksToKeep[I].contains(++FunctionCount)) - FuncsToKeep.insert(&F); - if (FunctionCount == ChunksToKeep[I].end) - ++I; - } - } - - // Delete out-of-chunk functions, and replace their calls with undef - std::vector FuncsToRemove; - for (auto &F : *Program) { - if (!F.isDeclaration() && !FuncsToKeep.count(&F)) { - F.replaceAllUsesWith(UndefValue::get(F.getType())); - FuncsToRemove.push_back(&F); - } - } - for (auto *F : FuncsToRemove) - F->eraseFromParent(); - - // Delete instructions with undef calls - std::vector InstToRemove; - for (auto &F : *Program) - for (auto &BB : F) - for (auto &I : BB) - if (auto *Call = dyn_cast(&I)) - if (!Call->getCalledFunction()) { - // Instruction might be stored / used somewhere else - I.replaceAllUsesWith(UndefValue::get(I.getType())); - InstToRemove.push_back(&I); - } - - for (auto *I : InstToRemove) - I->eraseFromParent(); -} - -/// Counts the amount of non-declaration functions and prints their -/// respective name & index -static unsigned countDefinedFunctions(Module *Program) { - // TODO: Silence index with --quiet flag - outs() << "----------------------------\n"; - outs() << "Function Index Reference:\n"; - unsigned FunctionCount = 0; - for (auto &F : *Program) - if (!F.isDeclaration()) - outs() << "\t" << ++FunctionCount << ": " << F.getName() << "\n"; - - outs() << "----------------------------\n"; - return FunctionCount; -} - -void llvm::reduceFunctionsDeltaPass(TestRunner &Test) { - outs() << "*** Reducing Functions...\n"; - unsigned Functions = countDefinedFunctions(Test.getProgram()); - runDeltaPass(Test, Functions, extractFunctionsFromModule); -} \ No newline at end of file diff --git a/llvm/tools/llvm-reduce/deltas/ReduceFunctions.h b/llvm/tools/llvm-reduce/deltas/ReduceFunctions.h deleted file mode 100644 index 7c2cd3f..0000000 --- a/llvm/tools/llvm-reduce/deltas/ReduceFunctions.h +++ /dev/null @@ -1,20 +0,0 @@ -//===- ReduceFunctions.h - Specialized Delta Pass -------------------------===// -// -// 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 implements a function which calls the Generic Delta pass in order -// to reduce functions (and any instruction that calls it) in the provided -// Module. -// -//===----------------------------------------------------------------------===// - -#include "Delta.h" -#include "llvm/Transforms/Utils/Cloning.h" - -namespace llvm { -void reduceFunctionsDeltaPass(TestRunner &Test); -} // namespace llvm diff --git a/llvm/tools/llvm-reduce/llvm-reduce.cpp b/llvm/tools/llvm-reduce/llvm-reduce.cpp deleted file mode 100644 index 6dd733e..0000000 --- a/llvm/tools/llvm-reduce/llvm-reduce.cpp +++ /dev/null @@ -1,105 +0,0 @@ -//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===// -// -// 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 program tries to reduce an IR test case for a given interesting-ness -// test. It runs multiple delta debugging passes in order to minimize the input -// file. It's worth noting that this is a *temporary* tool that will eventually -// be integrated into the bugpoint tool itself. -// -//===----------------------------------------------------------------------===// - -#include "DeltaManager.h" -#include "llvm/ADT/SmallString.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Verifier.h" -#include "llvm/IRReader/IRReader.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/InitLLVM.h" -#include "llvm/Support/SourceMgr.h" -#include "llvm/Support/raw_ostream.h" -#include -#include - -using namespace llvm; - -static cl::opt Help("h", cl::desc("Alias for -help"), cl::Hidden); -static cl::opt Version("v", cl::desc("Alias for -version"), cl::Hidden); - -static cl::opt InputFilename(cl::Positional, cl::Required, - cl::desc("")); - -static cl::opt - TestFilename("test", cl::Required, - cl::desc("Name of the interesting-ness test to be run")); - -static cl::list - TestArguments("test-arg", cl::ZeroOrMore, - cl::desc("Arguments passed onto the interesting-ness test")); - -static cl::opt - OutputFilename("output", - cl::desc("Specify the output file. default: reduced.ll")); -static cl::alias OutputFileAlias("o", cl::desc("Alias for -output"), - cl::aliasopt(OutputFilename)); - -static cl::opt - ReplaceInput("in-place", - cl::desc("WARNING: This option will replace your input file" - "with the reduced version!")); - -// Parses IR into a Module and verifies it -static std::unique_ptr parseInputFile(StringRef Filename, - LLVMContext &Ctxt) { - SMDiagnostic Err; - std::unique_ptr Result = parseIRFile(Filename, Err, Ctxt); - if (!Result) { - Err.print("llvm-reduce", errs()); - return Result; - } - - if (verifyModule(*Result, &errs())) { - errs() << "Error: " << Filename << " - input module is broken!\n"; - return std::unique_ptr(); - } - - return Result; -} - -int main(int argc, char **argv) { - InitLLVM X(argc, argv); - - cl::ParseCommandLineOptions(argc, argv, "LLVM automatic testcase reducer.\n"); - - LLVMContext Context; - std::unique_ptr OriginalProgram = - parseInputFile(InputFilename, Context); - - // Initialize test environment - TestRunner Tester(TestFilename, TestArguments, InputFilename); - Tester.setProgram(std::move(OriginalProgram)); - - // Try to reduce code - runDeltaPasses(Tester); - StringRef ReducedFilename = sys::path::filename(Tester.getReducedFilepath()); - - if (ReducedFilename == InputFilename) { - outs() << "\nCouldnt reduce input :/\n"; - } else { - if (ReplaceInput) // In-place - OutputFilename = InputFilename.c_str(); - else if (OutputFilename.empty()) - OutputFilename = "reduced.ll"; - else - OutputFilename += ".ll"; - - sys::fs::copy_file(Tester.getReducedFilepath(), OutputFilename); - outs() << "\nDone reducing! Reduced IR to file: " << OutputFilename << "\n"; - } - - return 0; -} -- 2.7.4