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 if (Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size()) 166 return None; 167 168 LegalizeAction Action; 169 const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx]; 170 LLT Ty = Aspect.Type; 171 do { 172 Ty = NextType(Ty); 173 auto ActionIt = Map.find(Ty); 174 if (ActionIt == Map.end()) { 175 auto DefaultIt = DefaultActions.find(Aspect.Opcode); 176 if (DefaultIt == DefaultActions.end()) 177 return None; 178 Action = DefaultIt->second; 179 } else 180 Action = ActionIt->second; 181 } while (needsLegalizingToDifferentSize(Action)); 182 return Ty; 183 } 184 185 /// Find what type it's actually OK to perform the given operation on, given 186 /// the general approach we've decided to take. 187 Optional<LLT> findLegalType(const InstrAspect &Aspect, LegalizeAction Action) const; 188 189 std::pair<LegalizeAction, LLT> findLegalAction(const InstrAspect &Aspect, 190 LegalizeAction Action) const { 191 auto LegalType = findLegalType(Aspect, Action); 192 if (!LegalType) 193 return std::make_pair(LegalizeAction::Unsupported, LLT()); 194 return std::make_pair(Action, *LegalType); 195 } 196 197 /// Find the specified \p Aspect in the primary (explicitly set) Actions 198 /// table. Returns either the action the target requested or NotFound if there 199 /// was no setAction call. 200 LegalizeAction findInActions(const InstrAspect &Aspect) const { 201 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp) 202 return NotFound; 203 if (Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size()) 204 return NotFound; 205 const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx]; 206 auto ActionIt = Map.find(Aspect.Type); 207 if (ActionIt == Map.end()) 208 return NotFound; 209 210 return ActionIt->second; 211 } 212 213 bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const; 214 215 virtual bool legalizeCustom(MachineInstr &MI, 216 MachineRegisterInfo &MRI, 217 MachineIRBuilder &MIRBuilder) const; 218 219 private: 220 static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START; 221 static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END; 222 223 using TypeMap = DenseMap<LLT, LegalizeAction>; 224 using SIVActionMap = DenseMap<std::pair<unsigned, LLT>, LegalizeAction>; 225 226 SmallVector<TypeMap, 1> Actions[LastOp - FirstOp + 1]; 227 SIVActionMap ScalarInVectorActions; 228 DenseMap<std::pair<unsigned, LLT>, uint16_t> MaxLegalVectorElts; 229 DenseMap<unsigned, LegalizeAction> DefaultActions; 230 231 bool TablesInitialized = false; 232 }; 233 234 } // end namespace llvm 235 236 #endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H 237
