[RFC] Pattern matching on schedule trees.

[chelini]

Summary

Ported in Polly the library for pattern matching on schedule tree available at https://github.com/PollyLabs/islutils.

[Meinersbur]

Thanks for the work,

Matching the MemoryAcesses would be interesting as well.

Consider adding some unittests.

[philip.pfaffe]

I like the idea! The API needs to be polished a bit I think.

Some time back I prototyped an approach to this as well, but never got around to using/submitting it. I'll paste my code later, since I liked the API at that time.

[philip.pfaffe]

This was how my API worked:

#include "isl/isl-noexceptions.h"
#include <vector>

enum class schedule_node_type {
  error = -1,
  band,
  context,
  domain,
  expansion,
  extension,
  filter,
  leaf,
  guard,
  mark,
  sequence,
  set,
  any
};

struct Matcher {
  /* implicit */ Matcher(schedule_node_type T) : MatchedType(T) {}
  Matcher(schedule_node_type T, Matcher &&Inner)
      : MatchedType(T), InnerMatchers({Inner}) {}
  template <typename... MatcherTs>
  Matcher(schedule_node_type T, MatcherTs &&... Matchers)
      : Matcher(T, {std::forward<MatcherTs>(Matchers)...}) {}
  Matcher(schedule_node_type T, std::initializer_list<Matcher> Inner)
      : MatchedType(T), InnerMatchers(Inner) {}

  isl::schedule_node match();

  template <typename Callable> isl::schedule_node match(Callable &&);

  schedule_node_type MatchedType;
  std::vector<Matcher> InnerMatchers;
};

int main() {
  {
    Matcher M{schedule_node_type::domain,
              {schedule_node_type::sequence,
               {schedule_node_type::filter, {schedule_node_type::filter}},
               {schedule_node_type::filter, {schedule_node_type::filter}}}};
  }
}

I prefer not using macros. With this implementation you get only one callback per full match, not per matched subtree, but I felt like this is all I needed.

[ftynse]

include/polly/ScheduleOptimizer.h

18

I would really appreciate if you mention the author(s) of the original code. It is distributed under an MIT license which, although open source, requires the license and copyright information to be preserved if you distribute copies or substantial portions of the code... I'm fine contributing it if you ask me explicitly, but please don't claim authorship on the code you did not write.

[grosser]

@ftynse, the source is referenced in the patch summary. If we commit such a patch to Polly, we must make we have your permission to contribute it under the LLVM license and obviously need to acknowledge the source. For now, I asked Lorenzo to push the code as RFC to allow others to see how it would be used. This already sparked a comment from Philip and will likely spark further discussions on how to extend the interface. Thanks for commenting.

I am not sure where you would prefer to have discussions on such a matcher. Probably an (organized?) mix of phabricator here and the github repo where you pushed the API could work.

[ftynse]

Matching the MemoryAcesses would be interesting as well.

Could you describe which properties you want to match?

[ftynse]

This was how my API worked:

I don't know when and how mainline isl will provide maintained C++ bindings, but the idea there is that enum isl_schedule_node_type will not be visible from C++. This is essentially a trick to have "inheritance" on node types in C. Practically, isl is going towards individual node types being specific classes that inherit from the generic schedule_node one. They are likely to feature isa<>-style interface. We can declare a local enum and use it to construct matchers though. The trade-off is that the matchers will not scale to non-structural properties. If we something closer to AST matchers, we will eventually have structure, traversal and property matchers, which are better off with functions or object constructors.

I prefer not using macros.

Between macros and almost identical copy-pasted code, I chose macros. Arguably, it can be rewritten with more templates where the almost-identical part is a one-liner. If the inheritance-based interface to trees is provided, we can think of something like

match<isl::schedule_node_domain>(
  match<isl::schedule_node_context>(
    match<isl::schedule_node_band>()))

although it does look more verbose.

With this implementation you get only one callback per full match, not per matched subtree, but I felt like this is all I needed.

The callbacks are intended to control the matching itself, not for actions on subtrees. Although one can use them for actions, I would discourage that. In practice, I often needed to match more than just a node type: filters involving specific statements, mapping to gpu blocks, marks with specific ids, etc. While it is possible to first collect all subtrees with the matching structures, and then filter them for the desired properties, it looks easier to not match such subtrees in the first place. When the desired properties are well-defined, one can build a higher-level API around these callbacks, like

auto isKernel = [](isl::schedule_node mark) {
  return mark.node_mark_get_id() == isl::id(mark.get_ctx(), "kernel");
};
auto matcher =
    mark(isKernel,
      context(
        band()));

or even

template <typename... Args>
Matcher kernel(Args... args) {
  return mark(isKernel, args...);
}
auto matcher = 
    kernel(
      conext(
        band()));

[ftynse]

include/polly/ScheduleOptimizer.h

50

It depends on what you need exactly. Just one node without specifying a type? Does that mean that the node _does_ exist or _may_ exist? Do you want to skip over multiple levels of the tree? Do you want to skip over multiple siblings? One can go shell-like wildcard way with ? and *. Or some flavor of regular expressions, but this quickly goes out of hand. I'd like to see examples of what needs to be expressed before taking a decision. My feeling after using different flavors of schedule trees is that you probably need some traversal matchers like hasSibling or hasDescendant

53

set is actually an tricky one, because it explicitly says the order of children does not matter. This implementation does not account for that, not sure if it should

include/polly/matchers-inl.h

14

about what?

lib/Transform/ScheduleOptimizer.cpp

1713

The idea is to use a scoped using namespace to make it less verbose. Optionally, add trailing comments to tell clang-format to leave the formatting alone and reflect the tree structure.

c++
{
  using namespace matchers;
  auto matcher =
      domain(                    // d
        sequence(              // s
          filter(                     // f
            band()),                // b
          filter(                     // f
            band())));              // b
}

[ftynse]

This comment was removed by ftynse.

[philip.pfaffe]

I don't know when and how mainline isl will provide maintained C++ bindings, but the idea there is that enum isl_schedule_node_type will not be visible from C++. This is essentially a trick to have "inheritance" on node types in C. Practically, isl is going towards individual node types being specific classes that inherit from the generic schedule_node one. They are likely to feature isa<>-style interface. We can declare a local enum and use it to construct matchers though.

Is there a roadmap or RFC for that? I think that's a great idea.

The trade-off is that the matchers will not scale to non-structural properties. If we something closer to AST matchers, we will eventually have structure, traversal and property matchers, which are better off with functions or object constructors.

I'm not sure if we're going to need something as powerful as AST matchers. I usually prefer using a low-tech solution first and upgrade once I know with certainty what I actually need out of my system.

Between macros and almost identical copy-pasted code, I chose macros.

This wasn't criticism about your use of macros, but that the code requires macros.

The callbacks are intended to control the matching itself, not for actions on subtrees. Although one can use them for actions, I would discourage that.

This absolutely makes sense, but I didn't get that from the original summary. This then also satisfies Micheal's wish for a mechanism to match memory patterns. You can just do that in the callbacks.

My interface above can be easily extended to also incorporate Callbacks in the constructor. I don't have a categorical aversion against the interface proposed in the RFC, but I find the enum-based API much more readable.

[ftynse]

For now, I asked Lorenzo to push the code as RFC to allow others to see how it would be used. This already sparked a comment from Philip and will likely spark further discussions on how to extend the interface.

It's better if we don't play the relay game and have people send comments on my code to me.

I am not sure where you would prefer to have discussions on such a matcher. Probably an (organized?) mix of phabricator here and the github repo where you pushed the API could work.

Absolutely not a mix of two things. In this case, we would spread out information and keep repeating the same things over and over again. Whatever going into my inbox (that is, CCing me directly) is fine.

[ftynse]

Is there a roadmap or RFC for that? I think that's a great idea.

No, I don't think there is anything like that in isl.

I'm not sure if we're going to need something as powerful as AST matchers. I usually prefer using a low-tech solution first and upgrade once I know with certainty what I actually need out of my system.

We agree on that. If somebody has concrete usecases now, that would be helpful though.

[Meinersbur]

In D48651#1147701, @ftynse wrote:

If somebody has concrete usecases now, that would be helpful though.

Polly's matrix-matrix multiplication detection.

[chelini]

Clean and update the patch as suggested.

[chelini]

include/polly/ScheduleOptimizer.h

50

Hi, Indeed hasSibling or hasDescendant would be really useful. In the case of matrix-multiplication suggested by Michael you may, for example, have two different schedule trees:

-Domain
--Band {/*mat mul op */}
---Leaf

For the simple case without initialization or

-Domain
--Sequence
---Filter
----Band
-----Leaf
---Filter
----Band
-----Leaf
---Filter
----Band {/*mat mul op */}
-----Leaf

For the case with initialization. A possible matchers would look like as Domain(hasDescendant(Band())). Of course, band should have specific properties related to the matmul operation. Do you already have in mind a possible implementation for these traversal matchers?

[ftynse]

include/polly/ScheduleOptimizer.h

50

I do have a possible implementation in mind. What I don't see is how to make it usable in this case. With a pure structural matcher,

domain(
  band(isMatMul))

you have a guaranteed structure in case of a match. That is, you can write

auto matcher = domain(band([](isl::schedule_node n) { return true; /*check if matmul*/ }));
if (ScheduleNodeMatcher::isMatching(matcher, node)) {
  auto n = node.get_child(0);  // guaranteed to produce a non-null node
  // n is guaranteed to be a band node here
  n.band_tile(...);  // no need for extra cheks
}

With traversals, you don't get such guarantee: the descendant you are interested in may be arbitrarily deep and you need to somehow reach it to do a transformation. One way to go would be to return some collection of nodes that matched with a predefined structure. Another possibility would be to do that transformation in the callback passed to the matcher, but I'm not convinced it is the right approach, I think matchers are for finding stuff.

In this particular example, I don't see why do you want to match the domain... It's always at the root anyway. But you seem to need to anchor the matcher at leafs.

include/polly/ScheduleOptimizer.h

 //===- polly/ScheduleOptimizer.h - The Schedule Optimizer -------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCHEDULEOPTIMIZER_H
 #define POLLY_SCHEDULEOPTIMIZER_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "isl/isl-noexceptions.h"
+#include "polly/ScopInfo.h"
+
+/*
+* Taken from: https://github.com/PollyLabs/islutils
+* Author: Alex (https://ozinenko.com/)
+* \brief Structural matchers on schedule trees.
+*
+* A matcher is an object that captures the structure of schedule trees.
+* Conceptually, a matcher is a tree itself where every node is assigned a node
+* type.  The matcher class provides functionality to detect if a subtree in
+* the schedule tree has the same structure, that is the same types of nodes
+* and parent/child relationships.  Contrary to regular trees, matchers can be
+* constructed using nested call syntax omitting the details about the content
+* of nodes.  For example,
+*
+* ```
+* auto m = domain(
+*            context(
+*              sequence(
+*                filter(),
+*                filter())));
+* ```
+*
+* matches a subtree that starts at a domain node, having context as only
+* child, which in turn has a sequence as only child node, and the latter has
+* two filter children.  The structure is not anchored at any position in the
+* tree: the first node is not necessarily the tree root, and the innermost
+* node may have children of their own.
+*/
+
+namespace matchers {
+class ScheduleNodeMatcher;
+
+/*
+* These functions construct a structural matcher on the schedule tree by
+* specifying the type of the node (indicated by the function name).  They take
+* other matchers as arguments to describe the children of the node.  Depending
+* on the node type, functions take a single child matcher or an arbitrary
+* number thereof.  Sequence and set matcher builders take multiple children as
+* these types of node are the only ones that can have more than one child.
+* Additionally, all constructors are overloaded with an extra leading argument
+* to store a callback function for finer-grain matching.  This function is
+* called on the node before attempting to match its children.  It is passed
+* the node itself and returns true if the matching may continue and false if
+* it should fail immediately without processing the children.  When no child
+* matchers are provided, the node is allowed to have zero or more children.
+*/
+
+ScheduleNodeMatcher sequence();
+
+template <typename Arg, typename... Args,
+          typename = typename std::enable_if<
+              std::is_same<typename std::remove_reference<Arg>::type,
+                           ScheduleNodeMatcher>::value>::type>
+ScheduleNodeMatcher sequence(Arg, Args... args);
+
+template <typename... Args>
+ScheduleNodeMatcher sequence(std::function<bool(isl::schedule_node)> callback,
+                             Args... args);
+
+ScheduleNodeMatcher set();
+
+template <typename Arg, typename... Args,
+          typename = typename std::enable_if<
+              std::is_same<typename std::remove_reference<Arg>::type,
+                           ScheduleNodeMatcher>::value>::type>
+ScheduleNodeMatcher set(Arg, Args... args);
+
+template <typename... Args>
+ScheduleNodeMatcher set(std::function<bool(isl::schedule_node)> callback,
+                        Args... args);
+
+ScheduleNodeMatcher band();
+ScheduleNodeMatcher band(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher band(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher band(std::function<bool(isl::schedule_node)> callback,
+                         ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher context();
+ScheduleNodeMatcher context(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher context(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher context(std::function<bool(isl::schedule_node)> callback,
+                            ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher domain();
+ScheduleNodeMatcher domain(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher domain(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher domain(std::function<bool(isl::schedule_node)> callback,
+                           ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher extension();
+ScheduleNodeMatcher extension(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher extension(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher extension(std::function<bool(isl::schedule_node)> callback,
+                              ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher filter();
+ScheduleNodeMatcher filter(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher filter(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher filter(std::function<bool(isl::schedule_node)> callback,
+                           ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher guard();
+ScheduleNodeMatcher guard(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher guard(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher guard(std::function<bool(isl::schedule_node)> callback,
+                          ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher mark();
+ScheduleNodeMatcher mark(ScheduleNodeMatcher &&child);
+ScheduleNodeMatcher mark(std::function<bool(isl::schedule_node)> callback);
+ScheduleNodeMatcher mark(std::function<bool(isl::schedule_node)> callback,
+                         ScheduleNodeMatcher &&child);
+
+ScheduleNodeMatcher leaf();
+
+class ScheduleNodeMatcher {
+#define DECL_FRIEND_TYPE_MATCH(name)                                           \
+  friend ScheduleNodeMatcher name();                                           \
+  template <typename... Args>                                                  \
+  friend ScheduleNodeMatcher name(std::function<bool(isl::schedule_node)>,     \
+                                  Args...);                                    \
+  template <typename Arg, typename... Args, typename>                          \
+  friend ScheduleNodeMatcher name(Arg, Args...);
+  DECL_FRIEND_TYPE_MATCH(sequence)
+  DECL_FRIEND_TYPE_MATCH(set)
+
+#undef DECL_FRIEND_TYPE_MATCH
+
+#define DECL_FRIEND_TYPE_MATCH(name)                                           \
+  friend ScheduleNodeMatcher name();                                           \
+  friend ScheduleNodeMatcher name(ScheduleNodeMatcher &&);                     \
+  friend ScheduleNodeMatcher name(std::function<bool(isl::schedule_node)>);    \
+  friend ScheduleNodeMatcher name(std::function<bool(isl::schedule_node)>,     \
+                                  ScheduleNodeMatcher &&);
+
+  DECL_FRIEND_TYPE_MATCH(band)
+  DECL_FRIEND_TYPE_MATCH(context)
+  DECL_FRIEND_TYPE_MATCH(domain)
+  DECL_FRIEND_TYPE_MATCH(extension)
+  DECL_FRIEND_TYPE_MATCH(filter)
+  DECL_FRIEND_TYPE_MATCH(guard)
+  DECL_FRIEND_TYPE_MATCH(mark)
+  DECL_FRIEND_TYPE_MATCH(leaf)
+
+#undef DECL_FRIEND_TYPE_MATCH
+
+public:
+  bool isMatching(const ScheduleNodeMatcher &matcher, isl::schedule_node node);
+  void printMatcher(raw_ostream &OS, const ScheduleNodeMatcher &matcher, int indent) const;
+
+private:
+  isl_schedule_node_type current_;
+  //TODO: SmallVector ??
+  std::vector<ScheduleNodeMatcher> children_;
+  std::function<bool(isl::schedule_node)> nodeCallback_;
+};
+
+#include "matchers-inl.h"
+
+} // namespace matchers
 
 namespace llvm {
 
 class TargetTransformInfo;
 } // namespace llvm
 
 struct isl_schedule_node;
 

include/polly/matchers-inl.h

+//#define DEBUG_TYPE "matchers-inl"
+
+#include <type_traits>
+#include <assert.h>
+#include "llvm/Support/Debug.h"
+
+namespace {
+template <typename Arg, typename... Args>
+inline typename std::enable_if<sizeof...(Args) != 0, void>::type
+appendVarargToVector(std::vector<Arg> &vec, Args... args) {
+  for(auto& a : {typename std::common_type<Args...>::type(args)...})
+  {
+    vec.push_back(a);
+  }
+}
+
+template <typename Arg, typename... Args>
+inline typename std::enable_if<sizeof...(Args) == 0, void>::type
+appendVarargToVector(std::vector<Arg> &vec, Args...) {
+  (void)vec;
+}
+
+template <typename R, typename... Args>
+std::vector<R> varargToVector(Args... args) {
+  std::vector<R> result;
+  appendVarargToVector<R, Args...>(result, args...);
+  return result;
+}
+} // namespace
+
+/* Definitions for schedule tree matcher factory functions ********************/
+#define DEF_TYPE_MATCHER(name, type)                                           \
+  template <typename Arg, typename... Args, typename>                          \
+  inline ScheduleNodeMatcher name(Arg arg, Args... args) {                     \
+    ScheduleNodeMatcher matcher;                                               \
+    matcher.current_ = type;                                                   \
+    matcher.children_ = varargToVector<ScheduleNodeMatcher>(arg, args...);     \
+    return matcher;                                                            \
+  }                                                                            \
+  inline ScheduleNodeMatcher name() {                                          \
+    ScheduleNodeMatcher matcher;                                               \
+    matcher.current_ = type;                                                   \
+    return matcher;                                                            \
+  }                                                                            \
+                                                                               \
+  template <typename... Args>                                                  \
+  inline ScheduleNodeMatcher name(                                             \
+      std::function<bool(isl::schedule_node)> callback, Args... args) {        \
+    ScheduleNodeMatcher matcher = name(std::forward<Args>(args)...);           \
+    matcher.nodeCallback_ = callback;                                          \
+    return matcher;                                                            \
+  }
+
+DEF_TYPE_MATCHER(sequence, isl_schedule_node_sequence)
+DEF_TYPE_MATCHER(set, isl_schedule_node_set)
+
+#undef DEF_TYPE_MATCHER
+
+#define DEF_TYPE_MATCHER(name, type)                                           \
+  inline ScheduleNodeMatcher name() {                                          \
+    ScheduleNodeMatcher matcher;                                               \
+    matcher.current_ = type;                                                   \
+    return matcher;                                                            \
+  }                                                                            \
+                                                                               \
+  inline ScheduleNodeMatcher name(ScheduleNodeMatcher &&child) {               \
+    ScheduleNodeMatcher matcher;                                               \
+    matcher.current_ = type;                                                   \
+    matcher.children_.emplace_back(child);                                     \
+    return matcher;                                                            \
+  }                                                                            \
+                                                                               \
+  inline ScheduleNodeMatcher name(                                             \
+      std::function<bool(isl::schedule_node)> callback) {                      \
+    ScheduleNodeMatcher matcher = name();                                      \
+    matcher.nodeCallback_ = callback;                                          \
+    return matcher;                                                            \
+  }                                                                            \
+                                                                               \
+  inline ScheduleNodeMatcher name(                                             \
+      std::function<bool(isl::schedule_node)> callback,                        \
+      ScheduleNodeMatcher &&child) {                                           \
+    ScheduleNodeMatcher matcher = name(std::move(child));                      \
+    matcher.nodeCallback_ = callback;                                          \
+    return matcher;                                                            \
+  }
+
+DEF_TYPE_MATCHER(band, isl_schedule_node_band)
+DEF_TYPE_MATCHER(context, isl_schedule_node_context)
+DEF_TYPE_MATCHER(domain, isl_schedule_node_domain)
+DEF_TYPE_MATCHER(extension, isl_schedule_node_extension)
+DEF_TYPE_MATCHER(filter, isl_schedule_node_filter)
+DEF_TYPE_MATCHER(guard, isl_schedule_node_guard)
+DEF_TYPE_MATCHER(mark, isl_schedule_node_mark)
+DEF_TYPE_MATCHER(leaf, isl_schedule_node_leaf)
+
+#undef DEF_TYPE_MATCHER

lib/Transform/ScheduleOptimizer.cpp

 
 STATISTIC(FirstLevelTileOpts, "Number of first level tiling applied");
 STATISTIC(SecondLevelTileOpts, "Number of second level tiling applied");
 STATISTIC(RegisterTileOpts, "Number of register tiling applied");
 STATISTIC(PrevectOpts, "Number of strip-mining for prevectorization applied");
 STATISTIC(MatMulOpts,
           "Number of matrix multiplication patterns detected and optimized");
 
+namespace matchers {
+
+void ScheduleNodeMatcher::printMatcher(raw_ostream &OS, 
+      const ScheduleNodeMatcher &matcher, int indent) const {
+ 
+  switch(matcher.current_) {
+    case isl_schedule_node_sequence:
+      OS.indent(indent) << "Sequence Node\n";
+      break;
+    case isl_schedule_node_set:
+      OS.indent(indent) << "Set Node\n";
+      break;
+    case isl_schedule_node_band:
+      OS.indent(indent) << "Band Node\n";
+      break;
+    case isl_schedule_node_context:
+      OS.indent(indent) << "Context Node\n";
+      break;
+    case isl_schedule_node_domain:
+      OS.indent(indent) << "Domain Node\n";
+      break;
+    case isl_schedule_node_extension:
+      OS.indent(indent) << "Extension Node\n";
+      break;
+    case isl_schedule_node_filter:
+      OS.indent(indent) << "Filter Node\n";
+      break;
+    case isl_schedule_node_guard:
+      OS.indent(indent) << "Guard Node\n";
+      break;
+    case isl_schedule_node_mark:
+      OS.indent(indent) << "Mark Node\n";
+      break;
+    case isl_schedule_node_leaf:
+      OS.indent(indent) << "Leaf Node\n";
+      break;
+    default:
+      OS.indent(indent) << "ND\n";
+  }
+
+  if(matcher.children_.empty()) {
+    return;
+  }
+ 
+  int n_children_ = matcher.children_.size();
+  for(int i = 0; i < n_children_; ++i) {
+    printMatcher(OS, matcher.children_[i], indent+2);
+  }
+
+  OS << "\n";
+}
+
+
+bool ScheduleNodeMatcher::isMatching(const ScheduleNodeMatcher &matcher,
+                                     isl::schedule_node node) {
+  if (!node.get()) {
+    return false;
+  }
+
+  if (matcher.current_ != isl_schedule_node_get_type(node.get())) {
+    return false;
+  }
+
+  if (matcher.nodeCallback_ && !matcher.nodeCallback_(node)) {
+    return false;
+  }
+
+  if (matcher.children_.size() == 0) {
+    return true;
+  }
+
+  size_t nChildren =
+      static_cast<size_t>(isl_schedule_node_n_children(node.get()));
+  if (matcher.children_.size() != nChildren) {
+    return false;
+  }
+
+  for (size_t i = 0; i < nChildren; ++i) {
+    if (!isMatching(matcher.children_.at(i), node.child(i))) {
+      return false;
+    }
+  }
+  return true;
+}
+
+} // namespace matchers
+
 /// Create an isl::union_set, which describes the isolate option based on
 /// IsolateDomain.
 ///
 /// @param IsolateDomain An isl::set whose @p OutDimsNum last dimensions should
 ///                      belong to the current band node.
 /// @param OutDimsNum    A number of dimensions that should belong to
 ///                      the current band node.
 static isl::union_set getIsolateOptions(isl::set IsolateDomain,
isl_schedule_node_foreach_descendant_top_down(
           break;
         }
 
         return isl_bool_true;
       },
       &Version);
 }
 
+static bool handlerMatcher(isl::schedule_node Node) {
+  LLVM_DEBUG(dbgs() << "hello matchers\n");
+  return true;
+}
+
 bool IslScheduleOptimizer::runOnScop(Scop &S) {
   // Skip SCoPs in case they're already optimised by PPCGCodeGeneration
   if (S.isToBeSkipped())
     return false;
 
   // Skip empty SCoPs but still allow code generation as it will delete the
   // loops present but not needed.
   if (S.getSize() == 0) {
LLVM_DEBUG({
     P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);
     P = isl_printer_print_schedule(P, Schedule.get());
     auto *str = isl_printer_get_str(P);
     dbgs() << "NewScheduleTree: \n" << str << "\n";
     free(str);
     isl_printer_free(P);
   });
 
+{
+  using namespace matchers;
+  // try different constructors for matchers. (to be removed)
+  auto MatcherObj = domain(sequence(filter(band()),filter(band())));
+  MatcherObj.printMatcher(llvm::dbgs(), MatcherObj, 2);
+  MatcherObj = band(sequence(filter()));
+  MatcherObj.printMatcher(llvm::dbgs(), MatcherObj, 2);
+  MatcherObj = band(set(filter()));
+  MatcherObj.printMatcher(llvm::dbgs(), MatcherObj, 2);
+  MatcherObj = band(sequence());
+  MatcherObj.printMatcher(llvm::dbgs(), MatcherObj, 2);
+  MatcherObj = domain(context(filter()));
+  MatcherObj.printMatcher(llvm::dbgs(), MatcherObj, 2);
+  // callback (to be removed)
+  bool isAMatch = false;
+  isl::schedule_node Root = Schedule.get_root();
+  MatcherObj = domain(sequence(handlerMatcher));
+  isAMatch = MatcherObj.isMatching(MatcherObj,Root);
+  LLVM_DEBUG(dbgs() << "Match :=" << isAMatch << "\n");
+  MatcherObj = domain(handlerMatcher);
+  isAMatch = MatcherObj.isMatching(MatcherObj,Root);
+  LLVM_DEBUG(dbgs() << "Match :=" << isAMatch << "\n");
+  // callback plus child (to be removed)
+  MatcherObj = domain(handlerMatcher,band());
+  isAMatch = MatcherObj.isMatching(MatcherObj,Root);
+  LLVM_DEBUG(dbgs() << "Match :=" << isAMatch << "\n");
+}
+  
+
   Function &F = S.getFunction();
   auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   const OptimizerAdditionalInfoTy OAI = {TTI, const_cast<Dependences *>(&D)};
   auto NewSchedule = ScheduleTreeOptimizer::optimizeSchedule(Schedule, &OAI);
   walkScheduleTreeForStatistics(NewSchedule, 2);
 
   if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule))
     return false;