diff --git a/llvm/docs/BugpointRedesign.md b/llvm/docs/BugpointRedesign.md new file mode 100644 --- /dev/null +++ b/llvm/docs/BugpointRedesign.md @@ -0,0 +1,106 @@ +# 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: + + +* Split the code into chunks and discard those that fail the given test +* 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/interestingness-test.sh b/llvm/test/Reduce/Inputs/interestingness-test.sh new file mode 100755 --- /dev/null +++ b/llvm/test/Reduce/Inputs/interestingness-test.sh @@ -0,0 +1,10 @@ +#!/bin/sh + +# lli is passed as a test-arg so lit can recognize it +ret=$($2 $1) + +if [[ $ret = 10 ]]; then + exit 0 +else + exit 1 +fi diff --git a/llvm/test/Reduce/remove-funcs.ll b/llvm/test/Reduce/remove-funcs.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Reduce/remove-funcs.ll @@ -0,0 +1,49 @@ +; Test that llvm-reduce can remove uninteresting functions as well as +; their InstCalls. +; +; RUN: llvm-reduce --test %p/Inputs/interestingness-test.sh --test-arg %lli %s +; RUN: cat reduced.ll | FileCheck %s +; REQUIRES: plugins, shell + +@.str = private unnamed_addr constant [4 x i8] c"%i\0A\00", align 1 + +; CHECK-NOT: uninteresting1() +define i32 @uninteresting1() { +entry: + ret i32 25 +} + +; CHECK: interesting() +define i32 @interesting() { +entry: + ret i32 10 +} + +; CHECK-NOT: uninteresting2() +define i32 @uninteresting2() { +entry: + ret i32 2000 +} + +; CHECK: main() +define i32 @main() { +entry: + %retval = alloca i32, align 4 + %number = alloca i32, align 4 + store i32 0, i32* %retval, align 4 + store i32 0, i32* %number, align 4 + ; CHECK-NOT: %call = call i32 @uninteresting1() + %call = call i32 @uninteresting1() + ; CHECK: %call1 = call i32 @interesting() + %call1 = call i32 @interesting() + store i32 %call1, i32* %number, align 4 + %0 = load i32, i32* %number, align 4 + %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %0) + ; CHECK-NOT: %call3 = call i32 @uninteresting1() + %call3 = call i32 @uninteresting1() + ; CHECK-NOT: %call4 = call i32 @uninteresting2() + %call4 = call i32 @uninteresting2() + ret i32 0 +} + +declare i32 @printf(i8*, ...) diff --git a/llvm/test/Reduce/remove-global-vars.ll b/llvm/test/Reduce/remove-global-vars.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Reduce/remove-global-vars.ll @@ -0,0 +1,55 @@ +; Test that llvm-reduce can remove uninteresting Global Variables as well as +; their uses (both direct and derived). +; +; RUN: llvm-reduce --test %p/Inputs/interestingness-test.sh --test-arg %lli %s +; RUN: cat reduced.ll | FileCheck %s +; REQUIRES: plugins, shell + +@uninteresting1 = global i32 0, align 4 +; CHECK: @interesting = global +@interesting = global i32 5, align 4 +; CHECK-NOT: global +@uninteresting2 = global i32 25, align 4 +@uninteresting3 = global i32 50, align 4 +@.str = private unnamed_addr constant [4 x i8] c"%i\0A\00", align 1 + +define void @func(i32* dereferenceable(4) %x) { +entry: + %x.addr = alloca i32*, align 8 + store i32* %x, i32** %x.addr, align 8 + %0 = load i32*, i32** %x.addr, align 8 + %1 = load i32, i32* %0, align 4 + %inc = add nsw i32 %1, 1 + store i32 %inc, i32* %0, align 4 + ret void +} + +define i32 @main() { +entry: + %retval = alloca i32, align 4 + store i32 0, i32* %retval, align 4 + ; CHECK-NOT: load i32, i32* @uninteresting2, align 4 + %0 = load i32, i32* @uninteresting2, align 4 + store i32 %0, i32* @interesting, align 4 + ; CHECK-NOT: load i32, i32* @uninteresting3, align 4 + %1 = load i32, i32* @uninteresting3, align 4 + %dec = add nsw i32 %1, -1 + ; CHECK-NOT: store i32 %dec, i32* @uninteresting3, align 4 + store i32 %dec, i32* @uninteresting3, align 4 + ; CHECK: load i32, i32* @interesting, align 4 + %2 = load i32, i32* @interesting, align 4 + ; CHECK-NOT: load i32, i32* @uninteresting2, align 4 + %3 = load i32, i32* @uninteresting2, align 4 + %add = add nsw i32 %2, %3 + ; CHECK-NOT: store i32 %add, i32* @uninteresting1, align 4 + store i32 %add, i32* @uninteresting1, align 4 + ; CHECK: store i32 10, i32* @interesting, align 4 + store i32 10, i32* @interesting, align 4 + ; CHECK-NOT: call void @func(i32* dereferenceable(4) @uninteresting1) + call void @func(i32* dereferenceable(4) @uninteresting1) + %4 = load i32, i32* @interesting, align 4 + %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4) + ret i32 0 +} + +declare i32 @printf(i8*, ...) diff --git a/llvm/tools/LLVMBuild.txt b/llvm/tools/LLVMBuild.txt --- a/llvm/tools/LLVMBuild.txt +++ b/llvm/tools/LLVMBuild.txt @@ -48,6 +48,7 @@ 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 new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/CMakeLists.txt @@ -0,0 +1,25 @@ +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/RemoveFunctions.cpp + deltas/RemoveGlobalVars.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 new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/DeltaManager.h @@ -0,0 +1,31 @@ +//===- 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/RemoveFunctions.h" +#include "deltas/RemoveGlobalVars.h" +#include "deltas/RemoveMetadata.h" + +namespace llvm { + +inline void runDeltaPasses(TestRunner &Tester) { + // TODO: Add option to only call certain delta passes + outs() << "Reducing functions...\n"; + removeFunctionsDeltaPass(Tester); + outs() << "Reducing GVs...\n"; + removeGlobalsDeltaPass(Tester); + // TODO: Implement the remaining Delta Passes +} + +} // namespace llvm diff --git a/llvm/tools/LLVMBuild.txt b/llvm/tools/llvm-reduce/LLVMBuild.txt copy from llvm/tools/LLVMBuild.txt copy to llvm/tools/llvm-reduce/LLVMBuild.txt --- a/llvm/tools/LLVMBuild.txt +++ b/llvm/tools/llvm-reduce/LLVMBuild.txt @@ -1,4 +1,4 @@ -;===- ./tools/LLVMBuild.txt ------------------------------------*- Conf -*--===; +;===- ./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. @@ -14,48 +14,11 @@ ; ;===------------------------------------------------------------------------===; -[common] -subdirectories = - bugpoint - dsymutil - llc - lli - llvm-ar - llvm-as - llvm-bcanalyzer - llvm-cat - llvm-cfi-verify - llvm-cov - llvm-cvtres - llvm-diff - llvm-dis - llvm-dwarfdump - llvm-dwp - llvm-elfabi - llvm-exegesis - llvm-extract - llvm-jitlistener - llvm-jitlink - llvm-link - llvm-lto - llvm-mc - llvm-mca - llvm-modextract - llvm-mt - llvm-nm - llvm-objcopy - llvm-objdump - llvm-pdbutil - llvm-profdata - llvm-rc - llvm-rtdyld - llvm-size - llvm-split - llvm-undname - opt - verify-uselistorder - [component_0] -type = Group -name = Tools -parent = $ROOT +type = Tool +name = llvm-reduce +parent = Tools +required_libraries = + BitReader + IRReader + all-targets diff --git a/llvm/tools/llvm-reduce/TestRunner.h b/llvm/tools/llvm-reduce/TestRunner.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/TestRunner.h @@ -0,0 +1,52 @@ +//===-- 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/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, SmallString<128> TmpDirectory); + + /// 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 = 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/TestRunner.cpp b/llvm/tools/llvm-reduce/TestRunner.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/TestRunner.cpp @@ -0,0 +1,40 @@ +//===-- 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" + +using namespace llvm; + +TestRunner::TestRunner(StringRef TestName, std::vector TestArgs, + StringRef ReducedFilepath, SmallString<128> TmpDirectory) + : TestName(TestName), TestArgs(TestArgs), ReducedFilepath(ReducedFilepath), + TmpDirectory(TmpDirectory) {} + +/// 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 (unsigned I = 0, E = TestArgs.size(); I != E; ++I) + ProgramArgs.push_back(TestArgs[I].c_str()); + + 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/deltas/Delta.h b/llvm/tools/llvm-reduce/deltas/Delta.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/Delta.h @@ -0,0 +1,74 @@ +//===- 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/Support/FileSystem.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/ScopedPrinter.h" +#include "llvm/Support/ToolOutputFile.h" +#include +#include +#include + +using namespace llvm; + +struct Chunk { + int begin; + int end; + + /// 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 C1.begin < C2.begin; + } +}; + +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, int Targets, + std::function(std::vector, Module *)> + ExtractChunksFromModule); + +} // namespace llvm + +#endif diff --git a/llvm/tools/llvm-reduce/deltas/Delta.cpp b/llvm/tools/llvm-reduce/deltas/Delta.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/Delta.cpp @@ -0,0 +1,171 @@ +//===- 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" + +/// 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) { + for (auto C : Chunks) { + if (!Oneline) + outs() << '\t'; + outs() << "[" << C.begin; + if (C.end - C.begin != 0) + outs() << "," << C.end; + outs() << "]"; + 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 { + int 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; +} + +void llvm::runDeltaPass( + TestRunner &Test, int Targets, + std::function(std::vector, Module *)> + ExtractChunksFromModule) { + if (!Targets) + return; + + std::vector Chunks = {{1, Targets}}; + std::set UninterestingChunks; + std::unique_ptr ReducedProgram; + + if (!Test.run(Test.getReducedFilepath()) || !increaseGranularity(Chunks)) { + outs() << "\nCouldn't reduce\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()) + break; + + // Generate Module with only Targets inside Current Chunks + std::unique_ptr CurrentProgram = + ExtractChunksFromModule(CurrentChunks, Test.getProgram()); + // 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; + } + // We only care about interesting chunks if they reduce the testcase + if (getLines(CurrentFilepath) < getLines(Test.getReducedFilepath())) { + UninterestingChunks.insert(Chunks[I]); + Test.setReducedFilepath(CurrentFilepath); + ReducedProgram = std::move(CurrentProgram); + outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath); + } + outs() << "\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/RemoveFunctions.h b/llvm/tools/llvm-reduce/deltas/RemoveFunctions.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/RemoveFunctions.h @@ -0,0 +1,20 @@ +//===- RemoveFunctions.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 removeFunctionsDeltaPass(TestRunner &Test); +} // namespace llvm diff --git a/llvm/tools/llvm-reduce/deltas/RemoveFunctions.cpp b/llvm/tools/llvm-reduce/deltas/RemoveFunctions.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/RemoveFunctions.cpp @@ -0,0 +1,86 @@ +//===- RemoveFunctions.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 "RemoveFunctions.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 std::unique_ptr +extractFunctionsFromModule(std::vector ChunksToKeep, Module *Program) { + std::unique_ptr Clone = CloneModule(*Program); + + // Get functions inside desired chunks + std::set FuncsToKeep; + int I = 0, FunctionCount = 1; + for (auto &F : *Clone) { + if (!F.isDeclaration() && I < ChunksToKeep.size()) { + if (FunctionCount >= ChunksToKeep[I].begin && + FunctionCount <= ChunksToKeep[I].end) + FuncsToKeep.insert(&F); + if (FunctionCount == ChunksToKeep[I].end) + ++I; + ++FunctionCount; + } + } + + // Delete out-of-chunk functions, and replace their calls with undef + std::vector FuncsToRemove; + for (auto &F : *Clone) { + 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 : *Clone) + 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(); + + return Clone; +} + +/// Counts the amount of non-declaration functions and prints their +/// respective name & index +static int countFunctions(Module *Program) { + // TODO: Silence index with --quiet flag + outs() << "----------------------------\n"; + outs() << "Function Index Reference:\n"; + int FunctionCount = 0; + for (auto &F : *Program) + if (!F.isDeclaration()) { + ++FunctionCount; + outs() << "\t" << FunctionCount << ": " << F.getName() << "\n"; + } + outs() << "----------------------------\n"; + return FunctionCount; +} + +void llvm::removeFunctionsDeltaPass(TestRunner &Test) { + int FunctionCount = countFunctions(Test.getProgram()); + runDeltaPass(Test, FunctionCount, extractFunctionsFromModule); +} \ No newline at end of file diff --git a/llvm/tools/llvm-reduce/deltas/RemoveGlobalVars.h b/llvm/tools/llvm-reduce/deltas/RemoveGlobalVars.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/RemoveGlobalVars.h @@ -0,0 +1,20 @@ +//===- RemoveGlobalVars.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 initialized Global Variables in the provided Module. +// +//===----------------------------------------------------------------------===// + +#include "Delta.h" +#include "llvm/IR/Value.h" +#include "llvm/Transforms/Utils/Cloning.h" + +namespace llvm { +void removeGlobalsDeltaPass(TestRunner &Test); +} // namespace llvm diff --git a/llvm/tools/llvm-reduce/deltas/RemoveGlobalVars.cpp b/llvm/tools/llvm-reduce/deltas/RemoveGlobalVars.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/RemoveGlobalVars.cpp @@ -0,0 +1,81 @@ +//===- RemoveGlobalVars.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 initialized Global Variables in the provided Module. +// +//===----------------------------------------------------------------------===// + +#include "RemoveGlobalVars.h" + +/// Removes all the Initialized GVs that aren't inside the desired Chunks. +/// @returns the Module stripped of out-of-chunk GVs +static std::unique_ptr +extractGVsFromModule(std::vector ChunksToKeep, Module *Program) { + std::unique_ptr Clone = CloneModule(*Program); + + // Get GVs inside desired chunks + std::set GVsToKeep; + int I = 0, GVCount = 1; + for (auto &GV : Clone->globals()) { + if (GV.hasInitializer() && I < ChunksToKeep.size()) { + if (GVCount >= ChunksToKeep[I].begin && GVCount <= ChunksToKeep[I].end) + GVsToKeep.insert(&GV); + if (GVCount == ChunksToKeep[I].end) + ++I; + ++GVCount; + } + } + + std::vector ToRemove; + std::vector InstToRemove; + for (auto &GV : Clone->globals()) { + if (GV.hasInitializer() && !GVsToKeep.count(&GV)) { + // Get all Instruction uses of the GV + for (auto U : GV.users()) + if (auto *I = dyn_cast(U)) + InstToRemove.push_back(I); + + GV.replaceAllUsesWith(UndefValue::get(GV.getType())); + ToRemove.push_back(&GV); + } + } + + // Delete direct use of GV + for (auto *I : InstToRemove) { + I->replaceAllUsesWith(UndefValue::get(I->getType())); + I->eraseFromParent(); + } + + // Delete out-of-chunk GVs + for (auto *GV : ToRemove) + GV->eraseFromParent(); + + return Clone; +} + +/// Counts the amount of initialized GVs and displays their +/// respective name & index +static int countGVs(Module *Program) { + // TODO: Silence index with --quiet flag + outs() << "----------------------------\n"; + outs() << "GlobalVariable Index Reference:\n"; + int GVCount = 0; + for (auto &GV : Program->globals()) + if (GV.hasInitializer()) { + ++GVCount; + outs() << "\t" << GVCount << ": " << GV.getName() << "\n"; + } + outs() << "----------------------------\n"; + return GVCount; +} + +void llvm::removeGlobalsDeltaPass(TestRunner &Test) { + int GVCount = countGVs(Test.getProgram()); + runDeltaPass(Test, GVCount, extractGVsFromModule); +} \ No newline at end of file diff --git a/llvm/tools/llvm-reduce/llvm-reduce.cpp b/llvm/tools/llvm-reduce/llvm-reduce.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/llvm-reduce.cpp @@ -0,0 +1,123 @@ +//===- 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 part of the bugpoint redesign +// proposal, and thus 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; +} + +/// 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; +} + +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 + SmallString<128> TmpDirectory = initializeTmpDirectory(); + TestRunner Tester(TestFilename, TestArguments, InputFilename, TmpDirectory); + 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; +}