[TableGen][AsmMatcherEmitter] Generate assembler checks for tied operands

[sdesmalen]

Summary

This extends TableGen's AsmMatcherEmitter with code that generates
a table with tied-operand constraints. The constraints are checked
when parsing the instruction. If an operand is not equal to its tied operand,
the assembler will give an error.

Patch [2/3] in a series to add operand constraint checks for SVE's predicated ADD/SUB.

[fhahn]

Thanks Sander, I left some comments.

This is needed for SVE, because some instructions force 2 registers to be equal for certain versions of the instruction. e.g.

add z1, z2, z3 # OK
add z1, p0/m, z2, z3 # Not OK, for predicated add the result reg must be equal to the first data src reg.

Adding Oliver as well, maybe you have some thoughts on the error handling in this case. Is there another way to handle this case?

utils/TableGen/AsmMatcherEmitter.cpp

518

Do we need a set here? It seems like we could just used a SmallVector instead. It looks like a set is used to avoid adding duplicated constraints for an instruction, right?

But the tied constraint only gets added to one of the 2 operands (I think), see CodeGenInstructions::ParseConstraint.

Also, those constraints are referred to as tied elsewhere. AsmOperandTiedContraints would be a more consistent name I think

897

Can AsmOperands be const?

901

Why not AsmOperands.begin(), AsmOperands.end()?

906

Why not AsmOperands.end()?

909

Why not AsmOperands.begin()?

975

For relatively short type names, using explicit types slightly improves readability here and elsewhere in this patch

994

Make type here size_t.

2889

Please use Tied in the name here and throughout the function to make it clear that this only deals with Tied constraints.

2894

Please use something more descriptive than DCL.

2912

Use something more descriptive than x.

2935

Having a struct for the SearchValue would better explain what the 3 fields are supposed to be.

[fhahn]

This comment was removed by fhahn.

[sdesmalen]

Replaced unordered set by SmallVector and did some refactoring to improve readability.

[sdesmalen]

utils/TableGen/AsmMatcherEmitter.cpp

901

I can't answer the 'why', but I did fix it in the latest iteration of this patch :)

[fhahn]

utils/TableGen/AsmMatcherEmitter.cpp

969

I think the loop body here can be simplified by using CGIOp.getTiedRegister(); rather than checking the constraints here:

+    int TiedReg = CGIOp.getTiedRegister();
+    if (TiedReg == -1)
+      continue;
+
+    Optional<size_t> LHSIdx = getAsmOperandIdx(AsmOperands, CGIOp.Name);
+    Optional<size_t> RHSIdx = getAsmOperandIdx(AsmOperands, CGIOperands[TiedReg].Name);
+    // Skipping operands with constraint but no reference in the
+    // AsmString. No need to throw a warning, as it's normal to have
+    // a $dst operand in the outs dag that is constrained to a $src
+    // operand in the ins dag but that does not appear in the AsmString.
+    if (!LHSIdx || !RHSIdx)
+      continue;
+
+    // Add the constraint. Using min/max as we consider constraint
+    // pair {A,B} and {B,A} the same
+    size_t AddMnemonicIdx = HasMnemonicFirst;
+    AsmOperandTiedConstraints.emplace_back(
+        std::min(*LHSIdx, *RHSIdx) + AddMnemonicIdx,
+        std::max(*LHSIdx, *RHSIdx) + AddMnemonicIdx);
+  }

[sdesmalen]

Replaced a custom loop with call to CGIOp.getTiedRegister().

[sdesmalen]

utils/TableGen/AsmMatcherEmitter.cpp

969

Thanks Florian, I've implemented your suggestion.

[fhahn]

Thanks Sander, LGTM, with 3 small comments. Please hold off committing this a couple of days, to give other people some more time to voice concerns.

utils/TableGen/AsmMatcherEmitter.cpp

2934

Can you re-name this to checkAsmOperandTiedConstraints?

3639

3 spaces here?

3721

3 spaces here?

[sdesmalen]

• Renamed checkAsmOperandConstraints -> checkAsmTiedOperandConstraints.
• Removed unnecessary indentation.

include/llvm/MC/MCParser/MCTargetAsmParser.h

private:
   NearMissInfo() : Kind(NoNearMiss) {}
 };
 
 /// MCTargetAsmParser - Generic interface to target specific assembly parsers.
 class MCTargetAsmParser : public MCAsmParserExtension {
 public:
   enum MatchResultTy {
     Match_InvalidOperand,
+    Match_InvalidTiedOperand,
     Match_MissingFeature,
     Match_MnemonicFail,
     Match_Success,
     Match_NearMisses,
     FIRST_TARGET_MATCH_RESULT_TY
   };
 
 protected: // Can only create subclasses.

lib/Target/AArch64/AsmParser/AArch64AsmParser.cpp

 }
 
 static std::string AArch64MnemonicSpellCheck(StringRef S, uint64_t FBS,
                                              unsigned VariantID = 0);
 
 bool AArch64AsmParser::showMatchError(SMLoc Loc, unsigned ErrCode,
                                       OperandVector &Operands) {
   switch (ErrCode) {
+  case Match_InvalidTiedOperand:
+    return Error(Loc, "operand must match destination register");
   case Match_MissingFeature:
     return Error(Loc,
                  "instruction requires a CPU feature not currently enabled");
   case Match_InvalidOperand:
     return Error(Loc, "invalid operand for instruction");
   case Match_InvalidSuffix:
     return Error(Loc, "invalid type suffix for instruction");
   case Match_InvalidCondCode:
case Match_InvalidOperand: {
     // If the match failed on a suffix token operand, tweak the diagnostic
     // accordingly.
     if (((AArch64Operand &)*Operands[ErrorInfo]).isToken() &&
         ((AArch64Operand &)*Operands[ErrorInfo]).isTokenSuffix())
       MatchResult = Match_InvalidSuffix;
 
     return showMatchError(ErrorLoc, MatchResult, Operands);
   }
+  case Match_InvalidTiedOperand:
   case Match_InvalidMemoryIndexed1:
   case Match_InvalidMemoryIndexed2:
   case Match_InvalidMemoryIndexed4:
   case Match_InvalidMemoryIndexed8:
   case Match_InvalidMemoryIndexed16:
   case Match_InvalidCondCode:
   case Match_AddSubRegExtendSmall:
   case Match_AddSubRegExtendLarge:

utils/TableGen/AsmMatcherEmitter.cpp

struct MatchableInfo {
   StringRef Mnemonic;
 
   /// AsmOperands - The textual operands that this instruction matches,
   /// annotated with a class and where in the OperandList they were defined.
   /// This directly corresponds to the tokenized AsmString after the mnemonic is
   /// removed.
   SmallVector<AsmOperand, 8> AsmOperands;
 
+  /// AsmOperandEqualityConstraints - an array of pairs holding operand
+  /// constraints.
+  /// Each constraint is represented as a pair holding position of the token of
+  /// the operand asm name.
+  /// For example, an "AsmString" "add $Vd.s, $Vn.s, $Xn" would be
+  /// split in the following list of tokens:
+  ///
+  ///    ['add', '$Vd', '.s', '$Vn', '.s', '$Xn']
+  ///
+  /// A constraint "$Vd = $Vn" (e.g. for a destructive operation) is rendered
+  /// as the pair {1,3} into this set (note that tokens are numbered starting
+  /// from 0).
+  SmallVector<std::pair<unsigned,unsigned>, 1> AsmOperandTiedConstraints;
+
   /// Predicates - The required subtarget features to match this instruction.
   SmallVector<const SubtargetFeatureInfo *, 4> RequiredFeatures;
 
   /// ConversionFnKind - The enum value which is passed to the generated
   /// convertToMCInst to convert parsed operands into an MCInst for this
   /// function.
   std::string ConversionFnKind;
 
extractSingletonRegisterForAsmOperand(MatchableInfo::AsmOperand &Op,
   StringRef RegName = Tok.substr(RegisterPrefix.size());
   if (const CodeGenRegister *Reg = Info.Target.getRegisterByName(RegName))
     Op.SingletonReg = Reg->TheDef;
 
   // If there is no register prefix (i.e. "%" in "%eax"), then this may
   // be some random non-register token, just ignore it.
 }
 
+static Optional<size_t>
+getAsmOperandIdx(const SmallVectorImpl<MatchableInfo::AsmOperand> &AsmOperands,
+                 std::string Name) {
+  const auto SymbolicName = std::string("$") + Name;
+  const auto Pos =
+      std::find_if(AsmOperands.begin(), AsmOperands.end(),
+                   [&SymbolicName](const MatchableInfo::AsmOperand &A) {
+        return A.Token == SymbolicName;
+      });
+
+  if (Pos == AsmOperands.end())
+    return Optional<size_t>();
+
+  return Optional<size_t>(std::distance(AsmOperands.begin(), Pos));
+}
+
 void MatchableInfo::initialize(const AsmMatcherInfo &Info,
                                SmallPtrSetImpl<Record*> &SingletonRegisters,
                                AsmVariantInfo const &Variant,
                                bool HasMnemonicFirst) {
   AsmVariantID = Variant.AsmVariantNo;
   AsmString =
     CodeGenInstruction::FlattenAsmStringVariants(AsmString,
                                                  Variant.AsmVariantNo);
void MatchableInfo::initialize(const AsmMatcherInfo &Info,
   }
 
   const RecordVal *DepMask = TheDef->getValue("DeprecatedFeatureMask");
   if (!DepMask)
     DepMask = TheDef->getValue("ComplexDeprecationPredicate");
 
   HasDeprecation =
       DepMask ? !DepMask->getValue()->getAsUnquotedString().empty() : false;
+
+  // Do not generate tied operand info if the instruction does not
+  // use the default AsmMatchConverter.
+  if (TheDef->getValue("AsmMatchConverter") &&
+      !TheDef->getValueAsString("AsmMatchConverter").empty())
+    return;
+
+  // Generate tied operand contraints info.
+  const auto &CGIOperands = getResultInst()->Operands;
+  for (const auto &CGIOp : CGIOperands) {
+    int TiedReg = CGIOp.getTiedRegister();
+    if (TiedReg == -1)
+      continue;
+
+    Optional<size_t> LHSIdx = getAsmOperandIdx(AsmOperands, CGIOp.Name);
+    Optional<size_t> RHSIdx =
+        getAsmOperandIdx(AsmOperands, CGIOperands[TiedReg].Name);
+    // Skipping operands with constraint but no reference in the
+    // AsmString. No need to throw a warning, as it's normal to have
+    // a $dst operand in the outs dag that is constrained to a $src
+    // operand in the ins dag but that does not appear in the AsmString.
+    if (!LHSIdx || !RHSIdx)
+      continue;
+
+    // Add the constraint. Using min/max as we consider constraint
+    // pair {A,B} and {B,A} the same
+    size_t AddMnemonicIdx = HasMnemonicFirst;
+    AsmOperandTiedConstraints.emplace_back(
+        std::min(*LHSIdx, *RHSIdx) + AddMnemonicIdx,
+        std::max(*LHSIdx, *RHSIdx) + AddMnemonicIdx);
+  }
 }
 
 /// Append an AsmOperand for the given substring of AsmString.
 void MatchableInfo::addAsmOperand(StringRef Token, bool IsIsolatedToken) {
   AsmOperands.push_back(AsmOperand(IsIsolatedToken, Token));
 }
 
 /// tokenizeAsmString - Tokenize a simplified assembly string.
 void MatchableInfo::tokenizeAsmString(const AsmMatcherInfo &Info,
                                       AsmVariantInfo const &Variant) {
   StringRef String = AsmString;
   size_t Prev = 0;
static void emitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target,
   OS << "      return Result;\n";
   OS << "  }\n\n";
 
   OS << "  // Okay, we had no match.\n";
   OS << "  return MatchOperand_NoMatch;\n";
   OS << "}\n\n";
 }
 
+static void emitAsmTiedOperandConstraints(CodeGenTarget &Target,
+                                          AsmMatcherInfo &Info,
+                                          raw_ostream &OS) {
+  std::string Buf;
+  raw_string_ostream TmpOS(Buf);
+  TmpOS << "namespace {\n";
+  TmpOS << "  struct TiedAsmOpndPair {\n";
+  TmpOS << "    unsigned Opcode;\n";
+  TmpOS << "    unsigned Opnd1;\n";
+  TmpOS << "    unsigned Opnd2;\n";
+  TmpOS << "    TiedAsmOpndPair(unsigned Opcode, unsigned Opnd1, unsigned "
+           "Opnd2)\n";
+  TmpOS << "      : Opcode(Opcode), Opnd1(Opnd1), Opnd2(Opnd2) {}\n";
+  TmpOS << "  };\n";
+  TmpOS << "} // end anonymous namespace\n\n";
+  TmpOS << "static const TiedAsmOpndPair TiedAsmOperandsTable[] = {\n";
+  bool TableEmpty = true;
+  for (const auto &Inst : Target.getInstructionsByEnumValue()) {
+    auto It = std::find_if(Info.Matchables.begin(), Info.Matchables.end(),
+                           [&Inst](const std::unique_ptr<MatchableInfo> &MI) {
+      return (MI->TheDef->getID() == Inst->TheDef->getID());
+    });
+
+    if (It == Info.Matchables.end())
+      continue;
+
+    auto &Constraints = (**It).AsmOperandTiedConstraints;
+    if (Constraints.empty())
+      continue;
+
+    std::string Namespace = Inst->TheDef->getValueAsString("Namespace");
+
+    for (const auto &C : Constraints) {
+      TableEmpty = false;
+      TmpOS << "  {";
+      TmpOS << Namespace << "::"<< (**It).TheDef->getName() << ", ";
+      TmpOS << C.first << ", " << C.second;
+      TmpOS << "},\n";
+    }
+  }
+  TmpOS << "};\n\n";
+  if (!TableEmpty)
+    OS << TmpOS.str();
+
+  OS << "static bool ";
+  OS << "checkAsmOperandConstraints(const MCInst &Inst,\n";
+  OS << "                           const OperandVector &Operands,\n";
+  OS << "                           SMLoc &Loc) {\n";
+
+  if (TableEmpty) {
+    OS << "return true;\n}\n\n";
+    return;
+  }
+
+  OS << "  const TiedAsmOpndPair SearchValue(Inst.getOpcode(), 0, 0);\n";
+  OS << "  const auto Range = std::equal_range(\n";
+  OS << "      std::begin(TiedAsmOperandsTable), std::end(TiedAsmOperandsTable),\n";
+  OS << "      SearchValue, [](const TiedAsmOpndPair &a,\n";
+  OS << "                      const TiedAsmOpndPair &b) {\n";
+  OS << "        return (a.Opcode < b.Opcode);\n";
+  OS << "      });\n\n";
+  OS << "  for (auto Item = Range.first;  Item != Range.second; ++Item) {\n";
+  OS << "    MCParsedAsmOperand &Op1 = *Operands[Item->Opnd1];\n";
+  OS << "    MCParsedAsmOperand &Op2 = *Operands[Item->Opnd2];\n";
+  OS << "    if ((Op1.isReg() && Op2.isReg()) &&\n";
+  OS << "        (Op1.getReg() != Op2.getReg())) {\n";
+  OS << "      Loc = Op2.getStartLoc();\n";
+  OS << "      return false;\n";
+  OS << "    }\n";
+  OS << "  }\n";
+  OS << "  return true;\n";
+  OS << "}\n\n";
+}
+
 static void emitMnemonicSpellChecker(raw_ostream &OS, CodeGenTarget &Target,
                                      unsigned VariantCount) {
   OS << "static std::string " << Target.getName()
      << "MnemonicSpellCheck(StringRef S, uint64_t FBS, unsigned VariantID) {\n";
   if (!VariantCount)
     OS <<  "  return \"\";";
   else {
     OS << "  const unsigned MaxEditDist = 2;\n";
#endif
 
   emitMatchClassKindNames(Info.Classes, OS);
 
   // Emit the available features compute function.
   SubtargetFeatureInfo::emitComputeAssemblerAvailableFeatures(
       Info.Target.getName(), ClassName, "ComputeAvailableFeatures",
       Info.SubtargetFeatures, OS);
 
+  if (!ReportMultipleNearMisses)
+    emitAsmTiedOperandConstraints(Target, Info, OS);
+
   StringToOffsetTable StringTable;
 
   size_t MaxNumOperands = 0;
   unsigned MaxMnemonicIndex = 0;
   bool HasDeprecation = false;
   for (const auto &MI : Info.Matchables) {
     MaxNumOperands = std::max(MaxNumOperands, MI->AsmOperands.size());
     HasDeprecation |= MI->HasDeprecation;
if (ReportMultipleNearMisses) {
     OS << "                                                 \"reporting near-miss\\n\");\n";
     OS << "      }\n";
     OS << "      continue;\n";
     OS << "    }\n\n";
   }
 
   OS << "    if (matchingInlineAsm) {\n";
   OS << "      convertToMapAndConstraints(it->ConvertFn, Operands);\n";
+  if (!ReportMultipleNearMisses) {
+    OS << "      SMLoc Loc;\n";
+    OS << "      if (!checkAsmOperandConstraints(Inst, Operands, Loc)) {\n";
+    OS << "         ErrorInfo = " << (HasMnemonicFirst ? "1" : "SIndex") << ";\n";
+    OS << "         return Match_InvalidTiedOperand;\n";
+    OS << "      }\n";
+    OS << "\n";
+  }
   OS << "      return Match_Success;\n";
   OS << "    }\n\n";
   OS << "    // We have selected a definite instruction, convert the parsed\n"
      << "    // operands into the appropriate MCInst.\n";
   if (HasOptionalOperands) {
     OS << "    convertToMCInst(it->ConvertFn, Inst, it->Opcode, Operands,\n"
        << "                    OptionalOperandsMask);\n";
   } else {
if (HasDeprecation) {
     OS << "        getTargetOptions().MCNoDeprecatedWarn &&\n";
     OS << "        MII.get(Inst.getOpcode()).getDeprecatedInfo(Inst, getSTI(), Info)) {\n";
     OS << "      SMLoc Loc = ((" << Target.getName()
        << "Operand&)*Operands[0]).getStartLoc();\n";
     OS << "      getParser().Warning(Loc, Info, None);\n";
     OS << "    }\n";
   }
 
+  if (!ReportMultipleNearMisses) {
+    OS << "      SMLoc Loc;\n";
+    OS << "      if (!checkAsmOperandConstraints(Inst, Operands, Loc)) {\n";
+    OS << "         ErrorInfo = " << (HasMnemonicFirst ? "1" : "SIndex") << ";\n";
+    OS << "         return Match_InvalidTiedOperand;\n";
+    OS << "      }\n";
+    OS << "\n";
+  }
+
   OS << "    DEBUG_WITH_TYPE(\n";
   OS << "        \"asm-matcher\",\n";
   OS << "        dbgs() << \"Opcode result: complete match, selecting this opcode\\n\");\n";
   OS << "    return Match_Success;\n";
   OS << "  }\n\n";
 
   if (ReportMultipleNearMisses) {
     OS << "  // No instruction variants matched exactly.\n";