From f8bab1ce0cac4c802372af46cd4c0045eab6fdb4 Mon Sep 17 00:00:00 2001
From: Tim Northover <tnorthover@apple.com>
Date: Mon, 29 Aug 2016 21:00:00 +0000
Subject: GlobalISel: use multi-dimensional arrays for legalize actions.

Instead of putting all possible requests into a single table, we can perform
the extremely dense lookup based on opcode and type-index in constant time
using multi-dimensional array-like things.

This roughly halves the time spent doing legalization, which was dominated by
queries against the Actions table.

llvm-svn: 280011
---
 llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp | 28 ++++++++++++++----------
 1 file changed, 16 insertions(+), 12 deletions(-)

(limited to 'llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp')

diff --git a/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp b/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp
index 11b04f491ee..baef7657eac 100644
--- a/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp
@@ -17,9 +17,9 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/CodeGen/GlobalISel/MachineLegalizer.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/ValueTypes.h"
-#include "llvm/CodeGen/GlobalISel/MachineLegalizer.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Target/TargetOpcodes.h"
 using namespace llvm;
@@ -39,14 +39,18 @@ MachineLegalizer::MachineLegalizer() : TablesInitialized(false) {
 }
 
 void MachineLegalizer::computeTables() {
-  for (auto &Op : Actions) {
-    LLT Ty = Op.first.Type;
-    if (!Ty.isVector())
-      continue;
-
-    auto &Entry = MaxLegalVectorElts[std::make_pair(Op.first.Opcode,
-                                                    Ty.getElementType())];
-    Entry = std::max(Entry, Ty.getNumElements());
+  for (unsigned Opcode = 0; Opcode <= LastOp - FirstOp; ++Opcode) {
+    for (unsigned Idx = 0; Idx != Actions[Opcode].size(); ++Idx) {
+      for (auto &Action : Actions[Opcode][Idx]) {
+        LLT Ty = Action.first;
+        if (!Ty.isVector())
+          continue;
+
+        auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
+                                                        Ty.getElementType())];
+        Entry = std::max(Entry, Ty.getNumElements());
+      }
+    }
   }
 
   TablesInitialized = true;
@@ -68,9 +72,9 @@ MachineLegalizer::getAction(const InstrAspect &Aspect) const {
       Aspect.Opcode == TargetOpcode::G_EXTRACT)
     return std::make_pair(Legal, Aspect.Type);
 
-  auto ActionIt = Actions.find(Aspect);
-  if (ActionIt != Actions.end())
-    return findLegalAction(Aspect, ActionIt->second);
+  LegalizeAction Action = findInActions(Aspect);
+  if (Action != NotFound)
+    return findLegalAction(Aspect, Action);
 
   unsigned Opcode = Aspect.Opcode;
   LLT Ty = Aspect.Type;
-- 
cgit v1.2.3