contrib/llvm/utils/TableGen/X86FoldTablesEmitter.cpp

   1 //===- utils/TableGen/X86FoldTablesEmitter.cpp - X86 backend-*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This tablegen backend is responsible for emitting the memory fold tables of
  11 // the X86 backend instructions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "CodeGenDAGPatterns.h"
  16 #include "CodeGenTarget.h"
  17 #include "X86RecognizableInstr.h"
  18 #include "llvm/TableGen/Error.h"
  19 #include "llvm/TableGen/TableGenBackend.h"
  20
  21 using namespace llvm;
  22
  23 namespace {
  24
  25 // 3 possible strategies for the unfolding flag (TB_NO_REVERSE) of the
  26 // manual added entries.
  27 enum UnfoldStrategy {
  28   UNFOLD,     // Allow unfolding
  29   NO_UNFOLD,  // Prevent unfolding
  30   NO_STRATEGY // Make decision according to operands' sizes
  31 };
  32
  33 // Represents an entry in the manual mapped instructions set.
  34 struct ManualMapEntry {
  35   const char *RegInstStr;
  36   const char *MemInstStr;
  37   UnfoldStrategy Strategy;
  38
  39   ManualMapEntry(const char *RegInstStr, const char *MemInstStr,
  40                  UnfoldStrategy Strategy = NO_STRATEGY)
  41       : RegInstStr(RegInstStr), MemInstStr(MemInstStr), Strategy(Strategy) {}
  42 };
  43
  44 class IsMatch;
  45
  46 // List of instructions requiring explicitly aligned memory.
  47 const char *const ExplicitAlign[] = {"MOVDQA",  "MOVAPS",  "MOVAPD",  "MOVNTPS",
  48                                      "MOVNTPD", "MOVNTDQ", "MOVNTDQA"};
  49
  50 // List of instructions NOT requiring explicit memory alignment.
  51 const char *const ExplicitUnalign[] = {"MOVDQU", "MOVUPS", "MOVUPD"};
  52
  53 // For manually mapping instructions that do not match by their encoding.
  54 const ManualMapEntry ManualMapSet[] = {
  55     { "ADD16ri_DB",       "ADD16mi",         NO_UNFOLD  },
  56     { "ADD16ri8_DB",      "ADD16mi8",        NO_UNFOLD  },
  57     { "ADD16rr_DB",       "ADD16mr",         NO_UNFOLD  },
  58     { "ADD32ri_DB",       "ADD32mi",         NO_UNFOLD  },
  59     { "ADD32ri8_DB",      "ADD32mi8",        NO_UNFOLD  },
  60     { "ADD32rr_DB",       "ADD32mr",         NO_UNFOLD  },
  61     { "ADD64ri32_DB",     "ADD64mi32",       NO_UNFOLD  },
  62     { "ADD64ri8_DB",      "ADD64mi8",        NO_UNFOLD  },
  63     { "ADD64rr_DB",       "ADD64mr",         NO_UNFOLD  },
  64     { "ADD16rr_DB",       "ADD16rm",         NO_UNFOLD  },
  65     { "ADD32rr_DB",       "ADD32rm",         NO_UNFOLD  },
  66     { "ADD64rr_DB",       "ADD64rm",         NO_UNFOLD  },
  67     { "PUSH16r",          "PUSH16rmm",       NO_UNFOLD  },
  68     { "PUSH32r",          "PUSH32rmm",       NO_UNFOLD  },
  69     { "PUSH64r",          "PUSH64rmm",       NO_UNFOLD  },
  70     { "TAILJMPr",         "TAILJMPm",        UNFOLD },
  71     { "TAILJMPr64",       "TAILJMPm64",      UNFOLD },
  72     { "TAILJMPr64_REX",   "TAILJMPm64_REX",  UNFOLD },
  73 };
  74
  75 // Do not add these instructions to any of the folding tables.
  76 const char *const NoFoldSet[] = {
  77     "TCRETURNri64",
  78     "TCRETURNmi64", // Special dealing (in X86InstrCompiler.td under
  79     "TCRETURNri",   // "tailcall stuff" section).
  80     "TCRETURNmi",
  81
  82     // Never fold XCHG, the register and memory forms have different locking
  83     // semantics.
  84     "XCHG8rr",  "XCHG8rm",
  85     "XCHG16rr", "XCHG16rm",
  86     "XCHG32rr", "XCHG32rm",
  87     "XCHG64rr", "XCHG64rm",
  88
  89     // Different calculations of the folded operand between
  90     // memory and register forms (folding is illegal).
  91     // - In their register form, the second register operand's relevant
  92     //   bits are only the first 4/5/6 (depending on mode and reg size).
  93     // - In their memory form, the second register operand's relevant
  94     //   bits are only the first 16/32/64 (depending on mode and reg size).
  95     "BT16rr",  "BT32rr",  "BT64rr",
  96     "BT16mr",  "BT32mr",  "BT64mr",
  97     "BTC16rr", "BTC32rr", "BTC64rr",
  98     "BTC16mr", "BTC32mr", "BTC64mr",
  99     "BTR16rr", "BTR32rr", "BTR64rr",
 100     "BTR16mr", "BTR32mr", "BTR64mr",
 101     "BTS16rr", "BTS32rr", "BTS64rr",
 102     "BTS16mr", "BTS32mr", "BTS64mr",
 103
 104     // Memory folding is enabled only when optimizing for size by DAG
 105     // patterns only. (issue detailed in D28744 review)
 106     "VCVTSS2SDrm",            "VCVTSS2SDrr",
 107     "VCVTSS2SDZrm",           "VCVTSS2SDZrr",
 108     "VCVTSS2SDZrmk",          "VCVTSS2SDZrrk",
 109     "VCVTSS2SDZrmkz",         "VCVTSS2SDZrrkz",
 110     "VCVTSS2SDZrm_Int",       "VCVTSS2SDZrr_Int",
 111     "VCVTSS2SDZrm_Intk",      "VCVTSS2SDZrr_Intk",
 112     "VCVTSS2SDZrm_Intkz",     "VCVTSS2SDZrr_Intkz",
 113     "VCVTSD2SSrm",            "VCVTSD2SSrr",
 114     "VCVTSD2SSZrm",           "VCVTSD2SSZrr",
 115     "VCVTSD2SSZrmk",          "VCVTSD2SSZrrk",
 116     "VCVTSD2SSZrmkz",         "VCVTSD2SSZrrkz",
 117     "VCVTSD2SSZrm_Int",       "VCVTSD2SSZrr_Int",
 118     "VCVTSD2SSZrm_Intk",      "VCVTSD2SSZrr_Intk",
 119     "VCVTSD2SSZrm_Intkz",     "VCVTSD2SSZrr_Intkz",
 120     "VRCP14SSrm",             "VRCP14SSrr",
 121     "VRCP14SDrm",             "VRCP14SDrr",
 122     "VRSQRT14SSrm",           "VRSQRT14SSrr",
 123     "VRSQRT14SDrm",           "VRSQRT14SDrr",
 124     "VSQRTSSm",               "VSQRTSSr",
 125     "VSQRTSSm_Int",           "VSQRTSSr_Int",
 126     "VSQRTSSZm",              "VSQRTSSZr",
 127     "VSQRTSSZm_Int",          "VSQRTSSZr_Int",
 128     "VSQRTSSZm_Intk",         "VSQRTSSZr_Intk",
 129     "VSQRTSSZm_Intkz",        "VSQRTSSZr_Intkz",
 130     "VSQRTSDm",               "VSQRTSDr",
 131     "VSQRTSDm_Int",           "VSQRTSDr_Int",
 132     "VSQRTSDZm",              "VSQRTSDZr",
 133     "VSQRTSDZm_Int",          "VSQRTSDZr_Int",
 134     "VSQRTSDZm_Intk",         "VSQRTSDZr_Intk",
 135     "VSQRTSDZm_Intkz",        "VSQRTSDZr_Intkz",
 136 };
 137
 138 static bool isExplicitAlign(const CodeGenInstruction *Inst) {
 139   return any_of(ExplicitAlign, [Inst](const char *InstStr) {
 140     return Inst->TheDef->getName().find(InstStr) != StringRef::npos;
 141   });
 142 }
 143
 144 static bool isExplicitUnalign(const CodeGenInstruction *Inst) {
 145   return any_of(ExplicitUnalign, [Inst](const char *InstStr) {
 146     return Inst->TheDef->getName().find(InstStr) != StringRef::npos;
 147   });
 148 }
 149
 150 class X86FoldTablesEmitter {
 151   RecordKeeper &Records;
 152   CodeGenTarget Target;
 153
 154   // Represents an entry in the folding table
 155   class X86FoldTableEntry {
 156     const CodeGenInstruction *RegInst;
 157     const CodeGenInstruction *MemInst;
 158
 159   public:
 160     bool CannotUnfold = false;
 161     bool IsLoad = false;
 162     bool IsStore = false;
 163     bool IsAligned = false;
 164     unsigned int Alignment = 0;
 165
 166     X86FoldTableEntry(const CodeGenInstruction *RegInst,
 167                       const CodeGenInstruction *MemInst)
 168         : RegInst(RegInst), MemInst(MemInst) {}
 169
 170     friend raw_ostream &operator<<(raw_ostream &OS,
 171                                    const X86FoldTableEntry &E) {
 172       OS << "{ X86::" << E.RegInst->TheDef->getName()
 173          << ", X86::" << E.MemInst->TheDef->getName() << ", ";
 174
 175       if (E.IsLoad)
 176         OS << "TB_FOLDED_LOAD | ";
 177       if (E.IsStore)
 178         OS << "TB_FOLDED_STORE | ";
 179       if (E.CannotUnfold)
 180         OS << "TB_NO_REVERSE | ";
 181       if (E.IsAligned)
 182         OS << "TB_ALIGN_" << E.Alignment << " | ";
 183
 184       OS << "0 },\n";
 185
 186       return OS;
 187     }
 188   };
 189
 190   typedef std::vector<X86FoldTableEntry> FoldTable;
 191   // std::vector for each folding table.
 192   // Table2Addr - Holds instructions which their memory form performs load+store
 193   // Table#i - Holds instructions which the their memory form perform a load OR
 194   //           a store,  and their #i'th operand is folded.
 195   FoldTable Table2Addr;
 196   FoldTable Table0;
 197   FoldTable Table1;
 198   FoldTable Table2;
 199   FoldTable Table3;
 200   FoldTable Table4;
 201
 202 public:
 203   X86FoldTablesEmitter(RecordKeeper &R) : Records(R), Target(R) {}
 204
 205   // run - Generate the 6 X86 memory fold tables.
 206   void run(raw_ostream &OS);
 207
 208 private:
 209   // Decides to which table to add the entry with the given instructions.
 210   // S sets the strategy of adding the TB_NO_REVERSE flag.
 211   void updateTables(const CodeGenInstruction *RegInstr,
 212                     const CodeGenInstruction *MemInstr,
 213                     const UnfoldStrategy S = NO_STRATEGY);
 214
 215   // Generates X86FoldTableEntry with the given instructions and fill it with
 216   // the appropriate flags - then adds it to Table.
 217   void addEntryWithFlags(FoldTable &Table, const CodeGenInstruction *RegInstr,
 218                          const CodeGenInstruction *MemInstr,
 219                          const UnfoldStrategy S, const unsigned int FoldedInd);
 220
 221   // Print the given table as a static const C++ array of type
 222   // X86MemoryFoldTableEntry.
 223   void printTable(const FoldTable &Table, std::string TableName,
 224                   raw_ostream &OS) {
 225     OS << "\nstatic const X86MemoryFoldTableEntry MemoryFold" << TableName
 226        << "[] = {\n";
 227
 228     for (const X86FoldTableEntry &E : Table)
 229       OS.indent(2) << E;
 230
 231     OS << "};\n";
 232   }
 233 };
 234
 235 // Return true if one of the instruction's operands is a RST register class
 236 static bool hasRSTRegClass(const CodeGenInstruction *Inst) {
 237   return any_of(Inst->Operands, [](const CGIOperandList::OperandInfo &OpIn) {
 238     return OpIn.Rec->getName() == "RST";
 239   });
 240 }
 241
 242 // Return true if one of the instruction's operands is a ptr_rc_tailcall
 243 static bool hasPtrTailcallRegClass(const CodeGenInstruction *Inst) {
 244   return any_of(Inst->Operands, [](const CGIOperandList::OperandInfo &OpIn) {
 245     return OpIn.Rec->getName() == "ptr_rc_tailcall";
 246   });
 247 }
 248
 249 // Calculates the integer value representing the BitsInit object
 250 static inline uint64_t getValueFromBitsInit(const BitsInit *B) {
 251   assert(B->getNumBits() <= sizeof(uint64_t) * CHAR_BIT &&
 252          "BitInits' too long!");
 253
 254   uint64_t Value = 0;
 255   for (unsigned i = 0, e = B->getNumBits(); i != e; ++i) {
 256     BitInit *Bit = cast<BitInit>(B->getBit(i));
 257     Value |= uint64_t(Bit->getValue()) << i;
 258   }
 259   return Value;
 260 }
 261
 262 // Returns true if the two given BitsInits represent the same integer value
 263 static inline bool equalBitsInits(const BitsInit *B1, const BitsInit *B2) {
 264   if (B1->getNumBits() != B2->getNumBits())
 265     PrintFatalError("Comparing two BitsInits with different sizes!");
 266
 267   for (unsigned i = 0, e = B1->getNumBits(); i != e; ++i) {
 268     BitInit *Bit1 = cast<BitInit>(B1->getBit(i));
 269     BitInit *Bit2 = cast<BitInit>(B2->getBit(i));
 270     if (Bit1->getValue() != Bit2->getValue())
 271       return false;
 272   }
 273   return true;
 274 }
 275
 276 // Return the size of the register operand
 277 static inline unsigned int getRegOperandSize(const Record *RegRec) {
 278   if (RegRec->isSubClassOf("RegisterOperand"))
 279     RegRec = RegRec->getValueAsDef("RegClass");
 280   if (RegRec->isSubClassOf("RegisterClass"))
 281     return RegRec->getValueAsListOfDefs("RegTypes")[0]->getValueAsInt("Size");
 282
 283   llvm_unreachable("Register operand's size not known!");
 284 }
 285
 286 // Return the size of the memory operand
 287 static inline unsigned int
 288 getMemOperandSize(const Record *MemRec, const bool IntrinsicSensitive = false) {
 289   if (MemRec->isSubClassOf("Operand")) {
 290     // Intrinsic memory instructions use ssmem/sdmem.
 291     if (IntrinsicSensitive &&
 292         (MemRec->getName() == "sdmem" || MemRec->getName() == "ssmem"))
 293       return 128;
 294
 295     std::string Name =
 296         MemRec->getValueAsDef("ParserMatchClass")->getValueAsString("Name");
 297     if (Name == "Mem8")
 298       return 8;
 299     if (Name == "Mem16")
 300       return 16;
 301     if (Name == "Mem32")
 302       return 32;
 303     if (Name == "Mem64")
 304       return 64;
 305     if (Name == "Mem80")
 306       return 80;
 307     if (Name == "Mem128")
 308       return 128;
 309     if (Name == "Mem256")
 310       return 256;
 311     if (Name == "Mem512")
 312       return 512;
 313   }
 314
 315   llvm_unreachable("Memory operand's size not known!");
 316 }
 317
 318 // Returns true if the record's list of defs includes the given def.
 319 static inline bool hasDefInList(const Record *Rec, const StringRef List,
 320                                 const StringRef Def) {
 321   if (!Rec->isValueUnset(List)) {
 322     return any_of(*(Rec->getValueAsListInit(List)),
 323                   [Def](const Init *I) { return I->getAsString() == Def; });
 324   }
 325   return false;
 326 }
 327
 328 // Return true if the instruction defined as a register flavor.
 329 static inline bool hasRegisterFormat(const Record *Inst) {
 330   const BitsInit *FormBits = Inst->getValueAsBitsInit("FormBits");
 331   uint64_t FormBitsNum = getValueFromBitsInit(FormBits);
 332
 333   // Values from X86Local namespace defined in X86RecognizableInstr.cpp
 334   return FormBitsNum >= X86Local::MRMDestReg && FormBitsNum <= X86Local::MRM7r;
 335 }
 336
 337 // Return true if the instruction defined as a memory flavor.
 338 static inline bool hasMemoryFormat(const Record *Inst) {
 339   const BitsInit *FormBits = Inst->getValueAsBitsInit("FormBits");
 340   uint64_t FormBitsNum = getValueFromBitsInit(FormBits);
 341
 342   // Values from X86Local namespace defined in X86RecognizableInstr.cpp
 343   return FormBitsNum >= X86Local::MRMDestMem && FormBitsNum <= X86Local::MRM7m;
 344 }
 345
 346 static inline bool isNOREXRegClass(const Record *Op) {
 347   return Op->getName().find("_NOREX") != StringRef::npos;
 348 }
 349
 350 static inline bool isRegisterOperand(const Record *Rec) {
 351   return Rec->isSubClassOf("RegisterClass") ||
 352          Rec->isSubClassOf("RegisterOperand") ||
 353          Rec->isSubClassOf("PointerLikeRegClass");
 354 }
 355
 356 static inline bool isMemoryOperand(const Record *Rec) {
 357   return Rec->isSubClassOf("Operand") &&
 358          Rec->getValueAsString("OperandType") == "OPERAND_MEMORY";
 359 }
 360
 361 static inline bool isImmediateOperand(const Record *Rec) {
 362   return Rec->isSubClassOf("Operand") &&
 363          Rec->getValueAsString("OperandType") == "OPERAND_IMMEDIATE";
 364 }
 365
 366 // Get the alternative instruction pointed by "FoldGenRegForm" field.
 367 static inline const CodeGenInstruction *
 368 getAltRegInst(const CodeGenInstruction *I, const RecordKeeper &Records,
 369               const CodeGenTarget &Target) {
 370
 371   std::string AltRegInstStr = I->TheDef->getValueAsString("FoldGenRegForm");
 372   Record *AltRegInstRec = Records.getDef(AltRegInstStr);
 373   assert(AltRegInstRec &&
 374          "Alternative register form instruction def not found");
 375   CodeGenInstruction &AltRegInst = Target.getInstruction(AltRegInstRec);
 376   return &AltRegInst;
 377 }
 378
 379 // Function object - Operator() returns true if the given VEX instruction
 380 // matches the EVEX instruction of this object.
 381 class IsMatch {
 382   const CodeGenInstruction *MemInst;
 383   const RecordKeeper &Records;
 384
 385 public:
 386   IsMatch(const CodeGenInstruction *Inst, const RecordKeeper &Records)
 387       : MemInst(Inst), Records(Records) {}
 388
 389   bool operator()(const CodeGenInstruction *RegInst) {
 390     Record *MemRec = MemInst->TheDef;
 391     Record *RegRec = RegInst->TheDef;
 392
 393     // Return false if one (at least) of the encoding fields of both
 394     // instructions do not match.
 395     if (RegRec->getValueAsDef("OpEnc") != MemRec->getValueAsDef("OpEnc") ||
 396         !equalBitsInits(RegRec->getValueAsBitsInit("Opcode"),
 397                         MemRec->getValueAsBitsInit("Opcode")) ||
 398         // VEX/EVEX fields
 399         RegRec->getValueAsDef("OpPrefix") !=
 400             MemRec->getValueAsDef("OpPrefix") ||
 401         RegRec->getValueAsDef("OpMap") != MemRec->getValueAsDef("OpMap") ||
 402         RegRec->getValueAsDef("OpSize") != MemRec->getValueAsDef("OpSize") ||
 403         RegRec->getValueAsBit("hasVEX_4V") !=
 404             MemRec->getValueAsBit("hasVEX_4V") ||
 405         RegRec->getValueAsBit("hasEVEX_K") !=
 406             MemRec->getValueAsBit("hasEVEX_K") ||
 407         RegRec->getValueAsBit("hasEVEX_Z") !=
 408             MemRec->getValueAsBit("hasEVEX_Z") ||
 409         RegRec->getValueAsBit("hasEVEX_B") !=
 410             MemRec->getValueAsBit("hasEVEX_B") ||
 411         RegRec->getValueAsBit("hasEVEX_RC") !=
 412             MemRec->getValueAsBit("hasEVEX_RC") ||
 413         RegRec->getValueAsBit("hasREX_WPrefix") !=
 414             MemRec->getValueAsBit("hasREX_WPrefix") ||
 415         RegRec->getValueAsBit("hasLockPrefix") !=
 416             MemRec->getValueAsBit("hasLockPrefix") ||
 417         !equalBitsInits(RegRec->getValueAsBitsInit("EVEX_LL"),
 418                         MemRec->getValueAsBitsInit("EVEX_LL")) ||
 419         !equalBitsInits(RegRec->getValueAsBitsInit("VEX_WPrefix"),
 420                         MemRec->getValueAsBitsInit("VEX_WPrefix")) ||
 421         // Instruction's format - The register form's "Form" field should be
 422         // the opposite of the memory form's "Form" field.
 423         !areOppositeForms(RegRec->getValueAsBitsInit("FormBits"),
 424                           MemRec->getValueAsBitsInit("FormBits")) ||
 425         RegRec->getValueAsBit("isAsmParserOnly") !=
 426             MemRec->getValueAsBit("isAsmParserOnly"))
 427       return false;
 428
 429     // Make sure the sizes of the operands of both instructions suit each other.
 430     // This is needed for instructions with intrinsic version (_Int).
 431     // Where the only difference is the size of the operands.
 432     // For example: VUCOMISDZrm and Int_VUCOMISDrm
 433     // Also for instructions that their EVEX version was upgraded to work with
 434     // k-registers. For example VPCMPEQBrm (xmm output register) and
 435     // VPCMPEQBZ128rm (k register output register).
 436     bool ArgFolded = false;
 437     unsigned MemOutSize = MemRec->getValueAsDag("OutOperandList")->getNumArgs();
 438     unsigned RegOutSize = RegRec->getValueAsDag("OutOperandList")->getNumArgs();
 439     unsigned MemInSize = MemRec->getValueAsDag("InOperandList")->getNumArgs();
 440     unsigned RegInSize = RegRec->getValueAsDag("InOperandList")->getNumArgs();
 441
 442     // Instructions with one output in their memory form use the memory folded
 443     // operand as source and destination (Read-Modify-Write).
 444     unsigned RegStartIdx =
 445         (MemOutSize + 1 == RegOutSize) && (MemInSize == RegInSize) ? 1 : 0;
 446
 447     for (unsigned i = 0, e = MemInst->Operands.size(); i < e; i++) {
 448       Record *MemOpRec = MemInst->Operands[i].Rec;
 449       Record *RegOpRec = RegInst->Operands[i + RegStartIdx].Rec;
 450
 451       if (MemOpRec == RegOpRec)
 452         continue;
 453
 454       if (isRegisterOperand(MemOpRec) && isRegisterOperand(RegOpRec)) {
 455         if (getRegOperandSize(MemOpRec) != getRegOperandSize(RegOpRec) ||
 456             isNOREXRegClass(MemOpRec) != isNOREXRegClass(RegOpRec))
 457           return false;
 458       } else if (isMemoryOperand(MemOpRec) && isMemoryOperand(RegOpRec)) {
 459         if (getMemOperandSize(MemOpRec) != getMemOperandSize(RegOpRec))
 460           return false;
 461       } else if (isImmediateOperand(MemOpRec) && isImmediateOperand(RegOpRec)) {
 462         if (MemOpRec->getValueAsDef("Type") != RegOpRec->getValueAsDef("Type"))
 463           return false;
 464       } else {
 465         // Only one operand can be folded.
 466         if (ArgFolded)
 467           return false;
 468
 469         assert(isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec));
 470         ArgFolded = true;
 471       }
 472     }
 473
 474     return true;
 475   }
 476
 477 private:
 478   // Return true of the 2 given forms are the opposite of each other.
 479   bool areOppositeForms(const BitsInit *RegFormBits,
 480                         const BitsInit *MemFormBits) {
 481     uint64_t MemFormNum = getValueFromBitsInit(MemFormBits);
 482     uint64_t RegFormNum = getValueFromBitsInit(RegFormBits);
 483
 484     if ((MemFormNum == X86Local::MRM0m && RegFormNum == X86Local::MRM0r) ||
 485         (MemFormNum == X86Local::MRM1m && RegFormNum == X86Local::MRM1r) ||
 486         (MemFormNum == X86Local::MRM2m && RegFormNum == X86Local::MRM2r) ||
 487         (MemFormNum == X86Local::MRM3m && RegFormNum == X86Local::MRM3r) ||
 488         (MemFormNum == X86Local::MRM4m && RegFormNum == X86Local::MRM4r) ||
 489         (MemFormNum == X86Local::MRM5m && RegFormNum == X86Local::MRM5r) ||
 490         (MemFormNum == X86Local::MRM6m && RegFormNum == X86Local::MRM6r) ||
 491         (MemFormNum == X86Local::MRM7m && RegFormNum == X86Local::MRM7r) ||
 492         (MemFormNum == X86Local::MRMXm && RegFormNum == X86Local::MRMXr) ||
 493         (MemFormNum == X86Local::MRMDestMem &&
 494          RegFormNum == X86Local::MRMDestReg) ||
 495         (MemFormNum == X86Local::MRMSrcMem &&
 496          RegFormNum == X86Local::MRMSrcReg) ||
 497         (MemFormNum == X86Local::MRMSrcMem4VOp3 &&
 498          RegFormNum == X86Local::MRMSrcReg4VOp3) ||
 499         (MemFormNum == X86Local::MRMSrcMemOp4 &&
 500          RegFormNum == X86Local::MRMSrcRegOp4))
 501       return true;
 502
 503     return false;
 504   }
 505 };
 506
 507 } // end anonymous namespace
 508
 509 void X86FoldTablesEmitter::addEntryWithFlags(FoldTable &Table,
 510                                              const CodeGenInstruction *RegInstr,
 511                                              const CodeGenInstruction *MemInstr,
 512                                              const UnfoldStrategy S,
 513                                              const unsigned int FoldedInd) {
 514
 515   X86FoldTableEntry Result = X86FoldTableEntry(RegInstr, MemInstr);
 516   Record *RegRec = RegInstr->TheDef;
 517   Record *MemRec = MemInstr->TheDef;
 518
 519   // Only table0 entries should explicitly specify a load or store flag.
 520   if (&Table == &Table0) {
 521     unsigned MemInOpsNum = MemRec->getValueAsDag("InOperandList")->getNumArgs();
 522     unsigned RegInOpsNum = RegRec->getValueAsDag("InOperandList")->getNumArgs();
 523     // If the instruction writes to the folded operand, it will appear as an
 524     // output in the register form instruction and as an input in the memory
 525     // form instruction.
 526     // If the instruction reads from the folded operand, it well appear as in
 527     // input in both forms.
 528     if (MemInOpsNum == RegInOpsNum)
 529       Result.IsLoad = true;
 530     else
 531       Result.IsStore = true;
 532   }
 533
 534   Record *RegOpRec = RegInstr->Operands[FoldedInd].Rec;
 535   Record *MemOpRec = MemInstr->Operands[FoldedInd].Rec;
 536
 537   // Unfolding code generates a load/store instruction according to the size of
 538   // the register in the register form instruction.
 539   // If the register's size is greater than the memory's operand size, do not
 540   // allow unfolding.
 541   if (S == UNFOLD)
 542     Result.CannotUnfold = false;
 543   else if (S == NO_UNFOLD)
 544     Result.CannotUnfold = true;
 545   else if (getRegOperandSize(RegOpRec) > getMemOperandSize(MemOpRec))
 546     Result.CannotUnfold = true; // S == NO_STRATEGY
 547
 548   uint64_t Enc = getValueFromBitsInit(RegRec->getValueAsBitsInit("OpEncBits"));
 549   if (isExplicitAlign(RegInstr)) {
 550     // The instruction require explicitly aligned memory.
 551     BitsInit *VectSize = RegRec->getValueAsBitsInit("VectSize");
 552     uint64_t Value = getValueFromBitsInit(VectSize);
 553     Result.IsAligned = true;
 554     Result.Alignment = Value;
 555   } else if (Enc != X86Local::XOP && Enc != X86Local::VEX &&
 556              Enc != X86Local::EVEX) {
 557     // Instructions with VEX encoding do not require alignment.
 558     if (!isExplicitUnalign(RegInstr) && getMemOperandSize(MemOpRec) > 64) {
 559       // SSE packed vector instructions require a 16 byte alignment.
 560       Result.IsAligned = true;
 561       Result.Alignment = 16;
 562     }
 563   }
 564
 565   Table.push_back(Result);
 566 }
 567
 568 void X86FoldTablesEmitter::updateTables(const CodeGenInstruction *RegInstr,
 569                                         const CodeGenInstruction *MemInstr,
 570                                         const UnfoldStrategy S) {
 571
 572   Record *RegRec = RegInstr->TheDef;
 573   Record *MemRec = MemInstr->TheDef;
 574   unsigned MemOutSize = MemRec->getValueAsDag("OutOperandList")->getNumArgs();
 575   unsigned RegOutSize = RegRec->getValueAsDag("OutOperandList")->getNumArgs();
 576   unsigned MemInSize = MemRec->getValueAsDag("InOperandList")->getNumArgs();
 577   unsigned RegInSize = RegRec->getValueAsDag("InOperandList")->getNumArgs();
 578
 579   // Instructions which have the WriteRMW value (Read-Modify-Write) should be
 580   // added to Table2Addr.
 581   if (hasDefInList(MemRec, "SchedRW", "WriteRMW") && MemOutSize != RegOutSize &&
 582       MemInSize == RegInSize) {
 583     addEntryWithFlags(Table2Addr, RegInstr, MemInstr, S, 0);
 584     return;
 585   }
 586
 587   if (MemInSize == RegInSize && MemOutSize == RegOutSize) {
 588     // Load-Folding cases.
 589     // If the i'th register form operand is a register and the i'th memory form
 590     // operand is a memory operand, add instructions to Table#i.
 591     for (unsigned i = RegOutSize, e = RegInstr->Operands.size(); i < e; i++) {
 592       Record *RegOpRec = RegInstr->Operands[i].Rec;
 593       Record *MemOpRec = MemInstr->Operands[i].Rec;
 594       if (isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec)) {
 595         switch (i) {
 596         default: llvm_unreachable("Unexpected operand count!");
 597         case 0:
 598           addEntryWithFlags(Table0, RegInstr, MemInstr, S, 0);
 599           return;
 600         case 1:
 601           addEntryWithFlags(Table1, RegInstr, MemInstr, S, 1);
 602           return;
 603         case 2:
 604           addEntryWithFlags(Table2, RegInstr, MemInstr, S, 2);
 605           return;
 606         case 3:
 607           addEntryWithFlags(Table3, RegInstr, MemInstr, S, 3);
 608           return;
 609         case 4:
 610           addEntryWithFlags(Table4, RegInstr, MemInstr, S, 4);
 611           return;
 612         }
 613       }
 614     }
 615   } else if (MemInSize == RegInSize + 1 && MemOutSize + 1 == RegOutSize) {
 616     // Store-Folding cases.
 617     // If the memory form instruction performs performs a store, the *output*
 618     // register of the register form instructions disappear and instead a
 619     // memory *input* operand appears in the memory form instruction.
 620     // For example:
 621     //   MOVAPSrr => (outs VR128:$dst), (ins VR128:$src)
 622     //   MOVAPSmr => (outs), (ins f128mem:$dst, VR128:$src)
 623     Record *RegOpRec = RegInstr->Operands[RegOutSize - 1].Rec;
 624     Record *MemOpRec = MemInstr->Operands[RegOutSize - 1].Rec;
 625     if (isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec))
 626       addEntryWithFlags(Table0, RegInstr, MemInstr, S, 0);
 627   }
 628
 629   return;
 630 }
 631
 632 void X86FoldTablesEmitter::run(raw_ostream &OS) {
 633   emitSourceFileHeader("X86 fold tables", OS);
 634
 635   // Holds all memory instructions
 636   std::vector<const CodeGenInstruction *> MemInsts;
 637   // Holds all register instructions - divided according to opcode.
 638   std::map<uint8_t, std::vector<const CodeGenInstruction *>> RegInsts;
 639
 640   ArrayRef<const CodeGenInstruction *> NumberedInstructions =
 641       Target.getInstructionsByEnumValue();
 642
 643   for (const CodeGenInstruction *Inst : NumberedInstructions) {
 644     if (!Inst->TheDef->getNameInit() || !Inst->TheDef->isSubClassOf("X86Inst"))
 645       continue;
 646
 647     const Record *Rec = Inst->TheDef;
 648
 649     // - Do not proceed matching if the instruction in NoFoldSet.
 650     // - Instructions including RST register class operands are not relevant
 651     //   for memory folding (for further details check the explanation in
 652     //   lib/Target/X86/X86InstrFPStack.td file).
 653     // - Some instructions (listed in the manual map above) use the register
 654     //   class ptr_rc_tailcall, which can be of a size 32 or 64, to ensure
 655     //   safe mapping of these instruction we manually map them and exclude
 656     //   them from the automation.
 657     if (find(NoFoldSet, Rec->getName()) != std::end(NoFoldSet) ||
 658         hasRSTRegClass(Inst) || hasPtrTailcallRegClass(Inst))
 659       continue;
 660
 661     // Add all the memory form instructions to MemInsts, and all the register
 662     // form instructions to RegInsts[Opc], where Opc in the opcode of each
 663     // instructions. this helps reducing the runtime of the backend.
 664     if (hasMemoryFormat(Rec))
 665       MemInsts.push_back(Inst);
 666     else if (hasRegisterFormat(Rec)) {
 667       uint8_t Opc = getValueFromBitsInit(Rec->getValueAsBitsInit("Opcode"));
 668       RegInsts[Opc].push_back(Inst);
 669     }
 670   }
 671
 672   // For each memory form instruction, try to find its register form
 673   // instruction.
 674   for (const CodeGenInstruction *MemInst : MemInsts) {
 675     uint8_t Opc =
 676         getValueFromBitsInit(MemInst->TheDef->getValueAsBitsInit("Opcode"));
 677
 678     if (RegInsts.count(Opc) == 0)
 679       continue;
 680
 681     // Two forms (memory & register) of the same instruction must have the same
 682     // opcode. try matching only with register form instructions with the same
 683     // opcode.
 684     std::vector<const CodeGenInstruction *> &OpcRegInsts =
 685         RegInsts.find(Opc)->second;
 686
 687     auto Match = find_if(OpcRegInsts, IsMatch(MemInst, Records));
 688     if (Match != OpcRegInsts.end()) {
 689       const CodeGenInstruction *RegInst = *Match;
 690       // If the matched instruction has it's "FoldGenRegForm" set, map the
 691       // memory form instruction to the register form instruction pointed by
 692       // this field
 693       if (RegInst->TheDef->isValueUnset("FoldGenRegForm")) {
 694         updateTables(RegInst, MemInst);
 695       } else {
 696         const CodeGenInstruction *AltRegInst =
 697             getAltRegInst(RegInst, Records, Target);
 698         updateTables(AltRegInst, MemInst);
 699       }
 700       OpcRegInsts.erase(Match);
 701     }
 702   }
 703
 704   // Add the manually mapped instructions listed above.
 705   for (const ManualMapEntry &Entry : ManualMapSet) {
 706     Record *RegInstIter = Records.getDef(Entry.RegInstStr);
 707     Record *MemInstIter = Records.getDef(Entry.MemInstStr);
 708
 709     updateTables(&(Target.getInstruction(RegInstIter)),
 710                  &(Target.getInstruction(MemInstIter)), Entry.Strategy);
 711   }
 712
 713   // Print all tables to raw_ostream OS.
 714   printTable(Table2Addr, "Table2Addr", OS);
 715   printTable(Table0, "Table0", OS);
 716   printTable(Table1, "Table1", OS);
 717   printTable(Table2, "Table2", OS);
 718   printTable(Table3, "Table3", OS);
 719   printTable(Table4, "Table4", OS);
 720 }
 721
 722 namespace llvm {
 723
 724 void EmitX86FoldTables(RecordKeeper &RK, raw_ostream &OS) {
 725   X86FoldTablesEmitter(RK).run(OS);
 726 }
 727 } // namespace llvm