Create the Reduction Tree Pass

[msifontes]

Summary

Implement the Reduction Tree Pass framework as part of the MLIR Reduce tool. This is a parametarizable pass that allows for the implementation of custom reductions passes in the tool.
Implement the OpReducer class as an example of a 'Reducer' parameter for the instantiation of a Reduction Tree Pass.
Create a pass pipeline with a Reduction Tree Pass with the OpReducer class specified as parameter.

[msifontes]

1. Updating D83969: Create the Reduction Tree Pass #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment. #
4. If you intended to create a new revision, use:
5. $ arc diff --create

Fix working directory HEAD

[msifontes]

Add empty line to CMakeList file.

[msifontes]

This comment was removed by msifontes.

[tpopp]

mlir/include/mlir/Reducer/Passes/OpReducer.h

8 ↗

(On Diff #278553)

Include a /// \file on the line before the text (so line 8 and other text on line 9)

Also, for lines 9-12, 3 '/'s

34 ↗

(On Diff #278553)

Maybe return the bool since you aren't returning anything right now?

mlir/include/mlir/Reducer/ReductionNode.h

9

/// \file again

21

I don't think this is needed in the header file.

50

Optional: Maybe just provide iterator implementations for begin/end. This might be safe now, but is rather risky in C++ because it requires that the object outlives the returned vector if someone captures the return as a reference.

mlir/include/mlir/Reducer/ReductionTreePass.h

9

\file

29

enums should start with an uppercase, so "TraversaMode". The values should also start capitalized.

49

I think the StringRef constructor here is unneeded

84

I think all of this deletion logic is unnecessary if you use std::vector<std::unique_ptr<ReductionNode>> and let it do all the deletion at the end.

85

micro-optimization doing this on one line. Right now this copies the vector.

103

2 if statements might be slightly more readable here. Otherwise you're missing a rare chance to use a do/while loop!!

117

I believe MLIR style wants something like golden.walk([&](auto *op) {opsToSwap.pushBack(op); } )

mlir/test/mlir-reduce/reduction-tree-pass.mlir

4

Can you leave a comment on what this is testing? It's surprising to see a 50 line test case with only 1 CHECK.

mlir/tools/mlir-reduce/Passes/OpReducer.cpp

22 ↗

(On Diff #278553)

I think this might just return the number of Blocks unless you use module.getOps()?

mlir/tools/mlir-reduce/ReductionNode.cpp

53

I don't know if LLVM feels this way, but usually people want constructors to be fast, so it would be better to not have this in the construction step.

mlir/tools/mlir-reduce/mlir-reduce.cpp

106

Do you need this print statement?

[msifontes]

Apply requested changes

• Use of smart pointers
• Simplify reduction node constructor by separating the testing and sorting
• Add test description comment
• Use getOps() to iterate over function operations
• Doxygen formatted comments
• Simplify updateGolden method
• Replace getVariants() with getVariant(int index)
• Eliminate reduction tree destructor
• Capitalize enumerator options
• Change variantGenerator() to type boolean

[tpopp]

mlir/include/mlir/Reducer/PassDetail.h

10

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

mlir/include/mlir/Reducer/Passes/OpReducer.h

15 ↗

(On Diff #279375)

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

mlir/include/mlir/Reducer/ReductionNode.h

9

On the style guide, they show 3 slashes being used for this section.

18

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

44

I wouldn't have thought of this before your line above, but since you started it, let's make the other const methods const also :D

mlir/include/mlir/Reducer/ReductionTreePass.h

2

Probably this should be a header and C++ file?

18

clang-tidy: warning: header guard does not follow preferred style [llvm-header-guard]

42

generateVariants = Reducer(); maybe? If not, it's fine the way it is.

54

I think you want make_shared here. https://en.cppreference.com/w/cpp/memory/shared_ptr/make_shared

mlir/test/mlir-reduce/reduction-tree-pass.mlir

4

Try to keep comments under 80 lines (CHECK lines can be longer).

mlir/tools/mlir-reduce/Passes/OpReducer.cpp

23 ↗

(On Diff #279375)

In theory you can ignore this, but in practice someone at Google will have to come correct this right after you land it, so try to handle unused variable notices with a (void) op; added in the for loop body.

33 ↗

(On Diff #279375)

nit: constexpr int numVariants = 2;

34 ↗

(On Diff #279375)

nit: const int for the next 2.

mlir/tools/mlir-reduce/ReductionNode.cpp

23

You don't need a shared_pointer at locations like these where your using it and not holding a reference to the object after the function call ends.

106

I think std::make_shared would work here also.

[mehdi_amini]

mlir/include/mlir/Reducer/ReductionNode.h

68

Why shared_ptr and not unique_ptr? It isn't clear to me why do we need refcounting here?

[msifontes]

Apply Requested changes

• Comment formatting changes
• Use unique_ptr to reference reduction nodes
• Split reduction Tree Pass into header and .cpp file
• Fix file header formatting
• Fix header guard formatting
• Use const where possible

[msifontes]

NFC Changes

[msifontes]

Remove duplicate Tester.cpp

[msifontes]

Fix PassDetail.h header guard format

[msifontes]

This comment was removed by msifontes.

[msifontes]

This comment was removed by msifontes.

[jpienaar]

mlir/include/mlir/Reducer/Passes/OpReducer.h

1 ↗

(On Diff #279920)

Missing c++ designator here

Could we perhaps reduce the file description?

Looking at the description too, perhaps the name is confusing :) This feels very general description, but if I look at the implementation then this is an instance of variant generation that tries to delete functions that are not interesting.

24 ↗

(On Diff #279920)

I feel like these might be comments for the markdown doc: you are using a specific variant generation but then describiing it as if a general one.

30 ↗

(On Diff #279920)

Why is this a public static method here? E.g., do we expect all reduction passes to implement this?

34 ↗

(On Diff #279920)

Why static? Meaning, how would folks be able to track variants already pursued from within this static method. That seems like it would require tracking the space explored in the reductionnode's and some way not attempting things that have been done before.

mlir/include/mlir/Reducer/ReductionNode.h

2

Missing c++ indicator

59

Do we care about those that aren't interesting?

mlir/include/mlir/Reducer/ReductionTreePass.h

73

Why is this needed here? It seems the ReductionTreePass is independent of this

mlir/tools/mlir-reduce/ReductionNode.cpp

23

I'd just pass in const ReductionNode&, std::unique_ptr adds nothing here for me (means you need to dereference at call site sure, but inside you don't have to care if the unique_ptr is empty or not, and no ownership changes)

70

Why not just print to a std::string instead? (no need to create and write a file). Unless there is a reason (e.g., in case of crashes), that you'd want this

[msifontes]

mlir/include/mlir/Reducer/ReductionTreePass.h

73

The linker was having trouble with the ReductionTreePass class because of the template. Two solutions I found was having the method definitions in the header file or defining this templated class. Is there a different way to solve this linker problem? I could also move this template class definition to the file handling the pass manager.

[msifontes]

mlir/tools/mlir-reduce/ReductionNode.cpp

70

This is needed for running the interestingness script.

[msifontes]

mlir/tools/mlir-reduce/ReductionNode.cpp

23

I believe this is needed because of the way std::sort is implemented. This function must accept two arguments of the same type as the members in the vector being sorted which is a unique_ptr vector.

[rriddle]

mlir/include/mlir/Reducer/PassDetail.h

2

This comment seems off.

mlir/include/mlir/Reducer/Passes.td

2

This line should be 80 characters long.

14

typo: REDUCER

20

nit: This looks like it is over 80 characters.

mlir/include/mlir/Reducer/Passes/OpReducer.h

15 ↗

(On Diff #278541)

This path needs to be updated.

8 ↗

(On Diff #278553)

nit: I would remove this, we don't use those directives anywhere else in the MLIR codebase.

mlir/include/mlir/Reducer/ReductionNode.h

9

We haven't used this anywhere else in MLIR, I'd rather just omit it.

26

Can you remove this?

64

Can you add comments to all of these? It isn't clear what they mean.

[rriddle]

mlir/include/mlir/Reducer/ReductionTreePass.h

31

Please move this down into the namespace.

52

I would expect this to already be provided for you by the base class.

58

nit: Please add comments to these.

60

nit: Drop the llvm::, it is re-exported in the mlir namespace.

73

Can you switch this to using pImpl techniques instead? That would allow for this to be templated while specifying the implementation within the .cpp file.

mlir/tools/mlir-reduce/Passes/OpReducer.cpp

23 ↗

(On Diff #279920)

Why are you counting functions? That doesn't match up with the method name or comments.

Also, I'd just do something like:

auto ops = module.getOps<FuncOp>();
return std::distance(ops.begin(), ops.end());

33 ↗

(On Diff #279920)

What is the result of this supposed to mean? It isn't documented in the method comments.

35 ↗

(On Diff #279920)

nit: Drop the constexpr here, and the const below. We don't attach those to integers/simple types in MLIR.

48 ↗

(On Diff #279920)

Use llvm::enumerate to have an index and a value.

54 ↗

(On Diff #279920)

nit: Spell out auto here.

57 ↗

(On Diff #279920)

This seems weird from an API perspective, it isn't clear what the ownership is. Can you refactor to make the ownership explicit? e.g. by using a static method instead of the constructor.

mlir/tools/mlir-reduce/ReductionNode.cpp

42

Where are you getting this function from? I don't expect this would work well on windows, can you use something from LLVM instead?

113

nit: Can you use llvm::array_pod_sort instead? It is generally preferred over std::sort.

https://github.com/llvm/llvm-project/blob/1890a65ca17504cab4032d3c8cc0c4c568d44717/llvm/include/llvm/ADT/STLExtras.h#L1367

[mehdi_amini]

mlir/tools/mlir-reduce/ReductionNode.cpp

113

I thoughts array_pod_sort relies on the element being sorted using std::less? There is a custom function here.

[msifontes]

Apply requested changes

• Add missing c++ designators
• Remove uninteresting nodes when sorting
• Create testing script to test new functionality
• Comment formatting changes
• Add class member descriptions
• Reformatted OpReducer class to FuncReducer class with the objective of reducing the number of functions.
• Remove ClonePass()
• Use of llvm::enumerate where possible
• Modify ReductioNode constructor to split the functionality of linking a child node to a parent
• Change module measurement to character measurement using ifstream and the temporary file

Pending:

• pimpl template class refactoring
• Making the variantGenerator method non-static
• Passes.h.inc dependency error
• Replace std::sort

[rriddle]

mlir/tools/mlir-reduce/ReductionNode.cpp

113

You can provide your own functor, it just defaults to std::less for convenience:

https://github.com/llvm/llvm-project/blob/873b79b8675d0c8eca6055ae8a874fe52b033c28/mlir/tools/mlir-tblgen/PassDocGen.cpp#L66
https://github.com/llvm/llvm-project/blob/ff6a0b6a8ee74693e9711973028a8a327adf9cd5/llvm/lib/Object/SymbolSize.cpp#L81
https://github.com/llvm/llvm-project/blob/308571074c13ea2a0758aa085aa02f72150f891e/mlir/tools/mlir-tblgen/mlir-tblgen.cpp#L46

[msifontes]

NFC

[msifontes]

Apply changes

• Replace static method reference with Reducer member object in ReductionTreePas class
• Use array_pod_sort instead of std::sort

[msifontes]

This comment was removed by msifontes.

[msifontes]

Fix Passes.h.inc dependency

[msifontes]

Resolve clang-tidy error

[msifontes]

NFC: Add ending namespace comment

[msifontes]

Move ReductionTreePass non-templated members to ReductionTreeUtils class in order to move some of the implementation to the .cpp file.

[jpienaar]

Nice, thanks

mlir/include/mlir/Reducer/Passes/FuncReducer.h

24

FuncReducer

30

children

mlir/include/mlir/Reducer/ReductionNode.h

21

I don't think this include is needed in this header

62

Link how? I'd have thought the parent linkage would be via construction.

mlir/include/mlir/Reducer/ReductionTreePass.h

82

Are we modifying Tester along the way? Seems like we could pass const ref version everyewhere

84

This description makes me think this shouldn't be a class member.

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

62

Nit: prefer (int)op.index() as that is more common here, else I'd say go for

int index = op.index();
if (index >= sectionSize*i && index < sectionSize*(i+1)) { ... }

67

So the functions are deleted but the symbol table is not changed, so what happens in the case where the function is invoked from a function not inside the deleted section? (would this be possible to tickle in a test? Perhaps one with 2 functions and on function calls the other).

mlir/tools/mlir-reduce/ReductionNode.cpp

54

s/bitcode/IR/ ? (or just s/bitcode//)

56

If you did out.os().tell() above, give you the same size? It seems to be counting chars written too which could avoid re-reading it.

104

Could this simply be a return? Also should this be lhs->get()->getSize() < rhs->get()->getSize()?

[msifontes]

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

67

I tested this by calling another function from the interesting function and the output was the interesting function along with the function it calls. I can look into dropping the calls in the OpReducer class I am working on which will allow for the removal of any function or MLIR dialect function like operation and would therefore replace this class.

[msifontes]

Apply requested changes

• Link children Reduction Nodes from constructor
• Use constant ref tester throughout
• Use out.os().tell() to measure files
• Simplify array_pod_sort return statement

[rriddle]

mlir/include/mlir/Reducer/ReductionTreePass.h

65

nit: You shouldn't need a break here, report_fatal_error doesn't return.

mlir/test/mlir-reduce/reduction-tree-pass.mlir

6

Can you add a few CHECK-NOTs to ensure the other functions aren't present?

9

Do you actually need anything inside of these functions for this test?

mlir/tools/mlir-reduce/ReductionNode.cpp

26

nit: Drop the trivial braces here.

50

test->isInteresting?

88

nit: Add braces here as the body is non-trivial.

90

The iterator would be invalidated after the erase, given that this is a vector.

mlir/tools/mlir-reduce/ReductionTreePass.cpp

24

You can access the raw operation list of a block via getOperations. That list can allow for erasing a range of operation, and splicing a range of operations from one list to another. Can you use that to simplify this?

36

nit: Spell out auto here and above.

mlir/tools/mlir-reduce/mlir-reduce.cpp

89

nit: Inline the use of this variable.

[msifontes]

Apply requested changes

• Simplify test and included CHECK-NOT tags
• Simplify updateGoldenModule utility
• Fix uninteresting variant removal

[jpienaar]

I think we can iterate from here, just a couple of things to fix and consider adding a few test cases for the edge cases (e.g., ops < variants, non multiple divisors)

mlir/include/mlir/Reducer/Passes/FuncReducer.h

2

s/Operation/Function/

29

Do you want to specialize these to correspond to what they do in this pass?

35

Does this just care about functions or any general op? Also does this need to be a class member vs a static function in the CC file?

mlir/include/mlir/Reducer/ReductionNode.h

58

Why is this needed on the public interface? Meaning, this seems like something that is called as part of "getInterestingVariants()" call. Could also be revised in follow up

84

Nit: I'd follow methods before data

mlir/include/mlir/Reducer/ReductionTreePass.h

2

Missing * c++ * part in header

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

33

Do you have a test where it doesn't evenly divide? (this would seem to round down and then we could miss terms on the end)

Also if we had 10 ops but 100 variants, this doesn't seem to work.

mlir/tools/mlir-reduce/ReductionNode.cpp

90

Instead of this, why not sort it based on (!interesting, size) pair and then just resizing the uninteresting end out?

[msifontes]

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

33

I have significantly refactored this so that the number of variants never exceeds the number of indices but it depends on the utilities I will be including in the next revision. I will be replacing this FunctionReducer file with the general OpReducer in the next revision which will be capable of performing the same reduction.

My thought process when it doesn't evenly split is to not remove any remainder Functions/indices that don't fit in the partitions since eventually variants will be created that attempt to remove these further down the tree. I could also look into including the removal of these remainder ops in the last variant generated at the level.

mlir/tools/mlir-reduce/ReductionNode.cpp

90

Implementing this approach.

[msifontes]

Apply requested changes

• Simplify the removal of uninteresting nodes
• Style and naming changes

[msifontes]

Fix header formatting warning

[msifontes]

NFC: clang format

mlir/include/mlir/CMakeLists.txt

 add_subdirectory(Conversion)
 add_subdirectory(Dialect)
 add_subdirectory(IR)
 add_subdirectory(Interfaces)
+add_subdirectory(Reducer)
 add_subdirectory(Transforms)

mlir/include/mlir/Reducer/CMakeLists.txt

+set(LLVM_TARGET_DEFINITIONS Passes.td)
+mlir_tablegen(Passes.h.inc -gen-pass-decls)
+add_public_tablegen_target(MLIRReducerIncGen)
+
+add_mlir_doc(Passes -gen-pass-doc ReducerPasses ./)

mlir/include/mlir/Reducer/PassDetail.h

+//===- PassDetail.h - Reducer 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 MLIR_REDUCER_PASSDETAIL_H
+#define MLIR_REDUCER_PASSDETAIL_H
+
+#include "mlir/Pass/Pass.h"
+
+namespace mlir {
+
+#define GEN_PASS_CLASSES
+#include "mlir/Reducer/Passes.h.inc"
+
+} // end namespace mlir
+
+#endif // MLIR_REDUCER_PASSDETAIL_H

mlir/include/mlir/Reducer/Passes.td

+//===-- 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_REDUCER_PASSES
+#define MLIR_REDUCER_PASSES
+
+include "mlir/Pass/PassBase.td"
+
+def ReductionTree : Pass<"reduction-tree", "ModuleOp"> {
+  let summary = "A general reduction tree pass for the MLIR Reduce Tool";
+  let constructor = "mlir::createReductionTreePass()";
+}
+
+#endif // MLIR_REDUCE_PASSES

mlir/include/mlir/Reducer/Passes/FuncReducer.h

+//===- FuncReducer.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 FuncReducer class. It defines a variant generator
+// method with the purpose of producing different variants by eliminating
+// operations from the  parent module.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_REDUCER_PASSES_FUNCREDUCER_H
+#define MLIR_REDUCER_PASSES_FUNCREDUCER_H
+
+#include "mlir/Reducer/ReductionNode.h"
+#include "mlir/Reducer/Tester.h"
+
+namespace mlir {
+
+/// The FuncReducer class defines a variant generator method that produces
+/// multiple variants by eliminating different operations from the
+/// parent module.
+class FuncReducer {
+public:
+  /// Generate variants by removing operations 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);
+
+private:
+  /// Iterate over the body of a module and return the number of operations.
+  static int countOps(ModuleOp module);
+};
+
+} // end namespace mlir
+
+#endif

mlir/include/mlir/Reducer/ReductionNode.h

+//===- ReductionNode.h - Reduction Node Implementation ----------*- 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 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_REDUCER_REDUCTIONNODE_H
+#define MLIR_REDUCER_REDUCTIONNODE_H
+
+#include <vector>
+
+#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);
+
+  /// Calculates and initializes the size and interesting values of the node.
+  void measureAndTest(const Tester *test);
+
+  /// Returns the module.
+  ModuleOp getModule() const { return module; }
+
+  /// Returns true if the size and interestingness have been calculated.
+  bool isEvaluated() const;
+
+  /// Returns the size in bytes of the module.
+  int getSize() const;
+
+  /// Returns true if the module exhibits the interesting behavior.
+  bool isInteresting() const;
+
+  /// Returns the pointer to a child variant by index.
+  ReductionNode *getVariant(unsigned long index) 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);
+
+private:
+  // This is the MLIR module of this variant.
+  ModuleOp module;
+
+  // This is true if the module has been evaluated and it exhibits the
+  // interesting behavior.
+  bool interesting;
+
+  // This indicates the number of characters in the printed module if the module
+  // has been evaluated.
+  int size;
+
+  // This indicates if the module has been evalueated (measured and tested).
+  bool evaluated;
+
+  // This points to the ReductionNode that was used as a starting point to
+  // create this variant. It is null if the reduction node is the root.
+  ReductionNode *parent;
+
+  // This points to the child variants that were created using this node as a
+  // starting point.
+  std::vector<std::unique_ptr<ReductionNode>> variants;
+
+  /// Link a child variant node.
+  void linkVariant(ReductionNode *newVariant);
+};
+
+} // end namespace mlir
+
+#endif

mlir/include/mlir/Reducer/ReductionTreePass.h

+//===- 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_REDUCER_REDUCTIONTREEPASS_H
+#define MLIR_REDUCER_REDUCTIONTREEPASS_H
+
+#include <vector>
+
+#include "PassDetail.h"
+#include "ReductionNode.h"
+#include "mlir/Reducer/Passes/FuncReducer.h"
+#include "mlir/Reducer/Tester.h"
+
+namespace mlir {
+
+/// 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);
+};
+
+/// 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 <typename Reducer, TraversalMode mode>
+class ReductionTreePass
+    : public ReductionTreeBase<ReductionTreePass<Reducer, mode>> {
+public:
+  ReductionTreePass(const Tester *test) : test(test) {}
+
+  ReductionTreePass(const ReductionTreePass &pass)
+      : root(new ReductionNode(pass.root->getModule().clone(), nullptr)),
+        test(pass.test) {}
+
+  /// Runs the pass instance in the pass pipeline.
+  void runOnOperation() override {
+    ModuleOp module = this->getOperation();
+    this->root = std::make_unique<ReductionNode>(module, nullptr);
+    ReductionNode *reduced;
+
+    switch (mode) {
+    case SinglePath:
+      reduced = singlePathTraversal();
+      break;
+    default:
+      llvm::report_fatal_error("Traversal method not currently supported.");
+      break;
+    }
+
+    ReductionTreeUtils utils;
+    utils.updateGoldenModule(module, reduced->getModule());
+  }
+
+private:
+  // Points to the root node in this reduction tree.
+  std::unique_ptr<ReductionNode> root;
+
+  // This object defines the variant generation at each level of the reduction
+  // tree.
+  Reducer reducer;
+
+  // 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 *currLevel = root.get();
+
+    while (true) {
+      reducer.generateVariants(currLevel, test);
+      currLevel->organizeVariants(test);
+
+      if (currLevel->variantsEmpty())
+        break;
+
+      currLevel = currLevel->getVariant(0);
+    }
+
+    return currLevel;
+  }
+};
+
+} // end namespace mlir
+
+#endif

mlir/include/mlir/Reducer/Tester.h

 //===- Tester.h -------------------------------------------------*- 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 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.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_REDUCER_TESTER_H
 #define MLIR_REDUCER_TESTER_H
 
 #include <vector>
 
 #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"
 
 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<std::string> 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);
-
-  /// 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; }
+  bool isInteresting(StringRef testCase) const;
 
 private:
   StringRef testScript;
   ArrayRef<std::string> testScriptArgs;
-  ModuleOp mostReduced;
 };
 
 } // end namespace mlir
 
-#endif
+#endif
 

mlir/lib/Reducer/Tester.cpp

 //===- Tester.cpp ---------------------------------------------------------===//
 //
 // 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 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.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Reducer/Tester.h"
 
 using namespace mlir;
 
 Tester::Tester(StringRef scriptName, ArrayRef<std::string> scriptArgs)
     : testScript(scriptName), testScriptArgs(scriptArgs) {}
 
 /// 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) {
+bool Tester::isInteresting(StringRef testCase) const {
 
   std::vector<StringRef> testerArgs;
   testerArgs.push_back(testCase);
 
   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,
       /*SecondsToWait=*/0, /*MemoryLimit=*/0, &errMsg);
 
   if (result < 0)
     llvm::report_fatal_error("Error running interestingness test: " + errMsg,
                              false);
 
   if (!result)
     return false;
 
   return true;
 }

mlir/test/mlir-reduce/failure-test.sh

+#!/bin/bash
+# Tests for the keyword "failure" in the stderr of the optimization pass
+mlir-opt $1 -test-mlir-reducer > /tmp/stdout.$$ 2>/tmp/stderr.$$
+
+if [ $? -ne 0 ] && grep 'failure' /tmp/stderr.$$; then
+  exit 1
+  #Interesting behavior
+else 
+  exit 0
+fi

mlir/test/mlir-reduce/reduction-tree-pass.mlir

+// UNSUPPORTED: -windows-
+// RUN: mlir-reduce %s -test %S/failure-test.sh | FileCheck %s
+// This input should be reduced by the pass pipeline so that only 
+// the @simple5 function remains as this is the shortest function 
+// containing the interesting behavior.
+// 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
+}

mlir/tools/mlir-reduce/CMakeLists.txt

set(LIBS
   MLIRPass
   MLIRReduce
   MLIRSupport
   MLIRTransforms
   MLIRTransformUtils
   )
 
 add_llvm_tool(mlir-reduce
+  Passes/FuncReducer.cpp
+  ReductionNode.cpp
+  ReductionTreePass.cpp
   mlir-reduce.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${MLIR_MAIN_INCLUDE_DIR}/mlir/Reducer
+
+  DEPENDS
+  MLIRReducerIncGen
   )
 
 target_link_libraries(mlir-reduce PRIVATE ${LIBS})
 llvm_update_compile_flags(mlir-reduce)
 
-mlir_check_all_link_libraries(mlir-reduce)
+mlir_check_all_link_libraries(mlir-reduce)
 

mlir/tools/mlir-reduce/Passes/FuncReducer.cpp

+//===- FuncReducer.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 FuncReducer 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/FuncReducer.h"
+#include "mlir/IR/Function.h"
+
+using namespace mlir;
+
+/// Return the number of function operations in the module's body.
+int FuncReducer::countOps(ModuleOp module) {
+  auto ops = module.getOps<FuncOp>();
+  return std::distance(ops.begin(), ops.end());
+}
+
+/// Generate variants by removing function operations from the module in the
+/// parent and link the variants as childs in the Reduction Tree Pass.
+void FuncReducer::generateVariants(ReductionNode *parent, const Tester *test) {
+  ModuleOp module = parent->getModule();
+  int numVariants = 2;
+  int opCount = countOps(module);
+  int sectionSize = opCount / numVariants;
+  std::vector<Operation *> 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<FuncOp>())
+      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 < numVariants; ++i) {
+    opsToRemove.clear();
+    ModuleOp moduleVariant = module.clone();
+
+    for (auto op : enumerate(moduleVariant.getOps<FuncOp>())) {
+      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;
+}

mlir/tools/mlir-reduce/ReductionNode.cpp

+//===- 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;
+
+/// Sets up the metadata and links the node to its parent.
+ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent)
+    : module(module), evaluated(false), parent(parent) {
+
+  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;
+  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 = out.os().tell();
+  interesting = (*test).isInteresting(filepath);
+  evaluated = true;
+}
+
+/// Returns true if the size and interestingness have been calculated.
+bool ReductionNode::isEvaluated() const { return evaluated; }
+
+/// Returns the size in bytes of the module.
+int ReductionNode::getSize() const { return size; }
+
+/// Returns true if the module exhibits the interesting behavior.
+bool ReductionNode::isInteresting() const { return interesting; }
+
+/// Returns the pointers to the child variants.
+ReductionNode *ReductionNode::getVariant(unsigned long index) const {
+  if (index < variants.size())
+    return variants[index].get();
+
+  return nullptr;
+}
+
+/// 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<ReductionNode> ptrVariant(newVariant);
+  variants.push_back(std::move(ptrVariant));
+}
+
+/// Sort the child variants and remove the uninteresting ones.
+void ReductionNode::organizeVariants(const Tester *test) {
+  for (auto &var : variants)
+    if (!var->isEvaluated())
+      var->measureAndTest(test);
+
+  // Remove uninteresting variants
+  auto it = variants.begin();
+  while (it != variants.end())
+    if (!(*it)->isInteresting()) {
+      variants.erase(it);
+    } else {
+      ++it;
+    }
+
+  llvm::array_pod_sort(variants.begin(), variants.end(),
+                       [](const auto *lhs, const auto *rhs) {
+                         return (lhs->get()->getSize(), rhs->get()->getSize());
+                       });
+}

mlir/tools/mlir-reduce/ReductionTreePass.cpp

+//===- 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) {
+  std::vector<Operation *> opsToDelete;
+
+  // Clear golden module body.
+  for (auto &op : golden)
+    if (!op.isKnownTerminator())
+      opsToDelete.push_back(&op);
+
+  for (auto *op : opsToDelete)
+    op->erase();
+
+  // Insert new operations into golden module.
+  opsToDelete.clear();
+  for (auto &op : reduced)
+    if (!op.isKnownTerminator())
+      golden.push_back(op.clone());
+}

mlir/tools/mlir-reduce/mlir-reduce.cpp

 //===----------------------------------------------------------------------===//
 
 #include <vector>
 
 #include "mlir/InitAllDialects.h"
 #include "mlir/Parser.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Pass/PassManager.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;
int main(int argc, char **argv) {
   mlir::MLIRContext context;
   mlir::OwningModuleRef moduleRef;
   context.allowUnregisteredDialects(true);
 
   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());
+  const Tester test(testFilename, testArguments);
+  const Tester *testRef = &test;
 
   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<ReductionTreePass<FuncReducer, SinglePath>>(testRef));
+
+  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;
-}
+}