Index: include/llvm/CodeGen/GlobalISel/LegalizerInfo.h =================================================================== --- include/llvm/CodeGen/GlobalISel/LegalizerInfo.h +++ include/llvm/CodeGen/GlobalISel/LegalizerInfo.h @@ -21,6 +21,7 @@ #include #include +#include namespace llvm { class LLVMContext; @@ -104,27 +105,163 @@ /// 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. + static bool NeedsLegalizingToDifferentSize(const LegalizeAction Action) { + switch (Action) { + case NarrowScalar: + case WidenScalar: + case FewerElements: + case MoreElements: + case Unsupported: + return true; + default: + return false; + } + } + + typedef std::pair SizeAndAction; + typedef std::vector SizeAndActionsVec; + typedef SmallVector SmallSizeAndActionsVec; + typedef SmallVector, 4> ActionAndTypes; + typedef SmallVector, 4> + ActionIndexAndTypes; + using SizeChangeStrategy = + std::function; + + /// Specify the action to take on a particular instruction aspect, + /// i.e. a specific generic opcode, typeindex and scalar or pointer + /// type. + /// The LegalizeAction must be one for which + /// NeedsLegalizingToDifferentSize + /// returns false. void setAction(const InstrAspect &Aspect, LegalizeAction Action) { + assert(!NeedsLegalizingToDifferentSize(Action)); TablesInitialized = false; - 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; + 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; } - /// If an operation on a given vector type (say ) 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; + /// 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 UnsupportedButFor. + 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. + /// setScalarAction(G_DIV, 0, + /// {{1, Unsupported}, // bit sizes [ 1, 31[ + /// {32, Legal}, // bit sizes [32, 33[ + /// {33, Unsupported}, // bit sizes [33, 64[ + /// {64, Lower}, // bit sizes [64, 65[ + /// {65, Unsupported} // bit sizes [65, +inf[ + /// }); + /// can be shortened to: + /// setScalarAction(G_DIV, 0, + /// UnsupportedExceptFor( + /// {32, Legal}, {64, Lower})); + static SizeAndActionsVec + unsupportedExceptFor(const SizeAndActionsVec &v) { + 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. E.g. + /// 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[ + /// }); + /// can be shortened to: + /// setScalarAction(G_ADD, 0, + /// WidenToLargerTypesAndNarrowToLargest( + /// {32, Legal}, {64, Legal})); + static SizeAndActionsVec + widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) { + return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar, + NarrowScalar); + } + + static SizeAndActionsVec + widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) { + return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar, + Unsupported); + } + + static SizeAndActionsVec + narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) { + return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar, + Unsupported); + } + /// 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. + /// {8,{ + /// {1, MoreElements}, // [ <1x8>, <8x8> [ :increase to <8x8> + /// {8, Legal}, // [ <8x8>, <9x8> [ :is Legal + /// {9, MoreElements}, // [ <9x8>, <16x8> [ :increase to <16x8> + /// {16, Legal}, // [ <16x8>, <16x8> [ :is Legal + /// {17, FewerElements}// [ <17x8>, [ :decrease to <16x8> + /// }} + /// can be shortened to: + /// {8, + /// MoreToWiderTypesAndLessToWidest({8, Legal}, {16, Legal}) + /// } + static SizeAndActionsVec + moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) { + return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements, + FewerElements); + } + + /// Helper function to implement many typical SizeChangeStrategy functions. + static SizeAndActionsVec + increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v, + LegalizeAction IncreaseAction, + LegalizeAction DecreaseAction); + /// Helper function to implement many typical SizeChangeStrategy functions. + static SizeAndActionsVec + decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v, + LegalizeAction DecreaseAction, + LegalizeAction IncreaseAction); /// Determine what action should be taken to legalize the given generic /// instruction opcode, type-index and type. Requires computeTables to have @@ -132,7 +269,7 @@ /// /// \returns a pair consisting of the kind of legalization that should be /// performed and the destination type. - std::pair getAction(const InstrAspect &Aspect) const; + ActionAndTypes getAction(const InstrAspect &Aspect) const; /// Determine what action should be taken to legalize the given generic /// instruction. @@ -140,73 +277,200 @@ /// \returns a tuple consisting of the LegalizeAction that should be /// performed, the type-index it should be performed on and the destination /// type. - std::tuple - getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const; - - /// Iterate the given function (typically something like doubling the width) - /// on Ty until we find a legal type for this operation. - LLT findLegalType(const InstrAspect &Aspect, - function_ref NextType) const { - LegalizeAction Action; - const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx]; - LLT Ty = Aspect.Type; - do { - Ty = NextType(Ty); - auto ActionIt = Map.find(Ty); - if (ActionIt == Map.end()) - Action = DefaultActions.find(Aspect.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(const InstrAspect &Aspect, LegalizeAction Action) const; - - std::pair findLegalAction(const InstrAspect &Aspect, - LegalizeAction Action) const { - 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; - } + ActionIndexAndTypes getAction(const MachineInstr &MI, + const MachineRegisterInfo &MRI) const; bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const; - virtual bool legalizeCustom(MachineInstr &MI, - MachineRegisterInfo &MRI, + virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder) const; private: + /// 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_GEP, 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 &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 &Actions = + AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second; + setActions(TypeIndex, Actions, SizeAndActions); + } + + /// See also setScalarInVectorAction. + /// This function let's you specify the number of elements in a vector that + /// are legal for various element sizes. + /// E.g. + /// setScalarInVectorAction( + /// G_ADD, WidenToLargerTypesAndNarrowToLargest( + /// {{8, Legal}, {16, Legal}, {32, Legal}, {64, Legal}})); + /// setLegalNrVectorLanes(BinOp, + /// { + /// {8, {4, 8, 16}}, // 4x8, 8x8 and 16x8 are legal + /// {16, {2, 4, 8}}, // 2x16, 4x16 and 8x16 are legal + /// {32, {1, 2, 4}}, // 1x32, 2x32 and 4x32 are legal + /// {64, {1, 2}}, // 1x64 and 2x642 are legal + /// }); + 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 &Actions = + NumElements2Actions[OpcodeIdx].find(ElementSize)->second; + setActions(TypeIndex, Actions, SizeAndActions); + } + + /// If an operation on a given vector type (say ) 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 &Actions = + ScalarInVectorActions[OpcodeIdx]; + 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) { +#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 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 &Actions, + const SizeAndActionsVec &SizeAndActions) { + checkFullSizeAndActionsVector(SizeAndActions); + if (Actions.size() <= TypeIndex) + Actions.resize(TypeIndex + 1); + Actions[TypeIndex] = SizeAndActions; + } + + static SmallSizeAndActionsVec + findActionInSizeAndActionsVec(const SizeAndActionsVec &Vec, + const uint32_t Size); + + /// Returns the sequence of actions the target requested to legalize + /// the scalar or pointer type. + /// E.g. findLegalAction({G_REM, 13}) should return + /// [(WidenScalar, 32), (Lower, 32)], indicating to first widen the s13 + /// scalar to 32 bits, and to then lower it, assuming the setScalarAction on + /// SREM 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[ + /// }); + ActionAndTypes findScalarLegalAction(const InstrAspect &Aspect) const; + + /// Returns the sequence of actions the target requested to legalize the + /// vector type. + ActionAndTypes 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: typedef DenseMap TypeMap; - typedef DenseMap, LegalizeAction> SIVActionMap; - - SmallVector Actions[LastOp - FirstOp + 1]; - SIVActionMap ScalarInVectorActions; - DenseMap, uint16_t> MaxLegalVectorElts; - DenseMap DefaultActions; - + SmallVector SpecifiedActions[LastOp - FirstOp + 1]; + SmallVector + ScalarSizeChangeStrategies[LastOp - FirstOp + 1]; + SmallVector + VectorElementSizeChangeStrategies[LastOp - FirstOp + 1]; bool TablesInitialized; -}; + // Data structures used by getAction: + SmallVector ScalarActions[LastOp - FirstOp + 1]; + SmallVector ScalarInVectorActions[LastOp - FirstOp + 1]; + std::map> + AddrSpace2PointerActions[LastOp - FirstOp + 1]; + std::map> + NumElements2Actions[LastOp - FirstOp + 1]; +}; } // End namespace llvm. Index: include/llvm/CodeGen/LowLevelType.h =================================================================== --- include/llvm/CodeGen/LowLevelType.h +++ include/llvm/CodeGen/LowLevelType.h @@ -23,7 +23,6 @@ class DataLayout; class Type; - /// Construct a low-level type based on an LLVM type. LLT getLLTForType(Type &Ty, const DataLayout &DL); Index: include/llvm/Support/LowLevelTypeImpl.h =================================================================== --- include/llvm/Support/LowLevelTypeImpl.h +++ include/llvm/Support/LowLevelTypeImpl.h @@ -118,47 +118,6 @@ return scalar(SizeInBits); } - /// Get a low-level type with half the size of the original, by halving the - /// size of the scalar type involved. For example `s32` will become `s16`, - /// `<2 x s32>` will become `<2 x s16>`. - LLT halfScalarSize() const { - assert(!isPointer() && getScalarSizeInBits() > 1 && - getScalarSizeInBits() % 2 == 0 && "cannot half size of this type"); - return LLT{Kind, ElementsOrAddrSpace, SizeInBits / 2}; - } - - /// Get a low-level type with twice the size of the original, by doubling the - /// size of the scalar type involved. For example `s32` will become `s64`, - /// `<2 x s32>` will become `<2 x s64>`. - LLT doubleScalarSize() const { - assert(!isPointer() && "cannot change size of this type"); - return LLT{Kind, ElementsOrAddrSpace, SizeInBits * 2}; - } - - /// Get a low-level type with half the size of the original, by halving the - /// number of vector elements of the scalar type involved. The source must be - /// a vector type with an even number of elements. For example `<4 x s32>` - /// will become `<2 x s32>`, `<2 x s32>` will become `s32`. - LLT halfElements() const { - assert(isVector() && ElementsOrAddrSpace % 2 == 0 && - "cannot half odd vector"); - if (ElementsOrAddrSpace == 2) - return scalar(SizeInBits); - - return LLT{Vector, static_cast(ElementsOrAddrSpace / 2), - SizeInBits}; - } - - /// Get a low-level type with twice the size of the original, by doubling the - /// number of vector elements of the scalar type involved. The source must be - /// a vector type. For example `<2 x s32>` will become `<4 x s32>`. Doubling - /// the number of elements in sN produces <2 x sN>. - LLT doubleElements() const { - assert(!isPointer() && "cannot double elements in pointer"); - return LLT{Vector, static_cast(ElementsOrAddrSpace * 2), - SizeInBits}; - } - void print(raw_ostream &OS) const; bool operator==(const LLT &RHS) const { Index: lib/CodeGen/GlobalISel/LegalizerHelper.cpp =================================================================== --- lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -36,26 +36,46 @@ LegalizerHelper::LegalizeResult LegalizerHelper::legalizeInstrStep(MachineInstr &MI, const LegalizerInfo &LegalizerInfo) { - auto Action = LegalizerInfo.getAction(MI, MRI); - switch (std::get<0>(Action)) { - case LegalizerInfo::Legal: - return AlreadyLegal; - case LegalizerInfo::Libcall: - return libcall(MI); - case LegalizerInfo::NarrowScalar: - return narrowScalar(MI, std::get<1>(Action), std::get<2>(Action)); - case LegalizerInfo::WidenScalar: - return widenScalar(MI, std::get<1>(Action), std::get<2>(Action)); - case LegalizerInfo::Lower: - return lower(MI, std::get<1>(Action), std::get<2>(Action)); - case LegalizerInfo::FewerElements: - return fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action)); - case LegalizerInfo::Custom: - return LegalizerInfo.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized - : UnableToLegalize; - default: - return UnableToLegalize; + const auto Actions = LegalizerInfo.getAction(MI, MRI); + LegalizeResult result; + bool AllLegal = true; + for (unsigned i = 0; i < Actions.size(); ++i) { + const auto Action = Actions[i]; + if (std::get<0>(Action) != LegalizerInfo::Legal) + AllLegal = false; + switch (std::get<0>(Action)) { + case LegalizerInfo::Legal: + result = AlreadyLegal; + break; + case LegalizerInfo::Libcall: + result = libcall(MI); + break; + case LegalizerInfo::NarrowScalar: + result = narrowScalar(MI, std::get<1>(Action), std::get<2>(Action)); + break; + case LegalizerInfo::WidenScalar: + result = widenScalar(MI, std::get<1>(Action), std::get<2>(Action)); + break; + case LegalizerInfo::Lower: + result = lower(MI, std::get<1>(Action), std::get<2>(Action)); + break; + case LegalizerInfo::FewerElements: + result = + fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action)); + break; + case LegalizerInfo::Custom: + result = LegalizerInfo.legalizeCustom(MI, MRI, MIRBuilder) + ? Legalized + : UnableToLegalize; + break; + default: + result = UnableToLegalize; + break; + } + if (result == UnableToLegalize) + return UnableToLegalize; } + return AllLegal ? AlreadyLegal : Legalized; } LegalizerHelper::LegalizeResult Index: lib/CodeGen/GlobalISel/LegalizerInfo.cpp =================================================================== --- lib/CodeGen/GlobalISel/LegalizerInfo.cpp +++ lib/CodeGen/GlobalISel/LegalizerInfo.cpp @@ -25,38 +25,119 @@ #include "llvm/CodeGen/ValueTypes.h" #include "llvm/IR/Type.h" #include "llvm/Target/TargetOpcodes.h" + +#include +#include using namespace llvm; LegalizerInfo::LegalizerInfo() : TablesInitialized(false) { - // FIXME: these two can be legalized to the fundamental load/store Jakob - // proposed. Once loads & stores are supported. - DefaultActions[TargetOpcode::G_ANYEXT] = Legal; - DefaultActions[TargetOpcode::G_TRUNC] = Legal; + // Set defaults. + // By default, G_FNEG is lowered for all bitsizes. + setScalarAction(TargetOpcode::G_ANYEXT, 0, {{1, Legal}}); + setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}}); + + setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}}); + setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}}); - DefaultActions[TargetOpcode::G_INTRINSIC] = Legal; - DefaultActions[TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS] = Legal; + setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}}); - DefaultActions[TargetOpcode::G_ADD] = NarrowScalar; - DefaultActions[TargetOpcode::G_LOAD] = NarrowScalar; - DefaultActions[TargetOpcode::G_STORE] = NarrowScalar; + setLegalizeScalarToDifferentSizeStrategy( + TargetOpcode::G_ADD, 0, narrowToSmallerAndUnsupportedIfTooSmall); + setLegalizeScalarToDifferentSizeStrategy( + TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall); + setLegalizeScalarToDifferentSizeStrategy( + TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall); + setLegalizeScalarToDifferentSizeStrategy( + TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall); - DefaultActions[TargetOpcode::G_BRCOND] = WidenScalar; - DefaultActions[TargetOpcode::G_INSERT] = NarrowScalar; - DefaultActions[TargetOpcode::G_FNEG] = Lower; + setLegalizeScalarToDifferentSizeStrategy( + TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise); } void LegalizerInfo::computeTables() { - 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()); + assert(TablesInitialized == false); + + // compute based on information provided through setAction calls. + for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) { + const unsigned Opcode = FirstOp + OpcodeIdx; + for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size(); + ++TypeIdx) { + // 0. Collect information specified through the setAction API. + // For scalar types: + SizeAndActionsVec ScalarSpecifiedActions; + // For pointer types: + std::map AddressSpace2SpecifiedActions; + // For vector types: + std::map ElemSize2SpecifiedActions; + for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) { + const LLT Type = LLT2Action.first; + const LegalizeAction Action = LLT2Action.second; + SizeAndActionsVec &v = + Type.isPointer() + ? AddressSpace2SpecifiedActions[Type.getAddressSpace()] + : Type.isVector() + ? ElemSize2SpecifiedActions[Type.getElementType() + .getSizeInBits()] + + : ScalarSpecifiedActions; + v.push_back({Type.getSizeInBits(), Action}); + } + + // 1. Handle scalar types + { + // Decide how to handle bit sizes for which no explicit specification + // was given. + SizeChangeStrategy S = &unsupportedExceptFor; + if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() && + ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr) + S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx]; + std::sort(ScalarSpecifiedActions.begin(), ScalarSpecifiedActions.end()); + checkPartialSizeAndActionsVector(ScalarSpecifiedActions); + setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions)); } + + // 2. Handle pointer types + for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) { + std::sort(PointerSpecifiedActions.second.begin(), + PointerSpecifiedActions.second.end()); + checkPartialSizeAndActionsVector(PointerSpecifiedActions.second); + // For pointer types, we assume that there isn't a meaningfull way + // to change the number of bits used in the pointer. + setPointerAction(Opcode, TypeIdx, PointerSpecifiedActions.first, + unsupportedExceptFor(PointerSpecifiedActions.second)); + } + + // 3. Handle vector types + SizeAndActionsVec ElementSizesSeen; + for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) { + std::sort(VectorSpecifiedActions.second.begin(), + VectorSpecifiedActions.second.end()); + const uint16_t ElementSize = VectorSpecifiedActions.first; + ElementSizesSeen.push_back({ElementSize, Legal}); + checkPartialSizeAndActionsVector(VectorSpecifiedActions.second); + // For vector types, we assume that the best way to adapt the number + // of elements is to the next larger number of elements type for which + // the vector type is legal, unless there is no such type. In that case, + // legalize towards a vector type with a smaller number of elements. + SizeAndActionsVec NumElementsActions; + for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) { + assert(BitsizeAndAction.first % ElementSize == 0); + const uint16_t NumElements = BitsizeAndAction.first / ElementSize; + NumElementsActions.push_back({NumElements, BitsizeAndAction.second}); + } + setVectorNumElementAction( + Opcode, TypeIdx, ElementSize, + moreToWiderTypesAndLessToWidest(NumElementsActions)); + } + std::sort(ElementSizesSeen.begin(), ElementSizesSeen.end()); + SizeChangeStrategy VectorElementSizeChangeStrategy = + &unsupportedExceptFor; + if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() && + VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr) + VectorElementSizeChangeStrategy = + VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx]; + setScalarInVectorAction( + Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen)); } } @@ -67,79 +148,40 @@ // 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 +LegalizerInfo::ActionAndTypes LegalizerInfo::getAction(const InstrAspect &Aspect) 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. - // Nothing is going to go well with types that aren't a power of 2 yet, so - // don't even try because we might make things worse. - if (!isPowerOf2_64(Aspect.Type.getSizeInBits())) - return std::make_pair(Unsupported, LLT()); - // FIXME: the long-term plan calls for expansion in terms of load/store (if // they're not legal). if (Aspect.Opcode == TargetOpcode::G_SEQUENCE || Aspect.Opcode == TargetOpcode::G_EXTRACT || Aspect.Opcode == TargetOpcode::G_MERGE_VALUES || Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES) - return std::make_pair(Legal, Aspect.Type); - - LegalizeAction Action = findInActions(Aspect); - if (Action != NotFound) - return findLegalAction(Aspect, Action); - - unsigned Opcode = Aspect.Opcode; - LLT Ty = Aspect.Type; - if (!Ty.isVector()) { - auto DefaultAction = DefaultActions.find(Aspect.Opcode); - if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal) - return std::make_pair(Legal, Ty); - - if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower) - return std::make_pair(Lower, Ty); - - if (DefaultAction == DefaultActions.end() || - DefaultAction->second != NarrowScalar) - return std::make_pair(Unsupported, LLT()); - return findLegalAction(Aspect, NarrowScalar); - } + return {std::make_pair(Legal, Aspect.Type)}; - 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(Aspect, 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(Aspect, 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(Aspect, FewerElements); + if (Aspect.Type.isScalar() || Aspect.Type.isPointer()) + return findScalarLegalAction(Aspect); + if (Aspect.Type.isVector()) + return findVectorLegalAction(Aspect); + return {}; } -std::tuple +LegalizerInfo::ActionIndexAndTypes LegalizerInfo::getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const { + ActionIndexAndTypes result; SmallBitVector SeenTypes(8); const MCOperandInfo *OpInfo = MI.getDesc().OpInfo; + // FIXME: probably we'll need to cache the results here somehow? for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) { if (!OpInfo[i].isGenericType()) continue; - // We don't want to repeatedly check the same operand index, that - // could get expensive. + // We must only record actions once for each TypeIdx; otherwise we'd + // try to legalize operands multiple times down the line. unsigned TypeIdx = OpInfo[i].getGenericTypeIndex(); if (SeenTypes[TypeIdx]) continue; @@ -147,50 +189,195 @@ SeenTypes.set(TypeIdx); LLT Ty = MRI.getType(MI.getOperand(i).getReg()); - auto Action = getAction({MI.getOpcode(), TypeIdx, Ty}); - if (Action.first != Legal) - return std::make_tuple(Action.first, TypeIdx, Action.second); + auto Actions = getAction({MI.getOpcode(), TypeIdx, Ty}); + for (auto &Action : Actions) + result.push_back(std::make_tuple(Action.first, TypeIdx, Action.second)); } - return std::make_tuple(Legal, 0, LLT{}); + return result; } bool LegalizerInfo::isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const { - return std::get<0>(getAction(MI, MRI)) == Legal; + const ActionIndexAndTypes Actions = getAction(MI, MRI); + for (auto Action : Actions) + if (std::get<0>(Action) != Legal) + return false; + return true; +} + +bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI, + MachineIRBuilder &MIRBuilder) const { + return false; +} + +LegalizerInfo::SizeAndActionsVec +LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest( + const SizeAndActionsVec &v, LegalizeAction IncreaseAction, + LegalizeAction DecreaseAction) { + SizeAndActionsVec result; + unsigned LargestSizeSoFar = 0; + if (v.size() >= 1 && v[0].first != 1) + result.push_back({1, IncreaseAction}); + for (size_t i = 0; i < v.size(); ++i) { + result.push_back(v[i]); + LargestSizeSoFar = v[i].first; + if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) { + result.push_back({LargestSizeSoFar + 1, IncreaseAction}); + LargestSizeSoFar = v[i].first + 1; + } + } + result.push_back({LargestSizeSoFar + 1, DecreaseAction}); + return result; +} + +LegalizerInfo::SizeAndActionsVec +LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest( + const SizeAndActionsVec &v, LegalizeAction DecreaseAction, + LegalizeAction IncreaseAction) { + SizeAndActionsVec result; + if (v.size() == 0 || v[0].first != 1) + result.push_back({1, IncreaseAction}); + for (size_t i = 0; i < v.size(); ++i) { + result.push_back(v[i]); + if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) { + result.push_back({v[i].first + 1, DecreaseAction}); + } + } + return result; } -LLT LegalizerInfo::findLegalType(const InstrAspect &Aspect, - LegalizeAction Action) const { - switch(Action) { - default: - llvm_unreachable("Cannot find legal type"); +LegalizerInfo::SmallSizeAndActionsVec +LegalizerInfo::findActionInSizeAndActionsVec(const SizeAndActionsVec &Vec, + const uint32_t Size) { + assert(Size >= 1); + // Find the first element in Vec that has a bitsize equal to or smaller + // than the requested bit size. We can do that using reverse iterators + int VecIdx = -1; + for (int i = Vec.size() - 1; i >= 0; --i) { + const uint32_t BitSize = Vec[i].first; + if (BitSize <= Size) { + VecIdx = i; + break; + } + } + assert(VecIdx != -1); + LegalizeAction Action = Vec[VecIdx].second; + switch (Action) { case Legal: case Lower: case Libcall: case Custom: - return Aspect.Type; - case NarrowScalar: { - return findLegalType(Aspect, - [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); }); + return {{Size, Action}}; + case FewerElements: + // Special case for scalarization: + if (Vec == SizeAndActionsVec({{1, FewerElements}})) + return {{1, FewerElements}}; + case NarrowScalar: + for (int i = VecIdx - 1; i >= 0; --i) + if (!NeedsLegalizingToDifferentSize(Vec[i].second)) { + if (Vec[i].second == Legal) + return {{Vec[i].first, Action}}; + else + return {{Vec[i].first, Action}, {Vec[i].first, Vec[i].second}}; + } + llvm_unreachable(""); + case WidenScalar: + case MoreElements: + for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i) + if (!NeedsLegalizingToDifferentSize(Vec[i].second)) { + if (Vec[i].second == Legal) + return {{Vec[i].first, Action}}; + else + return {{Vec[i].first, Action}, {Vec[i].first, Vec[i].second}}; + } + llvm_unreachable(""); + case Unsupported: + return {{Size, Unsupported}}; + case NotFound: + llvm_unreachable("NotFound"); } - case WidenScalar: { - return findLegalType(Aspect, [&](LLT Ty) -> LLT { - return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize(); - }); +} + +LegalizerInfo::ActionAndTypes +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; + if (Aspect.Type.isPointer() && + AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) == + AddrSpace2PointerActions[OpcodeIdx].end()) { + return {{NotFound, LLT()}}; } - case FewerElements: { - return findLegalType(Aspect, - [&](LLT Ty) -> LLT { return Ty.halfElements(); }); + const SmallVector &Actions = + Aspect.Type.isPointer() + ? AddrSpace2PointerActions[OpcodeIdx] + .find(Aspect.Type.getAddressSpace()) + ->second + : ScalarActions[OpcodeIdx]; + if (Aspect.Idx >= Actions.size()) + return {{NotFound, LLT()}}; + const SizeAndActionsVec &Vec = Actions[Aspect.Idx]; + // FIXME: speed up this search, e.g. by using a results cache for repeated + // queries? + + ActionAndTypes result; + for (auto SizeAndAction : + findActionInSizeAndActionsVec(Vec, Aspect.Type.getSizeInBits())) { + result.push_back({SizeAndAction.second, + Aspect.Type.isScalar() + ? LLT::scalar(SizeAndAction.first) + : LLT::pointer(Aspect.Type.getAddressSpace(), + SizeAndAction.first)}); } - case MoreElements: { - return findLegalType(Aspect, - [&](LLT Ty) -> LLT { return Ty.doubleElements(); }); + return result; +} + +LegalizerInfo::ActionAndTypes +LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const { + assert(Aspect.Type.isVector()); + // First legalize the vector element size, then legalize the number of + // lanes in the vector. + if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp) + return {{NotFound, Aspect.Type}}; + const unsigned OpcodeIdx = Aspect.Opcode - FirstOp; + const unsigned TypeIdx = Aspect.Idx; + if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size()) + return {{NotFound, Aspect.Type}}; + const SizeAndActionsVec &ElemSizeVec = + ScalarInVectorActions[OpcodeIdx][TypeIdx]; + + ActionAndTypes result; + LLT IntermediateType; + for (auto &SizeAndAction : findActionInSizeAndActionsVec( + ElemSizeVec, Aspect.Type.getScalarSizeInBits())) { + IntermediateType = + LLT::vector(Aspect.Type.getNumElements(), SizeAndAction.first); + // No need to push in an "already-legal" action here, as that will be + // pushed in by the number-of-elements legalization below. + if (SizeAndAction.second == Legal) + continue; + result.push_back({SizeAndAction.second, IntermediateType}); + if (SizeAndAction.second == NotFound || SizeAndAction.second == Unsupported) + return result; } + + auto i = NumElements2Actions[OpcodeIdx].find( + IntermediateType.getScalarSizeInBits()); + if (i == NumElements2Actions[OpcodeIdx].end()) { + return {{NotFound, IntermediateType}}; + } + const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx]; + for (auto &SizeAndAction : findActionInSizeAndActionsVec( + NumElementsVec, IntermediateType.getNumElements())) { + // No need to push in an "already-legal" action here, if there was + // already another action recorded. + if (SizeAndAction.second == Legal && result.size() != 0) + continue; + result.push_back({SizeAndAction.second, + LLT::vector(SizeAndAction.first, + IntermediateType.getScalarSizeInBits())}); } -} -bool LegalizerInfo::legalizeCustom(MachineInstr &MI, - MachineRegisterInfo &MRI, - MachineIRBuilder &MIRBuilder) const { - return false; + return result; } Index: lib/Support/LowLevelType.cpp =================================================================== --- lib/Support/LowLevelType.cpp +++ lib/Support/LowLevelType.cpp @@ -43,5 +43,5 @@ assert(isScalar() && "unexpected type"); OS << "s" << getScalarSizeInBits(); } else - llvm_unreachable("trying to print an invalid type"); + OS << "LLT_invalid"; } Index: lib/Target/AArch64/AArch64LegalizerInfo.cpp =================================================================== --- lib/Target/AArch64/AArch64LegalizerInfo.cpp +++ lib/Target/AArch64/AArch64LegalizerInfo.cpp @@ -27,6 +27,112 @@ #error "You shouldn't build this" #endif + +/// FIXME: The following static functions are SizeChangeStrategy functions +/// that are meant to temporarily mimic the behaviour of the old legalization +/// based on doubling/halving non-legal types as closely as possible. This is +/// not entirly possible as only legalizing the types that are exactly a power +/// of 2 times the size of the legal types would require specifying all those +/// sizes explicitly. +/// In practice, not specifying those isn't a problem, and the below functions +/// should disappear quickly as we add support for legalizing non-power-of-2 +/// sized types further. +static void +addAndInterleaveWithUnsupported(LegalizerInfo::SizeAndActionsVec &result, + const LegalizerInfo::SizeAndActionsVec &v) { + for (unsigned i = 0; i < v.size(); ++i) { + result.push_back(v[i]); + if (i + 1 < v[i].first && i + 1 < v.size() && + v[i + 1].first != v[i].first + 1) + result.push_back({v[i].first + 1, LegalizerInfo::Unsupported}); + } +} + +static LegalizerInfo::SizeAndActionsVec +widen_1_narrow_128_ToLargest(const LegalizerInfo::SizeAndActionsVec &v) { + assert(v.size() >= 1); + assert(v[0].first > 2); + LegalizerInfo::SizeAndActionsVec result = {{1, LegalizerInfo::WidenScalar}, + {2, LegalizerInfo::Unsupported}}; + addAndInterleaveWithUnsupported(result, v); + auto Largest = result.back().first; + assert(Largest + 1 < 128); + result.push_back({Largest + 1, LegalizerInfo::Unsupported}); + result.push_back({128, LegalizerInfo::NarrowScalar}); + result.push_back({129, LegalizerInfo::Unsupported}); + return result; +} + +static LegalizerInfo::SizeAndActionsVec +widen_16(const LegalizerInfo::SizeAndActionsVec &v) { + assert(v.size() >= 1); + assert(v[0].first > 17); + LegalizerInfo::SizeAndActionsVec result = {{1, LegalizerInfo::Unsupported}, + {16, LegalizerInfo::WidenScalar}, + {17, LegalizerInfo::Unsupported}}; + addAndInterleaveWithUnsupported(result, v); + auto Largest = result.back().first; + result.push_back({Largest + 1, LegalizerInfo::Unsupported}); + return result; +} + +static LegalizerInfo::SizeAndActionsVec +widen_1_8_16(const LegalizerInfo::SizeAndActionsVec &v) { + assert(v.size() >= 1); + assert(v[0].first > 17); + LegalizerInfo::SizeAndActionsVec result = { + {1, LegalizerInfo::WidenScalar}, {2, LegalizerInfo::Unsupported}, + {8, LegalizerInfo::WidenScalar}, {9, LegalizerInfo::Unsupported}, + {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}}; + addAndInterleaveWithUnsupported(result, v); + auto Largest = result.back().first; + result.push_back({Largest + 1, LegalizerInfo::Unsupported}); + return result; +} + +static LegalizerInfo::SizeAndActionsVec +widen_1_8_16_narrowToLargest(const LegalizerInfo::SizeAndActionsVec &v) { + assert(v.size() >= 1); + assert(v[0].first > 17); + LegalizerInfo::SizeAndActionsVec result = { + {1, LegalizerInfo::WidenScalar}, {2, LegalizerInfo::Unsupported}, + {8, LegalizerInfo::WidenScalar}, {9, LegalizerInfo::Unsupported}, + {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}}; + addAndInterleaveWithUnsupported(result, v); + auto Largest = result.back().first; + result.push_back({Largest + 1, LegalizerInfo::NarrowScalar}); + return result; +} + +static LegalizerInfo::SizeAndActionsVec +widen_1_8_16_narrowLarger(const LegalizerInfo::SizeAndActionsVec &v) { + assert(v.size() >= 1); + assert(v[0].first > 17); + LegalizerInfo::SizeAndActionsVec result = { + {1, LegalizerInfo::WidenScalar}, {2, LegalizerInfo::Unsupported}, + {8, LegalizerInfo::WidenScalar}, {9, LegalizerInfo::Unsupported}, + {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}}; + addAndInterleaveWithUnsupported(result, v); + auto Largest = result.back().first; + result.push_back({Largest + 1, LegalizerInfo::NarrowScalar}); + return result; +} + +static LegalizerInfo::SizeAndActionsVec +widen_1_8_16_32(const LegalizerInfo::SizeAndActionsVec &v) { + assert(v.size() >= 1); + assert(v[0].first > 33); + LegalizerInfo::SizeAndActionsVec result = { + {1, LegalizerInfo::WidenScalar}, {2, LegalizerInfo::Unsupported}, + {8, LegalizerInfo::WidenScalar}, {9, LegalizerInfo::Unsupported}, + {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}, + {32, LegalizerInfo::WidenScalar}, {33, LegalizerInfo::Unsupported}}; + addAndInterleaveWithUnsupported(result, v); + auto Largest = result.back().first; + result.push_back({Largest + 1, LegalizerInfo::Unsupported}); + return result; +} + AArch64LegalizerInfo::AArch64LegalizerInfo() { using namespace TargetOpcode; const LLT p0 = LLT::pointer(0, 64); @@ -45,15 +151,14 @@ for (auto Ty : {s32, s64, v2s32, v4s32, v2s64}) setAction({BinOp, Ty}, Legal); - for (auto Ty : {s1, s8, s16}) - setAction({BinOp, Ty}, WidenScalar); + setLegalizeScalarToDifferentSizeStrategy(BinOp, 0, + widen_1_8_16_narrowLarger); } setAction({G_GEP, p0}, Legal); setAction({G_GEP, 1, s64}, Legal); - for (auto Ty : {s1, s8, s16, s32}) - setAction({G_GEP, 1, Ty}, WidenScalar); + setLegalizeScalarToDifferentSizeStrategy(G_GEP, 1, widen_1_8_16_32); setAction({G_PTR_MASK, p0}, Legal); @@ -61,16 +166,17 @@ for (auto Ty : {s32, s64}) setAction({BinOp, Ty}, Legal); - for (auto Ty : {s1, s8, s16}) - setAction({BinOp, Ty}, WidenScalar); + setLegalizeScalarToDifferentSizeStrategy(BinOp, 0, widen_1_8_16); } for (unsigned BinOp : {G_SREM, G_UREM}) for (auto Ty : { s1, s8, s16, s32, s64 }) setAction({BinOp, Ty}, Lower); - for (unsigned Op : {G_SMULO, G_UMULO}) - setAction({Op, s64}, Lower); + for (unsigned Op : {G_SMULO, G_UMULO}) { + setAction({Op, 0, s64}, Lower); + setAction({Op, 1, s1}, Legal); + } for (unsigned Op : {G_UADDE, G_USUBE, G_SADDO, G_SSUBO, G_SMULH, G_UMULH}) { for (auto Ty : { s32, s64 }) @@ -92,8 +198,9 @@ setAction({G_INSERT, Ty}, Legal); setAction({G_INSERT, 1, Ty}, Legal); } + setLegalizeScalarToDifferentSizeStrategy(G_INSERT, 0, + widen_1_8_16_narrowToLargest); for (auto Ty : {s1, s8, s16}) { - setAction({G_INSERT, Ty}, WidenScalar); setAction({G_INSERT, 1, Ty}, Legal); // FIXME: Can't widen the sources because that violates the constraints on // G_INSERT (It seems entirely reasonable that inputs shouldn't overlap). @@ -103,7 +210,8 @@ for (auto Ty : {s8, s16, s32, s64, p0, v2s32}) setAction({MemOp, Ty}, Legal); - setAction({MemOp, s1}, WidenScalar); + setLegalizeScalarToDifferentSizeStrategy(MemOp, 0, + widen_1_narrow_128_ToLargest); // And everything's fine in addrspace 0. setAction({MemOp, 1, p0}, Legal); @@ -117,19 +225,15 @@ setAction({G_CONSTANT, p0}, Legal); - for (auto Ty : {s1, s8, s16}) - setAction({TargetOpcode::G_CONSTANT, Ty}, WidenScalar); - - setAction({TargetOpcode::G_FCONSTANT, s16}, WidenScalar); + setLegalizeScalarToDifferentSizeStrategy(G_CONSTANT, 0, widen_1_8_16); + setLegalizeScalarToDifferentSizeStrategy(G_FCONSTANT, 0, widen_16); setAction({G_ICMP, s1}, Legal); setAction({G_ICMP, 1, s32}, Legal); setAction({G_ICMP, 1, s64}, Legal); setAction({G_ICMP, 1, p0}, Legal); - for (auto Ty : {s1, s8, s16}) { - setAction({G_ICMP, 1, Ty}, WidenScalar); - } + setLegalizeScalarToDifferentSizeStrategy(G_ICMP, 1, widen_1_8_16); setAction({G_FCMP, s1}, Legal); setAction({G_FCMP, 1, s32}, Legal); @@ -171,12 +275,10 @@ setAction({G_SITOFP, 1, Ty}, Legal); setAction({G_UITOFP, 1, Ty}, Legal); } - for (auto Ty : { s1, s8, s16 }) { - setAction({G_FPTOSI, 0, Ty}, WidenScalar); - setAction({G_FPTOUI, 0, Ty}, WidenScalar); - setAction({G_SITOFP, 1, Ty}, WidenScalar); - setAction({G_UITOFP, 1, Ty}, WidenScalar); - } + setLegalizeScalarToDifferentSizeStrategy(G_FPTOSI, 0, widen_1_8_16); + setLegalizeScalarToDifferentSizeStrategy(G_FPTOUI, 0, widen_1_8_16); + setLegalizeScalarToDifferentSizeStrategy(G_SITOFP, 1, widen_1_8_16); + setLegalizeScalarToDifferentSizeStrategy(G_UITOFP, 1, widen_1_8_16); for (auto Ty : { s32, s64 }) { setAction({G_FPTOSI, 1, Ty}, Legal); @@ -191,8 +293,7 @@ setAction({G_BRINDIRECT, p0}, Legal); // Select - for (auto Ty : {s1, s8, s16}) - setAction({G_SELECT, Ty}, WidenScalar); + setLegalizeScalarToDifferentSizeStrategy(G_SELECT, 0, widen_1_8_16); for (auto Ty : {s32, s64, p0}) setAction({G_SELECT, Ty}, Legal); Index: unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp =================================================================== --- unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp +++ unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp @@ -49,72 +49,166 @@ using namespace TargetOpcode; LegalizerInfo L; // Typical RISCy set of operations based on AArch64. - L.setAction({G_ADD, LLT::scalar(8)}, LegalizerInfo::WidenScalar); - L.setAction({G_ADD, LLT::scalar(16)}, LegalizerInfo::WidenScalar); - L.setAction({G_ADD, LLT::scalar(32)}, LegalizerInfo::Legal); - L.setAction({G_ADD, LLT::scalar(64)}, LegalizerInfo::Legal); + for (auto Op : {G_ADD, G_SUB}) { + for (unsigned Size : {32, 64}) + L.setAction({Op, 0, LLT::scalar(Size)}, LegalizerInfo::Legal); + L.setLegalizeScalarToDifferentSizeStrategy( + Op, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest); + } + L.computeTables(); - // Check we infer the correct types and actually do what we're told. - ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(8)}), - std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32))); - ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(16)}), - std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32))); - ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(32)}), - std::make_pair(LegalizerInfo::Legal, LLT::scalar(32))); - ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(64)}), - std::make_pair(LegalizerInfo::Legal, LLT::scalar(64))); - - // Make sure the default for over-sized types applies. - ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(128)}), - std::make_pair(LegalizerInfo::NarrowScalar, LLT::scalar(64))); + for (auto &opcode : {G_ADD, G_SUB}) { + // Check we infer the correct types and actually do what we're told. + ASSERT_EQ(L.getAction({opcode, LLT::scalar(8)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::scalar(32)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(16)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::scalar(32)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(32)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::Legal, LLT::scalar(32)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(64)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::Legal, LLT::scalar(64)}})); + + // Make sure the default for over-sized types applies. + ASSERT_EQ(L.getAction({opcode, LLT::scalar(128)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::NarrowScalar, LLT::scalar(64)}})); + // Make sure we also handle unusual sizes + ASSERT_EQ(L.getAction({opcode, LLT::scalar(1)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::scalar(32)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(31)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::scalar(32)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(33)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::scalar(64)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(63)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::scalar(64)}})); + ASSERT_EQ(L.getAction({opcode, LLT::scalar(65)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::NarrowScalar, LLT::scalar(64)}})); + } } TEST(LegalizerInfoTest, VectorRISC) { using namespace TargetOpcode; LegalizerInfo L; // Typical RISCy set of operations based on ARM. - L.setScalarInVectorAction(G_ADD, LLT::scalar(8), LegalizerInfo::Legal); - L.setScalarInVectorAction(G_ADD, LLT::scalar(16), LegalizerInfo::Legal); - L.setScalarInVectorAction(G_ADD, LLT::scalar(32), LegalizerInfo::Legal); - L.setAction({G_ADD, LLT::vector(8, 8)}, LegalizerInfo::Legal); L.setAction({G_ADD, LLT::vector(16, 8)}, LegalizerInfo::Legal); L.setAction({G_ADD, LLT::vector(4, 16)}, LegalizerInfo::Legal); L.setAction({G_ADD, LLT::vector(8, 16)}, LegalizerInfo::Legal); L.setAction({G_ADD, LLT::vector(2, 32)}, LegalizerInfo::Legal); L.setAction({G_ADD, LLT::vector(4, 32)}, LegalizerInfo::Legal); + + L.setLegalizeVectorElementToDifferentSizeStrategy(G_ADD, 0, + LegalizerInfo::widenToLargerTypesUnsupportedOtherwise); + + L.setAction({G_SUB, 0, LLT::scalar(32)}, LegalizerInfo::Legal); + L.computeTables(); // Check we infer the correct types and actually do what we're told for some // simple cases. - ASSERT_EQ(L.getAction({G_ADD, LLT::vector(2, 8)}), - std::make_pair(LegalizerInfo::MoreElements, LLT::vector(8, 8))); ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 8)}), - std::make_pair(LegalizerInfo::Legal, LLT::vector(8, 8))); - ASSERT_EQ( - L.getAction({G_ADD, LLT::vector(8, 32)}), - std::make_pair(LegalizerInfo::FewerElements, LLT::vector(4, 32))); + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::Legal, LLT::vector(8, 8)}})); + ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 7)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::vector(8, 8)}})); + ASSERT_EQ(L.getAction({G_ADD, LLT::vector(2, 8)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::MoreElements, LLT::vector(8, 8)}})); + ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 32)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::FewerElements, LLT::vector(4, 32)}})); + // Check a few non-power-of-2 sizes: + ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 8)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::MoreElements, LLT::vector(8, 8)}})); + ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 3)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::WidenScalar, LLT::vector(3, 8)}, + {LegalizerInfo::MoreElements, LLT::vector(8, 8)}})); } TEST(LegalizerInfoTest, MultipleTypes) { using namespace TargetOpcode; LegalizerInfo L; LLT p0 = LLT::pointer(0, 64); - LLT s32 = LLT::scalar(32); LLT s64 = LLT::scalar(64); // Typical RISCy set of operations based on AArch64. L.setAction({G_PTRTOINT, 0, s64}, LegalizerInfo::Legal); L.setAction({G_PTRTOINT, 1, p0}, LegalizerInfo::Legal); - L.setAction({G_PTRTOINT, 0, s32}, LegalizerInfo::WidenScalar); + L.setLegalizeScalarToDifferentSizeStrategy( + G_PTRTOINT, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest); + L.computeTables(); // Check we infer the correct types and actually do what we're told. ASSERT_EQ(L.getAction({G_PTRTOINT, 0, s64}), - std::make_pair(LegalizerInfo::Legal, s64)); + LegalizerInfo::ActionAndTypes({{LegalizerInfo::Legal, s64}})); ASSERT_EQ(L.getAction({G_PTRTOINT, 1, p0}), - std::make_pair(LegalizerInfo::Legal, p0)); + LegalizerInfo::ActionAndTypes({{LegalizerInfo::Legal, p0}})); + // Make sure we also handle unusual sizes + ASSERT_EQ( + L.getAction({G_PTRTOINT, 0, LLT::scalar(65)}), + LegalizerInfo::ActionAndTypes({{LegalizerInfo::NarrowScalar, s64}})); + ASSERT_EQ(L.getAction({G_PTRTOINT, 1, LLT::pointer(0, 32)}), + LegalizerInfo::ActionAndTypes( + {{LegalizerInfo::Unsupported, LLT::pointer(0, 32)}})); +} + +TEST(LegalizerInfoTest, MultipleSteps) { + using namespace TargetOpcode; + LegalizerInfo L; + LLT s64 = LLT::scalar(64); + LLT s32 = LLT::scalar(32); + + L.setAction({G_UREM, 0, s32}, LegalizerInfo::Lower); + L.setAction({G_UREM, 0, s64}, LegalizerInfo::Lower); + + L.setLegalizeScalarToDifferentSizeStrategy( + G_UREM, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest); + + L.computeTables(); + + // Check we infer the correct types and actually do what we're told. + ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(8)}), + LegalizerInfo::ActionAndTypes({ + std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)), + std::make_pair(LegalizerInfo::Lower, LLT::scalar(32)), + })); +} + +TEST(LegalizerInfoTest, SizeChangeStrategy) { + using namespace TargetOpcode; + LegalizerInfo L; + for (unsigned Size : {1, 8, 16, 32}) + L.setAction({G_UREM, 0, LLT::scalar(Size)}, LegalizerInfo::Legal); + + L.computeTables(); + + // Check we infer the correct types and actually do what we're told. + for (unsigned Size : {1, 8, 16, 32}) { + ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(Size)}), + LegalizerInfo::ActionAndTypes({ + std::make_pair(LegalizerInfo::Legal, LLT::scalar(Size)), + })); + } + for (unsigned Size : {2, 7, 9, 17, 31, 33}) { + ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(Size)}), + LegalizerInfo::ActionAndTypes({ + std::make_pair(LegalizerInfo::Unsupported, LLT::scalar(Size)), + })); + } } } Index: unittests/CodeGen/LowLevelTypeTest.cpp =================================================================== --- unittests/CodeGen/LowLevelTypeTest.cpp +++ unittests/CodeGen/LowLevelTypeTest.cpp @@ -36,36 +36,22 @@ for (unsigned S : {1U, 17U, 32U, 64U, 0xfffffU}) { const LLT Ty = LLT::scalar(S); - const LLT HalfTy = (S % 2) == 0 ? Ty.halfScalarSize() : Ty; - const LLT DoubleTy = Ty.doubleScalarSize(); // Test kind. - for (const LLT TestTy : {Ty, HalfTy, DoubleTy}) { - ASSERT_TRUE(TestTy.isValid()); - ASSERT_TRUE(TestTy.isScalar()); + ASSERT_TRUE(Ty.isValid()); + ASSERT_TRUE(Ty.isScalar()); - ASSERT_FALSE(TestTy.isPointer()); - ASSERT_FALSE(TestTy.isVector()); - } + ASSERT_FALSE(Ty.isPointer()); + ASSERT_FALSE(Ty.isVector()); // Test sizes. EXPECT_EQ(S, Ty.getSizeInBits()); EXPECT_EQ(S, Ty.getScalarSizeInBits()); - EXPECT_EQ(S*2, DoubleTy.getSizeInBits()); - EXPECT_EQ(S*2, DoubleTy.getScalarSizeInBits()); - - if ((S % 2) == 0) { - EXPECT_EQ(S/2, HalfTy.getSizeInBits()); - EXPECT_EQ(S/2, HalfTy.getScalarSizeInBits()); - } - // Test equality operators. EXPECT_TRUE(Ty == Ty); EXPECT_FALSE(Ty != Ty); - EXPECT_NE(Ty, DoubleTy); - // Test Type->LLT conversion. Type *IRTy = IntegerType::get(C, S); EXPECT_EQ(Ty, getLLTForType(*IRTy, DL)); @@ -90,61 +76,18 @@ // Test getElementType(). EXPECT_EQ(STy, VTy.getElementType()); - const LLT HalfSzTy = ((S % 2) == 0) ? VTy.halfScalarSize() : VTy; - const LLT DoubleSzTy = VTy.doubleScalarSize(); - - // halfElements requires an even number of elements. - const LLT HalfEltIfEvenTy = ((Elts % 2) == 0) ? VTy.halfElements() : VTy; - const LLT DoubleEltTy = VTy.doubleElements(); - // Test kind. - for (const LLT TestTy : {VTy, HalfSzTy, DoubleSzTy, DoubleEltTy}) { - ASSERT_TRUE(TestTy.isValid()); - ASSERT_TRUE(TestTy.isVector()); - - ASSERT_FALSE(TestTy.isScalar()); - ASSERT_FALSE(TestTy.isPointer()); - } - - // Test halving elements to a scalar. - { - ASSERT_TRUE(HalfEltIfEvenTy.isValid()); - ASSERT_FALSE(HalfEltIfEvenTy.isPointer()); - if (Elts > 2) { - ASSERT_TRUE(HalfEltIfEvenTy.isVector()); - } else { - ASSERT_FALSE(HalfEltIfEvenTy.isVector()); - EXPECT_EQ(STy, HalfEltIfEvenTy); - } - } + ASSERT_TRUE(VTy.isValid()); + ASSERT_TRUE(VTy.isVector()); + ASSERT_FALSE(VTy.isScalar()); + ASSERT_FALSE(VTy.isPointer()); // Test sizes. EXPECT_EQ(S * Elts, VTy.getSizeInBits()); EXPECT_EQ(S, VTy.getScalarSizeInBits()); EXPECT_EQ(Elts, VTy.getNumElements()); - if ((S % 2) == 0) { - EXPECT_EQ((S / 2) * Elts, HalfSzTy.getSizeInBits()); - EXPECT_EQ(S / 2, HalfSzTy.getScalarSizeInBits()); - EXPECT_EQ(Elts, HalfSzTy.getNumElements()); - } - - EXPECT_EQ((S * 2) * Elts, DoubleSzTy.getSizeInBits()); - EXPECT_EQ(S * 2, DoubleSzTy.getScalarSizeInBits()); - EXPECT_EQ(Elts, DoubleSzTy.getNumElements()); - - if ((Elts % 2) == 0) { - EXPECT_EQ(S * (Elts / 2), HalfEltIfEvenTy.getSizeInBits()); - EXPECT_EQ(S, HalfEltIfEvenTy.getScalarSizeInBits()); - if (Elts > 2) - EXPECT_EQ(Elts / 2, HalfEltIfEvenTy.getNumElements()); - } - - EXPECT_EQ(S * (Elts * 2), DoubleEltTy.getSizeInBits()); - EXPECT_EQ(S, DoubleEltTy.getScalarSizeInBits()); - EXPECT_EQ(Elts * 2, DoubleEltTy.getNumElements()); - // Test equality operators. EXPECT_TRUE(VTy == VTy); EXPECT_FALSE(VTy != VTy); @@ -152,10 +95,6 @@ // Test inequality operators on.. // ..different kind. EXPECT_NE(VTy, STy); - // ..different #elts. - EXPECT_NE(VTy, DoubleEltTy); - // ..different scalar size. - EXPECT_NE(VTy, DoubleSzTy); // Test Type->LLT conversion. Type *IRSTy = IntegerType::get(C, S);