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 "CodeGenInstruction.h"
15#include "CodeGenTarget.h"
16#include "X86RecognizableInstr.h"
17#include "llvm/ADT/StringSwitch.h"
18#include "llvm/Support/FormattedStream.h"
19#include "llvm/Support/X86FoldTablesUtils.h"
20#include "llvm/TableGen/Record.h"
21#include "llvm/TableGen/TableGenBackend.h"
22#include <set>
23
24using namespace llvm;
25using namespace X86Disassembler;
26
27namespace {
28// Represents an entry in the manual mapped instructions set.
29struct ManualMapEntry {
30  const char *RegInstStr;
31  const char *MemInstStr;
32  uint16_t Strategy;
33};
34
35// List of instructions requiring explicitly aligned memory.
36const char *ExplicitAlign[] = {
37    "MOVDQA",    "MOVAPS",     "MOVAPD",     "MOVNTPS",    "MOVNTPD",
38    "MOVNTDQ",   "MOVNTDQA",   "SHA1MSG1",   "SHA1MSG2",   "SHA1NEXTE",
39    "SHA1RNDS4", "SHA256MSG1", "SHA256MSG2", "SHA256RNDS2"};
40
41// List of instructions NOT requiring explicit memory alignment.
42const char *ExplicitUnalign[] = {"MOVDQU",    "MOVUPS",    "MOVUPD",
43                                 "PCMPESTRM", "PCMPESTRI", "PCMPISTRM",
44                                 "PCMPISTRI"};
45
46const ManualMapEntry ManualMapSet[] = {
47#define ENTRY(REG, MEM, FLAGS) {#REG, #MEM, FLAGS},
48#include "X86ManualFoldTables.def"
49};
50
51const std::set<StringRef> NoFoldSet = {
52#define NOFOLD(INSN) #INSN,
53#include "X86ManualFoldTables.def"
54};
55
56static bool isExplicitAlign(const CodeGenInstruction *Inst) {
57  return any_of(ExplicitAlign, [Inst](const char *InstStr) {
58    return Inst->TheDef->getName().contains(InstStr);
59  });
60}
61
62static bool isExplicitUnalign(const CodeGenInstruction *Inst) {
63  return any_of(ExplicitUnalign, [Inst](const char *InstStr) {
64    return Inst->TheDef->getName().contains(InstStr);
65  });
66}
67
68class X86FoldTablesEmitter {
69  RecordKeeper &Records;
70  CodeGenTarget Target;
71
72  // Represents an entry in the folding table
73  class X86FoldTableEntry {
74    const CodeGenInstruction *RegInst;
75    const CodeGenInstruction *MemInst;
76
77  public:
78    bool NoReverse = false;
79    bool NoForward = false;
80    bool FoldLoad = false;
81    bool FoldStore = false;
82    enum BcastType {
83      BCAST_NONE,
84      BCAST_W,
85      BCAST_D,
86      BCAST_Q,
87      BCAST_SS,
88      BCAST_SD,
89      BCAST_SH,
90    };
91    BcastType BroadcastKind = BCAST_NONE;
92
93    Align Alignment;
94
95    X86FoldTableEntry() = default;
96    X86FoldTableEntry(const CodeGenInstruction *RegInst,
97                      const CodeGenInstruction *MemInst)
98        : RegInst(RegInst), MemInst(MemInst) {}
99
100    void print(formatted_raw_ostream &OS) const {
101      OS.indent(2);
102      OS << "{X86::" << RegInst->TheDef->getName() << ", ";
103      OS << "X86::" << MemInst->TheDef->getName() << ", ";
104
105      std::string Attrs;
106      if (FoldLoad)
107        Attrs += "TB_FOLDED_LOAD|";
108      if (FoldStore)
109        Attrs += "TB_FOLDED_STORE|";
110      if (NoReverse)
111        Attrs += "TB_NO_REVERSE|";
112      if (NoForward)
113        Attrs += "TB_NO_FORWARD|";
114      if (Alignment != Align(1))
115        Attrs += "TB_ALIGN_" + std::to_string(Alignment.value()) + "|";
116      switch (BroadcastKind) {
117      case BCAST_NONE:
118        break;
119      case BCAST_W:
120        Attrs += "TB_BCAST_W|";
121        break;
122      case BCAST_D:
123        Attrs += "TB_BCAST_D|";
124        break;
125      case BCAST_Q:
126        Attrs += "TB_BCAST_Q|";
127        break;
128      case BCAST_SS:
129        Attrs += "TB_BCAST_SS|";
130        break;
131      case BCAST_SD:
132        Attrs += "TB_BCAST_SD|";
133        break;
134      case BCAST_SH:
135        Attrs += "TB_BCAST_SH|";
136        break;
137      }
138
139      StringRef SimplifiedAttrs = StringRef(Attrs).rtrim("|");
140      if (SimplifiedAttrs.empty())
141        SimplifiedAttrs = "0";
142
143      OS << SimplifiedAttrs << "},\n";
144    }
145
146#ifndef NDEBUG
147    // Check that Uses and Defs are same after memory fold.
148    void checkCorrectness() const {
149      auto &RegInstRec = *RegInst->TheDef;
150      auto &MemInstRec = *MemInst->TheDef;
151      auto ListOfUsesReg = RegInstRec.getValueAsListOfDefs("Uses");
152      auto ListOfUsesMem = MemInstRec.getValueAsListOfDefs("Uses");
153      auto ListOfDefsReg = RegInstRec.getValueAsListOfDefs("Defs");
154      auto ListOfDefsMem = MemInstRec.getValueAsListOfDefs("Defs");
155      if (ListOfUsesReg != ListOfUsesMem || ListOfDefsReg != ListOfDefsMem)
156        report_fatal_error("Uses/Defs couldn't be changed after folding " +
157                           RegInstRec.getName() + " to " +
158                           MemInstRec.getName());
159    }
160#endif
161  };
162
163  // NOTE: We check the fold tables are sorted in X86InstrFoldTables.cpp by the
164  // enum of the instruction, which is computed in
165  // CodeGenTarget::ComputeInstrsByEnum. So we should use the same comparator
166  // here.
167  // FIXME: Could we share the code with CodeGenTarget::ComputeInstrsByEnum?
168  struct CompareInstrsByEnum {
169    bool operator()(const CodeGenInstruction *LHS,
170                    const CodeGenInstruction *RHS) const {
171      assert(LHS && RHS && "LHS and RHS shouldn't be nullptr");
172      const auto &D1 = *LHS->TheDef;
173      const auto &D2 = *RHS->TheDef;
174      return std::make_tuple(!D1.getValueAsBit("isPseudo"), D1.getName()) <
175             std::make_tuple(!D2.getValueAsBit("isPseudo"), D2.getName());
176    }
177  };
178
179  typedef std::map<const CodeGenInstruction *, X86FoldTableEntry,
180                   CompareInstrsByEnum>
181      FoldTable;
182  // Table2Addr - Holds instructions which their memory form performs
183  //              load+store.
184  //
185  // Table#i - Holds instructions which the their memory form
186  //           performs a load OR a store, and their #i'th operand is folded.
187  //
188  // BroadcastTable#i - Holds instructions which the their memory form performs
189  //                    a broadcast load and their #i'th operand is folded.
190  FoldTable Table2Addr;
191  FoldTable Table0;
192  FoldTable Table1;
193  FoldTable Table2;
194  FoldTable Table3;
195  FoldTable Table4;
196  FoldTable BroadcastTable1;
197  FoldTable BroadcastTable2;
198  FoldTable BroadcastTable3;
199  FoldTable BroadcastTable4;
200
201public:
202  X86FoldTablesEmitter(RecordKeeper &R) : Records(R), Target(R) {}
203
204  // run - Generate the 6 X86 memory fold tables.
205  void run(raw_ostream &OS);
206
207private:
208  // Decides to which table to add the entry with the given instructions.
209  // S sets the strategy of adding the TB_NO_REVERSE flag.
210  void updateTables(const CodeGenInstruction *RegInst,
211                    const CodeGenInstruction *MemInst, uint16_t S = 0,
212                    bool IsManual = false, bool IsBroadcast = false);
213
214  // Generates X86FoldTableEntry with the given instructions and fill it with
215  // the appropriate flags, then adds it to a memory fold table.
216  void addEntryWithFlags(FoldTable &Table, const CodeGenInstruction *RegInst,
217                         const CodeGenInstruction *MemInst, uint16_t S,
218                         unsigned FoldedIdx, bool IsManual);
219  // Generates X86FoldTableEntry with the given instructions and adds it to a
220  // broadcast table.
221  void addBroadcastEntry(FoldTable &Table, const CodeGenInstruction *RegInst,
222                         const CodeGenInstruction *MemInst);
223
224  // Print the given table as a static const C++ array of type
225  // X86FoldTableEntry.
226  void printTable(const FoldTable &Table, StringRef TableName,
227                  formatted_raw_ostream &OS) {
228    OS << "static const X86FoldTableEntry " << TableName << "[] = {\n";
229
230    for (auto &E : Table)
231      E.second.print(OS);
232
233    OS << "};\n\n";
234  }
235};
236
237// Return true if one of the instruction's operands is a RST register class
238static bool hasRSTRegClass(const CodeGenInstruction *Inst) {
239  return any_of(Inst->Operands, [](const CGIOperandList::OperandInfo &OpIn) {
240    return OpIn.Rec->getName() == "RST" || OpIn.Rec->getName() == "RSTi";
241  });
242}
243
244// Return true if one of the instruction's operands is a ptr_rc_tailcall
245static bool hasPtrTailcallRegClass(const CodeGenInstruction *Inst) {
246  return any_of(Inst->Operands, [](const CGIOperandList::OperandInfo &OpIn) {
247    return OpIn.Rec->getName() == "ptr_rc_tailcall";
248  });
249}
250
251static uint8_t byteFromBitsInit(const BitsInit *B) {
252  unsigned N = B->getNumBits();
253  assert(N <= 8 && "Field is too large for uint8_t!");
254
255  uint8_t Value = 0;
256  for (unsigned I = 0; I != N; ++I) {
257    BitInit *Bit = cast<BitInit>(B->getBit(I));
258    Value |= Bit->getValue() << I;
259  }
260  return Value;
261}
262
263static bool mayFoldFromForm(uint8_t Form) {
264  switch (Form) {
265  default:
266    return Form >= X86Local::MRM0r && Form <= X86Local::MRM7r;
267  case X86Local::MRMXr:
268  case X86Local::MRMXrCC:
269  case X86Local::MRMDestReg:
270  case X86Local::MRMSrcReg:
271  case X86Local::MRMSrcReg4VOp3:
272  case X86Local::MRMSrcRegOp4:
273  case X86Local::MRMSrcRegCC:
274    return true;
275  }
276}
277
278static bool mayFoldToForm(uint8_t Form) {
279  switch (Form) {
280  default:
281    return Form >= X86Local::MRM0m && Form <= X86Local::MRM7m;
282  case X86Local::MRMXm:
283  case X86Local::MRMXmCC:
284  case X86Local::MRMDestMem:
285  case X86Local::MRMSrcMem:
286  case X86Local::MRMSrcMem4VOp3:
287  case X86Local::MRMSrcMemOp4:
288  case X86Local::MRMSrcMemCC:
289    return true;
290  }
291}
292
293static bool mayFoldFromLeftToRight(uint8_t LHS, uint8_t RHS) {
294  switch (LHS) {
295  default:
296    llvm_unreachable("Unexpected Form!");
297  case X86Local::MRM0r:
298    return RHS == X86Local::MRM0m;
299  case X86Local::MRM1r:
300    return RHS == X86Local::MRM1m;
301  case X86Local::MRM2r:
302    return RHS == X86Local::MRM2m;
303  case X86Local::MRM3r:
304    return RHS == X86Local::MRM3m;
305  case X86Local::MRM4r:
306    return RHS == X86Local::MRM4m;
307  case X86Local::MRM5r:
308    return RHS == X86Local::MRM5m;
309  case X86Local::MRM6r:
310    return RHS == X86Local::MRM6m;
311  case X86Local::MRM7r:
312    return RHS == X86Local::MRM7m;
313  case X86Local::MRMXr:
314    return RHS == X86Local::MRMXm;
315  case X86Local::MRMXrCC:
316    return RHS == X86Local::MRMXmCC;
317  case X86Local::MRMDestReg:
318    return RHS == X86Local::MRMDestMem;
319  case X86Local::MRMSrcReg:
320    return RHS == X86Local::MRMSrcMem;
321  case X86Local::MRMSrcReg4VOp3:
322    return RHS == X86Local::MRMSrcMem4VOp3;
323  case X86Local::MRMSrcRegOp4:
324    return RHS == X86Local::MRMSrcMemOp4;
325  case X86Local::MRMSrcRegCC:
326    return RHS == X86Local::MRMSrcMemCC;
327  }
328}
329
330static bool isNOREXRegClass(const Record *Op) {
331  return Op->getName().contains("_NOREX");
332}
333
334// Function object - Operator() returns true if the given Reg instruction
335// matches the Mem instruction of this object.
336class IsMatch {
337  const CodeGenInstruction *MemInst;
338  const X86Disassembler::RecognizableInstrBase MemRI;
339  bool IsBroadcast;
340  const unsigned Variant;
341
342public:
343  IsMatch(const CodeGenInstruction *Inst, bool IsBroadcast, unsigned V)
344      : MemInst(Inst), MemRI(*MemInst), IsBroadcast(IsBroadcast), Variant(V) {}
345
346  bool operator()(const CodeGenInstruction *RegInst) {
347    X86Disassembler::RecognizableInstrBase RegRI(*RegInst);
348    const Record *RegRec = RegInst->TheDef;
349    const Record *MemRec = MemInst->TheDef;
350
351    // EVEX_B means different things for memory and register forms.
352    // register form: rounding control or SAE
353    // memory form: broadcast
354    if (IsBroadcast && (RegRI.HasEVEX_B || !MemRI.HasEVEX_B))
355      return false;
356    // EVEX_B indicates NDD for MAP4 instructions
357    if (!IsBroadcast && (RegRI.HasEVEX_B || MemRI.HasEVEX_B) &&
358        RegRI.OpMap != X86Local::T_MAP4)
359      return false;
360
361    if (!mayFoldFromLeftToRight(RegRI.Form, MemRI.Form))
362      return false;
363
364    // X86 encoding is crazy, e.g
365    //
366    // f3 0f c7 30       vmxon   (%rax)
367    // f3 0f c7 f0       senduipi        %rax
368    //
369    // This two instruction have similiar encoding fields but are unrelated
370    if (X86Disassembler::getMnemonic(MemInst, Variant) !=
371        X86Disassembler::getMnemonic(RegInst, Variant))
372      return false;
373
374    // Return false if any of the following fields of does not match.
375    if (std::make_tuple(RegRI.Encoding, RegRI.Opcode, RegRI.OpPrefix,
376                        RegRI.OpMap, RegRI.OpSize, RegRI.AdSize, RegRI.HasREX_W,
377                        RegRI.HasVEX_4V, RegRI.HasVEX_L, RegRI.IgnoresVEX_L,
378                        RegRI.IgnoresW, RegRI.HasEVEX_K, RegRI.HasEVEX_KZ,
379                        RegRI.HasEVEX_L2, RegRI.HasEVEX_NF,
380                        RegRec->getValueAsBit("hasEVEX_RC"),
381                        RegRec->getValueAsBit("hasLockPrefix"),
382                        RegRec->getValueAsBit("hasNoTrackPrefix")) !=
383        std::make_tuple(MemRI.Encoding, MemRI.Opcode, MemRI.OpPrefix,
384                        MemRI.OpMap, MemRI.OpSize, MemRI.AdSize, MemRI.HasREX_W,
385                        MemRI.HasVEX_4V, MemRI.HasVEX_L, MemRI.IgnoresVEX_L,
386                        MemRI.IgnoresW, MemRI.HasEVEX_K, MemRI.HasEVEX_KZ,
387                        MemRI.HasEVEX_L2, MemRI.HasEVEX_NF,
388                        MemRec->getValueAsBit("hasEVEX_RC"),
389                        MemRec->getValueAsBit("hasLockPrefix"),
390                        MemRec->getValueAsBit("hasNoTrackPrefix")))
391      return false;
392
393    // Make sure the sizes of the operands of both instructions suit each other.
394    // This is needed for instructions with intrinsic version (_Int).
395    // Where the only difference is the size of the operands.
396    // For example: VUCOMISDZrm and VUCOMISDrm_Int
397    // Also for instructions that their EVEX version was upgraded to work with
398    // k-registers. For example VPCMPEQBrm (xmm output register) and
399    // VPCMPEQBZ128rm (k register output register).
400    unsigned MemOutSize = MemRec->getValueAsDag("OutOperandList")->getNumArgs();
401    unsigned RegOutSize = RegRec->getValueAsDag("OutOperandList")->getNumArgs();
402    unsigned MemInSize = MemRec->getValueAsDag("InOperandList")->getNumArgs();
403    unsigned RegInSize = RegRec->getValueAsDag("InOperandList")->getNumArgs();
404
405    // Instructions with one output in their memory form use the memory folded
406    // operand as source and destination (Read-Modify-Write).
407    unsigned RegStartIdx =
408        (MemOutSize + 1 == RegOutSize) && (MemInSize == RegInSize) ? 1 : 0;
409
410    bool FoundFoldedOp = false;
411    for (unsigned I = 0, E = MemInst->Operands.size(); I != E; I++) {
412      Record *MemOpRec = MemInst->Operands[I].Rec;
413      Record *RegOpRec = RegInst->Operands[I + RegStartIdx].Rec;
414
415      if (MemOpRec == RegOpRec)
416        continue;
417
418      if (isRegisterOperand(MemOpRec) && isRegisterOperand(RegOpRec) &&
419          ((getRegOperandSize(MemOpRec) != getRegOperandSize(RegOpRec)) ||
420           (isNOREXRegClass(MemOpRec) != isNOREXRegClass(RegOpRec))))
421        return false;
422
423      if (isMemoryOperand(MemOpRec) && isMemoryOperand(RegOpRec) &&
424          (getMemOperandSize(MemOpRec) != getMemOperandSize(RegOpRec)))
425        return false;
426
427      if (isImmediateOperand(MemOpRec) && isImmediateOperand(RegOpRec) &&
428          (MemOpRec->getValueAsDef("Type") != RegOpRec->getValueAsDef("Type")))
429        return false;
430
431      // Only one operand can be folded.
432      if (FoundFoldedOp)
433        return false;
434
435      assert(isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec));
436      FoundFoldedOp = true;
437    }
438
439    return FoundFoldedOp;
440  }
441};
442
443} // end anonymous namespace
444
445void X86FoldTablesEmitter::addEntryWithFlags(FoldTable &Table,
446                                             const CodeGenInstruction *RegInst,
447                                             const CodeGenInstruction *MemInst,
448                                             uint16_t S, unsigned FoldedIdx,
449                                             bool IsManual) {
450
451  assert((IsManual || Table.find(RegInst) == Table.end()) &&
452         "Override entry unexpectedly");
453  X86FoldTableEntry Result = X86FoldTableEntry(RegInst, MemInst);
454  Record *RegRec = RegInst->TheDef;
455  Record *MemRec = MemInst->TheDef;
456
457  Result.NoReverse = S & TB_NO_REVERSE;
458  Result.NoForward = S & TB_NO_FORWARD;
459  Result.FoldLoad = S & TB_FOLDED_LOAD;
460  Result.FoldStore = S & TB_FOLDED_STORE;
461  Result.Alignment = Align(1ULL << ((S & TB_ALIGN_MASK) >> TB_ALIGN_SHIFT));
462  if (IsManual) {
463    Table[RegInst] = Result;
464    return;
465  }
466
467  // Only table0 entries should explicitly specify a load or store flag.
468  if (&Table == &Table0) {
469    unsigned MemInOpsNum = MemRec->getValueAsDag("InOperandList")->getNumArgs();
470    unsigned RegInOpsNum = RegRec->getValueAsDag("InOperandList")->getNumArgs();
471    // If the instruction writes to the folded operand, it will appear as an
472    // output in the register form instruction and as an input in the memory
473    // form instruction.
474    // If the instruction reads from the folded operand, it well appear as in
475    // input in both forms.
476    if (MemInOpsNum == RegInOpsNum)
477      Result.FoldLoad = true;
478    else
479      Result.FoldStore = true;
480  }
481
482  Record *RegOpRec = RegInst->Operands[FoldedIdx].Rec;
483  Record *MemOpRec = MemInst->Operands[FoldedIdx].Rec;
484
485  // Unfolding code generates a load/store instruction according to the size of
486  // the register in the register form instruction.
487  // If the register's size is greater than the memory's operand size, do not
488  // allow unfolding.
489
490  // the unfolded load size will be based on the register size. If that���s bigger
491  // than the memory operand size, the unfolded load will load more memory and
492  // potentially cause a memory fault.
493  if (getRegOperandSize(RegOpRec) > getMemOperandSize(MemOpRec))
494    Result.NoReverse = true;
495
496  // Check no-kz version's isMoveReg
497  StringRef RegInstName = RegRec->getName();
498  unsigned DropLen =
499      RegInstName.ends_with("rkz") ? 2 : (RegInstName.ends_with("rk") ? 1 : 0);
500  Record *BaseDef =
501      DropLen ? Records.getDef(RegInstName.drop_back(DropLen)) : nullptr;
502  bool IsMoveReg =
503      BaseDef ? Target.getInstruction(BaseDef).isMoveReg : RegInst->isMoveReg;
504  // A masked load can not be unfolded to a full load, otherwise it would access
505  // unexpected memory. A simple store can not be unfolded.
506  if (IsMoveReg && (BaseDef || Result.FoldStore))
507    Result.NoReverse = true;
508
509  uint8_t Enc = byteFromBitsInit(RegRec->getValueAsBitsInit("OpEncBits"));
510  if (isExplicitAlign(RegInst)) {
511    // The instruction require explicitly aligned memory.
512    BitsInit *VectSize = RegRec->getValueAsBitsInit("VectSize");
513    Result.Alignment = Align(byteFromBitsInit(VectSize));
514  } else if (!Enc && !isExplicitUnalign(RegInst) &&
515             getMemOperandSize(MemOpRec) > 64) {
516    // Instructions with XOP/VEX/EVEX encoding do not require alignment while
517    // SSE packed vector instructions require a 16 byte alignment.
518    Result.Alignment = Align(16);
519  }
520  // Expand is only ever created as a masked instruction. It is not safe to
521  // unfold a masked expand because we don't know if it came from an expand load
522  // intrinsic or folding a plain load. If it is from a expand load intrinsic,
523  // Unfolding to plain load would read more elements and could trigger a fault.
524  if (RegRec->getName().contains("EXPAND"))
525    Result.NoReverse = true;
526
527  Table[RegInst] = Result;
528}
529
530void X86FoldTablesEmitter::addBroadcastEntry(
531    FoldTable &Table, const CodeGenInstruction *RegInst,
532    const CodeGenInstruction *MemInst) {
533
534  assert(Table.find(RegInst) == Table.end() && "Override entry unexpectedly");
535  X86FoldTableEntry Result = X86FoldTableEntry(RegInst, MemInst);
536
537  DagInit *In = MemInst->TheDef->getValueAsDag("InOperandList");
538  for (unsigned I = 0, E = In->getNumArgs(); I != E; ++I) {
539    Result.BroadcastKind =
540        StringSwitch<X86FoldTableEntry::BcastType>(In->getArg(I)->getAsString())
541            .Case("i16mem", X86FoldTableEntry::BCAST_W)
542            .Case("i32mem", X86FoldTableEntry::BCAST_D)
543            .Case("i64mem", X86FoldTableEntry::BCAST_Q)
544            .Case("f16mem", X86FoldTableEntry::BCAST_SH)
545            .Case("f32mem", X86FoldTableEntry::BCAST_SS)
546            .Case("f64mem", X86FoldTableEntry::BCAST_SD)
547            .Default(X86FoldTableEntry::BCAST_NONE);
548    if (Result.BroadcastKind != X86FoldTableEntry::BCAST_NONE)
549      break;
550  }
551  assert(Result.BroadcastKind != X86FoldTableEntry::BCAST_NONE &&
552         "Unknown memory operand for broadcast");
553
554  Table[RegInst] = Result;
555}
556
557void X86FoldTablesEmitter::updateTables(const CodeGenInstruction *RegInst,
558                                        const CodeGenInstruction *MemInst,
559                                        uint16_t S, bool IsManual,
560                                        bool IsBroadcast) {
561
562  Record *RegRec = RegInst->TheDef;
563  Record *MemRec = MemInst->TheDef;
564  unsigned MemOutSize = MemRec->getValueAsDag("OutOperandList")->getNumArgs();
565  unsigned RegOutSize = RegRec->getValueAsDag("OutOperandList")->getNumArgs();
566  unsigned MemInSize = MemRec->getValueAsDag("InOperandList")->getNumArgs();
567  unsigned RegInSize = RegRec->getValueAsDag("InOperandList")->getNumArgs();
568
569  // Instructions which Read-Modify-Write should be added to Table2Addr.
570  if (!MemOutSize && RegOutSize == 1 && MemInSize == RegInSize) {
571    assert(!IsBroadcast && "Read-Modify-Write can not be broadcast");
572    // X86 would not unfold Read-Modify-Write instructions so add TB_NO_REVERSE.
573    addEntryWithFlags(Table2Addr, RegInst, MemInst, S | TB_NO_REVERSE, 0,
574                      IsManual);
575    return;
576  }
577
578  if (MemInSize == RegInSize && MemOutSize == RegOutSize) {
579    // Load-Folding cases.
580    // If the i'th register form operand is a register and the i'th memory form
581    // operand is a memory operand, add instructions to Table#i.
582    for (unsigned I = RegOutSize, E = RegInst->Operands.size(); I < E; I++) {
583      Record *RegOpRec = RegInst->Operands[I].Rec;
584      Record *MemOpRec = MemInst->Operands[I].Rec;
585      // PointerLikeRegClass: For instructions like TAILJMPr, TAILJMPr64,
586      // TAILJMPr64_REX
587      if ((isRegisterOperand(RegOpRec) ||
588           RegOpRec->isSubClassOf("PointerLikeRegClass")) &&
589          isMemoryOperand(MemOpRec)) {
590        switch (I) {
591        case 0:
592          assert(!IsBroadcast && "BroadcastTable0 needs to be added");
593          addEntryWithFlags(Table0, RegInst, MemInst, S, 0, IsManual);
594          return;
595        case 1:
596          IsBroadcast
597              ? addBroadcastEntry(BroadcastTable1, RegInst, MemInst)
598              : addEntryWithFlags(Table1, RegInst, MemInst, S, 1, IsManual);
599          return;
600        case 2:
601          IsBroadcast
602              ? addBroadcastEntry(BroadcastTable2, RegInst, MemInst)
603              : addEntryWithFlags(Table2, RegInst, MemInst, S, 2, IsManual);
604          return;
605        case 3:
606          IsBroadcast
607              ? addBroadcastEntry(BroadcastTable3, RegInst, MemInst)
608              : addEntryWithFlags(Table3, RegInst, MemInst, S, 3, IsManual);
609          return;
610        case 4:
611          IsBroadcast
612              ? addBroadcastEntry(BroadcastTable4, RegInst, MemInst)
613              : addEntryWithFlags(Table4, RegInst, MemInst, S, 4, IsManual);
614          return;
615        }
616      }
617    }
618  } else if (MemInSize == RegInSize + 1 && MemOutSize + 1 == RegOutSize) {
619    // Store-Folding cases.
620    // If the memory form instruction performs a store, the *output*
621    // register of the register form instructions disappear and instead a
622    // memory *input* operand appears in the memory form instruction.
623    // For example:
624    //   MOVAPSrr => (outs VR128:$dst), (ins VR128:$src)
625    //   MOVAPSmr => (outs), (ins f128mem:$dst, VR128:$src)
626    Record *RegOpRec = RegInst->Operands[RegOutSize - 1].Rec;
627    Record *MemOpRec = MemInst->Operands[RegOutSize - 1].Rec;
628    if (isRegisterOperand(RegOpRec) && isMemoryOperand(MemOpRec) &&
629        getRegOperandSize(RegOpRec) == getMemOperandSize(MemOpRec)) {
630      assert(!IsBroadcast && "Store can not be broadcast");
631      addEntryWithFlags(Table0, RegInst, MemInst, S, 0, IsManual);
632    }
633  }
634}
635
636void X86FoldTablesEmitter::run(raw_ostream &O) {
637  formatted_raw_ostream OS(O);
638
639  // Holds all memory instructions
640  std::vector<const CodeGenInstruction *> MemInsts;
641  // Holds all register instructions - divided according to opcode.
642  std::map<uint8_t, std::vector<const CodeGenInstruction *>> RegInsts;
643
644  ArrayRef<const CodeGenInstruction *> NumberedInstructions =
645      Target.getInstructionsByEnumValue();
646
647  for (const CodeGenInstruction *Inst : NumberedInstructions) {
648    const Record *Rec = Inst->TheDef;
649    if (!Rec->isSubClassOf("X86Inst") || Rec->getValueAsBit("isAsmParserOnly"))
650      continue;
651
652    if (NoFoldSet.find(Rec->getName()) != NoFoldSet.end())
653      continue;
654
655    // Promoted legacy instruction is in EVEX space, and has REX2-encoding
656    // alternative. It's added due to HW design and never emitted by compiler.
657    if (byteFromBitsInit(Rec->getValueAsBitsInit("OpMapBits")) ==
658            X86Local::T_MAP4 &&
659        byteFromBitsInit(Rec->getValueAsBitsInit("explicitOpPrefixBits")) ==
660            X86Local::ExplicitEVEX)
661      continue;
662
663    // - Instructions including RST register class operands are not relevant
664    //   for memory folding (for further details check the explanation in
665    //   lib/Target/X86/X86InstrFPStack.td file).
666    // - Some instructions (listed in the manual map above) use the register
667    //   class ptr_rc_tailcall, which can be of a size 32 or 64, to ensure
668    //   safe mapping of these instruction we manually map them and exclude
669    //   them from the automation.
670    if (hasRSTRegClass(Inst) || hasPtrTailcallRegClass(Inst))
671      continue;
672
673    // Add all the memory form instructions to MemInsts, and all the register
674    // form instructions to RegInsts[Opc], where Opc is the opcode of each
675    // instructions. this helps reducing the runtime of the backend.
676    const BitsInit *FormBits = Rec->getValueAsBitsInit("FormBits");
677    uint8_t Form = byteFromBitsInit(FormBits);
678    if (mayFoldToForm(Form))
679      MemInsts.push_back(Inst);
680    else if (mayFoldFromForm(Form)) {
681      uint8_t Opc = byteFromBitsInit(Rec->getValueAsBitsInit("Opcode"));
682      RegInsts[Opc].push_back(Inst);
683    }
684  }
685
686  // Create a copy b/c the register instruction will removed when a new entry is
687  // added into memory fold tables.
688  auto RegInstsForBroadcast = RegInsts;
689
690  Record *AsmWriter = Target.getAsmWriter();
691  unsigned Variant = AsmWriter->getValueAsInt("Variant");
692  auto FixUp = [&](const CodeGenInstruction *RegInst) {
693    StringRef RegInstName = RegInst->TheDef->getName();
694    if (RegInstName.ends_with("_REV") || RegInstName.ends_with("_alt"))
695      if (auto *RegAltRec = Records.getDef(RegInstName.drop_back(4)))
696        RegInst = &Target.getInstruction(RegAltRec);
697    return RegInst;
698  };
699  // For each memory form instruction, try to find its register form
700  // instruction.
701  for (const CodeGenInstruction *MemInst : MemInsts) {
702    uint8_t Opc =
703        byteFromBitsInit(MemInst->TheDef->getValueAsBitsInit("Opcode"));
704
705    auto RegInstsIt = RegInsts.find(Opc);
706    if (RegInstsIt == RegInsts.end())
707      continue;
708
709    // Two forms (memory & register) of the same instruction must have the same
710    // opcode.
711    std::vector<const CodeGenInstruction *> &OpcRegInsts = RegInstsIt->second;
712
713    // Memory fold tables
714    auto Match =
715        find_if(OpcRegInsts, IsMatch(MemInst, /*IsBroadcast=*/false, Variant));
716    if (Match != OpcRegInsts.end()) {
717      updateTables(FixUp(*Match), MemInst);
718      OpcRegInsts.erase(Match);
719    }
720
721    // Broadcast tables
722    StringRef MemInstName = MemInst->TheDef->getName();
723    if (!MemInstName.contains("mb") && !MemInstName.contains("mib"))
724      continue;
725    RegInstsIt = RegInstsForBroadcast.find(Opc);
726    assert(RegInstsIt != RegInstsForBroadcast.end() &&
727           "Unexpected control flow");
728    std::vector<const CodeGenInstruction *> &OpcRegInstsForBroadcast =
729        RegInstsIt->second;
730    Match = find_if(OpcRegInstsForBroadcast,
731                    IsMatch(MemInst, /*IsBroadcast=*/true, Variant));
732    if (Match != OpcRegInstsForBroadcast.end()) {
733      updateTables(FixUp(*Match), MemInst, 0, /*IsManual=*/false,
734                   /*IsBroadcast=*/true);
735      OpcRegInstsForBroadcast.erase(Match);
736    }
737  }
738
739  // Add the manually mapped instructions listed above.
740  for (const ManualMapEntry &Entry : ManualMapSet) {
741    Record *RegInstIter = Records.getDef(Entry.RegInstStr);
742    Record *MemInstIter = Records.getDef(Entry.MemInstStr);
743
744    updateTables(&(Target.getInstruction(RegInstIter)),
745                 &(Target.getInstruction(MemInstIter)), Entry.Strategy, true);
746  }
747
748#ifndef NDEBUG
749  auto CheckMemFoldTable = [](const FoldTable &Table) -> void {
750    for (const auto &Record : Table) {
751      auto &FoldEntry = Record.second;
752      FoldEntry.checkCorrectness();
753    }
754  };
755  CheckMemFoldTable(Table2Addr);
756  CheckMemFoldTable(Table0);
757  CheckMemFoldTable(Table1);
758  CheckMemFoldTable(Table2);
759  CheckMemFoldTable(Table3);
760  CheckMemFoldTable(Table4);
761  CheckMemFoldTable(BroadcastTable1);
762  CheckMemFoldTable(BroadcastTable2);
763  CheckMemFoldTable(BroadcastTable3);
764  CheckMemFoldTable(BroadcastTable4);
765#endif
766#define PRINT_TABLE(TABLE) printTable(TABLE, #TABLE, OS);
767  // Print all tables.
768  PRINT_TABLE(Table2Addr)
769  PRINT_TABLE(Table0)
770  PRINT_TABLE(Table1)
771  PRINT_TABLE(Table2)
772  PRINT_TABLE(Table3)
773  PRINT_TABLE(Table4)
774  PRINT_TABLE(BroadcastTable1)
775  PRINT_TABLE(BroadcastTable2)
776  PRINT_TABLE(BroadcastTable3)
777  PRINT_TABLE(BroadcastTable4)
778}
779
780static TableGen::Emitter::OptClass<X86FoldTablesEmitter>
781    X("gen-x86-fold-tables", "Generate X86 fold tables");
782