llvm/utils/TableGen/X86FoldTablesEmitter.cpp

   1 //===- utils/TableGen/X86FoldTablesEmitter.cpp - X86 backend-*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This tablegen backend is responsible for emitting the memory fold tables of
  10 // the X86 backend instructions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CodeGenInstruction.h"
  15 #include "CodeGenTarget.h"
  16 #include "X86RecognizableInstr.h"
  17 #include "llvm/Support/FormattedStream.h"
  18 #include "llvm/Support/X86FoldTablesUtils.h"
  19 #include "llvm/TableGen/Record.h"
  20 #include "llvm/TableGen/TableGenBackend.h"
  21 #include <set>
  22
  23 using namespace llvm;
  24 using namespace X86Disassembler;
  25
  26 namespace {
  27 // Represents an entry in the manual mapped instructions set.
  28 struct ManualMapEntry {
  29   const char *RegInstStr;
  30   const char *MemInstStr;
  31   uint16_t Strategy;
  32 };
  33
  34 // List of instructions requiring explicitly aligned memory.
  35 const char *ExplicitAlign[] = {"MOVDQA",  "MOVAPS",  "MOVAPD",  "MOVNTPS",
  36                                "MOVNTPD", "MOVNTDQ", "MOVNTDQA"};
  37
  38 // List of instructions NOT requiring explicit memory alignment.
  39 const char *ExplicitUnalign[] = {"MOVDQU",    "MOVUPS",    "MOVUPD",
  40                                  "PCMPESTRM", "PCMPESTRI", "PCMPISTRM",
  41                                  "PCMPISTRI"};
  42
  43 const ManualMapEntry ManualMapSet[] = {
  44 #define ENTRY(REG, MEM, FLAGS) {#REG, #MEM, FLAGS},
  45 #include "X86ManualFoldTables.def"
  46 };
  47
  48 const std::set<StringRef> NoFoldSet = {
  49 #define NOFOLD(INSN) #INSN,
  50 #include "X86ManualFoldTables.def"
  51 };
  52
  53 static bool isExplicitAlign(const CodeGenInstruction *Inst) {
  54   return any_of(ExplicitAlign, [Inst](const char *InstStr) {
  55     return Inst->TheDef->getName().contains(InstStr);
  56   });
  57 }
  58
  59 static bool isExplicitUnalign(const CodeGenInstruction *Inst) {
  60   return any_of(ExplicitUnalign, [Inst](const char *InstStr) {
  61     return Inst->TheDef->getName().contains(InstStr);
  62   });
  63 }
  64
  65 class X86FoldTablesEmitter {
  66   RecordKeeper &Records;
  67   CodeGenTarget Target;
  68
  69   // Represents an entry in the folding table
  70   class X86FoldTableEntry {
  71     const CodeGenInstruction *RegInst;
  72     const CodeGenInstruction *MemInst;
  73
  74   public:
  75     bool NoReverse = false;
  76     bool NoForward = false;
  77     bool FoldLoad = false;
  78     bool FoldStore = false;
  79     enum BcastType {
  80       BCAST_NONE,
  81       BCAST_D,
  82       BCAST_Q,
  83       BCAST_SS,
  84       BCAST_SD,
  85       BCAST_SH,
  86     };
  87     BcastType BroadcastKind = BCAST_NONE;
  88
  89     Align Alignment;
  90
  91     X86FoldTableEntry() = default;
  92     X86FoldTableEntry(const CodeGenInstruction *RegInst,
  93                       const CodeGenInstruction *MemInst)
  94         : RegInst(RegInst), MemInst(MemInst) {}
  95
  96     void print(formatted_raw_ostream &OS) const {
  97       OS.indent(2);
  98       OS << "{X86::" << RegInst->TheDef->getName() << ", ";
  99       OS << "X86::" << MemInst->TheDef->getName() << ", ";
 100
 101       std::string Attrs;
 102       if (FoldLoad)
 103         Attrs += "TB_FOLDED_LOAD|";
 104       if (FoldStore)
 105         Attrs += "TB_FOLDED_STORE|";
 106       if (NoReverse)
 107         Attrs += "TB_NO_REVERSE|";
 108       if (NoForward)
 109         Attrs += "TB_NO_FORWARD|";
 110       if (Alignment != Align(1))
 111         Attrs += "TB_ALIGN_" + std::to_string(Alignment.value()) + "|";
 112       switch (BroadcastKind) {
 113       case BCAST_NONE:
 114         break;
 115       case BCAST_D:
 116         Attrs += "TB_BCAST_D|";
 117         break;
 118       case BCAST_Q:
 119         Attrs += "TB_BCAST_Q|";
 120         break;
 121       case BCAST_SS:
 122         Attrs += "TB_BCAST_SS|";
 123         break;
 124       case BCAST_SD:
 125         Attrs += "TB_BCAST_SD|";
 126         break;
 127       case BCAST_SH:
 128         Attrs += "TB_BCAST_SH|";
 129         break;
 130       }
 131
 132       StringRef SimplifiedAttrs = StringRef(Attrs).rtrim("|");
 133       if (SimplifiedAttrs.empty())
 134         SimplifiedAttrs = "0";
 135
 136       OS << SimplifiedAttrs << "},\n";
 137     }
 138
 139 #ifndef NDEBUG
 140     // Check that Uses and Defs are same after memory fold.
 141     void checkCorrectness() const {
 142       auto &RegInstRec = *RegInst->TheDef;
 143       auto &MemInstRec = *MemInst->TheDef;
 144       auto ListOfUsesReg = RegInstRec.getValueAsListOfDefs("Uses");
 145       auto ListOfUsesMem = MemInstRec.getValueAsListOfDefs("Uses");
 146       auto ListOfDefsReg = RegInstRec.getValueAsListOfDefs("Defs");
 147       auto ListOfDefsMem = MemInstRec.getValueAsListOfDefs("Defs");
 148       if (ListOfUsesReg != ListOfUsesMem || ListOfDefsReg != ListOfDefsMem)
 149         report_fatal_error("Uses/Defs couldn't be changed after folding " +
 150                            RegInstRec.getName() + " to " +
 151                            MemInstRec.getName());
 152     }
 153 #endif
 154   };
 155
 156   // NOTE: We check the fold tables are sorted in X86InstrFoldTables.cpp by the
 157   // enum of the instruction, which is computed in
 158   // CodeGenTarget::ComputeInstrsByEnum. So we should use the same comparator
 159   // here.
 160   // FIXME: Could we share the code with CodeGenTarget::ComputeInstrsByEnum?
 161   struct CompareInstrsByEnum {
 162     bool operator()(const CodeGenInstruction *LHS,
 163                     const CodeGenInstruction *RHS) const {
 164       assert(LHS && RHS && "LHS and RHS shouldn't be nullptr");
 165       const auto &D1 = *LHS->TheDef;
 166       const auto &D2 = *RHS->TheDef;
 167       return std::make_tuple(!D1.getValueAsBit("isPseudo"), D1.getName()) <
 168              std::make_tuple(!D2.getValueAsBit("isPseudo"), D2.getName());
 169     }
 170   };
 171
 172   typedef std::map<const CodeGenInstruction *, X86FoldTableEntry,
 173                    CompareInstrsByEnum>
 174       FoldTable;
 175   // Table2Addr - Holds instructions which their memory form performs
 176   //              load+store.
 177   //
 178   // Table#i - Holds instructions which the their memory form
 179   //           performs a load OR a store, and their #i'th operand is folded.
 180   //
 181   // BroadcastTable#i - Holds instructions which the their memory form performs
 182   //                    a broadcast load and their #i'th operand is folded.
 183   FoldTable Table2Addr;
 184   FoldTable Table0;
 185   FoldTable Table1;
 186   FoldTable Table2;
 187   FoldTable Table3;
 188   FoldTable Table4;
 189   FoldTable BroadcastTable1;
 190   FoldTable BroadcastTable2;
 191   FoldTable BroadcastTable3;
 192   FoldTable BroadcastTable4;
 193
 194 public:
 195   X86FoldTablesEmitter(RecordKeeper &R) : Records(R), Target(R) {}
 196
 197   // run - Generate the 6 X86 memory fold tables.
 198   void run(raw_ostream &OS);
 199
 200 private:
 201   // Decides to which table to add the entry with the given instructions.
 202   // S sets the strategy of adding the TB_NO_REVERSE flag.
 203   void updateTables(const CodeGenInstruction *RegInst,
 204                     const CodeGenInstruction *MemInst, uint16_t S = 0,
 205                     bool IsManual = false, bool IsBroadcast = false);
 206
 207   // Generates X86FoldTableEntry with the given instructions and fill it with
 208   // the appropriate flags, then adds it to a memory fold table.
 209   void addEntryWithFlags(FoldTable &Table, const CodeGenInstruction *RegInst,
 210                          const CodeGenInstruction *MemInst, uint16_t S,
 211                          unsigned FoldedIdx, bool IsManual);
 212   // Generates X86FoldTableEntry with the given instructions and adds it to a
 213   // broadcast table.
 214   void addBroadcastEntry(FoldTable &Table, const CodeGenInstruction *RegInst,
 215                          const CodeGenInstruction *MemInst);
 216
 217   // Print the given table as a static const C++ array of type
 218   // X86FoldTableEntry.
 219   void printTable(const FoldTable &Table, StringRef TableName,
 220                   formatted_raw_ostream &OS) {
 221     OS << "static const X86FoldTableEntry " << TableName << "[] = {\n";
 222
 223     for (auto &E : Table)
 224       E.second.print(OS);
 225
 226     OS << "};\n\n";
 227   }
 228 };
 229
 230 // Return true if one of the instruction's operands is a RST register class
 231 static bool hasRSTRegClass(const CodeGenInstruction *Inst) {
 232   return any_of(Inst->Operands, [](const CGIOperandList::OperandInfo &OpIn) {
 233     return OpIn.Rec->getName() == "RST" || OpIn.Rec->getName() == "RSTi";
 234   });
 235 }
 236
 237 // Return true if one of the instruction's operands is a ptr_rc_tailcall
 238 static bool hasPtrTailcallRegClass(const CodeGenInstruction *Inst) {
 239   return any_of(Inst->Operands, [](const CGIOperandList::OperandInfo &OpIn) {
 240     return OpIn.Rec->getName() == "ptr_rc_tailcall";
 241   });
 242 }
 243
 244 static uint8_t byteFromBitsInit(const BitsInit *B) {
 245   unsigned N = B->getNumBits();
 246   assert(N <= 8 && "Field is too large for uint8_t!");
 247
 248   uint8_t Value = 0;
 249   for (unsigned I = 0; I != N; ++I) {
 250     BitInit *Bit = cast<BitInit>(B->getBit(I));
 251     Value |= Bit->getValue() << I;
 252   }
 253   return Value;
 254 }
 255
 256 static bool mayFoldFromForm(uint8_t Form) {
 257   switch (Form) {
 258   default:
 259     return Form >= X86Local::MRM0r && Form <= X86Local::MRM7r;
 260   case X86Local::MRMXr:
 261   case X86Local::MRMXrCC:
 262   case X86Local::MRMDestReg:
 263   case X86Local::MRMSrcReg:
 264   case X86Local::MRMSrcReg4VOp3:
 265   case X86Local::MRMSrcRegOp4:
 266   case X86Local::MRMSrcRegCC:
 267     return true;
 268   }
 269 }
 270
 271 static bool mayFoldToForm(uint8_t Form) {
 272   switch (Form) {
 273   default:
 274     return Form >= X86Local::MRM0m && Form <= X86Local::MRM7m;
 275   case X86Local::MRMXm:
 276   case X86Local::MRMXmCC:
 277   case X86Local::MRMDestMem:
 278   case X86Local::MRMSrcMem:
 279   case X86Local::MRMSrcMem4VOp3:
 280   case X86Local::MRMSrcMemOp4:
 281   case X86Local::MRMSrcMemCC:
 282     return true;
 283   }
 284 }
 285
 286 static bool mayFoldFromLeftToRight(uint8_t LHS, uint8_t RHS) {
 287   switch (LHS) {
 288   default:
 289     llvm_unreachable("Unexpected Form!");
 290   case X86Local::MRM0r:
 291     return RHS == X86Local::MRM0m;
 292   case X86Local::MRM1r:
 293     return RHS == X86Local::MRM1m;
 294   case X86Local::MRM2r:
 295     return RHS == X86Local::MRM2m;
 296   case X86Local::MRM3r:
 297     return RHS == X86Local::MRM3m;
 298   case X86Local::MRM4r:
 299     return RHS == X86Local::MRM4m;
 300   case X86Local::MRM5r:
 301     return RHS == X86Local::MRM5m;
 302   case X86Local::MRM6r:
 303     return RHS == X86Local::MRM6m;
 304   case X86Local::MRM7r:
 305     return RHS == X86Local::MRM7m;
 306   case X86Local::MRMXr:
 307     return RHS == X86Local::MRMXm;
 308   case X86Local::MRMXrCC:
 309     return RHS == X86Local::MRMXmCC;
 310   case X86Local::MRMDestReg:
 311     return RHS == X86Local::MRMDestMem;
 312   case X86Local::MRMSrcReg:
 313     return RHS == X86Local::MRMSrcMem;
 314   case X86Local::MRMSrcReg4VOp3:
 315     return RHS == X86Local::MRMSrcMem4VOp3;
 316   case X86Local::MRMSrcRegOp4:
 317     return RHS == X86Local::MRMSrcMemOp4;
 318   case X86Local::MRMSrcRegCC:
 319     return RHS == X86Local::MRMSrcMemCC;
 320   }
 321 }
 322
 323 static bool isNOREXRegClass(const Record *Op) {
 324   return Op->getName().contains("_NOREX");
 325 }
 326
 327 // Function object - Operator() returns true if the given Reg instruction
 328 // matches the Mem instruction of this object.
 329 class IsMatch {
 330   const CodeGenInstruction *MemInst;
 331   const X86Disassembler::RecognizableInstrBase MemRI;
 332   bool IsBroadcast;
 333   const unsigned Variant;
 334
 335 public:
 336   IsMatch(const CodeGenInstruction *Inst, bool IsBroadcast, unsigned V)
 337       : MemInst(Inst), MemRI(*MemInst), IsBroadcast(IsBroadcast), Variant(V) {}
 338
 339   bool operator()(const CodeGenInstruction *RegInst) {
 340     X86Disassembler::RecognizableInstrBase RegRI(*RegInst);
 341     const Record *RegRec = RegInst->TheDef;
 342     const Record *MemRec = MemInst->TheDef;
 343
 344     // EVEX_B means different things for memory and register forms.
 345     // register form: rounding control or SAE
 346     // memory form: broadcast
 347     if (IsBroadcast && (RegRI.HasEVEX_B || !MemRI.HasEVEX_B))
 348       return false;
 349     if (!IsBroadcast && (RegRI.HasEVEX_B || MemRI.HasEVEX_B))
 350       return false;
 351
 352     if (!mayFoldFromLeftToRight(RegRI.Form, MemRI.Form))
 353       return false;
 354
 355     // X86 encoding is crazy, e.g
 356     //
 357     // f3 0f c7 30       vmxon   (%rax)
 358     // f3 0f c7 f0       senduipi        %rax
 359     //
 360     // This two instruction have similiar encoding fields but are unrelated
 361     if (X86Disassembler::getMnemonic(MemInst, Variant) !=
 362         X86Disassembler::getMnemonic(RegInst, Variant))
 363       return false;
 364
 365     // Return false if any of the following fields of does not match.
 366     if (std::make_tuple(RegRI.Encoding, RegRI.Opcode, RegRI.OpPrefix,
 367                         RegRI.OpMap, RegRI.OpSize, RegRI.AdSize, RegRI.HasREX_W,
 368                         RegRI.HasVEX_4V, RegRI.HasVEX_L, RegRI.IgnoresVEX_L,
 369                         RegRI.IgnoresW, RegRI.HasEVEX_K, RegRI.HasEVEX_KZ,
 370                         RegRI.HasEVEX_L2, RegRec->getValueAsBit("hasEVEX_RC"),
 371                         RegRec->getValueAsBit("hasLockPrefix"),
 372                         RegRec->getValueAsBit("hasNoTrackPrefix"),
 373                         RegRec->getValueAsBit("EVEX_W1_VEX_W0")) !=
 374         std::make_tuple(MemRI.Encoding, MemRI.Opcode, MemRI.OpPrefix,
 375                         MemRI.OpMap, MemRI.OpSize, MemRI.AdSize, MemRI.HasREX_W,
 376                         MemRI.HasVEX_4V, MemRI.HasVEX_L, MemRI.IgnoresVEX_L,
 377                         MemRI.IgnoresW, MemRI.HasEVEX_K, MemRI.HasEVEX_KZ,
 378                         MemRI.HasEVEX_L2, MemRec->getValueAsBit("hasEVEX_RC"),
 379                         MemRec->getValueAsBit("hasLockPrefix"),
 380                         MemRec->getValueAsBit("hasNoTrackPrefix"),
 381                         MemRec->getValueAsBit("EVEX_W1_VEX_W0")))
 382       return false;
 383
 384     // Make sure the sizes of the operands of both instructions suit each other.
 385     // This is needed for instructions with intrinsic version (_Int).
 386     // Where the only difference is the size of the operands.
 387     // For example: VUCOMISDZrm and VUCOMISDrm_Int
 388     // Also for instructions that their EVEX version was upgraded to work with
 389     // k-registers. For example VPCMPEQBrm (xmm output register) and
 390     // VPCMPEQBZ128rm (k register output register).
 391     unsigned MemOutSize = MemRec->getValueAsDag("OutOperandList")->getNumArgs();
 392     unsigned RegOutSize = RegRec->getValueAsDag("OutOperandList")->getNumArgs();
 393     unsigned MemInSize = MemRec->getValueAsDag("InOperandList")->getNumArgs();
 394     unsigned RegInSize = RegRec->getValueAsDag("InOperandList")->getNumArgs();
 395
 396     // Instructions with one output in their memory form use the memory folded
 397     // operand as source and destination (Read-Modify-Write).
 398     unsigned RegStartIdx =
 399         (MemOutSize + 1 == RegOutSize) && (MemInSize == RegInSize) ? 1 : 0;
 400
 401     bool FoundFoldedOp = false;
 402     for (unsigned I = 0, E = MemInst->Operands.size(); I != E; I++) {
 403       Record *MemOpRec = MemInst->Operands[I].Rec;
 404       Record *RegOpRec = RegInst->Operands[I + RegStartIdx].Rec;
 405
 406       if (MemOpRec == RegOpRec)
 407         continue;
 408
 409       if (isRegisterOperand(MemOpRec) && isRegisterOperand(RegOpRec) &&
 410           ((getRegOperandSize(MemOpRec) != getRegOperandSize(RegOpRec)) ||
 411            (isNOREXRegClass(MemOpRec) != isNOREXRegClass(RegOpRec))))
 412         return false;
 413
 414       if (isMemoryOperand(MemOpRec) && isMemoryOperand(RegOpRec) &&
 415           (getMemOperandSize(MemOpRec) != getMemOperandSize(RegOpRec)))
 416         return false;
 417
 418       if (isImmediateOperand(MemOpRec) && isImmediateOperand(RegOpRec) &&
 419           (MemOpRec->getValueAsDef("Type") != RegOpRec->getValueAsDef("Type")))
 420         return false;
 421
 422       // Only one operand can be folded.
 423       if (FoundFoldedOp)
 424         return false;
 425
 426       assert(isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec));
 427       FoundFoldedOp = true;
 428     }
 429
 430     return FoundFoldedOp;
 431   }
 432 };
 433
 434 } // end anonymous namespace
 435
 436 void X86FoldTablesEmitter::addEntryWithFlags(FoldTable &Table,
 437                                              const CodeGenInstruction *RegInst,
 438                                              const CodeGenInstruction *MemInst,
 439                                              uint16_t S, unsigned FoldedIdx,
 440                                              bool IsManual) {
 441
 442   assert((IsManual || Table.find(RegInst) == Table.end()) &&
 443          "Override entry unexpectedly");
 444   X86FoldTableEntry Result = X86FoldTableEntry(RegInst, MemInst);
 445   Record *RegRec = RegInst->TheDef;
 446   Record *MemRec = MemInst->TheDef;
 447
 448   Result.NoReverse = S & TB_NO_REVERSE;
 449   Result.NoForward = S & TB_NO_FORWARD;
 450   Result.FoldLoad = S & TB_FOLDED_LOAD;
 451   Result.FoldStore = S & TB_FOLDED_STORE;
 452   Result.Alignment = Align(1ULL << ((S & TB_ALIGN_MASK) >> TB_ALIGN_SHIFT));
 453   if (IsManual) {
 454     Table[RegInst] = Result;
 455     return;
 456   }
 457
 458   // Only table0 entries should explicitly specify a load or store flag.
 459   if (&Table == &Table0) {
 460     unsigned MemInOpsNum = MemRec->getValueAsDag("InOperandList")->getNumArgs();
 461     unsigned RegInOpsNum = RegRec->getValueAsDag("InOperandList")->getNumArgs();
 462     // If the instruction writes to the folded operand, it will appear as an
 463     // output in the register form instruction and as an input in the memory
 464     // form instruction.
 465     // If the instruction reads from the folded operand, it well appear as in
 466     // input in both forms.
 467     if (MemInOpsNum == RegInOpsNum)
 468       Result.FoldLoad = true;
 469     else
 470       Result.FoldStore = true;
 471   }
 472
 473   Record *RegOpRec = RegInst->Operands[FoldedIdx].Rec;
 474   Record *MemOpRec = MemInst->Operands[FoldedIdx].Rec;
 475
 476   // Unfolding code generates a load/store instruction according to the size of
 477   // the register in the register form instruction.
 478   // If the register's size is greater than the memory's operand size, do not
 479   // allow unfolding.
 480
 481   // the unfolded load size will be based on the register size. If that’s bigger
 482   // than the memory operand size, the unfolded load will load more memory and
 483   // potentially cause a memory fault.
 484   if (getRegOperandSize(RegOpRec) > getMemOperandSize(MemOpRec))
 485     Result.NoReverse = true;
 486
 487   // Check no-kz version's isMoveReg
 488   StringRef RegInstName = RegRec->getName();
 489   unsigned DropLen =
 490       RegInstName.ends_with("rkz") ? 2 : (RegInstName.ends_with("rk") ? 1 : 0);
 491   Record *BaseDef =
 492       DropLen ? Records.getDef(RegInstName.drop_back(DropLen)) : nullptr;
 493   bool IsMoveReg =
 494       BaseDef ? Target.getInstruction(BaseDef).isMoveReg : RegInst->isMoveReg;
 495   // A masked load can not be unfolded to a full load, otherwise it would access
 496   // unexpected memory. A simple store can not be unfolded.
 497   if (IsMoveReg && (BaseDef || Result.FoldStore))
 498     Result.NoReverse = true;
 499
 500   uint8_t Enc = byteFromBitsInit(RegRec->getValueAsBitsInit("OpEncBits"));
 501   if (isExplicitAlign(RegInst)) {
 502     // The instruction require explicitly aligned memory.
 503     BitsInit *VectSize = RegRec->getValueAsBitsInit("VectSize");
 504     Result.Alignment = Align(byteFromBitsInit(VectSize));
 505   } else if (!Enc && !isExplicitUnalign(RegInst) &&
 506              getMemOperandSize(MemOpRec) > 64) {
 507     // Instructions with XOP/VEX/EVEX encoding do not require alignment while
 508     // SSE packed vector instructions require a 16 byte alignment.
 509     Result.Alignment = Align(16);
 510   }
 511   // Expand is only ever created as a masked instruction. It is not safe to
 512   // unfold a masked expand because we don't know if it came from an expand load
 513   // intrinsic or folding a plain load. If it is from a expand load intrinsic,
 514   // Unfolding to plain load would read more elements and could trigger a fault.
 515   if (RegRec->getName().contains("EXPAND"))
 516     Result.NoReverse = true;
 517
 518   Table[RegInst] = Result;
 519 }
 520
 521 void X86FoldTablesEmitter::addBroadcastEntry(
 522     FoldTable &Table, const CodeGenInstruction *RegInst,
 523     const CodeGenInstruction *MemInst) {
 524
 525   assert(Table.find(RegInst) == Table.end() && "Override entry unexpectedly");
 526   X86FoldTableEntry Result = X86FoldTableEntry(RegInst, MemInst);
 527
 528   Record *RegRec = RegInst->TheDef;
 529   StringRef RegInstName = RegRec->getName();
 530   StringRef MemInstName = MemInst->TheDef->getName();
 531   Record *Domain = RegRec->getValueAsDef("ExeDomain");
 532   bool IsSSEPackedInt = Domain->getName() == "SSEPackedInt";
 533   if ((RegInstName.contains("DZ") || RegInstName.contains("DWZ") ||
 534        RegInstName.contains("Dr") || RegInstName.contains("I32")) &&
 535       IsSSEPackedInt) {
 536     assert((MemInstName.contains("DZ") || RegInstName.contains("DWZ") ||
 537             MemInstName.contains("Dr") || MemInstName.contains("I32")) &&
 538            "Unmatched names for broadcast");
 539     Result.BroadcastKind = X86FoldTableEntry::BCAST_D;
 540   } else if ((RegInstName.contains("QZ") || RegInstName.contains("QBZ") ||
 541               RegInstName.contains("Qr") || RegInstName.contains("I64")) &&
 542              IsSSEPackedInt) {
 543     assert((MemInstName.contains("QZ") || MemInstName.contains("QBZ") ||
 544             MemInstName.contains("Qr") || MemInstName.contains("I64")) &&
 545            "Unmatched names for broadcast");
 546     Result.BroadcastKind = X86FoldTableEntry::BCAST_Q;
 547   } else if ((RegInstName.contains("PS") || RegInstName.contains("F32") ||
 548               RegInstName.contains("CPH")) &&
 549              !RegInstName.contains("PH2PS")) {
 550     assert((MemInstName.contains("PS") || MemInstName.contains("F32") ||
 551             MemInstName.contains("CPH")) &&
 552            "Unmatched names for broadcast");
 553     Result.BroadcastKind = X86FoldTableEntry::BCAST_SS;
 554   } else if ((RegInstName.contains("PD") || RegInstName.contains("F64")) &&
 555              !RegInstName.contains("PH2PD")) {
 556     assert((MemInstName.contains("PD") || MemInstName.contains("F64")) &&
 557            "Unmatched names for broadcast");
 558     Result.BroadcastKind = X86FoldTableEntry::BCAST_SD;
 559   } else if (RegInstName.contains("PH")) {
 560     assert(MemInstName.contains("PH") && "Unmatched names for broadcast");
 561     Result.BroadcastKind = X86FoldTableEntry::BCAST_SH;
 562   } else {
 563     errs() << RegInstName << ", " << MemInstName << "\n";
 564     llvm_unreachable("Name is not canoicalized for broadcast or "
 565                      "ExeDomain is incorrect");
 566   }
 567
 568   Table[RegInst] = Result;
 569 }
 570
 571 void X86FoldTablesEmitter::updateTables(const CodeGenInstruction *RegInst,
 572                                         const CodeGenInstruction *MemInst,
 573                                         uint16_t S, bool IsManual,
 574                                         bool IsBroadcast) {
 575
 576   Record *RegRec = RegInst->TheDef;
 577   Record *MemRec = MemInst->TheDef;
 578   unsigned MemOutSize = MemRec->getValueAsDag("OutOperandList")->getNumArgs();
 579   unsigned RegOutSize = RegRec->getValueAsDag("OutOperandList")->getNumArgs();
 580   unsigned MemInSize = MemRec->getValueAsDag("InOperandList")->getNumArgs();
 581   unsigned RegInSize = RegRec->getValueAsDag("InOperandList")->getNumArgs();
 582
 583   // Instructions which Read-Modify-Write should be added to Table2Addr.
 584   if (!MemOutSize && RegOutSize == 1 && MemInSize == RegInSize) {
 585     assert(!IsBroadcast && "Read-Modify-Write can not be broadcast");
 586     // X86 would not unfold Read-Modify-Write instructions so add TB_NO_REVERSE.
 587     addEntryWithFlags(Table2Addr, RegInst, MemInst, S | TB_NO_REVERSE, 0,
 588                       IsManual);
 589     return;
 590   }
 591
 592   if (MemInSize == RegInSize && MemOutSize == RegOutSize) {
 593     // Load-Folding cases.
 594     // If the i'th register form operand is a register and the i'th memory form
 595     // operand is a memory operand, add instructions to Table#i.
 596     for (unsigned I = RegOutSize, E = RegInst->Operands.size(); I < E; I++) {
 597       Record *RegOpRec = RegInst->Operands[I].Rec;
 598       Record *MemOpRec = MemInst->Operands[I].Rec;
 599       // PointerLikeRegClass: For instructions like TAILJMPr, TAILJMPr64,
 600       // TAILJMPr64_REX
 601       if ((isRegisterOperand(RegOpRec) ||
 602            RegOpRec->isSubClassOf("PointerLikeRegClass")) &&
 603           isMemoryOperand(MemOpRec)) {
 604         switch (I) {
 605         case 0:
 606           assert(!IsBroadcast && "BroadcastTable0 needs to be added");
 607           addEntryWithFlags(Table0, RegInst, MemInst, S, 0, IsManual);
 608           return;
 609         case 1:
 610           IsBroadcast
 611               ? addBroadcastEntry(BroadcastTable1, RegInst, MemInst)
 612               : addEntryWithFlags(Table1, RegInst, MemInst, S, 1, IsManual);
 613           return;
 614         case 2:
 615           IsBroadcast
 616               ? addBroadcastEntry(BroadcastTable2, RegInst, MemInst)
 617               : addEntryWithFlags(Table2, RegInst, MemInst, S, 2, IsManual);
 618           return;
 619         case 3:
 620           IsBroadcast
 621               ? addBroadcastEntry(BroadcastTable3, RegInst, MemInst)
 622               : addEntryWithFlags(Table3, RegInst, MemInst, S, 3, IsManual);
 623           return;
 624         case 4:
 625           IsBroadcast
 626               ? addBroadcastEntry(BroadcastTable4, RegInst, MemInst)
 627               : addEntryWithFlags(Table4, RegInst, MemInst, S, 4, IsManual);
 628           return;
 629         }
 630       }
 631     }
 632   } else if (MemInSize == RegInSize + 1 && MemOutSize + 1 == RegOutSize) {
 633     // Store-Folding cases.
 634     // If the memory form instruction performs a store, the *output*
 635     // register of the register form instructions disappear and instead a
 636     // memory *input* operand appears in the memory form instruction.
 637     // For example:
 638     //   MOVAPSrr => (outs VR128:$dst), (ins VR128:$src)
 639     //   MOVAPSmr => (outs), (ins f128mem:$dst, VR128:$src)
 640     Record *RegOpRec = RegInst->Operands[RegOutSize - 1].Rec;
 641     Record *MemOpRec = MemInst->Operands[RegOutSize - 1].Rec;
 642     if (isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec) &&
 643         getRegOperandSize(RegOpRec) == getMemOperandSize(MemOpRec)) {
 644       assert(!IsBroadcast && "Store can not be broadcast");
 645       addEntryWithFlags(Table0, RegInst, MemInst, S, 0, IsManual);
 646     }
 647   }
 648 }
 649
 650 void X86FoldTablesEmitter::run(raw_ostream &O) {
 651   formatted_raw_ostream OS(O);
 652
 653   // Holds all memory instructions
 654   std::vector<const CodeGenInstruction *> MemInsts;
 655   // Holds all register instructions - divided according to opcode.
 656   std::map<uint8_t, std::vector<const CodeGenInstruction *>> RegInsts;
 657
 658   ArrayRef<const CodeGenInstruction *> NumberedInstructions =
 659       Target.getInstructionsByEnumValue();
 660
 661   for (const CodeGenInstruction *Inst : NumberedInstructions) {
 662     const Record *Rec = Inst->TheDef;
 663     if (!Rec->isSubClassOf("X86Inst") || Rec->getValueAsBit("isAsmParserOnly"))
 664       continue;
 665
 666     if (NoFoldSet.find(Rec->getName()) != NoFoldSet.end())
 667       continue;
 668
 669     // - Instructions including RST register class operands are not relevant
 670     //   for memory folding (for further details check the explanation in
 671     //   lib/Target/X86/X86InstrFPStack.td file).
 672     // - Some instructions (listed in the manual map above) use the register
 673     //   class ptr_rc_tailcall, which can be of a size 32 or 64, to ensure
 674     //   safe mapping of these instruction we manually map them and exclude
 675     //   them from the automation.
 676     if (hasRSTRegClass(Inst) || hasPtrTailcallRegClass(Inst))
 677       continue;
 678
 679     // Add all the memory form instructions to MemInsts, and all the register
 680     // form instructions to RegInsts[Opc], where Opc is the opcode of each
 681     // instructions. this helps reducing the runtime of the backend.
 682     const BitsInit *FormBits = Rec->getValueAsBitsInit("FormBits");
 683     uint8_t Form = byteFromBitsInit(FormBits);
 684     if (mayFoldToForm(Form))
 685       MemInsts.push_back(Inst);
 686     else if (mayFoldFromForm(Form)) {
 687       uint8_t Opc = byteFromBitsInit(Rec->getValueAsBitsInit("Opcode"));
 688       RegInsts[Opc].push_back(Inst);
 689     }
 690   }
 691
 692   // Create a copy b/c the register instruction will removed when a new entry is
 693   // added into memory fold tables.
 694   auto RegInstsForBroadcast = RegInsts;
 695
 696   Record *AsmWriter = Target.getAsmWriter();
 697   unsigned Variant = AsmWriter->getValueAsInt("Variant");
 698   auto FixUp = [&](const CodeGenInstruction *RegInst) {
 699     StringRef RegInstName = RegInst->TheDef->getName();
 700     if (RegInstName.ends_with("_REV") || RegInstName.ends_with("_alt"))
 701       if (auto *RegAltRec = Records.getDef(RegInstName.drop_back(4)))
 702         RegInst = &Target.getInstruction(RegAltRec);
 703     return RegInst;
 704   };
 705   // For each memory form instruction, try to find its register form
 706   // instruction.
 707   for (const CodeGenInstruction *MemInst : MemInsts) {
 708     uint8_t Opc =
 709         byteFromBitsInit(MemInst->TheDef->getValueAsBitsInit("Opcode"));
 710
 711     auto RegInstsIt = RegInsts.find(Opc);
 712     if (RegInstsIt == RegInsts.end())
 713       continue;
 714
 715     // Two forms (memory & register) of the same instruction must have the same
 716     // opcode.
 717     std::vector<const CodeGenInstruction *> &OpcRegInsts = RegInstsIt->second;
 718
 719     // Memory fold tables
 720     auto Match =
 721         find_if(OpcRegInsts, IsMatch(MemInst, /*IsBroadcast=*/false, Variant));
 722     if (Match != OpcRegInsts.end()) {
 723       updateTables(FixUp(*Match), MemInst);
 724       OpcRegInsts.erase(Match);
 725     }
 726
 727     // Broadcast tables
 728     StringRef MemInstName = MemInst->TheDef->getName();
 729     if (!MemInstName.contains("mb") && !MemInstName.contains("mib"))
 730       continue;
 731     RegInstsIt = RegInstsForBroadcast.find(Opc);
 732     assert(RegInstsIt != RegInstsForBroadcast.end() &&
 733            "Unexpected control flow");
 734     std::vector<const CodeGenInstruction *> &OpcRegInstsForBroadcast =
 735         RegInstsIt->second;
 736     Match = find_if(OpcRegInstsForBroadcast,
 737                     IsMatch(MemInst, /*IsBroadcast=*/true, Variant));
 738     if (Match != OpcRegInstsForBroadcast.end()) {
 739       updateTables(FixUp(*Match), MemInst, 0, /*IsManual=*/false,
 740                    /*IsBroadcast=*/true);
 741       OpcRegInstsForBroadcast.erase(Match);
 742     }
 743   }
 744
 745   // Add the manually mapped instructions listed above.
 746   for (const ManualMapEntry &Entry : ManualMapSet) {
 747     Record *RegInstIter = Records.getDef(Entry.RegInstStr);
 748     Record *MemInstIter = Records.getDef(Entry.MemInstStr);
 749
 750     updateTables(&(Target.getInstruction(RegInstIter)),
 751                  &(Target.getInstruction(MemInstIter)), Entry.Strategy, true);
 752   }
 753
 754 #ifndef NDEBUG
 755   auto CheckMemFoldTable = [](const FoldTable &Table) -> void {
 756     for (const auto &Record : Table) {
 757       auto &FoldEntry = Record.second;
 758       FoldEntry.checkCorrectness();
 759     }
 760   };
 761   CheckMemFoldTable(Table2Addr);
 762   CheckMemFoldTable(Table0);
 763   CheckMemFoldTable(Table1);
 764   CheckMemFoldTable(Table2);
 765   CheckMemFoldTable(Table3);
 766   CheckMemFoldTable(Table4);
 767   CheckMemFoldTable(BroadcastTable1);
 768   CheckMemFoldTable(BroadcastTable2);
 769   CheckMemFoldTable(BroadcastTable3);
 770   CheckMemFoldTable(BroadcastTable4);
 771 #endif
 772 #define PRINT_TABLE(TABLE) printTable(TABLE, #TABLE, OS);
 773   // Print all tables.
 774   PRINT_TABLE(Table2Addr)
 775   PRINT_TABLE(Table0)
 776   PRINT_TABLE(Table1)
 777   PRINT_TABLE(Table2)
 778   PRINT_TABLE(Table3)
 779   PRINT_TABLE(Table4)
 780   PRINT_TABLE(BroadcastTable1)
 781   PRINT_TABLE(BroadcastTable2)
 782   PRINT_TABLE(BroadcastTable3)
 783   PRINT_TABLE(BroadcastTable4)
 784 }
 785
 786 static TableGen::Emitter::OptClass<X86FoldTablesEmitter>
 787     X("gen-x86-fold-tables", "Generate X86 fold tables");