[MC] Rewrite tablegen for printInstrAlias to comiple faster, NFC

[rnk]

Summary

Before this change, the *InstPrinter.cpp files of each target where some
of the slowest objects to compile in all of LLVM. See this snippet produced by
ClangBuildAnalyzer:
https://reviews.llvm.org/P8171$96
Search for "InstPrinter", and see that it shows up in a few places.

Tablegen was emitting a large switch containing a sequence of operand checks,
each of which created many conditions and many BBs. Register allocation and
jump threading both did not scale well with such a large repetitive sequence of
basic blocks.

So, this change essentially turns those control flow structures into
data. The previous structure looked like:

switch (Opc) {
case TGT::ADD:
  // check alias 1
  if (MI->getOperandCount() == N && // check num opnds
      MI->getOperand(0).isReg() && // check opnd 0
      ...
      MI->getOperand(1).isImm() && // check opnd 1
   AsmString = "foo";
   break;
 }
 // check alias 2
 if (...)
   ...
 return false;

The new structure looks like:

OpToPatterns: Sorted table of opcodes mapping to pattern indices.
 \->
   Patterns: List of patterns. Previous table points to subrange of
             patterns to match.
    \->
      Conds: The if conditions above encoded as a kind and 32-bit value.

See MCInstPrinter.cpp for the details of how the new data structures are
interpreted.

Here are some before and after metrics.
Time to compile AArch64InstPrinter.cpp:

0m29.062s vs. 0m2.203s

size of the obj:

3.9M vs. 676K

size of clang.exe:

97M vs. 96M

I have not benchmarked disassembly performance, but typically
disassemblers are bottlenecked on IO and string processing, not alias
matching, so I'm not sure it's interesting enough to be worth doing.

[RKSimon]

Adding extra reviewers as I'm about to go on holiday...

[spatel]

Looks very promising, but I don't know anything about this layer. Replacing me on the reviewer list with Craig.

[craig.topper]

llvm/utils/TableGen/AsmWriterEmitter.cpp

677

Should we rename this since it doesn't print to a stream anymore?

818

Can we move the IAP object down and pass this to the constructor?

921–923

Bad identation here

954

Why StringRef(Op)? Isn't Op already a StringRef?

[rnk]

• fix issues

[rnk]

Here's an example of the generated output for easier code review:
https://reviews.llvm.org/P8172

llvm/utils/TableGen/AsmWriterEmitter.cpp

677

Yeah. I named it formatAliasString.

818

Sure.

954

True, it is. This code uses std::string a lot, so I think I assumed I needed to convert first.

[craig.topper]

llvm/lib/MC/MCInstPrinter.cpp

106

Nit: I think the first "To" was supposed to be "Too"

llvm/utils/TableGen/AsmWriterEmitter.cpp

682–683

Was this changed from SmallString to std::string so we could just return it? Do we lose out on NRVO by going through OS.str() instead of OS.flush; return OutString;?

685–686

How efficient is putting 1 character at a time into a std::string with respect to heap allocations vs the large SmallString we had before. Though I'm not sure how long these strings are in practice. Do we stay under the small string size for std::string?

[rnk]

llvm/lib/MC/MCInstPrinter.cpp

106

Actually, this wasn't suppose to go up for review. I don't want to do O(n) things that should be O(log n) even in an asserts build. I'll try moving this assert into a static local constructor that runs once.

llvm/utils/TableGen/AsmWriterEmitter.cpp

682–683

Yes, I think you're right.

685–686

Well, this is tablegen anyway, so efficiency is less of a concern. If we wanted to save tablegen time, there are a number of things we could do to speed it up. These strings do end up being under 128 characters in practice, since they are derived from assembler snippets.

[rnk]

• NRVO std::string
• Move is_sorted check

[craig.topper]

LGTM

llvm/include/llvm/MC/MCInstPrinter.h

 
 #include "llvm/Support/Format.h"
 #include <cstdint>
 
 namespace llvm {
 
 class MCAsmInfo;
 class MCInst;
+class MCOperand;
 class MCInstrInfo;
 class MCRegisterInfo;
 class MCSubtargetInfo;
 class raw_ostream;
 class StringRef;
 
 /// Convert `Bytes' to a hex string and output to `OS'
 void dumpBytes(ArrayRef<uint8_t> Bytes, raw_ostream &OS);
 
 namespace HexStyle {
 
 enum Style {
   C,  ///< 0xff
   Asm ///< 0ffh
 };
 
 } // end namespace HexStyle
 
+struct AliasMatchingData;
+
 /// This is an instance of a target assembly language printer that
 /// converts an MCInst to valid target assembly syntax.
 class MCInstPrinter {
 protected:
   /// A stream that comments can be emitted to if desired.  Each comment
   /// must end with a newline.  This will be null if verbose assembly emission
   /// is disabled.
   raw_ostream *CommentStream = nullptr;
   const MCAsmInfo &MAI;
   const MCInstrInfo &MII;
   const MCRegisterInfo &MRI;
 
   /// True if we are printing marked up assembly.
   bool UseMarkup = false;
 
   /// True if we are printing immediates as hex.
   bool PrintImmHex = false;
 
   /// Which style to use for printing hexadecimal values.
   HexStyle::Style PrintHexStyle = HexStyle::C;
 
   /// Utility function for printing annotations.
   void printAnnotation(raw_ostream &OS, StringRef Annot);
 
+  /// Helper for matching MCInsts to alias patterns when printing instructions.
+  const char *matchAliasPatterns(const MCInst *MI, const MCSubtargetInfo *STI,
+                                 const AliasMatchingData &M);
+
 public:
   MCInstPrinter(const MCAsmInfo &mai, const MCInstrInfo &mii,
                 const MCRegisterInfo &mri) : MAI(mai), MII(mii), MRI(mri) {}
 
   virtual ~MCInstPrinter();
 
   /// Customize the printer according to a command line option.
   /// @return true if the option is recognized and applied.
public:
   }
 
   /// Utility functions to print decimal/hexadecimal values.
   format_object<int64_t> formatDec(int64_t Value) const;
   format_object<int64_t> formatHex(int64_t Value) const;
   format_object<uint64_t> formatHex(uint64_t Value) const;
 };
 
+/// Map from opcode to pattern list by binary search.
+struct PatternsForOpcode {
+  uint32_t Opcode;
+  uint16_t PatternStart;
+  uint16_t NumPatterns;
+};
+
+/// Data for each alias pattern. Includes feature bits, string, number of
+/// operands, and a variadic list of conditions to check.
+struct AliasPattern {
+  uint32_t AsmStrOffset;
+  uint32_t AliasCondStart;
+  uint8_t NumOperands;
+  uint8_t NumConds;
+};
+
+struct AliasPatternCond {
+  enum CondKind : uint8_t {
+    K_Feature,    // Match only if a feature is enabled.
+    K_NegFeature, // Match only if a feature is disabled.
+    K_Ignore,     // Match any operand.
+    K_Reg,        // Match a specific register.
+    K_TiedReg,    // Match another already matched register.
+    K_Imm,        // Match a specific immediate.
+    K_RegClass,   // Match registers in a class.
+    K_Custom,     // Call custom matcher by index.
+  };
+
+  CondKind Kind;
+  uint32_t Value;
+};
+
+/// Tablegenerated data structures needed to match alias patterns.
+struct AliasMatchingData {
+  ArrayRef<PatternsForOpcode> OpToPatterns;
+  ArrayRef<AliasPattern> Patterns;
+  ArrayRef<AliasPatternCond> PatternConds;
+  StringRef AsmStrings;
+  bool (*ValidateMCOperand)(const MCOperand &MCOp, const MCSubtargetInfo &STI,
+                            unsigned PredicateIndex);
+};
+
 } // end namespace llvm
 
 #endif // LLVM_MC_MCINSTPRINTER_H

llvm/lib/MC/MCInstPrinter.cpp

 //===- MCInstPrinter.cpp - Convert an MCInst to target assembly syntax ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/MC/MCInstPrinter.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cinttypes>
 #include <cstdint>
 
 using namespace llvm;
 
if (CommentStream) {
       // a newline after each comment.
       if (Annot.back() != '\n')
         (*CommentStream) << '\n';
     } else
       OS << " " << MAI.getCommentString() << " " << Annot;
   }
 }
 
+static bool matchAliasCondition(const MCInst &MI, const MCSubtargetInfo *STI,
+                                const MCRegisterInfo &MRI, unsigned &OpIdx,
+                                const AliasMatchingData &M,
+                                const AliasPatternCond &C) {
+  // Feature tests are special, they don't consume operands.
+  if (C.Kind == AliasPatternCond::K_Feature)
+    return STI->getFeatureBits().test(C.Value);
+  if (C.Kind == AliasPatternCond::K_NegFeature)
+    return !STI->getFeatureBits().test(C.Value);
+
+  // Get and consume an operand.
+  const MCOperand &Opnd = MI.getOperand(OpIdx);
+  ++OpIdx;
+
+  // Check the specific condition for the operand.
+  switch (C.Kind) {
+  case AliasPatternCond::K_Imm:
+    // Operand must be a specific immediate.
+    return Opnd.isImm() && Opnd.getImm() == int32_t(C.Value);
+  case AliasPatternCond::K_Reg:
+    // Operand must be a specific register.
+    return Opnd.isReg() && Opnd.getReg() == C.Value;
+  case AliasPatternCond::K_TiedReg:
+    // Operand must match the register of another operand.
+    return Opnd.isReg() && Opnd.getReg() == MI.getOperand(C.Value).getReg();
+  case AliasPatternCond::K_RegClass:
+    // Operand must be a register in this class. Value is a register class id.
+    return Opnd.isReg() && MRI.getRegClass(C.Value).contains(Opnd.getReg());
+  case AliasPatternCond::K_Custom:
+    // Operand must match some custom criteria.
+    return M.ValidateMCOperand(Opnd, *STI, C.Value);
+  case AliasPatternCond::K_Ignore:
+    // Operand can be anything.
+    return true;
+  case AliasPatternCond::K_Feature:
+  case AliasPatternCond::K_NegFeature:
+    llvm_unreachable("handled earlier");
+  }
+  llvm_unreachable("invalid kind");
+}
+
+const char *MCInstPrinter::matchAliasPatterns(const MCInst *MI,
+                                              const MCSubtargetInfo *STI,
+                                              const AliasMatchingData &M) {
+  // Binary search by opcode. Return false if there are no aliases for this
+  // opcode.
+  auto It = lower_bound(M.OpToPatterns, MI->getOpcode(),
+                        [](const PatternsForOpcode &L, unsigned Opcode) {
+                          return L.Opcode < Opcode;
+                        });
+  if (It == M.OpToPatterns.end() || It->Opcode != MI->getOpcode())
+    return nullptr;
+
+  // Try all patterns for this opcode.
+  uint32_t AsmStrOffset = ~0U;
+  ArrayRef<AliasPattern> Patterns =
+      M.Patterns.slice(It->PatternStart, It->NumPatterns);
+  for (const AliasPattern &P : Patterns) {
+    // Check operand count first.
+    if (MI->getNumOperands() != P.NumOperands)
+      return nullptr;
+
+    // Test all conditions for this pattern.
+    ArrayRef<AliasPatternCond> Conds =
+        M.PatternConds.slice(P.AliasCondStart, P.NumConds);
+    unsigned OpIdx = 0;
+    if (llvm::all_of(Conds, [&](const AliasPatternCond &C) {
+          return matchAliasCondition(*MI, STI, MRI, OpIdx, M, C);
+        })) {
+      // If all conditions matched, use this asm string.
+      AsmStrOffset = P.AsmStrOffset;
+      break;
+    }
+  }
+
+  // If no alias matched, don't print an alias.
+  if (AsmStrOffset == ~0U)
+    return nullptr;
+
+  // Go to offset AsmStrOffset and use the null terminated string there. The
+  // offset should point to the beginning of an alias string, so it should
+  // either be zero or be preceded by a null byte.
+  assert(AsmStrOffset < M.AsmStrings.size() &&
+         (AsmStrOffset == 0 || M.AsmStrings[AsmStrOffset - 1] == '\0') &&
+         "bad asm string offset");
+  return M.AsmStrings.data() + AsmStrOffset;
+}
+
 /// Utility functions to make adding mark ups simpler.
 StringRef MCInstPrinter::markup(StringRef s) const {
   if (getUseMarkup())
     return s;
   else
     return "";
 }
 

llvm/utils/TableGen/AsmWriterEmitter.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>

 }
 
 namespace {
 
 // IAPrinter - Holds information about an InstAlias. Two InstAliases match if
 // they both have the same conditionals. In which case, we cannot print out the
 // alias for that pattern.
 class IAPrinter {
-  std::vector<std::string> Conds;
   std::map<StringRef, std::pair<int, int>> OpMap;
 
+  std::vector<std::string> Conds;
+
   std::string Result;
   std::string AsmString;
 
+  unsigned NumMIOps;
+
 public:
-  IAPrinter(std::string R, std::string AS)
-      : Result(std::move(R)), AsmString(std::move(AS)) {}
+  IAPrinter(std::string R, std::string AS, unsigned NumMIOps)
+      : Result(std::move(R)), AsmString(std::move(AS)), NumMIOps(NumMIOps) {}
 
-  void addCond(const std::string &C) { Conds.push_back(C); }
+  void addCond(std::string C) { Conds.push_back(std::move(C)); }
+  ArrayRef<std::string> getConds() const { return Conds; }
+  size_t getCondCount() const { return Conds.size(); }
 
   void addOperand(StringRef Op, int OpIdx, int PrintMethodIdx = -1) {
     assert(OpIdx >= 0 && OpIdx < 0xFE && "Idx out of range");
     assert(PrintMethodIdx >= -1 && PrintMethodIdx < 0xFF &&
            "Idx out of range");
     OpMap[Op] = std::make_pair(OpIdx, PrintMethodIdx);
   }
 
+  unsigned getNumMIOps() { return NumMIOps; }
+
+  StringRef getResult() { return Result; }
+
   bool isOpMapped(StringRef Op) { return OpMap.find(Op) != OpMap.end(); }
   int getOpIndex(StringRef Op) { return OpMap[Op].first; }
   std::pair<int, int> &getOpData(StringRef Op) { return OpMap[Op]; }
 
   std::pair<StringRef, StringRef::iterator> parseName(StringRef::iterator Start,
                                                       StringRef::iterator End) {
     StringRef::iterator I = Start;
     StringRef::iterator Next;
if (*I == '{') {
               (*I >= '0' && *I <= '9') || *I == '_'))
         ++I;
       Next = I;
     }
 
     return std::make_pair(StringRef(Start, I - Start), Next);
   }
 
-  void print(raw_ostream &O) {
-    if (Conds.empty()) {
-      O.indent(6) << "return true;\n";
-      return;
-    }
-
-    O << "if (";
-
-    for (std::vector<std::string>::iterator
-           I = Conds.begin(), E = Conds.end(); I != E; ++I) {
-      if (I != Conds.begin()) {
-        O << " &&\n";
-        O.indent(8);
-      }
-
-      O << *I;
-    }
-
-    O << ") {\n";
-    O.indent(6) << "// " << Result << "\n";
-
+  std::string formatAliasString(uint32_t &UnescapedSize) {
     // Directly mangle mapped operands into the string. Each operand is
     // identified by a '$' sign followed by a byte identifying the number of the
     // operand. We add one to the index to avoid zero bytes.
     StringRef ASM(AsmString);
-    SmallString<128> OutString;
-    raw_svector_ostream OS(OutString);
+    std::string OutString;
+    raw_string_ostream OS(OutString);
     for (StringRef::iterator I = ASM.begin(), E = ASM.end(); I != E;) {
       OS << *I;
+      ++UnescapedSize;
       if (*I == '$') {
         StringRef Name;
         std::tie(Name, I) = parseName(++I, E);
         assert(isOpMapped(Name) && "Unmapped operand!");
 
         int OpIndex, PrintIndex;
         std::tie(OpIndex, PrintIndex) = getOpData(Name);
         if (PrintIndex == -1) {
           // Can use the default printOperand route.
           OS << format("\\x%02X", (unsigned char)OpIndex + 1);
-        } else
+          ++UnescapedSize;
+        } else {
           // 3 bytes if a PrintMethod is needed: 0xFF, the MCInst operand
           // number, and which of our pre-detected Methods to call.
           OS << format("\\xFF\\x%02X\\x%02X", OpIndex + 1, PrintIndex + 1);
+          UnescapedSize += 3;
+        }
       } else {
         ++I;
       }
     }
 
-    // Emit the string.
-    O.indent(6) << "AsmString = \"" << OutString << "\";\n";
-
-    O.indent(6) << "break;\n";
-    O.indent(4) << '}';
+    OS.flush();
+    return OutString;
   }
 
   bool operator==(const IAPrinter &RHS) const {
+    if (NumMIOps != RHS.NumMIOps)
+      return false;
     if (Conds.size() != RHS.Conds.size())
       return false;
 
     unsigned Idx = 0;
     for (const auto &str : Conds)
       if (str != RHS.Conds[Idx++])
         return false;
 
void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
 
   std::vector<std::string> PrintMethods;
 
   // A list of MCOperandPredicates for all operands in use, and the reverse map
   std::vector<const Record*> MCOpPredicates;
   DenseMap<const Record*, unsigned> MCOpPredicateMap;
 
   for (auto &Aliases : AliasMap) {
+    // Collection of instruction alias rules. May contain ambiguous rules.
+    std::vector<IAPrinter> IAPs;
+
     for (auto &Alias : Aliases.second) {
       const CodeGenInstAlias &CGA = Alias.first;
       unsigned LastOpNo = CGA.ResultInstOperandIndex.size();
       std::string FlatInstAsmString =
          CodeGenInstruction::FlattenAsmStringVariants(CGA.ResultInst->AsmString,
                                                       Variant);
       unsigned NumResultOps = CountNumOperands(FlatInstAsmString, Variant);
 
       std::string FlatAliasAsmString =
-        CodeGenInstruction::FlattenAsmStringVariants(CGA.AsmString,
-                                                      Variant);
+          CodeGenInstruction::FlattenAsmStringVariants(CGA.AsmString, Variant);
 
       // Don't emit the alias if it has more operands than what it's aliasing.
       if (NumResultOps < CountNumOperands(FlatAliasAsmString, Variant))
         continue;
 
-      IAPrinter IAP(CGA.Result->getAsString(), FlatAliasAsmString);
-
       StringRef Namespace = Target.getName();
-      std::vector<Record *> ReqFeatures;
-      if (PassSubtarget) {
-        // We only consider ReqFeatures predicates if PassSubtarget
-        std::vector<Record *> RF =
-            CGA.TheDef->getValueAsListOfDefs("Predicates");
-        copy_if(RF, std::back_inserter(ReqFeatures), [](Record *R) {
-          return R->getValueAsBit("AssemblerMatcherPredicate");
-        });
-      }
-
       unsigned NumMIOps = 0;
       for (auto &ResultInstOpnd : CGA.ResultInst->Operands)
         NumMIOps += ResultInstOpnd.MINumOperands;
 
-      std::string Cond;
-      Cond = std::string("MI->getNumOperands() == ") + utostr(NumMIOps);
-      IAP.addCond(Cond);
+      IAPrinter IAP(CGA.Result->getAsString(), FlatAliasAsmString, NumMIOps);
 
       bool CantHandle = false;
 
       unsigned MIOpNum = 0;
       for (unsigned i = 0, e = LastOpNo; i != e; ++i) {
         // Skip over tied operands as they're not part of an alias declaration.
         auto &Operands = CGA.ResultInst->Operands;
         while (true) {
           unsigned OpNum = Operands.getSubOperandNumber(MIOpNum).first;
           if (Operands[OpNum].MINumOperands == 1 &&
               Operands[OpNum].getTiedRegister() != -1) {
             // Tied operands of different RegisterClass should be explicit within
             // an instruction's syntax and so cannot be skipped.
             int TiedOpNum = Operands[OpNum].getTiedRegister();
             if (Operands[OpNum].Rec->getName() ==
                 Operands[TiedOpNum].Rec->getName()) {
               ++MIOpNum;
               continue;
             }
           }
           break;
         }
 
-        std::string Op = "MI->getOperand(" + utostr(MIOpNum) + ")";
+        // Ignore unchecked result operands.
+        while (IAP.getCondCount() < MIOpNum)
+          IAP.addCond("AliasPatternCond::K_Ignore, 0");
 
         const CodeGenInstAlias::ResultOperand &RO = CGA.ResultOperands[i];
 
         switch (RO.Kind) {
         case CodeGenInstAlias::ResultOperand::K_Record: {
           const Record *Rec = RO.getRecord();
           StringRef ROName = RO.getName();
           int PrintMethodIdx = -1;
for (auto &Alias : Aliases.second) {
               if (static_cast<unsigned>(PrintMethodIdx) == PrintMethods.size())
                 PrintMethods.push_back(PrintMethod);
             }
           }
 
           if (Rec->isSubClassOf("RegisterOperand"))
             Rec = Rec->getValueAsDef("RegClass");
           if (Rec->isSubClassOf("RegisterClass")) {
-            IAP.addCond(Op + ".isReg()");
-
             if (!IAP.isOpMapped(ROName)) {
               IAP.addOperand(ROName, MIOpNum, PrintMethodIdx);
               Record *R = CGA.ResultOperands[i].getRecord();
               if (R->isSubClassOf("RegisterOperand"))
                 R = R->getValueAsDef("RegClass");
-              Cond = std::string("MRI.getRegClass(") + Target.getName().str() +
-                     "::" + R->getName().str() + "RegClassID).contains(" + Op +
-                     ".getReg())";
+              IAP.addCond(formatv(
+                  "AliasPatternCond::K_RegClass, {0}::{1}RegClassID", Namespace,
+                  R->getName()));
             } else {
-              Cond = Op + ".getReg() == MI->getOperand(" +
-                     utostr(IAP.getOpIndex(ROName)) + ").getReg()";
+              IAP.addCond(formatv("AliasPatternCond::K_TiedReg, {0}",
+                                  IAP.getOpIndex(ROName)));
             }
           } else {
             // Assume all printable operands are desired for now. This can be
             // overridden in the InstAlias instantiation if necessary.
             IAP.addOperand(ROName, MIOpNum, PrintMethodIdx);
 
             // There might be an additional predicate on the MCOperand
             unsigned Entry = MCOpPredicateMap[Rec];
             if (!Entry) {
               if (!Rec->isValueUnset("MCOperandPredicate")) {
                 MCOpPredicates.push_back(Rec);
                 Entry = MCOpPredicates.size();
                 MCOpPredicateMap[Rec] = Entry;
               } else
                 break; // No conditions on this operand at all
             }
-            Cond = (Target.getName() + ClassName + "ValidateMCOperand(" + Op +
-                    ", STI, " + utostr(Entry) + ")")
-                       .str();
+            IAP.addCond(formatv("AliasPatternCond::K_Custom, {0}", Entry));
           }
-          // for all subcases of ResultOperand::K_Record:
-          IAP.addCond(Cond);
           break;
         }
         case CodeGenInstAlias::ResultOperand::K_Imm: {
           // Just because the alias has an immediate result, doesn't mean the
           // MCInst will. An MCExpr could be present, for example.
-          IAP.addCond(Op + ".isImm()");
-
-          Cond = Op + ".getImm() == " + itostr(CGA.ResultOperands[i].getImm());
-          IAP.addCond(Cond);
+          auto Imm = CGA.ResultOperands[i].getImm();
+          int32_t Imm32 = int32_t(Imm);
+          if (Imm != Imm32)
+            PrintFatalError("Matching an alias with an immediate out of the "
+                            "range of int32_t is not supported");
+          IAP.addCond(formatv("AliasPatternCond::K_Imm, uint32_t({0})", Imm32));
           break;
         }
         case CodeGenInstAlias::ResultOperand::K_Reg:
           // If this is zero_reg, something's playing tricks we're not
           // equipped to handle.
           if (!CGA.ResultOperands[i].getRegister()) {
             CantHandle = true;
             break;
           }
 
-          Cond = Op + ".getReg() == " + Target.getName().str() + "::" +
-                 CGA.ResultOperands[i].getRegister()->getName().str();
-          IAP.addCond(Cond);
+          StringRef Reg = CGA.ResultOperands[i].getRegister()->getName();
+          IAP.addCond(
+              formatv("AliasPatternCond::K_Reg, {0}::{1}", Namespace, Reg));
           break;
         }
 
         MIOpNum += RO.getMINumOperands();
       }
 
       if (CantHandle) continue;
 
+      std::vector<Record *> ReqFeatures;
+      if (PassSubtarget) {
+        // We only consider ReqFeatures predicates if PassSubtarget
+        std::vector<Record *> RF =
+            CGA.TheDef->getValueAsListOfDefs("Predicates");
+        copy_if(RF, std::back_inserter(ReqFeatures), [](Record *R) {
+          return R->getValueAsBit("AssemblerMatcherPredicate");
+        });
+      }
+
       for (auto I = ReqFeatures.cbegin(); I != ReqFeatures.cend(); I++) {
         Record *R = *I;
         StringRef AsmCondString = R->getValueAsString("AssemblerCondString");
 
         // AsmCondString has syntax [!]F(,[!]F)*
         SmallVector<StringRef, 4> Ops;
         SplitString(AsmCondString, Ops, ",");
         assert(!Ops.empty() && "AssemblerCondString cannot be empty");
 
-        for (auto &Op : Ops) {
+        for (StringRef Op : Ops) {
           assert(!Op.empty() && "Empty operator");
-          if (Op[0] == '!')
-            Cond = ("!STI.getFeatureBits()[" + Namespace + "::" + Op.substr(1) +
-                    "]")
-                       .str();
-          else
-            Cond =
-                ("STI.getFeatureBits()[" + Namespace + "::" + Op + "]").str();
-          IAP.addCond(Cond);
+          bool IsNeg = Op[0] == '!';
+          StringRef Feature = Op.drop_front(IsNeg ? 1 : 0);
+          IAP.addCond(formatv("AliasPatternCond::K_{0}Feature, {1}::{2}",
+                              IsNeg ? "Neg" : "", Namespace, Feature));
         }
       }
 
       IAPrinterMap[Aliases.first].push_back(std::move(IAP));
     }
   }
 
   //////////////////////////////
   // Write out the printAliasInstr function
   //////////////////////////////
 
   std::string Header;
   raw_string_ostream HeaderO(Header);
 
   HeaderO << "bool " << Target.getName() << ClassName
           << "::printAliasInstr(const MCInst"
           << " *MI, " << (PassSubtarget ? "const MCSubtargetInfo &STI, " : "")
           << "raw_ostream &OS) {\n";
 
-  std::string Cases;
-  raw_string_ostream CasesO(Cases);
+  std::string PatternsForOpcode;
+  raw_string_ostream OpcodeO(PatternsForOpcode);
 
-  for (auto &Entry : IAPrinterMap) {
-    std::vector<IAPrinter> &IAPs = Entry.second;
+  unsigned PatternCount = 0;
+  std::string Patterns;
+  raw_string_ostream PatternO(Patterns);
+
+  unsigned CondCount = 0;
+  std::string Conds;
+  raw_string_ostream CondO(Conds);
+
+  // All flattened alias strings.
+  std::map<std::string, uint32_t> AsmStringOffsets;
+  std::vector<std::pair<uint32_t, std::string>> AsmStrings;
+  size_t AsmStringsSize = 0;
+
+  // Iterate over the opcodes in enum order so they are sorted by opcode for
+  // binary search.
+  for (const CodeGenInstruction *Inst : NumberedInstructions) {
+    auto It = IAPrinterMap.find(getQualifiedName(Inst->TheDef));
+    if (It == IAPrinterMap.end())
+      continue;
+    std::vector<IAPrinter> &IAPs = It->second;
     std::vector<IAPrinter*> UniqueIAPs;
 
+    // Remove any ambiguous alias rules.
     for (auto &LHS : IAPs) {
       bool IsDup = false;
       for (const auto &RHS : IAPs) {
         if (&LHS != &RHS && LHS == RHS) {
           IsDup = true;
           break;
         }
       }
 
       if (!IsDup)
         UniqueIAPs.push_back(&LHS);
     }
 
     if (UniqueIAPs.empty()) continue;
 
-    CasesO.indent(2) << "case " << Entry.first << ":\n";
+    unsigned PatternStart = PatternCount;
+
+    // Insert the pattern start and opcode in the pattern list for debugging.
+    PatternO << formatv("    // {0} - {1}\n", It->first, PatternStart);
 
     for (IAPrinter *IAP : UniqueIAPs) {
-      CasesO.indent(4);
-      IAP->print(CasesO);
-      CasesO << '\n';
+      // Start each condition list with a comment of the resulting pattern that
+      // we're trying to match.
+      unsigned CondStart = CondCount;
+      CondO << formatv("    // {0} - {1}\n", IAP->getResult(), CondStart);
+      for (const auto &Cond : IAP->getConds())
+        CondO << "    {" << Cond << "},\n";
+      CondCount += IAP->getCondCount();
+
+      // After operands have been examined, re-encode the alias string with
+      // escapes indicating how operands should be printed.
+      uint32_t UnescapedSize = 0;
+      std::string EncodedAsmString = IAP->formatAliasString(UnescapedSize);
+      auto Insertion =
+          AsmStringOffsets.insert({EncodedAsmString, AsmStringsSize});
+      if (Insertion.second) {
+        // If the string is new, add it to the vector.
+        AsmStrings.push_back({AsmStringsSize, EncodedAsmString});
+        AsmStringsSize += UnescapedSize + 1;
+      }
+      unsigned AsmStrOffset = Insertion.first->second;
+
+      PatternO << formatv("    {{{0}, {1}, {2}, {3} },\n", AsmStrOffset,
+                          CondStart, IAP->getNumMIOps(), IAP->getCondCount());
+      ++PatternCount;
     }
 
-    CasesO.indent(4) << "return false;\n";
+    OpcodeO << formatv("    {{{0}, {1}, {2} },\n", It->first, PatternStart,
+                       PatternCount - PatternStart);
   }
 
-  if (CasesO.str().empty()) {
+  if (OpcodeO.str().empty()) {
     O << HeaderO.str();
     O << "  return false;\n";
     O << "}\n\n";
     O << "#endif // PRINT_ALIAS_INSTR\n";
     return;
   }
 
+  // Forward declare the validation method if needed.
   if (!MCOpPredicates.empty())
     O << "static bool " << Target.getName() << ClassName
       << "ValidateMCOperand(const MCOperand &MCOp,\n"
       << "                  const MCSubtargetInfo &STI,\n"
       << "                  unsigned PredicateIndex);\n";
 
   O << HeaderO.str();
-  O.indent(2) << "const char *AsmString;\n";
-  O.indent(2) << "switch (MI->getOpcode()) {\n";
-  O.indent(2) << "default: return false;\n";
-  O << CasesO.str();
-  O.indent(2) << "}\n\n";
+  O.indent(2) << "static const PatternsForOpcode OpToPatterns[] = {\n";
+  O << OpcodeO.str();
+  O.indent(2) << "};\n\n";
+  O.indent(2) << "static const AliasPattern Patterns[] = {\n";
+  O << PatternO.str();
+  O.indent(2) << "};\n\n";
+  O.indent(2) << "static const AliasPatternCond Conds[] = {\n";
+  O << CondO.str();
+  O.indent(2) << "};\n\n";
+  O.indent(2) << "static const char AsmStrings[] =\n";
+  for (const auto &P : AsmStrings) {
+    O.indent(4) << "/* " << P.first << " */ \"" << P.second << "\\0\"\n";
+  }
+
+  O.indent(2) << ";\n\n";
+
+  // Assert that the opcode table is sorted. Use a static local constructor to
+  // ensure that the check only happens once on first run.
+  O << "#ifndef NDEBUG\n";
+  O.indent(2) << "static struct SortCheck {\n";
+  O.indent(2) << "  SortCheck(ArrayRef<PatternsForOpcode> OpToPatterns) {\n";
+  O.indent(2) << "    assert(std::is_sorted(\n";
+  O.indent(2) << "               OpToPatterns.begin(), OpToPatterns.end(),\n";
+  O.indent(2) << "               [](const PatternsForOpcode &L, const "
+                 "PatternsForOpcode &R) {\n";
+  O.indent(2) << "                 return L.Opcode < R.Opcode;\n";
+  O.indent(2) << "               }) &&\n";
+  O.indent(2) << "           \"tablegen failed to sort opcode patterns\");\n";
+  O.indent(2) << "  }\n";
+  O.indent(2) << "} sortCheckVar(OpToPatterns);\n";
+  O << "#endif\n\n";
+
+  O.indent(2) << "AliasMatchingData M {\n";
+  O.indent(2) << "  makeArrayRef(OpToPatterns),\n";
+  O.indent(2) << "  makeArrayRef(Patterns),\n";
+  O.indent(2) << "  makeArrayRef(Conds),\n";
+  O.indent(2) << "  StringRef(AsmStrings, array_lengthof(AsmStrings)),\n";
+  if (MCOpPredicates.empty())
+    O.indent(2) << "  nullptr,\n";
+  else
+    O.indent(2) << "  &" << Target.getName() << ClassName << "ValidateMCOperand,\n";
+  O.indent(2) << "};\n";
+
+  O.indent(2) << "const char *AsmString = matchAliasPatterns(MI, "
+              << (PassSubtarget ? "&STI" : "nullptr") << ", M);\n";
+  O.indent(2) << "if (!AsmString) return false;\n\n";
 
   // Code that prints the alias, replacing the operands with the ones from the
   // MCInst.
   O << "  unsigned I = 0;\n";
   O << "  while (AsmString[I] != ' ' && AsmString[I] != '\\t' &&\n";
   O << "         AsmString[I] != '$' && AsmString[I] != '\\0')\n";
   O << "    ++I;\n";
   O << "  OS << '\\t' << StringRef(AsmString, I);\n";