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