[GISel] Fix match tree emitter.

[Kai]

Summary

The following changes are necessary to get the generated tree matcher to compile:

• In CodeExpansions::declare(), the assert() prevents connecting two instructions. E.g. the match code (match (MUL $t, $s1, $s2), (SUB $d, $t, $s3)), results in two declarations of $t, one for the def and one for the use. Removing the assertion allows this construct. If $t is later used, it is one of the operands, which should be perfectly fine for now.
  • The code emitted in GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode() is not compilable:
    • The value of NewInstrID should be emitted, not the name
    • Both calls involving getOperand() end with one parenthesis too many
  • Swaps generated condition for the partition code in the latter function

With these changes it is possible to use linear patterns.

I also change the rules i2p_to_p2i, fabs_fabs_fold, and fneg_fneg_fold
to use the tree matcher for a linear match. These rules are tested by:

CodeGen/AArch64/GlobalISel/combine-fabs.mir
CodeGen/AArch64/GlobalISel/combine-fneg.mir
CodeGen/AArch64/GlobalISel/combine-ptrtoint.mir
CodeGen/AMDGPU/GlobalISel/combine-add-nullptr.mir

[tschuett]

Did you forget the test case?

llvm/utils/TableGen/GlobalISel/CodeExpansions.h

26–27

You don't need the Inserted variable anymore.

[Kai]

Added missing test.

[Kai]

In D133257#3768704, @tschuett wrote:

Did you forget the test case?

Oops, yes. The crash is easily verified by running llvm-tblgen without -gicombiner-stop-after-build option.
For the syntax errors I currently do not have a good test. I tried to rewrite one of the combine rules in
Combine.td, but this resulted in some regression. :-( One issue with this code here is that it is obviously
not really used.

[Kai]

Remove unused Inserted variable.

[tschuett]

Would a new file match-tree2.td help you? Without include Combine.td. Then you can limit the test to a minimum.

[Kai]

I made another fix which enables matching of linear patterns.
To showcase the functionality I changed 3 simple combine rules
to use linear matching. All changed rules are covered by existing
tests.

[arsenm]

It would be good to add a dedicated tablegen test for this checking the generated code. I find them helpful when trying to extend tablegen without having to make some manageable sized extract to start from

llvm/include/llvm/Target/GlobalISel/Combine.td

534

Should also delete matchCombineFNegOfFNeg

559

Should also delete matchCombineFAbsOfFAbs

llvm/utils/TableGen/GlobalISel/CodeExpansions.h

27–30

Comment doesn't read right. Maybe you meant "refers not to different operands"?

[Kai]

• Remove unused functions in CombineHelper
• Add test checking source code

[Kai]

llvm/utils/TableGen/GlobalISel/CodeExpansions.h

27–30

What I am trying to describe: Consider

(match (MUL $t, $s1, $s2),
       (SUB $d, $t, $s3)),

the variable $t appears twice in the pattern, and declare() is called twice.

• • One replacement is MIs[0]->getOperand(1), that is, the use in the SUB instruction
• The other replacement is MIs[1]->getOperand(0), the definition in the MUL instruction

Thus the operands are different (even of different instructions), but both refer to the same virtual register.

[arsenm]

llvm/utils/TableGen/GlobalISel/CodeExpansions.h

27–30

How about

Duplicates are not inserted. The expansion refers to different MachineOperands using the same virtual register

[Kai]

Update comment.

[arsenm]

LGTM

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

public:
   void applyCombineConstantFoldFpUnary(MachineInstr &MI,
                                        Optional<APFloat> &Cst);
 
   /// Transform IntToPtr(PtrToInt(x)) to x if cast is in the same address space.
   bool matchCombineI2PToP2I(MachineInstr &MI, Register &Reg);
   void applyCombineI2PToP2I(MachineInstr &MI, Register &Reg);
 
   /// Transform PtrToInt(IntToPtr(x)) to x.
-  bool matchCombineP2IToI2P(MachineInstr &MI, Register &Reg);
   void applyCombineP2IToI2P(MachineInstr &MI, Register &Reg);
 
   /// Transform G_ADD (G_PTRTOINT x), y -> G_PTRTOINT (G_PTR_ADD x, y)
   /// Transform G_ADD y, (G_PTRTOINT x) -> G_PTRTOINT (G_PTR_ADD x, y)
   bool matchCombineAddP2IToPtrAdd(MachineInstr &MI,
                                   std::pair<Register, bool> &PtrRegAndCommute);
   void applyCombineAddP2IToPtrAdd(MachineInstr &MI,
                                   std::pair<Register, bool> &PtrRegAndCommute);
public:
   bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg);
 
   /// Transform [asz]ext([asz]ext(x)) to [asz]ext x.
   bool matchCombineExtOfExt(MachineInstr &MI,
                             std::tuple<Register, unsigned> &MatchInfo);
   void applyCombineExtOfExt(MachineInstr &MI,
                             std::tuple<Register, unsigned> &MatchInfo);
 
-  /// Transform fneg(fneg(x)) to x.
-  bool matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg);
-
-  /// Match fabs(fabs(x)) to fabs(x).
-  bool matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src);
+  /// Transform fabs(fabs(x)) to fabs(x).
   void applyCombineFAbsOfFAbs(MachineInstr &MI, Register &Src);
 
   /// Transform fabs(fneg(x)) to fabs(x).
   bool matchCombineFAbsOfFNeg(MachineInstr &MI, BuildFnTy &MatchInfo);
 
   /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x).
   bool matchCombineTruncOfExt(MachineInstr &MI,
                               std::pair<Register, unsigned> &MatchInfo);

llvm/include/llvm/Target/GlobalISel/Combine.td

def p2i_to_i2p: GICombineRule<
   (defs root:$root, register_matchinfo:$info),
   (match (wip_match_opcode G_INTTOPTR):$root,
     [{ return Helper.matchCombineI2PToP2I(*${root}, ${info}); }]),
   (apply [{ Helper.applyCombineI2PToP2I(*${root}, ${info}); }])
 >;
 
 // Fold ptr2int(int2ptr(x)) -> x
 def i2p_to_p2i: GICombineRule<
-  (defs root:$root, register_matchinfo:$info),
-  (match (wip_match_opcode G_PTRTOINT):$root,
-    [{ return Helper.matchCombineP2IToI2P(*${root}, ${info}); }]),
-  (apply [{ Helper.applyCombineP2IToI2P(*${root}, ${info}); }])
+  (defs root:$dst, register_matchinfo:$info),
+  (match (G_INTTOPTR $t, $ptr),
+         (G_PTRTOINT $dst, $t):$mi,
+    [{ ${info} = ${ptr}.getReg(); }]),
+  (apply [{ Helper.applyCombineP2IToI2P(*${mi}, ${info}); }])
 >;
 
 // Fold add ptrtoint(x), y -> ptrtoint (ptr_add x), y
 def add_p2i_to_ptradd_matchinfo : GIDefMatchData<"std::pair<Register, bool>">;
 def add_p2i_to_ptradd : GICombineRule<
   (defs root:$root, add_p2i_to_ptradd_matchinfo:$info),
   (match (wip_match_opcode G_ADD):$root,
     [{ return Helper.matchCombineAddP2IToPtrAdd(*${root}, ${info}); }]),
def not_cmp_fold : GICombineRule<
   (defs root:$d, not_cmp_fold_matchinfo:$info),
   (match (wip_match_opcode G_XOR): $d,
   [{ return Helper.matchNotCmp(*${d}, ${info}); }]),
   (apply [{ Helper.applyNotCmp(*${d}, ${info}); }])
 >;
 
 // Fold (fneg (fneg x)) -> x.
 def fneg_fneg_fold: GICombineRule <
-  (defs root:$root, register_matchinfo:$matchinfo),
-  (match (wip_match_opcode G_FNEG):$root,
-         [{ return Helper.matchCombineFNegOfFNeg(*${root}, ${matchinfo}); }]),
-  (apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
+  (defs root:$dst, register_matchinfo:$matchinfo),
+  (match (G_FNEG $t, $src),
+         (G_FNEG $dst, $t):$mi,
+         [{ ${matchinfo} = ${src}.getReg(); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithReg(*${mi}, ${matchinfo}); }])
 >;
 
 // Fold (unmerge(merge x, y, z)) -> z, y, z.
 def unmerge_merge_matchinfo : GIDefMatchData<"SmallVector<Register, 8>">;
 def unmerge_merge : GICombineRule<
   (defs root:$d, unmerge_merge_matchinfo:$info),
   (match (wip_match_opcode G_UNMERGE_VALUES): $d,
   [{ return Helper.matchCombineUnmergeMergeToPlainValues(*${d}, ${info}); }]),
   (apply [{ Helper.applyCombineUnmergeMergeToPlainValues(*${d}, ${info}); }])
 >;
 
 // Fold merge(unmerge).
 def merge_unmerge : GICombineRule<
   (defs root:$d, register_matchinfo:$matchinfo),
   (match (wip_match_opcode G_MERGE_VALUES):$d,
   [{ return Helper.matchCombineMergeUnmerge(*${d}, ${matchinfo}); }]),
   (apply [{ Helper.replaceSingleDefInstWithReg(*${d}, ${matchinfo}); }])
 >;
 
 // Fold (fabs (fabs x)) -> (fabs x).
 def fabs_fabs_fold: GICombineRule<
-  (defs root:$root, register_matchinfo:$matchinfo),
-  (match (wip_match_opcode G_FABS):$root,
-         [{ return Helper.matchCombineFAbsOfFAbs(*${root}, ${matchinfo}); }]),
-  (apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
+  (defs root:$dst, register_matchinfo:$matchinfo),
+  (match (G_FABS $abs, $src),
+         (G_FABS $dst, $abs):$mi,
+         [{ ${matchinfo} = ${abs}.getReg(); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithReg(*${mi}, ${matchinfo}); }])
 >;
 
 // Fold (fabs (fneg x)) -> (fabs x).
 def fabs_fneg_fold: GICombineRule <
   (defs root:$root, build_fn_matchinfo:$matchinfo),
   (match (wip_match_opcode G_FABS):$root,
          [{ return Helper.matchCombineFAbsOfFNeg(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyBuildFnNoErase(*${root}, ${matchinfo}); }])>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 void CombinerHelper::applyCombineI2PToP2I(MachineInstr &MI, Register &Reg) {
   assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR");
   Register DstReg = MI.getOperand(0).getReg();
   Builder.setInstr(MI);
   Builder.buildCopy(DstReg, Reg);
   MI.eraseFromParent();
 }
 
-bool CombinerHelper::matchCombineP2IToI2P(MachineInstr &MI, Register &Reg) {
-  assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT");
-  Register SrcReg = MI.getOperand(1).getReg();
-  return mi_match(SrcReg, MRI, m_GIntToPtr(m_Reg(Reg)));
-}
-
 void CombinerHelper::applyCombineP2IToI2P(MachineInstr &MI, Register &Reg) {
   assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT");
   Register DstReg = MI.getOperand(0).getReg();
   Builder.setInstr(MI);
   Builder.buildZExtOrTrunc(DstReg, Reg);
   MI.eraseFromParent();
 }
 
void CombinerHelper::applyCombineMulByNegativeOne(MachineInstr &MI) {
   LLT DstTy = MRI.getType(DstReg);
 
   Builder.setInstrAndDebugLoc(MI);
   Builder.buildSub(DstReg, Builder.buildConstant(DstTy, 0), SrcReg,
                    MI.getFlags());
   MI.eraseFromParent();
 }
 
-bool CombinerHelper::matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg) {
-  assert(MI.getOpcode() == TargetOpcode::G_FNEG && "Expected a G_FNEG");
-  Register SrcReg = MI.getOperand(1).getReg();
-  return mi_match(SrcReg, MRI, m_GFNeg(m_Reg(Reg)));
-}
-
-bool CombinerHelper::matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src) {
-  assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS");
-  Src = MI.getOperand(1).getReg();
-  Register AbsSrc;
-  return mi_match(Src, MRI, m_GFabs(m_Reg(AbsSrc)));
-}
-
 bool CombinerHelper::matchCombineFAbsOfFNeg(MachineInstr &MI,
                                             BuildFnTy &MatchInfo) {
   assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS");
   Register Src = MI.getOperand(1).getReg();
   Register NegSrc;
 
   if (!mi_match(Src, MRI, m_GFNeg(m_Reg(NegSrc))))
     return false;

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

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

 // 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"]
 // 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: }
+
+// 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:            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:            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:          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:  }
+

llvm/utils/TableGen/GlobalISel/CodeExpansions.h

 class CodeExpansions {
 public:
   using const_iterator = StringMap<std::string>::const_iterator;
 
 protected:
   StringMap<std::string> Expansions;
 
 public:
   void declare(StringRef Name, StringRef Expansion) {
-    bool Inserted = Expansions.try_emplace(Name, Expansion).second;
-    assert(Inserted && "Declared variable twice");
-    (void)Inserted;
+    // Duplicates are not inserted. The expansion refers to different
+    // MachineOperands using the same virtual register.
+    Expansions.try_emplace(Name, Expansion);
   }
 
   std::string lookup(StringRef Variable) const {
     return Expansions.lookup(Variable);
   }
 
   const_iterator begin() const { return Expansions.begin(); }
   const_iterator end() const { return Expansions.end(); }
   const_iterator find(StringRef Variable) const {
     return Expansions.find(Variable);
   }
 };
 } // end namespace llvm
 #endif // ifndef LLVM_UTILS_TABLEGEN_CODEEXPANSIONS_H

llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp

for (unsigned I : Partition.second.set_bits()) {
       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"
+  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 << "if (MIs[" << InstrID << "]->getOperand(" << OpIdx
+     << ").isReg())\n"
      << Indent << "  MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
-     << "].getOperand(" << OpIdx << ").getReg()));\n";
+     << "]->getOperand(" << OpIdx << ").getReg());\n";
 
   for (const auto &Pair : ResultToPartition)
     OS << Indent << "if (MIs[" << NewInstrID << "] "
-       << (Pair.first ? "==" : "!=")
+       << (Pair.first ? "!=" : "==")
        << " nullptr) Partition = " << Pair.second << ";\n";
 
   OS << Indent << "if (Partition == -1) return false;\n";
 }