diff --git a/mlir/include/mlir/Reducer/Passes/FunctionReducer.h b/mlir/include/mlir/Reducer/Passes/FunctionReducer.h deleted file mode 100644 --- a/mlir/include/mlir/Reducer/Passes/FunctionReducer.h +++ /dev/null @@ -1,36 +0,0 @@ -//===- FunctionReducer.h - MLIR Reduce Function Reducer ---------*- 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 -// -//===----------------------------------------------------------------------===// -// -// This file defines the FunctionReducer class. It defines a variant generator -// method with the purpose of producing different variants by eliminating -// functions from the parent module. -// -//===----------------------------------------------------------------------===// - -#ifndef MLIR_REDUCER_PASSES_FUNCTIONREDUCER_H -#define MLIR_REDUCER_PASSES_FUNCTIONREDUCER_H - -#include "mlir/Reducer/ReductionNode.h" -#include "mlir/Reducer/Tester.h" - -namespace mlir { - -/// The FunctionReducer class defines a variant generator method that produces -/// multiple variants by eliminating different operations from the -/// parent module. -class FunctionReducer { -public: - /// Generate variants by removing functions from the module in the parent - /// Reduction Node and link the variants as children in the Reduction Tree - /// Pass. - void generateVariants(ReductionNode *parent, const Tester *test); -}; - -} // end namespace mlir - -#endif 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,47 @@ +//===- OpReducer.h - MLIR Reduce Operation Reducer ------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines the OpReducer class. It defines a variant generator method +// with the purpose of producing different variants by eliminating a +// parametarizable type of operations from the parent module. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_REDUCER_PASSES_OPREDUCER_H +#define MLIR_REDUCER_PASSES_OPREDUCER_H + +#include "mlir/Dialect/GPU/GPUDialect.h" +#include "mlir/Dialect/LLVMIR/LLVMDialect.h" +#include "mlir/Dialect/SCF/SCF.h" +#include "mlir/Dialect/SPIRV/SPIRVOps.h" +#include "mlir/Reducer/ReductionNode.h" +#include "mlir/Reducer/Tester.h" + +namespace mlir { + +/// The OpReducer class defines a variant generator method that produces +/// multiple variants by eliminating different operations from the +/// parent module. +template +class OpReducer { +public: + /// Return the name of this reducer. + StringRef getName(); + + /// Return the initial transformSpace cointaing the transformable indexes. + static std::vector initTransformSpace(ModuleOp module); + + /// Generate variants by removing opType operations from the module in the + /// parent and link the variants as childs in the Reduction Tree Pass. + void generateVariants(ReductionNode *parent, const Tester *test, + int numVariants); +}; + +} // end namespace mlir + +#endif diff --git a/mlir/include/mlir/Reducer/ReductionNode.h b/mlir/include/mlir/Reducer/ReductionNode.h --- a/mlir/include/mlir/Reducer/ReductionNode.h +++ b/mlir/include/mlir/Reducer/ReductionNode.h @@ -32,6 +32,9 @@ public: ReductionNode(ModuleOp module, ReductionNode *parent); + ReductionNode(ModuleOp module, ReductionNode *parent, + std::vector transformSpace); + /// Calculates and initializes the size and interesting values of the node. void measureAndTest(const Tester *test); @@ -50,12 +53,21 @@ /// Returns the pointer to a child variant by index. ReductionNode *getVariant(unsigned long index) const; + /// Returns the number of child variants. + int variantsSize() const; + /// Returns true if the vector containing the child variants is empty. bool variantsEmpty() const; /// Sort the child variants and remove the uninteresting ones. void organizeVariants(const Tester *test); + /// Returns the number of child variants. + int transformSpaceSize(); + + /// Returns a vector of the transformable indices. + const std::vector getTransformSpace(); + private: /// Link a child variant node. void linkVariant(ReductionNode *newVariant); @@ -74,6 +86,10 @@ // This indicates if the module has been evalueated (measured and tested). bool evaluated; + // Contains the indices in the node that haven't been transformed in previous + // levels of the reduction tree. + std::vector transformSpace; + // This points to the child variants that were created using this node as a // starting point. std::vector> variants; diff --git a/mlir/include/mlir/Reducer/ReductionTreePass.h b/mlir/include/mlir/Reducer/ReductionTreePass.h --- a/mlir/include/mlir/Reducer/ReductionTreePass.h +++ b/mlir/include/mlir/Reducer/ReductionTreePass.h @@ -21,21 +21,17 @@ #include "PassDetail.h" #include "ReductionNode.h" -#include "mlir/Reducer/Passes/FunctionReducer.h" +#include "mlir/Reducer/Passes/OpReducer.h" +#include "mlir/Reducer/ReductionTreeUtils.h" #include "mlir/Reducer/Tester.h" +#define DEBUG_TYPE "mlir-reduce" + namespace mlir { -/// Defines the traversal method options to be used in the reduction tree +// Defines the traversal method options to be used in the reduction tree /// traversal. -enum TraversalMode { SinglePath, MultiPath, Concurrent, Backtrack }; - -// This class defines the non- templated utilities used by the ReductionTreePass -// class. -class ReductionTreeUtils { -public: - void updateGoldenModule(ModuleOp &golden, ModuleOp reduced); -}; +enum TraversalMode { SinglePath, Backtrack, MultiPath }; /// 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 @@ -44,28 +40,36 @@ class ReductionTreePass : public ReductionTreeBase> { public: - ReductionTreePass(const Tester *test) : test(test) {} - ReductionTreePass(const ReductionTreePass &pass) - : root(new ReductionNode(pass.root->getModule().clone(), nullptr)), + : root(new ReductionNode(pass.root->getModule().clone(), nullptr, + pass.root->getTransformSpace())), test(pass.test) {} + ReductionTreePass(const Tester *test) : test(test) {} + /// Runs the pass instance in the pass pipeline. void runOnOperation() override { ModuleOp module = this->getOperation(); - this->root = std::make_unique(module, nullptr); + std::vector transformSpace = Reducer::initTransformSpace(module); ReductionNode *reduced; + this->root = + std::make_unique(module, nullptr, transformSpace); + + root->measureAndTest(test); + + LLVM_DEBUG(llvm::dbgs() << "\nReduction Tree Pass: " << reducer.getName();); switch (mode) { case SinglePath: + LLVM_DEBUG(llvm::dbgs() << " (Single Path)\n";); reduced = singlePathTraversal(); break; default: llvm::report_fatal_error("Traversal method not currently supported."); } - ReductionTreeUtils utils; - utils.updateGoldenModule(module, reduced->getModule()); + ReductionTreeUtils::updateGoldenModule(module, + reduced->getModule().clone()); } private: @@ -85,19 +89,52 @@ /// function. Stops when no new successful variants can be created at the /// current level. ReductionNode *singlePathTraversal() { - ReductionNode *currLevel = root.get(); + ReductionNode *currNode = root.get(); + ReductionNode *smallestNode = currNode; + int tSpaceSize = currNode->transformSpaceSize(); + int numVariants = 2; + std::vector path; + + // Attempt to create atleast one succesful variant by creating the least + // number of variants. + while (numVariants <= tSpaceSize) { + ReductionTreeUtils::processNode(currNode, smallestNode, path); + + LLVM_DEBUG(llvm::dbgs() << "\nGenerating " << numVariants); + LLVM_DEBUG(llvm::dbgs() << " variants\nTesting\n"); + + reducer.generateVariants(currNode, test, numVariants); + currNode->organizeVariants(test); + + if (currNode->variantsEmpty()) { + numVariants = numVariants * 2; + continue; + } + + currNode = currNode->getVariant(0); + tSpaceSize = currNode->transformSpaceSize(); + path.push_back(0); + } + + // Attempt to create a single veriant by trasforming/erasing the unique + // index in the transform space. + if (tSpaceSize == 1) { + ReductionTreeUtils::processNode(currNode, smallestNode, path); + + LLVM_DEBUG(llvm::dbgs() << "\nGenerating 1 variant\nTesting\n";); - while (true) { - reducer.generateVariants(currLevel, test); - currLevel->organizeVariants(test); + reducer.generateVariants(currNode, test, numVariants); + currNode->organizeVariants(test); - if (currLevel->variantsEmpty()) - break; + if (!currNode->variantsEmpty()) { + currNode = currNode->getVariant(0); + path.push_back(0); - currLevel = currLevel->getVariant(0); + ReductionTreeUtils::processNode(currNode, smallestNode, path); + } } - return currLevel; + return smallestNode; } }; diff --git a/mlir/include/mlir/Reducer/ReductionTreeUtils.h b/mlir/include/mlir/Reducer/ReductionTreeUtils.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Reducer/ReductionTreeUtils.h @@ -0,0 +1,51 @@ +//===- ReductionTreeUtils.h - Reduction Tree utilities ----------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines the Reduction Tree Utilities. It defines pass independent +// methods that help in the reduction passes of the MLIR Reduce tool. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_REDUCER_REDUCTIONTREEUTILS_H +#define MLIR_REDUCER_REDUCTIONTREEUTILS_H + +#include "PassDetail.h" +#include "ReductionNode.h" +#include "mlir/Reducer/Tester.h" +#include "llvm/Support/Debug.h" + +#define DEBUG_TYPE "mlir-reduce" + +namespace mlir { + +// This class defines the utilities for the implementation of custom reduction +// passes using the ReductionTreePass framework. +class ReductionTreeUtils { +public: + /// Update the golden module's content with that of the reduced module. + static void updateGoldenModule(ModuleOp &golden, ModuleOp reduced); + + /// Update the the smallest node traversed so far in the reduction tree and + /// print the debugging information for the currNode being traversed. + static void processNode(ReductionNode *currNode, ReductionNode *&smallestNode, + std::vector path); + + /// Create a transform space index vector based on the specified number of + /// indices. + static std::vector createTransformSpace(ModuleOp module, int numIndices); + + /// Create the specified number of variants by applying the transform method + /// to different ranges of indices in the parent module. + static void createVariants(ReductionNode *parent, const Tester *test, + int numVariants, + std::function transform); +}; + +} // end namespace mlir + +#endif 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,9 +32,9 @@ ) add_llvm_tool(mlir-reduce - Passes/FunctionReducer.cpp + Passes/OpReducer.cpp ReductionNode.cpp - ReductionTreePass.cpp + ReductionTreeUtils.cpp mlir-reduce.cpp ADDITIONAL_HEADER_DIRS diff --git a/mlir/tools/mlir-reduce/Passes/FunctionReducer.cpp b/mlir/tools/mlir-reduce/Passes/FunctionReducer.cpp deleted file mode 100644 --- a/mlir/tools/mlir-reduce/Passes/FunctionReducer.cpp +++ /dev/null @@ -1,72 +0,0 @@ -//===- FunctionReducer.cpp - MLIR Reduce Function Reducer -----------------===// -// -// 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 FunctionReducer class. It defines a variant generator -// class to be used in a Reduction Tree Pass instantiation with the aim of -// reducing the number of function operations in an MLIR Module. -// -//===----------------------------------------------------------------------===// - -#include "mlir/Reducer/Passes/FunctionReducer.h" -#include "mlir/IR/Function.h" - -using namespace mlir; - -/// Return the number of function operations in the module's body. -int countFunctions(ModuleOp module) { - auto ops = module.getOps(); - return std::distance(ops.begin(), ops.end()); -} - -/// Generate variants by removing function operations from the module in the -/// parent and link the variants as children in the Reduction Tree Pass. -void FunctionReducer::generateVariants(ReductionNode *parent, - const Tester *test) { - ModuleOp module = parent->getModule(); - int opCount = countFunctions(module); - int sectionSize = opCount / 2; - std::vector opsToRemove; - - if (opCount == 0) - return; - - // Create a variant by deleting all ops. - if (opCount == 1) { - opsToRemove.clear(); - ModuleOp moduleVariant = module.clone(); - - for (FuncOp op : moduleVariant.getOps()) - opsToRemove.push_back(op); - - for (Operation *o : opsToRemove) - o->erase(); - - new ReductionNode(moduleVariant, parent); - - return; - } - - // Create two variants by bisecting the module. - for (int i = 0; i < 2; ++i) { - opsToRemove.clear(); - ModuleOp moduleVariant = module.clone(); - - for (auto op : enumerate(moduleVariant.getOps())) { - int index = op.index(); - if (index >= sectionSize * i && index < sectionSize * (i + 1)) - opsToRemove.push_back(op.value()); - } - - for (Operation *o : opsToRemove) - o->erase(); - - new ReductionNode(moduleVariant, parent); - } - - return; -} 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,77 @@ +//===- OpReducer.h - MLIR Reduce Operation Reducer --------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines the OpReducer class. It defines a variant generator method +// with the purpose of producing different variants by eliminating a +// parametarizable type of operations from the parent module. +// +//===----------------------------------------------------------------------===// +#include "mlir/Reducer/Passes/OpReducer.h" +#include "mlir/Reducer/ReductionTreeUtils.h" + +using namespace mlir; + +/// Return the number of opType operations in the module's body. +template +int countOps(ModuleOp module) { + auto ops = module.getOps(); + return std::distance(ops.begin(), ops.end()); +} + +/// Delete the opType opearations in a given range of indices. +template +static void deleteOps(ModuleOp module, int start, int end) { + std::vector opsToRemove; + + for (auto op : enumerate(module.getOps())) { + int index = op.index(); + if (index >= start && index < end) { + opsToRemove.push_back(op.value()); + } + } + + for (Operation *o : opsToRemove) { + o->dropAllUses(); + o->erase(); + } +} + +/// Return the name of this reducer class. +template +StringRef OpReducer::getName() { + return StringRef("High Level Operation Reduction"); +} + +/// Return the initial transformSpace cointaing the transformable indexes. +template +std::vector OpReducer::initTransformSpace(ModuleOp module) { + int numOps = countOps(module); + return ReductionTreeUtils::createTransformSpace(module, numOps); +} + +/// Generate variants by removing opType operations from the module in the +/// parent and link the variants as childs in the Reduction Tree Pass. +template +void OpReducer::generateVariants(ReductionNode *parent, + const Tester *test, int numVariants) { + ReductionTreeUtils::createVariants(parent, test, numVariants, + deleteOps); +} + +namespace mlir { + +template class OpReducer; +template class OpReducer; +template class OpReducer; +template class OpReducer; +template class OpReducer; +template class OpReducer; +template class OpReducer; +template class OpReducer; + +} // namespace mlir diff --git a/mlir/tools/mlir-reduce/ReductionNode.cpp b/mlir/tools/mlir-reduce/ReductionNode.cpp --- a/mlir/tools/mlir-reduce/ReductionNode.cpp +++ b/mlir/tools/mlir-reduce/ReductionNode.cpp @@ -26,6 +26,14 @@ parent->linkVariant(this); } +ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent, + std::vector transformSpace) + : module(module), evaluated(false), transformSpace(transformSpace) { + + if (parent != nullptr) + parent->linkVariant(this); +} + /// Calculates and updates the size and interesting values of the module. void ReductionNode::measureAndTest(const Tester *test) { SmallString<128> filepath; @@ -67,6 +75,9 @@ return nullptr; } +/// Returns the number of child variants. +int ReductionNode::variantsSize() const { return variants.size(); } + /// Returns true if the child variants vector is empty. bool ReductionNode::variantsEmpty() const { return variants.empty(); } @@ -107,3 +118,11 @@ // Remove uninteresting variants. variants.resize(interestingCount); } + +/// Returns the number of child variants. +int ReductionNode::transformSpaceSize() { return transformSpace.size(); } + +/// Returns a vector of the transformable indices in the Module. +const std::vector ReductionNode::getTransformSpace() { + return transformSpace; +} diff --git a/mlir/tools/mlir-reduce/ReductionTreePass.cpp b/mlir/tools/mlir-reduce/ReductionTreePass.cpp deleted file mode 100644 --- a/mlir/tools/mlir-reduce/ReductionTreePass.cpp +++ /dev/null @@ -1,28 +0,0 @@ -//===- ReductionTreePass.cpp - 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. 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. -// -//===----------------------------------------------------------------------===// - -#include "mlir/Reducer/ReductionTreePass.h" - -using namespace mlir; - -/// Update the golden module's content with that of the reduced module. -void ReductionTreeUtils::updateGoldenModule(ModuleOp &golden, - ModuleOp reduced) { - golden.getBody()->clear(); - - golden.getBody()->getOperations().splice(golden.getBody()->begin(), - reduced.getBody()->getOperations()); -} diff --git a/mlir/tools/mlir-reduce/ReductionTreeUtils.cpp b/mlir/tools/mlir-reduce/ReductionTreeUtils.cpp new file mode 100644 --- /dev/null +++ b/mlir/tools/mlir-reduce/ReductionTreeUtils.cpp @@ -0,0 +1,97 @@ +//===- ReductionTreeUtils.cpp - Reduction Tree Utilities ------------------===// +// +// 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 Utilities. It defines pass independent +// methods that help in a reduction pass of the MLIR Reduce tool. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Reducer/ReductionTreeUtils.h" + +using namespace mlir; + +/// Update the golden module's content with that of the reduced module. +void ReductionTreeUtils::updateGoldenModule(ModuleOp &golden, + ModuleOp reduced) { + golden.getBody()->clear(); + + golden.getBody()->getOperations().splice(golden.getBody()->begin(), + reduced.getBody()->getOperations()); +} + +/// Update the the smallest node traversed so far in the reduction tree and +/// print the debugging information for the currNode being traversed. +void ReductionTreeUtils::processNode(ReductionNode *currNode, + ReductionNode *&smallestNode, + std::vector path) { + LLVM_DEBUG(llvm::dbgs() << "\nTree Path: root"); + for (auto i = path.begin(); i != path.end(); ++i) + LLVM_DEBUG(llvm::dbgs() << " -> " << *i); + + LLVM_DEBUG(llvm::dbgs() << "\nSize (chars): " << currNode->getSize()); + if (currNode->getSize() < smallestNode->getSize()) { + LLVM_DEBUG(llvm::dbgs() << " - new smallest node!"); + smallestNode = currNode; + } +} + +/// Create a transform space index vector based on the specified number of +/// indices. +std::vector ReductionTreeUtils::createTransformSpace(ModuleOp module, + int numIndices) { + std::vector transformSpace; + + for (int i = 0; i < numIndices; ++i) + transformSpace.push_back(i); + + return transformSpace; +} + +/// Create the specified number of variants by applying the transform method +/// to different ranges of indices in the parent module. +void ReductionTreeUtils::createVariants( + ReductionNode *parent, const Tester *test, int numVariants, + std::function transform) { + + std::vector newTransformSpace; + ModuleOp module = parent->getModule(); + int indexCount = parent->transformSpaceSize(); + + // No new variants can be created. + if (indexCount == 0) + return; + + // Create a single variant by transforming the unique index. + if (indexCount == 1) { + ModuleOp variantModule = module.clone(); + transform(variantModule, 0, 1); + new ReductionNode(variantModule, parent, newTransformSpace); + + return; + } + + // Create the specified number of variants. + for (int i = 0; i < numVariants; ++i) { + ModuleOp variantModule = module.clone(); + newTransformSpace = parent->getTransformSpace(); + int sectionSize = indexCount / numVariants; + int start = sectionSize * i; + int end = sectionSize * (i + 1); + + if (i == numVariants - 1) + end = indexCount; + + transform(variantModule, start, end); + + for (int x = start; x < end; ++x) { + newTransformSpace.erase(newTransformSpace.begin() + start); + } + + new ReductionNode(variantModule, parent, newTransformSpace); + } +} 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 @@ -96,8 +96,8 @@ // Reduction tree pass with OpReducer variant generation and single path // traversal. - pm.addPass( - std::make_unique>(&test)); + pm.addPass(std::make_unique, SinglePath>>( + &test)); ModuleOp m = moduleRef.get().clone();