diff --git a/llvm/test/tools/llvm-mir-reduce/instr-reduce.mir b/llvm/test/tools/llvm-mir-reduce/instr-reduce.mir new file mode 100644 --- /dev/null +++ b/llvm/test/tools/llvm-mir-reduce/instr-reduce.mir @@ -0,0 +1,31 @@ +# RUN: llvm-mir-reduce -mtriple=riscv32 --test %python --test-arg %p/instr-reduce.py %s -o %t +# RUN: cat %t | FileCheck --match-full-lines %s + +# REQUIRES: plugins +# REQUIRES: riscv-registered-target + +# Verify that after reduction the following instruction sequence remains. The +# interestingness-test 'instr-reduce.py' matches a '%[0-9]+:gpr = ADDI %[0-9]+, 5' +# pattern in the output and that combined with that the MIR has to be valid +# (pass verify) results in the given sequence. + +# CHECK: %0:gpr = COPY $x10 +# CHECK-NEXT: %2:gpr = ADDI %0, 5 +# CHECK-NEXT: PseudoRET implicit $x10 + +... +--- +name: f +tracksRegLiveness: true +body: | + bb.0: + liveins: $x10 + + %10:gpr = COPY $x10 + %20:gpr = ADDI %10, 1 + %30:gpr = ADDI %20, 5 + %40:gpr = ADDI %30, 9 + $x10 = COPY %40 + PseudoRET implicit $x10 +... +--- diff --git a/llvm/test/tools/llvm-mir-reduce/instr-reduce.py b/llvm/test/tools/llvm-mir-reduce/instr-reduce.py new file mode 100755 --- /dev/null +++ b/llvm/test/tools/llvm-mir-reduce/instr-reduce.py @@ -0,0 +1,16 @@ +from subprocess import run, PIPE +import re +import sys + +llc = run( [ 'llc', '-disable-symbolication','-verify-machineinstrs', '-mtriple=riscv32', '-run-pass=none', '-o', '-', sys.argv[1]], stdout=PIPE, stderr=PIPE ) + +stdout = llc.stdout.decode() + +p = re.compile(r'^\s*%[0-9]+:gpr = ADDI %[0-9]+, 5$', flags=re.MULTILINE) + +if (llc.returncode == 0 and p.search(stdout)): + print('This is interesting!') + sys.exit(0) +else: + print('This is NOT interesting!') + sys.exit(1) diff --git a/llvm/tools/llvm-mir-reduce/CMakeLists.txt b/llvm/tools/llvm-mir-reduce/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/CMakeLists.txt @@ -0,0 +1,24 @@ +set(LLVM_LINK_COMPONENTS + AllTargetsAsmParsers + AllTargetsCodeGens + AllTargetsDescs + AllTargetsInfos + Core + IRReader + MIRParser + Support + Target + TransformUtils + ) + +add_llvm_tool(llvm-mir-reduce + DeltaManager.cpp + TestRunner.cpp + deltas/Delta.cpp + deltas/ReduceInstructions.cpp + llvm-mir-reduce.cpp + MyMachineModule.cpp + + DEPENDS + intrinsics_gen + ) diff --git a/llvm/tools/llvm-mir-reduce/DeltaManager.h b/llvm/tools/llvm-mir-reduce/DeltaManager.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAMANAGER_H +#define LLVM_TOOLS_LLVM_REDUCE_DELTAMANAGER_H + +namespace llvm { +class raw_ostream; +class TestRunner; + +void printDeltaPasses(raw_ostream &OS); +void runDeltaPasses(TestRunner &Tester); +} // namespace llvm + +#endif diff --git a/llvm/tools/llvm-mir-reduce/DeltaManager.cpp b/llvm/tools/llvm-mir-reduce/DeltaManager.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/DeltaManager.cpp @@ -0,0 +1,65 @@ +//===- DeltaManager.cpp - 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 "DeltaManager.h" +#include "TestRunner.h" +#include "deltas/Delta.h" +#include "deltas/ReduceInstructions.h" +#include "llvm/Support/CommandLine.h" + +using namespace llvm; + +static cl::opt + DeltaPasses("delta-passes", + cl::desc("Delta passes to run, separated by commas. By " + "default, run all delta passes.")); + +#define DELTA_PASSES DELTA_PASS("instructions", reduceInstructionsDeltaPass) + +static void runAllDeltaPasses(TestRunner &Tester) { +#define DELTA_PASS(NAME, FUNC) FUNC(Tester); + DELTA_PASSES +#undef DELTA_PASS +} + +static void runDeltaPassName(TestRunner &Tester, StringRef PassName) { +#define DELTA_PASS(NAME, FUNC) \ + if (PassName == NAME) { \ + FUNC(Tester); \ + return; \ + } + DELTA_PASSES +#undef DELTA_PASS + errs() << "unknown pass \"" << PassName << "\""; + exit(1); +} + +void llvm::printDeltaPasses(raw_ostream &OS) { + OS << "Delta passes (pass to `--delta-passes=` as a comma separated list):\n"; +#define DELTA_PASS(NAME, FUNC) OS << " " << NAME << "\n"; + DELTA_PASSES +#undef DELTA_PASS +} + +void llvm::runDeltaPasses(TestRunner &Tester) { + if (DeltaPasses.empty()) { + runAllDeltaPasses(Tester); + } else { + StringRef Passes = DeltaPasses; + while (!Passes.empty()) { + auto Split = Passes.split(","); + runDeltaPassName(Tester, Split.first); + Passes = Split.second; + } + } +} diff --git a/llvm/tools/llvm-mir-reduce/MyMachineModule.h b/llvm/tools/llvm-mir-reduce/MyMachineModule.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/MyMachineModule.h @@ -0,0 +1,38 @@ +//===- MyMachineModule.h - Wrapper for Module and MachineFunction ---------===// +// +// 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_LLVM_REDUCE_MYMACHINEMODULE_H +#define LLVM_TOOLS_LLVM_REDUCE_MYMACHINEMODULE_H + +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/IR/Module.h" + +using namespace llvm; + +class MyMachineModule { +public: + std::shared_ptr M; + MachineFunction *MF; // MF is owned by MMI. + void print(raw_ostream &ROS, void *p); +}; + +std::unique_ptr parseMyMachineModule(StringRef Filename, + LLVMContext &Ctxt, + MachineModuleInfo &MMI); + +std::unique_ptr +cloneMyMachineModule(const MyMachineModule &MMM); + +bool verifyMyMachineModule(const MyMachineModule &MMM, raw_fd_ostream *OS); + +void writeMyMachineModule(const MyMachineModule *MMM, StringRef FileName); + +bool runMyMachineModule(const std::unique_ptr &MMM); + +#endif diff --git a/llvm/tools/llvm-mir-reduce/MyMachineModule.cpp b/llvm/tools/llvm-mir-reduce/MyMachineModule.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/MyMachineModule.cpp @@ -0,0 +1,155 @@ +//===- MyMachineModule.cpp - Wrapper for Module and MachineFunction -------===// +// +// 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 "MyMachineModule.h" +#include "llvm/CodeGen/MIRParser/MIRParser.h" +#include "llvm/CodeGen/MIRPrinter.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/IRReader/IRReader.h" +#include "llvm/Target/TargetMachine.h" + +static MachineFunction *cloneMF(MachineFunction *SrcMF) { + auto *DstMF = new MachineFunction( + SrcMF->getFunction(), SrcMF->getTarget(), SrcMF->getSubtarget(), + SrcMF->getFunctionNumber(), SrcMF->getMMI()); + DenseMap Src2DstMBB; + DenseMap Src2DstReg; + + auto *SrcMRI = &SrcMF->getRegInfo(); + auto *DstMRI = &DstMF->getRegInfo(); + + // Create vregs. + for (auto &SrcMBB : *SrcMF) { + for (auto &SrcMI : SrcMBB) { + for (unsigned I = 0, E = SrcMI.getNumOperands(); I < E; ++I) { + auto &DMO = SrcMI.getOperand(I); + if (!DMO.isReg() || !DMO.isDef()) + continue; + Register SrcReg = DMO.getReg(); + if (Register::isPhysicalRegister(SrcReg)) + continue; + auto SrcRC = SrcMRI->getRegClass(SrcReg); + auto DstReg = DstMRI->createVirtualRegister(SrcRC); + Src2DstReg[SrcReg] = DstReg; + } + } + } + + // Clone blocks. + for (auto &SrcMBB : *SrcMF) + Src2DstMBB[&SrcMBB] = DstMF->CreateMachineBasicBlock(); + // Link blocks. + for (auto &SrcMBB : *SrcMF) { + auto *DstMBB = Src2DstMBB[&SrcMBB]; + DstMF->push_back(DstMBB); + for (auto It = SrcMBB.succ_begin(), IterEnd = SrcMBB.succ_end(); + It != IterEnd; ++It) { + auto *SrcSuccMBB = *It; + auto *DstSuccMBB = Src2DstMBB[SrcSuccMBB]; + DstMBB->addSuccessor(DstSuccMBB); + } + for (auto &LI : SrcMBB.liveins()) + DstMBB->addLiveIn(LI); + } + // Clone instructions. + for (auto &SrcMBB : *SrcMF) { + auto *DstMBB = Src2DstMBB[&SrcMBB]; + for (auto &SrcMI : SrcMBB) { + const auto &MCID = + DstMF->getSubtarget().getInstrInfo()->get(SrcMI.getOpcode()); + auto *DstMI = DstMF->CreateMachineInstr(MCID, SrcMI.getDebugLoc(), + /*NoImplicit=*/true); + DstMBB->push_back(DstMI); + for (auto &SrcMO : SrcMI.operands()) { + MachineOperand DstMO(SrcMO); + DstMO.clearParent(); + // Update vreg. + if (DstMO.isReg() && Src2DstReg.count(DstMO.getReg())) { + DstMO.setReg(Src2DstReg[DstMO.getReg()]); + } + // Update MBB. + if (DstMO.isMBB()) { + DstMO.setMBB(Src2DstMBB[DstMO.getMBB()]); + } + DstMI->addOperand(DstMO); + } + DstMI->setMemRefs(*DstMF, SrcMI.memoperands()); + } + } + + DstMF->verify(nullptr, "", /*AbortOnErrors=*/true); + return DstMF; +} + +std::unique_ptr parseMyMachineModule(StringRef Filename, + LLVMContext &Ctxt, + MachineModuleInfo &MMI) { + auto FileOrErr = MemoryBuffer::getFileOrSTDIN(Filename, /*IsText=*/true); + std::unique_ptr MParser = + createMIRParser(std::move(FileOrErr.get()), Ctxt); + + auto SetDataLayout = + [&](StringRef DataLayoutTargetTriple) -> Optional { + return MMI.getTarget().createDataLayout().getStringRepresentation(); + }; + + std::unique_ptr M = MParser->parseIRModule(SetDataLayout); + MParser->parseMachineFunctions(*M, MMI); + MachineFunction *MF = nullptr; + for (auto &F : *M) { + if (auto *MF4F = MMI.getMachineFunction(F)) { + // XXX: Maybe it would not be a lot of effort to handle multiple MFs by + // simply storing them in a MyMachineModule::SmallVector or similar. The + // single MF use-case seems a lot more common though so that will do for + // now. + assert(!MF && "Only single MF supported!"); + MF = MF4F; + } + } + assert(MF && "No MF found!"); + + auto MMM = std::make_unique(); + MMM->M = std::move(M); + MMM->MF = MF; + return MMM; +} + +std::unique_ptr +cloneMyMachineModule(const MyMachineModule &MMM) { + auto CloneMMM = std::make_unique(); + // Note that we cannot clone the Module as then we would need a way to + // updated the cloned MachineFunction's IR references. + CloneMMM->M = MMM.M; + CloneMMM->MF = cloneMF(MMM.MF); + return CloneMMM; +} + +bool verifyMyMachineModule(const MyMachineModule &MMM, raw_fd_ostream *OS) { + return !MMM.MF->verify(nullptr, "", /*AbortOnErrors=*/false); +} + +void writeMyMachineModule(const MyMachineModule *MMM, StringRef FileName) { + std::error_code EC; + raw_fd_ostream OS(FileName, EC); + if (EC) { + errs() << "Error opening output file: " << EC.message() << "!\n"; + exit(1); + } + printMIR(OS, *MMM->M.get()); + printMIR(OS, *MMM->MF); + OS.close(); +} + +void MyMachineModule::print(raw_ostream &ROS, void *p) { + printMIR(ROS, *M.get()); + printMIR(ROS, *MF); +} diff --git a/llvm/tools/llvm-mir-reduce/TestRunner.h b/llvm/tools/llvm-mir-reduce/TestRunner.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/TestRunner.h @@ -0,0 +1,47 @@ +//===-- 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_LLVM_REDUCE_TESTRUNNER_H +#define LLVM_TOOLS_LLVM_REDUCE_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 "MyMachineModule.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, const std::vector &TestArgs); + + /// Runs the interesting-ness test for the specified file + /// @returns 0 if test was successful, 1 if otherwise + int run(StringRef Filename); + + /// Returns the most reduced version of the original testcase + MyMachineModule *getProgram() const { return Program.get(); } + + void setProgram(std::unique_ptr P) { Program = std::move(P); } + +private: + StringRef TestName; + const std::vector &TestArgs; + std::unique_ptr Program; +}; + +} // namespace llvm + +#endif diff --git a/llvm/tools/llvm-mir-reduce/TestRunner.cpp b/llvm/tools/llvm-mir-reduce/TestRunner.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/TestRunner.cpp @@ -0,0 +1,42 @@ +//===-- 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, const std::vector &TestArgs) + : TestName(TestName), TestArgs(TestArgs) { +} + +/// 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); + + for (const auto &Arg : TestArgs) + ProgramArgs.push_back(Arg); + + ProgramArgs.push_back(Filename); + + std::string ErrMsg; + int Result = sys::ExecuteAndWait( + TestName, ProgramArgs, /*Env=*/None, /*Redirects=*/None, + /*SecondsToWait=*/0, /*MemoryLimit=*/0, &ErrMsg); + + if (Result < 0) { + Error E = make_error("Error running interesting-ness test: " + + ErrMsg, + inconvertibleErrorCode()); + errs() << toString(std::move(E)); + exit(1); + } + + return !Result; +} diff --git a/llvm/tools/llvm-mir-reduce/deltas/Delta.h b/llvm/tools/llvm-mir-reduce/deltas/Delta.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/deltas/Delta.h @@ -0,0 +1,109 @@ +//===- 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_LLVM_REDUCE_DELTAS_DELTA_H +#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_DELTA_H + +#include "TestRunner.h" +#include "llvm/ADT/ScopeExit.h" +#include +#include +#include + +namespace llvm { + +struct Chunk { + int Begin; + int End; + + /// Helper function to verify if a given Target-index is inside the Chunk + bool contains(int Index) const { return Index >= Begin && Index <= End; } + + void print() const { + errs() << "[" << Begin; + if (End - Begin != 0) + errs() << "," << End; + errs() << "]"; + } + + /// Operator when populating CurrentChunks in Generic Delta Pass + friend bool operator!=(const Chunk &C1, const Chunk &C2) { + return C1.Begin != C2.Begin || C1.End != C2.End; + } + + /// Operator used for sets + friend bool operator<(const Chunk &C1, const Chunk &C2) { + return std::tie(C1.Begin, C1.End) < std::tie(C2.Begin, C2.End); + } +}; + +/// Provides opaque interface for querying into ChunksToKeep without having to +/// actually understand what is going on. +class Oracle { + /// Out of all the features that we promised to be, + /// how many have we already processed? 1-based! + int Index = 1; + + /// The actual workhorse, contains the knowledge whether or not + /// some particular feature should be preserved this time. + ArrayRef ChunksToKeep; + +public: + explicit Oracle(ArrayRef ChunksToKeep) : ChunksToKeep(ChunksToKeep) {} + + /// Should be called for each feature on which we are operating. + /// Name is self-explanatory - if returns true, then it should be preserved. + bool shouldKeep() { + if (ChunksToKeep.empty()) + return false; // All further features are to be discarded. + + // Does the current (front) chunk contain such a feature? + bool ShouldKeep = ChunksToKeep.front().contains(Index); + auto _ = make_scope_exit([&]() { ++Index; }); // Next time - next feature. + + // Is this the last feature in the chunk? + if (ChunksToKeep.front().End == Index) + ChunksToKeep = ChunksToKeep.drop_front(); // Onto next chunk. + + return ShouldKeep; + } +}; + +/// 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 &, MyMachineModule *)> + ExtractChunksFromModule); +} // namespace llvm + +#endif diff --git a/llvm/tools/llvm-mir-reduce/deltas/Delta.cpp b/llvm/tools/llvm-mir-reduce/deltas/Delta.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/deltas/Delta.cpp @@ -0,0 +1,190 @@ +//===- 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 "MyMachineModule.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/IR/Verifier.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/ToolOutputFile.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include +#include + +using namespace llvm; + +static cl::opt AbortOnInvalidReduction( + "abort-on-invalid-reduction", + cl::desc("Abort if any reduction results in invalid IR")); + +void writeOutput(MyMachineModule *M, llvm::StringRef Message); + +bool isReduced(MyMachineModule &M, TestRunner &Test, SmallString<128> &CurrentFilepath) { + // Write MyMachineModule to tmp file + int FD; + std::error_code EC = + sys::fs::createTemporaryFile("llvm-mir-reduce", "mir", FD, CurrentFilepath); + if (EC) { + errs() << "Error making unique filename: " << EC.message() << "!\n"; + exit(1); + } + + ToolOutputFile Out(CurrentFilepath, FD); + M.print(Out.os(), /*AnnotationWriter=*/nullptr); + Out.os().close(); + if (Out.os().has_error()) { + errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n"; + exit(1); + } + + // Current Chunks aren't interesting + return Test.run(CurrentFilepath); +} + +/// Counts the amount of lines for a given file +static int getLines(StringRef Filepath) { + int Lines = 0; + std::string CurrLine; + std::ifstream FileStream{std::string(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) { + errs() << "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; + errs() << "Success! New Chunks:\n"; + for (auto C : Chunks) { + errs() << '\t'; + C.print(); + errs() << '\n'; + } + } + 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, int Targets, + std::function &, MyMachineModule *)> + ExtractChunksFromModule) { + assert(Targets >= 0); + if (!Targets) { + errs() << "\nNothing to reduce\n"; + return; + } + + if (MyMachineModule *Program = Test.getProgram()) { + SmallString<128> CurrentFilepath; + if (!isReduced(*Program, Test, CurrentFilepath)) { + errs() << "\nInput isn't interesting! Verify interesting-ness test\n"; + exit(1); + } + + assert(!verifyMyMachineModule(*Program, &errs()) && + "input module is broken before making changes"); + } + + std::vector ChunksStillConsideredInteresting = {{1, Targets}}; + std::unique_ptr ReducedProgram; + + bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity; + do { + FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false; + + std::set UninterestingChunks; + for (Chunk &ChunkToCheckForUninterestingness : + reverse(ChunksStillConsideredInteresting)) { + // Take all of ChunksStillConsideredInteresting chunks, except those we've + // already deemed uninteresting (UninterestingChunks) but didn't remove + // from ChunksStillConsideredInteresting yet, and additionally ignore + // ChunkToCheckForUninterestingness chunk. + std::vector CurrentChunks; + CurrentChunks.reserve(ChunksStillConsideredInteresting.size() - + UninterestingChunks.size() - 1); + copy_if(ChunksStillConsideredInteresting, + std::back_inserter(CurrentChunks), [&](const Chunk &C) { + return !UninterestingChunks.count(C) && + C != ChunkToCheckForUninterestingness; + }); + + // Clone module before hacking it up.. + std::unique_ptr Clone = cloneMyMachineModule(*Test.getProgram()); + // Generate Module with only Targets inside Current Chunks + ExtractChunksFromModule(CurrentChunks, Clone.get()); + + // Some reductions may result in invalid IR. Skip such reductions. + if (verifyMyMachineModule(*Clone.get(), &errs())) { + if (AbortOnInvalidReduction) { + errs() << "Invalid reduction\n"; + exit(1); + } + errs() << " **** WARNING | reduction resulted in invalid module, " + "skipping\n"; + continue; + } + + errs() << "Ignoring: "; + ChunkToCheckForUninterestingness.print(); + for (const Chunk &C : UninterestingChunks) + C.print(); + + SmallString<128> CurrentFilepath; + if (!isReduced(*Clone, Test, CurrentFilepath)) { + // Program became non-reduced, so this chunk appears to be interesting. + errs() << "\n"; + continue; + } + + FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true; + UninterestingChunks.insert(ChunkToCheckForUninterestingness); + ReducedProgram = std::move(Clone); + errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n"; + writeOutput(ReducedProgram.get(), "Saved new best reduction to "); + } + // Delete uninteresting chunks + erase_if(ChunksStillConsideredInteresting, + [&UninterestingChunks](const Chunk &C) { + return UninterestingChunks.count(C); + }); + } while (!ChunksStillConsideredInteresting.empty() && + (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity || + increaseGranularity(ChunksStillConsideredInteresting))); + + // If we reduced the testcase replace it + if (ReducedProgram) + Test.setProgram(std::move(ReducedProgram)); + errs() << "Couldn't increase anymore.\n"; +} diff --git a/llvm/tools/llvm-mir-reduce/deltas/ReduceInstructions.h b/llvm/tools/llvm-mir-reduce/deltas/ReduceInstructions.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/deltas/ReduceInstructions.h @@ -0,0 +1,23 @@ +//===- ReduceArguments.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 uninteresting Arguments from defined functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEINSTRUCTIONS_H +#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEINSTRUCTIONS_H + +#include "Delta.h" + +namespace llvm { +void reduceInstructionsDeltaPass(TestRunner &Test); +} // namespace llvm + +#endif diff --git a/llvm/tools/llvm-mir-reduce/deltas/ReduceInstructions.cpp b/llvm/tools/llvm-mir-reduce/deltas/ReduceInstructions.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/deltas/ReduceInstructions.cpp @@ -0,0 +1,150 @@ +//===- ReduceArguments.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 uninteresting Arguments from defined functions. +// +//===----------------------------------------------------------------------===// + +#include "ReduceInstructions.h" + +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +static Register getPrevDefOfRCInMBB(MachineBasicBlock &MBB, + MachineBasicBlock::reverse_iterator &RI, + const TargetRegisterClass *RC, + SetVector &ExcludeMIs) { + auto MRI = &MBB.getParent()->getRegInfo(); + for (MachineBasicBlock::reverse_instr_iterator E = MBB.instr_rend(); RI != E; + ++RI) { + auto &MI = *RI; + // All Def operands explicit and implicit. + for (auto &MO : MI.operands()) { + if (!MO.isReg() || !MO.isDef()) + continue; + auto Reg = MO.getReg(); + if (Register::isPhysicalRegister(Reg)) + continue; + + if (MRI->getRegClass(Reg) == RC && !ExcludeMIs.count(MO.getParent())) + return Reg; + } + } + return 0; +} + +static unsigned countInstructions(MyMachineModule *Program) { + unsigned Count = 0; + MachineInstr *TopMI = nullptr; + for (auto &MBB : *Program->MF) { + for (auto &MI : MBB) { + if (MI.isTerminator()) + continue; + if (MBB.isEntryBlock() && !TopMI) { + TopMI = &MI; + continue; + } + Count++; + } + } + return Count; +} + +static void extractInstrFromModule(std::vector ChunksToKeep, + MyMachineModule *Program) { + auto &MF = *Program->MF; + MachineDominatorTree MDT; + MDT.runOnMachineFunction(MF); + + Oracle O(ChunksToKeep); + + auto MRI = &MF.getRegInfo(); + SetVector ToDelete; + + MachineInstr *TopMI = nullptr; + + // Mark MIs for deletion according to some criteria. + for (auto &MBB : MF) { + for (auto &MI : MBB) { + if (MI.isTerminator()) + continue; + if (MBB.isEntryBlock() && !TopMI) { + TopMI = &MI; + continue; + } + if (!O.shouldKeep()) { + ToDelete.insert(&MI); + // errs() << "Deleting: " << MI; + } + } + } + + // For each MI to be deleted update users of regs defined by that MI to use + // some other dominating definition (that is not to be deleted). + for (auto *MI : ToDelete) { + for (auto &MO : MI->operands()) { + if (!MO.isReg() || !MO.isDef()) + continue; + auto Reg = MO.getReg(); + if (Register::isPhysicalRegister(Reg)) + continue; + auto UI = MRI->use_begin(Reg); + auto UE = MRI->use_end(); + + auto RegRC = MRI->getRegClass(Reg); + Register NewReg = 0; + // If this is not a physical register and there are some uses. + if (UI != UE) { + MachineBasicBlock::reverse_iterator RI(*MI); + MachineBasicBlock *BB = MI->getParent(); + ++RI; + while (NewReg == 0 && BB) { + NewReg = getPrevDefOfRCInMBB(*BB, RI, RegRC, ToDelete); + // Prepare for idom(BB). + if (auto *IDM = MDT.getNode(BB)->getIDom()) { + BB = IDM->getBlock(); + RI = BB->rbegin(); + } else { + BB = nullptr; + } + } + } + + // If no dominating definition was found then add an implicit one to the + // first instruction in the entry block. + if (!NewReg && TopMI) { + NewReg = MRI->createVirtualRegister(RegRC); + TopMI->addOperand(MachineOperand::CreateReg( + NewReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/)); + } + + // Update all uses. + while (UI != UE) { + auto &UMO = *UI++; + UMO.setReg(NewReg); + } + } + } + + // Finally delete the MIs. + for (auto *MI : ToDelete) + MI->eraseFromParent(); +} + +void llvm::reduceInstructionsDeltaPass(TestRunner &Test) { + outs() << "*** Reducing Instructions...\n"; + unsigned InstCount = countInstructions(Test.getProgram()); + runDeltaPass(Test, InstCount, extractInstrFromModule); +} diff --git a/llvm/tools/llvm-mir-reduce/llvm-mir-reduce.cpp b/llvm/tools/llvm-mir-reduce/llvm-mir-reduce.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-mir-reduce/llvm-mir-reduce.cpp @@ -0,0 +1,177 @@ +//===- 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 "MyMachineModule.h" +#include "TestRunner.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/CodeGen/CommandFlags.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/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetMachine.h" +#include +#include + +using namespace llvm; + +static cl::OptionCategory Options("llvm-reduce options"); + +static cl::opt Help("h", cl::desc("Alias for -help"), cl::Hidden, + cl::cat(Options)); +static cl::opt Version("v", cl::desc("Alias for -version"), cl::Hidden, + cl::cat(Options)); + +static cl::opt + PrintDeltaPasses("print-delta-passes", + cl::desc("Print list of delta passes, passable to " + "--delta-passes as a comma separated list")); + +static cl::opt InputFilename(cl::Positional, cl::Required, + cl::desc(""), + cl::cat(Options)); + +static cl::opt + TestFilename("test", cl::Required, + cl::desc("Name of the interesting-ness test to be run"), + cl::cat(Options)); + +static cl::list + TestArguments("test-arg", cl::ZeroOrMore, + cl::desc("Arguments passed onto the interesting-ness test"), + cl::cat(Options)); + +static cl::opt + OutputFilename("output", + cl::desc("Specify the output file. default: reduced.mir")); +static cl::alias OutputFileAlias("o", cl::desc("Alias for -output"), + cl::aliasopt(OutputFilename), + cl::cat(Options)); + +static cl::opt + ReplaceInput("in-place", + cl::desc("WARNING: This option will replace your input file " + "with the reduced version!"), + cl::cat(Options)); + +static cl::opt TargetTriple("mtriple", cl::Required, + cl::desc("Set the target triple")); + +static codegen::RegisterCodeGenFlags CGF; + +#if 0 +// 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; +} +#endif + +void writeOutput(MyMachineModule *M, StringRef Message) { + if (ReplaceInput) // In-place + OutputFilename = InputFilename.c_str(); + else if (OutputFilename.empty() || OutputFilename == "-") + OutputFilename = "reduced.mir"; +#if 0 + std::error_code EC; + raw_fd_ostream Out(OutputFilename, EC); + if (EC) { + errs() << "Error opening output file: " << EC.message() << "!\n"; + exit(1); + } + M->print(Out, /*AnnotationWriter=*/nullptr); +#else + writeMyMachineModule(M, OutputFilename); +#endif + errs() << Message << OutputFilename << "\n"; +} + +static std::unique_ptr createTargetMachine() { + InitializeAllTargets(); + InitializeAllTargetMCs(); + InitializeAllAsmPrinters(); + InitializeAllAsmParsers(); + + auto TT(Triple::normalize(TargetTriple)); + std::string CPU(codegen::getCPUStr()); + std::string FS(codegen::getFeaturesStr()); + + std::string Error; + const Target *TheTarget = TargetRegistry::lookupTarget(TT, Error); + + return std::unique_ptr( + static_cast(TheTarget->createTargetMachine( + TT, CPU, FS, TargetOptions(), None, None, CodeGenOpt::Default))); +} + +int main(int Argc, char **Argv) { + InitLLVM X(Argc, Argv); + + cl::HideUnrelatedOptions({&Options, &getColorCategory()}); + cl::ParseCommandLineOptions(Argc, Argv, "LLVM automatic testcase reducer.\n"); + + if (PrintDeltaPasses) { + printDeltaPasses(errs()); + return 0; + } + + LLVMContext Context; + std::unique_ptr TM = createTargetMachine(); + MachineModuleInfo MMI(TM.get()); + std::unique_ptr OriginalProgram = + parseMyMachineModule(InputFilename, Context, MMI); + + if (!OriginalProgram) { + return 1; + } + + // Initialize test environment + TestRunner Tester(TestFilename, TestArguments); + Tester.setProgram(std::move(OriginalProgram)); + + // Try to reduce code + runDeltaPasses(Tester); + + if (!Tester.getProgram()) { + errs() << "\nCouldnt reduce input :/\n"; + } else { + // Print reduced file to STDOUT + if (OutputFilename == "-") + Tester.getProgram()->print(outs(), nullptr); + else + writeOutput(Tester.getProgram(), "\nDone reducing! Reduced testcase: "); + } + + return 0; +}