diff --git a/llvm/docs/CommandGuide/tblgen.rst b/llvm/docs/CommandGuide/tblgen.rst --- a/llvm/docs/CommandGuide/tblgen.rst +++ b/llvm/docs/CommandGuide/tblgen.rst @@ -507,31 +507,19 @@ .. option:: -gen-global-isel-combiner - (Deprecated, pending removal) - Generate legacy GlobalISel combiner. - -.. option:: -gen-global-isel-combiner-matchtable - - Generate MatchTable-based GlobalISel combiner. + Generate GlobalISel combiner. .. option:: -combiners=list - Make -gen-global-isel-combiner and -gen-global-isel-combiner-matchtable - emit the specified combiners. - -.. option:: -gicombiner-show-expansions - - Make -gen-global-isel-combiner use C++ comments to indicate occurrences - of code expansion. + Make -gen-global-isel-combiner emit the specified combiners. -.. option:: -gicombiner-stop-after-build +.. option:: -gicombiner-debug-cxxpreds - Make -gen-global-isel-combiner stop processing after building the match tree. + Add debug comments to all C++ predicates emitted by -gen-global-isel-combiner .. option:: -gicombiner-stop-after-parse - Make -gen-global-isel-combiner and -gen-global-isel-combiner-matchtable stop - processing after parsing rules and dump state. + Make -gen-global-isel-combiner stop processing after parsing rules and dump state. .. option:: -gen-instr-info diff --git a/llvm/lib/Target/AArch64/CMakeLists.txt b/llvm/lib/Target/AArch64/CMakeLists.txt --- a/llvm/lib/Target/AArch64/CMakeLists.txt +++ b/llvm/lib/Target/AArch64/CMakeLists.txt @@ -10,13 +10,13 @@ tablegen(LLVM AArch64GenDisassemblerTables.inc -gen-disassembler) tablegen(LLVM AArch64GenFastISel.inc -gen-fast-isel) tablegen(LLVM AArch64GenGlobalISel.inc -gen-global-isel) -tablegen(LLVM AArch64GenO0PreLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AArch64GenO0PreLegalizeGICombiner.inc -gen-global-isel-combiner -combiners="AArch64O0PreLegalizerCombiner") -tablegen(LLVM AArch64GenPreLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AArch64GenPreLegalizeGICombiner.inc -gen-global-isel-combiner -combiners="AArch64PreLegalizerCombiner") -tablegen(LLVM AArch64GenPostLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AArch64GenPostLegalizeGICombiner.inc -gen-global-isel-combiner -combiners="AArch64PostLegalizerCombiner") -tablegen(LLVM AArch64GenPostLegalizeGILowering.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AArch64GenPostLegalizeGILowering.inc -gen-global-isel-combiner -combiners="AArch64PostLegalizerLowering") tablegen(LLVM AArch64GenInstrInfo.inc -gen-instr-info) tablegen(LLVM AArch64GenMCCodeEmitter.inc -gen-emitter) diff --git a/llvm/lib/Target/AMDGPU/CMakeLists.txt b/llvm/lib/Target/AMDGPU/CMakeLists.txt --- a/llvm/lib/Target/AMDGPU/CMakeLists.txt +++ b/llvm/lib/Target/AMDGPU/CMakeLists.txt @@ -17,11 +17,11 @@ set(LLVM_TARGET_DEFINITIONS AMDGPUGISel.td) tablegen(LLVM AMDGPUGenGlobalISel.inc -gen-global-isel) -tablegen(LLVM AMDGPUGenPreLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AMDGPUGenPreLegalizeGICombiner.inc -gen-global-isel-combiner -combiners="AMDGPUPreLegalizerCombiner") -tablegen(LLVM AMDGPUGenPostLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AMDGPUGenPostLegalizeGICombiner.inc -gen-global-isel-combiner -combiners="AMDGPUPostLegalizerCombiner") -tablegen(LLVM AMDGPUGenRegBankGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM AMDGPUGenRegBankGICombiner.inc -gen-global-isel-combiner -combiners="AMDGPURegBankCombiner") set(LLVM_TARGET_DEFINITIONS R600.td) diff --git a/llvm/lib/Target/Mips/CMakeLists.txt b/llvm/lib/Target/Mips/CMakeLists.txt --- a/llvm/lib/Target/Mips/CMakeLists.txt +++ b/llvm/lib/Target/Mips/CMakeLists.txt @@ -9,7 +9,7 @@ tablegen(LLVM MipsGenDisassemblerTables.inc -gen-disassembler) tablegen(LLVM MipsGenFastISel.inc -gen-fast-isel) tablegen(LLVM MipsGenGlobalISel.inc -gen-global-isel) -tablegen(LLVM MipsGenPostLegalizeGICombiner.inc -gen-global-isel-combiner-matchtable +tablegen(LLVM MipsGenPostLegalizeGICombiner.inc -gen-global-isel-combiner -combiners="MipsPostLegalizerCombiner") tablegen(LLVM MipsGenInstrInfo.inc -gen-instr-info) tablegen(LLVM MipsGenMCCodeEmitter.inc -gen-emitter) diff --git a/llvm/test/TableGen/GICombinerEmitter/defs-invalid.td b/llvm/test/TableGen/GICombinerEmitter/defs-invalid.td deleted file mode 100644 --- a/llvm/test/TableGen/GICombinerEmitter/defs-invalid.td +++ /dev/null @@ -1,42 +0,0 @@ -// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombiner %s 2>&1 | \ -// RUN: FileCheck -implicit-check-not=error: %s - -include "llvm/Target/Target.td" -include "llvm/Target/GlobalISel/Combine.td" - -def MyTargetISA : InstrInfo; -def MyTarget : Target { let InstructionSet = MyTargetISA; } - -def dummy; - -def missing_defs_node : GICombineRule< - (dummy), - (dummy), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected defs operator -// CHECK-NEXT: def missing_defs_node : GICombineRule< -// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule - -def no_roots : GICombineRule< - (defs), - (dummy), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Combine rules must have at least one root -// CHECK-NEXT: def no_roots : GICombineRule< -// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule - -def unknown_kind : GICombineRule< - (defs dummy:$a), - (dummy), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected a subclass of GIDefKind or a sub-dag whose operator is of type GIDefKindWithArgs -// CHECK-NEXT: def unknown_kind : GICombineRule< -// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule - -def MyCombiner: GICombinerHelper<"GenMyCombiner", [ -// CHECK: :[[@LINE-1]]:{{[0-9]+}}: error: Failed to parse one or more rules - missing_defs_node, - no_roots, - unknown_kind -]>; diff --git a/llvm/test/TableGen/GICombinerEmitter/match-invalid.td b/llvm/test/TableGen/GICombinerEmitter/match-invalid.td deleted file mode 100644 --- a/llvm/test/TableGen/GICombinerEmitter/match-invalid.td +++ /dev/null @@ -1,81 +0,0 @@ -// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombiner %s 2>&1 | \ -// RUN: FileCheck -implicit-check-not=error: %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 missing_match_node : GICombineRule< - (defs root:$a), - (dummy), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected match operator -// CHECK-NEXT: def missing_match_node : GICombineRule< -// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule - -def null_matcher : GICombineRule< - (defs root:$a), - (match), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Matcher is empty -// CHECK-NEXT: def null_matcher : GICombineRule< -// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule - -def unknown_kind1 : GICombineRule< - (defs root:$a), - (match 0), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected a subclass of GIMatchKind or a sub-dag whose operator is either of a GIMatchKindWithArgs or Instruction -// CHECK-NEXT: def unknown_kind1 : GICombineRule< -// CHECK: :[[@LINE-6]]:{{[0-9]+}}: error: Failed to parse rule - -def unknown_kind2 : GICombineRule< - (defs root:$a), - (match (dummy)), - (dummy)>; -// CHECK: :[[@LINE-4]]:{{[0-9]+}}: error: Expected a subclass of GIMatchKind or a sub-dag whose operator is either of a GIMatchKindWithArgs or Instruction -// 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), - (MOV $a, $b)), - (dummy)>; -// CHECK-NOT: :[[@LINE-5]]:{{[0-9]+}}: error: - -def MyCombiner: GICombinerHelper<"GenMyCombiner", [ -// CHECK: :[[@LINE-1]]:{{[0-9]+}}: error: Failed to parse one or more rules - missing_match_node, - 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/match-tree.td b/llvm/test/TableGen/GICombinerEmitter/match-tree.td deleted file mode 100644 --- a/llvm/test/TableGen/GICombinerEmitter/match-tree.td +++ /dev/null @@ -1,315 +0,0 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombinerHelper -gicombiner-stop-after-build %s \ -// RUN: -o %t.inc | FileCheck %s -// -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombinerHelper %s | \ -// RUN: FileCheck --check-prefix=CODE %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 ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; -def SUB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; -def MUL : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; -def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def ICMP : I<(outs GPR32:$dst), (ins GPR32:$tst, GPR32:$src1, GPR32:$src2), []>; - -def HasFoo : Predicate<"Subtarget->hasFoo()">; -def HasAnswerToEverything : Predicate<"Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42">; - -def Rule0 : GICombineRule< - (defs root:$d), - (match (MUL $t, $s1, $s2), - (SUB $d, $t, $s3)), - (apply [{ APPLY }])>; - -def Rule1 : GICombineRule< - (defs root:$d), - (match (MOV $s1, $s2), - (MOV $d, $s1)), - (apply [{ APPLY }])>; - -def Rule2 : GICombineRule< - (defs root:$d), - (match (MOV $d, $s)), - (apply [{ APPLY }])>; - -def Rule3 : GICombineRule< - (defs root:$d), - (match (MUL $t, $s1, $s2), - (ADD $d, $t, $s3), [{ A }]), - (apply [{ APPLY }])>; - -def Rule4 : GICombineRule< - (defs root:$d), - (match (ADD $d, $s1, $s2)), - (apply [{ APPLY }])>; - -let Predicates = [HasFoo] in -def Rule5 : GICombineRule< - (defs root:$d), - (match (SUB $d, $s1, $s2)), - (apply [{ APPLY }])>; - -let Predicates = [HasFoo, HasAnswerToEverything] in -def Rule6 : GICombineRule< - (defs root:$d), - (match (SEXT $t, $s1), - (TRUNC $d, $t)), - (apply [{ APPLY }])>; - -def Rule7 : GICombineRule< - (defs root:$d), - (match (ZEXT $t, $s1), - (TRUNC $d, $t)), - (apply [{ APPLY }])>; - -// Rules 8&9 check that the partitions are formed correctly if -// - there is an edge different from Operand(1) -> Operand(0) -// - more than one leaf is ignored because the leaf does not -// care about the instruction -// - a single instruction has more operands than all others -// These conditions triggered a crash when emitting the -// resulting source code. -def Rule8 : GICombineRule< - (defs root:$d), - (match (ICMP $ic, $cc, $s2, $s3), - (ZEXT $z, $ic), - (MUL $d, $t, $z), - [{ MATCH }]), - (apply [{ APPLY }])>; - -def Rule9 : GICombineRule< - (defs root:$d), - (match (MUL $d, $t, $z)), - (apply [{ APPLY }])>; - -def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ - Rule0, - Rule1, - Rule2, - Rule3, - Rule4, - Rule5, - Rule6, - Rule7, - Rule8, - Rule9 -]>; - -// CHECK-LABEL: digraph "matchtree" { -// CHECK-DAG: Node[[N0:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[0].getOpcode()|5 partitions|Rule0,Rule1,Rule2,Rule3,Rule4,Rule5,Rule6,Rule7,Rule8,Rule9}"] -// CHECK-DAG: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule0,Rule5}"] -// CHECK-DAG: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule0,Rule5}"] -// CHECK-DAG: Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule0}"] -// CHECK-DAG: Node[[N4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule5}"] -// CHECK-DAG: Node[[N5:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule5}"] -// CHECK-DAG: Node[[N6:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule1,Rule2}"] -// CHECK-DAG: Node[[N7:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule1,Rule2}"] -// CHECK-DAG: Node[[N8:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule1}"] -// CHECK-DAG: Node[[N9:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule2}"] -// CHECK-DAG: Node[[N10:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule2}"] -// CHECK-DAG: Node[[N11:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule3,Rule4}"] -// CHECK-DAG: Node[[N12:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule3,Rule4}"] -// CHECK-DAG: Node[[N13:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule3,Rule4}",color=red] -// CHECK-DAG: Node[[N14:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule4}"] -// CHECK-DAG: Node[[N15:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule4}"] -// CHECK-DAG: Node[[N16:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|1 partitions|Rule6,Rule7}"] -// CHECK-DAG: Node[[N17:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule6,Rule7}"] -// CHECK-DAG: Node[[N18:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule6}"] -// CHECK-DAG: Node[[N19:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule7}"] -// CHECK-DAG: Node[[N20:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(2))|2 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N21:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N22:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[2] = getVRegDef(MI[1].getOperand(1))|1 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N23:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[2].getOpcode()|2 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N24:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule8,Rule9}",color=red] -// CHECK-DAG: Node[[N25:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"] -// CHECK-DAG: Node[[N26:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"] -// CHECK-DAG: Node[[N27:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"] - -// The most important partitioner is on the first opcode: -// CHECK-DAG: Node[[N0]] -> Node[[N1]] [label="#0 MyTarget::SUB"] -// CHECK-DAG: Node[[N0]] -> Node[[N6]] [label="#1 MyTarget::MOV"] -// CHECK-DAG: Node[[N0]] -> Node[[N11]] [label="#2 MyTarget::ADD"] -// CHECK-DAG: Node[[N0]] -> Node[[N16]] [label="#3 MyTarget::TRUNC"] -// CHECK-DAG: Node[[N0]] -> Node[[N20]] [label="#4 MyTarget::MUL"] - -// For, MI[0].getOpcode() == SUB, then has to determine whether it has a reg -// operand and follow that link. If it can't then Rule5 is the only choice as -// that rule is not constrained to a reg. -// CHECK-DAG: Node[[N1]] -> Node[[N2]] [label="#0 true"] -// CHECK-DAG: Node[[N1]] -> Node[[N5]] [label="#1 false"] - -// For, MI[0].getOpcode() == SUB && MI[0].getOperand(1).isReg(), if MI[1] is a -// MUL then it must be either Rule0 or Rule5. Rule0 is fully tested so Rule5 is -// unreachable. If it's not MUL then it must be Rule5. -// CHECK-DAG: Node[[N2]] -> Node[[N3]] [label="#0 MyTarget::MUL"] -// CHECK-DAG: Node[[N2]] -> Node[[N4]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N6]] -> Node[[N7]] [label="#0 true"] -// CHECK-DAG: Node[[N6]] -> Node[[N10]] [label="#1 false"] - -// CHECK-DAG: Node[[N7]] -> Node[[N8]] [label="#0 MyTarget::MOV"] -// CHECK-DAG: Node[[N7]] -> Node[[N9]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N11]] -> Node[[N12]] [label="#0 true"] -// CHECK-DAG: Node[[N11]] -> Node[[N15]] [label="#1 false"] - -// CHECK-DAG: Node[[N12]] -> Node[[N13]] [label="#0 MyTarget::MUL"] -// CHECK-DAG: Node[[N12]] -> Node[[N14]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N16]] -> Node[[N17]] [label="#0 true"] - -// CHECK-DAG: Node[[N17]] -> Node[[N18]] [label="#0 MyTarget::SEXT"] -// CHECK-DAG: Node[[N17]] -> Node[[N19]] [label="#1 MyTarget::ZEXT"] - -// Follow the links for MI[0].getOpcode() == MUL. -// CHECK-DAG: Node[[N20]] -> Node[[N21]] [label="#0 true"] -// CHECK-DAG: Node[[N20]] -> Node[[N27]] [label="#1 false"] - -// CHECK-DAG: Node[[N21]] -> Node[[N22]] [label="#0 MyTarget::ZEXT"] -// CHECK-DAG: Node[[N21]] -> Node[[N26]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N22]] -> Node[[N23]] [label="#0 true"] - -// CHECK-DAG: Node[[N23]] -> Node[[N24]] [label="#0 MyTarget::ICMP"] -// CHECK-DAG: Node[[N23]] -> Node[[N25]] [label="#1 * or nullptr"] - - -// CHECK-LABEL: {{^}$}} - - -// Check the generated source code. - -// CODE-LABEL: GenMyCombinerHelper::tryCombineAll - -// Check the first partition. The numbers correspond to the labels above. -// CODE: switch (MIs[0]->getOpcode()) { -// CODE-NEXT: case MyTarget::SUB: Partition = 0; break; -// CODE-NEXT: case MyTarget::MOV: Partition = 1; break; -// CODE-NEXT: case MyTarget::ADD: Partition = 2; break; -// CODE-NEXT: case MyTarget::TRUNC: Partition = 3; break; -// CODE-NEXT: case MyTarget::MUL: Partition = 4; break; -// CODE-NEXT: } - -// Check that the correct partition is choosen if operand 1 is a register. - -// CODE: if (Partition == 0 /* MyTarget::SUB */) { -// CODE-NEXT: Partition = -1; -// CODE-NEXT: if (MIs.size() <= 1) MIs.resize(2); -// CODE-NEXT: MIs[1] = nullptr; -// CODE-NEXT: if (MIs[0]->getOperand(1).isReg()) -// CODE-NEXT: MIs[1] = MRI.getVRegDef(MIs[0]->getOperand(1).getReg()); -// CODE-NEXT: if (MIs[1] == nullptr) Partition = 1; -// CODE-NEXT: if (MIs[1] != nullptr) Partition = 0; - - -// Check that the MUL opcode is tested. - -// CODE: if (Partition == 0 /* true */) { -// CODE-NEXT: Partition = -1; -// CODE-NEXT: switch (MIs[1]->getOpcode()) { -// CODE-NEXT: case MyTarget::MUL: Partition = 0; break; -// CODE-NEXT: default: Partition = 1; break; -// CODE-NEXT: } - -// Check that action for MUL is executed. - -// CODE: if (Partition == 0 /* MyTarget::MUL */) { -// CODE-NEXT: // Leaf name: Rule0 -// CODE-NEXT: // Rule: Rule0 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(0)) { -// CODE-NEXT: if (1 -// CODE-NEXT:) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule0'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } -// CODE-NEXT: llvm_unreachable("Combine rule elision was incorrect"); -// CODE-NEXT: return false; -// CODE-NEXT: } - -// Check that the other rule involving SUB (Rule5) is run otherwise. - -// CODE-NEXT: if (Partition == 1 /* * or nullptr */) { -// CODE-NEXT: // Leaf name: Rule5 -// CODE-NEXT: // Rule: Rule5 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(5)) { -// CODE-NEXT: if (1 -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasFoo -// CODE-NEXT: Subtarget->hasFoo() -// CODE-NEXT: ) -// CODE-NEXT:) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule5'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } -// CODE-NEXT: llvm_unreachable("Combine rule elision was incorrect"); -// CODE-NEXT: return false; -// CODE-NEXT: } -// CODE-NEXT: } - -// Check that Rule5 is run if operand 1 is not MUL. - -// CODE-NEXT: if (Partition == 1 /* false */) { -// CODE-NEXT: // Leaf name: Rule5 -// CODE-NEXT: // Rule: Rule5 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(5)) { -// CODE-NEXT: if (1 -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasFoo -// CODE-NEXT: Subtarget->hasFoo() -// CODE-NEXT: ) -// CODE-NEXT: ) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule5'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } -// CODE-NEXT: llvm_unreachable("Combine rule elision was incorrect"); -// CODE-NEXT: return false; -// CODE-NEXT: } -// CODE-NEXT: } - - -// Check multiple predicates are correctly emitted - -// CODE: // Leaf name: Rule6 -// CODE-NEXT: // Rule: Rule6 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(6)) { -// CODE-NEXT: if (1 -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasFoo -// CODE-NEXT: Subtarget->hasFoo() -// CODE-NEXT: ) -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasAnswerToEverything -// CODE-NEXT: Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42 -// CODE-NEXT: ) -// CODE-NEXT: ) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule6'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } diff --git a/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td b/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td deleted file mode 100644 --- a/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td +++ /dev/null @@ -1,215 +0,0 @@ -// 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 -// REQUIRES: asserts - -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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon0_0|MOV|Match starts here|$d=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred0_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon1_0|MOV|$t=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon1_2|MOV|Match starts here|$d=getOperand(0), $t=getOperand(1)|{{(0x)?[0-9a-fA-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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred1_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred1_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_0|MOV|$s=getOperand(0), $s2=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_2|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_4|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_5|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred2_6|$mi0 == $mi1|{{(0x)?[0-9a-fA-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_0[dst] --[s]--> __anon3_2[src1] -// CHECK-NEXT: __anon3_0[dst] --[s]--> __anon3_4[src1] -// 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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_0|MOV|Match starts here|$s=getOperand(0), $s2=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_2|MOV|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_4|MOV|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow] -// CHECK-NEXT: Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_5|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred3_6|$mi0 == $mi1|{{(0x)?[0-9a-fA-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-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon4_0|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon4_2|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred4_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred4_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred4_4|$mi0 == $mi1|{{(0x)?[0-9a-fA-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/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-imms.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-imms.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-imms.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-imms.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-imms.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-imms.td @@ -1,4 +1,4 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -combiners=MyCombiner %s | \ // RUN: FileCheck %s diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-operand-types.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-operand-types.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-operand-types.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-operand-types.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-operand-types.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-operand-types.td @@ -1,4 +1,4 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -combiners=MyCombiner %s | \ // RUN: FileCheck %s diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-patfrag-root.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-patfrag-root.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-patfrag-root.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-patfrag-root.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-patfrag-root.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-patfrag-root.td @@ -1,5 +1,5 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ -// RUN: -combiners=MyCombiner -gicombiner-matchtable-debug-cxxpreds %s | \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ +// RUN: -combiners=MyCombiner -gicombiner-debug-cxxpreds %s | \ // RUN: FileCheck %s include "llvm/Target/Target.td" diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-permutations.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-permutations.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-permutations.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-permutations.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-permutations.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-permutations.td @@ -1,5 +1,5 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ -// RUN: -combiners=MyCombiner -gicombiner-matchtable-debug-cxxpreds %s | \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ +// RUN: -combiners=MyCombiner -gicombiner-debug-cxxpreds %s | \ // RUN: FileCheck %s include "llvm/Target/Target.td" diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-variadics.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-variadics.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-variadics.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-variadics.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table-variadics.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table-variadics.td @@ -1,4 +1,4 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -combiners=MyCombiner %s | \ // RUN: FileCheck %s diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/match-table.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/match-table.td @@ -1,4 +1,4 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -combiners=MyCombiner %s | \ // RUN: FileCheck %s diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/operand-types.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/operand-types.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/operand-types.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/operand-types.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/operand-types.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/operand-types.td @@ -1,4 +1,4 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -gicombiner-stop-after-parse -combiners=MyCombiner %s | \ // RUN: FileCheck %s diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/patfrag-errors.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/patfrag-errors.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/patfrag-errors.td @@ -1,4 +1,4 @@ -// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -combiners=MyCombiner %s 2>&1| \ // RUN: FileCheck %s -implicit-check-not=error: diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-errors.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-errors.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-errors.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-errors.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-errors.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-errors.td @@ -1,4 +1,4 @@ -// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -combiners=MyCombiner %s 2>&1| \ // RUN: FileCheck %s -implicit-check-not=error: diff --git a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td b/llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-parsing.td rename from llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td rename to llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-parsing.td --- a/llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td +++ b/llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-parsing.td @@ -1,4 +1,4 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ // RUN: -gicombiner-stop-after-parse -combiners=MyCombiner %s | \ // RUN: FileCheck %s diff --git a/llvm/utils/TableGen/CMakeLists.txt b/llvm/utils/TableGen/CMakeLists.txt --- a/llvm/utils/TableGen/CMakeLists.txt +++ b/llvm/utils/TableGen/CMakeLists.txt @@ -59,8 +59,7 @@ DXILEmitter.cpp ExegesisEmitter.cpp FastISelEmitter.cpp - GICombinerEmitter.cpp - GlobalISelCombinerMatchTableEmitter.cpp + GlobalISelCombinerEmitter.cpp GlobalISelEmitter.cpp GlobalISelMatchTable.cpp GlobalISelMatchTableExecutorEmitter.cpp diff --git a/llvm/utils/TableGen/GICombinerEmitter.cpp b/llvm/utils/TableGen/GICombinerEmitter.cpp deleted file mode 100644 --- a/llvm/utils/TableGen/GICombinerEmitter.cpp +++ /dev/null @@ -1,1044 +0,0 @@ -//===- GlobalCombinerEmitter.cpp - Generate a combiner --------------------===// -// -// 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 -// -//===----------------------------------------------------------------------===// -// -/// \file Generate a combiner implementation for GlobalISel from a declarative -/// syntax -/// -//===----------------------------------------------------------------------===// - -#include "CodeGenTarget.h" -#include "GlobalISel/CodeExpander.h" -#include "GlobalISel/CodeExpansions.h" -#include "GlobalISel/CombinerUtils.h" -#include "GlobalISel/GIMatchDag.h" -#include "GlobalISel/GIMatchDagEdge.h" -#include "GlobalISel/GIMatchDagInstr.h" -#include "GlobalISel/GIMatchDagOperands.h" -#include "GlobalISel/GIMatchDagPredicate.h" -#include "GlobalISel/GIMatchTree.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/StringSet.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/ScopedPrinter.h" -#include "llvm/TableGen/Error.h" -#include "llvm/TableGen/Record.h" -#include "llvm/TableGen/StringMatcher.h" -#include "llvm/TableGen/TableGenBackend.h" -#include - -using namespace llvm; - -#define DEBUG_TYPE "gicombiner-emitter" - -// FIXME: Use ALWAYS_ENABLED_STATISTIC once it's available. -unsigned NumPatternTotal = 0; -STATISTIC(NumPatternTotalStatistic, "Total number of patterns"); - -cl::OptionCategory - GICombinerEmitterCat("Options for -gen-global-isel-combiner"); -cl::list - SelectedCombiners("combiners", cl::desc("Emit the specified combiners"), - cl::cat(GICombinerEmitterCat), cl::CommaSeparated); -static cl::opt ShowExpansions( - "gicombiner-show-expansions", - cl::desc("Use C++ comments to indicate occurence of code expansion"), - cl::cat(GICombinerEmitterCat)); -cl::opt StopAfterParse( - "gicombiner-stop-after-parse", - cl::desc("Stop processing after parsing rules and dump state"), - cl::cat(GICombinerEmitterCat)); -static cl::opt StopAfterBuild( - "gicombiner-stop-after-build", - cl::desc("Stop processing after building the match tree"), - 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 format_partition_name { - const GIMatchTree &Tree; - unsigned Idx; - -public: - format_partition_name(const GIMatchTree &Tree, unsigned Idx) - : Tree(Tree), Idx(Idx) {} - void print(raw_ostream &OS) const { - Tree.getPartitioner()->emitPartitionName(OS, Idx); - } -}; -raw_ostream &operator<<(raw_ostream &OS, const format_partition_name &Fmt) { - Fmt.print(OS); - return OS; -} - -/// Declares data that is passed from the match stage to the apply stage. -class MatchDataInfo { - /// The symbol used in the tablegen patterns - StringRef PatternSymbol; - /// The data type for the variable - StringRef Type; - /// The name of the variable as declared in the generated matcher. - std::string VariableName; - -public: - MatchDataInfo(StringRef PatternSymbol, StringRef Type, StringRef VariableName) - : PatternSymbol(PatternSymbol), Type(Type), VariableName(VariableName) {} - - StringRef getPatternSymbol() const { return PatternSymbol; }; - StringRef getType() const { return Type; }; - StringRef getVariableName() const { return VariableName; }; -}; - -class RootInfo { - StringRef PatternSymbol; - -public: - RootInfo(StringRef PatternSymbol) : PatternSymbol(PatternSymbol) {} - - StringRef getPatternSymbol() const { return PatternSymbol; } -}; - -class CombineRule { -public: - - using const_matchdata_iterator = std::vector::const_iterator; - - 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; - - /// The roots of a match. These are the leaves of the DAG that are closest to - /// the end of the function. I.e. the nodes that are encountered without - /// following any edges of the DAG described by the pattern as we work our way - /// 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 StringInit *MatchingFixupCode = nullptr; - - /// The MatchData defined by the match stage and required by the apply stage. - /// This allows the plumbing of arbitrary data from C++ predicates between the - /// stages. - /// - /// For example, suppose you have: - /// %A = - /// %0 = G_ADD %1, %A - /// you could define a GIMatchPredicate that walks %A, constant folds as much - /// as possible and returns an APInt containing the discovered constant. You - /// could then declare: - /// def apint : GIDefMatchData<"APInt">; - /// add it to the rule with: - /// (defs root:$root, apint:$constant) - /// evaluate it in the pattern with a C++ function that takes a - /// MachineOperand& and an APInt& with: - /// (match [{MIR %root = G_ADD %0, %A }], - /// (constantfold operand:$A, apint:$constant)) - /// and finally use it in the apply stage with: - /// (apply (create_operand - /// [{ MachineOperand::CreateImm(${constant}.getZExtValue()); - /// ]}, apint:$constant), - /// [{MIR %root = FOO %0, %constant }]) - std::vector MatchDataDecls; - - void declareMatchData(StringRef PatternSymbol, StringRef Type, - StringRef VarName); - - bool parseInstructionMatcher(const CodeGenTarget &Target, StringInit *ArgName, - const Init &Arg, - StringMap> &NamedEdgeDefs, - StringMap> &NamedEdgeUses); - bool parseWipMatchOpcodeMatcher(const CodeGenTarget &Target, - StringInit *ArgName, const Init &Arg); - -public: - 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 StringInit *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(); } - iterator_range roots() const { - return llvm::make_range(Roots.begin(), Roots.end()); - } - - iterator_range matchdata_decls() const { - return make_range(MatchDataDecls.begin(), MatchDataDecls.end()); - } - - /// Export expansions for this rule - void declareExpansions(CodeExpansions &Expansions) const { - for (const auto &I : matchdata_decls()) - Expansions.declare(I.getPatternSymbol(), I.getVariableName()); - } - - /// The matcher will begin from the roots and will perform the match by - /// traversing the edges to cover the whole DAG. This function reverses DAG - /// edges such that everything is reachable from a root. This is part of the - /// preparation work for flattening the DAG into a tree. - void reorientToRoots() { - SmallSet Roots; - SmallSet Visited; - SmallSet EdgesRemaining; - - for (auto &I : MatchDag.roots()) { - Roots.insert(I); - Visited.insert(I); - } - for (auto &I : MatchDag.edges()) - EdgesRemaining.insert(I); - - bool Progressed = false; - SmallSet EdgesToRemove; - while (!EdgesRemaining.empty()) { - for (auto *EI : EdgesRemaining) { - if (Visited.count(EI->getFromMI())) { - if (Roots.count(EI->getToMI())) - PrintError(TheDef.getLoc(), "One or more roots are unnecessary"); - Visited.insert(EI->getToMI()); - EdgesToRemove.insert(EI); - Progressed = true; - } - } - for (GIMatchDagEdge *ToRemove : EdgesToRemove) - EdgesRemaining.erase(ToRemove); - EdgesToRemove.clear(); - - for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end(); - EI != EE; ++EI) { - if (Visited.count((*EI)->getToMI())) { - (*EI)->reverse(); - Visited.insert((*EI)->getToMI()); - EdgesToRemove.insert(*EI); - Progressed = true; - } - for (GIMatchDagEdge *ToRemove : EdgesToRemove) - EdgesRemaining.erase(ToRemove); - EdgesToRemove.clear(); - } - - if (!Progressed) { - LLVM_DEBUG(dbgs() << "No progress\n"); - return; - } - Progressed = false; - } - } -}; - -StringRef makeNameForAnonInstr(CombineRule &Rule) { - return insertStrTab(to_string( - format("__anon%" PRIu64 "_%u", 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%" PRIu64 "_%u", Rule.getID(), Rule.allocUID()))); -} - -void CombineRule::declareMatchData(StringRef PatternSymbol, StringRef Type, - StringRef VarName) { - MatchDataDecls.emplace_back(PatternSymbol, Type, VarName); -} - -bool CombineRule::parseDefs() { - DagInit *Defs = TheDef.getValueAsDag("Defs"); - - if (Defs->getOperatorAsDef(TheDef.getLoc())->getName() != "defs") { - PrintError(TheDef.getLoc(), "Expected defs operator"); - return false; - } - - for (unsigned I = 0, E = Defs->getNumArgs(); I < E; ++I) { - // Roots should be collected into Roots - if (isSpecificDef(*Defs->getArg(I), "root")) { - Roots.emplace_back(Defs->getArgNameStr(I)); - continue; - } - - // Subclasses of GIDefMatchData should declare that this rule needs to pass - // data from the match stage to the apply stage, and ensure that the - // generated matcher has a suitable variable for it to do so. - if (Record *MatchDataRec = - getDefOfSubClass(*Defs->getArg(I), "GIDefMatchData")) { - declareMatchData(Defs->getArgNameStr(I), - MatchDataRec->getValueAsString("Type"), - llvm::to_string(llvm::format("MatchData%" PRIu64, ID))); - continue; - } - - // Otherwise emit an appropriate error message. - if (getDefOfSubClass(*Defs->getArg(I), "GIDefKind")) - PrintError(TheDef.getLoc(), - "This GIDefKind not implemented in tablegen"); - else if (getDefOfSubClass(*Defs->getArg(I), "GIDefKindWithArgs")) - PrintError(TheDef.getLoc(), - "This GIDefKindWithArgs not implemented in tablegen"); - else - PrintError(TheDef.getLoc(), - "Expected a subclass of GIDefKind or a sub-dag whose " - "operator is of type GIDefKindWithArgs"); - return false; - } - - if (Roots.empty()) { - PrintError(TheDef.getLoc(), "Combine rules must have at least one root"); - return false; - } - 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 (any_of(Roots, [&](const RootInfo &X) { - return X.getPatternSymbol() == Name; - })) { - N->setMatchRoot(); - } - } - - OpIdx++; - } - - return true; - } - return false; -} - -// Parse the wip_match_opcode placeholder that's temporarily present in lieu of -// implementing macros or choices between two matchers. -bool CombineRule::parseWipMatchOpcodeMatcher(const CodeGenTarget &Target, - StringInit *ArgName, - const Init &Arg) { - if (const DagInit *Matcher = - getDagWithSpecificOperator(Arg, "wip_match_opcode")) { - StringRef Name = ArgName ? ArgName->getValue() : ""; - - GIMatchDagInstr *N = - MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name), - MatchDag.getContext().makeEmptyOperandList()); - - if (any_of(Roots, [&](const RootInfo &X) { - return ArgName && X.getPatternSymbol() == ArgName->getValue(); - })) { - N->setMatchRoot(); - } - - const auto &P = MatchDag.addPredicateNode( - makeNameForAnonPredicate(*this)); - MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]); - // Each argument is an opcode that will pass this predicate. Add them all to - // the predicate implementation - for (const auto &Arg : Matcher->getArgs()) { - Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction"); - if (OpcodeDef) { - P->addOpcode(&Target.getInstruction(OpcodeDef)); - continue; - } - PrintError(TheDef.getLoc(), - "Arguments to wip_match_opcode must be instructions"); - return false; - } - return true; - } - return false; -} -bool CombineRule::parseMatcher(const CodeGenTarget &Target) { - StringMap> NamedEdgeDefs; - StringMap> NamedEdgeUses; - DagInit *Matchers = TheDef.getValueAsDag("Match"); - - if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") { - PrintError(TheDef.getLoc(), "Expected match operator"); - return false; - } - - if (Matchers->getNumArgs() == 0) { - PrintError(TheDef.getLoc(), "Matcher is empty"); - return false; - } - - // 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; - - if (parseWipMatchOpcodeMatcher(Target, Matchers->getArgName(I), - *Matchers->getArg(I))) - continue; - - - // Parse arbitrary C++ code we have in lieu of supporting MIR matching - if (const StringInit *StringI = dyn_cast(Matchers->getArg(I))) { - assert(!MatchingFixupCode && - "Only one block of arbitrary code is currently permitted"); - MatchingFixupCode = StringI; - MatchDag.setHasPostMatchPredicate(true); - continue; - } - - PrintError(TheDef.getLoc(), - "Expected a subclass of GIMatchKind or a sub-dag whose " - "operator is either of a GIMatchKindWithArgs or Instruction"); - 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; -} - -class GICombinerEmitter { - RecordKeeper &Records; - StringRef Name; - const CodeGenTarget &Target; - Record *Combiner; - std::vector> Rules; - GIMatchDagContext MatchDagCtx; - - std::unique_ptr makeCombineRule(const Record &R); - - void gatherRules(std::vector> &ActiveRules, - const std::vector &&RulesAndGroups); - -public: - explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target, - StringRef Name, Record *Combiner); - ~GICombinerEmitter() {} - - StringRef getClassName() const { - return Combiner->getValueAsString("Classname"); - } - void run(raw_ostream &OS); - - /// Emit the name matcher (guarded by #ifndef NDEBUG) used to disable rules in - /// response to the generated cl::opt. - void emitNameMatcher(raw_ostream &OS) const; - - void generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree, - StringRef Indent) const; -}; - -GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK, - const CodeGenTarget &Target, - StringRef Name, Record *Combiner) - : Records(RK), Name(Name), Target(Target), Combiner(Combiner) {} - -void GICombinerEmitter::emitNameMatcher(raw_ostream &OS) const { - std::vector> Cases; - Cases.reserve(Rules.size()); - - for (const CombineRule &EnumeratedRule : make_pointee_range(Rules)) { - std::string Code; - raw_string_ostream SS(Code); - SS << "return " << EnumeratedRule.getID() << ";\n"; - Cases.push_back( - std::make_pair(std::string(EnumeratedRule.getName()), Code)); - } - - OS << "static std::optional getRuleIdxForIdentifier(StringRef " - "RuleIdentifier) {\n" - << " uint64_t I;\n" - << " // getAtInteger(...) returns false on success\n" - << " bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n" - << " if (Parsed)\n" - << " return I;\n\n" - << "#ifndef NDEBUG\n"; - StringMatcher Matcher("RuleIdentifier", Cases, OS); - Matcher.Emit(); - OS << "#endif // ifndef NDEBUG\n\n" - << " return std::nullopt;\n" - << "}\n"; -} - -std::unique_ptr -GICombinerEmitter::makeCombineRule(const Record &TheDef) { - std::unique_ptr Rule = - std::make_unique(Target, MatchDagCtx, NumPatternTotal, TheDef); - - if (!Rule->parseDefs()) - return nullptr; - if (!Rule->parseMatcher(Target)) - return nullptr; - - Rule->reorientToRoots(); - - LLVM_DEBUG({ - dbgs() << "Parsed rule defs/match for '" << Rule->getName() << "'\n"; - Rule->getMatchDag().dump(); - Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName()); - }); - if (StopAfterParse) - return Rule; - - // For now, don't support traversing from def to use. We'll come back to - // this later once we have the algorithm changes to support it. - bool EmittedDefToUseError = false; - for (const auto &E : Rule->getMatchDag().edges()) { - if (E->isDefToUse()) { - if (!EmittedDefToUseError) { - PrintError( - TheDef.getLoc(), - "Generated state machine cannot lookup uses from a def (yet)"); - EmittedDefToUseError = true; - } - PrintNote("Node " + to_string(*E->getFromMI())); - PrintNote("Node " + to_string(*E->getToMI())); - PrintNote("Edge " + to_string(*E)); - } - } - if (EmittedDefToUseError) - return nullptr; - - // 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) { - PrintError(TheDef.getLoc(), "Multi-root matches are not supported (yet)"); - return nullptr; - } - return Rule; -} - -/// Recurse into GICombineGroup's and flatten the ruleset into a simple list. -void GICombinerEmitter::gatherRules( - std::vector> &ActiveRules, - const std::vector &&RulesAndGroups) { - for (Record *R : RulesAndGroups) { - if (R->isValueUnset("Rules")) { - std::unique_ptr Rule = makeCombineRule(*R); - if (Rule == nullptr) { - PrintError(R->getLoc(), "Failed to parse rule"); - continue; - } - ActiveRules.emplace_back(std::move(Rule)); - ++NumPatternTotal; - } else - gatherRules(ActiveRules, R->getValueAsListOfDefs("Rules")); - } -} - -void GICombinerEmitter::generateCodeForTree(raw_ostream &OS, - const GIMatchTree &Tree, - StringRef Indent) const { - if (Tree.getPartitioner() != nullptr) { - Tree.getPartitioner()->generatePartitionSelectorCode(OS, Indent); - for (const auto &EnumChildren : enumerate(Tree.children())) { - OS << Indent << "if (Partition == " << EnumChildren.index() << " /* " - << format_partition_name(Tree, EnumChildren.index()) << " */) {\n"; - generateCodeForTree(OS, EnumChildren.value(), (Indent + " ").str()); - OS << Indent << "}\n"; - } - return; - } - - bool AnyFullyTested = false; - for (const auto &Leaf : Tree.possible_leaves()) { - OS << Indent << "// Leaf name: " << Leaf.getName() << "\n"; - - const CombineRule *Rule = Leaf.getTargetData(); - const Record &RuleDef = Rule->getDef(); - - OS << Indent << "// Rule: " << RuleDef.getName() << "\n" - << Indent << "if (!RuleConfig->isRuleDisabled(" << Rule->getID() - << ")) {\n"; - - CodeExpansions Expansions; - for (const auto &VarBinding : Leaf.var_bindings()) { - if (VarBinding.isInstr()) - Expansions.declare(VarBinding.getName(), - "MIs[" + to_string(VarBinding.getInstrID()) + "]"); - else - Expansions.declare(VarBinding.getName(), - "MIs[" + to_string(VarBinding.getInstrID()) + - "]->getOperand(" + - to_string(VarBinding.getOpIdx()) + ")"); - } - Rule->declareExpansions(Expansions); - - DagInit *Applyer = RuleDef.getValueAsDag("Apply"); - if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() != - "apply") { - PrintError(RuleDef.getLoc(), "Expected 'apply' operator in Apply DAG"); - return; - } - - OS << Indent << " if (1\n"; - - // Emit code for C++ Predicates. - if (RuleDef.getValue("Predicates")) { - ListInit *Preds = RuleDef.getValueAsListInit("Predicates"); - for (Init *I : Preds->getValues()) { - if (DefInit *Pred = dyn_cast(I)) { - Record *Def = Pred->getDef(); - if (!Def->isSubClassOf("Predicate")) { - PrintError(Def->getLoc(), "Unknown 'Predicate' Type"); - return; - } - - StringRef CondString = Def->getValueAsString("CondString"); - if (CondString.empty()) - continue; - - OS << Indent << " && (\n" - << Indent << " // Predicate: " << Def->getName() << "\n" - << Indent << " " << CondString << "\n" - << Indent << " )\n"; - } - } - } - - // Attempt to emit code for any untested predicates left over. Note that - // isFullyTested() will remain false even if we succeed here and therefore - // combine rule elision will not be performed. This is because we do not - // know if there's any connection between the predicates for each leaf and - // therefore can't tell if one makes another unreachable. Ideally, the - // partitioner(s) would be sufficiently complete to prevent us from having - // untested predicates left over. - for (const GIMatchDagPredicate *Predicate : Leaf.untested_predicates()) { - if (Predicate->generateCheckCode(OS, (Indent + " ").str(), - Expansions)) - continue; - PrintError(RuleDef.getLoc(), - "Unable to test predicate used in rule"); - PrintNote(SMLoc(), - "This indicates an incomplete implementation in tablegen"); - Predicate->print(errs()); - errs() << "\n"; - OS << Indent - << "llvm_unreachable(\"TableGen did not emit complete code for this " - "path\");\n"; - break; - } - - if (Rule->getMatchingFixupCode() && - !Rule->getMatchingFixupCode()->getValue().empty()) { - // FIXME: Single-use lambda's like this are a serious compile-time - // performance and memory issue. It's convenient for this early stage to - // defer some work to successive patches but we need to eliminate this - // before the ruleset grows to small-moderate size. Last time, it became - // a big problem for low-mem systems around the 500 rule mark but by the - // time we grow that large we should have merged the ISel match table - // mechanism with the Combiner. - OS << Indent << " && [&]() {\n" - << Indent << " " - << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions, - RuleDef.getLoc(), ShowExpansions) - << '\n' - << Indent << " return true;\n" - << Indent << " }()"; - } - OS << Indent << " ) {\n" << Indent << " "; - - if (const StringInit *Code = dyn_cast(Applyer->getArg(0))) { - OS << " LLVM_DEBUG(dbgs() << \"Applying rule '" - << RuleDef.getName() - << "'\\n\");\n" - << CodeExpander(Code->getAsUnquotedString(), Expansions, - RuleDef.getLoc(), ShowExpansions) - << '\n' - << Indent << " return true;\n" - << Indent << " }\n"; - } else { - PrintError(RuleDef.getLoc(), "Expected apply code block"); - return; - } - - OS << Indent << "}\n"; - - assert(Leaf.isFullyTraversed()); - - // If we didn't have any predicates left over and we're not using the - // trap-door we have to support arbitrary C++ code while we're migrating to - // the declarative style then we know that subsequent leaves are - // unreachable. - if (Leaf.isFullyTested() && - (!Rule->getMatchingFixupCode() || - Rule->getMatchingFixupCode()->getValue().empty())) { - AnyFullyTested = true; - OS << Indent - << "llvm_unreachable(\"Combine rule elision was incorrect\");\n" - << Indent << "return false;\n"; - } - } - if (!AnyFullyTested) - OS << Indent << "return false;\n"; -} - -static void emitAdditionalHelperMethodArguments(raw_ostream &OS, - Record *Combiner) { - for (Record *Arg : Combiner->getValueAsListOfDefs("AdditionalArguments")) - OS << ",\n " << Arg->getValueAsString("Type") - << " " << Arg->getValueAsString("Name"); -} - -void GICombinerEmitter::run(raw_ostream &OS) { - Records.startTimer("Gather rules"); - 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"); - LLVM_DEBUG(dbgs() << "Optimizing tree for " << Rules.size() << " rules\n"); - std::unique_ptr Tree; - Records.startTimer("Optimize combiner"); - { - GIMatchTreeBuilder TreeBuilder(0); - for (const auto &Rule : Rules) { - bool HadARoot = false; - for (const auto &Root : enumerate(Rule->getMatchDag().roots())) { - TreeBuilder.addLeaf(Rule->getName(), Root.index(), Rule->getMatchDag(), - Rule.get()); - HadARoot = true; - } - if (!HadARoot) - PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root"); - } - - Tree = TreeBuilder.run(); - } - if (StopAfterBuild) { - Tree->writeDOTGraph(outs()); - PrintNote(Combiner->getLoc(), - "Terminating due to -gicombiner-stop-after-build"); - return; - } - - Records.startTimer("Emit combiner"); - OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n" - << "#include \"llvm/ADT/SparseBitVector.h\"\n" - << "namespace llvm {\n" - << "extern cl::OptionCategory GICombinerOptionCategory;\n" - << "} // end namespace llvm\n" - << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n\n"; - - OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n" - << "class " << getClassName() << "RuleConfig {\n" - << " SparseBitVector<> DisabledRules;\n" - << "\n" - << "public:\n" - << " bool parseCommandLineOption();\n" - << " bool isRuleDisabled(unsigned ID) const;\n" - << " bool setRuleEnabled(StringRef RuleIdentifier);\n" - << " bool setRuleDisabled(StringRef RuleIdentifier);\n" - << "};\n" - << "\n" - << "class " << getClassName(); - StringRef StateClass = Combiner->getValueAsString("StateClass"); - if (!StateClass.empty()) - OS << " : public " << StateClass; - OS << " {\n" - << " const " << getClassName() << "RuleConfig *RuleConfig;\n" - << "\n" - << "public:\n" - << " template " << getClassName() << "(const " - << getClassName() << "RuleConfig &RuleConfig, Args &&... args) : "; - if (!StateClass.empty()) - OS << StateClass << "(std::forward(args)...), "; - OS << "RuleConfig(&RuleConfig) {}\n" - << "\n" - << " bool tryCombineAll(\n" - << " GISelChangeObserver &Observer,\n" - << " MachineInstr &MI,\n" - << " MachineIRBuilder &B"; - emitAdditionalHelperMethodArguments(OS, Combiner); - OS << ") const;\n"; - OS << "};\n\n"; - - emitNameMatcher(OS); - - OS << "static std::optional> " - "getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n" - << " std::pair RangePair = " - "RuleIdentifier.split('-');\n" - << " if (!RangePair.second.empty()) {\n" - << " const auto First = " - "getRuleIdxForIdentifier(RangePair.first);\n" - << " const auto Last = " - "getRuleIdxForIdentifier(RangePair.second);\n" - << " if (!First || !Last)\n" - << " return std::nullopt;\n" - << " if (First >= Last)\n" - << " report_fatal_error(\"Beginning of range should be before " - "end of range\");\n" - << " return {{*First, *Last + 1}};\n" - << " }\n" - << " if (RangePair.first == \"*\") {\n" - << " return {{0, " << Rules.size() << "}};\n" - << " }\n" - << " const auto I = getRuleIdxForIdentifier(RangePair.first);\n" - << " if (!I)\n" - << " return std::nullopt;\n" - << " return {{*I, *I + 1}};\n" - << "}\n\n"; - - for (bool Enabled : {true, false}) { - OS << "bool " << getClassName() << "RuleConfig::setRule" - << (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n" - << " auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n" - << " if (!MaybeRange)\n" - << " return false;\n" - << " for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n" - << " DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n" - << " return true;\n" - << "}\n\n"; - } - - OS << "bool " << getClassName() - << "RuleConfig::isRuleDisabled(unsigned RuleID) const {\n" - << " return DisabledRules.test(RuleID);\n" - << "}\n"; - OS << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n\n"; - - OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n" - << "\n" - << "std::vector " << Name << "Option;\n" - << "cl::list " << Name << "DisableOption(\n" - << " \"" << Name.lower() << "-disable-rule\",\n" - << " cl::desc(\"Disable one or more combiner rules temporarily in " - << "the " << Name << " pass\"),\n" - << " cl::CommaSeparated,\n" - << " cl::Hidden,\n" - << " cl::cat(GICombinerOptionCategory),\n" - << " cl::callback([](const std::string &Str) {\n" - << " " << Name << "Option.push_back(Str);\n" - << " }));\n" - << "cl::list " << Name << "OnlyEnableOption(\n" - << " \"" << Name.lower() << "-only-enable-rule\",\n" - << " cl::desc(\"Disable all rules in the " << Name - << " pass then re-enable the specified ones\"),\n" - << " cl::Hidden,\n" - << " cl::cat(GICombinerOptionCategory),\n" - << " cl::callback([](const std::string &CommaSeparatedArg) {\n" - << " StringRef Str = CommaSeparatedArg;\n" - << " " << Name << "Option.push_back(\"*\");\n" - << " do {\n" - << " auto X = Str.split(\",\");\n" - << " " << Name << "Option.push_back((\"!\" + X.first).str());\n" - << " Str = X.second;\n" - << " } while (!Str.empty());\n" - << " }));\n" - << "\n" - << "bool " << getClassName() << "RuleConfig::parseCommandLineOption() {\n" - << " for (StringRef Identifier : " << Name << "Option) {\n" - << " bool Enabled = Identifier.consume_front(\"!\");\n" - << " if (Enabled && !setRuleEnabled(Identifier))\n" - << " return false;\n" - << " if (!Enabled && !setRuleDisabled(Identifier))\n" - << " return false;\n" - << " }\n" - << " return true;\n" - << "}\n\n"; - - OS << "bool " << getClassName() << "::tryCombineAll(\n" - << " GISelChangeObserver &Observer,\n" - << " MachineInstr &MI,\n" - << " MachineIRBuilder &B"; - emitAdditionalHelperMethodArguments(OS, Combiner); - OS << ") const {\n" - << " MachineBasicBlock *MBB = MI.getParent();\n" - << " MachineFunction *MF = MBB->getParent();\n" - << " MachineRegisterInfo &MRI = MF->getRegInfo();\n" - << " SmallVector MIs = {&MI};\n\n" - << " (void)MBB; (void)MF; (void)MRI; (void)RuleConfig;\n\n"; - - OS << " // Match data\n"; - for (const auto &Rule : Rules) - for (const auto &I : Rule->matchdata_decls()) - OS << " " << I.getType() << " " << I.getVariableName() << ";\n"; - OS << "\n"; - - OS << " int Partition = -1;\n"; - generateCodeForTree(OS, *Tree, " "); - OS << "\n return false;\n" - << "}\n" - << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"; -} - -} // end anonymous namespace - -//===----------------------------------------------------------------------===// - -static void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) { - PrintWarning( - "'-gen-global-isel-combiner' is deprecated and will be removed soon; " - "please use '-gen-global-isel-combiner-match-table' instead"); - PrintNote( - "See " - "https://discourse.llvm.org/t/rfc-matchtable-based-globalisel-combiners"); - - CodeGenTarget Target(RK); - emitSourceFileHeader("Global Combiner", OS); - - if (SelectedCombiners.empty()) - PrintFatalError("No combiners selected with -combiners"); - for (const auto &Combiner : SelectedCombiners) { - Record *CombinerDef = RK.getDef(Combiner); - if (!CombinerDef) - PrintFatalError("Could not find " + Combiner); - GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS); - } - NumPatternTotalStatistic = NumPatternTotal; -} - -static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner, - "Generate GlobalISel combiner"); 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 @@ -1,18 +1,10 @@ set(LLVM_LINK_COMPONENTS - CodeGenTypes Support TableGen ) add_llvm_library(LLVMTableGenGlobalISel STATIC DISABLE_LLVM_LINK_LLVM_DYLIB CodeExpander.cpp - GIMatchDag.cpp - GIMatchDagEdge.cpp - GIMatchDagInstr.cpp - GIMatchDagOperands.cpp - GIMatchDagPredicate.cpp - GIMatchDagPredicateDependencyEdge.cpp - GIMatchTree.cpp DEPENDS vt_gen diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDag.h b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDag.h +++ /dev/null @@ -1,240 +0,0 @@ -//===- GIMatchDag.h - Represent a DAG to be matched -------------*- C++ -*-===// -// -// 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 { - -/// 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 instr_node_iterator = raw_pointer_iterator; - using const_instr_node_iterator = - raw_pointer_iterator; - - using EdgesVec = std::vector>; - using edge_iterator = raw_pointer_iterator; - using const_edge_iterator = raw_pointer_iterator; - - using PredicateNodesVec = std::vector>; - using predicate_iterator = raw_pointer_iterator; - using const_predicate_iterator = - raw_pointer_iterator; - - using PredicateDependencyEdgesVec = - std::vector>; - using predicate_edge_iterator = - raw_pointer_iterator; - using const_predicate_edge_iterator = - raw_pointer_iterator; - -protected: - GIMatchDagContext &Ctx; - InstrNodesVec InstrNodes; - PredicateNodesVec PredicateNodes; - EdgesVec Edges; - PredicateDependencyEdgesVec PredicateDependencies; - std::vector MatchRoots; - // FIXME: This is a temporary measure while we still accept arbitrary code - // blocks to fix up the matcher while it's being developed. - bool HasPostMatchPredicate = false; - -public: - GIMatchDag(GIMatchDagContext &Ctx) : Ctx(Ctx) {} - GIMatchDag(const GIMatchDag &) = delete; - - GIMatchDagContext &getContext() const { return Ctx; } - edge_iterator edges_begin() { - return raw_pointer_iterator(Edges.begin()); - } - edge_iterator edges_end() { - return raw_pointer_iterator(Edges.end()); - } - const_edge_iterator edges_begin() const { - return raw_pointer_iterator(Edges.begin()); - } - const_edge_iterator edges_end() const { - return raw_pointer_iterator(Edges.end()); - } - iterator_range edges() { - return make_range(edges_begin(), edges_end()); - } - iterator_range edges() const { - return make_range(edges_begin(), edges_end()); - } - iterator_range::iterator> roots() { - return make_range(MatchRoots.begin(), MatchRoots.end()); - } - iterator_range::const_iterator> roots() const { - return make_range(MatchRoots.begin(), MatchRoots.end()); - } - - instr_node_iterator instr_nodes_begin() { - return raw_pointer_iterator(InstrNodes.begin()); - } - instr_node_iterator instr_nodes_end() { - return raw_pointer_iterator(InstrNodes.end()); - } - const_instr_node_iterator instr_nodes_begin() const { - return raw_pointer_iterator( - InstrNodes.begin()); - } - const_instr_node_iterator instr_nodes_end() const { - return raw_pointer_iterator( - InstrNodes.end()); - } - iterator_range instr_nodes() { - return make_range(instr_nodes_begin(), instr_nodes_end()); - } - iterator_range instr_nodes() const { - return make_range(instr_nodes_begin(), instr_nodes_end()); - } - predicate_edge_iterator predicate_edges_begin() { - return raw_pointer_iterator( - PredicateDependencies.begin()); - } - predicate_edge_iterator predicate_edges_end() { - return raw_pointer_iterator( - PredicateDependencies.end()); - } - const_predicate_edge_iterator predicate_edges_begin() const { - return raw_pointer_iterator( - PredicateDependencies.begin()); - } - const_predicate_edge_iterator predicate_edges_end() const { - return raw_pointer_iterator( - PredicateDependencies.end()); - } - iterator_range predicate_edges() { - return make_range(predicate_edges_begin(), predicate_edges_end()); - } - iterator_range predicate_edges() const { - return make_range(predicate_edges_begin(), predicate_edges_end()); - } - predicate_iterator predicates_begin() { - return raw_pointer_iterator( - PredicateNodes.begin()); - } - predicate_iterator predicates_end() { - return raw_pointer_iterator( - PredicateNodes.end()); - } - const_predicate_iterator predicates_begin() const { - return raw_pointer_iterator( - PredicateNodes.begin()); - } - const_predicate_iterator predicates_end() const { - return raw_pointer_iterator( - PredicateNodes.end()); - } - iterator_range predicates() { - return make_range(predicates_begin(), predicates_end()); - } - iterator_range predicates() const { - return make_range(predicates_begin(), predicates_end()); - } - - 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; - } - - size_t getInstrNodeIdx(instr_node_iterator I) { - return std::distance(instr_nodes_begin(), I); - } - size_t getInstrNodeIdx(const_instr_node_iterator I) const { - return std::distance(instr_nodes_begin(), I); - } - size_t getNumInstrNodes() const { return InstrNodes.size(); } - size_t getNumEdges() const { return Edges.size(); } - size_t getNumPredicates() const { return PredicateNodes.size(); } - - void setHasPostMatchPredicate(bool V) { HasPostMatchPredicate = V; } - bool hasPostMatchPredicate() const { return HasPostMatchPredicate; } - - 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp +++ /dev/null @@ -1,138 +0,0 @@ -//===- 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); - StringRef Separator = ""; - for (const auto &Assignment : ToPrint) { - OS << Separator << "$" << Assignment.second << "=getOperand(" - << Assignment.first << ")"; - Separator = ", "; - } - OS << llvm::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 << llvm::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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h +++ /dev/null @@ -1,70 +0,0 @@ -//===- GIMatchDagEdge.h - Represent node shared operand lists ---*- C++ -*-===// -// -// 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; } - - /// Flip the direction of the edge. - void reverse(); - - /// Does this edge run from a def to (one of many) uses? - bool isDefToUse() const; - - 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp +++ /dev/null @@ -1,39 +0,0 @@ -//===- 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 "GIMatchDagOperands.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() - << "]"; -} - -bool GIMatchDagEdge::isDefToUse() const { - // Def -> Def is invalid so we only need to check FromMO. - return FromMO->isDef(); -} - -void GIMatchDagEdge::reverse() { - std::swap(FromMI, ToMI); - std::swap(FromMO, ToMO); -} - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -LLVM_DUMP_METHOD void GIMatchDagEdge::dump() const { print(errs()); } -#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - -raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagEdge &E) { - E.print(OS); - return OS; -} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h +++ /dev/null @@ -1,118 +0,0 @@ -//===- GIMatchDagInstr.h - Represent instruction to be matched --*- C++ -*-===// -// -// 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 "llvm/ADT/DenseMap.h" -#include "llvm/ADT/StringRef.h" -#include "llvm/Support/raw_ostream.h" - -namespace llvm { -class CodeGenInstruction; -class GIMatchDag; -class GIMatchDagOperandList; - -/// 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 = nullptr; - - /// 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; } - StringRef getUserAssignedName() const { return UserAssignedName; } - 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp +++ /dev/null @@ -1,48 +0,0 @@ -//===- 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 "../CodeGenInstruction.h" -#include "GIMatchDag.h" -#include "llvm/TableGen/Record.h" - -using namespace llvm; - -void GIMatchDagInstr::print(raw_ostream &OS) const { - OS << "("; - if (const auto *Annotation = getOpcodeAnnotation()) - OS << Annotation->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); - 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h +++ /dev/null @@ -1,133 +0,0 @@ -//===- GIMatchDagOperands.h - Represent operand lists for nodes -*- C++ -*-===// -// -// 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp +++ /dev/null @@ -1,153 +0,0 @@ -//===- 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 : OperandListsOwner) { - 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h +++ /dev/null @@ -1,145 +0,0 @@ -//===- GIMatchDagPredicate - Represent a predicate to check -----*- C++ -*-===// -// -// 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/SmallVector.h" -#include "llvm/ADT/StringRef.h" - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -#include "llvm/Support/raw_ostream.h" -#endif - -namespace llvm { -class CodeExpansions; -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_OneOfOpcodes, - 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; } - - // Generate C++ code to check this predicate. If a partitioner has already - // tested this predicate then this function won't be called. If this function - // is called, it must emit code and return true to indicate that it did so. If - // it ever returns false, then the caller will abort due to an untested - // predicate. - virtual bool generateCheckCode(raw_ostream &OS, StringRef Indent, - const CodeExpansions &Expansions) const { - return false; - } - - 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) - LLVM_DUMP_METHOD void dump() const override { print(errs()); } -#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -}; - -class GIMatchDagOneOfOpcodesPredicate : public GIMatchDagPredicate { - SmallVector Instrs; - -public: - GIMatchDagOneOfOpcodesPredicate(GIMatchDagContext &Ctx, StringRef Name); - - void addOpcode(const CodeGenInstruction *Instr) { Instrs.push_back(Instr); } - - static bool classof(const GIMatchDagPredicate *P) { - return P->getKind() == GIMatchDagPredicateKind_OneOfOpcodes; - } - - const SmallVectorImpl &getInstrs() const { - return Instrs; - } - - void printDescription(raw_ostream &OS) const override; - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - 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) - 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp +++ /dev/null @@ -1,69 +0,0 @@ -//===- 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 "../CodeGenInstruction.h" -#include "GIMatchDag.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(); -} - -GIMatchDagOneOfOpcodesPredicate::GIMatchDagOneOfOpcodesPredicate( - GIMatchDagContext &Ctx, StringRef Name) - : GIMatchDagPredicate(GIMatchDagPredicateKind_OneOfOpcodes, Name, - Ctx.makeMIPredicateOperandList()) {} - -void GIMatchDagOneOfOpcodesPredicate::printDescription(raw_ostream &OS) const { - OS << "$mi.getOpcode() == oneof("; - StringRef Separator = ""; - for (const CodeGenInstruction *Instr : Instrs) { - OS << Separator << Instr->TheDef->getName(); - Separator = ","; - } - OS << ")"; -} - -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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h +++ /dev/null @@ -1,61 +0,0 @@ -//===- 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 "llvm/Support/Compiler.h" - -namespace llvm { -class GIMatchDagInstr; -class GIMatchDagPredicate; -class GIMatchDagOperand; - -class raw_ostream; - -/// 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 deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp +++ /dev/null @@ -1,38 +0,0 @@ -//===- 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 "GIMatchDagOperands.h" -#include "GIMatchDagPredicate.h" - -#include "llvm/Support/raw_ostream.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; -} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.h b/llvm/utils/TableGen/GlobalISel/GIMatchTree.h deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchTree.h +++ /dev/null @@ -1,626 +0,0 @@ -//===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===// -// -// 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_GIMATCHTREE_H -#define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H - -#include "GIMatchDag.h" -#include "llvm/ADT/BitVector.h" - -namespace llvm { -class raw_ostream; - -class GIMatchTreeBuilder; -class GIMatchTreePartitioner; - -/// Describes the binding of a variable to the matched MIR -class GIMatchTreeVariableBinding { - /// The name of the variable described by this binding. - StringRef Name; - // The matched instruction it is bound to. - unsigned InstrID; - // The matched operand (if appropriate) it is bound to. - std::optional OpIdx; - -public: - GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID, - std::optional OpIdx = std::nullopt) - : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {} - - bool isInstr() const { return !OpIdx; } - StringRef getName() const { return Name; } - unsigned getInstrID() const { return InstrID; } - unsigned getOpIdx() const { - assert(OpIdx && "Is not an operand binding"); - return *OpIdx; - } -}; - -/// Associates a matchable with a leaf of the decision tree. -class GIMatchTreeLeafInfo { -public: - using const_var_binding_iterator = - std::vector::const_iterator; - using UntestedPredicatesTy = SmallVector; - using const_untested_predicates_iterator = UntestedPredicatesTy::const_iterator; - -protected: - /// A name for the matchable. This is primarily for debugging. - StringRef Name; - /// Where rules have multiple roots, this is which root we're starting from. - unsigned RootIdx; - /// Opaque data the caller of the tree building code understands. - void *Data; - /// Has the decision tree covered every edge traversal? If it hasn't then this - /// is an unrecoverable error indicating there's something wrong with the - /// partitioners. - bool IsFullyTraversed; - /// Has the decision tree covered every predicate test? If it has, then - /// subsequent matchables on the same leaf are unreachable. If it hasn't, the - /// code that requested the GIMatchTree is responsible for finishing off any - /// remaining predicates. - bool IsFullyTested; - /// The variable bindings associated with this leaf so far. - std::vector VarBindings; - /// Any predicates left untested by the time we reach this leaf. - UntestedPredicatesTy UntestedPredicates; - -public: - GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); } - GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data) - : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false), - IsFullyTested(false) {} - - StringRef getName() const { return Name; } - unsigned getRootIdx() const { return RootIdx; } - template Ty *getTargetData() const { - return static_cast(Data); - } - bool isFullyTraversed() const { return IsFullyTraversed; } - void setIsFullyTraversed(bool V) { IsFullyTraversed = V; } - bool isFullyTested() const { return IsFullyTested; } - void setIsFullyTested(bool V) { IsFullyTested = V; } - - void bindInstrVariable(StringRef Name, unsigned InstrID) { - VarBindings.emplace_back(Name, InstrID); - } - void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) { - VarBindings.emplace_back(Name, InstrID, OpIdx); - } - - const_var_binding_iterator var_bindings_begin() const { - return VarBindings.begin(); - } - const_var_binding_iterator var_bindings_end() const { - return VarBindings.end(); - } - iterator_range var_bindings() const { - return make_range(VarBindings.begin(), VarBindings.end()); - } - iterator_range untested_predicates() const { - return make_range(UntestedPredicates.begin(), UntestedPredicates.end()); - } - void addUntestedPredicate(const GIMatchDagPredicate *P) { - UntestedPredicates.push_back(P); - } -}; - -/// The nodes of a decision tree used to perform the match. -/// This will be used to generate the C++ code or state machine equivalent. -/// -/// It should be noted that some nodes of this tree (most notably nodes handling -/// def -> use edges) will need to iterate over several possible matches. As -/// such, code generated from this will sometimes need to support backtracking. -class GIMatchTree { - using LeafVector = std::vector; - - /// The partitioner that has been chosen for this node. This may be nullptr if - /// a partitioner hasn't been chosen yet or if the node is a leaf. - std::unique_ptr Partitioner; - /// All the leaves that are possible for this node of the tree. - /// Note: This should be emptied after the tree is built when there are - /// children but this currently isn't done to aid debuggability of the DOT - /// graph for the decision tree. - LeafVector PossibleLeaves; - /// The children of this node. The index into this array must match the index - /// chosen by the partitioner. - std::vector Children; - - void writeDOTGraphNode(raw_ostream &OS) const; - void writeDOTGraphEdges(raw_ostream &OS) const; - -public: - void writeDOTGraph(raw_ostream &OS) const; - - void setNumChildren(unsigned Num) { Children.resize(Num); } - void addPossibleLeaf(const GIMatchTreeLeafInfo &V, bool IsFullyTraversed, - bool IsFullyTested) { - PossibleLeaves.push_back(V); - PossibleLeaves.back().setIsFullyTraversed(IsFullyTraversed); - PossibleLeaves.back().setIsFullyTested(IsFullyTested); - } - void dropLeavesAfter(size_t Length) { - if (PossibleLeaves.size() > Length) - PossibleLeaves.resize(Length); - } - void setPartitioner(std::unique_ptr &&V) { - Partitioner = std::move(V); - } - GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); } - - std::vector::iterator children_begin() { - return Children.begin(); - } - std::vector::iterator children_end() { return Children.end(); } - iterator_range::iterator> children() { - return make_range(children_begin(), children_end()); - } - std::vector::const_iterator children_begin() const { - return Children.begin(); - } - std::vector::const_iterator children_end() const { - return Children.end(); - } - iterator_range::const_iterator> children() const { - return make_range(children_begin(), children_end()); - } - - LeafVector::const_iterator possible_leaves_begin() const { - return PossibleLeaves.begin(); - } - LeafVector::const_iterator possible_leaves_end() const { - return PossibleLeaves.end(); - } - iterator_range - possible_leaves() const { - return make_range(possible_leaves_begin(), possible_leaves_end()); - } - LeafVector::iterator possible_leaves_begin() { - return PossibleLeaves.begin(); - } - LeafVector::iterator possible_leaves_end() { - return PossibleLeaves.end(); - } - iterator_range possible_leaves() { - return make_range(possible_leaves_begin(), possible_leaves_end()); - } -}; - -/// Record information that is known about the instruction bound to this ID and -/// GIMatchDagInstrNode. Every rule gets its own set of -/// GIMatchTreeInstrInfo to bind the shared IDs to an instr node in its -/// DAG. -/// -/// For example, if we know that there are 3 operands. We can record it here to -/// elide duplicate checks. -class GIMatchTreeInstrInfo { - /// The instruction ID for the matched instruction. - unsigned ID; - /// The corresponding instruction node in the MatchDAG. - const GIMatchDagInstr *InstrNode; - -public: - GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode) - : ID(ID), InstrNode(InstrNode) {} - - unsigned getID() const { return ID; } - const GIMatchDagInstr *getInstrNode() const { return InstrNode; } -}; - -/// Record information that is known about the operand bound to this ID, OpIdx, -/// and GIMatchDagInstrNode. Every rule gets its own set of -/// GIMatchTreeOperandInfo to bind the shared IDs to an operand of an -/// instr node from its DAG. -/// -/// For example, if we know that there the operand is a register. We can record -/// it here to elide duplicate checks. -class GIMatchTreeOperandInfo { - /// The corresponding instruction node in the MatchDAG that the operand - /// belongs to. - const GIMatchDagInstr *InstrNode; - unsigned OpIdx; - -public: - GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx) - : InstrNode(InstrNode), OpIdx(OpIdx) {} - - const GIMatchDagInstr *getInstrNode() const { return InstrNode; } - unsigned getOpIdx() const { return OpIdx; } -}; - -/// Represent a leaf of the match tree and any working data we need to build the -/// tree. -/// -/// It's important to note that each rule can have multiple -/// GIMatchTreeBuilderLeafInfo's since the partitioners do not always partition -/// into mutually-exclusive partitions. For example: -/// R1: (FOO ..., ...) -/// R2: (oneof(FOO, BAR) ..., ...) -/// will partition by opcode into two partitions FOO=>[R1, R2], and BAR=>[R2] -/// -/// As an optimization, all instructions, edges, and predicates in the DAGs are -/// numbered and tracked in BitVectors. As such, the GIMatchDAG must not be -/// modified once construction of the tree has begun. -class GIMatchTreeBuilderLeafInfo { -protected: - GIMatchTreeBuilder &Builder; - GIMatchTreeLeafInfo Info; - const GIMatchDag &MatchDag; - /// The association between GIMatchDagInstr* and GIMatchTreeInstrInfo. - /// The primary reason for this members existence is to allow the use of - /// InstrIDToInfo.lookup() since that requires that the value is - /// default-constructible. - DenseMap InstrNodeToInfo; - /// The instruction information for a given ID in the context of this - /// particular leaf. - DenseMap InstrIDToInfo; - /// The operand information for a given ID and OpIdx in the context of this - /// particular leaf. - DenseMap, GIMatchTreeOperandInfo> - OperandIDToInfo; - -public: - /// The remaining instrs/edges/predicates to visit - BitVector RemainingInstrNodes; - BitVector RemainingEdges; - BitVector RemainingPredicates; - - // The remaining predicate dependencies for each predicate - std::vector UnsatisfiedPredDepsForPred; - - /// The edges/predicates we can visit as a result of the declare*() calls we - /// have already made. We don't need an instrs version since edges imply the - /// instr. - BitVector TraversableEdges; - BitVector TestablePredicates; - - /// Map predicates from the DAG to their position in the DAG predicate - /// iterators. - DenseMap PredicateIDs; - /// Map predicate dependency edges from the DAG to their position in the DAG - /// predicate dependency iterators. - DenseMap PredicateDepIDs; - -public: - GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name, - unsigned RootIdx, const GIMatchDag &MatchDag, - void *Data); - - StringRef getName() const { return Info.getName(); } - GIMatchTreeLeafInfo &getInfo() { return Info; } - const GIMatchTreeLeafInfo &getInfo() const { return Info; } - const GIMatchDag &getMatchDag() const { return MatchDag; } - unsigned getRootIdx() const { return Info.getRootIdx(); } - - /// Has this DAG been fully traversed. This must be true by the time the tree - /// builder finishes. - bool isFullyTraversed() const { - // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates - // can't be all-zero without satisfying all the dependencies. The same is - // almost true for Edges and Instrs but it's possible to have Instrs without - // Edges. - return RemainingInstrNodes.none() && RemainingEdges.none(); - } - - /// Has this DAG been fully tested. This hould be true by the time the tree - /// builder finishes but clients can finish any untested predicates left over - /// if it's not true. - bool isFullyTested() const { - // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates - // can't be all-zero without satisfying all the dependencies. The same is - // almost true for Edges and Instrs but it's possible to have Instrs without - // Edges. - return RemainingInstrNodes.none() && RemainingEdges.none() && - RemainingPredicates.none(); - } - - const GIMatchDagInstr *getInstr(unsigned Idx) const { - return *(MatchDag.instr_nodes_begin() + Idx); - } - const GIMatchDagEdge *getEdge(unsigned Idx) const { - return *(MatchDag.edges_begin() + Idx); - } - GIMatchDagEdge *getEdge(unsigned Idx) { - return *(MatchDag.edges_begin() + Idx); - } - const GIMatchDagPredicate *getPredicate(unsigned Idx) const { - return *(MatchDag.predicates_begin() + Idx); - } - iterator_range - untested_instrs() const { - return RemainingInstrNodes.set_bits(); - } - iterator_range - untested_edges() const { - return RemainingEdges.set_bits(); - } - iterator_range - untested_predicates() const { - return RemainingPredicates.set_bits(); - } - - /// Bind an instr node to the given ID and clear any blocking dependencies - /// that were waiting for it. - void declareInstr(const GIMatchDagInstr *Instr, unsigned ID); - - /// Bind an operand to the given ID and OpIdx and clear any blocking - /// dependencies that were waiting for it. - void declareOperand(unsigned InstrID, unsigned OpIdx); - - GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const { - return InstrIDToInfo.lookup(ID); - } - - void dump(raw_ostream &OS) const { - OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n"; - MatchDag.print(OS); - for (const auto &I : InstrIDToInfo) - OS << "Declared Instr #" << I.first << "\n"; - for (const auto &I : OperandIDToInfo) - OS << "Declared Instr #" << I.first.first << ", Op #" << I.first.second - << "\n"; - OS << RemainingInstrNodes.count() << " untested instrs of " - << RemainingInstrNodes.size() << "\n"; - OS << RemainingEdges.count() << " untested edges of " - << RemainingEdges.size() << "\n"; - OS << RemainingPredicates.count() << " untested predicates of " - << RemainingPredicates.size() << "\n"; - - OS << TraversableEdges.count() << " edges could be traversed\n"; - OS << TestablePredicates.count() << " predicates could be tested\n"; - } -}; - -/// The tree builder has a fairly tough job. It's purpose is to merge all the -/// DAGs from the ruleset into a decision tree that walks all of them -/// simultaneously and identifies the rule that was matched. In addition to -/// that, it also needs to find the most efficient order to make decisions -/// without violating any dependencies and ensure that every DAG covers every -/// instr/edge/predicate. -class GIMatchTreeBuilder { -public: - using LeafVec = std::vector; - -protected: - /// The leaves that the resulting decision tree will distinguish. - LeafVec Leaves; - /// The tree node being constructed. - GIMatchTree *TreeNode = nullptr; - /// The builders for each subtree resulting from the current decision. - std::vector SubtreeBuilders; - /// The possible partitioners we could apply right now. - std::vector> Partitioners; - /// The next instruction ID to allocate when requested by the chosen - /// Partitioner. - unsigned NextInstrID; - - /// Use any context we have stored to cull partitioners that only test things - /// we already know. At the time of writing, there's no need to do anything - /// here but it will become important once, for example, there is a - /// num-operands and an opcode partitioner. This is because applying an opcode - /// partitioner (usually) makes the number of operands known which makes - /// additional checking pointless. - void filterRedundantPartitioners(); - - /// Evaluate the available partioners and select the best one at the moment. - void evaluatePartitioners(); - - /// Construct the current tree node. - void runStep(); - -public: - GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {} - GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID) - : TreeNode(TreeNode), NextInstrID(NextInstrID) {} - - void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag, - void *Data) { - Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data); - } - void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); } - void addPartitioner(std::unique_ptr P) { - Partitioners.push_back(std::move(P)); - } - void addPartitionersForInstr(unsigned InstrIdx); - void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx); - - LeafVec &getPossibleLeaves() { return Leaves; } - - unsigned allocInstrID() { return NextInstrID++; } - - /// Construct the decision tree. - std::unique_ptr run(); -}; - -/// Partitioners are the core of the tree builder and are unfortunately rather -/// tricky to write. -class GIMatchTreePartitioner { -protected: - /// The partitions resulting from applying the partitioner to the possible - /// leaves. The keys must be consecutive integers starting from 0. This can - /// lead to some unfortunate situations where partitioners test a predicate - /// and use 0 for success and 1 for failure if the ruleset encounters a - /// success case first but is necessary to assign the partition to one of the - /// tree nodes children. As a result, you usually need some kind of - /// indirection to map the natural keys (e.g. ptrs/bools) to this linear - /// sequence. The values are a bitvector indicating which leaves belong to - /// this partition. - DenseMap Partitions; - -public: - virtual ~GIMatchTreePartitioner() {} - virtual std::unique_ptr clone() const = 0; - - /// Determines which partitions the given leaves belong to. A leaf may belong - /// to multiple partitions in which case it will be duplicated during - /// applyForPartition(). - /// - /// This function can be rather complicated. A few particular things to be - /// aware of include: - /// * One leaf can be assigned to multiple partitions when there's some - /// ambiguity. - /// * Not all DAG's for the leaves may be able to perform the test. For - /// example, the opcode partitiioner must account for one DAG being a - /// superset of another such as [(ADD ..., ..., ...)], and [(MUL t, ..., - /// ...), (ADD ..., t, ...)] - /// * Attaching meaning to a particular partition index will generally not - /// work due to the '0, 1, ..., n' requirement. You might encounter cases - /// where only partition 1 is seen, leaving a missing 0. - /// * Finding a specific predicate such as the opcode predicate for a specific - /// instruction is non-trivial. It's often O(NumPredicates), leading to - /// O(NumPredicates*NumRules) when applied to the whole ruleset. The good - /// news there is that n is typically small thanks to predicate dependencies - /// limiting how many are testable at once. Also, with opcode and type - /// predicates being so frequent the value of m drops very fast too. It - /// wouldn't be terribly surprising to see a 10k ruleset drop down to an - /// average of 100 leaves per partition after a single opcode partitioner. - /// * The same goes for finding specific edges. The need to traverse them in - /// dependency order dramatically limits the search space at any given - /// moment. - /// * If you need to add a leaf to all partitions, make sure you don't forget - /// them when adding partitions later. - virtual void repartition(GIMatchTreeBuilder::LeafVec &Leaves) = 0; - - /// Delegate the leaves for a given partition to the corresponding subbuilder, - /// update any recorded context for this partition (e.g. allocate instr id's - /// for instrs recorder by the current node), and clear any blocking - /// dependencies this partitioner resolved. - virtual void applyForPartition(unsigned PartitionIdx, - GIMatchTreeBuilder &Builder, - GIMatchTreeBuilder &SubBuilder) = 0; - - /// Return a BitVector indicating which leaves should be transferred to the - /// specified partition. Note that the same leaf can be indicated for multiple - /// partitions. - BitVector getPossibleLeavesForPartition(unsigned Idx) { - const auto &I = Partitions.find(Idx); - assert(I != Partitions.end() && "Requested non-existant partition"); - return I->second; - } - - size_t getNumPartitions() const { return Partitions.size(); } - size_t getNumLeavesWithDupes() const { - size_t S = 0; - for (const auto &P : Partitions) - S += P.second.size(); - return S; - } - - /// Emit a brief description of the partitioner suitable for debug printing or - /// use in a DOT graph. - virtual void emitDescription(raw_ostream &OS) const = 0; - /// Emit a label for the given partition suitable for debug printing or use in - /// a DOT graph. - virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0; - - /// Emit a long description of how the partitioner partitions the leaves. - virtual void emitPartitionResults(raw_ostream &OS) const = 0; - - /// Generate code to select between partitions based on the MIR being matched. - /// This is typically a switch statement that picks a partition index. - virtual void generatePartitionSelectorCode(raw_ostream &OS, - StringRef Indent) const = 0; -}; - -/// Partition according to the opcode of the instruction. -/// -/// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition, -/// nullptr, represents the case where the instruction isn't known. -/// -/// * If the opcode can be tested and is a single opcode, create the partition -/// for that opcode and assign the leaf to it. This partition no longer needs -/// to test the opcode, and many details about the instruction will usually -/// become known (e.g. number of operands for non-variadic instrs) via the -/// CodeGenInstr ptr. -/// * (not implemented yet) If the opcode can be tested and is a choice of -/// opcodes, then the leaf can be treated like the single-opcode case but must -/// be added to all relevant partitions and not quite as much becomes known as -/// a result. That said, multiple-choice opcodes are likely similar enough -/// (because if they aren't then handling them together makes little sense) -/// that plenty still becomes known. The main implementation issue with this -/// is having a description to represent the commonality between instructions. -/// * If the opcode is not tested, the leaf must be added to all partitions -/// including the wildcard nullptr partition. What becomes known as a result -/// varies between partitions. -/// * If the instruction to be tested is not declared then add the leaf to all -/// partitions. This occurs when we encounter one rule that is a superset of -/// the other and we are still matching the remainder of the superset. The -/// result is that the cases that don't match the superset will match the -/// subset rule, while the ones that do match the superset will match either -/// (which one is algorithm dependent but will usually be the superset). -class GIMatchTreeOpcodePartitioner : public GIMatchTreePartitioner { - unsigned InstrID; - DenseMap InstrToPartition; - std::vector PartitionToInstr; - std::vector TestedPredicates; - -public: - GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {} - - std::unique_ptr clone() const override { - return std::make_unique(*this); - } - - void emitDescription(raw_ostream &OS) const override { - OS << "MI[" << InstrID << "].getOpcode()"; - } - - void emitPartitionName(raw_ostream &OS, unsigned Idx) const override; - - void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override; - void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder, - GIMatchTreeBuilder &Builder) override; - - void emitPartitionResults(raw_ostream &OS) const override; - - void generatePartitionSelectorCode(raw_ostream &OS, - StringRef Indent) const override; -}; - -class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner { - unsigned NewInstrID = -1; - unsigned InstrID; - unsigned OpIdx; - std::vector TraversedEdges; - DenseMap ResultToPartition; - BitVector PartitionToResult; - - void addToPartition(bool Result, unsigned LeafIdx); - -public: - GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx) - : InstrID(InstrID), OpIdx(OpIdx) {} - - std::unique_ptr clone() const override { - return std::make_unique(*this); - } - - void emitDescription(raw_ostream &OS) const override { - OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID - << "].getOperand(" << OpIdx << "))"; - } - - void emitPartitionName(raw_ostream &OS, unsigned Idx) const override { - bool Result = PartitionToResult[Idx]; - if (Result) - OS << "true"; - else - OS << "false"; - } - - void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override; - void applyForPartition(unsigned PartitionIdx, GIMatchTreeBuilder &Builder, - GIMatchTreeBuilder &SubBuilder) override; - void emitPartitionResults(raw_ostream &OS) const override; - - void generatePartitionSelectorCode(raw_ostream &OS, - StringRef Indent) const override; -}; - -} // end namespace llvm -#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp deleted file mode 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp +++ /dev/null @@ -1,761 +0,0 @@ -//===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===// -// -// 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 "GIMatchTree.h" -#include "GIMatchDagPredicate.h" - -#include "../CodeGenInstruction.h" - -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/ScopedPrinter.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/TableGen/Error.h" -#include "llvm/TableGen/Record.h" - -#define DEBUG_TYPE "gimatchtree" - -using namespace llvm; - -void GIMatchTree::writeDOTGraph(raw_ostream &OS) const { - OS << "digraph \"matchtree\" {\n"; - writeDOTGraphNode(OS); - OS << "}\n"; -} - -void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const { - OS << format(" Node%p", this) << " [shape=record,label=\"{"; - if (Partitioner) { - Partitioner->emitDescription(OS); - OS << "|" << Partitioner->getNumPartitions() << " partitions|"; - } else - OS << "No partitioner|"; - bool IsFullyTraversed = true; - bool IsFullyTested = true; - StringRef Separator = ""; - for (const auto &Leaf : PossibleLeaves) { - OS << Separator << Leaf.getName(); - Separator = ","; - if (!Leaf.isFullyTraversed()) - IsFullyTraversed = false; - if (!Leaf.isFullyTested()) - IsFullyTested = false; - } - if (!Partitioner && !IsFullyTraversed) - OS << "|Not fully traversed"; - if (!Partitioner && !IsFullyTested) { - OS << "|Not fully tested"; - if (IsFullyTraversed) { - for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) { - if (Leaf.isFullyTested()) - continue; - OS << "\\n" << Leaf.getName() << ": " << &Leaf; - for (const GIMatchDagPredicate *P : Leaf.untested_predicates()) - OS << *P; - } - } - } - OS << "}\""; - if (!Partitioner && - (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1)) - OS << ",color=red"; - OS << "]\n"; - for (const auto &C : Children) - C.writeDOTGraphNode(OS); - writeDOTGraphEdges(OS); -} - -void GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const { - for (const auto &Child : enumerate(Children)) { - OS << format(" Node%p", this) << " -> " << format("Node%p", &Child.value()) - << " [label=\"#" << Child.index() << " "; - Partitioner->emitPartitionName(OS, Child.index()); - OS << "\"]\n"; - } -} - -GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo( - GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx, - const GIMatchDag &MatchDag, void *Data) - : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag), - RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)), - RemainingEdges(BitVector(MatchDag.getNumEdges(), true)), - RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)), - TraversableEdges(MatchDag.getNumEdges()), - TestablePredicates(MatchDag.getNumPredicates()) { - // Number all the predicates in this DAG - for (const auto &[Idx, P] : enumerate(MatchDag.predicates())) { - PredicateIDs.insert(std::make_pair(P, Idx)); - } - - // Number all the predicate dependencies in this DAG and set up a bitvector - // for each predicate indicating the unsatisfied dependencies. - for (const auto &[Idx, Dep] : enumerate(MatchDag.predicate_edges())) { - PredicateDepIDs.insert(std::make_pair(Dep, Idx)); - } - UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(), - BitVector(PredicateDepIDs.size())); - for (const auto &[Idx, Dep] : enumerate(MatchDag.predicate_edges())) { - unsigned ID = PredicateIDs.lookup(Dep->getPredicate()); - UnsatisfiedPredDepsForPred[ID].set(Idx); - } -} - -void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) { - // Record the assignment of this instr to the given ID. - auto InfoI = InstrNodeToInfo.insert(std::make_pair( - Instr, GIMatchTreeInstrInfo(ID, Instr))); - InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second)); - - if (Instr == nullptr) - return; - - if (!Instr->getUserAssignedName().empty()) - Info.bindInstrVariable(Instr->getUserAssignedName(), ID); - for (const auto &VarBinding : Instr->user_assigned_operand_names()) - Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first); - - // Clear the bit indicating we haven't visited this instr. - const auto &NodeI = find(MatchDag.instr_nodes(), Instr); - assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG"); - unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI); - RemainingInstrNodes.reset(InstrIdx); - - // When we declare an instruction, we don't expose any traversable edges just - // yet. A partitioner has to check they exist and are registers before they - // are traversable. - - // When we declare an instruction, we potentially activate some predicates. - // Mark the dependencies that are now satisfied as a result of this - // instruction and mark any predicates whose dependencies are fully - // satisfied. - for (const auto &Dep : enumerate(MatchDag.predicate_edges())) { - if (Dep.value()->getRequiredMI() == Instr && - Dep.value()->getRequiredMO() == nullptr) { - for (const auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) { - DepsFor.value().reset(Dep.index()); - if (DepsFor.value().none()) - TestablePredicates.set(DepsFor.index()); - } - } - } -} - -void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID, - unsigned OpIdx) { - const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode(); - - OperandIDToInfo.insert(std::make_pair( - std::make_pair(InstrID, OpIdx), - GIMatchTreeOperandInfo(Instr, OpIdx))); - - // When an operand becomes reachable, we potentially activate some traversals. - // Record the edges that can now be followed as a result of this - // instruction. - for (const auto &[Idx, E] : enumerate(MatchDag.edges())) { - if (E->getFromMI() == Instr && E->getFromMO()->getIdx() == OpIdx) { - TraversableEdges.set(Idx); - } - } - - // When an operand becomes reachable, we potentially activate some predicates. - // Clear the dependencies that are now satisfied as a result of this - // operand and activate any predicates whose dependencies are fully - // satisfied. - for (const auto &Dep : enumerate(MatchDag.predicate_edges())) { - if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() && - Dep.value()->getRequiredMO()->getIdx() == OpIdx) { - for (const auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) { - DepsFor.value().reset(Dep.index()); - if (DepsFor.value().none()) - TestablePredicates.set(DepsFor.index()); - } - } - } -} - -void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) { - // Find the partitioners that can be used now that this node is - // uncovered. Our choices are: - // - Test the opcode - addPartitioner(std::make_unique(InstrIdx)); -} - -void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID, - unsigned OpIdx) { - LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID - << "].getOperand(" << OpIdx << ")\n"); - addPartitioner( - std::make_unique(InstrID, OpIdx)); -} - -void GIMatchTreeBuilder::filterRedundantPartitioners() { - // TODO: Filter partitioners for facts that are already known - // - If we know the opcode, we can elide the num operand check so long as - // the instruction has a fixed number of operands. - // - If we know an exact number of operands then we can elide further number - // of operand checks. - // - If the current min number of operands exceeds the one we want to check - // then we can elide it. -} - -void GIMatchTreeBuilder::evaluatePartitioners() { - // Determine the partitioning the partitioner would produce - for (auto &Partitioner : Partitioners) { - LLVM_DEBUG(dbgs() << " Weighing up "; - Partitioner->emitDescription(dbgs()); dbgs() << "\n"); - Partitioner->repartition(Leaves); - LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs())); - } -} - -void GIMatchTreeBuilder::runStep() { - LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n"); - LLVM_DEBUG(dbgs() << " Rules reachable at this node:\n"); - for (const auto &Leaf : Leaves) { - LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n"); - TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(), - Leaf.isFullyTested()); - } - - LLVM_DEBUG(dbgs() << " Partitioners available at this node:\n"); -#ifndef NDEBUG - for (const auto &Partitioner : Partitioners) - LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs()); - dbgs() << "\n"); -#endif // ifndef NDEBUG - - LLVM_DEBUG(dbgs() << " Eliminating redundant partitioners:\n"); - filterRedundantPartitioners(); - LLVM_DEBUG(dbgs() << " Partitioners remaining:\n"); -#ifndef NDEBUG - for (const auto &Partitioner : Partitioners) - LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs()); - dbgs() << "\n"); -#endif // ifndef NDEBUG - - if (Partitioners.empty()) { - // Nothing left to do but check we really did identify a single rule. - if (Leaves.size() > 1) { - LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first " - "fully tested rule\n"); - auto FirstFullyTested = - llvm::find_if(Leaves, [](const GIMatchTreeBuilderLeafInfo &X) { - return X.isFullyTraversed() && X.isFullyTested() && - !X.getMatchDag().hasPostMatchPredicate(); - }); - if (FirstFullyTested != Leaves.end()) - FirstFullyTested++; - -#ifndef NDEBUG - for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested)) - LLVM_DEBUG(dbgs() << " Kept " << Leaf.getName() << "\n"); - for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end())) - LLVM_DEBUG(dbgs() << " Dropped " << Leaf.getName() << "\n"); -#endif // ifndef NDEBUG - TreeNode->dropLeavesAfter( - std::distance(Leaves.begin(), FirstFullyTested)); - } - for (const auto &Leaf : Leaves) { - if (!Leaf.isFullyTraversed()) { - PrintError("Leaf " + Leaf.getName() + " is not fully traversed"); - PrintNote("This indicates a missing partitioner within tblgen"); - Leaf.dump(errs()); - for (unsigned InstrIdx : Leaf.untested_instrs()) - PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx))); - for (unsigned EdgeIdx : Leaf.untested_edges()) - PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx))); - } - } - - // Copy out information about untested predicates so the user of the tree - // can deal with them. - for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) { - const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair); - GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair); - if (!BuilderLeaf.isFullyTested()) - for (unsigned PredicateIdx : BuilderLeaf.untested_predicates()) - TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx)); - } - return; - } - - LLVM_DEBUG(dbgs() << " Weighing up partitioners:\n"); - evaluatePartitioners(); - - // Select the best partitioner by its ability to partition - // - Prefer partitioners that don't distinguish between partitions. This - // is to fail early on decisions that must go a single way. - auto PartitionerI = std::max_element( - Partitioners.begin(), Partitioners.end(), - [](const std::unique_ptr &A, - const std::unique_ptr &B) { - // We generally want partitioners that subdivide the - // ruleset as much as possible since these take fewer - // checks to converge on a particular rule. However, - // it's important to note that one leaf can end up in - // multiple partitions if the check isn't mutually - // exclusive (e.g. getVRegDef() vs isReg()). - // We therefore minimize average leaves per partition. - return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() > - (double)B->getNumLeavesWithDupes() / B->getNumPartitions(); - }); - - // Select a partitioner and partition the ruleset - // Note that it's possible for a single rule to end up in multiple - // partitions. For example, an opcode test on a rule without an opcode - // predicate will result in it being passed to all partitions. - std::unique_ptr Partitioner = std::move(*PartitionerI); - Partitioners.erase(PartitionerI); - LLVM_DEBUG(dbgs() << " Selected partitioner: "; - Partitioner->emitDescription(dbgs()); dbgs() << "\n"); - - assert(Partitioner->getNumPartitions() > 0 && - "Must always partition into at least one partition"); - - TreeNode->setNumChildren(Partitioner->getNumPartitions()); - for (const auto &[Idx, Child] : enumerate(TreeNode->children())) { - SubtreeBuilders.emplace_back(&Child, NextInstrID); - Partitioner->applyForPartition(Idx, *this, SubtreeBuilders.back()); - } - - TreeNode->setPartitioner(std::move(Partitioner)); - - // Recurse into the subtree builders. Each one must get a copy of the - // remaining partitioners as each path has to check everything. - for (auto &SubtreeBuilder : SubtreeBuilders) { - for (const auto &Partitioner : Partitioners) - SubtreeBuilder.addPartitioner(Partitioner->clone()); - SubtreeBuilder.runStep(); - } -} - -std::unique_ptr GIMatchTreeBuilder::run() { - unsigned NewInstrID = allocInstrID(); - // Start by recording the root instruction as instr #0 and set up the initial - // partitioners. - for (auto &Leaf : Leaves) { - LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName())); - GIMatchDagInstr *Root = - *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx()); - Leaf.declareInstr(Root, NewInstrID); - } - - addPartitionersForInstr(NewInstrID); - - std::unique_ptr TreeRoot = std::make_unique(); - TreeNode = TreeRoot.get(); - runStep(); - - return TreeRoot; -} - -void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const { - if (PartitionToInstr[Idx] == nullptr) { - OS << "* or nullptr"; - return; - } - OS << PartitionToInstr[Idx]->Namespace - << "::" << PartitionToInstr[Idx]->TheDef->getName(); -} - -void GIMatchTreeOpcodePartitioner::repartition( - GIMatchTreeBuilder::LeafVec &Leaves) { - Partitions.clear(); - InstrToPartition.clear(); - PartitionToInstr.clear(); - TestedPredicates.clear(); - - for (const auto &Leaf : enumerate(Leaves)) { - bool AllOpcodes = true; - GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); - BitVector TestedPredicatesForLeaf( - Leaf.value().getMatchDag().getNumPredicates()); - - // If the instruction isn't declared then we don't care about it. Ignore - // it for now and add it to all partitions later once we know what - // partitions we have. - if (!InstrInfo) { - LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() - << " doesn't care about Instr[" << InstrID << "]\n"); - assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates()); - TestedPredicates.push_back(TestedPredicatesForLeaf); - continue; - } - - // If the opcode is available to test then any opcode predicates will have - // been enabled too. - for (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) { - const auto &P = Leaf.value().getPredicate(PIdx); - SmallVector OpcodesForThisPredicate; - if (const auto *OpcodeP = dyn_cast(P)) { - // We've found _an_ opcode predicate, but we don't know if it's - // checking this instruction yet. - bool IsThisPredicate = false; - for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) { - if (PDep->getRequiredMI() == InstrInfo->getInstrNode() && - PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) { - IsThisPredicate = true; - break; - } - } - if (!IsThisPredicate) - continue; - - // If we get here twice then we've somehow ended up with two opcode - // predicates for one instruction in the same DAG. That should be - // impossible. - assert(AllOpcodes && "Conflicting opcode predicates"); - const CodeGenInstruction *Expected = OpcodeP->getInstr(); - OpcodesForThisPredicate.push_back(Expected); - } - - if (const auto *OpcodeP = - dyn_cast(P)) { - // We've found _an_ oneof(opcodes) predicate, but we don't know if it's - // checking this instruction yet. - bool IsThisPredicate = false; - for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) { - if (PDep->getRequiredMI() == InstrInfo->getInstrNode() && - PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) { - IsThisPredicate = true; - break; - } - } - if (!IsThisPredicate) - continue; - - // If we get here twice then we've somehow ended up with two opcode - // predicates for one instruction in the same DAG. That should be - // impossible. - assert(AllOpcodes && "Conflicting opcode predicates"); - append_range(OpcodesForThisPredicate, OpcodeP->getInstrs()); - } - - for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) { - // Mark this predicate as one we're testing. - TestedPredicatesForLeaf.set(PIdx); - - // Partitions must be numbered 0, 1, .., N but instructions don't meet - // that requirement. Assign a partition number to each opcode if we - // lack one ... - auto Partition = InstrToPartition.find(Expected); - if (Partition == InstrToPartition.end()) { - BitVector Contents(Leaves.size()); - Partition = InstrToPartition - .insert(std::make_pair(Expected, Partitions.size())) - .first; - PartitionToInstr.push_back(Expected); - Partitions.insert(std::make_pair(Partitions.size(), Contents)); - } - // ... and mark this leaf as being in that partition. - Partitions.find(Partition->second)->second.set(Leaf.index()); - AllOpcodes = false; - LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() - << " is in partition " << Partition->second << "\n"); - } - - // TODO: This is where we would handle multiple choices of opcode - // the end result will be that this leaf ends up in multiple - // partitions similarly to AllOpcodes. - } - - // If we never check the opcode, add it to every partition. - if (AllOpcodes) { - // Add a partition for the default case if we don't already have one. - if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { - PartitionToInstr.push_back(nullptr); - BitVector Contents(Leaves.size()); - Partitions.insert(std::make_pair(Partitions.size(), Contents)); - } - LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() - << " is in all partitions (opcode not checked)\n"); - for (auto &Partition : Partitions) - Partition.second.set(Leaf.index()); - } - - assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates()); - TestedPredicates.push_back(TestedPredicatesForLeaf); - } - - if (Partitions.size() == 0) { - // Add a partition for the default case if we don't already have one. - if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { - PartitionToInstr.push_back(nullptr); - BitVector Contents(Leaves.size()); - Partitions.insert(std::make_pair(Partitions.size(), Contents)); - } - } - - // Add any leaves that don't care about this instruction to all partitions. - for (const auto &Leaf : enumerate(Leaves)) { - GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); - if (!InstrInfo) { - // Add a partition for the default case if we don't already have one. - if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { - PartitionToInstr.push_back(nullptr); - BitVector Contents(Leaves.size()); - Partitions.insert(std::make_pair(Partitions.size(), Contents)); - } - for (auto &Partition : Partitions) - Partition.second.set(Leaf.index()); - } - } - -} - -void GIMatchTreeOpcodePartitioner::applyForPartition( - unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) { - LLVM_DEBUG(dbgs() << " Making partition " << PartitionIdx << "\n"); - const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx]; - - BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx); - // Consume any predicates we handled. - for (const auto &[Index, EnumeratedLeaf] : - enumerate(Builder.getPossibleLeaves())) { - if (!PossibleLeaves[Index]) - continue; - - const auto &TestedPredicatesForLeaf = TestedPredicates[Index]; - - for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) { - LLVM_DEBUG(dbgs() << " " << EnumeratedLeaf.getName() - << " tested predicate #" << PredIdx << " of " - << TestedPredicatesForLeaf.size() << " " - << *EnumeratedLeaf.getPredicate(PredIdx) << "\n"); - EnumeratedLeaf.RemainingPredicates.reset(PredIdx); - EnumeratedLeaf.TestablePredicates.reset(PredIdx); - } - SubBuilder.addLeaf(EnumeratedLeaf); - } - - // Nothing to do, we don't know anything about this instruction as a result - // of this partitioner. - if (CGI == nullptr) - return; - - GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves(); - // Find all the operands we know to exist and are referenced. This will - // usually be all the referenced operands but there are some cases where - // instructions are variadic. Such operands must be handled by partitioners - // that check the number of operands. - BitVector ReferencedOperands(1); - for (auto &Leaf : NewLeaves) { - GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID); - // Skip any leaves that don't care about this instruction. - if (!InstrInfo) - continue; - const GIMatchDagInstr *Instr = InstrInfo->getInstrNode(); - for (const auto &E : Leaf.getMatchDag().edges()) { - if (E->getFromMI() == Instr && - E->getFromMO()->getIdx() < CGI->Operands.size()) { - ReferencedOperands.resize(E->getFromMO()->getIdx() + 1); - ReferencedOperands.set(E->getFromMO()->getIdx()); - } - } - } - for (auto &Leaf : NewLeaves) { - // Skip any leaves that don't care about this instruction. - if (!Leaf.getInstrInfo(InstrID)) - continue; - - for (unsigned OpIdx : ReferencedOperands.set_bits()) { - Leaf.declareOperand(InstrID, OpIdx); - } - } - for (unsigned OpIdx : ReferencedOperands.set_bits()) { - SubBuilder.addPartitionersForOperand(InstrID, OpIdx); - } -} - -void GIMatchTreeOpcodePartitioner::emitPartitionResults( - raw_ostream &OS) const { - OS << "Partitioning by opcode would produce " << Partitions.size() - << " partitions\n"; - for (const auto &Partition : InstrToPartition) { - if (Partition.first == nullptr) - OS << "Default: "; - else - OS << Partition.first->TheDef->getName() << ": "; - StringRef Separator = ""; - for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) { - OS << Separator << I; - Separator = ", "; - } - OS << "\n"; - } -} - -void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode( - raw_ostream &OS, StringRef Indent) const { - // Make sure not to emit empty switch or switch with just default - if (PartitionToInstr.size() == 1 && PartitionToInstr[0] == nullptr) { - OS << Indent << "Partition = 0;\n"; - } else if (PartitionToInstr.size()) { - OS << Indent << "Partition = -1;\n" - << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n"; - for (const auto &EnumInstr : enumerate(PartitionToInstr)) { - if (EnumInstr.value() == nullptr) - OS << Indent << "default:"; - else - OS << Indent << "case " << EnumInstr.value()->Namespace - << "::" << EnumInstr.value()->TheDef->getName() << ":"; - OS << " Partition = " << EnumInstr.index() << "; break;\n"; - } - OS << Indent << "}\n"; - } - OS << Indent - << "// Default case but without conflicting with potential default case " - "in selection.\n" - << Indent << "if (Partition == -1) return false;\n"; -} - -void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result, - unsigned LeafIdx) { - auto I = ResultToPartition.find(Result); - if (I == ResultToPartition.end()) { - ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size())); - PartitionToResult.push_back(Result); - } - I = ResultToPartition.find(Result); - auto P = Partitions.find(I->second); - if (P == Partitions.end()) - P = Partitions.insert(std::make_pair(I->second, BitVector())).first; - P->second.resize(LeafIdx + 1); - P->second.set(LeafIdx); -} - -void GIMatchTreeVRegDefPartitioner::repartition( - GIMatchTreeBuilder::LeafVec &Leaves) { - Partitions.clear(); - - for (const auto &Leaf : enumerate(Leaves)) { - GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); - BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges()); - - // If the instruction isn't declared then we don't care about it. Ignore - // it for now and add it to all partitions later once we know what - // partitions we have. - if (!InstrInfo) { - TraversedEdges.push_back(TraversedEdgesForLeaf); - continue; - } - - // If this node has an use -> def edge from this operand then this - // instruction must be in partition 1 (isVRegDef()). - bool WantsEdge = false; - for (unsigned EIdx : Leaf.value().TraversableEdges.set_bits()) { - const auto &E = Leaf.value().getEdge(EIdx); - if (E->getFromMI() != InstrInfo->getInstrNode() || - E->getFromMO()->getIdx() != OpIdx || E->isDefToUse()) - continue; - - // We're looking at the right edge. This leaf wants a vreg def so we'll - // put it in partition 1. - addToPartition(true, Leaf.index()); - TraversedEdgesForLeaf.set(EIdx); - WantsEdge = true; - } - - if (!WantsEdge) { - // If this leaf doesn't have an edge and we don't know what we want, - // then add it to partition 0 and 1. - addToPartition(false, Leaf.index()); - addToPartition(true, Leaf.index()); - } - - TraversedEdges.push_back(TraversedEdgesForLeaf); - } - - // Add any leaves that don't care about this instruction to all partitions. - for (const auto &Leaf : enumerate(Leaves)) { - GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); - if (!InstrInfo) - for (auto &Partition : Partitions) { - Partition.second.resize(Leaf.index() + 1); - Partition.second.set(Leaf.index()); - } - } -} - -void GIMatchTreeVRegDefPartitioner::applyForPartition( - unsigned PartitionIdx, GIMatchTreeBuilder &Builder, - GIMatchTreeBuilder &SubBuilder) { - BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx); - - std::vector TraversedEdgesByNewLeaves; - // Consume any edges we handled. - for (const auto &[Index, EnumeratedLeaf] : - enumerate(Builder.getPossibleLeaves())) { - if (!PossibleLeaves[Index]) - continue; - - const auto &TraversedEdgesForLeaf = TraversedEdges[Index]; - TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf); - EnumeratedLeaf.RemainingEdges.reset(TraversedEdgesForLeaf); - EnumeratedLeaf.TraversableEdges.reset(TraversedEdgesForLeaf); - SubBuilder.addLeaf(EnumeratedLeaf); - } - - // Nothing to do. The only thing we know is that it isn't a vreg-def. - if (PartitionToResult[PartitionIdx] == false) - return; - - NewInstrID = SubBuilder.allocInstrID(); - - GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves(); - for (const auto &I : zip(NewLeaves, TraversedEdgesByNewLeaves)) { - auto &Leaf = std::get<0>(I); - auto &TraversedEdgesForLeaf = std::get<1>(I); - GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID); - // Skip any leaves that don't care about this instruction. - if (!InstrInfo) - continue; - for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) { - const GIMatchDagEdge *E = Leaf.getEdge(EIdx); - Leaf.declareInstr(E->getToMI(), NewInstrID); - } - } - SubBuilder.addPartitionersForInstr(NewInstrID); -} - -void GIMatchTreeVRegDefPartitioner::emitPartitionResults( - raw_ostream &OS) const { - OS << "Partitioning by vreg-def would produce " << Partitions.size() - << " partitions\n"; - for (const auto &Partition : Partitions) { - OS << Partition.first << " ("; - emitPartitionName(OS, Partition.first); - OS << "): "; - StringRef Separator = ""; - for (unsigned I : Partition.second.set_bits()) { - OS << Separator << I; - Separator = ", "; - } - OS << "\n"; - } -} - -void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode( - raw_ostream &OS, StringRef Indent) const { - OS << Indent << "Partition = -1;\n" - << Indent << "if (MIs.size() <= " << NewInstrID << ") MIs.resize(" - << (NewInstrID + 1) << ");\n" - << Indent << "MIs[" << NewInstrID << "] = nullptr;\n" - << Indent << "if (MIs[" << InstrID << "]->getOperand(" << OpIdx - << ").isReg())\n" - << Indent << " MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID - << "]->getOperand(" << OpIdx << ").getReg());\n"; - - for (const auto &Pair : ResultToPartition) - OS << Indent << "if (MIs[" << NewInstrID << "] " - << (Pair.first ? "!=" : "==") - << " nullptr) Partition = " << Pair.second << ";\n"; - - OS << Indent << "if (Partition == -1) return false;\n"; -} diff --git a/llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp b/llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp rename from llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp rename to llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp --- a/llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp +++ b/llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp @@ -52,17 +52,23 @@ using namespace llvm; using namespace llvm::gi; -#define DEBUG_TYPE "gicombiner-matchtable-emitter" +#define DEBUG_TYPE "gicombiner-emitter" -extern cl::list SelectedCombiners; -extern cl::opt StopAfterParse; -extern cl::OptionCategory GICombinerEmitterCat; - -static cl::opt DebugCXXPreds( - "gicombiner-matchtable-debug-cxxpreds", +namespace { +cl::OptionCategory + GICombinerEmitterCat("Options for -gen-global-isel-combiner"); +cl::opt StopAfterParse( + "gicombiner-stop-after-parse", + cl::desc("Stop processing after parsing rules and dump state"), + cl::cat(GICombinerEmitterCat)); +cl::list + SelectedCombiners("combiners", cl::desc("Emit the specified combiners"), + cl::cat(GICombinerEmitterCat), cl::CommaSeparated); +cl::opt DebugCXXPreds( + "gicombiner-debug-cxxpreds", cl::desc("Add Contextual/Debug comments to all C++ predicates"), cl::cat(GICombinerEmitterCat)); -namespace { + constexpr StringLiteral CXXApplyPrefix = "GICXXCustomAction_CombineApply"; constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_"; constexpr StringLiteral PatFragClassName = "GICombinePatFrag"; @@ -3488,6 +3494,5 @@ } } -static TableGen::Emitter::Opt X("gen-global-isel-combiner-matchtable", - EmitGICombiner, - "Generate GlobalISel combiner Match Table"); +static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner, + "Generate GlobalISel Combiner"); diff --git a/llvm/utils/gn/secondary/llvm/lib/Target/AArch64/BUILD.gn b/llvm/utils/gn/secondary/llvm/lib/Target/AArch64/BUILD.gn --- a/llvm/utils/gn/secondary/llvm/lib/Target/AArch64/BUILD.gn +++ b/llvm/utils/gn/secondary/llvm/lib/Target/AArch64/BUILD.gn @@ -21,7 +21,7 @@ tablegen("AArch64GenO0PreLegalizeGICombiner") { visibility = [ ":LLVMAArch64CodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AArch64O0PreLegalizerCombiner", ] td_file = "AArch64.td" @@ -42,7 +42,7 @@ tablegen("AArch64GenPostLegalizeGICombiner") { visibility = [ ":LLVMAArch64CodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AArch64PostLegalizerCombiner", ] td_file = "AArch64.td" @@ -51,7 +51,7 @@ tablegen("AArch64GenPreLegalizeGICombiner") { visibility = [ ":LLVMAArch64CodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AArch64PreLegalizerCombiner", ] td_file = "AArch64.td" @@ -60,7 +60,7 @@ tablegen("AArch64GenPostLegalizeGILowering") { visibility = [ ":LLVMAArch64CodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AArch64PostLegalizerLowering", ] td_file = "AArch64.td" diff --git a/llvm/utils/gn/secondary/llvm/lib/Target/AMDGPU/BUILD.gn b/llvm/utils/gn/secondary/llvm/lib/Target/AMDGPU/BUILD.gn --- a/llvm/utils/gn/secondary/llvm/lib/Target/AMDGPU/BUILD.gn +++ b/llvm/utils/gn/secondary/llvm/lib/Target/AMDGPU/BUILD.gn @@ -27,7 +27,7 @@ tablegen("AMDGPUGenPreLegalizeGICombiner") { visibility = [ ":LLVMAMDGPUCodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AMDGPUPreLegalizerCombiner", ] td_file = "AMDGPUGISel.td" @@ -36,7 +36,7 @@ tablegen("AMDGPUGenPostLegalizeGICombiner") { visibility = [ ":LLVMAMDGPUCodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AMDGPUPostLegalizerCombiner", ] td_file = "AMDGPUGISel.td" @@ -45,7 +45,7 @@ tablegen("AMDGPUGenRegBankGICombiner") { visibility = [ ":LLVMAMDGPUCodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=AMDGPURegBankCombiner", ] td_file = "AMDGPUGISel.td" diff --git a/llvm/utils/gn/secondary/llvm/lib/Target/Mips/BUILD.gn b/llvm/utils/gn/secondary/llvm/lib/Target/Mips/BUILD.gn --- a/llvm/utils/gn/secondary/llvm/lib/Target/Mips/BUILD.gn +++ b/llvm/utils/gn/secondary/llvm/lib/Target/Mips/BUILD.gn @@ -33,7 +33,7 @@ tablegen("MipsGenPostLegalizeGICombiner") { visibility = [ ":LLVMMipsCodeGen" ] args = [ - "-gen-global-isel-combiner-matchtable", + "-gen-global-isel-combiner", "-combiners=MipsPostLegalizerCombiner", ] td_file = "Mips.td" diff --git a/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel b/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel @@ -1813,10 +1813,10 @@ ("-gen-dag-isel", "lib/Target/AArch64/AArch64GenDAGISel.inc"), ("-gen-fast-isel", "lib/Target/AArch64/AArch64GenFastISel.inc"), ("-gen-global-isel", "lib/Target/AArch64/AArch64GenGlobalISel.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AArch64O0PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenO0PreLegalizeGICombiner.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AArch64PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenPreLegalizeGICombiner.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AArch64PostLegalizerCombiner", "lib/Target/AArch64/AArch64GenPostLegalizeGICombiner.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AArch64PostLegalizerLowering", "lib/Target/AArch64/AArch64GenPostLegalizeGILowering.inc"), + ("-gen-global-isel-combiner -combiners=AArch64O0PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenO0PreLegalizeGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=AArch64PreLegalizerCombiner", "lib/Target/AArch64/AArch64GenPreLegalizeGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=AArch64PostLegalizerCombiner", "lib/Target/AArch64/AArch64GenPostLegalizeGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=AArch64PostLegalizerLowering", "lib/Target/AArch64/AArch64GenPostLegalizeGILowering.inc"), ("-gen-callingconv", "lib/Target/AArch64/AArch64GenCallingConv.inc"), ("-gen-subtarget", "lib/Target/AArch64/AArch64GenSubtargetInfo.inc"), ("-gen-disassembler", "lib/Target/AArch64/AArch64GenDisassemblerTables.inc"), @@ -1956,7 +1956,7 @@ ("-gen-exegesis", "lib/Target/Mips/MipsGenExegesis.inc"), ("-gen-fast-isel", "lib/Target/Mips/MipsGenFastISel.inc"), ("-gen-global-isel", "lib/Target/Mips/MipsGenGlobalISel.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=MipsPostLegalizerCombiner", "lib/Target/Mips/MipsGenPostLegalizeGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=MipsPostLegalizerCombiner", "lib/Target/Mips/MipsGenPostLegalizeGICombiner.inc"), ("-gen-instr-info", "lib/Target/Mips/MipsGenInstrInfo.inc"), ("-gen-pseudo-lowering", "lib/Target/Mips/MipsGenMCPseudoLowering.inc"), ("-gen-register-bank", "lib/Target/Mips/MipsGenRegisterBank.inc"), @@ -2147,9 +2147,9 @@ strip_include_prefix = "lib/Target/AMDGPU", tbl_outs = [ ("-gen-global-isel", "lib/Target/AMDGPU/AMDGPUGenGlobalISel.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AMDGPUPreLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPreLegalizeGICombiner.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AMDGPUPostLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPostLegalizeGICombiner.inc"), - ("-gen-global-isel-combiner-matchtable -combiners=AMDGPURegBankCombiner", "lib/Target/AMDGPU/AMDGPUGenRegBankGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=AMDGPUPreLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPreLegalizeGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=AMDGPUPostLegalizerCombiner", "lib/Target/AMDGPU/AMDGPUGenPostLegalizeGICombiner.inc"), + ("-gen-global-isel-combiner -combiners=AMDGPURegBankCombiner", "lib/Target/AMDGPU/AMDGPUGenRegBankGICombiner.inc"), ], tblgen = ":llvm-tblgen", td_file = "lib/Target/AMDGPU/AMDGPUGISel.td",