diff --git a/mlir/include/mlir/Reducer/CMakeLists.txt b/mlir/include/mlir/Reducer/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/CMakeLists.txt @@ -0,0 +1,7 @@ +add_mlir_library(MLIRReduce + Tester.cpp + DEPENDS + MLIRIR + ) + + mlir_check_all_link_libraries(MLIRReduce) \ No newline at end of file diff --git a/mlir/include/mlir/Reducer/PassDetail.h b/mlir/include/mlir/Reducer/PassDetail.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/PassDetail.h @@ -0,0 +1,21 @@ +//===- PassDetail.h - Transforms Pass class details -------------*- 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 TRANSFORMS_PASSDETAIL_H_ +#define TRANSFORMS_PASSDETAIL_H_ + +#include "mlir/Pass/Pass.h" + +namespace mlir { + +#define GEN_PASS_CLASSES +#include "Passes.h.inc" + +} // end namespace mlir + +#endif // TRANSFORMS_PASSDETAIL_H_ diff --git a/mlir/include/mlir/Reducer/Passes/OpReducer.h b/mlir/include/mlir/Reducer/Passes/OpReducer.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/Passes/OpReducer.h @@ -0,0 +1,39 @@ +//===- OpReducer.h - MLIR Reduce Operation Reducer Variant Generator -----===// +// +// 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 defines the OpReducer class. It defines a variant generator class +// to be used in a Reduction Tree Pass instantiation with the aim of reducing +// the number of operations in an MLIR Module. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_TOOLS_MLIRREDUCE_OP_REDUCER_H +#define MLIR_TOOLS_MLIRREDUCE_OP_REDUCER_H + +#include "mlir/Reducer/ReductionNode.h" +#include "mlir/Reducer/Tester.h" + +namespace mlir { + +/// The OpReducer class defines the variant generation of a Reducer Tree Pass +/// with the aim of reducing the number of operations in a module. It should be +/// specified as the first parameter in a Reduction Tree Pass. +class OpReducer { +public: + /// Iterate over the body of a module and return the number of operations. + static int countOps(ModuleOp module); + + /// Generate variants by removing operations from the module in the parent + /// Reduction Node and link the variants as childs in the Reduction Tree Pass. + static void variantGenerator(ReductionNode *parent, Tester test, + bool &doneTraversing); +}; + +} // end namespace mlir + +#endif diff --git a/mlir/include/mlir/Reducer/ReductionNode.h b/mlir/include/mlir/Reducer/ReductionNode.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/ReductionNode.h @@ -0,0 +1,70 @@ +//===- ReductionNode.h - Reduction Node 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 defines the reduction nodes which are used to track of the +// metadata for a specific generated variant within a reduction pass and are the +// building blocks of the reduction tree structure. A reduction tree is used to +// keep track of the different generated variants throughout a reduction pass in +// the MLIR Reduce tool. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_TOOLS_MLIRREDUCE_REDUCTIONNODE_H +#define MLIR_TOOLS_MLIRREDUCE_REDUCTIONNODE_H + +#include "sys/stat.h" +#include + +#include "mlir/Reducer/Tester.h" +#include "llvm/Support/ToolOutputFile.h" + +namespace mlir { + +/// This class defines the ReductionNode which is used to wrap the module of +/// a generated variant and keep track of the necessary metadata for the +/// reduction pass. The nodes are linked together in a reduction tree stucture +/// which defines the relationship between all the different generated variants. +class ReductionNode { +public: + ReductionNode(ModuleOp module, ReductionNode *parent, Tester &test); + + /// Calculates and initializes the size and interesting values of the node. + void measureAndTest(Tester &test); + + /// Returns the module. + ModuleOp getModule() const { return module; } + + /// Returns the size in bytes of the module. + int getSize(); + + /// Returns true if the module exhibits the interesting behavior. + bool isInteresting(); + + /// Returns the pointers to the child variants. + const std::vector &getVariants(); + + /// Returns true if the vector containing the child variants is empty. + bool variantsEmpty(); + +private: + ModuleOp module; + bool interesting; + int size; + ReductionNode *parent; + std::vector variants; + + /// Link a child variant node. + void linkVariant(ReductionNode *newVariant); + + /// Sort the vector containing the child variants by interestingness and size. + void sortVariants(); +}; + +} // end namespace mlir + +#endif diff --git a/mlir/include/mlir/Reducer/ReductionTreePass.h b/mlir/include/mlir/Reducer/ReductionTreePass.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/ReductionTreePass.h @@ -0,0 +1,142 @@ +//===- ReductionTreePass.h - Reduction Tree Pass 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 defines the Reduction Tree Pass class. It provides a framework for +// the implementation of different reduction passes in the MLIR Reduce tool. It +// allows for custom specification of the variant generation behavior. It +// implements methods that define the different possible traversals of the +// reduction tree. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_TOOLS_MLIRREDUCE_REDUCTION_TREE_PASS_H +#define MLIR_TOOLS_MLIRREDUCE_REDUCTION_TREE_PASS_H + +#include + +#include "PassDetail.h" +#include "ReductionNode.h" +#include "mlir/Reducer/Tester.h" + +/// Defines the traversal method options to be used in the reduction tree +/// traversal. +enum traversalMode { singlePath, multiPath, kConcurrent, kBacktrack }; + +namespace mlir { + +/// This class defines the Reduction Tree Pass. It provides a framework to +/// to implement a reduction pass using a tree structure to keep track of the +/// generated reduced variants. +template +class ReductionTreePass + : public ReductionTreeBase> { +public: + ReductionTreePass(Tester test) : test(test) { + Reducer reducer; + generateVariants = reducer.variantGenerator; + } + + ~ReductionTreePass() { destructTree(root); } + + /// Returns the name of the pass. + StringRef getName() const override { + return StringRef("Reduction Tree Pass"); + } + + /// Clones the pass. + std::unique_ptr clonePass() const override { + return std::make_unique>( + *static_cast(this)); + } + + /// Runs the pass instance in the pass pipeline. + void runOnOperation() override { + ModuleOp module = this->getOperation(); + this->root = new ReductionNode(module, nullptr, test); + ReductionNode *reduced; + + switch (mode) { + case singlePath: + reduced = singlePathTraversal(); + break; + default: + llvm::report_fatal_error("Traversal method not currently supported."); + break; + } + + updateGoldenModule(module, reduced->getModule()); + } + +private: + ReductionNode *root; + Tester test; + llvm::function_ref + generateVariants; + + /// Recursively delete the reduction nodes in the reduction tree. + void destructTree(ReductionNode *node) { + std::vector currVariants = node->getVariants(); + for (auto *variant : currVariants) + destructTree(variant); + + delete node; + } + + /// Traverse the most reduced path in the reduction tree by generating the + /// variants at each level using the Reducer parameter's generateVariants + /// function. Stops when no new successful variants can be created at the + /// current level. + ReductionNode *singlePathTraversal() { + ReductionNode *currLevel = root; + bool doneTraversing = false; + + while (true) { + generateVariants(currLevel, test, doneTraversing); + + if (currLevel->variantsEmpty() || + !currLevel->getVariants()[0]->isInteresting() || doneTraversing) + return currLevel; + + currLevel = currLevel->getVariants()[0]; + } + } + + /// Update the module passed by the pass manager with the reduced version + /// produced in this pass. + static void updateGoldenModule(ModuleOp &golden, ModuleOp reduced) { + std::vector opsToSwap; + + // Clear golden module body. + for (auto &op : golden) + opsToSwap.push_back(&op); + + int i = 0; + for (auto *op : opsToSwap) { + if (i != int(opsToSwap.size()) - 1) + op->erase(); + ++i; + } + + // Insert new operations into golden module. + opsToSwap.clear(); + for (auto &op : reduced) + opsToSwap.push_back(op.clone()); + + i = 0; + for (auto *op : opsToSwap) { + if (i != int(opsToSwap.size()) - 1) + golden.push_back(op); + ++i; + } + } +}; + +} // end namespace mlir + +#endif diff --git a/mlir/include/mlir/Reducer/Tester.h b/mlir/include/mlir/Reducer/Tester.h --- a/mlir/include/mlir/Reducer/Tester.h +++ b/mlir/include/mlir/Reducer/Tester.h @@ -9,8 +9,8 @@ // This file defines the Tester class used in the MLIR Reduce tool. // // A Tester object is passed as an argument to the reduction passes and it is -// used to keep track of the state of the reduction throughout the multiple -// passes. +// used to run the interestigness testing script on the different generated +// reduced variants of the test case. // //===----------------------------------------------------------------------===// @@ -27,9 +27,9 @@ namespace mlir { -/// This class is used to keep track of the state of the reduction. It contains -/// a method to run the interestingness testing script on MLIR test case files -/// and provides functionality to track the most reduced test case. +/// This class is used to keep track of the testing environment of the tool. It +/// contains a method to run the interestingness testing script on a MLIR test +/// case file. class Tester { public: Tester(StringRef testScript, ArrayRef testScriptArgs); @@ -39,21 +39,11 @@ /// otherwise. bool isInteresting(StringRef testCase); - /// Returns the most reduced MLIR test case module. - ModuleOp getMostReduced() const { return mostReduced; } - - /// Updates the most reduced MLIR test case module. If a - /// generated variant is found to be successful and shorter than the - /// mostReduced module, the mostReduced module must be updated with the new - /// variant. - void setMostReduced(ModuleOp t) { mostReduced = t; } - private: StringRef testScript; ArrayRef testScriptArgs; - ModuleOp mostReduced; }; } // end namespace mlir -#endif \ No newline at end of file +#endif diff --git a/mlir/lib/Reducer/Tester.cpp b/mlir/include/mlir/Reducer/Tester.cpp copy from mlir/lib/Reducer/Tester.cpp copy to mlir/include/mlir/Reducer/Tester.cpp --- a/mlir/lib/Reducer/Tester.cpp +++ b/mlir/include/mlir/Reducer/Tester.cpp @@ -9,8 +9,8 @@ // This file defines the Tester class used in the MLIR Reduce tool. // // A Tester object is passed as an argument to the reduction passes and it is -// used to keep track of the state of the reduction throughout the multiple -// passes. +// used to run the interestigness testing script on the different generated +// reduced variants of the test case. // //===----------------------------------------------------------------------===// @@ -32,6 +32,8 @@ for (const std::string &arg : testScriptArgs) testerArgs.push_back(arg); + testerArgs.push_back(testCase); + std::string errMsg; int result = llvm::sys::ExecuteAndWait( testScript, testerArgs, /*Env=*/None, /*Redirects=*/None, diff --git a/mlir/lib/Reducer/Tester.cpp b/mlir/lib/Reducer/Tester.cpp --- a/mlir/lib/Reducer/Tester.cpp +++ b/mlir/lib/Reducer/Tester.cpp @@ -9,8 +9,8 @@ // This file defines the Tester class used in the MLIR Reduce tool. // // A Tester object is passed as an argument to the reduction passes and it is -// used to keep track of the state of the reduction throughout the multiple -// passes. +// used to run the interestigness testing script on the different generated +// reduced variants of the test case. // //===----------------------------------------------------------------------===// @@ -32,6 +32,8 @@ for (const std::string &arg : testScriptArgs) testerArgs.push_back(arg); + testerArgs.push_back(testCase); + std::string errMsg; int result = llvm::sys::ExecuteAndWait( testScript, testerArgs, /*Env=*/None, /*Redirects=*/None, diff --git a/mlir/test/mlir-reduce/reduction-tree-pass.mlir b/mlir/test/mlir-reduce/reduction-tree-pass.mlir new file mode 100644 --- /dev/null +++ b/mlir/test/mlir-reduce/reduction-tree-pass.mlir @@ -0,0 +1,53 @@ +// UNSUPPORTED: -windows- +// RUN: mlir-reduce %s -test %S/test.sh | FileCheck %s +// CHECK-LABEL: func @simple5(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) { + +func @simple1(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) { + cond_br %arg0, ^bb1, ^bb2 +^bb1: + br ^bb3(%arg1 : memref<2xf32>) +^bb2: + %0 = alloc() : memref<2xf32> + br ^bb3(%0 : memref<2xf32>) +^bb3(%1: memref<2xf32>): + return +} + +func @simple2(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) { + cond_br %arg0, ^bb1, ^bb2 +^bb1: + br ^bb3(%arg1 : memref<2xf32>) +^bb2: + %0 = alloc() : memref<2xf32> + br ^bb3(%0 : memref<2xf32>) +^bb3(%1: memref<2xf32>): + return +} + +func @simple3(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) { + cond_br %arg0, ^bb1, ^bb2 +^bb1: + br ^bb3(%arg1 : memref<2xf32>) +^bb2: + %0 = alloc() : memref<2xf32> + br ^bb3(%0 : memref<2xf32>) +^bb3(%1: memref<2xf32>): + "test.crashOp"(%1, %arg2) : (memref<2xf32>, memref<2xf32>) -> () + return +} + +func @simple4(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) { + cond_br %arg0, ^bb1, ^bb2 +^bb1: + br ^bb3(%arg1 : memref<2xf32>) +^bb2: + %0 = alloc() : memref<2xf32> + br ^bb3(%0 : memref<2xf32>) +^bb3(%1: memref<2xf32>): + return +} + +func @simple5(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) { + "test.crashOp" () : () -> () + return +} diff --git a/mlir/tools/mlir-reduce/CMakeLists.txt b/mlir/tools/mlir-reduce/CMakeLists.txt --- a/mlir/tools/mlir-reduce/CMakeLists.txt +++ b/mlir/tools/mlir-reduce/CMakeLists.txt @@ -32,10 +32,21 @@ ) add_llvm_tool(mlir-reduce + Passes/OpReducer.cpp + ReductionNode.cpp mlir-reduce.cpp + + DEPENDS + MLIRReducerPassIncGen ) target_link_libraries(mlir-reduce PRIVATE ${LIBS}) llvm_update_compile_flags(mlir-reduce) -mlir_check_all_link_libraries(mlir-reduce) \ No newline at end of file +mlir_check_all_link_libraries(mlir-reduce) + +set(LLVM_TARGET_DEFINITIONS Passes.td) +mlir_tablegen(Passes.h.inc -gen-pass-decls) +add_public_tablegen_target(MLIRReducerPassIncGen) + +add_mlir_doc(Passes -gen-pass-doc ReducerPasses ./) \ No newline at end of file diff --git a/mlir/tools/mlir-reduce/Passes.td b/mlir/tools/mlir-reduce/Passes.td new file mode 100644 --- /dev/null +++ b/mlir/tools/mlir-reduce/Passes.td @@ -0,0 +1,23 @@ +//===-- Passes.td - MLIR Reduce pass definition file -----------*- tablegen -*-===// +// +// 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 definitions of the passes for the MLIR Reduce Tool. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_REDUCE_PASSES +#define MLIR_REDUCE_PASSES + +include "mlir/Pass/PassBase.td" + +def ReductionTree : Pass<"reduction-tree", "ModuleOp"> { + let summary = "A parameterizable reduction tree pass for the MLIR Reduce Tool"; + let constructor = "mlir::createReductionTreePass()"; +} + +#endif // MLIR_REDUCE_PASSES diff --git a/mlir/tools/mlir-reduce/Passes/OpReducer.cpp b/mlir/tools/mlir-reduce/Passes/OpReducer.cpp new file mode 100644 --- /dev/null +++ b/mlir/tools/mlir-reduce/Passes/OpReducer.cpp @@ -0,0 +1,61 @@ +//===- OpReducer.cpp - MLIR Reduce Operation Reducer Variant Generator ----===// +// +// 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 defines the OpReducer class. It defines a variant generator class +// to be used in a Reduction Tree Pass instantiation with the aim of reducing +// the number of operations in an MLIR Module. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Reducer/Passes/OpReducer.h" + +using namespace mlir; + +/// Return the number of operations in the module's body. +int OpReducer::countOps(ModuleOp module) { + int opCount = 0; + for (auto &O : module) + ++opCount; + + return opCount; +} + +/// Generate variants by removing operations from the module in the parent +/// and link the variants as childs in the Reduction Tree Pass. +void OpReducer::variantGenerator(ReductionNode *parent, Tester test, + bool &doneTraversing) { + + ModuleOp module = parent->getModule(); + int numVariants = 2; + int opCount = countOps(module); + int sectionSize = opCount / numVariants; + std::vector opsToRemove; + + if (opCount == 2) { + doneTraversing = true; + return; + } + + // Create two variants by bisecting the module. + for (int i = 0; i < numVariants; ++i) { + opsToRemove.clear(); + ModuleOp moduleVariant = module.clone(); + int x = 0; + for (auto &op : moduleVariant) { + if ((x >= sectionSize * i && x < sectionSize * (i + 1)) && + x != opCount - 1) + opsToRemove.push_back(&op); + x++; + } + + for (auto *o : opsToRemove) + o->erase(); + + new ReductionNode(moduleVariant, parent, test); + } +} diff --git a/mlir/tools/mlir-reduce/ReductionNode.cpp b/mlir/tools/mlir-reduce/ReductionNode.cpp new file mode 100644 --- /dev/null +++ b/mlir/tools/mlir-reduce/ReductionNode.cpp @@ -0,0 +1,106 @@ +//===- ReductionNode.cpp - Reduction Node 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 defines the reduction nodes which are used to track of the +// metadata for a specific generated variant within a reduction pass and are the +// building blocks of the reduction tree structure. A reduction tree is used to +// keep track of the different generated variants throughout a reduction pass in +// the MLIR Reduce tool. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Reducer/ReductionNode.h" + +using namespace mlir; + +/// Defines the sorting order of two ReductionNodes by interestingness and size. +static bool sortFunction(ReductionNode *a, ReductionNode *b) { + // Sort nodes by interestingness. + bool aInteresting = a->isInteresting(); + bool bInteresting = b->isInteresting(); + + if (aInteresting && !bInteresting) + return true; + + if (!aInteresting && bInteresting) + return false; + + // Sort nodes by size. + return (a->getSize() < b->getSize()); +} + +/// Returns the size in bytes of a file. +static int measureFile(SmallString<128> filepath) { + struct stat stats; + int rc = stat(filepath.c_str(), &stats); + if (rc != 0) + llvm::report_fatal_error("Error measuring the file size" + filepath); + + return stats.st_size; +} + +/// Sets up the metadata and links the node to its parent. +ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent, + Tester &test) + : module(module), parent(parent) { + + this->measureAndTest(test); + + // Link variant to parent node + if (parent != nullptr) + parent->linkVariant(this); +} + +/// Calculates and updates the size and interesting values of the module. +void ReductionNode::measureAndTest(Tester &test) { + + SmallString<128> filepath; + int fd; + + // Print module to temprary file. + std::error_code ec = + llvm::sys::fs::createTemporaryFile("mlir-reduce", "mlir", fd, filepath); + + if (ec) + llvm::report_fatal_error("Error making unique filename: " + ec.message()); + + llvm::ToolOutputFile out(filepath, fd); + module.print(out.os()); + out.os().close(); + + if (out.os().has_error()) + llvm::report_fatal_error("Error emitting bitcode to file '" + filepath); + + size = measureFile(filepath); + interesting = test.isInteresting(filepath); +} + +/// Returns the size in bytes of the module. +int ReductionNode::getSize() { return size; } + +/// Returns true if the module exhibits the interesting behavior. +bool ReductionNode::isInteresting() { return interesting; } + +/// Returns the pointers to the child variants. +const std::vector &ReductionNode::getVariants() { + return variants; +} + +/// Returns true if the child variants vector is empty. +bool ReductionNode::variantsEmpty() { return variants.empty(); } + +/// Link a child variant node. +void ReductionNode::linkVariant(ReductionNode *newVariant) { + variants.push_back(newVariant); + this->sortVariants(); +} + +/// Sort the vector containing the child variants by interestingness and size. +void ReductionNode::sortVariants() { + std::sort(variants.begin(), variants.end(), sortFunction); +} diff --git a/mlir/tools/mlir-reduce/mlir-reduce.cpp b/mlir/tools/mlir-reduce/mlir-reduce.cpp --- a/mlir/tools/mlir-reduce/mlir-reduce.cpp +++ b/mlir/tools/mlir-reduce/mlir-reduce.cpp @@ -19,6 +19,9 @@ #include "mlir/Parser.h" #include "mlir/Pass/Pass.h" #include "mlir/Pass/PassManager.h" +#include "mlir/Reducer/Passes/OpReducer.h" +#include "mlir/Reducer/ReductionNode.h" +#include "mlir/Reducer/ReductionTreePass.h" #include "mlir/Reducer/Tester.h" #include "mlir/Support/FileUtilities.h" #include "mlir/Support/LogicalResult.h" @@ -84,14 +87,24 @@ // Initialize test environment. Tester test(testFilename, testArguments); - test.setMostReduced(moduleRef.get()); if (!test.isInteresting(inputFilename)) llvm::report_fatal_error( "Input test case does not exhibit interesting behavior"); - test.getMostReduced().print(output->os()); + // Reduction pass pipeline. + PassManager pm(&context); + + // Reduction tree pass with OpReducer variant generation and single path + // traversal. + pm.addPass(std::make_unique>(test)); + + ModuleOp m = moduleRef.get().clone(); + if (failed(pm.run(m))) + llvm::report_fatal_error("Error running the reduction pass pipeline"); + + m.print(output->os()); output->keep(); return 0; -} \ No newline at end of file +}