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,105 @@ +# 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.py b/llvm/test/Reduce/Inputs/remove-funcs.py new file mode 100755 --- /dev/null +++ b/llvm/test/Reduce/Inputs/remove-funcs.py @@ -0,0 +1,10 @@ +#!/usr/bin/env python + +import sys + +input = open(sys.argv[1], "r") +for line in input: + if "@interesting" in line: + sys.exit(0) + +sys.exit(1) 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,34 @@ +; Test that llvm-reduce can remove uninteresting functions as well as +; their InstCalls. +; +; RUN: llvm-reduce --test %p/Inputs/remove-funcs.py %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 --- 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,24 @@ +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 new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/DeltaManager.h @@ -0,0 +1,25 @@ +//===- 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/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,56 @@ +//===-- 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/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,58 @@ +//===-- 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; + +/// 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()); + + 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,84 @@ +//===- 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); +} // 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,182 @@ +//===- 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; + + SmallString<128> TmpFilepath; + sys::path::append(TmpFilepath, TmpDir, "tmp-%%%.ll"); + std::error_code EC = + sys::fs::createUniqueFile(TmpFilepath, 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; +} + +/// 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/ReduceFunctions.h b/llvm/tools/llvm-reduce/deltas/ReduceFunctions.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceFunctions.h @@ -0,0 +1,20 @@ +//===- 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/deltas/ReduceFunctions.cpp b/llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp @@ -0,0 +1,80 @@ +//===- 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/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,105 @@ +//===- 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 == sys::path::filename(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; +}