4 files changed, 228 insertions, 6 deletions
diff --git a/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt b/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
index e68ed179558..4c1da3756b1 100644
--- a/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -6,8 +6,10 @@ add_llvm_library(LLVMGlobalISel
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
-        LegalizerHelper.cpp
+        LegalityPredicates.cpp
+        LegalizeMutations.cpp
         Legalizer.cpp
+        LegalizerHelper.cpp
         LegalizerInfo.cpp
         Localizer.cpp
         MachineIRBuilder.cpp
diff --git a/llvm/lib/CodeGen/GlobalISel/LegalityPredicates.cpp b/llvm/lib/CodeGen/GlobalISel/LegalityPredicates.cpp
new file mode 100644
index 00000000000..0d30e0781cd
--- /dev/null
+++ b/llvm/lib/CodeGen/GlobalISel/LegalityPredicates.cpp
@@ -0,0 +1,78 @@
+//===- lib/CodeGen/GlobalISel/LegalizerPredicates.cpp - Predicates --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// A library of predicate factories to use for LegalityPredicate.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
+
+using namespace llvm;
+
+LegalityPredicate
+LegalityPredicates::all(LegalityPredicate P0, LegalityPredicate P1) {
+  return [=](const LegalityQuery &Query) {
+    return P0(Query) && P1(Query);
+  };
+}
+
+LegalityPredicate
+LegalityPredicates::typeInSet(unsigned TypeIdx,
+                              std::initializer_list<LLT> TypesInit) {
+  SmallVector<LLT, 4> Types = TypesInit;
+  return [=](const LegalityQuery &Query) {
+    return std::find(Types.begin(), Types.end(), Query.Types[TypeIdx]) != Types.end();
+  };
+}
+
+LegalityPredicate LegalityPredicates::typePairInSet(
+    unsigned TypeIdx0, unsigned TypeIdx1,
+    std::initializer_list<std::pair<LLT, LLT>> TypesInit) {
+  SmallVector<std::pair<LLT, LLT>, 4> Types = TypesInit;
+  return [=](const LegalityQuery &Query) {
+    std::pair<LLT, LLT> Match = {Query.Types[TypeIdx0], Query.Types[TypeIdx1]};
+    return std::find(Types.begin(), Types.end(), Match) != Types.end();
+  };
+}
+
+LegalityPredicate LegalityPredicates::isScalar(unsigned TypeIdx) {
+  return [=](const LegalityQuery &Query) {
+    return Query.Types[TypeIdx].isScalar();
+  };
+}
+
+LegalityPredicate LegalityPredicates::narrowerThan(unsigned TypeIdx,
+                                                   unsigned Size) {
+  return [=](const LegalityQuery &Query) {
+    const LLT &QueryTy = Query.Types[TypeIdx];
+    return QueryTy.isScalar() && QueryTy.getSizeInBits() < Size;
+  };
+}
+
+LegalityPredicate LegalityPredicates::widerThan(unsigned TypeIdx,
+                                                unsigned Size) {
+  return [=](const LegalityQuery &Query) {
+    const LLT &QueryTy = Query.Types[TypeIdx];
+    return QueryTy.isScalar() && QueryTy.getSizeInBits() > Size;
+  };
+}
+
+LegalityPredicate LegalityPredicates::sizeNotPow2(unsigned TypeIdx) {
+  return [=](const LegalityQuery &Query) {
+    const LLT &QueryTy = Query.Types[TypeIdx];
+    return QueryTy.isScalar() && !isPowerOf2_32(QueryTy.getSizeInBits());
+  };
+}
+
+LegalityPredicate LegalityPredicates::numElementsNotPow2(unsigned TypeIdx) {
+  return [=](const LegalityQuery &Query) {
+    const LLT &QueryTy = Query.Types[TypeIdx];
+    return QueryTy.isVector() && isPowerOf2_32(QueryTy.getNumElements());
+  };
+}
diff --git a/llvm/lib/CodeGen/GlobalISel/LegalizeMutations.cpp b/llvm/lib/CodeGen/GlobalISel/LegalizeMutations.cpp
new file mode 100644
index 00000000000..961988515e5
--- /dev/null
+++ b/llvm/lib/CodeGen/GlobalISel/LegalizeMutations.cpp
@@ -0,0 +1,44 @@
+//===- lib/CodeGen/GlobalISel/LegalizerMutations.cpp - Mutations ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// A library of mutation factories to use for LegalityMutation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
+
+using namespace llvm;
+
+LegalizeMutation LegalizeMutations::identity(unsigned TypeIdx, LLT Ty) {
+  return
+      [=](const LegalityQuery &Query) { return std::make_pair(TypeIdx, Ty); };
+}
+
+LegalizeMutation LegalizeMutations::widenScalarToNextPow2(unsigned TypeIdx,
+                                                          unsigned Min) {
+  return [=](const LegalityQuery &Query) {
+    unsigned NewSizeInBits =
+        1 << Log2_32_Ceil(Query.Types[TypeIdx].getSizeInBits());
+    if (NewSizeInBits < Min)
+      NewSizeInBits = Min;
+    return std::make_pair(TypeIdx, LLT::scalar(NewSizeInBits));
+  };
+}
+
+LegalizeMutation LegalizeMutations::moreElementsToNextPow2(unsigned TypeIdx,
+                                                           unsigned Min) {
+  return [=](const LegalityQuery &Query) {
+    const LLT &VecTy = Query.Types[TypeIdx];
+    unsigned NewNumElements = 1 << Log2_32_Ceil(VecTy.getNumElements());
+    if (NewNumElements < Min)
+      NewNumElements = Min;
+    return std::make_pair(
+        TypeIdx, LLT::vector(NewNumElements, VecTy.getScalarSizeInBits()));
+  };
+}
diff --git a/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
index 12f5524aa8c..054acc1d2fe 100644
--- a/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
@@ -24,6 +24,7 @@
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/MC/MCInstrDesc.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include "llvm/Support/MathExtras.h"
@@ -33,6 +34,40 @@
 using namespace llvm;
 using namespace LegalizeActions;
 
+#define DEBUG_TYPE "legalizer-info"
+
+raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
+  OS << Opcode << ", {";
+  for (const auto &Type : Types) {
+    OS << Type << ", ";
+  }
+  OS << "}";
+  return OS;
+}
+
+LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
+  DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
+        dbgs() << "\n");
+  if (Rules.empty()) {
+    DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
+    return {LegalizeAction::UseLegacyRules, 0, LLT{}};
+  }
+  for (const auto &Rule : Rules) {
+    if (Rule.match(Query)) {
+      DEBUG(dbgs() << ".. match\n");
+      std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
+      DEBUG(dbgs() << ".. .. " << (unsigned)Rule.getAction() << ", "
+                   << Mutation.first << ", " << Mutation.second << "\n");
+      assert(Query.Types[Mutation.first] != Mutation.second &&
+             "Simple loop detected");
+      return {Rule.getAction(), Mutation.first, Mutation.second};
+    } else
+      DEBUG(dbgs() << ".. no match\n");
+  }
+  DEBUG(dbgs() << ".. unsupported\n");
+  return {LegalizeAction::Unsupported, 0, LLT{}};
+}
+
 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
   // Set defaults.
   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
@@ -188,17 +223,79 @@ static LLT getTypeFromTypeIdx(const MachineInstr &MI,
   return MRI.getType(MI.getOperand(OpIdx).getReg());
 }
 
-LegalizerInfo::LegalizeActionStep
+unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
+  assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
+  return Opcode - FirstOp;
+}
+
+unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
+  unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
+  if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
+    DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
+                 << "\n");
+    OpcodeIdx = getOpcodeIdxForOpcode(Alias);
+    DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to "
+                 << RulesForOpcode[OpcodeIdx].getAlias() << "\n");
+    assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
+  }
+
+  return OpcodeIdx;
+}
+
+const LegalizeRuleSet &
+LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
+  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
+  return RulesForOpcode[OpcodeIdx];
+}
+
+LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
+  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
+  auto &Result = RulesForOpcode[OpcodeIdx];
+  assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
+  return Result;
+}
+
+LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
+    std::initializer_list<unsigned> Opcodes) {
+  unsigned Representative = *Opcodes.begin();
+
+  for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
+    aliasActionDefinitions(Representative, *I);
+
+  auto &Return = getActionDefinitionsBuilder(Representative);
+  Return.setIsAliasedByAnother();
+  return Return;
+}
+
+void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
+                                           unsigned OpcodeFrom) {
+  assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
+  assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
+  const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
+  RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
+}
+
+LegalizeActionStep
 LegalizerInfo::getAction(const LegalityQuery &Query) const {
+  LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
+  if (Step.Action != LegalizeAction::UseLegacyRules) {
+    return Step;
+  }
+
   for (unsigned i = 0; i < Query.Types.size(); ++i) {
     auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
-    if (Action.first != Legal)
+    if (Action.first != Legal) {
+      DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
+                   << (unsigned)Action.first << ", " << Action.second << "\n");
       return {Action.first, i, Action.second};
+    } else
+      DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
   }
+  DEBUG(dbgs() << ".. (legacy) Legal\n");
   return {Legal, 0, LLT{}};
 }
 
-LegalizerInfo::LegalizeActionStep
+LegalizeActionStep
 LegalizerInfo::getAction(const MachineInstr &MI,
                          const MachineRegisterInfo &MRI) const {
   SmallVector<LLT, 2> Types;
@@ -323,6 +420,7 @@ LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
   case Unsupported:
     return {Size, Unsupported};
   case NotFound:
+  case UseLegacyRules:
     llvm_unreachable("NotFound");
   }
   llvm_unreachable("Action has an unknown enum value");
@@ -333,7 +431,7 @@ LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
     return {NotFound, LLT()};
-  const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
+  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
   if (Aspect.Type.isPointer() &&
       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
           AddrSpace2PointerActions[OpcodeIdx].end()) {
@@ -364,7 +462,7 @@ LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
   // lanes in the vector.
   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
     return {NotFound, Aspect.Type};
-  const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
+  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
   const unsigned TypeIdx = Aspect.Idx;
   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
     return {NotFound, Aspect.Type};