RyuJIT: IR Tree matching APIs

[EgorBo]

Today, when we need to recognize simple expressions (nodes/trees), e.g. a tree must be either "X op CNS" or "CNS op X" we usually end up with something like this:

GenTree*       op  = nullptr;
GenTreeIntCon* cns = nullptr;
if (tree->gtGetOp1()->IsIntegralConst())
{
    cns = tree->gtGetOp1()->AsIntConCommon();
    op  = tree->gtGetOp2();
}
else if (tree->gtGetOp2()->IsIntegralConst())
{
    cns = tree->gtGetOp2()->AsIntConCommon();
    op  = tree->gtGetOp1();
}
if (cns != nullptr)
{
    // do work with op and cns
}

I'm thinking of proposing a sort of "match" API similar to what is used in LLVM, for example LLVM's equivalent of ^:

Value* A;    // as a generic GenTree*
Constant* B; // as a GenTreeIntCon*
if (match(tree, m_BinOp(m_Value(A), m_Constant(B))) || 
    match(tree, m_BinOp(m_Constant(B), m_Value(A))))
{
    // do work with A and B
}

So we can adopt it to something like this for RyuJIT:

GenTree* op;
GenTreeIntCon* cns;
if (pmMatch(tree, pmBinOp(pmAnyOp(op), pmIntCon(cns))) || 
    pmMatch(tree, pmBinOp(pmIntCon(cns), pmAnyOp(op))))
{
    // work with op and cns
}

It's extremely powerful and easy to read once you get used to it, and waaaaaay less verbose.

More LLVM examples:

// 8 >> X
Value *X;
APInt *C;
if (match(tree, m_LShr(m_Power2(C), m_Value(X))) {

// (X - Y) + 1
Value *X, *Y;
if (match(tree, 
      m_Add(
          m_OneUse(m_Sub(
                       m_Value(X), 
                       m_Value(Y))),
          m_AllOnes())) {

m_OneUse as in "single use"

Alternative Design

Rewrite JIT to C#/F# 😐

cc @dotnet/jit-contrib @SingleAccretion

category:design theme:ir

[ghost]

Tagging subscribers to this area: @JulieLeeMSFT See info in area-owners.md if you want to be subscribed.

Issue Details

---

Today, when we need to recognize simple expressions (nodes/trees), e.g. `a tree must be either "X op CNS" or "CNS op X"` we usually end up with something like this: ```c++ GenTree* op = nullptr; GenTreeIntCon* cns = nullptr; if (tree->gtGetOp1()->IsIntegralConst()) { cns = tree->gtGetOp1()->AsIntConCommon(); op = tree->gtGetOp2(); } else if (tree->gtGetOp2()->IsIntegralConst()) { cns = tree->gtGetOp2()->AsIntConCommon(); op = tree->gtGetOp1(); } if (cns != nullptr) { // do work with op and cns } ``` I'm thinking of proposing a sort of "match" API similar to what is used in LLVM, for example LLVM's equivalent of ^: ```c++ Value* A; // as a generic GenTree* Constant* B; // as a GenTreeIntCon* if (match(tree, m_BinOp(m_Value(A), m_Constant(B))) || match(tree, m_BinOp(m_Constant(B), m_Value(A)))) { // do work with A and B } ``` So we can adopt it to something like this for RyuJIT: ```c++ GenTree* op; GenTreeIntCon* cns; if (pmMatch(tree, pmBinOp(pmAnyOp(op), pmIntCon(cns))) || pmMatch(tree, pmBinOp(pmIntCon(cns), pmAnyOp(op)))) { // work with op and cns } ``` It's extremely powerful and easy to read once you get used to it, and waaaaaay less verbose. More LLVM examples: ``` // 8 >> X Value *X; APInt *C; if (match(tree, m_LShr(m_Power2(C), m_Value(X))) { ``` ``` // (X - Y) + 1 Value *X, *Y; if (match(tree, m_Add( m_OneUse(m_Sub(m_Value(X), m_Value(Y))), m_AllOnes())) { ``` `m_OneUse` as in "single use" ## Alternative Design Rewrite JIT to C#/F# 😐 cc @dotnet/jit-contrib @SingleAccretion

Author:	EgorBo
Assignees:	-
Labels:	`area-CodeGen-coreclr`, `untriaged`
Milestone:	-

[ShreyasJejurkar]

I support alternate design 😅

[hypeartist]

Take my 2 cents in favor of alternative design!

[masonwheeler]

Agreeing with the alternative design option. The less C++ there is powering things we care about, the better! Let's build C# in itself.

[TIHan]

As someone who has used pattern matching (F#) for a long time, especially in compilers, the 'match' API is a very interesting idea; a prototype would be worth doing. The thing to check is what the performance implications are since this is not a proper form of pattern matching.

[anthonycanino]

Hi @EgorBo , just curious if there has been any more thoughts / prototype work on this?

[TIHan]

On vacation but spent a little bit of time trying to create a prototype.

Based on @EgorBo 's example, it works and looks like this:

GenTree*       op;
GenTreeIntCon* cns;
if (tree->Match(&op, &cns) || tree->Match(&cns, &op))
{
    // work with op and cns
}

Implementation of this overload of Match:

    template <class T1 = GenTree, class T2 = GenTree>
    bool Match(T1** op1, T2** op2)
    {
        if (OperIsBinary())
        {
            *op1 = dynamic_cast<T1*>(gtGetOp1());
            *op2 = dynamic_cast<T2*>(gtGetOp2());
            if ((*op1 != nullptr) && (*op2 != nullptr))
            {
                return true;
            }
            *op1 = nullptr;
            *op2 = nullptr;
            return false;
        }
        return false;
    }

Another example: Before:

if (tree->OperIs(GT_MOD, GT_UMOD) && (op2->IsIntegralConst(1)))
{
    // work
}

After:

if (tree->MatchOp2<GT_MOD, GT_UMOD>(1))
{
    // work
}

Implementation of this overload of MatchOp2:

    template <genTreeOps... T>
    bool MatchOp2(ssize_t cns)
    {
        static_assert(AllOperIsBinary(T...) && "Not a binary operator!");
        return OperIs(T...) && gtGetOp2()->IsIntegralConst(cns);
    }

I have more implementations of the other overloads for these functions, but thought I'd share a little bit here.