From f8bab1ce0cac4c802372af46cd4c0045eab6fdb4 Mon Sep 17 00:00:00 2001 From: Tim Northover Date: Mon, 29 Aug 2016 21:00:00 +0000 Subject: [PATCH] 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/CodeGen/GlobalISel/MachineLegalizer.h | 52 +++++++++++++--------- llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp | 28 +++++++----- .../CodeGen/GlobalISel/MachineLegalizerTest.cpp | 2 + 3 files changed, 50 insertions(+), 32 deletions(-) diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h index c6f453c..1195fb6 100644 --- a/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h +++ b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h @@ -17,6 +17,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/CodeGen/LowLevelType.h" +#include "llvm/Target/TargetOpcodes.h" #include #include @@ -44,21 +45,6 @@ struct InstrAspect { } }; -template <> struct DenseMapInfo { - static inline InstrAspect getEmptyKey() { return {-1u, 0, LLT{}}; } - - static inline InstrAspect getTombstoneKey() { return {-2u, 0, LLT{}}; } - - static unsigned getHashValue(const InstrAspect &Val) { - return DenseMapInfo>::getHashValue( - {(uint64_t)Val.Opcode << 32 | Val.Idx, Val.Type}); - } - - static bool isEqual(const InstrAspect &LHS, const InstrAspect &RHS) { - return LHS == RHS; - } -}; - class MachineLegalizer { public: enum LegalizeAction : std::uint8_t { @@ -103,6 +89,9 @@ public: /// This operation is completely unsupported on the target. A programming /// error has occurred. Unsupported, + + /// Sentinel value for when no action was found in the specified table. + NotFound, }; MachineLegalizer(); @@ -116,7 +105,10 @@ public: /// representation. void setAction(const InstrAspect &Aspect, LegalizeAction Action) { TablesInitialized = false; - Actions[Aspect] = Action; + unsigned Opcode = Aspect.Opcode - FirstOp; + if (Actions[Opcode].size() <= Aspect.Idx) + Actions[Opcode].resize(Aspect.Idx + 1); + Actions[Aspect.Opcode - FirstOp][Aspect.Idx][Aspect.Type] = Action; } /// If an operation on a given vector type (say ) isn't explicitly @@ -152,11 +144,12 @@ public: LLT findLegalType(const InstrAspect &Aspect, std::function NextType) const { LegalizeAction Action; + const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx]; LLT Ty = Aspect.Type; do { Ty = NextType(Ty); - auto ActionIt = Actions.find({Aspect.Opcode, Aspect.Idx, Ty}); - if (ActionIt == Actions.end()) + auto ActionIt = Map.find(Ty); + if (ActionIt == Map.end()) Action = DefaultActions.find(Aspect.Opcode)->second; else Action = ActionIt->second; @@ -173,13 +166,32 @@ public: return std::make_pair(Action, findLegalType(Aspect, Action)); } + /// Find the specified \p Aspect in the primary (explicitly set) Actions + /// table. Returns either the action the target requested or NotFound if there + /// was no setAction call. + LegalizeAction findInActions(const InstrAspect &Aspect) const { + if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp) + return NotFound; + if (Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size()) + return NotFound; + const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx]; + auto ActionIt = Map.find(Aspect.Type); + if (ActionIt == Map.end()) + return NotFound; + + return ActionIt->second; + } + bool isLegal(const MachineInstr &MI) const; private: - typedef DenseMap ActionMap; + static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START; + static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END; + + typedef DenseMap TypeMap; typedef DenseMap, LegalizeAction> SIVActionMap; - ActionMap Actions; + SmallVector Actions[LastOp - FirstOp + 1]; SIVActionMap ScalarInVectorActions; DenseMap, uint16_t> MaxLegalVectorElts; DenseMap DefaultActions; diff --git a/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp b/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp index 11b04f4..baef765 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; diff --git a/llvm/unittests/CodeGen/GlobalISel/MachineLegalizerTest.cpp b/llvm/unittests/CodeGen/GlobalISel/MachineLegalizerTest.cpp index f7544af..f0b7573 100644 --- a/llvm/unittests/CodeGen/GlobalISel/MachineLegalizerTest.cpp +++ b/llvm/unittests/CodeGen/GlobalISel/MachineLegalizerTest.cpp @@ -21,6 +21,7 @@ using llvm::MachineLegalizer::LegalizeAction::MoreElements; using llvm::MachineLegalizer::LegalizeAction::Libcall; using llvm::MachineLegalizer::LegalizeAction::Custom; using llvm::MachineLegalizer::LegalizeAction::Unsupported; +using llvm::MachineLegalizer::LegalizeAction::NotFound; // Define a couple of pretty printers to help debugging when things go wrong. namespace llvm { @@ -36,6 +37,7 @@ operator<<(std::ostream &OS, const llvm::MachineLegalizer::LegalizeAction Act) { case Libcall: OS << "Libcall"; break; case Custom: OS << "Custom"; break; case Unsupported: OS << "Unsupported"; break; + case NotFound: OS << "NotFound"; } return OS; } -- 2.7.4