Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

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