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