Failure to match a DAG after a minor pattern change in a custom Target

Project Infrastructure LLVM Dev List Archives
1

In an attempt to add vector registers to my target, I ran into a problem. LLVM started to complain about not being able to infer types from the provided DAG patterns for several classes of instructions. After a discussion on the llvm-dev mailing list and IRC channel the recommendation was to make DAG patterns for these classes of instructions more specific. Which is what was done. However after the changes were made, LLVM stopped recognizing a particular pattern, saying that it can not match it. Given that my understanding of DAG patterns is quite weak, I’d appreciate any help on this. For that matter, any opportunity to learn about LLVM is welcomed. Original code, modified code as well as the error are provided below. I can provide more if needed. There were two changes made. One in the definition of SDT_EsenciaSetFlag and another in SF_RI class (specifically in its DAG pattern).

Any help is appreciated.

========================= Orignal Code =====================================

def SDT_EsenciaSetFlag : SDTypeProfile<0, 3, [SDTCisSameAs<0, 1>]>;

def Esenciasetflag : SDNode<“EsenciaISD::SET_FLAG”, SDT_EsenciaSetFlag,
[SDNPOutGlue]>;

def Esencia_CC_LT : PatLeaf<(imm),
[{return (N->getZExtValue() == ISD::SETLT);}]>;

class SF_RI<bits<5> op2Val, string asmstr, PatLeaf Cond>
: InstRI<0xf, (outs), (ins GPR:$rA, s16imm:$imm),
!strconcat(asmstr, “i\t$rA, $imm”),
[(Esenciasetflag (i32 GPR:$rA), immSExt16:$imm, Cond)]> {
bits<5> op2;
bits<5> rA;
bits<16> imm;

let Inst{25-21} = op2;
let Inst{20-16} = rA;
let Inst{15-0} = imm;

let format = AFrm;
let op2 = op2Val;
}

defm SFLTS : SF<0xc, “l.sflts”, Esencia_CC_LT>;

========================= Modified Code =====================================

def SDT_EsenciaSetFlag : SDTypeProfile<1, 3, [SDTCisSameAs<1, 2>]>;

def Esenciasetflag : SDNode<“EsenciaISD::SET_FLAG”, SDT_EsenciaSetFlag,
[SDNPOutGlue]>;

def Esencia_CC_LT : PatLeaf<(imm),
[{return (N->getZExtValue() == ISD::SETLT);}]>;

class SF_RI<bits<5> op2Val, string asmstr, PatLeaf Cond>
: InstRI<0xf, (outs), (ins GPR:$rA, s16imm:$imm),
!strconcat(asmstr, “i\t$rA, $imm”),
[(set SR:$rD, (Esenciasetflag (i32 GPR:$rA), (i32 immSExt16:$imm), (i32 Cond)))]> {
bits<5> op2;
bits<5> rA;
bits<16> imm;

let Inst{25-21} = op2;
let Inst{20-16} = rA;
let Inst{15-0} = imm;

let format = AFrm;
let op2 = op2Val;
}

multiclass SF<bits<5> op2Val, string asmstr, PatLeaf Cond> {
def _rr : SF_RR<op2Val, asmstr, Cond>;
def _ri : SF_RI<op2Val, asmstr, Cond>;
}

defm SFLTS : SF<0xc, “l.sflts”, Esencia_CC_LT>;

========================= Orignal Match Result =====================================

Selecting: 0x2ebfa78: glue = EsenciaISD::SET_FLAG 0x2ebee18, 0x2ebef20, 0x2ebf658 [ORD=3] [ID=11]

ISEL: Starting pattern match on root node: 0x2ebfa78: glue = EsenciaISD::SET_FLAG 0x2ebee18, 0x2ebef20, 0x2ebf658 [ORD=3] [ID=11]

Initial Opcode index to 258
Skipped scope entry (due to false predicate) at index 278, continuing at 292
Skipped scope entry (due to false predicate) at index 293, continuing at 307
Skipped scope entry (due to false predicate) at index 308, continuing at 322
Skipped scope entry (due to false predicate) at index 323, continuing at 337
Skipped scope entry (due to false predicate) at index 338, continuing at 352
Skipped scope entry (due to false predicate) at index 353, continuing at 367
Skipped scope entry (due to false predicate) at index 368, continuing at 382
Skipped scope entry (due to false predicate) at index 383, continuing at 397
Morphed node: 0x2ebfa78: i32,glue = SFLTS_ri 0x2ebee18, 0x2ebf130 [ORD=3]

ISEL: Match complete!
=> 0x2ebfa78: i32,glue = SFLTS_ri 0x2ebee18, 0x2ebf130 [ORD=3]

========================= Failed Match Result =====================================

Selecting: 0x242d278: glue = EsenciaISD::SET_FLAG 0x242c618, 0x242c720, 0x242ce58 [ORD=3] [ID=11]

ISEL: Starting pattern match on root node: 0x242d278: glue = EsenciaISD::SET_FLAG 0x242c618, 0x242c720, 0x242ce58 [ORD=3] [ID=11]

Initial Opcode index to 258
Skipped scope entry (due to false predicate) at index 285, continuing at 301
Skipped scope entry (due to false predicate) at index 302, continuing at 318
Skipped scope entry (due to false predicate) at index 319, continuing at 335
Skipped scope entry (due to false predicate) at index 336, continuing at 352
Skipped scope entry (due to false predicate) at index 353, continuing at 369
Skipped scope entry (due to false predicate) at index 370, continuing at 386
Skipped scope entry (due to false predicate) at index 387, continuing at 403
Skipped scope entry (due to false predicate) at index 404, continuing at 420
Match failed at index 424
Continuing at 437
Match failed at index 438
Continuing at 454
Continuing at 455
Skipped scope entry (due to false predicate) at index 466, continuing at 480
Skipped scope entry (due to false predicate) at index 481, continuing at 495
Skipped scope entry (due to false predicate) at index 496, continuing at 510
Skipped scope entry (due to false predicate) at index 511, continuing at 525
Skipped scope entry (due to false predicate) at index 526, continuing at 540
Skipped scope entry (due to false predicate) at index 541, continuing at 555
Skipped scope entry (due to false predicate) at index 556, continuing at 570
Skipped scope entry (due to false predicate) at index 571, continuing at 585
Match failed at index 589
Continuing at 600
Match failed at index 601
Continuing at 615
Continuing at 616
Continuing at 617
Match failed at index 619
Continuing at 811
LLVM ERROR: Cannot select: 0x242d278: glue = EsenciaISD::SET_FLAG 0x242c618, 0x242c720, 0x242ce58 [ORD=3] [ID=11]
0x242c618: i32,ch = CopyFromReg 0x24009a0, 0x242c510 [ORD=1] [ID=9]
0x242c510: i32 = Register %vreg5 [ID=1]
0x242c720: i32 = Constant<3> [ID=2]
0x242ce58: i32 = Constant<20> [ID=8]
In function: fib

2

I suspect that the "set SR:$rD" is the problem here. The Esenciasetflag does not have any values that can be assigned to a
register, so it's probably this part that causes the pattern to fail.

Tablegen creates a xxxGenDAGISel.inc file in your target's build directory. The "index" numbers that the debugging info shows correspond to the numbers in that file. Here's an example from HexagonGenDAGISel.inc:

/*28*/ OPC_Scope, 88|128,3/*472*/, /*->503*/ // 3 children in Scope
/*31*/ OPC_MoveChild, 1,
/*33*/ OPC_CheckOpcode, TARGET_VAL(ISD::ADD),
/*36*/ OPC_RecordChild0, // #2 = $base
/*37*/ OPC_RecordChild1, // #3 = $offset
/*38*/ OPC_MoveChild, 1,
/*40*/ OPC_CheckOpcode, TARGET_VAL(ISD::Constant),
/*43*/ OPC_Scope, 65, /*->110*/ // 7 children in Scope
/*45*/ OPC_CheckPredicate, 0, // Predicate_u32ImmPred
/*47*/ OPC_MoveParent,
/*48*/ OPC_CheckType, MVT::i32,

When the matcher says "false predicate at index 123", you can look at the line marked with /*123*/ and see exactly what predicate it was checking. This helps immensely with solving such problems.

-Krzysztof

3

I'm having difficulty interpreting the EsenciaGenDAGISel.inc. Specifically
the MatcherTable. I would really appreciate any help on this. Say we are
looking at the following code:

/*254*/ /*SwitchOpcode*/ 42|128,4/*554*/,
TARGET_VAL(EsenciaISD::SET_FLAG),// ->812
/*258*/ OPC_RecordChild0, // #0 = $rA
/*259*/ OPC_Scope, 99|128,2/*355*/, /*->617*/ // 2 children in Scope
/*262*/ OPC_CheckChild0Type, MVT::i32,
/*264*/ OPC_RecordChild1, // #1 = $imm
/*265*/ OPC_Scope, 59|128,1/*187*/, /*->455*/ // 2 children in Scope
/*268*/ OPC_MoveChild, 1,
/*270*/ OPC_CheckOpcode, TARGET_VAL(ISD::Constant),
/*273*/ OPC_CheckPredicate, 16, // Predicate_immSExt16
/*275*/ OPC_MoveParent,
/*276*/ OPC_MoveChild, 2,
/*278*/ OPC_CheckOpcode, TARGET_VAL(ISD::Constant),
/*281*/ OPC_CheckType, MVT::i32,
/*283*/ OPC_Scope, 16, /*->301*/ // 10 children in Scope
/*285*/ OPC_CheckPredicate, 17, // Predicate_Esencia_CC_EQ
/*287*/ OPC_MoveParent,
/*288*/ OPC_CheckType, MVT::i32,
/*290*/ OPC_EmitConvertToTarget, 1,
/*292*/ OPC_MorphNodeTo, TARGET_VAL(Esencia::SFEQ_ri),
0|OPFL_GlueOutput,
                        1/*#VTs*/, MVT::i32, 2/*#Ops*/, 0, 2,
                    // Src: (Esenciasetflag:i32 GPR:i32:$rA,
(imm:i32)<<P:Predicate_immSExt16>>:$imm,
(imm:i32)<<P:Predicate_Esencia_CC_EQ>>) - Complexity = 11
                    // Dst: (SFEQ_ri:i32 GPR:i32:$rA, (imm:i32):$imm)
/*301*/ /*Scope*/ 16, /*->318*/
/*302*/ OPC_CheckPredicate, 18, // Predicate_Esencia_CC_NE
/*304*/ OPC_MoveParent,
/*305*/ OPC_CheckType, MVT::i32,
/*307*/ OPC_EmitConvertToTarget, 1,
/*309*/ OPC_MorphNodeTo, TARGET_VAL(Esencia::SFNE_ri),
0|OPFL_GlueOutput,
                        1/*#VTs*/, MVT::i32, 2/*#Ops*/, 0, 2,
                    // Src: (Esenciasetflag:i32 GPR:i32:$rA,
(imm:i32)<<P:Predicate_immSExt16>>:$imm,
(imm:i32)<<P:Predicate_Esencia_CC_NE>>) - Complexity = 11
                    // Dst: (SFNE_ri:i32 GPR:i32:$rA, (imm:i32):$imm)
/*318*/ /*Scope*/ 16, /*->335*/
/*319*/ OPC_CheckPredicate, 19, // Predicate_Esencia_CC_GTU
/*321*/ OPC_MoveParent,
/*322*/ OPC_CheckType, MVT::i32,
/*324*/ OPC_EmitConvertToTarget, 1,

what does it tell me? How do I interpret it?

I also have a question about predicates. What exactly are they? I know that
they are pattern leaves and have code associated with them. But how exactly
do they fit into the pattern matching?

Any help on this is appreciated.

4

            [(set SR:$rD, (Esenciasetflag (i32 GPR:$rA), (i32
immSExt16:$imm), (i32 Cond)))]> {

I suspect that the "set SR:$rD" is the problem here. The Esenciasetflag
does not have any values that can be assigned to a
register, so it's probably this part that causes the pattern to fail.

Would you mind showing how to make Esenciasetflag to actually set a flag? I
can't figure out the syntax.

5

Is the "setflag" instruction setting something in a special register (such as EFLAGS on x86)? If so, then you can add "let Defs [xyz] in ..." to your .td definition of that instruction and leave the "set" out of the pattern.

The type that you defined
   def SDT_EsenciaSetFlag : SDTypeProfile<0, 3, [SDTCisSameAs<0, 1>]>;
indicates 0 return values, so it would match this approach.

If the instructions is intended to actually produce a value that could be stored in an allocatable register, then you'd need to change the type to have 1 return value. The selection pattern would likely work as is.

-Krzysztof

6

Thanks for the reply. I actually managed to figure it out before the answer. You first post was correct. The issue was with the set SR:$rD. I simply need to remove it.

Thanks for the help.