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,73 @@ +//===- 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 child variant in the specified index. + ReductionNode *getVariant(unsigned long index); + + /// Returns the pointers to the child variants. + 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_REDUCTIONTREE_H +#define MLIR_TOOLS_MLIRREDUCE_REDUCTIONTREE_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(std::function + 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,6 +32,8 @@ ) add_llvm_tool(mlir-reduce + ReductionNode.cpp + ReductionTree.cpp mlir-reduce.cpp ) 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,112 @@ +//===- 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 child variant in the specified index. +ReductionNode *ReductionNode::getVariant(unsigned long index) { + if (index < variants.size()) + return variants.at(index); + + return nullptr; +} + +/// Returns the pointers to the child variants. +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); +} \ No newline at end of file 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,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. +// +//===----------------------------------------------------------------------===// + +#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( + std::function generateVariants) { + + ReductionNode *currLevel = root; + + while (true) { + generateVariants(currLevel, *test); + + if (currLevel->variantsEmpty() || + !currLevel->getVariant(0)->isInteresting()) + break; + + // Update the mostReduced module in the tester object + test->setMostReduced(currLevel->getVariant(0)->getModule()); + currLevel = currLevel->getVariant(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 @@ -15,6 +15,9 @@ #include +//#include "Passes/PassManager.h" +#include "llvm/Support/InitLLVM.h" +#include "llvm/Support/ToolOutputFile.h" #include "mlir/InitAllDialects.h" #include "mlir/Parser.h" #include "mlir/Pass/Pass.h" @@ -23,8 +26,6 @@ #include "mlir/Support/FileUtilities.h" #include "mlir/Support/LogicalResult.h" #include "mlir/Transforms/Passes.h" -#include "llvm/Support/InitLLVM.h" -#include "llvm/Support/ToolOutputFile.h" using namespace mlir; @@ -81,17 +82,19 @@ if (failed(loadModule(context, moduleRef, inputFilename))) llvm::report_fatal_error("Input test case can't be parsed"); - + // 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"); + //callReductionPasses(test); + test.getMostReduced().print(output->os()); output->keep(); return 0; -} \ No newline at end of file +}