clang-r458507/include/llvm/CodeGen/GlobalISel/LegacyLegalizerInfo.h - platform/prebuilts/clang/host/darwin-x86 - Git at Google

 //===- llvm/CodeGen/GlobalISel/LegacyLegalizerInfo.h ------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// Interface for Targets to specify which operations they can successfully
 /// select and how the others should be expanded most efficiently.
 /// This implementation has been deprecated for a long time but it still in use
 /// in a few places.
 //===----------------------------------------------------------------------===//

 #ifndef LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H
 #define LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include <unordered_map>

 namespace llvm {
 struct LegalityQuery;

 namespace LegacyLegalizeActions {
 enum LegacyLegalizeAction : 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,

   /// Perform the operation on a different, but equivalently sized type.
   Bitcast,

   /// The operation itself must be expressed in terms of simpler actions on
   /// this target. E.g. a SREM replaced by an SDIV and subtraction.
   Lower,

   /// 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,

   /// Sentinel value for when no action was found in the specified table.
   NotFound,
 };
 } // end namespace LegacyLegalizeActions
 raw_ostream &operator<<(raw_ostream &OS,
                         LegacyLegalizeActions::LegacyLegalizeAction Action);

 /// Legalization is decided based on an instruction's opcode, which type slot
 /// we're considering, and what the existing type is. These aspects are gathered
 /// together for convenience in the InstrAspect class.
 struct InstrAspect {
   unsigned Opcode;
   unsigned Idx = 0;
   LLT Type;

   InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
   InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
       : Opcode(Opcode), Idx(Idx), Type(Type) {}

   bool operator==(const InstrAspect &RHS) const {
     return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
   }
 };

 /// The result of a query. It either indicates a final answer of Legal or
 /// Unsupported or describes an action that must be taken to make an operation
 /// more legal.
 struct LegacyLegalizeActionStep {
   /// The action to take or the final answer.
   LegacyLegalizeActions::LegacyLegalizeAction Action;
   /// If describing an action, the type index to change. Otherwise zero.
   unsigned TypeIdx;
   /// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
   LLT NewType;

   LegacyLegalizeActionStep(LegacyLegalizeActions::LegacyLegalizeAction Action,
                            unsigned TypeIdx, const LLT NewType)
       : Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}

   bool operator==(const LegacyLegalizeActionStep &RHS) const {
     return std::tie(Action, TypeIdx, NewType) ==
         std::tie(RHS.Action, RHS.TypeIdx, RHS.NewType);
   }
 };


 class LegacyLegalizerInfo {
 public:
   using SizeAndAction =
       std::pair<uint16_t, LegacyLegalizeActions::LegacyLegalizeAction>;
   using SizeAndActionsVec = std::vector<SizeAndAction>;
   using SizeChangeStrategy =
       std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;

   LegacyLegalizerInfo();

   static bool needsLegalizingToDifferentSize(
       const LegacyLegalizeActions::LegacyLegalizeAction Action) {
     using namespace LegacyLegalizeActions;
     switch (Action) {
     case NarrowScalar:
     case WidenScalar:
     case FewerElements:
     case MoreElements:
     case Unsupported:
       return true;
     default:
       return false;
     }
   }

   /// 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.
   /// The LegacyLegalizeAction must be one for which
   /// NeedsLegalizingToDifferentSize returns false.
   void setAction(const InstrAspect &Aspect,
                  LegacyLegalizeActions::LegacyLegalizeAction Action) {
     assert(!needsLegalizingToDifferentSize(Action));
     TablesInitialized = false;
     const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
     if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
       SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
     SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
   }

   /// The setAction calls record the non-size-changing legalization actions
   /// to take on specificly-sized types. The SizeChangeStrategy defines what
   /// to do when the size of the type needs to be changed to reach a legally
   /// sized type (i.e., one that was defined through a setAction call).
   /// e.g.
   /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
   /// setLegalizeScalarToDifferentSizeStrategy(
   ///   G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
   /// will end up defining getAction({G_ADD, 0, T}) to return the following
   /// actions for different scalar types T:
   ///  LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
   ///  LLT::scalar(32):                 {Legal, 0, LLT::scalar(32)}
   ///  LLT::scalar(33)..:               {NarrowScalar, 0, LLT::scalar(32)}
   ///
   /// If no SizeChangeAction gets defined, through this function,
   /// the default is unsupportedForDifferentSizes.
   void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
                                                 const unsigned TypeIdx,
                                                 SizeChangeStrategy S) {
     const unsigned OpcodeIdx = Opcode - FirstOp;
     if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
       ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
     ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
   }

   /// See also setLegalizeScalarToDifferentSizeStrategy.
   /// This function allows to set the SizeChangeStrategy for vector elements.
   void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
                                                        const unsigned TypeIdx,
                                                        SizeChangeStrategy S) {
     const unsigned OpcodeIdx = Opcode - FirstOp;
     if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
       VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
     VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
   }

   /// A SizeChangeStrategy for the common case where legalization for a
   /// particular operation consists of only supporting a specific set of type
   /// sizes. E.g.
   ///   setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
   ///   setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
   ///   setLegalizeScalarToDifferentSizeStrategy(
   ///     G_DIV, 0, unsupportedForDifferentSizes);
   /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
   /// and Unsupported for all other scalar types T.
   static SizeAndActionsVec
   unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
     using namespace LegacyLegalizeActions;
     return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
                                                      Unsupported);
   }

   /// A SizeChangeStrategy for the common case where legalization for a
   /// particular operation consists of widening the type to a large legal type,
   /// unless there is no such type and then instead it should be narrowed to the
   /// largest legal type.
   static SizeAndActionsVec
   widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
     using namespace LegacyLegalizeActions;
     assert(v.size() > 0 &&
            "At least one size that can be legalized towards is needed"
            " for this SizeChangeStrategy");
     return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
                                                      NarrowScalar);
   }

   static SizeAndActionsVec
   widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
     using namespace LegacyLegalizeActions;
     return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
                                                      Unsupported);
   }

   static SizeAndActionsVec
   narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
     using namespace LegacyLegalizeActions;
     return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
                                                        Unsupported);
   }

   static SizeAndActionsVec
   narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec &v) {
     using namespace LegacyLegalizeActions;
     assert(v.size() > 0 &&
            "At least one size that can be legalized towards is needed"
            " for this SizeChangeStrategy");
     return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
                                                        WidenScalar);
   }

   /// A SizeChangeStrategy for the common case where legalization for a
   /// particular vector operation consists of having more elements in the
   /// vector, to a type that is legal. Unless there is no such type and then
   /// instead it should be legalized towards the widest vector that's still
   /// legal. E.g.
   ///   setAction({G_ADD, LLT::vector(8, 8)}, Legal);
   ///   setAction({G_ADD, LLT::vector(16, 8)}, Legal);
   ///   setAction({G_ADD, LLT::vector(2, 32)}, Legal);
   ///   setAction({G_ADD, LLT::vector(4, 32)}, Legal);
   ///   setLegalizeVectorElementToDifferentSizeStrategy(
   ///     G_ADD, 0, moreToWiderTypesAndLessToWidest);
   /// will result in the following getAction results:
   ///   * getAction({G_ADD, LLT::vector(8,8)}) returns
   ///       (Legal, vector(8,8)).
   ///   * getAction({G_ADD, LLT::vector(9,8)}) returns
   ///       (MoreElements, vector(16,8)).
   ///   * getAction({G_ADD, LLT::vector(8,32)}) returns
   ///       (FewerElements, vector(4,32)).
   static SizeAndActionsVec
   moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
     using namespace LegacyLegalizeActions;
     return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
                                                      FewerElements);
   }

   /// Helper function to implement many typical SizeChangeStrategy functions.
   static SizeAndActionsVec increaseToLargerTypesAndDecreaseToLargest(
       const SizeAndActionsVec &v,
       LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction,
       LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction);
   /// Helper function to implement many typical SizeChangeStrategy functions.
   static SizeAndActionsVec decreaseToSmallerTypesAndIncreaseToSmallest(
       const SizeAndActionsVec &v,
       LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction,
       LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction);

   LegacyLegalizeActionStep getAction(const LegalityQuery &Query) const;

   unsigned getOpcodeIdxForOpcode(unsigned Opcode) const;

 private:
   /// Determine what action should be taken to legalize the given generic
   /// instruction opcode, type-index and type. Requires computeTables to have
   /// been called.
   ///
   /// \returns a pair consisting of the kind of legalization that should be
   /// performed and the destination type.
   std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
   getAspectAction(const InstrAspect &Aspect) const;

   /// The SizeAndActionsVec is a representation mapping between all natural
   /// numbers and an Action. The natural number represents the bit size of
   /// the InstrAspect. For example, for a target with native support for 32-bit
   /// and 64-bit additions, you'd express that as:
   /// setScalarAction(G_ADD, 0,
   ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
   ///            {32, Legal},       // bit sizes [32, 33[
   ///            {33, WidenScalar}, // bit sizes [33, 64[
   ///            {64, Legal},       // bit sizes [64, 65[
   ///            {65, NarrowScalar} // bit sizes [65, +inf[
   ///           });
   /// It may be that only 64-bit pointers are supported on your target:
   /// setPointerAction(G_PTR_ADD, 0, LLT:pointer(1),
   ///           {{1, Unsupported},  // bit sizes [ 1, 63[
   ///            {64, Legal},       // bit sizes [64, 65[
   ///            {65, Unsupported}, // bit sizes [65, +inf[
   ///           });
   void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
                        const SizeAndActionsVec &SizeAndActions) {
     const unsigned OpcodeIdx = Opcode - FirstOp;
     SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
     setActions(TypeIndex, Actions, SizeAndActions);
   }
   void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
                         const unsigned AddressSpace,
                         const SizeAndActionsVec &SizeAndActions) {
     const unsigned OpcodeIdx = Opcode - FirstOp;
     if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
         AddrSpace2PointerActions[OpcodeIdx].end())
       AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
     SmallVector<SizeAndActionsVec, 1> &Actions =
         AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
     setActions(TypeIndex, Actions, SizeAndActions);
   }

   /// 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(const unsigned Opcode, const unsigned TypeIndex,
                                const SizeAndActionsVec &SizeAndActions) {
     unsigned OpcodeIdx = Opcode - FirstOp;
     SmallVector<SizeAndActionsVec, 1> &Actions =
         ScalarInVectorActions[OpcodeIdx];
     setActions(TypeIndex, Actions, SizeAndActions);
   }

   /// See also setScalarInVectorAction.
   /// This function let's you specify the number of elements in a vector that
   /// are legal for a legal element size.
   void setVectorNumElementAction(const unsigned Opcode,
                                  const unsigned TypeIndex,
                                  const unsigned ElementSize,
                                  const SizeAndActionsVec &SizeAndActions) {
     const unsigned OpcodeIdx = Opcode - FirstOp;
     if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
         NumElements2Actions[OpcodeIdx].end())
       NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
     SmallVector<SizeAndActionsVec, 1> &Actions =
         NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
     setActions(TypeIndex, Actions, SizeAndActions);
   }

   /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
   /// i.e. it's OK if it doesn't start from size 1.
   static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
     using namespace LegacyLegalizeActions;
 #ifndef NDEBUG
     // The sizes should be in increasing order
     int prev_size = -1;
     for(auto SizeAndAction: v) {
       assert(SizeAndAction.first > prev_size);
       prev_size = SizeAndAction.first;
     }
     // - for every Widen action, there should be a larger bitsize that
     //   can be legalized towards (e.g. Legal, Lower, Libcall or Custom
     //   action).
     // - for every Narrow action, there should be a smaller bitsize that
     //   can be legalized towards.
     int SmallestNarrowIdx = -1;
     int LargestWidenIdx = -1;
     int SmallestLegalizableToSameSizeIdx = -1;
     int LargestLegalizableToSameSizeIdx = -1;
     for(size_t i=0; i<v.size(); ++i) {
       switch (v[i].second) {
         case FewerElements:
         case NarrowScalar:
           if (SmallestNarrowIdx == -1)
             SmallestNarrowIdx = i;
           break;
         case WidenScalar:
         case MoreElements:
           LargestWidenIdx = i;
           break;
         case Unsupported:
           break;
         default:
           if (SmallestLegalizableToSameSizeIdx == -1)
             SmallestLegalizableToSameSizeIdx = i;
           LargestLegalizableToSameSizeIdx = i;
       }
     }
     if (SmallestNarrowIdx != -1) {
       assert(SmallestLegalizableToSameSizeIdx != -1);
       assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
     }
     if (LargestWidenIdx != -1)
       assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
 #endif
   }

   /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
   /// from size 1.
   static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
 #ifndef NDEBUG
     // Data structure invariant: The first bit size must be size 1.
     assert(v.size() >= 1);
     assert(v[0].first == 1);
     checkPartialSizeAndActionsVector(v);
 #endif
   }

   /// Sets actions for all bit sizes on a particular generic opcode, type
   /// index and scalar or pointer type.
   void setActions(unsigned TypeIndex,
                   SmallVector<SizeAndActionsVec, 1> &Actions,
                   const SizeAndActionsVec &SizeAndActions) {
     checkFullSizeAndActionsVector(SizeAndActions);
     if (Actions.size() <= TypeIndex)
       Actions.resize(TypeIndex + 1);
     Actions[TypeIndex] = SizeAndActions;
   }

   static SizeAndAction findAction(const SizeAndActionsVec &Vec,
                                   const uint32_t Size);

   /// Returns the next action needed to get the scalar or pointer type closer
   /// to being legal
   /// E.g. findLegalAction({G_REM, 13}) should return
   /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
   /// probably be called, which should return (Lower, 32).
   /// This is assuming the setScalarAction on G_REM was something like:
   /// setScalarAction(G_REM, 0,
   ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
   ///            {32, Lower},       // bit sizes [32, 33[
   ///            {33, NarrowScalar} // bit sizes [65, +inf[
   ///           });
   std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
   findScalarLegalAction(const InstrAspect &Aspect) const;

   /// Returns the next action needed towards legalizing the vector type.
   std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
   findVectorLegalAction(const InstrAspect &Aspect) const;

   static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
   static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;

   // Data structures used temporarily during construction of legality data:
   using TypeMap = DenseMap<LLT, LegacyLegalizeActions::LegacyLegalizeAction>;
   SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
   SmallVector<SizeChangeStrategy, 1>
       ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
   SmallVector<SizeChangeStrategy, 1>
       VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
   bool TablesInitialized = false;

   // Data structures used by getAction:
   SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
   SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
   std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
       AddrSpace2PointerActions[LastOp - FirstOp + 1];
   std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
       NumElements2Actions[LastOp - FirstOp + 1];
 };

 } // end namespace llvm

 #endif // LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H
	//===- llvm/CodeGen/GlobalISel/LegacyLegalizerInfo.h ------------- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	/// \file
	/// Interface for Targets to specify which operations they can successfully
	/// select and how the others should be expanded most efficiently.
	/// This implementation has been deprecated for a long time but it still in use
	/// in a few places.
	//===----------------------------------------------------------------------===//

	#ifndef LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H
	#define LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H

	#include "llvm/ADT/DenseMap.h"
	#include "llvm/CodeGen/TargetOpcodes.h"
	#include "llvm/Support/LowLevelTypeImpl.h"
	#include <unordered_map>

	namespace llvm {
	struct LegalityQuery;

	namespace LegacyLegalizeActions {
	enum LegacyLegalizeAction : 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,

	/// Perform the operation on a different, but equivalently sized type.
	Bitcast,

	/// The operation itself must be expressed in terms of simpler actions on
	/// this target. E.g. a SREM replaced by an SDIV and subtraction.
	Lower,

	/// 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,

	/// Sentinel value for when no action was found in the specified table.
	NotFound,
	};
	} // end namespace LegacyLegalizeActions
	raw_ostream &operator<<(raw_ostream &OS,
	LegacyLegalizeActions::LegacyLegalizeAction Action);

	/// Legalization is decided based on an instruction's opcode, which type slot
	/// we're considering, and what the existing type is. These aspects are gathered
	/// together for convenience in the InstrAspect class.
	struct InstrAspect {
	unsigned Opcode;
	unsigned Idx = 0;
	LLT Type;

	InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
	InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
	: Opcode(Opcode), Idx(Idx), Type(Type) {}

	bool operator==(const InstrAspect &RHS) const {
	return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
	}
	};

	/// The result of a query. It either indicates a final answer of Legal or
	/// Unsupported or describes an action that must be taken to make an operation
	/// more legal.
	struct LegacyLegalizeActionStep {
	/// The action to take or the final answer.
	LegacyLegalizeActions::LegacyLegalizeAction Action;
	/// If describing an action, the type index to change. Otherwise zero.
	unsigned TypeIdx;
	/// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
	LLT NewType;

	LegacyLegalizeActionStep(LegacyLegalizeActions::LegacyLegalizeAction Action,
	unsigned TypeIdx, const LLT NewType)
	: Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}

	bool operator==(const LegacyLegalizeActionStep &RHS) const {
	return std::tie(Action, TypeIdx, NewType) ==
	std::tie(RHS.Action, RHS.TypeIdx, RHS.NewType);
	}
	};


	class LegacyLegalizerInfo {
	public:
	using SizeAndAction =
	std::pair<uint16_t, LegacyLegalizeActions::LegacyLegalizeAction>;
	using SizeAndActionsVec = std::vector<SizeAndAction>;
	using SizeChangeStrategy =
	std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;

	LegacyLegalizerInfo();

	static bool needsLegalizingToDifferentSize(
	const LegacyLegalizeActions::LegacyLegalizeAction Action) {
	using namespace LegacyLegalizeActions;
	switch (Action) {
	case NarrowScalar:
	case WidenScalar:
	case FewerElements:
	case MoreElements:
	case Unsupported:
	return true;
	default:
	return false;
	}
	}

	/// 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.
	/// The LegacyLegalizeAction must be one for which
	/// NeedsLegalizingToDifferentSize returns false.
	void setAction(const InstrAspect &Aspect,
	LegacyLegalizeActions::LegacyLegalizeAction Action) {
	assert(!needsLegalizingToDifferentSize(Action));
	TablesInitialized = false;
	const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
	if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
	SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
	SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
	}

	/// The setAction calls record the non-size-changing legalization actions
	/// to take on specificly-sized types. The SizeChangeStrategy defines what
	/// to do when the size of the type needs to be changed to reach a legally
	/// sized type (i.e., one that was defined through a setAction call).
	/// e.g.
	/// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
	/// setLegalizeScalarToDifferentSizeStrategy(
	/// G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
	/// will end up defining getAction({G_ADD, 0, T}) to return the following
	/// actions for different scalar types T:
	/// LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
	/// LLT::scalar(32): {Legal, 0, LLT::scalar(32)}
	/// LLT::scalar(33)..: {NarrowScalar, 0, LLT::scalar(32)}
	///
	/// If no SizeChangeAction gets defined, through this function,
	/// the default is unsupportedForDifferentSizes.
	void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
	const unsigned TypeIdx,
	SizeChangeStrategy S) {
	const unsigned OpcodeIdx = Opcode - FirstOp;
	if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
	ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
	ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
	}

	/// See also setLegalizeScalarToDifferentSizeStrategy.
	/// This function allows to set the SizeChangeStrategy for vector elements.
	void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
	const unsigned TypeIdx,
	SizeChangeStrategy S) {
	const unsigned OpcodeIdx = Opcode - FirstOp;
	if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
	VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
	VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
	}

	/// A SizeChangeStrategy for the common case where legalization for a
	/// particular operation consists of only supporting a specific set of type
	/// sizes. E.g.
	/// setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
	/// setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
	/// setLegalizeScalarToDifferentSizeStrategy(
	/// G_DIV, 0, unsupportedForDifferentSizes);
	/// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
	/// and Unsupported for all other scalar types T.
	static SizeAndActionsVec
	unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
	using namespace LegacyLegalizeActions;
	return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
	Unsupported);
	}

	/// A SizeChangeStrategy for the common case where legalization for a
	/// particular operation consists of widening the type to a large legal type,
	/// unless there is no such type and then instead it should be narrowed to the
	/// largest legal type.
	static SizeAndActionsVec
	widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
	using namespace LegacyLegalizeActions;
	assert(v.size() > 0 &&
	"At least one size that can be legalized towards is needed"
	" for this SizeChangeStrategy");
	return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
	NarrowScalar);
	}

	static SizeAndActionsVec
	widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
	using namespace LegacyLegalizeActions;
	return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
	Unsupported);
	}

	static SizeAndActionsVec
	narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
	using namespace LegacyLegalizeActions;
	return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
	Unsupported);
	}

	static SizeAndActionsVec
	narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec &v) {
	using namespace LegacyLegalizeActions;
	assert(v.size() > 0 &&
	"At least one size that can be legalized towards is needed"
	" for this SizeChangeStrategy");
	return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
	WidenScalar);
	}

	/// A SizeChangeStrategy for the common case where legalization for a
	/// particular vector operation consists of having more elements in the
	/// vector, to a type that is legal. Unless there is no such type and then
	/// instead it should be legalized towards the widest vector that's still
	/// legal. E.g.
	/// setAction({G_ADD, LLT::vector(8, 8)}, Legal);
	/// setAction({G_ADD, LLT::vector(16, 8)}, Legal);
	/// setAction({G_ADD, LLT::vector(2, 32)}, Legal);
	/// setAction({G_ADD, LLT::vector(4, 32)}, Legal);
	/// setLegalizeVectorElementToDifferentSizeStrategy(
	/// G_ADD, 0, moreToWiderTypesAndLessToWidest);
	/// will result in the following getAction results:
	/// * getAction({G_ADD, LLT::vector(8,8)}) returns
	/// (Legal, vector(8,8)).
	/// * getAction({G_ADD, LLT::vector(9,8)}) returns
	/// (MoreElements, vector(16,8)).
	/// * getAction({G_ADD, LLT::vector(8,32)}) returns
	/// (FewerElements, vector(4,32)).
	static SizeAndActionsVec
	moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
	using namespace LegacyLegalizeActions;
	return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
	FewerElements);
	}

	/// Helper function to implement many typical SizeChangeStrategy functions.
	static SizeAndActionsVec increaseToLargerTypesAndDecreaseToLargest(
	const SizeAndActionsVec &v,
	LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction,
	LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction);
	/// Helper function to implement many typical SizeChangeStrategy functions.
	static SizeAndActionsVec decreaseToSmallerTypesAndIncreaseToSmallest(
	const SizeAndActionsVec &v,
	LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction,
	LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction);

	LegacyLegalizeActionStep getAction(const LegalityQuery &Query) const;

	unsigned getOpcodeIdxForOpcode(unsigned Opcode) const;

	private:
	/// Determine what action should be taken to legalize the given generic
	/// instruction opcode, type-index and type. Requires computeTables to have
	/// been called.
	///
	/// \returns a pair consisting of the kind of legalization that should be
	/// performed and the destination type.
	std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
	getAspectAction(const InstrAspect &Aspect) const;

	/// The SizeAndActionsVec is a representation mapping between all natural
	/// numbers and an Action. The natural number represents the bit size of
	/// the InstrAspect. For example, for a target with native support for 32-bit
	/// and 64-bit additions, you'd express that as:
	/// setScalarAction(G_ADD, 0,
	/// {{1, WidenScalar}, // bit sizes [ 1, 31[
	/// {32, Legal}, // bit sizes [32, 33[
	/// {33, WidenScalar}, // bit sizes [33, 64[
	/// {64, Legal}, // bit sizes [64, 65[
	/// {65, NarrowScalar} // bit sizes [65, +inf[
	/// });
	/// It may be that only 64-bit pointers are supported on your target:
	/// setPointerAction(G_PTR_ADD, 0, LLT:pointer(1),
	/// {{1, Unsupported}, // bit sizes [ 1, 63[
	/// {64, Legal}, // bit sizes [64, 65[
	/// {65, Unsupported}, // bit sizes [65, +inf[
	/// });
	void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
	const SizeAndActionsVec &SizeAndActions) {
	const unsigned OpcodeIdx = Opcode - FirstOp;
	SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
	setActions(TypeIndex, Actions, SizeAndActions);
	}
	void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
	const unsigned AddressSpace,
	const SizeAndActionsVec &SizeAndActions) {
	const unsigned OpcodeIdx = Opcode - FirstOp;
	if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
	AddrSpace2PointerActions[OpcodeIdx].end())
	AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
	SmallVector<SizeAndActionsVec, 1> &Actions =
	AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
	setActions(TypeIndex, Actions, SizeAndActions);
	}

	/// 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(const unsigned Opcode, const unsigned TypeIndex,
	const SizeAndActionsVec &SizeAndActions) {
	unsigned OpcodeIdx = Opcode - FirstOp;
	SmallVector<SizeAndActionsVec, 1> &Actions =
	ScalarInVectorActions[OpcodeIdx];
	setActions(TypeIndex, Actions, SizeAndActions);
	}

	/// See also setScalarInVectorAction.
	/// This function let's you specify the number of elements in a vector that
	/// are legal for a legal element size.
	void setVectorNumElementAction(const unsigned Opcode,
	const unsigned TypeIndex,
	const unsigned ElementSize,
	const SizeAndActionsVec &SizeAndActions) {
	const unsigned OpcodeIdx = Opcode - FirstOp;
	if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
	NumElements2Actions[OpcodeIdx].end())
	NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
	SmallVector<SizeAndActionsVec, 1> &Actions =
	NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
	setActions(TypeIndex, Actions, SizeAndActions);
	}

	/// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
	/// i.e. it's OK if it doesn't start from size 1.
	static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
	using namespace LegacyLegalizeActions;
	#ifndef NDEBUG
	// The sizes should be in increasing order
	int prev_size = -1;
	for(auto SizeAndAction: v) {
	assert(SizeAndAction.first > prev_size);
	prev_size = SizeAndAction.first;
	}
	// - for every Widen action, there should be a larger bitsize that
	// can be legalized towards (e.g. Legal, Lower, Libcall or Custom
	// action).
	// - for every Narrow action, there should be a smaller bitsize that
	// can be legalized towards.
	int SmallestNarrowIdx = -1;
	int LargestWidenIdx = -1;
	int SmallestLegalizableToSameSizeIdx = -1;
	int LargestLegalizableToSameSizeIdx = -1;
	for(size_t i=0; i<v.size(); ++i) {
	switch (v[i].second) {
	case FewerElements:
	case NarrowScalar:
	if (SmallestNarrowIdx == -1)
	SmallestNarrowIdx = i;
	break;
	case WidenScalar:
	case MoreElements:
	LargestWidenIdx = i;
	break;
	case Unsupported:
	break;
	default:
	if (SmallestLegalizableToSameSizeIdx == -1)
	SmallestLegalizableToSameSizeIdx = i;
	LargestLegalizableToSameSizeIdx = i;
	}
	}
	if (SmallestNarrowIdx != -1) {
	assert(SmallestLegalizableToSameSizeIdx != -1);
	assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
	}
	if (LargestWidenIdx != -1)
	assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
	#endif
	}

	/// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
	/// from size 1.
	static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
	#ifndef NDEBUG
	// Data structure invariant: The first bit size must be size 1.
	assert(v.size() >= 1);
	assert(v[0].first == 1);
	checkPartialSizeAndActionsVector(v);
	#endif
	}

	/// Sets actions for all bit sizes on a particular generic opcode, type
	/// index and scalar or pointer type.
	void setActions(unsigned TypeIndex,
	SmallVector<SizeAndActionsVec, 1> &Actions,
	const SizeAndActionsVec &SizeAndActions) {
	checkFullSizeAndActionsVector(SizeAndActions);
	if (Actions.size() <= TypeIndex)
	Actions.resize(TypeIndex + 1);
	Actions[TypeIndex] = SizeAndActions;
	}

	static SizeAndAction findAction(const SizeAndActionsVec &Vec,
	const uint32_t Size);

	/// Returns the next action needed to get the scalar or pointer type closer
	/// to being legal
	/// E.g. findLegalAction({G_REM, 13}) should return
	/// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
	/// probably be called, which should return (Lower, 32).
	/// This is assuming the setScalarAction on G_REM was something like:
	/// setScalarAction(G_REM, 0,
	/// {{1, WidenScalar}, // bit sizes [ 1, 31[
	/// {32, Lower}, // bit sizes [32, 33[
	/// {33, NarrowScalar} // bit sizes [65, +inf[
	/// });
	std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
	findScalarLegalAction(const InstrAspect &Aspect) const;

	/// Returns the next action needed towards legalizing the vector type.
	std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
	findVectorLegalAction(const InstrAspect &Aspect) const;

	static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
	static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;

	// Data structures used temporarily during construction of legality data:
	using TypeMap = DenseMap<LLT, LegacyLegalizeActions::LegacyLegalizeAction>;
	SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
	SmallVector<SizeChangeStrategy, 1>
	ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
	SmallVector<SizeChangeStrategy, 1>
	VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
	bool TablesInitialized = false;

	// Data structures used by getAction:
	SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
	SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
	std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
	AddrSpace2PointerActions[LastOp - FirstOp + 1];
	std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
	NumElements2Actions[LastOp - FirstOp + 1];
	};

	} // end namespace llvm

	#endif // LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H