[GISel] TreeMatcher: always skip leaves if they don't care

[Kai]

Summary

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.

[arsenm]

LGTM with nit

llvm/test/TableGen/GICombinerEmitter/match-tree.td

80

Should add a comment explaining what this tests

[Kai]

• Adds a resize when adding the leaves which do not care about the instruction to all partitions, as it is done already in addToPartition()
• Adds a comment to the test. The test just follows the edges in the graph, to make sure the construction is correct.

[Kai]

Fix formatting complain from clang-format.

[arsenm]

LGTM but I don't see the comment

llvm/test/TableGen/GICombinerEmitter/match-tree.td

80

I don't see the comment here?

[Kai]

Add comment (again? hm.).

[Kai]

llvm/test/TableGen/GICombinerEmitter/match-tree.td

80

Sorry, now its there.

llvm/test/TableGen/GICombinerEmitter/match-tree.td

 }
 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 Rule0 : GICombineRule<
   (defs root:$d),
   (match (MUL $t, $s1, $s2),
          (SUB $d, $t, $s3)),
   (apply [{ APPLY }])>;
 
 def Rule1 : GICombineRule<
def Rule6 : GICombineRule<
   (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
+  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}"]
 // 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

 
 // 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;

llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp

for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
       if (E.value()->getFromMI() == Instr &&
           E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
         ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
         ReferencedOperands.set(E.value()->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);
   }
 }
for (const auto &Leaf : enumerate(Leaves)) {
 
     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)
+      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<BitVector> TraversedEdgesByNewLeaves;
   // Consume any edges we handled.