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/ReductionTree.h b/mlir/include/mlir/Reducer/ReductionTree.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/ReductionTree.h @@ -0,0 +1,55 @@ +//===- ReductionTree.h - Reduction Tree 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 class. It provides a framework to +// track and perform reductions within a specific reduction pass in the MLIR +// Reduce tool. It allows for custom implementation of the variant generation +// behavior with the purpose of integrating this framework regardless of the +// transformation being performed in the different reduction passes. It also +// implements methods that define the traversal of the reduction tree. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_TOOLS_MLIRREDUCE_REDUCTION_TREE_H +#define MLIR_TOOLS_MLIRREDUCE_REDUCTION_TREE_H + +#include + +#include "ReductionNode.h" +#include "mlir/Reducer/Tester.h" + +namespace mlir { + +/// This class defines the Reduction Tree structure. It provides a framework to +/// keep track of the reduction in a particular reduction pass. The root +/// specifies the original module in the reduction pass and childs are created +/// by generating variants using their parent module as a starting point. +class ReductionTree { +public: + ReductionTree(ReductionNode *root, Tester &test); + + ~ReductionTree(); + + /// Traverse the most reduced path in the reduction tree by generating the + /// variants at each level using the generateVariants parameter function. It + /// stops when no new successful variants can be created at the current level. + void singlePathTraversal( + llvm::function_ref + generateVariants); + +private: + ReductionNode *root; + Tester *test; + + /// Recursively delete the reduction nodes in the reduction tree + void destructTree(ReductionNode *node); +}; + +} // end namespace mlir + +#endif 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 @@ -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/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,12 @@ ) add_llvm_tool(mlir-reduce + ReductionNode.cpp + ReductionTree.cpp mlir-reduce.cpp ) 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) 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/ReductionTree.cpp b/mlir/tools/mlir-reduce/ReductionTree.cpp new file mode 100644 --- /dev/null +++ b/mlir/tools/mlir-reduce/ReductionTree.cpp @@ -0,0 +1,56 @@ +//===- ReductionTree.h - Reduction Tree 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 class. It provides a framework to +// track and perform reductions within a specific reduction pass in the MLIR +// Reduce tool. It allows for custom implementation of the variant generation +// behavior with the purpose of integrating this framework regardless of the +// transformation being performed in the different reduction passes. It also +// implements methods that define the traversal of the reduction tree. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Reducer/ReductionTree.h" + +using namespace mlir; + +ReductionTree::ReductionTree(ReductionNode *root, Tester &test) + : root(root), test(&test) {} + +ReductionTree::~ReductionTree() { destructTree(root); } + +/// Recursively delete the reduction nodes in the reduction tree. +void ReductionTree::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 generateVariants parameter function. It +/// stops when no new successful variants can be created at the current level. +void ReductionTree::singlePathTraversal( + llvm::function_ref + generateVariants) { + + ReductionNode *currLevel = root; + + while (true) { + generateVariants(currLevel, *test); + + if (currLevel->variantsEmpty() || + !currLevel->getVariants()[0]->isInteresting()) + break; + + // Update the mostReduced module in the tester object + test->setMostReduced(currLevel->getVariants()[0]->getModule()); + currLevel = currLevel->getVariants()[0]; + } +} 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 @@ -94,4 +94,4 @@ output->keep(); return 0; -} \ No newline at end of file +}