How to understand `PatFrags` in backend codegen?

MLIR
1

Hi, I’m just little bit confusing of how to use PatFrags, let me present my understanding of PatFrags:

  1. The first parameter is the accepting format, it has a form of (ops node:$name1, node:$name2, ...)
  2. The second parameter, which is a list of DAGs, is the “replacement possibilities”, within these DAGs any use of node:$name#i will be replaced by the instantiated accepting format

Now I’m going to use an example to illustrate my question, suppose we have the PatFrags defined as follow:

def test_add_frag : PatFrags<
    (ops node:$a, node:$b), 
    [
        (add node:$a, node$:b), 
        (mul node:$a, (div (add node:$a, node:$b), node:$a))
    ]
>;

We use that as patterns of an instruction:

def ADD : Instruction {
    ...
    let Pattern  = [(set Reg:$dst, (test_add_frag reg_or_imm:$src0, reg_or_imm:$src1))];;
    ...
};

Now my questions is since the PatFrags is inside of one DAG, how to show that it is matching a list, is it equivalent to the following so that it is matching both pattern generated from the divergent of PatFrags?

def ADD : Instruction {
    ...
    let Pattern  = [
        (set Reg:$dst, (add reg_or_imm:$src0, reg_or_imm:$src1)),
        (set Reg:$dst, (mul reg_or_imm:$src0, (div (add reg_or_imm:$src0, reg_or_imm:$src1), reg_or_imm:$src0)))
    ];;
    ...
};

Thanks!

2 
PatFrags [pattern1, pattern2, ...]

is equivalent to

PatFrag[pattern1] || PatFrag[pattern2] ...

PatFrags evolved from PatFrag which accepts only one fragment. It turned out to be a common situation where people wrote several patterns using separate PatFrags, which in the end generated the same output for different patterns. Instead of duplicating code for each separate fragment, you can now combine them into PatFrags.

1 Like
3

Thanks for replying, I’m confusing is because that the PatFrags is inside of a DAG, and how to show that the PatFrags is matching 2 patterns instead of 1??

In other words, are the following 2 example equivalent based on the definition I listed in the question

def ADD : Instruction {
    ...
    let Pattern  = [(set Reg:$dst, (test_add_frag reg_or_imm:$src0, reg_or_imm:$src1))];;
    ...
};

and

def ADD : Instruction {
    ...
    let Pattern  = [
        (set Reg:$dst, (add reg_or_imm:$src0, reg_or_imm:$src1)),
        (set Reg:$dst, (mul reg_or_imm:$src0, (div (add reg_or_imm:$src0, reg_or_imm:$src1), reg_or_imm:$src0)))
    ];
    ...
};
4

Only one of the patterns is expected to match. That is sufficient for the PatFrags to match.

IIRC, you can’t have multiple patterns in the definition of Instruction. Pattern fragments are usually used in Pats, so

def Frag1<(ops node:$a, node:$b), (add $a, $b)>;
def Frag2<(ops node:$a, node:$b), (mul (div $a, $b), $a)>;
def: Pat<(Frag1 $a, $b), (ADD $a, $b)>;
def: Pat<(Frag2 $a, $b), (ADD $a, $b)>;

is equivalent to

def Frags: PatFrags<(ops node:$a, node:$b), [
  (add $a, $b),
  (mul (div $a, $b), $a)
]>;

def: Pat<(Frags $a, $b), (ADD $a, $b)>;
1 Like
5

Thanks~~ I think the type of patterns in class Instruction is a list<dag>, which means different patterns can match the target instruction.

Emmmmm, if the 2 are not equivalent, then if I write

def ADD : Instruction {
    ...
    let Pattern  = [(set Reg:$dst, (test_add_frag reg_or_imm:$src0, reg_or_imm:$src1))];;
    ...
};

What patterns will be matched exactly??

6

It will be the one you specified in the Pattern. When I said that you can’t have multiple patterns with (set ...) in Instruction, I meant that I’m not sure if TableGen would accept that syntax. But that aside, in principle, the two (set ...)s would indeed be equivalent to the one with PatFrags.

1 Like
7

I’m pretty sure that can be accepted by llvm, and lots of examples using any_fadd as their pattern node.

I’m a little bit confused, so in the final, the following two examples are the same right?

def ADD : Instruction {
    ...
    let Pattern  = [(set Reg:$dst, (test_add_frag reg_or_imm:$src0, reg_or_imm:$src1))];;
    ...
};

def ADD : Instruction {
    ...
    let Pattern  = [
        (set Reg:$dst, (add reg_or_imm:$src0, reg_or_imm:$src1)),
        (set Reg:$dst, (mul reg_or_imm:$src0, (div (add reg_or_imm:$src0, reg_or_imm:$src1), reg_or_imm:$src0)))
    ];
    ...
};
8

No, this list forms a single pattern. IIRC the second and subsequent elements of the list could only contain (implicit ...) construct that lists physical registers defined by the pattern. I dropped support for this and the list should be exactly one element long now. (This is still a list and not a Pattern because it is hard to change now.)

It doesn’t, currently. I looked into it a while ago and it didn’t seem difficult to support.

9

Thanks but I got more confused since to me it’s normal that different patterns can match the same instruction.

What if I have two patterns that can match the same instruction, then do I have to define the instruction 2 times with different name ??

10

You have to define extra patterns outside the instruction.
@kparzysz gave examples of how to do this above.

1 Like
12

That makes me more confused, do you mean by defining Pat I can make two patterns matching to one instruction?? If you could be so kind to provide an example of it??

And for the PatFrags question, are the following 2 equal or not?

def ADD : Instruction {
    ...
    let Pattern  = [(set Reg:$dst, (test_add_frag reg_or_imm:$src0, reg_or_imm:$src1))];;
    ...
};

def ADD : Instruction {
    ...
    let Pattern  = [
        (set Reg:$dst, (add reg_or_imm:$src0, reg_or_imm:$src1))
    ];
    ...
};
13

Yes. There are lots of examples in-tree. grep for def : Pat.

If test_add_frag is defined as:

def test_add_frag : PatFrags<
    (ops node:$a, node:$b), 
    [(add node:$a, node$:b)]
>;

then yes, they are equivalent.

1 Like
14

Thanks so much, I do have some more questions that I need to ask.

I do find lots of def: Pat but all are anonymous standalone definition. How they can they be applied to specific instructions??

I do have a llvm example of using PatFrags with multiple entry as part of patterns:

class X86Inst<bits<8> opcod, Format f, ImmType i, dag outs, dag ins,
              string AsmStr, Domain d = GenericDomain>
  : Instruction {
  ...
}

class PseudoI<dag oops, dag iops, list<dag> pattern>
  : X86Inst<0, Pseudo, NoImm, oops, iops, ""> {
  let Pattern = pattern;
}

class FpI_<dag outs, dag ins, FPFormat fp, list<dag> pattern>
  : PseudoI<outs, ins, pattern> {
  ...
}

class FpIf32<dag outs, dag ins, FPFormat fp, list<dag> pattern> :
             FpI_<outs, ins, fp, pattern>, Requires<[FPStackf32]>;

multiclass FPBinary_rr<SDPatternOperator OpNode> {
// Register op register -> register
// These are separated out because they have no reversed form.
def _Fp32 : FpIf32<(outs RFP32:$dst), (ins RFP32:$src1, RFP32:$src2), TwoArgFP,
    [(set RFP32:$dst, (OpNode RFP32:$src1, RFP32:$src2))]>;
...
}

let hasNoSchedulingInfo = 1 in {
defm ADD : FPBinary_rr<any_fadd>;
...
}

It can be clearly followed that the pattern of instruction is [(set RFP32:$dst, (any_fadd RFP32:$src1, RFP32:$src2))] and the definition for any_fadd would be the following. It is an example from X86 target and I just pulled my repo

def any_fadd       : PatFrags<(ops node:$lhs, node:$rhs),
                              [(strict_fadd node:$lhs, node:$rhs),
                               (fadd node:$lhs, node:$rhs)]>;
15

The instruction it applies to is referred to by the second argument of the anonymous Pat.

Correct, you can use PatFrag in Instruction’s Pattern. Internally, this will expand in two patterns, and either of them can match the instruction. This only happens internally; you cannot “expand” PatFrag used in Instruction’s Pattern by yourself, as I pointed out earlier.

1 Like
16

So for Pat, if I would like to say pattern (mul node:$a, (div (add node:$a, node:$b), node:$a)) should produce the instruction (ADD reg_or_imm:$a, reg_or_imm:$b), then I should define it like the following

def : Pat<
    (mul reg_or_imm:$a, (div (add reg_or_imm:$a, reg_or_imm:$b), reg_or_imm:$a)),
    (ADD reg_or_imm:$a, reg_or_imm:$b)
>

And I can define multiple patterns using PatFrags for the first parameter

And for PatFrags, basically if I have the following:

def test_add_frag : PatFrags<
    (ops node:$a, node:$b), 
    [
        (add node:$a, node$:b), 
        (mul node:$a, (div (add node:$a, node:$b), node:$a))
    ]
>;
def ADD : Instruction {
    ...
    let Pattern  = [(set Reg:$dst, (test_add_frag reg_or_imm:$src0, reg_or_imm:$src1))];;
    ...
};

Then both patterns of (set Reg:$dst, (add reg_or_imm:$src0, reg_or_imm:$src1)) and (set Reg:$dst, (mul reg_or_imm:$src0, (div (add reg_or_imm:$src0, reg_or_imm:$src1), reg_or_imm:$src0))) can be matched to the target instruction.

However, because the following definition is wrong in syntax, then it will not be equivalent to the above definition.

def ADD : Instruction {
    ...
    let Pattern  = [
        (set Reg:$dst, (add reg_or_imm:$src0, reg_or_imm:$src1)),
        (set Reg:$dst, (mul reg_or_imm:$src0, (div (add reg_or_imm:$src0, reg_or_imm:$src1), reg_or_imm:$src0)))
    ];
    ...
};

Would the above be correct?? Thanks so much for your help!!!

17

Yes, sounds correct.

1 Like