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