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_ \ No newline at end of file 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 --- a/mlir/include/mlir/Reducer/ReductionNode.h +++ b/mlir/include/mlir/Reducer/ReductionNode.h @@ -31,7 +31,7 @@ /// which defines the relationship between all the different generated variants. class ReductionNode { public: - ReductionNode(ModuleOp module, ReductionNode *parent, Tester test); + ReductionNode(ModuleOp module, ReductionNode *parent, Tester &test); /// Calculates and initializes the size and interesting values of the node. void measureAndTest(Tester &test); diff --git a/mlir/include/mlir/Reducer/ReductionTree.h b/mlir/include/mlir/Reducer/ReductionTree.h deleted file mode 100644 --- a/mlir/include/mlir/Reducer/ReductionTree.h +++ /dev/null @@ -1,55 +0,0 @@ -//===- 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/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. // //===----------------------------------------------------------------------===// @@ -19,17 +19,16 @@ #include -#include "mlir/IR/Module.h" #include "llvm/ADT/SmallString.h" #include "llvm/Support/Error.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/Program.h" +#include "mlir/IR/Module.h" 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 +38,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/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. // //===----------------------------------------------------------------------===// diff --git a/mlir/test/mlir-reduce/test-pass-pipeline.mlir b/mlir/test/mlir-reduce/test-pass-pipeline.mlir new file mode 100644 --- /dev/null +++ b/mlir/test/mlir-reduce/test-pass-pipeline.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,12 +32,21 @@ ) add_llvm_tool(mlir-reduce + Passes/OpReducer.cpp ReductionNode.cpp - ReductionTree.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) + +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 --- a/mlir/tools/mlir-reduce/ReductionNode.cpp +++ b/mlir/tools/mlir-reduce/ReductionNode.cpp @@ -46,7 +46,7 @@ /// Sets up the metadata and links the node to its parent. ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent, - Tester test) + Tester &test) : module(module), parent(parent) { this->measureAndTest(test); diff --git a/mlir/tools/mlir-reduce/ReductionTree.cpp b/mlir/tools/mlir-reduce/ReductionTree.cpp deleted file mode 100644 --- a/mlir/tools/mlir-reduce/ReductionTree.cpp +++ /dev/null @@ -1,56 +0,0 @@ -//===- 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 @@ -15,16 +15,19 @@ #include +#include "llvm/Support/InitLLVM.h" +#include "llvm/Support/ToolOutputFile.h" #include "mlir/InitAllDialects.h" #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" #include "mlir/Transforms/Passes.h" -#include "llvm/Support/InitLLVM.h" -#include "llvm/Support/ToolOutputFile.h" using namespace mlir; @@ -84,13 +87,23 @@ // 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;