[TableGen][AsmMatcherEmitter] Fix tied-constraint checking for InstAliases

[sdesmalen]

Summary

This is a bit of a reimplementation the work done in
https://reviews.llvm.org/D41446, since that patch only really works for
tied operands of instructions, not aliases.

Instead of checking the constraints based on the matched instruction's opcode,
this patch uses the match-info's convert function to check the operand
constraints for that specific instruction/alias.
This is based on the matched operands for the instruction, not the
resulting opcode of the MCInst.

This patch adds the following enum/table to the *GenAsmMatcher.inc file:

enum {
  Tie0_1_1,
  Tie0_1_2,
  Tie0_1_5,
  ...
};

const char TiedAsmOperandTable[][3] = {
  /* Tie0_1_1 */ { 0, 1, 1 },
  /* Tie0_1_2 */ { 0, 1, 2 },
  /* Tie0_1_5 */ { 0, 1, 5 },
  ...
};

And it is referenced directly in the ConversionTable, like this:
static const uint8_t ConversionTable[CVT_NUM_SIGNATURES][13] = {

...
{ CVT_95_addRegOperands, 1,
  CVT_95_addRegOperands, 2,
  CVT_Tied, Tie0_1_5,
  CVT_95_addRegOperands, 6, CVT_Done },
...

The Tie0_1_5 (and corresponding table) encodes that:

• Result operand 0 is the operand to copy (which is e.g. done when building up the operands to the MCInst in convertToMCInst())
• Asm operands 1 and 5 should be the same operands (which is checked in checkAsmTiedOperandConstraints()).

[olista01]

I was looking at your original version of this the other day to work out if it could be used to do 3-operand aliases of 2-operand Thumb1 instructions, and this (adding support for aliases) looks like it's what we would need for that.

Why do you need to modify the conversion to MCInst? There is still a parsed operand for every MCInst operand, so can the existing conversion function not handle this already?

Thinking about how to integrate this with the new diagnostics used in the ARM assembler, I think it might be better to check tied operands at the same time as we check the operand classes. In fact, the tied-operand check might be able to replace the operand class check.

utils/TableGen/AsmMatcherEmitter.cpp

3669 ↗

(On Diff #130591)

If we are in a ReportMultipleNearMisses backend then this check will be skipped, so should we assert here?

[sdesmalen]

In D42293#981862, @olista01 wrote:

I was looking at your original version of this the other day to work out if it could be used to do 3-operand aliases of 2-operand Thumb1 instructions, and this (adding support for aliases) looks like it's what we would need for that.

That's great to hear!

Why do you need to modify the conversion to MCInst?

Well, this patch doesn't change the actual conversion to MCInst, it just encodes more information into the conversion-function by using an indirection through the 'TiedAsmOperandTable'. It will still create the MCInst in the same way as it did before.

There is still a parsed operand for every MCInst operand, so can the existing conversion function not handle this already?

Yes, however the existing conversion function does not encode which parsed operands correspond to each other and rather just tells 'Copy operand X' from the list of result operands (which is not the same as the list of parsed operands). This patch adds that extra bit of information to the conversion function, so now it can just say that "parsed operand Y" and "parsed operand Z" should match (that both result in "result operand X"). I hope my explanation/terminology makes some sense :)

Thinking about how to integrate this with the new diagnostics used in the ARM assembler, I think it might be better to check tied operands at the same time as we check the operand classes. In fact, the tied-operand check might be able to replace the operand class check.

That might be possible, but I worry that it might lead to unmatched instructions and/or vague error messages if the register-operands don't match up. At the moment it just tries to match the whole instruction based on the operand classes, and then checks that the operands should be the same, already knowing they are of the right operand class, so we already know the instruction should otherwise match. What would be the benefit of doing it during matching of the operand classes?

[olista01]

Well, this patch doesn't change the actual conversion to MCInst, it just encodes more information into the conversion-function by using an indirection through the 'TiedAsmOperandTable'. It will still create the MCInst in the same way as it did before.

Ah, yep, I misread the patch. It confused me a bit that CVT_Tied is being used for these two different cases (if i've understood it correctly this time):

• One parsed operand which generates two identical MCInst operands
• Two parsed operands which must bet the same, and generate two identical MCInst operand

That might be possible, but I worry that it might lead to unmatched instructions and/or vague error messages if the register-operands don't match up. At the moment it just tries to match the whole instruction based on the operand classes, and then checks that the operands should be the same, already knowing they are of the right operand class, so we already know the instruction should otherwise match. What would be the benefit of doing it during matching of the operand classes?

I think the way it is being done now will result in the situation where a diagnostic says "operand must be a register in some range", the user fixes that, then the diagnostic changes to "operand must be the same as this other operand". That's something I've been trying to avoid, always emitting diagnostics that will result in a valid instruction if followed. My thought here was that it would be better to do all of the operand checks at once, so that we can favour the more precise diagnostics (the tied-operand ones) over the looser ones (operand class).

However, now that I've thought about it a bit more, I'm not sure that would work any better. In particular, in the case where the left-most of a pair of tied operands isn't in the correct register class, we can't emit the tied-operand diagnostic because we haven't matched the right-most operand yet. I also can't think of a good way to word diagnostics that say "_this_ operand is valid, but _that one_ needs to match it". Maybe it would be better to relax that rule, giving slightly less precise, but easier to understand diagnostics.

[dsanders]

The approach you're describing sounds good to me. I've got one question about the example from the other review:

def : InstAlias<"mov $dst, $src, $src, $src", (ORRWrs GPR32:$dst, WZR, GPR32:$src, 0), 2>;

It looks like this patch will handle the tie between the first two $src's but ignore the third. If that's a limitation of the implementation then I think that buildAliasResultOperands() should call findAsmOperandNamed() once more and report an error if another instance of $src is found.

[sdesmalen]

@olista01 Thanks, I see your point about wanting to avoid taking the user through multiple steps to get the operand right, I think the work you did on reporting 'multiple near misses' is a step in that direction by giving all the information to the user at once. Having the tied-constraint diagnostic being mentioned in that list would be useful.

When giving only a single diagnostic however, the difference with matching different operand classes and matching the tied operand's case is that there will be no other possible match that is more likely to match than the current one, so in a way the tied-operand diagnostic takes precedence over all other diagnostics in that case.

At the moment the checking of tied constraints is still disabled when 'ReportMultipleNearMisses' is used, maybe it is worth integrating the constraint checking with that work in a separate patch?

[sdesmalen]

In D42293#982062, @dsanders wrote:

The approach you're describing sounds good to me. I've got one question about the example from the other review:

def : InstAlias<"mov $dst, $src, $src, $src", (ORRWrs GPR32:$dst, WZR, GPR32:$src, 0), 2>;

It looks like this patch will handle the tie between the first two $src's but ignore the third. If that's a limitation of the implementation then I think that buildAliasResultOperands() should call findAsmOperandNamed() once more and report an error if another instance of $src is found.

Only multiple $src operands that correspond to a tied operand in the MCInst will be handled, subsequent mentions of $src in the asm-string are error'd by TableGen. This is done in AsmMatcherEmitter.cpp line 1891 where it goes through the map of all named operands and their 'last' mention in the asm string. If it is mentioned more than once without corresponding to a variable in the MCInst (at line 1891, all result operands are handled so any further mention of a variable in the asm string cannot correspond to a result operand) , an error is given that the operand can never be matched.

[sdesmalen]

Retain old behaviour of disallowing repeated operands in InstAliases when tied-operand checking is not enabled (which is currently the case with ReportMultipleNearMisses)

[sdesmalen]

utils/TableGen/AsmMatcherEmitter.cpp

3669 ↗

(On Diff #130591)

Hi @olista01, my apologies, I didn't notice your comment earlier. I have addressed your concern in my latest patch.

[olista01]

LGTM.

llvm/trunk/utils/TableGen/AsmMatcherEmitter.cpp

struct AsmOperand {
     StringRef Token;
 
     /// The unique class instance this operand should match.
     ClassInfo *Class;
 
     /// The operand name this is, if anything.
     StringRef SrcOpName;
 
+    /// The operand name this is, before renaming for tied operands.
+    StringRef OrigSrcOpName;
+
     /// The suboperand index within SrcOpName, or -1 for the entire operand.
     int SubOpIdx;
 
     /// Whether the token is "isolated", i.e., it is preceded and followed
     /// by separators.
     bool IsIsolatedToken;
 
     /// Register record if this token is singleton register.
enum {
       /// ImmOperand - This represents an immediate value that is dumped into
       /// the operand.
       ImmOperand,
 
       /// RegOperand - This represents a fixed register that is dumped in.
       RegOperand
     } Kind;
 
+    /// Tuple containing the index of the (earlier) result operand that should
+    /// be copied from, as well as the indices of the corresponding (parsed)
+    /// operands in the asm string.
+    struct TiedOperandsTuple {
+      unsigned ResOpnd;
+      unsigned SrcOpnd1Idx;
+      unsigned SrcOpnd2Idx;
+    };
+
     union {
       /// This is the operand # in the AsmOperands list that this should be
       /// copied from.
       unsigned AsmOperandNum;
 
-      /// TiedOperandNum - This is the (earlier) result operand that should be
-      /// copied from.
-      unsigned TiedOperandNum;
+      /// Description of tied operands.
+      TiedOperandsTuple TiedOperands;
 
       /// ImmVal - This is the immediate value added to the instruction.
       int64_t ImmVal;
 
       /// Register - This is the register record.
       Record *Register;
     };
 
     /// MINumOperands - The number of MCInst operands populated by this
     /// operand.
     unsigned MINumOperands;
 
     static ResOperand getRenderedOp(unsigned AsmOpNum, unsigned NumOperands) {
       ResOperand X;
       X.Kind = RenderAsmOperand;
       X.AsmOperandNum = AsmOpNum;
       X.MINumOperands = NumOperands;
       return X;
     }
 
-    static ResOperand getTiedOp(unsigned TiedOperandNum) {
+    static ResOperand getTiedOp(unsigned TiedOperandNum, unsigned SrcOperand1,
+                                unsigned SrcOperand2) {
       ResOperand X;
       X.Kind = TiedOperand;
-      X.TiedOperandNum = TiedOperandNum;
+      X.TiedOperands = { TiedOperandNum, SrcOperand1, SrcOperand2 };
       X.MINumOperands = 1;
       return X;
     }
 
     static ResOperand getImmOp(int64_t Val) {
       ResOperand X;
       X.Kind = ImmOperand;
       X.ImmVal = Val;
struct MatchableInfo {
 
   void initialize(const AsmMatcherInfo &Info,
                   SmallPtrSetImpl<Record*> &SingletonRegisters,
                   AsmVariantInfo const &Variant,
                   bool HasMnemonicFirst);
 
   /// validate - Return true if this matchable is a valid thing to match against
   /// and perform a bunch of validity checking.
-  bool validate(StringRef CommentDelimiter, bool Hack) const;
+  bool validate(StringRef CommentDelimiter, bool IsAlias) const;
 
   /// findAsmOperand - Find the AsmOperand with the specified name and
   /// suboperand index.
   int findAsmOperand(StringRef N, int SubOpIdx) const {
     auto I = find_if(AsmOperands, [&](const AsmOperand &Op) {
       return Op.SrcOpName == N && Op.SubOpIdx == SubOpIdx;
     });
     return (I != AsmOperands.end()) ? I - AsmOperands.begin() : -1;
   }
 
   /// findAsmOperandNamed - Find the first AsmOperand with the specified name.
   /// This does not check the suboperand index.
-  int findAsmOperandNamed(StringRef N) const {
-    auto I = find_if(AsmOperands,
+  int findAsmOperandNamed(StringRef N, int LastIdx = -1) const {
+    auto I = std::find_if(AsmOperands.begin() + LastIdx + 1, AsmOperands.end(),
                      [&](const AsmOperand &Op) { return Op.SrcOpName == N; });
     return (I != AsmOperands.end()) ? I - AsmOperands.begin() : -1;
   }
 
+  int findAsmOperandOriginallyNamed(StringRef N) const {
+    auto I =
+        find_if(AsmOperands,
+                [&](const AsmOperand &Op) { return Op.OrigSrcOpName == N; });
+    return (I != AsmOperands.end()) ? I - AsmOperands.begin() : -1;
+  }
+
   void buildInstructionResultOperands();
-  void buildAliasResultOperands();
+  void buildAliasResultOperands(bool AliasConstraintsAreChecked);
 
   /// operator< - Compare two matchables.
   bool operator<(const MatchableInfo &RHS) const {
     // The primary comparator is the instruction mnemonic.
     if (int Cmp = Mnemonic.compare(RHS.Mnemonic))
       return Cmp == -1;
 
     if (AsmOperands.size() != RHS.AsmOperands.size())
for (ResOperand &Op : ResOperands) {
     switch(Op.Kind) {
     default:
       // Nothing to do for operands that don't reference AsmOperands.
       break;
     case ResOperand::RenderAsmOperand:
       if (Op.AsmOperandNum > (unsigned)SrcAsmOperand)
         --Op.AsmOperandNum;
       break;
-    case ResOperand::TiedOperand:
-      if (Op.TiedOperandNum > (unsigned)SrcAsmOperand)
-        --Op.TiedOperandNum;
-      break;
     }
   }
 }
 
 /// extractSingletonRegisterForAsmOperand - Extract singleton register,
 /// if present, from specified token.
 static void
 extractSingletonRegisterForAsmOperand(MatchableInfo::AsmOperand &Op,
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.
default:
       InTok = true;
       break;
     }
   }
   if (InTok && Prev != String.size())
     addAsmOperand(String.substr(Prev), IsIsolatedToken);
 }
 
-bool MatchableInfo::validate(StringRef CommentDelimiter, bool Hack) const {
+bool MatchableInfo::validate(StringRef CommentDelimiter, bool IsAlias) const {
   // Reject matchables with no .s string.
   if (AsmString.empty())
     PrintFatalError(TheDef->getLoc(), "instruction with empty asm string");
 
   // Reject any matchables with a newline in them, they should be marked
   // isCodeGenOnly if they are pseudo instructions.
   if (AsmString.find('\n') != std::string::npos)
     PrintFatalError(TheDef->getLoc(),
bool MatchableInfo::validate(StringRef CommentDelimiter, bool IsAlias) const {
   // this implies a constraint we would not honor.
   std::set<std::string> OperandNames;
   for (const AsmOperand &Op : AsmOperands) {
     StringRef Tok = Op.Token;
     if (Tok[0] == '$' && Tok.find(':') != StringRef::npos)
       PrintFatalError(TheDef->getLoc(),
                       "matchable with operand modifier '" + Tok +
                       "' not supported by asm matcher.  Mark isCodeGenOnly!");
-
     // Verify that any operand is only mentioned once.
     // We reject aliases and ignore instructions for now.
-    if (Tok[0] == '$' && !OperandNames.insert(Tok).second) {
-      if (!Hack)
-        PrintFatalError(TheDef->getLoc(),
-                        "ERROR: matchable with tied operand '" + Tok +
-                        "' can never be matched!");
-      // FIXME: Should reject these.  The ARM backend hits this with $lane in a
-      // bunch of instructions.  It is unclear what the right answer is.
+    if (!IsAlias && Tok[0] == '$' && !OperandNames.insert(Tok).second) {
       DEBUG({
         errs() << "warning: '" << TheDef->getName() << "': "
                << "ignoring instruction with tied operand '"
                << Tok << "'\n";
       });
       return false;
     }
   }
SubtargetFeatures.insert(SubtargetFeaturePairs.begin(),
                            SubtargetFeaturePairs.end());
 #ifndef NDEBUG
   for (const auto &Pair : SubtargetFeatures)
     DEBUG(Pair.second.dump());
 #endif // NDEBUG
   assert(SubtargetFeatures.size() <= 64 && "Too many subtarget features!");
 
   bool HasMnemonicFirst = AsmParser->getValueAsBit("HasMnemonicFirst");
+  bool ReportMultipleNearMisses =
+      AsmParser->getValueAsBit("ReportMultipleNearMisses");
 
   // Parse the instructions; we need to do this first so that we can gather the
   // singleton register classes.
   SmallPtrSet<Record*, 16> SingletonRegisters;
   unsigned VariantCount = Target.getAsmParserVariantCount();
   for (unsigned VC = 0; VC != VariantCount; ++VC) {
     Record *AsmVariant = Target.getAsmParserVariant(VC);
     StringRef CommentDelimiter =
for (const CodeGenInstruction *CGI : Target.getInstructionsByEnumValue()) {
         continue;
 
       auto II = llvm::make_unique<MatchableInfo>(*CGI);
 
       II->initialize(*this, SingletonRegisters, Variant, HasMnemonicFirst);
 
       // Ignore instructions which shouldn't be matched and diagnose invalid
       // instruction definitions with an error.
-      if (!II->validate(CommentDelimiter, true))
+      if (!II->validate(CommentDelimiter, false))
         continue;
 
       Matchables.push_back(std::move(II));
     }
 
     // Parse all of the InstAlias definitions and stick them in the list of
     // matchables.
     std::vector<Record*> AllInstAliases =
for (unsigned i = 0, e = AllInstAliases.size(); i != e; ++i) {
       if (!V.empty() && V != Variant.Name)
         continue;
 
       auto II = llvm::make_unique<MatchableInfo>(std::move(Alias));
 
       II->initialize(*this, SingletonRegisters, Variant, HasMnemonicFirst);
 
       // Validate the alias definitions.
-      II->validate(CommentDelimiter, false);
+      II->validate(CommentDelimiter, true);
 
       Matchables.push_back(std::move(II));
     }
   }
 
   // Build info for the register classes.
   buildRegisterClasses(SingletonRegisters);
 
if (II->DefRec.is<const CodeGenInstruction*>()) {
 
         // Adjust it to be a two-operand alias.
         AliasII->formTwoOperandAlias(Constraint);
 
         // Add the alias to the matchables list.
         NewMatchables.push_back(std::move(AliasII));
       }
     } else
-      II->buildAliasResultOperands();
+      // FIXME: The tied operands checking is not yet integrated with the
+      // framework for reporting multiple near misses. To prevent invalid
+      // formats from being matched with an alias if a tied-operands check
+      // would otherwise have disallowed it, we just disallow such constructs
+      // in TableGen completely.
+      II->buildAliasResultOperands(!ReportMultipleNearMisses);
   }
   if (!NewMatchables.empty())
     Matchables.insert(Matchables.end(),
                       std::make_move_iterator(NewMatchables.begin()),
                       std::make_move_iterator(NewMatchables.end()));
 
   // Process token alias definitions and set up the associated superclass
   // information.
if (MatchClass && MatchClass->getValueAsString("Name") == "Imm") {
       // Replace Op with first suboperand.
       Op = &II->AsmOperands[AsmOpIdx]; // update the pointer in case it moved
       Op->SubOpIdx = 0;
     }
   }
 
   // Set up the operand class.
   Op->Class = getOperandClass(Operands[Idx], Op->SubOpIdx);
+  Op->OrigSrcOpName = OperandName;
 
   // If the named operand is tied, canonicalize it to the untied operand.
   // For example, something like:
   //   (outs GPR:$dst), (ins GPR:$src)
   // with an asmstring of
   //   "inc $src"
   // we want to canonicalize to:
   //   "inc $dst"
if (CGA.ResultOperands[i].isRecord() &&
       // validates that all operands with the same name have the same record.
       Op.SubOpIdx = CGA.ResultInstOperandIndex[i].second;
       // Use the match class from the Alias definition, not the
       // destination instruction, as we may have an immediate that's
       // being munged by the match class.
       Op.Class = getOperandClass(CGA.ResultOperands[i].getRecord(),
                                  Op.SubOpIdx);
       Op.SrcOpName = OperandName;
+      Op.OrigSrcOpName = OperandName;
       return;
     }
 
   PrintFatalError(II->TheDef->getLoc(),
                   "error: unable to find operand: '" + OperandName + "'");
 }
 
 void MatchableInfo::buildInstructionResultOperands() {
   const CodeGenInstruction *ResultInst = getResultInst();
 
   // Loop over all operands of the result instruction, determining how to
   // populate them.
   for (const CGIOperandList::OperandInfo &OpInfo : ResultInst->Operands) {
     // If this is a tied operand, just copy from the previously handled operand.
     int TiedOp = -1;
     if (OpInfo.MINumOperands == 1)
       TiedOp = OpInfo.getTiedRegister();
     if (TiedOp != -1) {
-      ResOperands.push_back(ResOperand::getTiedOp(TiedOp));
+      int TiedSrcOperand = findAsmOperandOriginallyNamed(OpInfo.Name);
+      if (TiedSrcOperand != -1 &&
+          ResOperands[TiedOp].Kind == ResOperand::RenderAsmOperand)
+        ResOperands.push_back(ResOperand::getTiedOp(
+            TiedOp, ResOperands[TiedOp].AsmOperandNum, TiedSrcOperand));
+      else
+        ResOperands.push_back(ResOperand::getTiedOp(TiedOp, 0, 0));
       continue;
     }
 
-    // Find out what operand from the asmparser this MCInst operand comes from.
     int SrcOperand = findAsmOperandNamed(OpInfo.Name);
     if (OpInfo.Name.empty() || SrcOperand == -1) {
       // This may happen for operands that are tied to a suboperand of a
       // complex operand.  Simply use a dummy value here; nobody should
       // use this operand slot.
       // FIXME: The long term goal is for the MCOperand list to not contain
       // tied operands at all.
       ResOperands.push_back(ResOperand::getImmOp(0));
for (unsigned AI = 0; AI < NumOperands; ++AI) {
       assert(AsmOperands[SrcOperand+AI].SubOpIdx == (int)AI &&
              AsmOperands[SrcOperand+AI].SrcOpName == OpInfo.Name &&
              "unexpected AsmOperands for suboperands");
       ResOperands.push_back(ResOperand::getRenderedOp(SrcOperand + AI, 1));
     }
   }
 }
 
-void MatchableInfo::buildAliasResultOperands() {
+void MatchableInfo::buildAliasResultOperands(bool AliasConstraintsAreChecked) {
   const CodeGenInstAlias &CGA = *DefRec.get<const CodeGenInstAlias*>();
   const CodeGenInstruction *ResultInst = getResultInst();
 
+  // Map of:  $reg -> #lastref
+  //   where $reg is the name of the operand in the asm string
+  //   where #lastref is the last processed index where $reg was referenced in
+  //   the asm string.
+  SmallDenseMap<StringRef, int> OperandRefs;
+
   // Loop over all operands of the result instruction, determining how to
   // populate them.
   unsigned AliasOpNo = 0;
   unsigned LastOpNo = CGA.ResultInstOperandIndex.size();
   for (unsigned i = 0, e = ResultInst->Operands.size(); i != e; ++i) {
     const CGIOperandList::OperandInfo *OpInfo = &ResultInst->Operands[i];
 
     // If this is a tied operand, just copy from the previously handled operand.
     int TiedOp = -1;
     if (OpInfo->MINumOperands == 1)
       TiedOp = OpInfo->getTiedRegister();
     if (TiedOp != -1) {
-      ResOperands.push_back(ResOperand::getTiedOp(TiedOp));
+      unsigned SrcOp1 = 0;
+      unsigned SrcOp2 = 0;
+
+      // If an operand has been specified twice in the asm string,
+      // add the two source operand's indices to the TiedOp so that
+      // at runtime the 'tied' constraint is checked.
+      if (ResOperands[TiedOp].Kind == ResOperand::RenderAsmOperand) {
+        SrcOp1 = ResOperands[TiedOp].AsmOperandNum;
+
+        // Find the next operand (similarly named operand) in the string.
+        StringRef Name = AsmOperands[SrcOp1].SrcOpName;
+        auto Insert = OperandRefs.try_emplace(Name, SrcOp1);
+        SrcOp2 = findAsmOperandNamed(Name, Insert.first->second);
+
+        // Not updating the record in OperandRefs will cause TableGen
+        // to fail with an error at the end of this function.
+        if (AliasConstraintsAreChecked)
+          Insert.first->second = SrcOp2;
+
+        // In case it only has one reference in the asm string,
+        // it doesn't need to be checked for tied constraints.
+        SrcOp2 = (SrcOp2 == (unsigned)-1) ? SrcOp1 : SrcOp2;
+      }
+
+      ResOperands.push_back(ResOperand::getTiedOp(TiedOp, SrcOp1, SrcOp2));
       continue;
     }
 
     // Handle all the suboperands for this operand.
     const std::string &OpName = OpInfo->Name;
     for ( ; AliasOpNo <  LastOpNo &&
             CGA.ResultInstOperandIndex[AliasOpNo].first == i; ++AliasOpNo) {
       int SubIdx = CGA.ResultInstOperandIndex[AliasOpNo].second;
 
       // Find out what operand from the asmparser that this MCInst operand
       // comes from.
       switch (CGA.ResultOperands[AliasOpNo].Kind) {
       case CodeGenInstAlias::ResultOperand::K_Record: {
         StringRef Name = CGA.ResultOperands[AliasOpNo].getName();
         int SrcOperand = findAsmOperand(Name, SubIdx);
         if (SrcOperand == -1)
           PrintFatalError(TheDef->getLoc(), "Instruction '" +
                         TheDef->getName() + "' has operand '" + OpName +
                         "' that doesn't appear in asm string!");
+
+        // Add it to the operand references. If it is added a second time, the
+        // record won't be updated and it will fail later on.
+        OperandRefs.try_emplace(Name, SrcOperand);
+
         unsigned NumOperands = (SubIdx == -1 ? OpInfo->MINumOperands : 1);
         ResOperands.push_back(ResOperand::getRenderedOp(SrcOperand,
                                                         NumOperands));
         break;
       }
       case CodeGenInstAlias::ResultOperand::K_Imm: {
         int64_t ImmVal = CGA.ResultOperands[AliasOpNo].getImm();
         ResOperands.push_back(ResOperand::getImmOp(ImmVal));
         break;
       }
       case CodeGenInstAlias::ResultOperand::K_Reg: {
         Record *Reg = CGA.ResultOperands[AliasOpNo].getRegister();
         ResOperands.push_back(ResOperand::getRegOp(Reg));
         break;
       }
       }
     }
   }
+
+  // Check that operands are not repeated more times than is supported.
+  for (auto &T : OperandRefs) {
+    if (T.second != -1 && findAsmOperandNamed(T.first, T.second) != -1)
+      PrintFatalError(TheDef->getLoc(),
+                      "Operand '" + T.first + "' can never be matched");
+  }
 }
 
 static unsigned
 getConverterOperandID(const std::string &Name,
                       SmallSetVector<CachedHashString, 16> &Table,
                       bool &IsNew) {
   IsNew = Table.insert(CachedHashString(Name));
 
if (HasOptionalOperands) {
     CvtOS << "    OpIdx = *(p + 1);\n";
   }
   CvtOS << "    switch (*p) {\n";
   CvtOS << "    default: llvm_unreachable(\"invalid conversion entry!\");\n";
   CvtOS << "    case CVT_Reg:\n";
   CvtOS << "      static_cast<" << TargetOperandClass
         << "&>(*Operands[OpIdx]).addRegOperands(Inst, 1);\n";
   CvtOS << "      break;\n";
-  CvtOS << "    case CVT_Tied:\n";
-  CvtOS << "      Inst.addOperand(Inst.getOperand(OpIdx));\n";
+  CvtOS << "    case CVT_Tied: {\n";
+  CvtOS << "      assert(OpIdx < (std::end(TiedAsmOperandTable) -\n";
+  CvtOS << "                      std::begin(TiedAsmOperandTable)) &&\n";
+  CvtOS << "             \"Tied operand not found\");\n";
+  CvtOS << "      unsigned TiedResOpnd = TiedAsmOperandTable[OpIdx][0];\n";
+  CvtOS << "      Inst.addOperand(Inst.getOperand(TiedResOpnd));\n";
   CvtOS << "      break;\n";
+  CvtOS << "    }\n";
 
   std::string OperandFnBody;
   raw_string_ostream OpOS(OperandFnBody);
   // Start the operand number lookup function.
   OpOS << "void " << Target.getName() << ClassName << "::\n"
        << "convertToMapAndConstraints(unsigned Kind,\n";
   OpOS.indent(27);
   OpOS << "const OperandVector &Operands) {\n"
static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName,
 
   // Pre-populate the operand conversion kinds with the standard always
   // available entries.
   OperandConversionKinds.insert(CachedHashString("CVT_Done"));
   OperandConversionKinds.insert(CachedHashString("CVT_Reg"));
   OperandConversionKinds.insert(CachedHashString("CVT_Tied"));
   enum { CVT_Done, CVT_Reg, CVT_Tied };
 
+  // Map of e.g. <0, 2, 3> -> "Tie_0_2_3" enum label.
+  std::map<std::tuple<unsigned, unsigned, unsigned>, std::string>
+  TiedOperandsEnumMap;
+
   for (auto &II : Infos) {
     // Check if we have a custom match function.
     StringRef AsmMatchConverter =
         II->getResultInst()->TheDef->getValueAsString("AsmMatchConverter");
     if (!AsmMatchConverter.empty() && II->UseInstAsmMatchConverter) {
       std::string Signature = ("ConvertCustom_" + AsmMatchConverter).str();
       II->ConversionFnKind = Signature;
 
for (unsigned i = 0, e = II->ResOperands.size(); i != e; ++i) {
         OpOS << "      NumMCOperands += " << OpInfo.MINumOperands << ";\n"
              << "      break;\n";
         break;
       }
       case MatchableInfo::ResOperand::TiedOperand: {
         // If this operand is tied to a previous one, just copy the MCInst
         // operand from the earlier one.We can only tie single MCOperand values.
         assert(OpInfo.MINumOperands == 1 && "Not a singular MCOperand");
-        unsigned TiedOp = OpInfo.TiedOperandNum;
+        unsigned TiedOp = OpInfo.TiedOperands.ResOpnd;
+        unsigned SrcOp1 = OpInfo.TiedOperands.SrcOpnd1Idx + HasMnemonicFirst;
+        unsigned SrcOp2 = OpInfo.TiedOperands.SrcOpnd2Idx + HasMnemonicFirst;
         assert(i > TiedOp && "Tied operand precedes its target!");
-        Signature += "__Tie" + utostr(TiedOp);
+        auto TiedTupleName = std::string("Tie") + utostr(TiedOp) + '_' +
+                             utostr(SrcOp1) + '_' + utostr(SrcOp2);
+        Signature += "__" + TiedTupleName;
         ConversionRow.push_back(CVT_Tied);
         ConversionRow.push_back(TiedOp);
+        ConversionRow.push_back(SrcOp1);
+        ConversionRow.push_back(SrcOp2);
+
+        // Also create an 'enum' for this combination of tied operands.
+        auto Key = std::make_tuple(TiedOp, SrcOp1, SrcOp2);
+        TiedOperandsEnumMap.emplace(Key, TiedTupleName);
         break;
       }
       case MatchableInfo::ResOperand::ImmOperand: {
         int64_t Val = OpInfo.ImmVal;
         std::string Ty = "imm_" + itostr(Val);
         Ty = getEnumNameForToken(Ty);
         Signature += "__" + Ty;
 
static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName,
   }
 
   // Finish up the converter driver function.
   CvtOS << "    }\n  }\n}\n\n";
 
   // Finish up the operand number lookup function.
   OpOS << "    }\n  }\n}\n\n";
 
+  // Output a static table for tied operands.
+  if (TiedOperandsEnumMap.size()) {
+    // The number of tied operand combinations will be small in practice,
+    // but just add the assert to be sure.
+    assert(TiedOperandsEnumMap.size() <= 255 &&
+           "Too many tied-operand combinations to reference with "
+           "an 8bit offset from the conversion table");
+
+    OS << "enum {\n";
+    for (auto &KV : TiedOperandsEnumMap) {
+      OS << "  " << KV.second << ",\n";
+    }
+    OS << "};\n\n";
+
+    OS << "const char TiedAsmOperandTable[][3] = {\n";
+    for (auto &KV : TiedOperandsEnumMap) {
+      OS << "  /* " << KV.second << " */ { " << std::get<0>(KV.first) << ", "
+         << std::get<1>(KV.first) << ", " << std::get<2>(KV.first) << " },\n";
+    }
+    OS << "};\n\n";
+  } else
+    OS << "const char TiedAsmOperandTable[][3] = { /* empty  */ {0, 0, 0} "
+          "};\n\n";
+
   OS << "namespace {\n";
 
   // Output the operand conversion kind enum.
   OS << "enum OperatorConversionKind {\n";
   for (const auto &Converter : OperandConversionKinds)
     OS << "  " << Converter << ",\n";
   OS << "  CVT_NUM_CONVERTERS\n";
   OS << "};\n\n";
static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName,
   // Output the conversion table.
   OS << "static const uint8_t ConversionTable[CVT_NUM_SIGNATURES]["
      << MaxRowLength << "] = {\n";
 
   for (unsigned Row = 0, ERow = ConversionTable.size(); Row != ERow; ++Row) {
     assert(ConversionTable[Row].size() % 2 == 0 && "bad conversion row!");
     OS << "  // " << InstructionConversionKinds[Row] << "\n";
     OS << "  { ";
-    for (unsigned i = 0, e = ConversionTable[Row].size(); i != e; i += 2)
-      OS << OperandConversionKinds[ConversionTable[Row][i]] << ", "
-         << (unsigned)(ConversionTable[Row][i + 1]) << ", ";
+    for (unsigned i = 0, e = ConversionTable[Row].size(); i != e; i += 2) {
+      OS << OperandConversionKinds[ConversionTable[Row][i]] << ", ";
+      if (OperandConversionKinds[ConversionTable[Row][i]] !=
+          CachedHashString("CVT_Tied")) {
+        OS << (unsigned)(ConversionTable[Row][i + 1]) << ", ";
+        continue;
+      }
+
+      // For a tied operand, emit a reference to the TiedAsmOperandTable
+      // that contains the operand to copy, and the parsed operands to
+      // check for their tied constraints.
+      auto Key = std::make_tuple((unsigned)ConversionTable[Row][i + 1],
+                                 (unsigned)ConversionTable[Row][i + 2],
+                                 (unsigned)ConversionTable[Row][i + 3]);
+      auto TiedOpndEnum = TiedOperandsEnumMap.find(Key);
+      assert(TiedOpndEnum != TiedOperandsEnumMap.end() &&
+             "No record for tied operand pair");
+      OS << TiedOpndEnum->second << ", ";
+      i += 2;
+    }
     OS << "CVT_Done },\n";
   }
 
   OS << "};\n\n";
 
   // Spit out the conversion driver function.
   OS << CvtOS.str();
 
static void emitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target,
   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 << "checkAsmTiedOperandConstraints(const MCInst &Inst,\n";
+  OS << "checkAsmTiedOperandConstraints(unsigned Kind,\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 << "                               uint64_t &ErrorInfo) {\n";
+  OS << "  assert(Kind < CVT_NUM_SIGNATURES && \"Invalid signature!\");\n";
+  OS << "  const uint8_t *Converter = ConversionTable[Kind];\n";
+  OS << "  for (const uint8_t *p = Converter; *p; p+= 2) {\n";
+  OS << "    switch (*p) {\n";
+  OS << "    case CVT_Tied: {\n";
+  OS << "      unsigned OpIdx = *(p+1);\n";
+  OS << "      assert(OpIdx < (std::end(TiedAsmOperandTable) -\n";
+  OS << "                     std::begin(TiedAsmOperandTable)) &&\n";
+  OS << "             \"Tied operand not found\");\n";
+  OS << "      unsigned OpndNum1 = TiedAsmOperandTable[OpIdx][1];\n";
+  OS << "      unsigned OpndNum2 = TiedAsmOperandTable[OpIdx][2];\n";
+  OS << "      if (OpndNum1 != OpndNum2) {\n";
+  OS << "        auto &SrcOp1 = Operands[OpndNum1];\n";
+  OS << "        auto &SrcOp2 = Operands[OpndNum2];\n";
+  OS << "        if (SrcOp1->isReg() && SrcOp2->isReg() &&\n";
+  OS << "            SrcOp1->getReg() != SrcOp2->getReg()) {\n";
+  OS << "          ErrorInfo = OpndNum2;\n";
+  OS << "          return false;\n";
+  OS << "        }\n";
+  OS << "      }\n";
+  OS << "      break;\n";
+  OS << "    }\n";
+  OS << "    default:\n";
+  OS << "      break;\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 (ReportMultipleNearMisses) {
     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 (!checkAsmTiedOperandConstraints(Inst, Operands, Loc)) {\n";
-    OS << "        ErrorInfo = " << (HasMnemonicFirst ? "1" : "SIndex") << ";\n";
+    OS << "      if (!checkAsmTiedOperandConstraints(it->ConvertFn, Operands, ErrorInfo))\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"
if (HasDeprecation) {
     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 (!checkAsmTiedOperandConstraints(Inst, Operands, Loc)) {\n";
-    OS << "        ErrorInfo = " << (HasMnemonicFirst ? "1" : "SIndex") << ";\n";
+    OS << "      if (!checkAsmTiedOperandConstraints(it->ConvertFn, Operands, ErrorInfo))\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";