[globalisel][legalizer] Adapt LegalizerInfo to support inter-type dependencies and other things.

Summary:
As discussed in D42244, we have difficulty describing the legality of some
operations. We're not able to specify relationships between types.
For example, declaring the following
  setAction({..., 0, s32}, Legal)
  setAction({..., 0, s64}, Legal)
  setAction({..., 1, s32}, Legal)
  setAction({..., 1, s64}, Legal)
currently declares these type combinations as legal:
  {s32, s32}
  {s64, s32}
  {s32, s64}
  {s64, s64}
but we currently have no means to say that, for example, {s64, s32} is
not legal. Some operations such as G_INSERT/G_EXTRACT/G_MERGE_VALUES/
G_UNMERGE_VALUES have relationships between the types that are currently
described incorrectly.
    
Additionally, G_LOAD/G_STORE currently have no means to legalize non-atomics
differently to atomics. The necessary information is in the MMO but we have no
way to use this in the legalizer. Similarly, there is currently no way for the
register type and the memory type to differ so there is no way to cleanly
represent extending-load/truncating-store in a way that can't be broken by
optimizers (resulting in illegal MIR).

It's also difficult to control the legalization strategy. We've added support
for legalizing non-power of 2 types but there's still some hardcoded assumptions
about the strategy. The main one I've noticed is that type0 is always legalized
before type1 which is not a good strategy for `type0 = G_EXTRACT type1, ...` if
you need to widen the container. It will converge on the same result eventually
but it will take a much longer route when legalizing type0 than if you legalize
type1 first.

Lastly, the definition of legality and the legalization strategy is kept
separate which is not ideal. It's helpful to be able to look at a one piece of
code and see both what is legal and the method the legalizer will use to make
illegal MIR more legal.

This patch adds a layer onto the LegalizerInfo (to be removed when all targets
have been migrated) which resolves all these issues.

Here are the rules for shift and division:
  for (unsigned BinOp : {G_LSHR, G_ASHR, G_SDIV, G_UDIV})
    getActionDefinitions(BinOp)
        .legalFor({s32, s64})     // If type0 is s32/s64 then it's Legal
        .clampScalar(0, s32, s64) // If type0 is <s32 then WidenScalar to s32
                                  // If type0 is >s64 then NarrowScalar to s64
        .widenScalarToPow2(0)     // Round type0 scalars up to powers of 2
        .unsupported();           // Otherwise, it's unsupported
This describes everything needed to both define legality and describe how to
make illegal things legal.

Here's an example of a complex rule:
  getActionDefinitions(G_INSERT)
      .unsupportedIf([=](const LegalityQuery &Query) {
        // If type0 is smaller than type1 then it's unsupported
        return Query.Types[0].getSizeInBits() <= Query.Types[1].getSizeInBits();
      })
      .legalIf([=](const LegalityQuery &Query) {
        // If type0 is s32/s64/p0 and type1 is a power of 2 other than 2 or 4 then it's legal
        // We don't need to worry about large type1's because unsupportedIf caught that.
        const LLT &Ty0 = Query.Types[0];
        const LLT &Ty1 = Query.Types[1];
        if (Ty0 != s32 && Ty0 != s64 && Ty0 != p0)
          return false;
        return isPowerOf2_32(Ty1.getSizeInBits()) &&
               (Ty1.getSizeInBits() == 1 || Ty1.getSizeInBits() >= 8);
      })
      .clampScalar(0, s32, s64)
      .widenScalarToPow2(0)
      .maxScalarIf(typeInSet(0, {s32}), 1, s16) // If type0 is s32 and type1 is bigger than s16 then NarrowScalar type1 to s16
      .maxScalarIf(typeInSet(0, {s64}), 1, s32) // If type0 is s64 and type1 is bigger than s32 then NarrowScalar type1 to s32
      .widenScalarToPow2(1)                     // Round type1 scalars up to powers of 2
      .unsupported();
This uses a lambda to say that G_INSERT is unsupported when type0 is bigger than
type1 (in practice, this would be a default rule for G_INSERT). It also uses one
to describe the legal cases. This particular predicate is equivalent to:
  .legalFor({{s32, s1}, {s32, s8}, {s32, s16}, {s64, s1}, {s64, s8}, {s64, s16}, {s64, s32}})

In terms of performance, I saw a slight (~6%) performance improvement when
AArch64 was around 30% ported but it's pretty much break even right now.
I'm going to take a look at constexpr as a means to reduce the initialization
cost.

Future work:
* Make it possible for opcodes to share rulesets. There's no need for
  G_LSHR/G_ASHR/G_SDIV/G_UDIV to have separate rule and ruleset objects. There's
  no technical barrier to this, it just hasn't been done yet.
* Replace the type-index numbers with an enum to get .clampScalar(Type0, s32, s64)
* Better names for things like .maxScalarIf() (clampMaxScalar?) and the vector rules.
* Improve initialization cost using constexpr

Possible future work:
* It's possible to make these rulesets change the MIR directly instead of
  returning a description of how to change the MIR. This should remove a little
  overhead caused by parsing the description and routing to the right code, but
  the real motivation is that it removes the need for LegalizeAction::Custom.
  With Custom removed, there's no longer a requirement that Custom legalization
  change the opcode to something that's considered legal.

Reviewers: ab, t.p.northover, qcolombet, rovka, aditya_nandakumar, volkan, reames, bogner

Reviewed By: bogner

Subscribers: hintonda, bogner, aemerson, mgorny, javed.absar, kristof.beyls, llvm-commits

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

llvm-svn: 323681

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};