[X86] Use a std::vector for the memory unfolding vector.

[craig.topper]

Summary

Previously we used a DenseMap which is costly to setup due to multiple full table rehashes as the size increases and causes the table to be reallocated.

This patch changes the table to a vector of structs. We now walk the reg->mem tables and push new entries in the mem->reg table for each row not marked TB_NO_REVERSE. Once all the table entries have been created, we sort the vector. Then we can use a binary search for lookups.

[greened]

LGTM.

lib/Target/X86/X86InstrInfo.cpp

5424

One thing I have wanted with the previous assert is to dump the duplicate entry so I know what to look for. That's probably a separate change, but a useful one, I think. I've been bitten by this before and it's a pain to figure out what happened. Since this is under NDEBUG it seems like we can do a little more work here to inform about what's going on.

lib/Target/X86/X86InstrInfo.h

175

Wonderful!

[craig.topper]

@greened, did you forget to Accept when you wrote LGTM or should I wait for another reviewer?

lib/Target/X86/X86InstrInfo.cpp

5424

What would that look like? Do you just want to print the enum values from the failing row or do you want to try to turn that back into a string that a human could read?

[RKSimon]

LGTM - better error reporting would be great but not mandatory.

lib/Target/X86/X86InstrInfo.cpp

5424

Anything that can be used to debug would be useful - enums are easy enough to work with as you can manually look them up in X86GenInstrInfo.inc - but an actual string would be even better.

[greened]

In D48585#1147543, @craig.topper wrote:

@greened, did you forget to Accept when you wrote LGTM or should I wait for another reviewer?

I'm not a code owner and I don't know what the rules are around accepting.

lib/Target/X86/X86InstrInfo.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_X86_X86INSTRINFO_H
 #define LLVM_LIB_TARGET_X86_X86INSTRINFO_H
 
 #include "MCTargetDesc/X86BaseInfo.h"
 #include "X86InstrFMA3Info.h"
 #include "X86RegisterInfo.h"
-#include "llvm/ADT/DenseMap.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
+#include <vector>
 
 #define GET_INSTRINFO_HEADER
 #include "X86GenInstrInfo.inc"
 
 namespace llvm {
 class MachineInstrBuilder;
 class X86RegisterInfo;
 class X86Subtarget;
inline static bool isMem(const MachineInstr &MI, unsigned Op) {
   return Op + X86::AddrNumOperands <= MI.getNumOperands() &&
          MI.getOperand(Op + X86::AddrSegmentReg).isReg() && isLeaMem(MI, Op);
 }
 
 class X86InstrInfo final : public X86GenInstrInfo {
   X86Subtarget &Subtarget;
   const X86RegisterInfo RI;
 
+  struct MemOp2RegOpTableTypeEntry {
+    uint16_t MemOp;
+    uint16_t RegOp;
+    uint16_t Flags;
+
+    bool operator<(const MemOp2RegOpTableTypeEntry &RHS) const {
+      return MemOp < RHS.MemOp;
+    }
+    bool operator==(const MemOp2RegOpTableTypeEntry &RHS) const {
+      return MemOp == RHS.MemOp;
+    }
+    friend bool operator<(const MemOp2RegOpTableTypeEntry &TE,
+                          unsigned Opcode) {
+      return TE.MemOp < Opcode;
+    }
+  };
+
   /// MemOp2RegOpTable - Load / store unfolding opcode map.
   ///
-  typedef DenseMap<unsigned, std::pair<uint16_t, uint16_t>>
-      MemOp2RegOpTableType;
+  typedef std::vector<MemOp2RegOpTableTypeEntry> MemOp2RegOpTableType;
   MemOp2RegOpTableType MemOp2RegOpTable;
 
   static void AddTableEntry(MemOp2RegOpTableType &M2RTable, uint16_t RegOp,
                             uint16_t MemOp, uint16_t Flags);
+  const MemOp2RegOpTableTypeEntry *lookupUnfoldTable(unsigned MemOp) const;
 
   virtual void anchor();
 
   bool AnalyzeBranchImpl(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                          MachineBasicBlock *&FBB,
                          SmallVectorImpl<MachineOperand> &Cond,
                          SmallVectorImpl<MachineInstr *> &CondBranches,
                          bool AllowModify) const;

lib/Target/X86/X86InstrInfo.cpp

AddTableEntry(MemOp2RegOpTable, Entry.RegOp, Entry.MemOp,
                   // Index 3, folded load
                   Entry.Flags | TB_INDEX_3 | TB_FOLDED_LOAD);
 
   for (const X86MemoryFoldTableEntry &Entry : MemoryFoldTable4)
     AddTableEntry(MemOp2RegOpTable, Entry.RegOp, Entry.MemOp,
                   // Index 4, folded load
                   Entry.Flags | TB_INDEX_4 | TB_FOLDED_LOAD);
 
+  // Sort the memory->reg unfold table.
+  array_pod_sort(MemOp2RegOpTable.begin(), MemOp2RegOpTable.end());
+
 #ifndef NDEBUG
   // Make sure the tables are sorted.
   static bool FoldTablesChecked = false;
   if (!FoldTablesChecked) {
+    assert(std::adjacent_find(MemOp2RegOpTable.begin(),
+                              MemOp2RegOpTable.end()) ==
+           MemOp2RegOpTable.end() &&
+           "MemOp2RegOpTable is not unique!");
     assert(std::is_sorted(std::begin(MemoryFoldTable2Addr),
                           std::end(MemoryFoldTable2Addr)) &&
            std::adjacent_find(std::begin(MemoryFoldTable2Addr),
                               std::end(MemoryFoldTable2Addr)) ==
            std::end(MemoryFoldTable2Addr) &&
            "MemoryFoldTable2Addr is not sorted and unique!");
     assert(std::is_sorted(std::begin(MemoryFoldTable0),
                           std::end(MemoryFoldTable0)) &&
if (!FoldTablesChecked) {
     FoldTablesChecked = true;
   }
 #endif
 }
 
 void
 X86InstrInfo::AddTableEntry(MemOp2RegOpTableType &M2RTable,
                             uint16_t RegOp, uint16_t MemOp, uint16_t Flags) {
-  if ((Flags & TB_NO_REVERSE) == 0) {
-    assert(!M2RTable.count(MemOp) &&
-         "Duplicated entries in unfolding maps?");
-    M2RTable[MemOp] = std::make_pair(RegOp, Flags);
-  }
+  if ((Flags & TB_NO_REVERSE) == 0)
+    M2RTable.push_back({MemOp, RegOp, Flags});
+
+const X86InstrInfo::MemOp2RegOpTableTypeEntry *
+X86InstrInfo::lookupUnfoldTable(unsigned MemOp) const {
+  auto I = std::lower_bound(MemOp2RegOpTable.begin(), MemOp2RegOpTable.end(),
+                            MemOp);
+  if (I != MemOp2RegOpTable.end() && I->MemOp == MemOp)
+    return &*I;
+  return nullptr;
 }
 
 static const X86MemoryFoldTableEntry *
 lookupFoldTable(ArrayRef<X86MemoryFoldTableEntry> Table, unsigned RegOp) {
   const X86MemoryFoldTableEntry *Data = std::lower_bound(Table.begin(),
                                                          Table.end(),
                                                          RegOp);
   if (Data != Table.end() && Data->RegOp == RegOp &&
MachineInstr *X86InstrInfo::foldMemoryOperandImpl(
   }
   return foldMemoryOperandImpl(MF, MI, Ops[0], MOs, InsertPt,
                                /*Size=*/0, Alignment, /*AllowCommute=*/true);
 }
 
 bool X86InstrInfo::unfoldMemoryOperand(
     MachineFunction &MF, MachineInstr &MI, unsigned Reg, bool UnfoldLoad,
     bool UnfoldStore, SmallVectorImpl<MachineInstr *> &NewMIs) const {
-  auto I = MemOp2RegOpTable.find(MI.getOpcode());
-  if (I == MemOp2RegOpTable.end())
+  const MemOp2RegOpTableTypeEntry *I = lookupUnfoldTable(MI.getOpcode());
+  if (I == nullptr)
     return false;
-  unsigned Opc = I->second.first;
-  unsigned Index = I->second.second & TB_INDEX_MASK;
-  bool FoldedLoad = I->second.second & TB_FOLDED_LOAD;
-  bool FoldedStore = I->second.second & TB_FOLDED_STORE;
+  unsigned Opc = I->RegOp;
+  unsigned Index = I->Flags & TB_INDEX_MASK;
+  bool FoldedLoad = I->Flags & TB_FOLDED_LOAD;
+  bool FoldedStore = I->Flags & TB_FOLDED_STORE;
   if (UnfoldLoad && !FoldedLoad)
     return false;
   UnfoldLoad &= FoldedLoad;
   if (UnfoldStore && !FoldedStore)
     return false;
   UnfoldStore &= FoldedStore;
 
   const MCInstrDesc &MCID = get(Opc);

 }
 
 bool
 X86InstrInfo::unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
                                   SmallVectorImpl<SDNode*> &NewNodes) const {
   if (!N->isMachineOpcode())
     return false;
 
-  auto I = MemOp2RegOpTable.find(N->getMachineOpcode());
-  if (I == MemOp2RegOpTable.end())
+  const MemOp2RegOpTableTypeEntry *I = lookupUnfoldTable(N->getMachineOpcode());
+  if (I == nullptr)
     return false;
-  unsigned Opc = I->second.first;
-  unsigned Index = I->second.second & TB_INDEX_MASK;
-  bool FoldedLoad = I->second.second & TB_FOLDED_LOAD;
-  bool FoldedStore = I->second.second & TB_FOLDED_STORE;
+  unsigned Opc = I->RegOp;
+  unsigned Index = I->Flags & TB_INDEX_MASK;
+  bool FoldedLoad = I->Flags & TB_FOLDED_LOAD;
+  bool FoldedStore = I->Flags & TB_FOLDED_STORE;
   const MCInstrDesc &MCID = get(Opc);
   MachineFunction &MF = DAG.getMachineFunction();
   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
   const TargetRegisterClass *RC = getRegClass(MCID, Index, &RI, MF);
   unsigned NumDefs = MCID.NumDefs;
   std::vector<SDValue> AddrOps;
   std::vector<SDValue> BeforeOps;
   std::vector<SDValue> AfterOps;
X86InstrInfo::unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
   }
 
   return true;
 }
 
 unsigned X86InstrInfo::getOpcodeAfterMemoryUnfold(unsigned Opc,
                                       bool UnfoldLoad, bool UnfoldStore,
                                       unsigned *LoadRegIndex) const {
-  auto I = MemOp2RegOpTable.find(Opc);
-  if (I == MemOp2RegOpTable.end())
+  const MemOp2RegOpTableTypeEntry *I = lookupUnfoldTable(Opc);
+  if (I == nullptr)
     return 0;
-  bool FoldedLoad = I->second.second & TB_FOLDED_LOAD;
-  bool FoldedStore = I->second.second & TB_FOLDED_STORE;
+  bool FoldedLoad = I->Flags & TB_FOLDED_LOAD;
+  bool FoldedStore = I->Flags & TB_FOLDED_STORE;
   if (UnfoldLoad && !FoldedLoad)
     return 0;
   if (UnfoldStore && !FoldedStore)
     return 0;
   if (LoadRegIndex)
-    *LoadRegIndex = I->second.second & TB_INDEX_MASK;
-  return I->second.first;
+    *LoadRegIndex = I->Flags & TB_INDEX_MASK;
+  return I->RegOp;
 }
 
 bool
 X86InstrInfo::areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2,
                                      int64_t &Offset1, int64_t &Offset2) const {
   if (!Load1->isMachineOpcode() || !Load2->isMachineOpcode())
     return false;
   unsigned Opc1 = Load1->getMachineOpcode();