Page MenuHomePhabricator

[RFC] Pattern matching on schedule trees.
Needs ReviewPublic

Authored by chelini on Jun 27 2018, 8:42 AM.

Details

Summary

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

Diff Detail

Event Timeline

chelini created this revision.Jun 27 2018, 8:42 AM

Thanks for the work,

Matching the MemoryAcesses would be interesting as well.

Consider adding some unittests.

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 added a comment.EditedJun 27 2018, 10:13 AM

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 added a subscriber: ftynse.Jun 28 2018, 2:28 AM
ftynse added inline comments.
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 added a comment.EditedJun 28 2018, 2:32 AM

@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.

Matching the MemoryAcesses would be interesting as well.

Could you describe which properties you want to match?

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 added inline comments.Jun 29 2018, 3:06 AM
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
}
This comment was removed by ftynse.

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.

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.

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.

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

Polly's matrix-matrix multiplication detection.

chelini updated this revision to Diff 153873.Jul 3 2018, 1:28 AM

Clean and update the patch as suggested.

chelini added inline comments.Jul 3 2018, 1:52 AM
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 added inline comments.Jul 3 2018, 5:26 AM
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.