From 34a809591bf97bd8832dbbabd7f0b7f7a3355783 Mon Sep 17 00:00:00 2001 From: Kai Nacke Date: Mon, 19 Sep 2022 16:03:32 +0000 Subject: [PATCH] [GISel] TreeMatcher: always skip leaves if they don't care In `GIMatchTreeOpcodePartitioner::applyForPartition()`, the loop over the possible leaves skip a leaf if the instruction does not care about the instruction. When processing the referenced operands in the next loop the same leaves need to be skipped. Later, when these leaves are added to all partitions, the bit vector must be resized first before the bit representing the leaf is set. This fixes a crash in llvm-tblgen. Reviewed By: arsenm Differential Revision: https://reviews.llvm.org/D134192 --- llvm/test/TableGen/GICombinerEmitter/match-tree.td | 51 +++++++++++++++++++++- llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp | 8 +++- 2 files changed, 56 insertions(+), 3 deletions(-) diff --git a/llvm/test/TableGen/GICombinerEmitter/match-tree.td b/llvm/test/TableGen/GICombinerEmitter/match-tree.td index 64ab435..b52d7ae 100644 --- a/llvm/test/TableGen/GICombinerEmitter/match-tree.td +++ b/llvm/test/TableGen/GICombinerEmitter/match-tree.td @@ -30,6 +30,7 @@ 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 Rule0 : GICombineRule< (defs root:$d), @@ -76,6 +77,26 @@ def Rule7 : GICombineRule< (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, @@ -84,11 +105,13 @@ def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ Rule4, Rule5, Rule6, - Rule7 + Rule7, + Rule8, + Rule9 ]>; // CHECK-LABEL: digraph "matchtree" { -// CHECK-DAG: Node[[N0:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[0].getOpcode()|4 partitions|Rule0,Rule1,Rule2,Rule3,Rule4,Rule5,Rule6,Rule7}"] +// 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}"] @@ -108,12 +131,21 @@ def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ // 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 @@ -143,6 +175,20 @@ def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ // 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: {{^}$}} @@ -156,6 +202,7 @@ def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ // 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. diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp index f797e04..d988844 100644 --- a/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp +++ b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp @@ -580,6 +580,10 @@ void GIMatchTreeOpcodePartitioner::applyForPartition( } } 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); } @@ -697,8 +701,10 @@ void GIMatchTreeVRegDefPartitioner::repartition( for (const auto &Leaf : enumerate(Leaves)) { GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); if (!InstrInfo) - for (auto &Partition : Partitions) + for (auto &Partition : Partitions) { + Partition.second.resize(Leaf.index() + 1); Partition.second.set(Leaf.index()); + } } } -- 2.7.4