Index: mlir/include/mlir/Reducer/Passes/OpReducer.h =================================================================== --- mlir/include/mlir/Reducer/Passes/OpReducer.h +++ mlir/include/mlir/Reducer/Passes/OpReducer.h @@ -15,65 +15,46 @@ #ifndef MLIR_REDUCER_PASSES_OPREDUCER_H #define MLIR_REDUCER_PASSES_OPREDUCER_H +#include + #include "mlir/IR/Region.h" #include "mlir/Reducer/ReductionNode.h" -#include "mlir/Reducer/ReductionTreeUtils.h" #include "mlir/Reducer/Tester.h" namespace mlir { -class OpReducerImpl { +class OpReducer { public: - OpReducerImpl( - llvm::function_ref(ModuleOp)> getSpecificOps); - - /// Return the name of this reducer class. - StringRef getName(); - - /// Return the initial transformSpace containing the transformable indices. - 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); - - /// Generate variants by removing OpType operations from the module in the - /// parent and link the variants as childs in the Reduction Tree Pass. The - /// transform argument defines the function used to remove the OpTpye - /// operations in range of indexed OpType operations. - void generateVariants(ReductionNode *parent, const Tester &test, - int numVariants, - llvm::function_ref transform); - -private: - llvm::function_ref(ModuleOp)> getSpecificOps; + virtual ~OpReducer() = default; + virtual void reduce(ModuleOp module, + llvm::ArrayRef> rangeToKeep) = 0; + virtual int getNumTargetOps(ModuleOp module) const = 0; }; -/// The OpReducer class defines a variant generator method that produces -/// multiple variants by eliminating different OpType operations from the -/// parent module. +/// Reducer is a helper class to remove potential uninteresting operations from +/// module. template -class OpReducer { +class Reducer : public OpReducer { public: - OpReducer() : impl(new OpReducerImpl(getSpecificOps)) {} + ~Reducer() override = default; - /// Returns the vector of pointer to the OpType operations in the module. - static std::vector getSpecificOps(ModuleOp module) { - std::vector ops; - for (auto op : module.getOps()) { - ops.push_back(op); - } - return ops; + int getNumTargetOps(ModuleOp module) const override { + return std::distance(module.getOps().begin(), + module.getOps().end()); } - /// Deletes the OpType operations in the module in the specified index. - static void deleteOps(ModuleOp module, int start, int end) { + void reduce(ModuleOp module, + llvm::ArrayRef> rangeToKeep) override { std::vector opsToRemove; + size_t keepIndex = 0; - for (auto op : enumerate(getSpecificOps(module))) { + for (auto op : llvm::enumerate(module.getOps())) { int index = op.index(); - if (index >= start && index < end) + if (keepIndex < rangeToKeep.size() && + index == rangeToKeep[keepIndex].second) + ++keepIndex; + if (keepIndex == rangeToKeep.size() || + index < rangeToKeep[keepIndex].first) opsToRemove.push_back(op.value()); } @@ -82,24 +63,6 @@ o->erase(); } } - - /// Return the name of this reducer class. - StringRef getName() { return impl->getName(); } - - /// Return the initial transformSpace containing the transformable indices. - std::vector initTransformSpace(ModuleOp module) { - return impl->initTransformSpace(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) { - impl->generateVariants(parent, test, numVariants, deleteOps); - } - -private: - std::unique_ptr impl; }; } // end namespace mlir Index: mlir/include/mlir/Reducer/ReductionNode.h =================================================================== --- mlir/include/mlir/Reducer/ReductionNode.h +++ mlir/include/mlir/Reducer/ReductionNode.h @@ -17,82 +17,133 @@ #ifndef MLIR_REDUCER_REDUCTIONNODE_H #define MLIR_REDUCER_REDUCTIONNODE_H +#include #include #include "mlir/Reducer/Tester.h" +#include "llvm/Support/Allocator.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 structure -/// which defines the relationship between all the different generated variants. +/// Defines the traversal method options to be used in the reduction tree +/// traversal. +enum TraversalMode { SinglePath, Backtrack, MultiPath }; + +/// This class defines the ReductionNode which is used to generate variant and +/// keep track of the necessary metadata for the reduction pass. The nodes are +/// linked together in a reduction tree structure which defines the relationship +/// between all the different generated variants. class ReductionNode { public: - ReductionNode(ModuleOp module, ReductionNode *parent); + using Range = std::pair; - ReductionNode(ModuleOp module, ReductionNode *parent, - std::vector transformSpace); + ReductionNode(ReductionNode *parent, std::vector range, + llvm::SpecificBumpPtrAllocator &allocator); - /// Calculates and initializes the size and interesting values of the node. - void measureAndTest(const Tester &test); + ReductionNode *getParent() const; - /// Returns the module. - ModuleOp getModule() const { return module; } + size_t getSize() const; - /// Returns true if the size and interestingness have been calculated. - bool isEvaluated() const; + /// Returns true if the module exhibits the interesting behavior. + Tester::Interestingness isInteresting() const; - /// Returns the size in bytes of the module. - int getSize() const; + std::vector getRanges() const; - /// Returns true if the module exhibits the interesting behavior. - bool isInteresting() const; + std::vector &getVariants(); - /// Returns the pointer to a child variant by index. - ReductionNode *getVariant(unsigned long index) const; + /// Split the ranges and generate new variants. + std::vector generateNewVariants(); - /// Returns the number of child variants. - int variantsSize() const; + /// Update the interestingness result from tester. + void update(std::pair result); - /// Returns true if the vector containing the child variants is empty. - bool variantsEmpty() const; +private: + /// Split the largest range into half. Return false if all ranges have length + /// 1, i.e., we can't do further split. + bool splitOneRange(); - /// Sort the child variants and remove the uninteresting ones. - void organizeVariants(const Tester &test); +private: + /// A custom BFS iterator. The difference between + /// llvm/ADT/BreadthFirstIterator.h is the graph we're exploring is dynamic. + /// We may explore more neighbors at certain node if we didn't find interested + /// event. + /// + /// Subclass BaseIterator and implement your node exploration strategy inside + /// getNeighbors(). + template + class BaseIterator { + protected: + std::vector getNeighbors(ReductionNode *node) { + return static_cast(this)->getNeighbors(node); + } + + public: + BaseIterator(ReductionNode *node) { visitQueue.push(node); } + BaseIterator(const BaseIterator &) = default; + BaseIterator() = default; + + static BaseIterator end() { return BaseIterator(); } + + bool operator==(const BaseIterator &i) { + return visitQueue == i.visitQueue; + } + bool operator!=(const BaseIterator &i) { return !(*this == i); } + + BaseIterator &operator++() { + ReductionNode *top = visitQueue.front(); + visitQueue.pop(); + std::vector neighbors = getNeighbors(top); + for (ReductionNode *node : neighbors) + visitQueue.push(node); + return *this; + } + + BaseIterator operator++(int) { + BaseIterator tmp = *this; + ++*this; + return tmp; + } + + ReductionNode &operator*() const { return *(visitQueue.front()); } + ReductionNode *operator->() const { return visitQueue.front(); } + + private: + std::queue visitQueue; + }; - /// Returns the number of child variants. - int transformSpaceSize(); +public: + template + class iterator; - /// Returns a vector indicating the transformed indices as true. - const std::vector getTransformSpace(); + template <> + class iterator : public BaseIterator> { + friend BaseIterator>; + using BaseIterator::BaseIterator; + std::vector getNeighbors(ReductionNode *node); + }; private: - /// Link a child variant node. - void linkVariant(ReductionNode *newVariant); - - // This is the MLIR module of this variant. - ModuleOp module; + /// The size of module after applying the range constraints. + size_t size; - // This is true if the module has been evaluated and it exhibits the - // interesting behavior. - bool interesting; + /// This is true if the module has been evaluated and it exhibits the + /// interesting behavior. + Tester::Interestingness interesting; - // This indicates the number of characters in the printed module if the module - // has been evaluated. - int size; + ReductionNode *parent; - // This indicates if the module has been evaluated (measured and tested). - bool evaluated; + /// We will only keep the operation with index falls into the ranges. + /// For example, number each function in a certain module and then we will + /// remove the functions with index outside the ranges and see if the + /// resulting module is still interesting. + std::vector ranges; - // Indicates the indices in the node that have 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; - // This points to the child variants that were created using this node as a - // starting point. - std::vector> variants; + llvm::SpecificBumpPtrAllocator &allocator; }; } // end namespace mlir Index: mlir/include/mlir/Reducer/ReductionTreePass.h =================================================================== --- mlir/include/mlir/Reducer/ReductionTreePass.h +++ mlir/include/mlir/Reducer/ReductionTreePass.h @@ -22,131 +22,42 @@ #include "PassDetail.h" #include "ReductionNode.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 -/// traversal. -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 /// generated reduced variants. -template -class ReductionTreePass - : public ReductionTreeBase> { +class ReductionTreePass : public ReductionTreeBase { public: ReductionTreePass(const ReductionTreePass &pass) - : ReductionTreeBase>(pass), - root(new ReductionNode(pass.root->getModule().clone(), nullptr)), - test(pass.test) {} + : ReductionTreeBase(pass), opType(pass.opType), + mode(pass.mode), test(pass.test) {} - ReductionTreePass(const Tester &test) : test(test) {} + ReductionTreePass(llvm::StringRef opType, TraversalMode mode, + const Tester &test) + : opType(opType), mode(mode), test(test) {} /// Runs the pass instance in the pass pipeline. - void runOnOperation() override { - ModuleOp module = this->getOperation(); - Reducer reducer; - std::vector transformSpace = reducer.initTransformSpace(module); - ReductionNode *reduced; - - this->root = - std::make_unique(module, nullptr, transformSpace); - - root->measureAndTest(test); + void runOnOperation() override; - 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::updateGoldenModule(module, - reduced->getModule().clone()); - } +private: + template + ModuleOp findOptimal(ModuleOp module, std::unique_ptr reducer, + ReductionNode *node); private: - // Points to the root node in this reduction tree. - std::unique_ptr root; + /// The name of operation that we will try to remove. + llvm::StringRef opType; - // This object defines the variant generation at each level of the reduction - // tree. - Reducer reducer; + TraversalMode mode; - // This is used to test the interesting behavior of the reduction nodes in the - // tree. + /// This is used to test the interesting behavior of the reduction nodes in + /// the tree. const Tester &test; - - /// 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 *currNode = root.get(); - ReductionNode *smallestNode = currNode; - int tSpaceSize = currNode->transformSpaceSize(); - std::vector path; - - ReductionTreeUtils::updateSmallestNode(currNode, smallestNode, path); - - LLVM_DEBUG(llvm::dbgs() << "\nGenerating 1 variant: applying the "); - LLVM_DEBUG(llvm::dbgs() << "transformation to the entire module\n"); - - reducer.generateVariants(currNode, test, 1); - LLVM_DEBUG(llvm::dbgs() << "Testing\n"); - currNode->organizeVariants(test); - - if (!currNode->variantsEmpty()) - return currNode->getVariant(0); - - while (tSpaceSize != 1) { - ReductionTreeUtils::updateSmallestNode(currNode, smallestNode, path); - - LLVM_DEBUG(llvm::dbgs() << "\nGenerating 2 variants: applying the "); - LLVM_DEBUG(llvm::dbgs() << "transformation to two different sections "); - LLVM_DEBUG(llvm::dbgs() << "of transformable indices\n"); - - reducer.generateVariants(currNode, test, 2); - LLVM_DEBUG(llvm::dbgs() << "Testing\n"); - currNode->organizeVariants(test); - - if (currNode->variantsEmpty()) - break; - - currNode = currNode->getVariant(0); - tSpaceSize = currNode->transformSpaceSize(); - path.push_back(0); - } - - if (tSpaceSize == 1) { - ReductionTreeUtils::updateSmallestNode(currNode, smallestNode, path); - - LLVM_DEBUG(llvm::dbgs() << "\nGenerating 1 variants: applying the "); - LLVM_DEBUG(llvm::dbgs() << "transformation to the only transformable"); - LLVM_DEBUG(llvm::dbgs() << "index\n"); - - reducer.generateVariants(currNode, test, 1); - LLVM_DEBUG(llvm::dbgs() << "Testing\n"); - currNode->organizeVariants(test); - - if (!currNode->variantsEmpty()) { - currNode = currNode->getVariant(0); - path.push_back(0); - - ReductionTreeUtils::updateSmallestNode(currNode, smallestNode, path); - } - } - - return currNode; - } }; } // end namespace mlir Index: mlir/include/mlir/Reducer/ReductionTreeUtils.h =================================================================== --- mlir/include/mlir/Reducer/ReductionTreeUtils.h +++ /dev/null @@ -1,53 +0,0 @@ -//===- 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 - -#include "PassDetail.h" -#include "ReductionNode.h" -#include "mlir/Reducer/Tester.h" -#include "llvm/Support/Debug.h" - -namespace mlir { - -// Defines the utilities for the implementation of custom reduction -// passes using the ReductionTreePass framework. -namespace ReductionTreeUtils { - -/// Update the golden module's content with that of the reduced module. -void updateGoldenModule(ModuleOp &golden, ModuleOp reduced); - -/// Update the smallest node traversed so far in the reduction tree and -/// print the debugging information for the currNode being traversed. -void updateSmallestNode(ReductionNode *currNode, ReductionNode *&smallestNode, - std::vector path); - -/// Create a transform space index vector based on the specified number of -/// indices. -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. The isDeletion boolean -/// specifies if the transformation is the deletion of indices. -void createVariants(ReductionNode *parent, const Tester &test, int numVariants, - llvm::function_ref transform, - bool isDeletion); - -} // namespace ReductionTreeUtils - -} // end namespace mlir - -#endif Index: mlir/include/mlir/Reducer/Tester.h =================================================================== --- mlir/include/mlir/Reducer/Tester.h +++ mlir/include/mlir/Reducer/Tester.h @@ -32,12 +32,21 @@ /// case file. class Tester { public: + enum class Interestingness { + True, + False, + NotSure, + }; + Tester(StringRef testScript, ArrayRef testScriptArgs); /// Runs the interestingness testing script on a MLIR test case file. Returns /// true if the interesting behavior is present in the test case or false /// otherwise. - bool isInteresting(StringRef testCase) const; + std::pair isInteresting(ModuleOp module) const; + + /// Check the interestingness of the file in the given path. + Interestingness isInteresting(StringRef testCase) const; private: StringRef testScript; Index: mlir/lib/Reducer/Tester.cpp =================================================================== --- mlir/lib/Reducer/Tester.cpp +++ mlir/lib/Reducer/Tester.cpp @@ -16,15 +16,40 @@ #include "mlir/Reducer/Tester.h" +#include "llvm/Support/ToolOutputFile.h" + using namespace mlir; Tester::Tester(StringRef scriptName, ArrayRef scriptArgs) : testScript(scriptName), testScriptArgs(scriptArgs) {} +std::pair +Tester::isInteresting(ModuleOp module) const { + SmallString<128> filepath; + int fd; + + // Print module to temporary 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_t size = out.os().tell(); + return std::make_pair(isInteresting(filepath), size); +} + /// Runs the interestingness testing script on a MLIR test case file. Returns /// true if the interesting behavior is present in the test case or false /// otherwise. -bool Tester::isInteresting(StringRef testCase) const { +Tester::Interestingness Tester::isInteresting(StringRef testCase) const { std::vector testerArgs; testerArgs.push_back(testCase); @@ -44,7 +69,7 @@ false); if (!result) - return false; + return Interestingness::False; - return true; + return Interestingness::True; } Index: mlir/tools/mlir-reduce/CMakeLists.txt =================================================================== --- mlir/tools/mlir-reduce/CMakeLists.txt +++ mlir/tools/mlir-reduce/CMakeLists.txt @@ -45,9 +45,8 @@ add_llvm_tool(mlir-reduce OptReductionPass.cpp - Passes/OpReducer.cpp ReductionNode.cpp - ReductionTreeUtils.cpp + ReductionTreePass.cpp mlir-reduce.cpp ADDITIONAL_HEADER_DIRS Index: mlir/tools/mlir-reduce/OptReductionPass.cpp =================================================================== --- mlir/tools/mlir-reduce/OptReductionPass.cpp +++ mlir/tools/mlir-reduce/OptReductionPass.cpp @@ -36,21 +36,25 @@ PassManager pmTransform(context); pmTransform.addPass(std::move(optPass)); + std::pair original = test.isInteresting(module); + if (failed(pmTransform.run(moduleVariant))) return; - ReductionNode original(module, nullptr); - original.measureAndTest(test); - - ReductionNode reduced(moduleVariant, nullptr); - reduced.measureAndTest(test); + std::pair reduced = + test.isInteresting(moduleVariant); - if (reduced.isInteresting() && reduced.getSize() < original.getSize()) { - ReductionTreeUtils::updateGoldenModule(module, reduced.getModule().clone()); + if (reduced.first == Tester::Interestingness::True && + reduced.second < original.second) { + module.getBody()->clear(); + module.getBody()->getOperations().splice( + module.getBody()->begin(), moduleVariant.getBody()->getOperations()); LLVM_DEBUG(llvm::dbgs() << "\nSuccessful Transformed version\n\n"); } else { LLVM_DEBUG(llvm::dbgs() << "\nUnsuccessful Transformed version\n\n"); } + moduleVariant->destroy(); + LLVM_DEBUG(llvm::dbgs() << "Pass Complete\n\n"); } Index: mlir/tools/mlir-reduce/Passes/OpReducer.cpp =================================================================== --- mlir/tools/mlir-reduce/Passes/OpReducer.cpp +++ /dev/null @@ -1,41 +0,0 @@ -//===- OpReducer.cpp - 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 -// parameterizable type of operations from the parent module. -// -//===----------------------------------------------------------------------===// -#include "mlir/Reducer/Passes/OpReducer.h" - -using namespace mlir; - -OpReducerImpl::OpReducerImpl( - llvm::function_ref(ModuleOp)> getSpecificOps) - : getSpecificOps(getSpecificOps) {} - -/// Return the name of this reducer class. -StringRef OpReducerImpl::getName() { - return StringRef("High Level Operation Reduction"); -} - -/// Return the initial transformSpace containing the transformable indices. -std::vector OpReducerImpl::initTransformSpace(ModuleOp module) { - auto ops = getSpecificOps(module); - int numOps = std::distance(ops.begin(), ops.end()); - 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. -void OpReducerImpl::generateVariants( - ReductionNode *parent, const Tester &test, int numVariants, - llvm::function_ref transform) { - ReductionTreeUtils::createVariants(parent, test, numVariants, transform, - true); -} Index: mlir/tools/mlir-reduce/ReductionNode.cpp =================================================================== --- mlir/tools/mlir-reduce/ReductionNode.cpp +++ mlir/tools/mlir-reduce/ReductionNode.cpp @@ -15,116 +15,122 @@ //===----------------------------------------------------------------------===// #include "mlir/Reducer/ReductionNode.h" +#include "llvm/ADT/STLExtras.h" + +#include +#include using namespace mlir; -/// Sets up the metadata and links the node to its parent. -ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent) - : module(module), evaluated(false) { +ReductionNode::ReductionNode( + ReductionNode *parent, std::vector ranges, + llvm::SpecificBumpPtrAllocator &allocator) + : size(std::numeric_limits::max()), + interesting(Tester::Interestingness::NotSure), + /// Root node will have the parent pointer point to themselves. + parent(parent == nullptr ? this : parent), ranges(ranges), + allocator(allocator) {} - if (parent != nullptr) - parent->linkVariant(this); -} +/// Returns the size in bytes of the module. +size_t ReductionNode::getSize() const { return size; } -ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent, - std::vector transformSpace) - : module(module), evaluated(false), transformSpace(transformSpace) { +ReductionNode *ReductionNode::getParent() const { return parent; } - if (parent != nullptr) - parent->linkVariant(this); +/// Returns true if the module exhibits the interesting behavior. +Tester::Interestingness ReductionNode::isInteresting() const { + return interesting; } -/// Calculates and updates the size and interesting values of the module. -void ReductionNode::measureAndTest(const Tester &test) { - SmallString<128> filepath; - int fd; - - // Print module to temporary 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()); +std::vector ReductionNode::getRanges() const { + return ranges; +} - llvm::ToolOutputFile out(filepath, fd); - module.print(out.os()); - out.os().close(); +bool ReductionNode::splitOneRange() { + std::vector newRange; + bool split = false; + auto max_element = std::max_element( + ranges.begin(), ranges.end(), [](const Range &lhs, const Range &rhs) { + return (lhs.second - lhs.first) > (rhs.second - rhs.first); + }); - if (out.os().has_error()) - llvm::report_fatal_error("Error emitting bitcode to file '" + filepath); + if (max_element->second - max_element->first == 1) { + return false; + } - size = out.os().tell(); - interesting = test.isInteresting(filepath); - evaluated = true; + for (const Range &range : ranges) { + if (!split && range == *max_element) { + split = true; + int half = (range.first + range.second) / 2; + newRange.push_back(std::make_pair(range.first, half)); + newRange.push_back(std::make_pair(half, range.second)); + } else { + newRange.push_back(range); + } + } + ranges = newRange; + return true; } -/// Returns true if the size and interestingness have been calculated. -bool ReductionNode::isEvaluated() const { return evaluated; } +std::vector &ReductionNode::getVariants() { return variants; } -/// Returns the size in bytes of the module. -int ReductionNode::getSize() const { return size; } +std::vector ReductionNode::generateNewVariants() { + // if we haven't created any variants, we can just generate new variants by + // removing some ranges without spliting ranges. + if (variants.size() != 0 || ranges.size() == 1) { + if (!splitOneRange()) { + return {}; + } + } -/// Returns true if the module exhibits the interesting behavior. -bool ReductionNode::isInteresting() const { return interesting; } + std::vector newNodes; -/// Returns the pointers to the child variants. -ReductionNode *ReductionNode::getVariant(unsigned long index) const { - if (index < variants.size()) - return variants[index].get(); + for (const Range &range : ranges) { + std::vector subRange = ranges; + llvm::erase_value(subRange, range); + ReductionNode *newNode = allocator.Allocate(); + new (newNode) ReductionNode(this, subRange, allocator); + newNodes.push_back(newNode); + variants.push_back(newNode); + } - return nullptr; + return newNodes; } -/// 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(); } - -/// Link a child variant node. -void ReductionNode::linkVariant(ReductionNode *newVariant) { - std::unique_ptr ptrVariant(newVariant); - variants.push_back(std::move(ptrVariant)); +void ReductionNode::update(std::pair result) { + std::tie(interesting, size) = result; } -/// Sort the child variants and remove the uninteresting ones. -void ReductionNode::organizeVariants(const Tester &test) { - // Ensure all variants are evaluated. - for (auto &var : variants) - if (!var->isEvaluated()) - var->measureAndTest(test); - - // Sort variants by interestingness and size. - llvm::array_pod_sort( - variants.begin(), variants.end(), [](const auto *lhs, const auto *rhs) { - if (lhs->get()->isInteresting() && !rhs->get()->isInteresting()) - return 0; - - if (!lhs->get()->isInteresting() && rhs->get()->isInteresting()) - return 1; - - return (lhs->get()->getSize(), rhs->get()->getSize()); - }); - - int interestingCount = 0; - for (auto &var : variants) { - if (var->isInteresting()) { - ++interestingCount; - } else { - break; - } +std::vector +ReductionNode::iterator::getNeighbors(ReductionNode *node) { + // Single Path: Traverses the smallest successful variant at each level until + // no new successful variants can be created at that level. + llvm::ArrayRef variantsFromParent = + node->getParent()->getVariants(); + + if (!llvm::all_of(variantsFromParent, [](ReductionNode *node) { + return node->isInteresting() != Tester::Interestingness::NotSure; + })) { + // We still have variants in queue, wait for them to test interestingness + // and then we can try to select the smallest variant. + return {}; } - // Remove uninteresting variants. - variants.resize(interestingCount); -} + ReductionNode *smallest = nullptr; + for (ReductionNode *node : variantsFromParent) { + if (node->isInteresting() != Tester::Interestingness::True) + continue; + if (smallest == nullptr || node->getSize() < smallest->getSize()) + smallest = node; + } -/// Returns the number of non transformed indices. -int ReductionNode::transformSpaceSize() { - return std::count(transformSpace.begin(), transformSpace.end(), false); -} + if (smallest != nullptr) { + // We got a smallest one, keep traversing from this node. + node = smallest; + } else { + // None of these variants is interesting, let the parent node to generate + // more variants. + node = node->getParent(); + } -/// Returns a vector of the transformable indices in the Module. -const std::vector ReductionNode::getTransformSpace() { - return transformSpace; + return node->generateNewVariants(); } Index: mlir/tools/mlir-reduce/ReductionTreePass.cpp =================================================================== --- /dev/null +++ mlir/tools/mlir-reduce/ReductionTreePass.cpp @@ -0,0 +1,100 @@ +//===- ReductionTreePass.cpp - ReductionTreePass 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. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Reducer/ReductionTreePass.h" + +#include "llvm/Support/Allocator.h" + +namespace mlir { + +namespace { + +std::unique_ptr getOpReducer(llvm::StringRef opType) { + if (opType == ModuleOp::getOperationName()) + return std::make_unique>(); + else if (opType == FuncOp::getOperationName()) + return std::make_unique>(); + llvm_unreachable("Now only supports two built-in ops"); +} + +} // end namespace + +void ReductionTreePass::runOnOperation() { + ModuleOp module = this->getOperation(); + std::unique_ptr reducer = getOpReducer(opType); + std::vector> ranges = { + {0, reducer->getNumTargetOps(module)}}; + + llvm::SpecificBumpPtrAllocator allocator; + + ReductionNode *root = allocator.Allocate(); + new (root) ReductionNode(nullptr, ranges, allocator); + + ModuleOp golden = module; + switch (mode) { + case TraversalMode::SinglePath: + golden = findOptimal(module, std::move(reducer), root); + break; + default: + llvm_unreachable("Unsupported mode"); + } + + if (golden != module) { + module.getBody()->clear(); + module.getBody()->getOperations().splice(module.getBody()->begin(), + golden.getBody()->getOperations()); + golden->destroy(); + } +} + +template +ModuleOp ReductionTreePass::findOptimal(ModuleOp module, + std::unique_ptr reducer, + ReductionNode *root) { + std::pair initStatus = + test.isInteresting(module); + root->update(initStatus); + + ReductionNode *smallestNode = root; + ModuleOp golden = module; + + ReductionNode::iterator iter(root); + + while (iter != ReductionNode::iterator::end()) { + ModuleOp cloneModule = module.clone(); + + ReductionNode ¤tNode = *iter; + reducer->reduce(cloneModule, currentNode.getRanges()); + + std::pair result = + test.isInteresting(cloneModule); + currentNode.update(result); + + if (result.first == Tester::Interestingness::True && + result.second < smallestNode->getSize()) { + smallestNode = ¤tNode; + golden = cloneModule; + } else { + cloneModule->destroy(); + } + + ++iter; + } + + return golden; +} + +} // end namespace mlir Index: mlir/tools/mlir-reduce/ReductionTreeUtils.cpp =================================================================== --- mlir/tools/mlir-reduce/ReductionTreeUtils.cpp +++ /dev/null @@ -1,159 +0,0 @@ -//===- 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" - -#define DEBUG_TYPE "mlir-reduce" - -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 smallest node traversed so far in the reduction tree and -/// print the debugging information for the currNode being traversed. -void ReductionTreeUtils::updateSmallestNode(ReductionNode *currNode, - ReductionNode *&smallestNode, - std::vector path) { - LLVM_DEBUG(llvm::dbgs() << "\nTree Path: root"); - #ifndef NDEBUG - for (int nodeIndex : path) - LLVM_DEBUG(llvm::dbgs() << " -> " << nodeIndex); - #endif - - 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(false); - - return transformSpace; -} - -/// Translate section start and end into a vector of ranges specifying the -/// section in the non transformed indices in the transform space. -static std::vector> getRanges(std::vector tSpace, - int start, int end) { - std::vector> ranges; - int rangeStart = 0; - int rangeEnd = 0; - bool inside = false; - int transformableCount = 0; - - for (auto element : llvm::enumerate(tSpace)) { - int index = element.index(); - bool value = element.value(); - - if (start <= transformableCount && transformableCount < end) { - if (!value && !inside) { - inside = true; - rangeStart = index; - } - if (value && inside) { - rangeEnd = index; - ranges.push_back(std::make_tuple(rangeStart, rangeEnd)); - inside = false; - } - } - - if (!value) - transformableCount++; - - if (transformableCount == end && inside) { - ranges.push_back(std::make_tuple(rangeStart, index + 1)); - inside = false; - break; - } - } - - return ranges; -} - -/// Create the specified number of variants by applying the transform method -/// to different ranges of indices in the parent module. The isDeletion boolean -/// specifies if the transformation is the deletion of indices. -void ReductionTreeUtils::createVariants( - ReductionNode *parent, const Tester &test, int numVariants, - llvm::function_ref transform, bool isDeletion) { - std::vector newTSpace; - ModuleOp module = parent->getModule(); - - std::vector parentTSpace = parent->getTransformSpace(); - int indexCount = parent->transformSpaceSize(); - std::vector> ranges; - - // 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(); - if (isDeletion) { - transform(variantModule, 0, 1); - } else { - ranges = getRanges(parentTSpace, 0, parentTSpace.size()); - transform(variantModule, std::get<0>(ranges[0]), std::get<1>(ranges[0])); - } - - new ReductionNode(variantModule, parent, newTSpace); - - return; - } - - // Create the specified number of variants. - for (int i = 0; i < numVariants; ++i) { - ModuleOp variantModule = module.clone(); - newTSpace = parent->getTransformSpace(); - int sectionSize = indexCount / numVariants; - int sectionStart = sectionSize * i; - int sectionEnd = sectionSize * (i + 1); - - if (i == numVariants - 1) - sectionEnd = indexCount; - - if (isDeletion) - transform(variantModule, sectionStart, sectionEnd); - - ranges = getRanges(parentTSpace, sectionStart, sectionEnd); - - for (auto range : ranges) { - int rangeStart = std::get<0>(range); - int rangeEnd = std::get<1>(range); - - for (int x = rangeStart; x < rangeEnd; ++x) - newTSpace[x] = true; - - if (!isDeletion) - transform(variantModule, rangeStart, rangeEnd); - } - - // Create Reduction Node in the Reduction tree - new ReductionNode(variantModule, parent, newTSpace); - } -} Index: mlir/tools/mlir-reduce/mlir-reduce.cpp =================================================================== --- mlir/tools/mlir-reduce/mlir-reduce.cpp +++ mlir/tools/mlir-reduce/mlir-reduce.cpp @@ -103,7 +103,7 @@ // Initialize test environment. const Tester test(testFilename, testArguments); - if (!test.isInteresting(inputFilename)) + if (test.isInteresting(inputFilename) != Tester::Interestingness::True) llvm::report_fatal_error( "Input test case does not exhibit interesting behavior"); @@ -118,11 +118,10 @@ } else if (passTestSpecifier == "function-reducer") { - // Reduction tree pass with OpReducer variant generation and single path + // Reduction tree pass with Reducer variant generation and single path // traversal. - pm.addPass( - std::make_unique, SinglePath>>( - test)); + pm.addPass(std::make_unique( + FuncOp::getOperationName(), TraversalMode::SinglePath, test)); } ModuleOp m = moduleRef.get().clone();