contrib/llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

   1 //===- llvm/CodeGen/GlobalISel/LegalizerInfo.h ------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// Interface for Targets to specify which operations they can successfully
  11 /// select and how the others should be expanded most efficiently.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
  16 #define LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/None.h"
  20 #include "llvm/ADT/Optional.h"
  21 #include "llvm/ADT/STLExtras.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/Support/LowLevelTypeImpl.h"
  24 #include "llvm/Target/TargetOpcodes.h"
  25 #include <cstdint>
  26 #include <cassert>
  27 #include <tuple>
  28 #include <utility>
  29
  30 namespace llvm {
  31
  32 class MachineInstr;
  33 class MachineIRBuilder;
  34 class MachineRegisterInfo;
  35
  36 /// Legalization is decided based on an instruction's opcode, which type slot
  37 /// we're considering, and what the existing type is. These aspects are gathered
  38 /// together for convenience in the InstrAspect class.
  39 struct InstrAspect {
  40   unsigned Opcode;
  41   unsigned Idx = 0;
  42   LLT Type;
  43
  44   InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
  45   InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
  46       : Opcode(Opcode), Idx(Idx), Type(Type) {}
  47
  48   bool operator==(const InstrAspect &RHS) const {
  49     return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
  50   }
  51 };
  52
  53 class LegalizerInfo {
  54 public:
  55   enum LegalizeAction : std::uint8_t {
  56     /// The operation is expected to be selectable directly by the target, and
  57     /// no transformation is necessary.
  58     Legal,
  59
  60     /// The operation should be synthesized from multiple instructions acting on
  61     /// a narrower scalar base-type. For example a 64-bit add might be
  62     /// implemented in terms of 32-bit add-with-carry.
  63     NarrowScalar,
  64
  65     /// The operation should be implemented in terms of a wider scalar
  66     /// base-type. For example a <2 x s8> add could be implemented as a <2
  67     /// x s32> add (ignoring the high bits).
  68     WidenScalar,
  69
  70     /// The (vector) operation should be implemented by splitting it into
  71     /// sub-vectors where the operation is legal. For example a <8 x s64> add
  72     /// might be implemented as 4 separate <2 x s64> adds.
  73     FewerElements,
  74
  75     /// The (vector) operation should be implemented by widening the input
  76     /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
  77     /// rarely legal, but you might perform an <8 x i8> and then only look at
  78     /// the first two results.
  79     MoreElements,
  80
  81     /// The operation itself must be expressed in terms of simpler actions on
  82     /// this target. E.g. a SREM replaced by an SDIV and subtraction.
  83     Lower,
  84
  85     /// The operation should be implemented as a call to some kind of runtime
  86     /// support library. For example this usually happens on machines that don't
  87     /// support floating-point operations natively.
  88     Libcall,
  89
  90     /// The target wants to do something special with this combination of
  91     /// operand and type. A callback will be issued when it is needed.
  92     Custom,
  93
  94     /// This operation is completely unsupported on the target. A programming
  95     /// error has occurred.
  96     Unsupported,
  97
  98     /// Sentinel value for when no action was found in the specified table.
  99     NotFound,
 100   };
 101
 102   LegalizerInfo();
 103   virtual ~LegalizerInfo() = default;
 104
 105   /// Compute any ancillary tables needed to quickly decide how an operation
 106   /// should be handled. This must be called after all "set*Action"methods but
 107   /// before any query is made or incorrect results may be returned.
 108   void computeTables();
 109
 110   static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
 111     switch (Action) {
 112     case NarrowScalar:
 113     case WidenScalar:
 114     case FewerElements:
 115     case MoreElements:
 116     case Unsupported:
 117       return true;
 118     default:
 119       return false;
 120     }
 121   }
 122
 123   /// More friendly way to set an action for common types that have an LLT
 124   /// representation.
 125   void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
 126     TablesInitialized = false;
 127     unsigned Opcode = Aspect.Opcode - FirstOp;
 128     if (Actions[Opcode].size() <= Aspect.Idx)
 129       Actions[Opcode].resize(Aspect.Idx + 1);
 130     Actions[Aspect.Opcode - FirstOp][Aspect.Idx][Aspect.Type] = Action;
 131   }
 132
 133   /// If an operation on a given vector type (say <M x iN>) isn't explicitly
 134   /// specified, we proceed in 2 stages. First we legalize the underlying scalar
 135   /// (so that there's at least one legal vector with that scalar), then we
 136   /// adjust the number of elements in the vector so that it is legal. The
 137   /// desired action in the first step is controlled by this function.
 138   void setScalarInVectorAction(unsigned Opcode, LLT ScalarTy,
 139                                LegalizeAction Action) {
 140     assert(!ScalarTy.isVector());
 141     ScalarInVectorActions[std::make_pair(Opcode, ScalarTy)] = Action;
 142   }
 143
 144   /// Determine what action should be taken to legalize the given generic
 145   /// instruction opcode, type-index and type. Requires computeTables to have
 146   /// been called.
 147   ///
 148   /// \returns a pair consisting of the kind of legalization that should be
 149   /// performed and the destination type.
 150   std::pair<LegalizeAction, LLT> getAction(const InstrAspect &Aspect) const;
 151
 152   /// Determine what action should be taken to legalize the given generic
 153   /// instruction.
 154   ///
 155   /// \returns a tuple consisting of the LegalizeAction that should be
 156   /// performed, the type-index it should be performed on and the destination
 157   /// type.
 158   std::tuple<LegalizeAction, unsigned, LLT>
 159   getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 160
 161   /// Iterate the given function (typically something like doubling the width)
 162   /// on Ty until we find a legal type for this operation.
 163   Optional<LLT> findLegalizableSize(const InstrAspect &Aspect,
 164                                     function_ref<LLT(LLT)> NextType) const {
 165     LegalizeAction Action;
 166     const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
 167     LLT Ty = Aspect.Type;
 168     do {
 169       Ty = NextType(Ty);
 170       auto ActionIt = Map.find(Ty);
 171       if (ActionIt == Map.end()) {
 172         auto DefaultIt = DefaultActions.find(Aspect.Opcode);
 173         if (DefaultIt == DefaultActions.end())
 174           return None;
 175         Action = DefaultIt->second;
 176       } else
 177         Action = ActionIt->second;
 178     } while (needsLegalizingToDifferentSize(Action));
 179     return Ty;
 180   }
 181
 182   /// Find what type it's actually OK to perform the given operation on, given
 183   /// the general approach we've decided to take.
 184   Optional<LLT> findLegalType(const InstrAspect &Aspect, LegalizeAction Action) const;
 185
 186   std::pair<LegalizeAction, LLT> findLegalAction(const InstrAspect &Aspect,
 187                                                  LegalizeAction Action) const {
 188     auto LegalType = findLegalType(Aspect, Action);
 189     if (!LegalType)
 190       return std::make_pair(LegalizeAction::Unsupported, LLT());
 191     return std::make_pair(Action, *LegalType);
 192   }
 193
 194   /// Find the specified \p Aspect in the primary (explicitly set) Actions
 195   /// table. Returns either the action the target requested or NotFound if there
 196   /// was no setAction call.
 197   LegalizeAction findInActions(const InstrAspect &Aspect) const {
 198     if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
 199       return NotFound;
 200     if (Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size())
 201       return NotFound;
 202     const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
 203     auto ActionIt =  Map.find(Aspect.Type);
 204     if (ActionIt == Map.end())
 205       return NotFound;
 206
 207     return ActionIt->second;
 208   }
 209
 210   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 211
 212   virtual bool legalizeCustom(MachineInstr &MI,
 213                               MachineRegisterInfo &MRI,
 214                               MachineIRBuilder &MIRBuilder) const;
 215
 216 private:
 217   static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
 218   static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
 219
 220   using TypeMap = DenseMap<LLT, LegalizeAction>;
 221   using SIVActionMap = DenseMap<std::pair<unsigned, LLT>, LegalizeAction>;
 222
 223   SmallVector<TypeMap, 1> Actions[LastOp - FirstOp + 1];
 224   SIVActionMap ScalarInVectorActions;
 225   DenseMap<std::pair<unsigned, LLT>, uint16_t> MaxLegalVectorElts;
 226   DenseMap<unsigned, LegalizeAction> DefaultActions;
 227
 228   bool TablesInitialized = false;
 229 };
 230
 231 } // end namespace llvm
 232
 233 #endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H