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