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