//===-- X86InstrFoldTables.cpp - X86 Instruction Folding Tables -----------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file contains the X86 memory folding tables.

//

//===----------------------------------------------------------------------===//

#include "X86InstrFoldTables.h"

#include "X86InstrInfo.h"

#include "llvm/ADT/STLExtras.h"

#include <atomic>

#include <vector>

using namespace llvm;

// These tables are sorted by their RegOp value allowing them to be binary

// searched at runtime without the need for additional storage. The enum values

// are currently emitted in X86GenInstrInfo.inc in alphabetical order. Which

// makes sorting these tables a simple matter of alphabetizing the table.

#include "X86GenFoldTables.inc"

// Table to map instructions safe to broadcast using a different width from the

// element width.

static const X86FoldTableEntry BroadcastSizeTable2[] = {

  { X86::VANDNPDZ128rr,        X86::VANDNPSZ128rmb,       TB_BCAST_SS },

  { X86::VANDNPDZ256rr,        X86::VANDNPSZ256rmb,       TB_BCAST_SS },

  { X86::VANDNPDZrr,           X86::VANDNPSZrmb,          TB_BCAST_SS },

  { X86::VANDNPSZ128rr,        X86::VANDNPDZ128rmb,       TB_BCAST_SD },

  { X86::VANDNPSZ256rr,        X86::VANDNPDZ256rmb,       TB_BCAST_SD },

  { X86::VANDNPSZrr,           X86::VANDNPDZrmb,          TB_BCAST_SD },

  { X86::VANDPDZ128rr,         X86::VANDPSZ128rmb,        TB_BCAST_SS },

  { X86::VANDPDZ256rr,         X86::VANDPSZ256rmb,        TB_BCAST_SS },

  { X86::VANDPDZrr,            X86::VANDPSZrmb,           TB_BCAST_SS },

  { X86::VANDPSZ128rr,         X86::VANDPDZ128rmb,        TB_BCAST_SD },

  { X86::VANDPSZ256rr,         X86::VANDPDZ256rmb,        TB_BCAST_SD },

  { X86::VANDPSZrr,            X86::VANDPDZrmb,           TB_BCAST_SD },

  { X86::VORPDZ128rr,          X86::VORPSZ128rmb,         TB_BCAST_SS },

  { X86::VORPDZ256rr,          X86::VORPSZ256rmb,         TB_BCAST_SS },

  { X86::VORPDZrr,             X86::VORPSZrmb,            TB_BCAST_SS },

  { X86::VORPSZ128rr,          X86::VORPDZ128rmb,         TB_BCAST_SD },

  { X86::VORPSZ256rr,          X86::VORPDZ256rmb,         TB_BCAST_SD },

  { X86::VORPSZrr,             X86::VORPDZrmb,            TB_BCAST_SD },

  { X86::VPANDDZ128rr,         X86::VPANDQZ128rmb,        TB_BCAST_Q },

  { X86::VPANDDZ256rr,         X86::VPANDQZ256rmb,        TB_BCAST_Q },

  { X86::VPANDDZrr,            X86::VPANDQZrmb,           TB_BCAST_Q },

  { X86::VPANDNDZ128rr,        X86::VPANDNQZ128rmb,       TB_BCAST_Q },

  { X86::VPANDNDZ256rr,        X86::VPANDNQZ256rmb,       TB_BCAST_Q },

  { X86::VPANDNDZrr,           X86::VPANDNQZrmb,          TB_BCAST_Q },

  { X86::VPANDNQZ128rr,        X86::VPANDNDZ128rmb,       TB_BCAST_D },

  { X86::VPANDNQZ256rr,        X86::VPANDNDZ256rmb,       TB_BCAST_D },

  { X86::VPANDNQZrr,           X86::VPANDNDZrmb,          TB_BCAST_D },

  { X86::VPANDQZ128rr,         X86::VPANDDZ128rmb,        TB_BCAST_D },

  { X86::VPANDQZ256rr,         X86::VPANDDZ256rmb,        TB_BCAST_D },

  { X86::VPANDQZrr,            X86::VPANDDZrmb,           TB_BCAST_D },

  { X86::VPORDZ128rr,          X86::VPORQZ128rmb,         TB_BCAST_Q },

  { X86::VPORDZ256rr,          X86::VPORQZ256rmb,         TB_BCAST_Q },

  { X86::VPORDZrr,             X86::VPORQZrmb,            TB_BCAST_Q },

  { X86::VPORQZ128rr,          X86::VPORDZ128rmb,         TB_BCAST_D },

  { X86::VPORQZ256rr,          X86::VPORDZ256rmb,         TB_BCAST_D },

  { X86::VPORQZrr,             X86::VPORDZrmb,            TB_BCAST_D },

  { X86::VPXORDZ128rr,         X86::VPXORQZ128rmb,        TB_BCAST_Q },

  { X86::VPXORDZ256rr,         X86::VPXORQZ256rmb,        TB_BCAST_Q },

  { X86::VPXORDZrr,            X86::VPXORQZrmb,           TB_BCAST_Q },

  { X86::VPXORQZ128rr,         X86::VPXORDZ128rmb,        TB_BCAST_D },

  { X86::VPXORQZ256rr,         X86::VPXORDZ256rmb,        TB_BCAST_D },

  { X86::VPXORQZrr,            X86::VPXORDZrmb,           TB_BCAST_D },

  { X86::VXORPDZ128rr,         X86::VXORPSZ128rmb,        TB_BCAST_SS },

  { X86::VXORPDZ256rr,         X86::VXORPSZ256rmb,        TB_BCAST_SS },

  { X86::VXORPDZrr,            X86::VXORPSZrmb,           TB_BCAST_SS },

  { X86::VXORPSZ128rr,         X86::VXORPDZ128rmb,        TB_BCAST_SD },

  { X86::VXORPSZ256rr,         X86::VXORPDZ256rmb,        TB_BCAST_SD },

  { X86::VXORPSZrr,            X86::VXORPDZrmb,           TB_BCAST_SD },

};

static const X86FoldTableEntry BroadcastSizeTable3[] = {

  { X86::VPTERNLOGDZ128rri,    X86::VPTERNLOGQZ128rmbi,   TB_BCAST_Q },

  { X86::VPTERNLOGDZ256rri,    X86::VPTERNLOGQZ256rmbi,   TB_BCAST_Q },

  { X86::VPTERNLOGDZrri,       X86::VPTERNLOGQZrmbi,      TB_BCAST_Q },

  { X86::VPTERNLOGQZ128rri,    X86::VPTERNLOGDZ128rmbi,   TB_BCAST_D },

  { X86::VPTERNLOGQZ256rri,    X86::VPTERNLOGDZ256rmbi,   TB_BCAST_D },

  { X86::VPTERNLOGQZrri,       X86::VPTERNLOGDZrmbi,      TB_BCAST_D },

};

static const X86FoldTableEntry *

lookupFoldTableImpl(ArrayRef<X86FoldTableEntry> Table, unsigned RegOp) {

#ifndef NDEBUG

#define CHECK_SORTED_UNIQUE(TABLE)                                             \

  assert(llvm::is_sorted(TABLE) && #TABLE " is not sorted");                   \

  assert(std::adjacent_find(std::begin(Table), std::end(Table)) ==             \

             std::end(Table) &&                                                \

         #TABLE " is not unique");

  // Make sure the tables are sorted.

  static std::atomic<bool> FoldTablesChecked(false);

  if (!FoldTablesChecked.load(std::memory_order_relaxed)) {

    CHECK_SORTED_UNIQUE(Table2Addr)

    CHECK_SORTED_UNIQUE(Table0)

    CHECK_SORTED_UNIQUE(Table1)

    CHECK_SORTED_UNIQUE(Table2)

    CHECK_SORTED_UNIQUE(Table3)

    CHECK_SORTED_UNIQUE(Table4)

    CHECK_SORTED_UNIQUE(BroadcastTable1)

    CHECK_SORTED_UNIQUE(BroadcastTable2)

    CHECK_SORTED_UNIQUE(BroadcastTable3)

    CHECK_SORTED_UNIQUE(BroadcastTable4)

    CHECK_SORTED_UNIQUE(BroadcastSizeTable2)

    CHECK_SORTED_UNIQUE(BroadcastSizeTable3)

    FoldTablesChecked.store(true, std::memory_order_relaxed);

  }

#endif

  const X86FoldTableEntry *Data = llvm::lower_bound(Table, RegOp);

  if (Data != Table.end() && Data->KeyOp == RegOp &&

      !(Data->Flags & TB_NO_FORWARD))

    return Data;

  return nullptr;

}

const X86FoldTableEntry *

llvm::lookupTwoAddrFoldTable(unsigned RegOp) {

  return lookupFoldTableImpl(Table2Addr, RegOp);

}

const X86FoldTableEntry *

llvm::lookupFoldTable(unsigned RegOp, unsigned OpNum) {

  ArrayRef<X86FoldTableEntry> FoldTable;

  if (OpNum == 0)

    FoldTable = ArrayRef(Table0);

  else if (OpNum == 1)

    FoldTable = ArrayRef(Table1);

  else if (OpNum == 2)

    FoldTable = ArrayRef(Table2);

  else if (OpNum == 3)

    FoldTable = ArrayRef(Table3);

  else if (OpNum == 4)

    FoldTable = ArrayRef(Table4);

  else

    return nullptr;

  return lookupFoldTableImpl(FoldTable, RegOp);

}

namespace {

// This class stores the memory unfolding tables. It is instantiated as a

// function scope static variable to lazily init the unfolding table.

struct X86MemUnfoldTable {

  // Stores memory unfolding tables entries sorted by opcode.

  std::vector<X86FoldTableEntry> Table;

  X86MemUnfoldTable() {

    for (const X86FoldTableEntry &Entry : Table2Addr)

      // Index 0, folded load and store, no alignment requirement.

      addTableEntry(Entry, TB_INDEX_0 | TB_FOLDED_LOAD | TB_FOLDED_STORE);

    for (const X86FoldTableEntry &Entry : Table0)

      // Index 0, mix of loads and stores.

      addTableEntry(Entry, TB_INDEX_0);

    for (const X86FoldTableEntry &Entry : Table1)

      // Index 1, folded load

      addTableEntry(Entry, TB_INDEX_1 | TB_FOLDED_LOAD);

    for (const X86FoldTableEntry &Entry : Table2)

      // Index 2, folded load

      addTableEntry(Entry, TB_INDEX_2 | TB_FOLDED_LOAD);

    for (const X86FoldTableEntry &Entry : Table3)

      // Index 3, folded load

      addTableEntry(Entry, TB_INDEX_3 | TB_FOLDED_LOAD);

    for (const X86FoldTableEntry &Entry : Table4)

      // Index 4, folded load

      addTableEntry(Entry, TB_INDEX_4 | TB_FOLDED_LOAD);

    // Broadcast tables.

    for (const X86FoldTableEntry &Entry : BroadcastTable2)

      // Index 2, folded broadcast

      addTableEntry(Entry, TB_INDEX_2 | TB_FOLDED_LOAD | TB_FOLDED_BCAST);

    for (const X86FoldTableEntry &Entry : BroadcastTable3)

      // Index 3, folded broadcast

      addTableEntry(Entry, TB_INDEX_3 | TB_FOLDED_LOAD | TB_FOLDED_BCAST);

    for (const X86FoldTableEntry &Entry : BroadcastTable4)

      // Index 4, folded broadcast

      addTableEntry(Entry, TB_INDEX_4 | TB_FOLDED_LOAD | TB_FOLDED_BCAST);

    // Sort the memory->reg unfold table.

    array_pod_sort(Table.begin(), Table.end());

    // Now that it's sorted, ensure its unique.

    assert(std::adjacent_find(Table.begin(), Table.end()) == Table.end() &&

           "Memory unfolding table is not unique!");

  }

  void addTableEntry(const X86FoldTableEntry &Entry,

                     uint16_t ExtraFlags) {

    // NOTE: This swaps the KeyOp and DstOp in the table so we can sort it.

    if ((Entry.Flags & TB_NO_REVERSE) == 0)

      Table.push_back({Entry.DstOp, Entry.KeyOp,

                      static_cast<uint16_t>(Entry.Flags | ExtraFlags) });

  }

};

}

const X86FoldTableEntry *

llvm::lookupUnfoldTable(unsigned MemOp) {

  static X86MemUnfoldTable MemUnfoldTable;

  auto &Table = MemUnfoldTable.Table;

  auto I = llvm::lower_bound(Table, MemOp);

  if (I != Table.end() && I->KeyOp == MemOp)

    return &*I;

  return nullptr;

}

namespace {

// This class stores the memory -> broadcast folding tables. It is instantiated

// as a function scope static variable to lazily init the folding table.

struct X86BroadcastFoldTable {

  // Stores memory broadcast folding tables entries sorted by opcode.

  std::vector<X86FoldTableEntry> Table;

  X86BroadcastFoldTable() {

    // Broadcast tables.

    for (const X86FoldTableEntry &Reg2Bcst : BroadcastTable2) {

      unsigned RegOp = Reg2Bcst.KeyOp;

      unsigned BcstOp = Reg2Bcst.DstOp;

      if (const X86FoldTableEntry *Reg2Mem = lookupFoldTable(RegOp, 2)) {

        unsigned MemOp = Reg2Mem->DstOp;

        uint16_t Flags = Reg2Mem->Flags | Reg2Bcst.Flags | TB_INDEX_2 |

                         TB_FOLDED_LOAD | TB_FOLDED_BCAST;

        Table.push_back({MemOp, BcstOp, Flags});

      }

    }

    for (const X86FoldTableEntry &Reg2Bcst : BroadcastSizeTable2) {

      unsigned RegOp = Reg2Bcst.KeyOp;

      unsigned BcstOp = Reg2Bcst.DstOp;

      if (const X86FoldTableEntry *Reg2Mem = lookupFoldTable(RegOp, 2)) {

        unsigned MemOp = Reg2Mem->DstOp;

        uint16_t Flags = Reg2Mem->Flags | Reg2Bcst.Flags | TB_INDEX_2 |

                         TB_FOLDED_LOAD | TB_FOLDED_BCAST;

        Table.push_back({MemOp, BcstOp, Flags});

      }

    }

    for (const X86FoldTableEntry &Reg2Bcst : BroadcastTable3) {

      unsigned RegOp = Reg2Bcst.KeyOp;

      unsigned BcstOp = Reg2Bcst.DstOp;

      if (const X86FoldTableEntry *Reg2Mem = lookupFoldTable(RegOp, 3)) {

        unsigned MemOp = Reg2Mem->DstOp;

        uint16_t Flags = Reg2Mem->Flags | Reg2Bcst.Flags | TB_INDEX_3 |

                         TB_FOLDED_LOAD | TB_FOLDED_BCAST;

        Table.push_back({MemOp, BcstOp, Flags});

      }

    }

    for (const X86FoldTableEntry &Reg2Bcst : BroadcastSizeTable3) {

      unsigned RegOp = Reg2Bcst.KeyOp;

      unsigned BcstOp = Reg2Bcst.DstOp;

      if (const X86FoldTableEntry *Reg2Mem = lookupFoldTable(RegOp, 3)) {

        unsigned MemOp = Reg2Mem->DstOp;

        uint16_t Flags = Reg2Mem->Flags | Reg2Bcst.Flags | TB_INDEX_3 |

                         TB_FOLDED_LOAD | TB_FOLDED_BCAST;

        Table.push_back({MemOp, BcstOp, Flags});

      }

    }

    for (const X86FoldTableEntry &Reg2Bcst : BroadcastTable4) {

      unsigned RegOp = Reg2Bcst.KeyOp;

      unsigned BcstOp = Reg2Bcst.DstOp;

      if (const X86FoldTableEntry *Reg2Mem = lookupFoldTable(RegOp, 4)) {

        unsigned MemOp = Reg2Mem->DstOp;

        uint16_t Flags = Reg2Mem->Flags | Reg2Bcst.Flags | TB_INDEX_4 |

                         TB_FOLDED_LOAD | TB_FOLDED_BCAST;

        Table.push_back({MemOp, BcstOp, Flags});

      }

    }

    // Sort the memory->broadcast fold table.

    array_pod_sort(Table.begin(), Table.end());

  }

};

} // namespace

static bool matchBroadcastSize(const X86FoldTableEntry &Entry,

                               unsigned BroadcastBits) {

  switch (Entry.Flags & TB_BCAST_MASK) {

  case TB_BCAST_SD:

  case TB_BCAST_Q:

    return BroadcastBits == 64;

  case TB_BCAST_SS:

  case TB_BCAST_D:

    return BroadcastBits == 32;

  }

  return false;

}

const X86FoldTableEntry *

llvm::lookupBroadcastFoldTable(unsigned MemOp, unsigned BroadcastBits) {

  static X86BroadcastFoldTable BroadcastFoldTable;

  auto &Table = BroadcastFoldTable.Table;

  for (auto I = llvm::lower_bound(Table, MemOp);

       I != Table.end() && I->KeyOp == MemOp; ++I) {

    if (matchBroadcastSize(*I, BroadcastBits))

      return &*I;

  }

  return nullptr;

}