GlobalISel: legalization policy class

[t.p.northover]

Summary

Hi,

As suggested in D21534, I've split off the class deciding on how legalization should proceed (plus the legalizeInstr stub) into a separate unit-tested patch.

I've addressed most of the relevant comments from the original diff, with two outstanding issues:

• We'll need a richer setAction interface to cope with multiple types on instructions.
• Similarly, we'll need to be able to cope with per-address-space legalization.

I fully agree with both of these, but think they'll probably be added organically as we grow (certainly the first is needed for AArch64, and I'll make sure the second doesn't get neglected).

As with most of the other GlobalISel things, it's pretty rough around the edges as a prototype and I'm hoping to fill in the details as-needed and as-testable.

Tim.

[eli.friedman]

Are you sure you uploaded the right patch here? This isn't against trunk, as far as I can tell.

[t.p.northover]

Ah sorry, it does depend on D22008. I did mean to mention that but forgot. Together they should apply cleanly.

[arsenm]

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

68

There's one value left in uint8_t, can we make it be unsupported? We custom lower a variety of operations now just to emit an error saying they don't work

lib/CodeGen/GlobalISel/MachineLegalizer.cpp

81–82

No else after return

[t.p.northover]

Add Unsupported class for error reporting.

[t.p.northover]

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

68

Bother, I hadn't ignored you last time but that seems to have ended up in the wrong patch. I'll relocate it.

[t.p.northover]

Sorry, wrong diff. And I think I addressed Eli's comment too.

[t.p.northover]

Sorry, complete mess-up with the last revision. I don't think anything substantial has changed here yet I'm just trying to undo my last upload.

[t.p.northover]

Ping? I'm getting patches stacking on top of this (mostly straightforward themselves, but difficult to keep rebasing and making progress while the low-level bits are unsettled).

[qcolombet]

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

84

I found the returns comment hard to understand :).
I believe that means MI has been legalized successfully?
What happen when we return false? In particular is the function left untouched as nothing as happened or are we in a strange state that we may not be able to recover?

86

ancillary :).

89

Shouldn’t we hide this function?

For instance, I would have expected that the class call it internally the first time it does a query.
Note: I understand why for compile time reason we would like to expose this API. I am just nervous that if we forget to do it, we end up with a bunch of hard to understand errors.
Alternative, could you add an assert of some sort catch that?

110

Those are the queries you were talking about in computeTables, right?

include/llvm/CodeGen/LowLevelType.h

89

This diff shouldn’t be in that patch, right?

[t.p.northover]

Updated diff coming soon (I wish you could both answer and upload a patch at the same time).

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

84

The intent is that legalizeInstr will always succeed. False indicates the instruction was already legal (and so no changes were made). I'll clarify the wording.

86

You know, I thought so too! But Matt quite tactfully pointed out that I'd been mistaken all my life.

89

I'm not too worried about the errors, it's going to be once-per-backend which is pretty miniscule. I'll put an assert in I think.

110

Yep.

include/llvm/CodeGen/LowLevelType.h

89

Probably the previous one (though It think this might be the first use of that function?). I'll move it.

[t.p.northover]

Updating diff with latest comments.

[qcolombet]

LGTM.

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

86

:D

110

Could you mention that in a comment?

[t.p.northover]

Thanks Quentin. Committed as r276184.

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

+//==-- llvm/CodeGen/GlobalISel/MachineLegalizer.h ----------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// Interface for Targets to specify which operations they can successfully
+/// select and how the others should be expanded most efficiently.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZER_H
+#define LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/CodeGen/LowLevelType.h"
+
+#include <cstdint>
+#include <functional>
+
+namespace llvm {
+class LLVMContext;
+class MachineInstr;
+class Type;
+class VectorType;
+
+class MachineLegalizer {
+public:
+  enum LegalizeAction : std::uint8_t {
+    /// The operation is expected to be selectable directly by the target, and
+    /// no transformation is necessary.
+    Legal,
+
+    /// The operation should be synthesized from multiple instructions acting on
+    /// a narrower scalar base-type. For example a 64-bit add might be
+    /// implemented in terms of 32-bit add-with-carry.
+    NarrowScalar,
+
+    /// The operation should be implemented in terms of a wider scalar
+    /// base-type. For example a <2 x s8> add could be implemented as a <2
+    /// x s32> add (ignoring the high bits).
+    WidenScalar,
+
+    /// The (vector) operation should be implemented by splitting it into
+    /// sub-vectors where the operation is legal. For example a <8 x s64> add
+    /// might be implemented as 4 separate <2 x s64> adds.
+    FewerElements,
+
+    /// The (vector) operation should be implemented by widening the input
+    /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
+    /// rarely legal, but you might perform an <8 x i8> and then only look at
+    /// the first two results.
+    MoreElements,
+
+    /// The operation should be implemented as a call to some kind of runtime
+    /// support library. For example this usually happens on machines that don't
+    /// support floating-point operations natively.
+    Libcall,
+
+    /// The target wants to do something special with this combination of
+    /// operand and type. A callback will be issued when it is needed.
+    Custom,
+
+    /// This operation is completely unsupported on the target. A programming
+    /// error has occurred.
+    Unsupported,
+  };
+
+  MachineLegalizer();
+
+  /// Replace \p MI by a sequence of legal instructions that can implement the
+  /// same operation. Note that this means \p MI may be deleted, so any iterator
+  /// steps should be performed before calling this function.
+  ///
+  /// Considered as an opaque blob, the legal code will use and define the same
+  /// registers as \p MI.
+  ///
+  /// \returns true if the function is modified, false if the instruction was
+  /// already legal.
+  bool legalizeInstr(MachineInstr &MI) const;
+
+  /// Compute any ancillary tables needed to quickly decide how an operation
+  /// should be handled. This must be called after all "set*Action"methods but
+  /// before any query is made or incorrect results may be returned.
+  void computeTables();
+
+  /// More friendly way to set an action for common types that have an LLT
+  /// representation.
+  void setAction(unsigned Opcode, LLT Ty, LegalizeAction Action) {
+    TablesInitialized = false;
+    Actions[std::make_pair(Opcode, Ty)] = Action;
+  }
+
+  /// If an operation on a given vector type (say <M x iN>) isn't explicitly
+  /// specified, we proceed in 2 stages. First we legalize the underlying scalar
+  /// (so that there's at least one legal vector with that scalar), then we
+  /// adjust the number of elements in the vector so that it is legal. The
+  /// desired action in the first step is controlled by this function.
+  void setScalarInVectorAction(unsigned Opcode, LLT ScalarTy,
+                               LegalizeAction Action) {
+    assert(!ScalarTy.isVector());
+    ScalarInVectorActions[std::make_pair(Opcode, ScalarTy)] = Action;
+  }
+
+
+  std::pair<LegalizeAction, LLT> getAction(unsigned Opcode, LLT) const;
+  std::pair<LegalizeAction, LLT> getAction(MachineInstr &MI) const;
+
+  /// Iterate the given function (typically something like doubling the width)
+  /// on Ty until we find a legal type for this operation.
+  LLT findLegalType(unsigned Opcode, LLT Ty,
+                      std::function<LLT(LLT)> NextType) const {
+    LegalizeAction Action;
+    do {
+      Ty = NextType(Ty);
+      auto ActionIt = Actions.find(std::make_pair(Opcode, Ty));
+      if (ActionIt == Actions.end())
+        Action = DefaultActions.find(Opcode)->second;
+      else
+        Action = ActionIt->second;
+    } while(Action != Legal);
+    return Ty;
+  }
+
+  /// Find what type it's actually OK to perform the given operation on, given
+  /// the general approach we've decided to take.
+  LLT findLegalType(unsigned Opcode, LLT Ty, LegalizeAction Action) const;
+
+  std::pair<LegalizeAction, LLT> findLegalAction(unsigned Opcode, LLT Ty,
+                                                 LegalizeAction Action) const {
+    return std::make_pair(Action, findLegalType(Opcode, Ty, Action));
+  }
+
+  bool isLegal(MachineInstr &MI) const;
+
+private:
+  typedef DenseMap<std::pair<unsigned, LLT>, LegalizeAction> ActionMap;
+
+  ActionMap Actions;
+  ActionMap ScalarInVectorActions;
+  DenseMap<std::pair<unsigned, LLT>, uint16_t> MaxLegalVectorElts;
+  DenseMap<unsigned, LegalizeAction> DefaultActions;
+
+  bool TablesInitialized;
+};
+
+} // End namespace llvm.
+
+#endif

include/llvm/CodeGen/LowLevelType.h

public:
   /// type
   static LLT vector(uint16_t NumElements, LLT ScalarTy) {
     assert(NumElements > 1 && "invalid number of vector elements");
     assert(ScalarTy.isScalar() && "invalid vector element type");
     return LLT{Vector, NumElements, ScalarTy.getSizeInBits()};
   }
 
   /// \brief get an unsized but valid low-level type (e.g. for a label).
+
   static LLT unsized() {
     return LLT{Unsized, 1, 0};
   }
 
   explicit LLT(TypeKind Kind, uint16_t NumElements, unsigned ScalarSizeInBits)
     : ScalarSize(ScalarSizeInBits), NumElements(NumElements), Kind(Kind) {
     assert((Kind != Vector || NumElements > 1) &&
            "invalid number of vector elements");
   }
 
   explicit LLT() : ScalarSize(0), NumElements(0), Kind(Invalid) {}
 
   /// \brief construct a low-level type based on an LLVM type.
   explicit LLT(const Type &Ty);
 
   bool isValid() const { return Kind != Invalid; }
 
   bool isScalar() const { return Kind == Scalar; }
 
   bool isVector() const { return Kind == Vector; }
 
   bool isSized() const { return Kind == Scalar || Kind == Vector; }
 
   /// \brief Returns the number of elements in a vector LLT. Must only be called
   /// on vector types.
   uint16_t getNumElements() const {
     assert(isVector() && "cannot get number of elements on scalar/aggregate");

lib/CodeGen/GlobalISel/CMakeLists.txt

 # List of all GlobalISel files.
 set(GLOBAL_ISEL_FILES
       IRTranslator.cpp
       MachineIRBuilder.cpp
+      MachineLegalizer.cpp
       RegBankSelect.cpp
       RegisterBank.cpp
       RegisterBankInfo.cpp
       )
 
 # Add GlobalISel files to the dependencies if the user wants to build it.
 if(LLVM_BUILD_GLOBAL_ISEL)
   set(GLOBAL_ISEL_BUILD_FILES ${GLOBAL_ISEL_FILES})

lib/CodeGen/GlobalISel/MachineLegalizer.cpp

+//===---- lib/CodeGen/GlobalISel/MachineLegalizer.cpp - IRTranslator -------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implement an interface to specify and query how an illegal operation on a
+// given type should be expanded.
+//
+// Issues to be resolved:
+//   + Make it fast.
+//   + Support weird types like i3, <7 x i3>, ...
+//   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
+//
+//===----------------------------------------------------------------------===//
+
+#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;
+
+MachineLegalizer::MachineLegalizer() : TablesInitialized(false) {
+  DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
+}
+
+bool MachineLegalizer::legalizeInstr(MachineInstr &MI) const {
+  llvm_unreachable("Unimplemented functionality");
+}
+
+void MachineLegalizer::computeTables() {
+  for (auto &Op : Actions) {
+    LLT Ty = Op.first.second;
+    if (!Ty.isVector())
+      continue;
+
+    auto &Entry =
+        MaxLegalVectorElts[std::make_pair(Op.first.first, Ty.getElementType())];
+    Entry = std::max(Entry, Ty.getNumElements());
+  }
+
+  TablesInitialized = true;
+}
+
+// FIXME: inefficient implementation for now. Without ComputeValueVTs we're
+// probably going to need specialized lookup structures for various types before
+// we have any hope of doing well with something like <13 x i3>. Even the common
+// cases should do better than what we have now.
+std::pair<MachineLegalizer::LegalizeAction, LLT>
+MachineLegalizer::getAction(unsigned Opcode, LLT Ty) const {
+  assert(TablesInitialized && "backend forgot to call computeTables");
+  // These *have* to be implemented for now, they're the fundamental basis of
+  // how everything else is transformed.
+
+  auto ActionIt = Actions.find(std::make_pair(Opcode, Ty));
+  if (ActionIt != Actions.end())
+    return findLegalAction(Opcode, Ty, ActionIt->second);
+
+  if (!Ty.isVector()) {
+    auto DefaultAction = DefaultActions.find(Opcode);
+    if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
+      return std::make_pair(Legal, Ty);
+
+    assert(DefaultAction->second == NarrowScalar && "unexpected default");
+    return findLegalAction(Opcode, Ty, NarrowScalar);
+  }
+
+  LLT EltTy = Ty.getElementType();
+  int NumElts = Ty.getNumElements();
+
+  auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
+  if (ScalarAction != ScalarInVectorActions.end() &&
+      ScalarAction->second != Legal)
+    return findLegalAction(Opcode, EltTy, ScalarAction->second);
+
+  // The element type is legal in principle, but the number of elements is
+  // wrong.
+  auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
+  if (MaxLegalElts > NumElts)
+    return findLegalAction(Opcode, Ty, MoreElements);
+
+  if (MaxLegalElts == 0) {
+    // Scalarize if there's no legal vector type, which is just a special case
+    // of FewerElements.
+    return std::make_pair(FewerElements, EltTy);
+  }
+
+  return findLegalAction(Opcode, Ty, FewerElements);
+}
+
+std::pair<MachineLegalizer::LegalizeAction, LLT>
+MachineLegalizer::getAction(MachineInstr &MI) const {
+  return getAction(MI.getOpcode(), MI.getType());
+}
+
+bool MachineLegalizer::isLegal(MachineInstr &MI) const {
+  return getAction(MI).first == Legal;
+}
+
+LLT MachineLegalizer::findLegalType(unsigned Opcode, LLT Ty,
+                                    LegalizeAction Action) const {
+  switch(Action) {
+  default:
+    llvm_unreachable("Cannot find legal type");
+  case Legal:
+    return Ty;
+  case NarrowScalar: {
+    return findLegalType(Opcode, Ty,
+                         [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
+  }
+  case WidenScalar: {
+    return findLegalType(Opcode, Ty,
+                         [&](LLT Ty) -> LLT { return Ty.doubleScalarSize(); });
+  }
+  case FewerElements: {
+    return findLegalType(Opcode, Ty,
+                         [&](LLT Ty) -> LLT { return Ty.halfElements(); });
+  }
+  case MoreElements: {
+    return findLegalType(
+        Opcode, Ty, [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
+  }
+  }
+}

unittests/CodeGen/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AsmPrinter
   Support
   )
 
 set(CodeGenSources
   DIEHashTest.cpp
   )
 
 add_llvm_unittest(CodeGenTests
   ${CodeGenSources}
   )
+
+add_subdirectory(GlobalISel)

unittests/CodeGen/GlobalISel/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  GlobalISel
+  )
+
+if(LLVM_BUILD_GLOBAL_ISEL)
+  add_llvm_unittest(GlobalISelTests
+          MachineLegalizerTest.cpp
+          )
+endif()

unittests/CodeGen/GlobalISel/MachineLegalizerTest.cpp

+//===- llvm/unittest/CodeGen/GlobalISel/MachineLegalizerTest.cpp ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/MachineLegalizer.h"
+#include "llvm/Target/TargetOpcodes.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using llvm::MachineLegalizer::LegalizeAction::Legal;
+using llvm::MachineLegalizer::LegalizeAction::NarrowScalar;
+using llvm::MachineLegalizer::LegalizeAction::WidenScalar;
+using llvm::MachineLegalizer::LegalizeAction::FewerElements;
+using llvm::MachineLegalizer::LegalizeAction::MoreElements;
+using llvm::MachineLegalizer::LegalizeAction::Libcall;
+using llvm::MachineLegalizer::LegalizeAction::Custom;
+using llvm::MachineLegalizer::LegalizeAction::Unsupported;
+
+// Define a couple of pretty printers to help debugging when things go wrong.
+namespace llvm {
+std::ostream &
+operator<<(std::ostream &OS, const llvm::MachineLegalizer::LegalizeAction Act) {
+  switch (Act) {
+  case Legal: OS << "Legal"; break;
+  case NarrowScalar: OS << "NarrowScalar"; break;
+  case WidenScalar:  OS << "WidenScalar"; break;
+  case FewerElements:  OS << "FewerElements"; break;
+  case MoreElements:  OS << "MoreElements"; break;
+  case Libcall: OS << "Libcall"; break;
+  case Custom: OS << "Custom"; break;
+  case Unsupported: OS << "Unsupported"; break;
+  }
+  return OS;
+}
+
+std::ostream &
+operator<<(std::ostream &OS, const llvm::LLT Ty) {
+  std::string Repr;
+  raw_string_ostream SS{Repr};
+  Ty.print(SS);
+  OS << SS.str();
+  return OS;
+}
+}
+
+namespace {
+
+
+TEST(MachineLegalizerTest, ScalarRISC) {
+  MachineLegalizer L;
+  // Typical RISCy set of operations based on AArch64.
+  L.setAction(TargetOpcode::G_ADD, LLT::scalar(8), WidenScalar);
+  L.setAction(TargetOpcode::G_ADD, LLT::scalar(16), WidenScalar);
+  L.setAction(TargetOpcode::G_ADD, LLT::scalar(32), Legal);
+  L.setAction(TargetOpcode::G_ADD, LLT::scalar(64), Legal);
+  L.computeTables();
+
+  // Check we infer the correct types and actually do what we're told.
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::scalar(8)),
+                        std::make_pair(WidenScalar, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::scalar(16)),
+                        std::make_pair(WidenScalar, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::scalar(32)),
+                        std::make_pair(Legal, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::scalar(64)),
+                        std::make_pair(Legal, LLT::scalar(64)));
+
+  // Make sure the default for over-sized types applies.
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::scalar(128)),
+                        std::make_pair(NarrowScalar, LLT::scalar(64)));
+}
+
+TEST(MachineLegalizerTest, VectorRISC) {
+  MachineLegalizer L;
+  // Typical RISCy set of operations based on ARM.
+  L.setScalarInVectorAction(TargetOpcode::G_ADD, LLT::scalar(8), Legal);
+  L.setScalarInVectorAction(TargetOpcode::G_ADD, LLT::scalar(16), Legal);
+  L.setScalarInVectorAction(TargetOpcode::G_ADD, LLT::scalar(32), Legal);
+
+  L.setAction(TargetOpcode::G_ADD, LLT::vector(8, 8), Legal);
+  L.setAction(TargetOpcode::G_ADD, LLT::vector(16, 8), Legal);
+  L.setAction(TargetOpcode::G_ADD, LLT::vector(4, 16), Legal);
+  L.setAction(TargetOpcode::G_ADD, LLT::vector(8, 16), Legal);
+  L.setAction(TargetOpcode::G_ADD, LLT::vector(2, 32), Legal);
+  L.setAction(TargetOpcode::G_ADD, LLT::vector(4, 32), Legal);
+  L.computeTables();
+
+  // Check we infer the correct types and actually do what we're told for some
+  // simple cases.
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::vector(2, 8)),
+            std::make_pair(MoreElements, LLT::vector(8, 8)));
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::vector(8, 8)),
+            std::make_pair(Legal, LLT::vector(8, 8)));
+  ASSERT_EQ(L.getAction(TargetOpcode::G_ADD, LLT::vector(8, 32)),
+            std::make_pair(FewerElements, LLT::vector(4, 32)));
+}
+}