[DAG] SDPatternMatch - add matchers for reassociatable binops

[RKSimon]

For binop opcodes that are commutable + reassociatable (ISD::AND/OR/OR/ADD/MUL etc.) we need support for variable args matchers that can match operands that might be in different locations in a dependency chain:

e.g.

(add X, (add Y, Z))
(add (add X, Y), (add Z, W))
(add X, (add Y, (add Z, W)))

SDValue X, Y, Z, W;
m_Add(m_Value(X), m_Value(Y), m_Value(Z))
m_Add(m_Value(X), m_Value(Y), m_Value(Z), m_Value(W))

We probably only need the 3 and 4 argument patterns for this initial ticket.

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

For binop opcodes that are commutable + reassociatable (ISD::AND/OR/OR/ADD/MUL etc.) we need support for a variable args matchers that can match operands that might be in different locations in a dependency chain:

e.g.

(add X, (add Y, Z))
(add (add X, Y), (add Z, W))
(add X, (add Y, (add Z, W)))

SDValue X, Y, Z, W;
m_Add(m_Value(X), m_Value(Y), m_Value(Z))
m_Add(m_Value(X), m_Value(Y), m_Value(Z), m_Value(W))

[RKSimon]

@mshockwave Any preference/suggestions on how this is implemented?

[mshockwave]

(for simplicity, let's use ADD for the discussion here)
I believe you're not talking about supporting only binding SDValues via m_Value but something more generic like m_Add(A, B, C, D) where A, B, C, and D can be any sub-pattern.
Since we're going to take reassociate into consideration, I think the most proper way would be collecting all the non-ADD SDValue first, before matching them with the provided sub-patterns. This is basically what the ReassociatePass does as well, in which case they call it "linearizing" the expression.

At first I thought we can implement the SDValue collection logics by recursively decompose the original m_Add into smaller SDPatternMatch patterns. But since the expression is a tree, to do so we have to account for every single possible shapes of the tree, which doesn't scale well because the number of such combinations will grow exponentially. For instance, for four operands like m_Add(X, Y, Z, W) where X, Y, Z, W are not the provided sub-patterns but the "collector" patterns (i.e. m_Value), we have to check m_Add(X, m_Add(Y, Z, W)), m_Add(m_Add(X, Y), m_Add(Z, W)), and m_Add(m_Add(X, Y, Z), W). With m_c_Add (the commutative version) we can cut this number from 3 to 2, but still, I don't think it will scale well.

I think it might be easier to just do a simple DFS walk on the tree and collect all the non-ADD SDValues.

With the collected (non-ADD) SDValues, now comes the matching phase. I think the tricky cases here would be that a single SDValue matches multiple patterns (on the other hand, the situation is a lot easier when each SDValue only matches zero or one pattern). And you certainly don't want to let it pass when each of the 5 SDValues matches the same 2 patterns. You might need to do some bookkeeping.

[GrumpyPigSkin]

Hi,

I am a completely new contributor but I thought I would give this a go (without being assigned). I have had a look around the code base taken onboard the comments made by @mshockwave and looked at walking an SDValue. I came up with this naive solution based on other matches I have seen in the code and thought I would check if this is even along the right lines:

template <auto op_code>
auto collectLeaves(SDValue V, SmallVector<SDValue> &Leaves) -> void {
  SDNode *N = V.getNode();
  if (N->getOpcode() == op_code) {
    for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
      collectLeaves<op_code>(N->getOperand(i), Leaves);
    }
  } else {
    Leaves.push_back(V);
  }
}

template <bool sorting = false>
auto matchAddOps(SDNode *N, SDValue V) -> bool {
  SmallVector<SDValue> Leaves;
  collectLeaves<ISD::ADD>(V, Leaves);

  if constexpr (sorting) {
    // Do we want to sort these in any order?
  }

  if (Leaves.size() == 2) {
    SDValue X = Leaves[0];
    SDValue Y = Leaves[1];
    if (sd_match(N, m_Add(m_Value(X), m_Value(Y)))) {
      return true;
    }
  }

  if (Leaves.size() == 3) {
    SDValue X = Leaves[0];
    SDValue Y = Leaves[1];
    SDValue Z = Leaves[2];
    if (sd_match(N, m_Add(m_Add(m_Value(X), m_Value(Y)), m_Value(Z)))) {
      return true;
    }
  }

  if (Leaves.size() == 4) {
    SDValue X = Leaves[0];
    SDValue Y = Leaves[1];
    SDValue Z = Leaves[2];
    SDValue W = Leaves[3];
    if (sd_match(N, m_Add(m_Add(m_Value(X), m_Value(Y)),
                          m_Add(m_Value(Z), m_Value(W))))) {
      return true;
    }
  }
  return false;
}

Naturally, this needs expanding out into something that can pattern patch any number of commutative operations, but thought I would start with the 3/4 @RKSimon asked for. If you could give me any tips, that would be appreciated as it is an issue I would like to tackle, but not too sure if this is a bit out of my depth for a first issue as I have never done anything with DAGs before.

[mshockwave]

if (sd_match(N, m_Add(m_Value(X), m_Value(Y)))) {
return true;
}

m_Value(X) stores the matched SDValue into X rather than checks if the SDValue is equal to X, as m_Value is declared as m_Value(SDValue &N). If you want to check if the underlying SDValue equals to X, m_Specific(X) is what you're looking for.

Also, I believe this part of the code is trying to explicitly enumerate every single possible shape of an expression tree:

  if (Leaves.size() == 2) {
    SDValue X = Leaves[0];
    SDValue Y = Leaves[1];
    if (sd_match(N, m_Add(m_Value(X), m_Value(Y)))) {
      return true;
    }
  }

  if (Leaves.size() == 3) {
    SDValue X = Leaves[0];
    SDValue Y = Leaves[1];
    SDValue Z = Leaves[2];
    if (sd_match(N, m_Add(m_Add(m_Value(X), m_Value(Y)), m_Value(Z)))) {
      return true;
    }
  }

  if (Leaves.size() == 4) {
    SDValue X = Leaves[0];
    SDValue Y = Leaves[1];
    SDValue Z = Leaves[2];
    SDValue W = Leaves[3];
    if (sd_match(N, m_Add(m_Add(m_Value(X), m_Value(Y)),
                          m_Add(m_Value(Z), m_Value(W))))) {
      return true;
    }
  }

Which I would not recommend, for the reason I stated in my previous comment.

IIUC, that part of the code is trying to implement the matching phase. Conceptually, the most naive way would be using something like this:

for (SDValue N : Leaves) {
  for (const auto &Pat : Patterns) {
    if (!sd_match(N, Pat))
      continue;
    // N matches one of the sub-patterns, Pat
    Patterns.erase(Pat);
    break;
  }
}
// If Patterns is not empty at this point, we fail the match

But each leave SDValue might match more than one sub-patterns, or a single sub-pattern matches more than one SDValue, in either case we might yield a false negative result. This is the problem I described in my previous comment, where I suggested to solve with some sort of bookkeepings.

[Esan5]

Hello, I would like to attempt this if @GrumpyPigSkin is no longer interested. @mshockwave would you be willing to take a look at this and let me know if its a good start?

// Is all this supposed to be inside a single struct?
template <typename... PatternTs> struct ReassociatableOpc_match {
  unsigned Opcode;
  std::tuple<PatternTs...> Patterns;

  ReassociatableOpc_match(unsigned Opc, PatternTs &&...P) : Opcode(Opc), Patterns(P...) {}

  template <typename MatchContext>
  bool match(const MatchContext &Ctx, SDValue N) {
    SmallVector<SDValue> Leaves;
    collectLeaves(N, Leaves);
    if (Leaves.size() != std::tuple_size_v<std::tuple<PatternTs...>>) {
      return false;
    }

    // J in Matches[I] iff sd_context_match(Leaves[I], Ctx,
    // std::get<J>(Patterns)) == true
    SmallVector<SmallVector<size_t>> Matches(Leaves.size());
    for (size_t I = 0; I < Leaves.size(); I += 1) {
      SmallVector<bool> MatchResults;
      std::apply(
          [&](auto &...P) {
            (MatchResults.emplace_back(sd_context_match(Leaves[I], Ctx, P)),
             ...);
          },
          Patterns);
      for (size_t J = 0; J < MatchResults.size(); J += 1) {
        if (MatchResults[J]) {
          Matches[I].emplace_back(J);
        }
      }
    }

    SmallVector<bool> Used(std::tuple_size_v<std::tuple<PatternTs...>>, false);
    return reassociatableMatchHelper(Matches, Used);
  }

  void collectLeaves(SDValue V, SmallVector<SDValue> &Leaves) {
    if (V->getOpcode() == Opcode) {
      for (size_t I = 0; I < V->getNumOperands(); I += 1) {
        collectLeaves(V->getOperand(I), Leaves);
      }
    } else {
      Leaves.emplace_back(V);
    }
  }

  // naive solution recursively tries all matches until success
  [[nodiscard]] inline bool
  reassociatableMatchHelper(const SmallVector<SmallVector<size_t>> &Matches,
                            SmallVector<bool> &Used, size_t Curr = 0) {
    if (Curr == Matches.size()) {
      return true;
    }
    for (auto Match : Matches[Curr]) {
      if (Used[Match]) { // pattern is already used
        continue;
      }
      Used[Match] = true;
      if (reassociatableMatchHelper(Matches, Used, Curr + 1)) {
        return true;
      }
      Used[Match] = false;
    }
    return false; // All patterns that match the current leaf are taken so we fail
  }
};

I did have a few questions while reading the existing code. Please correct me if I'm wrong, but it seems like patterns are distinct types, like Value_match and BinaryOpc_match so my solution uses a tuple to hold all the patterns, but maybe there's an easier way to do this? Also, is it correct to place this logic in some kind of ReasssociatableOpc_match struct or am I misinterpreting the way this works?

[Shoreshen]

Hi, for this function I may have some questions, maybe I'm wrong since I haven't fully understand the exact implementation.

The main problem is should we consider the situation that maybe sub nodes also include add, for example we have the following:

SDValue Op0 = DAG->getCopyFromReg(DAG->getEntryNode(), DL, 1, Int32VT);
SDValue Op1 = DAG->getCopyFromReg(DAG->getEntryNode(), DL, 2, Int32VT);
SDValue Op2 = DAG->getCopyFromReg(DAG->getEntryNode(), DL, 3, Int32VT);

SDValue ADD01 = DAG->getNode(ISD::ADD, DL, Int32VT, Op0, Op1);
SDValue ADD23 = DAG->getNode(ISD::ADD, DL, Int32VT, ADD01, Op2);

bool ret = sd_match(ADD01, m_ReassociatableAdd(m_Value(), m_Value()));

Since one of the sub node is ISD::ADD, the collect process will return size of 3, which will reject directly. But from a normal user perspective of view, I would expect the pattern should be matched.

If we accept ADD also can be sub node, there can be other problems

1. The matched pattern it self can be ambiguous. For example we have the DAG as (add (add Op0, Op1), (add Op2, Op3)), and we try to match m_ReassociatableAdd(m_Value(), m_Value(), m_Value()), so we can have the match as m_ReassociatableAdd(Op0, Op1, (add Op2, Op3)) or m_ReassociatableAdd((add Op0, Op1), Op2, Op3) depends on the search pattern. It may mis-match the purpose of user
2. If we have DAG as (add Op1, (add (sub Op2, Op0), Op3)) and would like to match m_ReassociatableAdd(m_Value(), m_sub(m_Value(),m_Value())), then should it be applied?? Since it does not match m_add(m_Value(), m_sub(m_Value(),m_Value()))

---

One more thing, can we merge the process of collecting leaves and verify? During the DFS search:

1. match the sub node with all patterns
2. if one pattern matched, then remove it from all patterns, start to deal with other sub nodes
3. if none of the pattern matched, then check if the opcode of node is ADD
4. if nothing in all patterns, it is a match
5. if search space exhausted, it is a not match

[Esan5]

I'll defer to others who definitely have a better grasp of this than me, but I think the general idea, and what I aimed for with my implementation, is to not allow ADD in matches, i.e. m_ReassociatableAdd(Pattern1, Pattern2, Pattern3, Pattern4) should match things of the form Pattern1 + Pattern2 + Pattern3 + Pattern4 assuming none of the patterns are themselves adds. I think with some clever function overloading and metaprogramming it would be possible to "unbox" adds so that something like m_ReassociatableAdd(Pattern1, (add Pattern2, Pattern3)) would be converted to m_ReassociatableAdd(Pattern1, Patttern2, Pattern3), but I didn't implement this in my PR.

As for merging the collection and the verification, I think it would be possible, but difficult. Patterns are possibly distinct types, so it isn't possible to hold them in a container that easily supports remove i.e. vector. Instead, I hold them in a tuple which would make adding and removing difficult, but I may be missing something.

[Shoreshen]

I'll defer to others who definitely have a better grasp of this than me, but I think the general idea, and what I aimed for with my implementation, is to not allow ADD in matches, i.e. m_ReassociatableAdd(Pattern1, Pattern2, Pattern3, Pattern4) should match things of the form Pattern1 + Pattern2 + Pattern3 + Pattern4 assuming none of the patterns are themselves adds. I think with some clever function overloading and metaprogramming it would be possible to "unbox" adds so that something like m_ReassociatableAdd(Pattern1, (add Pattern2, Pattern3)) would be converted to m_ReassociatableAdd(Pattern1, Patttern2, Pattern3), but I didn't implement this in my PR.

As for merging the collection and the verification, I think it would be possible, but difficult. Patterns are possibly distinct types, so it isn't possible to hold them in a container that easily supports remove i.e. vector. Instead, I hold them in a tuple which would make adding and removing difficult, but I may be missing something.

Hi, maybe using a vector of bools to mark the position of tuple which has been matched.

BTW, I think in you current implementation, it is also not allowed to match (add Op1, (add (sub Op2, Op0), Op3)) to m_ReassociatableAdd(m_Value(), m_sub(m_Value(),m_Value())) right?? Since the number of leafs will be 3 and reject the pattern??

[Esan5]

Yeah I currently use a vector of bools in order to check matches, I am personally of the opinion that eagerly matching during the searching phase if a leaf only matches a single pattern would be a case of premature optimization. I don't expect the number of patterns provided to the matcher to be much larger than 4, but implementing something like that would add an extra for loop and likely also an additional fold expression as well as requiring additional parameters, so I think it may not be worth it. I am more than willing to implement it if it is important, but I want to keep something like this as simple as possible if it isn't a necessity.

As for you second point, I'm a bit confused, the add is Op1 + (Op2 - Op0) + Op3 so we would need three patterns. m_sub(...) will match the subtraction, but m_Value() can only match Op1 or Op3, not both, so it it correct to reject this case. I may be interpreting this wrong, so let me know if things needs to change.