[DAG] SDPatternMatch - add m_BinOp/m_c_BinOp variants driven by TLI.isBinOp/isCommutativeBinOp

[RKSimon]

As noticed on #84759 - we should be able to allow folds to generally match any binary ops that are recognized by the TLI.isBinOp/isCommutativeBinOp callbacks, allowing us to match target binops in generic dag combines.

CC @mshockwave

[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. In the comments of the issue, request for it to be assigned to you.
2. Fix the issue locally.
3. 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.
4. Create a Git commit.
5. Run git clang-format HEAD~1 to format your changes.
6. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation.

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)

As noticed on #84759 - we should be able to allow folds to generally match any binary ops that are recognized by the TLI.isBinOp/isCommutativeBinOp callbacks, allowing us to match target binops in generic dag combines.

CC @mshockwave

[Sh0g0-1758]

@RKSimon, I would like to work on this. I can provide a patch both for this issue and for reducing the matching code as mentioned here.

[Sh0g0-1758]

Needed a little help. Am I to add a variant of this code in SDPatternMatch.h but now use TLI.isBinOp/isCommutativeBinOp for the match logic? Because isBinOp works on binary opcodes and in the original thread,

I would favor adding pattern like PatternMatch::m_BinOp(LHS, RHS) was mentioned which implies no use of opcode. :

template <typename LHS_t, typename RHS_t, bool Commutable = false>
struct AnyBinaryOp_match {
  LHS_t L;
  RHS_t R;

  // The evaluation order is always stable, regardless of Commutability.
  // The LHS is always matched first.
  AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}

  template <typename OpTy> bool match(OpTy *V) {
    if (auto *I = dyn_cast<BinaryOperator>(V))
      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
             (Commutable && L.match(I->getOperand(1)) &&
              R.match(I->getOperand(0)));
    return false;
  }
};

template <typename LHS, typename RHS>
inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
  return AnyBinaryOp_match<LHS, RHS>(L, R);
}

[RKSimon]

CC @mshockwave

[RKSimon]

We're going to need to extract the opcode, m_AnyBinOp(unsigned &Opcode, const LHS &L, const RHS &R) maybe?

[Sh0g0-1758]

but doesn't the m_BinOp variant of SDPatternMatch does exactly this ?

[RKSimon]

No, in this case we need to be told whatever the opcode is, not match for an explicit opcode

[Sh0g0-1758]

This is in SDPatternMatch.h :

template <typename LHS, typename RHS>
inline BinaryOpc_match<LHS, RHS, false> m_BinOp(unsigned Opc, const LHS &L,
                                                const RHS &R) {
  return BinaryOpc_match<LHS, RHS, false>(Opc, L, R);
}
template <typename LHS, typename RHS>
inline BinaryOpc_match<LHS,RHS,false> m_BinOp(const LHS &L, const RHS &R) {
  return BinaryOpc_match<LHS, RHS, false>(TLI.isBinOp(), L, R);
}

So we need something like? :

template <typename LHS, typename RHS>
inline BinaryOpc_match<LHS,RHS,false> m_AnyBinOp(unsigned Opc,const LHS &L, const RHS &R) {
  if (TLI.isBinOP(Opc)) {
     return BinaryOpc_match<LHS, RHS, false>(TLI.isBinOp(), L, R);
  }
}

[Sh0g0-1758]

gentle ping. I am aware of the weekly ping policy but it seems prudent so that we can progress on this.

[RKSimon]

@mshockwave Any suggestions please?

[mshockwave]

I think the general direction of your interface design makes sense; in addition to the existing m_BinOp/m_c_BinOp you're adding another two: m_AnyBinOp(LHS, RHS) for opcode-agnostic matching, and m_AnyBinOp(unsigned &Opc, LHS, RHS) for opcode-agnostic matching while extracting opcode at the same time. Whether the new m_AnyBinOp and m_BinOp should share the underlying implementation is another thing, which I'm fine with either creating a new class for m_AnyBinOp or modifying the existing BinaryOpc_match. If you would like to take the latter option, you could create a new constructor for BinaryOpc_match that handles m_AnyBinOp's functionalities, namely, checking against TLI and extracting opcode. For instance BinaryOpc_match(unsigned *ExtractedOpcode, Pattern LHS, Patten RHS). Then, inside BinaryOpc_match::match, based on which constructor was used, we conditionally used the proper opcode checking strategy.

[Sh0g0-1758]

I have opened a draft PR. I am not sure how to handle the case where we tackle TLI with m_AnyBinOp(LHS, RHS), for now I have simply returned true. I would also like to have a sanity check on the tests.