Create ReductionTree and ReductionNode classes

[msifontes]

Summary

Implement the ReductionNode and ReductionTree data structures for the purpose of creating a framework to track the reductions within each pass in the MLIR Reduce tool.
This is a flexible framework that offers a general structure for the reduction implementation while allowing for different transformations to be integrated depending on the reduction pass objective.

[msifontes]

Delete commented out function call in mlir-reduce.cpp

[msifontes]

Formatting changes

[mehdi_amini]

mlir/include/mlir/Reducer/ReductionNode.h

19

(please fix the clang-tidy warning)

21

Is this needed in this header?

25

Same as above: is this include needed here?

53

Seems like this could return a const & to the member vector, and I think we wouldn't need the getVariant API (because getVariants()[i]would just work)

63

Could/should this be a vector of unique_ptr?

mlir/include/mlir/Reducer/ReductionTree.h

47

Can this be a unique_ptr?

51

(nit: fix clang-tidy naming)

mlir/tools/mlir-reduce/ReductionNode.cpp

93

Nit: replace at with subscript operator[]

mlir/tools/mlir-reduce/ReductionTree.cpp

41

You don't take ownership of the callback, so seems like a case to use llvm::function_ref instead of std::function

53

Side-note: I'm still unsure why the "tester" is the right place to keep track of the most reduced module)

[jpienaar]

mlir/include/mlir/Reducer/ReductionTree.h

33

As discussed offline, lets explore making this a module pass parameterized on a reducer class which has a generateVariants method and then can use pass manager.

[msifontes]

Apply requested changes

• Delete getVariant method
• Modify getVariants return type
• Formatting changes
• Replace std::function with llvm::function_ref

Will make the unique_ptr changes in the following update along with making the reduction tree a module pass and use the pass manager.

[msifontes]

mlir/tools/mlir-reduce/ReductionTree.cpp

53

Currently, the tester is the only object that gets passed from one pass to another in the reduction pipeline. The 'mostReduced' refers to the most reduced test case up to that point: it is used as the starting point in a pass and it is updated at the end of a pass if the reduction was effective. I agree it is somewhat counter intuitive so I am currently trying to refactor this.

mlir/include/mlir/Reducer/ReductionNode.h

+//===- ReductionNode.h - Reduction Node Implementation --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the reduction nodes which are used to track of the
+// metadata for a specific generated variant within a reduction pass and are the
+// building blocks of the reduction tree structure. A reduction tree is used to
+// keep track of the different generated variants throughout a reduction pass in
+// the MLIR Reduce tool.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_TOOLS_MLIRREDUCE_REDUCTIONNODE_H
+#define MLIR_TOOLS_MLIRREDUCE_REDUCTIONNODE_H
+
+#include "sys/stat.h"
+#include <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, Tester test);
+
+  /// Calculates and initializes the size and interesting values of the node.
+  void measureAndTest(Tester &test);
+
+  /// Returns the module.
+  ModuleOp getModule() const { return module; }
+
+  /// Returns the size in bytes of the module.
+  int getSize();
+
+  /// Returns true if the module exhibits the interesting behavior.
+  bool isInteresting();
+
+  /// Returns the pointers to the child variants.
+  const std::vector<ReductionNode *> &getVariants();
+
+  /// Returns true if the vector containing the child variants is empty.
+  bool variantsEmpty();
+
+private:
+  ModuleOp module;
+  bool interesting;
+  int size;
+  ReductionNode *parent;
+  std::vector<ReductionNode *> variants;
+
+  /// Link a child variant node.
+  void linkVariant(ReductionNode *newVariant);
+
+  /// Sort the vector containing the child variants by interestingness and size.
+  void sortVariants();
+};
+
+} // end namespace mlir
+
+#endif

mlir/include/mlir/Reducer/ReductionTree.h

+//===- 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 <vector>
+
+#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<void(ReductionNode *parent, Tester &test)>
+          generateVariants);
+
+private:
+  ReductionNode *root;
+  Tester *test;
+
+  /// Recursively delete the reduction nodes in the reduction tree
+  void destructTree(ReductionNode *node);
+};
+
+} // end namespace mlir
+
+#endif

mlir/lib/Reducer/Tester.cpp

 bool Tester::isInteresting(StringRef testCase) {
 
   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/tools/mlir-reduce/CMakeLists.txt

set(LIBS
   MLIRPass
   MLIRReduce
   MLIRSupport
   MLIRTransforms
   MLIRTransformUtils
   )
 
 add_llvm_tool(mlir-reduce
+  ReductionNode.cpp
+  ReductionTree.cpp
   mlir-reduce.cpp
   )
 
 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/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;
+
+/// Defines the sorting order of two ReductionNodes by interestingness and size.
+static bool sortFunction(ReductionNode *a, ReductionNode *b) {
+  // Sort nodes by interestingness.
+  bool aInteresting = a->isInteresting();
+  bool bInteresting = b->isInteresting();
+
+  if (aInteresting && !bInteresting)
+    return true;
+
+  if (!aInteresting && bInteresting)
+    return false;
+
+  // Sort nodes by size.
+  return (a->getSize() < b->getSize());
+}
+
+/// Returns the size in bytes of a file.
+static int measureFile(SmallString<128> filepath) {
+  struct stat stats;
+  int rc = stat(filepath.c_str(), &stats);
+  if (rc != 0)
+    llvm::report_fatal_error("Error measuring the file size" + filepath);
+
+  return stats.st_size;
+}
+
+/// Sets up the metadata and links the node to its parent.
+ReductionNode::ReductionNode(ModuleOp module, ReductionNode *parent,
+                             Tester test)
+    : module(module), parent(parent) {
+
+  this->measureAndTest(test);
+
+  // Link variant to parent node
+  if (parent != nullptr)
+    parent->linkVariant(this);
+}
+
+/// Calculates and updates the size and interesting values of the module.
+void ReductionNode::measureAndTest(Tester &test) {
+
+  SmallString<128> filepath;
+  int fd;
+
+  // Print module to temprary file.
+  std::error_code ec =
+      llvm::sys::fs::createTemporaryFile("mlir-reduce", "mlir", fd, filepath);
+
+  if (ec)
+    llvm::report_fatal_error("Error making unique filename: " + ec.message());
+
+  llvm::ToolOutputFile out(filepath, fd);
+  module.print(out.os());
+  out.os().close();
+
+  if (out.os().has_error())
+    llvm::report_fatal_error("Error emitting bitcode to file '" + filepath);
+
+  size = measureFile(filepath);
+  interesting = test.isInteresting(filepath);
+}
+
+/// Returns the size in bytes of the module.
+int ReductionNode::getSize() { return size; }
+
+/// Returns true if the module exhibits the interesting behavior.
+bool ReductionNode::isInteresting() { return interesting; }
+
+/// Returns the pointers to the child variants.
+const std::vector<ReductionNode *> &ReductionNode::getVariants() {
+  return variants;
+}
+
+/// Returns true if the child variants vector is empty.
+bool ReductionNode::variantsEmpty() { return variants.empty(); }
+
+/// Link a child variant node.
+void ReductionNode::linkVariant(ReductionNode *newVariant) {
+  variants.push_back(newVariant);
+  this->sortVariants();
+}
+
+/// Sort the vector containing the child variants by interestingness and size.
+void ReductionNode::sortVariants() {
+  std::sort(variants.begin(), variants.end(), sortFunction);
+}

mlir/tools/mlir-reduce/ReductionTree.cpp

+//===- 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<ReductionNode *> 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<void(ReductionNode *parent, Tester &test)>
+        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];
+  }
+}

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

int main(int argc, char **argv) {
   if (!test.isInteresting(inputFilename))
     llvm::report_fatal_error(
         "Input test case does not exhibit interesting behavior");
 
   test.getMostReduced().print(output->os());
   output->keep();
 
   return 0;
-}
+}