diff --git a/llvm/test/TableGen/GICombinerEmitter/match-invalid.td b/llvm/test/TableGen/GICombinerEmitter/match-invalid.td --- a/llvm/test/TableGen/GICombinerEmitter/match-invalid.td +++ b/llvm/test/TableGen/GICombinerEmitter/match-invalid.td @@ -53,6 +53,15 @@ // CHECK-NEXT: def unknown_kind2 : GICombineRule< // CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule +def multidef : GICombineRule< + (defs root:$a), + (match (MOV $a, $b), + (MOV $a, $b)), + (dummy)>; +// CHECK: :[[@LINE-5]]:{{[0-9]+}}: error: Two different MachineInstrs cannot def the same vreg +// CHECK-NEXT: def multidef : GICombineRule< +// CHECK: :[[@LINE-7]]:{{[0-9]+}}: error: Failed to parse rule + def multidef_but_not_an_error: GICombineRule< (defs root:$a), (match (MOV $a, $b), @@ -66,6 +75,7 @@ null_matcher, unknown_kind1, unknown_kind2, + multidef // Rules omitted from a matcher can be as broken as you like. They will not be read. // multidef_but_not_an_error ]>; diff --git a/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td b/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td new file mode 100644 --- /dev/null +++ b/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td @@ -0,0 +1,214 @@ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ +// RUN: -combiners=MyCombiner -gicombiner-stop-after-parse %s \ +// RUN: -o /dev/null -debug 2>&1 | FileCheck %s + +include "llvm/Target/Target.td" +include "llvm/Target/GlobalISel/Combine.td" + +def MyTargetISA : InstrInfo; +def MyTarget : Target { let InstructionSet = MyTargetISA; } + +def dummy; + +def R0 : Register<"r0"> { let Namespace = "MyTarget"; } +def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>; +class I Pat> + : Instruction { + let Namespace = "MyTarget"; + let OutOperandList = OOps; + let InOperandList = IOps; + let Pattern = Pat; +} +def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; +def MOV2 : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; + +def trivial : GICombineRule< + (defs root:$d), + (match (MOV $d, $s)), + (apply [{ APPLY }])>; + +// CHECK-LABEL: Parsed rule defs/match for 'trivial' + +// The matchdag block is a fairly direct dump of the information that was read. +// It's oriented towards the data structures within tablegen. +// CHECK-NEXT: matchdag { +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon0_0 // $d=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred0_1 +// CHECK-NEXT: __anon0_0 ==> __anonpred0_1[mi] +// CHECK-NEXT: {{^}$}} + +// The digraph block is a human-oriented dump of the information that was read. +// Run it through graphviz to produce a nice DAG showing the matcher behaviour. +// CHECK-NEXT: digraph "trivial" { +// CHECK-NEXT: rankdir="BT" +// CHECK-NEXT: Node[[N1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon0_0|MOV|Match starts here|$d=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred0_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] +// CHECK-NEXT: {{^}$}} + +def simple : GICombineRule< + (defs root:$d), + (match (MOV $t, $s), + (MOV $d, $t)), + (apply [{ APPLY }])>; + +// CHECK-LABEL: Parsed rule defs/match for 'simple' + +// CHECK-NEXT: matchdag { +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon1_0 // $t=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon1_2 // $d=getOperand(0), $t=getOperand(1) +// CHECK-NEXT: __anon1_2[src1] --[t]--> __anon1_0[dst] +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred1_1 +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred1_3 +// CHECK-NEXT: __anon1_0 ==> __anonpred1_1[mi] +// CHECK-NEXT: __anon1_2 ==> __anonpred1_3[mi] +// CHECK-NEXT: {{^}$}} + +// CHECK-NEXT: digraph "simple" { +// CHECK-NEXT: rankdir="BT" +// CHECK-NEXT: Node[[N1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon1_0|MOV|$t=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}"] +// CHECK-NEXT: Node[[N2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon1_2|MOV|Match starts here|$d=getOperand(0), $t=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$t"] +// CHECK-NEXT: Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred1_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred1_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] +// CHECK-NEXT: {{^}$}} + +def multiroot : GICombineRule< + (defs root:$d1, root:$d2), + (match (MOV $s, $s2), + (MOV $d1, $s), + (MOV $d2, $s)), + (apply [{ APPLY }])>; + +// CHECK-LABEL: Parsed rule defs/match for 'multiroot' + +// CHECK-NEXT: matchdag { +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon2_0 // $s=getOperand(0), $s2=getOperand(1) +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon2_2 // $d1=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon2_4 // $d2=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: __anon2_2[src1] --[s]--> __anon2_0[dst] +// CHECK-NEXT: __anon2_4[src1] --[s]--> __anon2_0[dst] +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred2_1 +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred2_3 +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred2_5 +// CHECK-NEXT: <<$mi0 == $mi1>>:$__anonpred2_6 +// CHECK-NEXT: __anon2_0 ==> __anonpred2_1[mi] +// CHECK-NEXT: __anon2_2 ==> __anonpred2_3[mi] +// CHECK-NEXT: __anon2_4 ==> __anonpred2_5[mi] +// CHECK-NEXT: __anon2_2[src1] ==> __anonpred2_6[mi0] +// CHECK-NEXT: __anon2_4[src1] ==> __anonpred2_6[mi1] +// CHECK-NEXT: {{^}$}} + +// CHECK-NEXT: digraph "multiroot" { +// CHECK-NEXT: rankdir="BT" +// CHECK-NEXT: Node[[N1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_0|MOV|$s=getOperand(0), $s2=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}"] +// CHECK-NEXT: Node[[N2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_2|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Node[[N3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_4|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s"] +// CHECK-NEXT: Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s"] +// CHECK-NEXT: Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_5|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P4:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred2_6|$mi0 == $mi1|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi0|#2 $mi1}}",style=dotted] +// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N3]]:s1:n -> Pred[[P4]]:d2:s [style=dotted] +// CHECK-NEXT: {{^}$}} + +def nonstandardroot : GICombineRule< + (defs root:$s), + (match (MOV $s, $s2), + (MOV $d1, $s), + (MOV $d2, $s)), + (apply [{ APPLY }])>; + +// CHECK-LABEL: Parsed rule defs/match for 'nonstandardroot' + +// CHECK-NEXT: matchdag { +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon3_0 // $s=getOperand(0), $s2=getOperand(1) +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon3_2 // $d1=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon3_4 // $d2=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: __anon3_2[src1] --[s]--> __anon3_0[dst] +// CHECK-NEXT: __anon3_4[src1] --[s]--> __anon3_0[dst] +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred3_1 +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred3_3 +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred3_5 +// CHECK-NEXT: <<$mi0 == $mi1>>:$__anonpred3_6 +// CHECK-NEXT: __anon3_0 ==> __anonpred3_1[mi] +// CHECK-NEXT: __anon3_2 ==> __anonpred3_3[mi] +// CHECK-NEXT: __anon3_4 ==> __anonpred3_5[mi] +// CHECK-NEXT: __anon3_2[src1] ==> __anonpred3_6[mi0] +// CHECK-NEXT: __anon3_4[src1] ==> __anonpred3_6[mi1] +// CHECK-NEXT: {{^}$}} + +// CHECK-NEXT: digraph "nonstandardroot" { +// CHECK-NEXT: rankdir="BT" +// CHECK-NEXT: Node[[N1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_0|MOV|Match starts here|$s=getOperand(0), $s2=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Node[[N2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_2|MOV|$d1=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}"] +// CHECK-NEXT: Node[[N3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_4|MOV|$d2=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}"] +// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s"] +// CHECK-NEXT: Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s"] +// CHECK-NEXT: Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_5|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P4:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred3_6|$mi0 == $mi1|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi0|#2 $mi1}}",style=dotted] +// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N3]]:s1:n -> Pred[[P4]]:d2:s [style=dotted] +// CHECK-NEXT: {{^}$}} + +def multiref_use : GICombineRule< + (defs root:$d1, root:$d2), + (match (MOV $d1, $s), + (MOV $d2, $s)), + (apply [{ APPLY }])>; + +// CHECK-LABEL: Parsed rule defs/match for 'multiref_use' + +// CHECK-NEXT: matchdag { +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon4_0 // $d1=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon4_2 // $d2=getOperand(0), $s=getOperand(1) +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred4_1 +// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred4_3 +// CHECK-NEXT: <<$mi0 == $mi1>>:$__anonpred4_4 +// CHECK-NEXT: __anon4_0 ==> __anonpred4_1[mi] +// CHECK-NEXT: __anon4_2 ==> __anonpred4_3[mi] +// CHECK-NEXT: __anon4_0[src1] ==> __anonpred4_4[mi0] +// CHECK-NEXT: __anon4_2[src1] ==> __anonpred4_4[mi1] +// CHECK-NEXT: {{^}$}} + +// CHECK-NEXT: digraph "multiref_use" { +// CHECK-NEXT: rankdir="BT" +// CHECK-NEXT: Node[[N1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon4_0|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Node[[N2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon4_2|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{#0 $dst|#1 $src1}}",color=red] +// CHECK-NEXT: Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred4_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred4_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi}}",style=dotted] +// CHECK-NEXT: Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred4_4|$mi0 == $mi1|{{0x[0-9a-f]+}}|{#0 $$|#1 $mi0|#2 $mi1}}",style=dotted] +// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N1]]:s1:n -> Pred[[P3]]:d1:s [style=dotted] +// CHECK-NEXT: Node[[N2]]:s1:n -> Pred[[P3]]:d2:s [style=dotted] +// CHECK-NEXT: {{^}$}} + +def MyCombiner: GICombinerHelper<"GenMyCombiner", [ + trivial, + simple, + multiroot, + nonstandardroot, + multiref_use +]>; + +// Verify we're sharing operand lists correctly +// CHECK-LABEL: GIMatchDagOperandListContext { +// CHECK-NEXT: OperandLists { +// CHECK-NEXT: 0:dst, 1:src1 +// CHECK-NEXT: 0:$, 1:mi +// CHECK-NEXT: 0:$, 1:mi0, 2:mi1 +// CHECK-NEXT: } +// CHECK-NEXT: } diff --git a/llvm/utils/TableGen/GICombinerEmitter.cpp b/llvm/utils/TableGen/GICombinerEmitter.cpp --- a/llvm/utils/TableGen/GICombinerEmitter.cpp +++ b/llvm/utils/TableGen/GICombinerEmitter.cpp @@ -12,7 +12,9 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringSet.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/ScopedPrinter.h" #include "llvm/Support/Timer.h" #include "llvm/TableGen/Error.h" #include "llvm/TableGen/StringMatcher.h" @@ -20,6 +22,7 @@ #include "CodeGenTarget.h" #include "GlobalISel/CodeExpander.h" #include "GlobalISel/CodeExpansions.h" +#include "GlobalISel/GIMatchDag.h" using namespace llvm; @@ -38,10 +41,25 @@ "gicombiner-show-expansions", cl::desc("Use C++ comments to indicate occurence of code expansion"), cl::cat(GICombinerEmitterCat)); +static cl::opt StopAfterParse( + "gicombiner-stop-after-parse", + cl::desc("Stop processing after parsing rules and dump state"), + cl::cat(GICombinerEmitterCat)); namespace { typedef uint64_t RuleID; +// We're going to be referencing the same small strings quite a lot for operand +// names and the like. Make their lifetime management simple with a global +// string table. +StringSet<> StrTab; + +StringRef insertStrTab(StringRef S) { + if (S.empty()) + return S; + return StrTab.insert(S).first->first(); +} + class RootInfo { StringRef PatternSymbol; @@ -52,12 +70,28 @@ }; class CombineRule { + struct VarInfo { + const GIMatchDagInstr *N; + const GIMatchDagOperand *Op; + const DagInit *Matcher; + + public: + VarInfo(const GIMatchDagInstr *N, const GIMatchDagOperand *Op, + const DagInit *Matcher) + : N(N), Op(Op), Matcher(Matcher) {} + }; + protected: /// A unique ID for this rule /// ID's are used for debugging and run-time disabling of rules among other /// things. RuleID ID; + /// A unique ID that can be used for anonymous objects belonging to this rule. + /// Used to create unique names in makeNameForAnon*() without making tests + /// overly fragile. + unsigned UID = 0; + /// The record defining this rule. const Record &TheDef; @@ -67,21 +101,36 @@ /// from the bottom of the function to the top. std::vector Roots; + GIMatchDag MatchDag; + /// A block of arbitrary C++ to finish testing the match. /// FIXME: This is a temporary measure until we have actual pattern matching const CodeInit *MatchingFixupCode = nullptr; + + bool parseInstructionMatcher(const CodeGenTarget &Target, StringInit *ArgName, + const Init &Arg, + StringMap> &NamedEdgeDefs, + StringMap> &NamedEdgeUses); + public: - CombineRule(const CodeGenTarget &Target, RuleID ID, const Record &R) - : ID(ID), TheDef(R) {} + CombineRule(const CodeGenTarget &Target, GIMatchDagContext &Ctx, RuleID ID, + const Record &R) + : ID(ID), TheDef(R), MatchDag(Ctx) {} + CombineRule(const CombineRule &) = delete; + bool parseDefs(); bool parseMatcher(const CodeGenTarget &Target); RuleID getID() const { return ID; } + unsigned allocUID() { return UID++; } StringRef getName() const { return TheDef.getName(); } const Record &getDef() const { return TheDef; } const CodeInit *getMatchingFixupCode() const { return MatchingFixupCode; } size_t getNumRoots() const { return Roots.size(); } + GIMatchDag &getMatchDag() { return MatchDag; } + const GIMatchDag &getMatchDag() const { return MatchDag; } + using const_root_iterator = std::vector::const_iterator; const_root_iterator roots_begin() const { return Roots.begin(); } const_root_iterator roots_end() const { return Roots.end(); } @@ -111,6 +160,34 @@ return nullptr; } +/// A convenience function to check that an Init refers to a dag whose operator +/// is a def that is a subclass of the given class and coerce it to a dag if it +/// is. This is primarily useful for testing for subclasses of GIMatchKind and +/// similar in DagInit's since DagInit's support any type inside them. +static const DagInit *getDagWithOperatorOfSubClass(const Init &N, + StringRef Cls) { + if (const DagInit *I = dyn_cast(&N)) + if (I->getNumArgs() > 0) + if (const DefInit *OpI = dyn_cast(I->getOperator())) + if (OpI->getDef()->isSubClassOf(Cls)) + return I; + return nullptr; +} + +StringRef makeNameForAnonInstr(CombineRule &Rule) { + return insertStrTab( + to_string(format("__anon%d_%d", Rule.getID(), Rule.allocUID()))); +} + +StringRef makeDebugName(CombineRule &Rule, StringRef Name) { + return insertStrTab(Name.empty() ? makeNameForAnonInstr(Rule) : StringRef(Name)); +} + +StringRef makeNameForAnonPredicate(CombineRule &Rule) { + return insertStrTab( + to_string(format("__anonpred%d_%d", Rule.getID(), Rule.allocUID()))); +} + bool CombineRule::parseDefs() { NamedRegionTimer T("parseDefs", "Time spent parsing the defs", "Rule Parsing", "Time spent on rule parsing", TimeRegions); @@ -149,9 +226,66 @@ return true; } +// Parse an (Instruction $a:Arg1, $b:Arg2, ...) matcher. Edges are formed +// between matching operand names between different matchers. +bool CombineRule::parseInstructionMatcher( + const CodeGenTarget &Target, StringInit *ArgName, const Init &Arg, + StringMap> &NamedEdgeDefs, + StringMap> &NamedEdgeUses) { + if (const DagInit *Matcher = + getDagWithOperatorOfSubClass(Arg, "Instruction")) { + auto &Instr = + Target.getInstruction(Matcher->getOperatorAsDef(TheDef.getLoc())); + + StringRef Name = ArgName ? ArgName->getValue() : ""; + + GIMatchDagInstr *N = + MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name), + MatchDag.getContext().makeOperandList(Instr)); + + N->setOpcodeAnnotation(&Instr); + const auto &P = MatchDag.addPredicateNode( + makeNameForAnonPredicate(*this), Instr); + MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]); + unsigned OpIdx = 0; + for (const auto &NameInit : Matcher->getArgNames()) { + StringRef Name = insertStrTab(NameInit->getAsUnquotedString()); + if (Name.empty()) + continue; + N->assignNameToOperand(OpIdx, Name); + + // Record the endpoints of any named edges. We'll add the cartesian + // product of edges later. + const auto &InstrOperand = N->getOperandInfo()[OpIdx]; + if (InstrOperand.isDef()) { + NamedEdgeDefs.try_emplace(Name); + NamedEdgeDefs[Name].emplace_back(N, &InstrOperand, Matcher); + } else { + NamedEdgeUses.try_emplace(Name); + NamedEdgeUses[Name].emplace_back(N, &InstrOperand, Matcher); + } + + if (InstrOperand.isDef()) { + if (find_if(Roots, [&](const RootInfo &X) { + return X.getPatternSymbol() == Name; + }) != Roots.end()) { + N->setMatchRoot(); + } + } + + OpIdx++; + } + + return true; + } + return false; +} + bool CombineRule::parseMatcher(const CodeGenTarget &Target) { NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher", "Rule Parsing", "Time spent on rule parsing", TimeRegions); + StringMap> NamedEdgeDefs; + StringMap> NamedEdgeUses; DagInit *Matchers = TheDef.getValueAsDag("Match"); if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") { @@ -167,6 +301,11 @@ // The match section consists of a list of matchers and predicates. Parse each // one and add the equivalent GIMatchDag nodes, predicates, and edges. for (unsigned I = 0; I < Matchers->getNumArgs(); ++I) { + if (parseInstructionMatcher(Target, Matchers->getArgName(I), + *Matchers->getArg(I), NamedEdgeDefs, + NamedEdgeUses)) + continue; + // Parse arbitrary C++ code we have in lieu of supporting MIR matching if (const CodeInit *CodeI = dyn_cast(Matchers->getArg(I))) { @@ -182,6 +321,63 @@ PrintNote("Pattern was `" + Matchers->getArg(I)->getAsString() + "'"); return false; } + + // Add the cartesian product of use -> def edges. + bool FailedToAddEdges = false; + for (const auto &NameAndDefs : NamedEdgeDefs) { + if (NameAndDefs.getValue().size() > 1) { + PrintError(TheDef.getLoc(), + "Two different MachineInstrs cannot def the same vreg"); + for (const auto &NameAndDefOp : NameAndDefs.getValue()) + PrintNote("in " + to_string(*NameAndDefOp.N) + " created from " + + to_string(*NameAndDefOp.Matcher) + ""); + FailedToAddEdges = true; + } + const auto &Uses = NamedEdgeUses[NameAndDefs.getKey()]; + for (const VarInfo &DefVar : NameAndDefs.getValue()) { + for (const VarInfo &UseVar : Uses) { + MatchDag.addEdge(insertStrTab(NameAndDefs.getKey()), UseVar.N, UseVar.Op, + DefVar.N, DefVar.Op); + } + } + } + if (FailedToAddEdges) + return false; + + // If a variable is referenced in multiple use contexts then we need a + // predicate to confirm they are the same operand. We can elide this if it's + // also referenced in a def context and we're traversing the def-use chain + // from the def to the uses but we can't know which direction we're going + // until after reorientToRoots(). + for (const auto &NameAndUses : NamedEdgeUses) { + const auto &Uses = NameAndUses.getValue(); + if (Uses.size() > 1) { + const auto &LeadingVar = Uses.front(); + for (const auto &Var : ArrayRef(Uses).drop_front()) { + // Add a predicate for each pair until we've covered the whole + // equivalence set. We could test the whole set in a single predicate + // but that means we can't test any equivalence until all the MO's are + // available which can lead to wasted work matching the DAG when this + // predicate can already be seen to have failed. + // + // We have a similar problem due to the need to wait for a particular MO + // before being able to test any of them. However, that is mitigated by + // the order in which we build the DAG. We build from the roots outwards + // so by using the first recorded use in all the predicates, we are + // making the dependency on one of the earliest visited references in + // the DAG. It's not guaranteed once the generated matcher is optimized + // (because the factoring the common portions of rules might change the + // visit order) but this should mean that these predicates depend on the + // first MO to become available. + const auto &P = MatchDag.addPredicateNode( + makeNameForAnonPredicate(*this)); + MatchDag.addPredicateDependency(LeadingVar.N, LeadingVar.Op, P, + &P->getOperandInfo()["mi0"]); + MatchDag.addPredicateDependency(Var.N, Var.Op, P, + &P->getOperandInfo()["mi1"]); + } + } + } return true; } @@ -190,6 +386,8 @@ const CodeGenTarget &Target; Record *Combiner; std::vector> Rules; + GIMatchDagContext MatchDagCtx; + std::unique_ptr makeCombineRule(const Record &R); void gatherRules(std::vector> &ActiveRules, @@ -246,12 +444,20 @@ std::unique_ptr GICombinerEmitter::makeCombineRule(const Record &TheDef) { std::unique_ptr Rule = - std::make_unique(Target, NumPatternTotal, TheDef); + std::make_unique(Target, MatchDagCtx, NumPatternTotal, TheDef); if (!Rule->parseDefs()) return nullptr; if (!Rule->parseMatcher(Target)) return nullptr; + LLVM_DEBUG(dbgs() << "Parsed rule defs/match for '" << Rule->getName() + << "'\n"); + LLVM_DEBUG(Rule->getMatchDag().dump()); + LLVM_DEBUG(Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName())); + if (StopAfterParse) { + return Rule; + } + // For now, don't support multi-root rules. We'll come back to this later // once we have the algorithm changes to support it. if (Rule->getNumRoots() > 1) { @@ -337,6 +543,12 @@ void GICombinerEmitter::run(raw_ostream &OS) { gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules")); + if (StopAfterParse) { + MatchDagCtx.print(errs()); + PrintNote(Combiner->getLoc(), + "Terminating due to -gicombiner-stop-after-parse"); + return; + } if (ErrorsPrinted) PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules"); diff --git a/llvm/utils/TableGen/GlobalISel/CMakeLists.txt b/llvm/utils/TableGen/GlobalISel/CMakeLists.txt --- a/llvm/utils/TableGen/GlobalISel/CMakeLists.txt +++ b/llvm/utils/TableGen/GlobalISel/CMakeLists.txt @@ -4,4 +4,10 @@ llvm_add_library(LLVMTableGenGlobalISel STATIC DISABLE_LLVM_LINK_LLVM_DYLIB CodeExpander.cpp + GIMatchDag.cpp + GIMatchDagEdge.cpp + GIMatchDagInstr.cpp + GIMatchDagOperands.cpp + GIMatchDagPredicate.cpp + GIMatchDagPredicateDependencyEdge.cpp ) diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDag.h b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h @@ -0,0 +1,124 @@ +//===- GIMatchDag.h - Represent a DAG to be matched -----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAG_H +#define LLVM_UTILS_TABLEGEN_GIMATCHDAG_H + +#include "GIMatchDagEdge.h" +#include "GIMatchDagInstr.h" +#include "GIMatchDagOperands.h" +#include "GIMatchDagPredicate.h" +#include "GIMatchDagPredicateDependencyEdge.h" + +namespace llvm { +class GIMatchDag; + +/// This class manages lifetimes for data associated with the GIMatchDag object. +class GIMatchDagContext { + GIMatchDagOperandListContext OperandListCtx; + +public: + const GIMatchDagOperandList &makeEmptyOperandList() { + return OperandListCtx.makeEmptyOperandList(); + } + + const GIMatchDagOperandList &makeOperandList(const CodeGenInstruction &I) { + return OperandListCtx.makeOperandList(I); + } + + const GIMatchDagOperandList &makeMIPredicateOperandList() { + return OperandListCtx.makeMIPredicateOperandList(); + } + + + const GIMatchDagOperandList &makeTwoMOPredicateOperandList() { + return OperandListCtx.makeTwoMOPredicateOperandList(); + } + + void print(raw_ostream &OS) const { + OperandListCtx.print(OS); + } + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +class GIMatchDag { +public: + using InstrNodesVec = std::vector>; + using EdgesVec = std::vector>; + using PredicateNodesVec = std::vector>; + + using PredicateDependencyEdgesVec = + std::vector>; + +protected: + GIMatchDagContext &Ctx; + InstrNodesVec InstrNodes; + PredicateNodesVec PredicateNodes; + EdgesVec Edges; + PredicateDependencyEdgesVec PredicateDependencies; + std::vector MatchRoots; + +public: + GIMatchDag(GIMatchDagContext &Ctx) + : Ctx(Ctx), InstrNodes(), PredicateNodes(), Edges(), + PredicateDependencies() {} + GIMatchDag(const GIMatchDag &) = delete; + + GIMatchDagContext &getContext() const { return Ctx; } + + template GIMatchDagInstr *addInstrNode(Args &&... args) { + auto Obj = + std::make_unique(*this, std::forward(args)...); + auto ObjRaw = Obj.get(); + InstrNodes.push_back(std::move(Obj)); + return ObjRaw; + } + + template + T *addPredicateNode(Args &&... args) { + auto Obj = std::make_unique(getContext(), std::forward(args)...); + auto ObjRaw = Obj.get(); + PredicateNodes.push_back(std::move(Obj)); + return ObjRaw; + } + + template GIMatchDagEdge *addEdge(Args &&... args) { + auto Obj = std::make_unique(std::forward(args)...); + auto ObjRaw = Obj.get(); + Edges.push_back(std::move(Obj)); + return ObjRaw; + } + + template + GIMatchDagPredicateDependencyEdge *addPredicateDependency(Args &&... args) { + auto Obj = std::make_unique( + std::forward(args)...); + auto ObjRaw = Obj.get(); + PredicateDependencies.push_back(std::move(Obj)); + return ObjRaw; + } + + void addMatchRoot(GIMatchDagInstr *N) { MatchRoots.push_back(N); } + + LLVM_DUMP_METHOD void print(raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + + void writeDOTGraph(raw_ostream &OS, StringRef ID) const; +}; + +raw_ostream &operator<<(raw_ostream &OS, const GIMatchDag &G); + +} // end namespace llvm + +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAG_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp @@ -0,0 +1,138 @@ +//===- GIMatchDag.cpp - A DAG representation of a pattern to be matched ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchDag.h" + +#include "llvm/Support/Format.h" +#include "llvm/TableGen/Record.h" +#include "../CodeGenInstruction.h" + +using namespace llvm; + +void GIMatchDag::writeDOTGraph(raw_ostream &OS, StringRef ID) const { + const auto writePorts = [&](StringRef Prefix, + const GIMatchDagOperandList &Operands) { + StringRef Separator = ""; + OS << "{"; + for (const auto &Op : enumerate(Operands)) { + OS << Separator << "<" << Prefix << format("%d", Op.index()) << ">" + << "#" << Op.index() << " $" << Op.value().getName(); + Separator = "|"; + } + OS << "}"; + }; + + OS << "digraph \"" << ID << "\" {\n" + << " rankdir=\"BT\"\n"; + for (const auto &N : InstrNodes) { + OS << " " << format("Node%p", &*N) << " [shape=record,label=\"{"; + writePorts("s", N->getOperandInfo()); + OS << "|" << N->getName(); + if (N->getOpcodeAnnotation()) + OS << "|" << N->getOpcodeAnnotation()->TheDef->getName(); + if (N->isMatchRoot()) + OS << "|Match starts here"; + OS << "|"; + SmallVector, 8> ToPrint; + for (const auto &Assignment : N->user_assigned_operand_names()) + ToPrint.emplace_back(Assignment.first, Assignment.second); + llvm::sort(ToPrint.begin(), ToPrint.end()); + StringRef Separator = ""; + for (const auto &Assignment : ToPrint) { + OS << Separator << "$" << Assignment.second << "=getOperand(" + << Assignment.first << ")"; + Separator = ", "; + } + OS << format("|%p|", &N); + writePorts("d", N->getOperandInfo()); + OS << "}\""; + if (N->isMatchRoot()) + OS << ",color=red"; + OS << "]\n"; + } + + for (const auto &E : Edges) { + const char *FromFmt = "Node%p:s%d:n"; + const char *ToFmt = "Node%p:d%d:s"; + if (E->getFromMO()->isDef() && !E->getToMO()->isDef()) + std::swap(FromFmt, ToFmt); + auto From = format(FromFmt, E->getFromMI(), E->getFromMO()->getIdx()); + auto To = format(ToFmt, E->getToMI(), E->getToMO()->getIdx()); + if (E->getFromMO()->isDef() && !E->getToMO()->isDef()) + std::swap(From, To); + + OS << " " << From << " -> " << To << " [label=\"$" << E->getName(); + if (E->getFromMO()->isDef() == E->getToMO()->isDef()) + OS << " INVALID EDGE!"; + OS << "\""; + if (E->getFromMO()->isDef() == E->getToMO()->isDef()) + OS << ",color=red"; + else if (E->getFromMO()->isDef() && !E->getToMO()->isDef()) + OS << ",dir=back,arrowtail=crow"; + OS << "]\n"; + } + + for (const auto &N : PredicateNodes) { + OS << " " << format("Pred%p", &*N) << " [shape=record,label=\"{"; + writePorts("s", N->getOperandInfo()); + OS << "|" << N->getName() << "|"; + N->printDescription(OS); + OS << format("|%p|", &N); + writePorts("d", N->getOperandInfo()); + OS << "}\",style=dotted]\n"; + } + + for (const auto &E : PredicateDependencies) { + const char *FromMIFmt = "Node%p:e"; + const char *FromMOFmt = "Node%p:s%d:n"; + const char *ToFmt = "Pred%p:d%d:s"; + auto To = format(ToFmt, E->getPredicate(), E->getPredicateOp()->getIdx()); + auto Style = "[style=dotted]"; + if (E->getRequiredMO()) { + auto From = + format(FromMOFmt, E->getRequiredMI(), E->getRequiredMO()->getIdx()); + OS << " " << From << " -> " << To << " " << Style << "\n"; + continue; + } + auto From = format(FromMIFmt, E->getRequiredMI()); + OS << " " << From << " -> " << To << " " << Style << "\n"; + } + + OS << "}\n"; +} + +LLVM_DUMP_METHOD void GIMatchDag::print(raw_ostream &OS) const { + OS << "matchdag {\n"; + for (const auto &N : InstrNodes) { + OS << " "; + N->print(OS); + OS << "\n"; + } + for (const auto &E : Edges) { + OS << " "; + E->print(OS); + OS << "\n"; + } + + for (const auto &P : PredicateNodes) { + OS << " "; + P->print(OS); + OS << "\n"; + } + for (const auto &D : PredicateDependencies) { + OS << " "; + D->print(OS); + OS << "\n"; + } + OS << "}\n"; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDag &G) { + G.print(OS); + return OS; +} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h @@ -0,0 +1,64 @@ +//===- GIMatchDagEdge.h - Represent a shared operand list for nodes -------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H +#define LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H + +#include "llvm/ADT/StringRef.h" + +namespace llvm { +class raw_ostream; +class GIMatchDagInstr; +class GIMatchDagOperand; + +/// Represents an edge that connects two instructions together via a pair of +/// operands. For example: +/// %a = FOO ... +/// %0 = BAR %a +/// %1 = BAZ %a +/// would have two edges for %a like so: +/// BAR:Op#1 --[a]----> Op#0:FOO +/// ^ +/// BAZ:Op#1 --[a]------/ +/// Ideally, all edges in the DAG are from a use to a def as this is a many +/// to one edge but edges from defs to uses are supported too. +class GIMatchDagEdge { + /// The name of the edge. For example, + /// (FOO $a, $b, $c) + /// (BAR $d, $e, $a) + /// will create an edge named 'a' to connect FOO to BAR. Although the name + /// refers to the edge, the canonical value of 'a' is the operand that defines + /// it. + StringRef Name; + const GIMatchDagInstr *FromMI; + const GIMatchDagOperand *FromMO; + const GIMatchDagInstr *ToMI; + const GIMatchDagOperand *ToMO; + +public: + GIMatchDagEdge(StringRef Name, const GIMatchDagInstr *FromMI, const GIMatchDagOperand *FromMO, + const GIMatchDagInstr *ToMI, const GIMatchDagOperand *ToMO) + : Name(Name), FromMI(FromMI), FromMO(FromMO), ToMI(ToMI), ToMO(ToMO) {} + + StringRef getName() const { return Name; } + const GIMatchDagInstr *getFromMI() const { return FromMI; } + const GIMatchDagOperand *getFromMO() const { return FromMO; } + const GIMatchDagInstr *getToMI() const { return ToMI; } + const GIMatchDagOperand *getToMO() const { return ToMO; } + + LLVM_DUMP_METHOD void print(raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const; +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagEdge &E); + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp @@ -0,0 +1,20 @@ +//===- GIMatchDagEdge.cpp - An edge describing a def/use lookup -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchDagEdge.h" +#include "GIMatchDagInstr.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +LLVM_DUMP_METHOD void GIMatchDagEdge::print(raw_ostream &OS) const { + OS << getFromMI()->getName() << "[" << getFromMO()->getName() << "] --[" + << Name << "]--> " << getToMI()->getName() << "[" << getToMO()->getName() + << "]"; +} + diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h @@ -0,0 +1,115 @@ +//===- GIMatchDagInstr.h - Represent a instruction to be matched ----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H +#define LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H + +#include "GIMatchDagOperands.h" + +#include "llvm/ADT/DenseMap.h" + +namespace llvm { +class GIMatchDag; + +/// Represents an instruction in the match DAG. This object knows very little +/// about the actual instruction to be matched as the bulk of that is in +/// predicates that are associated with the match DAG. It merely knows the names +/// and indices of any operands that need to be matched in order to allow edges +/// to link to them. +/// +/// Instances of this class objects are owned by the GIMatchDag and are not +/// shareable between instances of GIMatchDag. This is because the Name, +/// IsMatchRoot, and OpcodeAnnotation are likely to differ between GIMatchDag +/// instances. +class GIMatchDagInstr { +public: + using const_user_assigned_operand_names_iterator = + DenseMap::const_iterator; + +protected: + /// The match DAG this instruction belongs to. + GIMatchDag &Dag; + + /// The name of the instruction in the pattern. For example: + /// (FOO $a, $b, $c):$name + /// will cause name to be assigned to this member. Anonymous instructions will + /// have a name assigned for debugging purposes. + StringRef Name; + + /// The name of the instruction in the pattern as assigned by the user. For + /// example: + /// (FOO $a, $b, $c):$name + /// will cause name to be assigned to this member. If a name is not provided, + /// this will be empty. This name is used to bind variables from rules to the + /// matched instruction. + StringRef UserAssignedName; + + /// The name of each operand (if any) that was assigned by the user. For + /// example: + /// (FOO $a, $b, $c):$name + /// will cause {0, "a"}, {1, "b"}, {2, "c} to be inserted into this map. + DenseMap UserAssignedNamesForOperands; + + /// The operand list for this instruction. This object may be shared with + /// other instructions of a similar 'shape'. + const GIMatchDagOperandList &OperandInfo; + + /// For debugging purposes, it's helpful to have access to a description of + /// the Opcode. However, this object shouldn't use it for more than debugging + /// output since predicates are expected to be handled outside the DAG. + CodeGenInstruction *OpcodeAnnotation = 0; + + /// When true, this instruction will be a starting point for a match attempt. + bool IsMatchRoot = false; + +public: + GIMatchDagInstr(GIMatchDag &Dag, StringRef Name, StringRef UserAssignedName, + const GIMatchDagOperandList &OperandInfo) + : Dag(Dag), Name(Name), UserAssignedName(UserAssignedName), + OperandInfo(OperandInfo) {} + + const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; } + StringRef getName() const { return Name; } + void assignNameToOperand(unsigned Idx, StringRef Name) { + assert(UserAssignedNamesForOperands[Idx].empty() && "Cannot assign twice"); + UserAssignedNamesForOperands[Idx] = Name; + } + + const_user_assigned_operand_names_iterator + user_assigned_operand_names_begin() const { + return UserAssignedNamesForOperands.begin(); + } + const_user_assigned_operand_names_iterator + user_assigned_operand_names_end() const { + return UserAssignedNamesForOperands.end(); + } + iterator_range + user_assigned_operand_names() const { + return make_range(user_assigned_operand_names_begin(), + user_assigned_operand_names_end()); + } + + /// Mark this instruction as being a root of the match. This means that the + /// matcher will start from this node when attempting to match MIR. + void setMatchRoot(); + bool isMatchRoot() const { return IsMatchRoot; } + + void setOpcodeAnnotation(CodeGenInstruction *I) { OpcodeAnnotation = I; } + CodeGenInstruction *getOpcodeAnnotation() const { return OpcodeAnnotation; } + + void print(raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagInstr &N); + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp @@ -0,0 +1,50 @@ +//===- GIMatchDagInstr.cpp - A shared operand list for nodes --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchDagInstr.h" +#include "GIMatchDag.h" + +#include "llvm/TableGen/Record.h" + +#include "../CodeGenInstruction.h" + +using namespace llvm; + +void GIMatchDagInstr::print(raw_ostream &OS) const { + OS << "("; + if (getOpcodeAnnotation()) + OS << getOpcodeAnnotation()->TheDef->getName(); + else + OS << ""; + OS << " "; + OperandInfo.print(OS); + OS << "):$" << Name; + if (!UserAssignedNamesForOperands.empty()) { + OS << " // "; + SmallVector, 8> ToPrint; + for (const auto &Assignment : UserAssignedNamesForOperands) + ToPrint.emplace_back(Assignment.first, Assignment.second); + llvm::sort(ToPrint.begin(), ToPrint.end()); + StringRef Separator = ""; + for (const auto &Assignment : ToPrint) { + OS << Separator << "$" << Assignment.second << "=getOperand(" + << Assignment.first << ")"; + Separator = ", "; + } + } +} + +void GIMatchDagInstr::setMatchRoot() { + IsMatchRoot = true; + Dag.addMatchRoot(this); +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagInstr &N) { + N.print(OS); + return OS; +} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h @@ -0,0 +1,133 @@ +//===- GIMatchDagOperands.h - Represent a shared operand list for nodes ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H +#define LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H + +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/raw_ostream.h" + +#include + +namespace llvm { +class CodeGenInstruction; +/// Describes an operand of a MachineInstr w.r.t the DAG Matching. This +/// information is derived from CodeGenInstruction::Operands but is more +/// readily available for context-less access as we don't need to know which +/// instruction it's used with or know how many defs that instruction had. +/// +/// There may be multiple GIMatchDagOperand's with the same contents. However, +/// they are uniqued within the set of instructions that have the same overall +/// operand list. For example, given: +/// Inst1 operands ($dst:, $src1, $src2) +/// Inst2 operands ($dst:, $src1, $src2) +/// Inst3 operands ($dst:, $src) +/// $src1 will have a single instance of GIMatchDagOperand shared by Inst1 and +/// Inst2, as will $src2. $dst however, will have two instances one shared +/// between Inst1 and Inst2 and one unique to Inst3. We could potentially +/// fully de-dupe the GIMatchDagOperand instances but the saving is not expected +/// to be worth the overhead. +/// +/// The result of this is that the address of the object can be relied upon to +/// trivially identify commonality between two instructions which will be useful +/// when generating the matcher. When the pointers differ, the contents can be +/// inspected instead. +class GIMatchDagOperand { + unsigned Idx; + StringRef Name; + bool IsDef; + +public: + GIMatchDagOperand(unsigned Idx, StringRef Name, bool IsDef) + : Idx(Idx), Name(Name), IsDef(IsDef) {} + + unsigned getIdx() const { return Idx; } + StringRef getName() const { return Name; } + bool isDef() const { return IsDef; } + + /// This object isn't a FoldingSetNode but it's part of one. See FoldingSet + /// for details on the Profile function. + void Profile(FoldingSetNodeID &ID) const; + + /// A helper that behaves like Profile() but is also usable without the object. + /// We use size_t here to match enumerate<...>::index(). If we don't match + /// that the hashes won't be equal. + static void Profile(FoldingSetNodeID &ID, size_t Idx, StringRef Name, + bool IsDef); +}; + +/// A list of GIMatchDagOperands for an instruction without any association with +/// a particular instruction. +/// +/// An important detail to be aware of with this class is that they are shared +/// with other instructions of a similar 'shape'. For example, all the binary +/// instructions are likely to share a single GIMatchDagOperandList. This is +/// primarily a memory optimization as it's fairly common to have a large number +/// of instructions but only a few 'shapes'. +/// +/// See GIMatchDagOperandList::Profile() for the details on how they are folded. +class GIMatchDagOperandList : public FoldingSetNode { +public: + using value_type = GIMatchDagOperand; + +protected: + using vector_type = SmallVector; + +public: + using iterator = vector_type::iterator; + using const_iterator = vector_type::const_iterator; + +protected: + vector_type Operands; + StringMap OperandsByName; + +public: + void add(StringRef Name, unsigned Idx, bool IsDef); + + /// See FoldingSet for details. + void Profile(FoldingSetNodeID &ID) const; + + iterator begin() { return Operands.begin(); } + const_iterator begin() const { return Operands.begin(); } + iterator end() { return Operands.end(); } + const_iterator end() const { return Operands.end(); } + + const value_type &operator[](unsigned I) const { return Operands[I]; } + const value_type &operator[](StringRef K) const; + + void print(raw_ostream &OS) const; +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +/// This is the portion of GIMatchDagContext that directly relates to +/// GIMatchDagOperandList and GIMatchDagOperandList. +class GIMatchDagOperandListContext { + FoldingSet OperandLists; + std::vector> OperandListsOwner; + +public: + const GIMatchDagOperandList &makeEmptyOperandList(); + const GIMatchDagOperandList &makeOperandList(const CodeGenInstruction &I); + const GIMatchDagOperandList &makeMIPredicateOperandList(); + const GIMatchDagOperandList &makeTwoMOPredicateOperandList(); + + void print(raw_ostream &OS) const; +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp @@ -0,0 +1,153 @@ +//===- GIMatchDagOperands.cpp - A shared operand list for nodes -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchDagOperands.h" + +#include "../CodeGenInstruction.h" + +using namespace llvm; + +void GIMatchDagOperand::Profile(FoldingSetNodeID &ID) const { + Profile(ID, Idx, Name, IsDef); +} + +void GIMatchDagOperand::Profile(FoldingSetNodeID &ID, size_t Idx, + StringRef Name, bool IsDef) { + ID.AddInteger(Idx); + ID.AddString(Name); + ID.AddBoolean(IsDef); +} + +void GIMatchDagOperandList::add(StringRef Name, unsigned Idx, bool IsDef) { + assert(Idx == Operands.size() && "Operands added in wrong order"); + Operands.emplace_back(Operands.size(), Name, IsDef); + OperandsByName.try_emplace(Operands.back().getName(), Operands.size() - 1); +} + +void GIMatchDagOperandList::Profile(FoldingSetNodeID &ID) const { + for (const auto &I : enumerate(Operands)) + GIMatchDagOperand::Profile(ID, I.index(), I.value().getName(), + I.value().isDef()); +} + +void GIMatchDagOperandList::print(raw_ostream &OS) const { + if (Operands.empty()) { + OS << ""; + return; + } + StringRef Separator = ""; + for (const auto &I : Operands) { + OS << Separator << I.getIdx() << ":" << I.getName(); + if (I.isDef()) + OS << ""; + Separator = ", "; + } +} + +const GIMatchDagOperandList::value_type &GIMatchDagOperandList:: +operator[](StringRef K) const { + const auto &I = OperandsByName.find(K); + assert(I != OperandsByName.end() && "Operand not found by name"); + return Operands[I->second]; +} + +const GIMatchDagOperandList & +GIMatchDagOperandListContext::makeEmptyOperandList() { + FoldingSetNodeID ID; + + void *InsertPoint; + GIMatchDagOperandList *Value = + OperandLists.FindNodeOrInsertPos(ID, InsertPoint); + if (Value) + return *Value; + + std::unique_ptr NewValue = + std::make_unique(); + OperandLists.InsertNode(NewValue.get(), InsertPoint); + OperandListsOwner.push_back(std::move(NewValue)); + return *OperandListsOwner.back().get(); +} + +const GIMatchDagOperandList & +GIMatchDagOperandListContext::makeOperandList(const CodeGenInstruction &I) { + FoldingSetNodeID ID; + for (unsigned i = 0; i < I.Operands.size(); ++i) + GIMatchDagOperand::Profile(ID, i, I.Operands[i].Name, + i < I.Operands.NumDefs); + + void *InsertPoint; + GIMatchDagOperandList *Value = + OperandLists.FindNodeOrInsertPos(ID, InsertPoint); + if (Value) + return *Value; + + std::unique_ptr NewValue = + std::make_unique(); + for (unsigned i = 0; i < I.Operands.size(); ++i) + NewValue->add(I.Operands[i].Name, i, i < I.Operands.NumDefs); + OperandLists.InsertNode(NewValue.get(), InsertPoint); + OperandListsOwner.push_back(std::move(NewValue)); + return *OperandListsOwner.back().get(); +} + +const GIMatchDagOperandList & +GIMatchDagOperandListContext::makeMIPredicateOperandList() { + FoldingSetNodeID ID; + GIMatchDagOperand::Profile(ID, 0, "$", true); + GIMatchDagOperand::Profile(ID, 1, "mi", false); + + void *InsertPoint; + GIMatchDagOperandList *Value = + OperandLists.FindNodeOrInsertPos(ID, InsertPoint); + if (Value) + return *Value; + + std::unique_ptr NewValue = + std::make_unique(); + NewValue->add("$", 0, true); + NewValue->add("mi", 1, false); + OperandLists.InsertNode(NewValue.get(), InsertPoint); + OperandListsOwner.push_back(std::move(NewValue)); + return *OperandListsOwner.back().get(); +} + + +const GIMatchDagOperandList & +GIMatchDagOperandListContext::makeTwoMOPredicateOperandList() { + FoldingSetNodeID ID; + GIMatchDagOperand::Profile(ID, 0, "$", true); + GIMatchDagOperand::Profile(ID, 1, "mi0", false); + GIMatchDagOperand::Profile(ID, 2, "mi1", false); + + void *InsertPoint; + GIMatchDagOperandList *Value = + OperandLists.FindNodeOrInsertPos(ID, InsertPoint); + if (Value) + return *Value; + + std::unique_ptr NewValue = + std::make_unique(); + NewValue->add("$", 0, true); + NewValue->add("mi0", 1, false); + NewValue->add("mi1", 2, false); + OperandLists.InsertNode(NewValue.get(), InsertPoint); + OperandListsOwner.push_back(std::move(NewValue)); + return *OperandListsOwner.back().get(); +} + +void GIMatchDagOperandListContext::print(raw_ostream &OS) const { + OS << "GIMatchDagOperandListContext {\n" + << " OperandLists {\n"; + for (const auto &I : OperandLists) { + OS << " "; + I.print(OS); + OS << "\n"; + } + OS << " }\n" + << "}\n"; +} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h @@ -0,0 +1,105 @@ +//===- GIMatchDagPredicate - Represent a predicate to check ---------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H +#define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H + +#include "llvm/ADT/StringRef.h" +#include "GIMatchDag.h" +namespace llvm { +class CodeGenInstruction; +class GIMatchDagOperandList; +class GIMatchDagContext; +class raw_ostream; + +/// Represents a predicate on the match DAG. This records the details of the +/// predicate. The dependencies are stored in the GIMatchDag as edges. +/// +/// Instances of this class objects are owned by the GIMatchDag and are not +/// shareable between instances of GIMatchDag. +class GIMatchDagPredicate { +public: + enum GIMatchDagPredicateKind { + GIMatchDagPredicateKind_Opcode, + GIMatchDagPredicateKind_SameMO, + }; + +protected: + const GIMatchDagPredicateKind Kind; + + /// The name of the predicate. For example: + /// (FOO $a:s32, $b, $c) + /// will cause 's32' to be assigned to this member for the $a predicate. + /// Similarly, the opcode predicate will cause 'FOO' to be assigned to this + /// member. Anonymous instructions will have a name assigned for debugging + /// purposes. + StringRef Name; + + /// The operand list for this predicate. This object may be shared with + /// other predicates of a similar 'shape'. + const GIMatchDagOperandList &OperandInfo; + +public: + GIMatchDagPredicate(GIMatchDagPredicateKind Kind, StringRef Name, + const GIMatchDagOperandList &OperandInfo) + : Kind(Kind), Name(Name), OperandInfo(OperandInfo) {} + virtual ~GIMatchDagPredicate() {} + + GIMatchDagPredicateKind getKind() const { return Kind; } + + StringRef getName() const { return Name; } + const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; } + + virtual void print(raw_ostream &OS) const; + virtual void printDescription(raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + virtual LLVM_DUMP_METHOD void dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +class GIMatchDagOpcodePredicate : public GIMatchDagPredicate { + const CodeGenInstruction &Instr; + +public: + GIMatchDagOpcodePredicate(GIMatchDagContext &Ctx, StringRef Name, + const CodeGenInstruction &Instr); + + static bool classof(const GIMatchDagPredicate *P) { + return P->getKind() == GIMatchDagPredicateKind_Opcode; + } + + const CodeGenInstruction *getInstr() const { return &Instr; } + + void printDescription(raw_ostream &OS) const override; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +class GIMatchDagSameMOPredicate : public GIMatchDagPredicate { +public: + GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, StringRef Name); + + static bool classof(const GIMatchDagPredicate *P) { + return P->getKind() == GIMatchDagPredicateKind_SameMO; + } + + void printDescription(raw_ostream &OS) const override; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagPredicate &N); +raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagOpcodePredicate &N); + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp @@ -0,0 +1,53 @@ +//===- GIMatchDagPredicate.cpp - Represent a predicate to check -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchDagPredicate.h" +#include "llvm/TableGen/Record.h" + +#include "GIMatchDagOperands.h" +#include "../CodeGenInstruction.h" + +using namespace llvm; + +void GIMatchDagPredicate::print(raw_ostream &OS) const { + OS << "<<"; + printDescription(OS); + OS << ">>:$" << Name; +} + +void GIMatchDagPredicate::printDescription(raw_ostream &OS) const { OS << ""; } + +GIMatchDagOpcodePredicate::GIMatchDagOpcodePredicate( + GIMatchDagContext &Ctx, StringRef Name, const CodeGenInstruction &Instr) + : GIMatchDagPredicate(GIMatchDagPredicateKind_Opcode, Name, + Ctx.makeMIPredicateOperandList()), + Instr(Instr) {} + +void GIMatchDagOpcodePredicate::printDescription(raw_ostream &OS) const { + OS << "$mi.getOpcode() == " << Instr.TheDef->getName(); +} + +GIMatchDagSameMOPredicate::GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, + StringRef Name) + : GIMatchDagPredicate(GIMatchDagPredicateKind_SameMO, Name, + Ctx.makeTwoMOPredicateOperandList()) {} + +void GIMatchDagSameMOPredicate::printDescription(raw_ostream &OS) const { + OS << "$mi0 == $mi1"; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagPredicate &N) { + N.print(OS); + return OS; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, + const GIMatchDagOpcodePredicate &N) { + N.print(OS); + return OS; +} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h @@ -0,0 +1,60 @@ +//===- GIMatchDagPredicateDependencyEdge - Ensure predicates have inputs --===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H +#define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H + +#include "GIMatchDagOperands.h" + +namespace llvm { +class GIMatchDag; +class GIMatchDagInstr; +class GIMatchDagEdge; +class GIMatchDagPredicate; + +/// Represents a dependency that must be met to evaluate a predicate. +/// +/// Instances of this class objects are owned by the GIMatchDag and are not +/// shareable between instances of GIMatchDag. +class GIMatchDagPredicateDependencyEdge { + /// The MI that must be available in order to test the predicate. + const GIMatchDagInstr *RequiredMI; + /// The MO that must be available in order to test the predicate. May be + /// nullptr when only the MI is required. + const GIMatchDagOperand *RequiredMO; + /// The Predicate that requires information from RequiredMI/RequiredMO. + const GIMatchDagPredicate *Predicate; + /// The Predicate operand that requires information from + /// RequiredMI/RequiredMO. + const GIMatchDagOperand *PredicateOp; + +public: + GIMatchDagPredicateDependencyEdge(const GIMatchDagInstr *RequiredMI, + const GIMatchDagOperand *RequiredMO, + const GIMatchDagPredicate *Predicate, + const GIMatchDagOperand *PredicateOp) + : RequiredMI(RequiredMI), RequiredMO(RequiredMO), Predicate(Predicate), + PredicateOp(PredicateOp) {} + + const GIMatchDagInstr *getRequiredMI() const { return RequiredMI; } + const GIMatchDagOperand *getRequiredMO() const { return RequiredMO; } + const GIMatchDagPredicate *getPredicate() const { return Predicate; } + const GIMatchDagOperand *getPredicateOp() const { return PredicateOp; } + + void print(raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + LLVM_DUMP_METHOD void dump() const; +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + +raw_ostream &operator<<(raw_ostream &OS, + const GIMatchDagPredicateDependencyEdge &N); + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp @@ -0,0 +1,35 @@ +//===- GIMatchDagPredicateDependencyEdge.cpp - Have inputs before check ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchDagPredicateDependencyEdge.h" + +#include "GIMatchDagInstr.h" +#include "GIMatchDagPredicate.h" + +using namespace llvm; + +LLVM_DUMP_METHOD void +GIMatchDagPredicateDependencyEdge::print(raw_ostream &OS) const { + OS << getRequiredMI()->getName(); + if (getRequiredMO()) + OS << "[" << getRequiredMO()->getName() << "]"; + OS << " ==> " << getPredicate()->getName() << "[" + << getPredicateOp()->getName() << "]"; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void GIMatchDagPredicateDependencyEdge::dump() const { + print(errs()); +} +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + +raw_ostream &llvm::operator<<(raw_ostream &OS, + const GIMatchDagPredicateDependencyEdge &E) { + E.print(OS); + return OS; +}