From d22ad8568c463157d0064611509c92d7e217c33b Mon Sep 17 00:00:00 2001
From: Craig Topper <craig.topper@intel.com>
Date: Wed, 20 Jun 2018 04:32:04 +0000
Subject: [PATCH] [X86] Use binary search of the EVEX->VEX static tables
 instead of populating two DenseMaps for lookups

Summary:
After r335018, the static tables are guaranteed sorted by the EVEX opcode to convert. We can use this to do a binary search and remove the need for any secondary data structures.

Right now one table is 736 entries and the other is 482 entries. It might make sense to merge the two tables as a follow up. The effort it takes to select the table is probably similar to the extra binary search step it would require for a larger table.

I haven't done any measurements to see if this has any effect on compile time, but I don't imagine that EVEX->VEX conversion is a place we spend a lot of time.

Reviewers: RKSimon, spatel, chandlerc

Reviewed By: RKSimon

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D48312

llvm-svn: 335092
---
 llvm/lib/Target/X86/X86EvexToVex.cpp | 67 ++++++++++++++++--------------------
 1 file changed, 29 insertions(+), 38 deletions(-)

diff --git a/llvm/lib/Target/X86/X86EvexToVex.cpp b/llvm/lib/Target/X86/X86EvexToVex.cpp
index b71b0c6..fb7217b2 100644
--- a/llvm/lib/Target/X86/X86EvexToVex.cpp
+++ b/llvm/lib/Target/X86/X86EvexToVex.cpp
@@ -42,6 +42,15 @@ using namespace llvm;
 struct X86EvexToVexCompressTableEntry {
   uint16_t EvexOpcode;
   uint16_t VexOpcode;
+
+  bool operator<(const X86EvexToVexCompressTableEntry &RHS) const {
+    return EvexOpcode < RHS.EvexOpcode;
+  }
+
+  friend bool operator<(const X86EvexToVexCompressTableEntry &TE,
+                        unsigned Opc) {
+    return TE.EvexOpcode < Opc;
+  }
 };
 #include "X86GenEVEX2VEXTables.inc"
 
@@ -54,35 +63,15 @@ namespace {
 
 class EvexToVexInstPass : public MachineFunctionPass {
 
-  /// X86EvexToVexCompressTable - Evex to Vex encoding opcode map.
-  using EvexToVexTableType = DenseMap<unsigned, uint16_t>;
-  EvexToVexTableType EvexToVex128Table;
-  EvexToVexTableType EvexToVex256Table;
-
   /// For EVEX instructions that can be encoded using VEX encoding, replace
   /// them by the VEX encoding in order to reduce size.
   bool CompressEvexToVexImpl(MachineInstr &MI) const;
 
-  /// For initializing the hash map tables of all AVX-512 EVEX
-  /// corresponding to AVX/AVX2 opcodes.
-  void AddTableEntry(EvexToVexTableType &EvexToVexTable, uint16_t EvexOp,
-                     uint16_t VexOp);
-
 public:
   static char ID;
 
   EvexToVexInstPass() : MachineFunctionPass(ID) {
     initializeEvexToVexInstPassPass(*PassRegistry::getPassRegistry());
-
-    // Initialize the EVEX to VEX 128 table map.
-    for (X86EvexToVexCompressTableEntry Entry : X86EvexToVex128CompressTable) {
-      AddTableEntry(EvexToVex128Table, Entry.EvexOpcode, Entry.VexOpcode);
-    }
-
-    // Initialize the EVEX to VEX 256 table map.
-    for (X86EvexToVexCompressTableEntry Entry : X86EvexToVex256CompressTable) {
-      AddTableEntry(EvexToVex256Table, Entry.EvexOpcode, Entry.VexOpcode);
-    }
   }
 
   StringRef getPassName() const override { return EVEX2VEX_DESC; }
@@ -127,11 +116,6 @@ bool EvexToVexInstPass::runOnMachineFunction(MachineFunction &MF) {
   return Changed;
 }
 
-void EvexToVexInstPass::AddTableEntry(EvexToVexTableType &EvexToVexTable,
-                                      uint16_t EvexOp, uint16_t VexOp) {
-  EvexToVexTable[EvexOp] = VexOp;
-}
-
 static bool usesExtendedRegister(const MachineInstr &MI) {
   auto isHiRegIdx = [](unsigned Reg) {
     // Check for XMM register with indexes between 16 - 31.
@@ -253,24 +237,31 @@ bool EvexToVexInstPass::CompressEvexToVexImpl(MachineInstr &MI) const {
   if (Desc.TSFlags & X86II::EVEX_L2)
     return false;
 
-  unsigned NewOpc = 0;
+#ifndef NDEBUG
+  // Make sure the tables are sorted.
+  static bool TableChecked = false;
+  if (!TableChecked) {
+    assert(std::is_sorted(std::begin(X86EvexToVex128CompressTable),
+                          std::end(X86EvexToVex128CompressTable)) &&
+           "X86EvexToVex128CompressTable is not sorted!");
+    assert(std::is_sorted(std::begin(X86EvexToVex256CompressTable),
+                          std::end(X86EvexToVex256CompressTable)) &&
+           "X86EvexToVex256CompressTable is not sorted!");
+    TableChecked = true;
+  }
+#endif
 
   // Use the VEX.L bit to select the 128 or 256-bit table.
-  if (Desc.TSFlags & X86II::VEX_L) {
-    // Search for opcode in the EvexToVex256 table.
-    auto It = EvexToVex256Table.find(MI.getOpcode());
-    if (It != EvexToVex256Table.end())
-      NewOpc = It->second;
-  } else {
-    // Search for opcode in the EvexToVex128 table.
-    auto It = EvexToVex128Table.find(MI.getOpcode());
-    if (It != EvexToVex128Table.end())
-      NewOpc = It->second;
-  }
+  ArrayRef<X86EvexToVexCompressTableEntry> Table =
+    (Desc.TSFlags & X86II::VEX_L) ? makeArrayRef(X86EvexToVex256CompressTable)
+                                  : makeArrayRef(X86EvexToVex128CompressTable);
 
-  if (!NewOpc)
+  auto I = std::lower_bound(Table.begin(), Table.end(), MI.getOpcode());
+  if (I == Table.end() || I->EvexOpcode != MI.getOpcode())
     return false;
 
+  unsigned NewOpc = I->VexOpcode;
+
   if (usesExtendedRegister(MI))
     return false;
 
-- 
2.7.4