1 //===- llvm/CodeGen/GlobalISel/InstructionSelector.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 /// \file This file declares the API for the instruction selector. 11 /// This class is responsible for selecting machine instructions. 12 /// It's implemented by the target. It's used by the InstructionSelect pass. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H 17 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H 18 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/Optional.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/Support/CodeGenCoverage.h" 23 #include "llvm/Support/LowLevelTypeImpl.h" 24 #include <bitset> 25 #include <cstddef> 26 #include <cstdint> 27 #include <functional> 28 #include <initializer_list> 29 #include <vector> 30 31 namespace llvm { 32 33 class APInt; 34 class APFloat; 35 class MachineInstr; 36 class MachineInstrBuilder; 37 class MachineFunction; 38 class MachineOperand; 39 class MachineRegisterInfo; 40 class RegisterBankInfo; 41 class TargetInstrInfo; 42 class TargetRegisterClass; 43 class TargetRegisterInfo; 44 45 /// Container class for CodeGen predicate results. 46 /// This is convenient because std::bitset does not have a constructor 47 /// with an initializer list of set bits. 48 /// 49 /// Each InstructionSelector subclass should define a PredicateBitset class 50 /// with: 51 /// const unsigned MAX_SUBTARGET_PREDICATES = 192; 52 /// using PredicateBitset = PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>; 53 /// and updating the constant to suit the target. Tablegen provides a suitable 54 /// definition for the predicates in use in <Target>GenGlobalISel.inc when 55 /// GET_GLOBALISEL_PREDICATE_BITSET is defined. 56 template <std::size_t MaxPredicates> 57 class PredicateBitsetImpl : public std::bitset<MaxPredicates> { 58 public: 59 // Cannot inherit constructors because it's not supported by VC++.. 60 PredicateBitsetImpl() = default; 61 PredicateBitsetImpl(const std::bitset<MaxPredicates> & B)62 PredicateBitsetImpl(const std::bitset<MaxPredicates> &B) 63 : std::bitset<MaxPredicates>(B) {} 64 PredicateBitsetImpl(std::initializer_list<unsigned> Init)65 PredicateBitsetImpl(std::initializer_list<unsigned> Init) { 66 for (auto I : Init) 67 std::bitset<MaxPredicates>::set(I); 68 } 69 }; 70 71 enum { 72 /// Begin a try-block to attempt a match and jump to OnFail if it is 73 /// unsuccessful. 74 /// - OnFail - The MatchTable entry at which to resume if the match fails. 75 /// 76 /// FIXME: This ought to take an argument indicating the number of try-blocks 77 /// to exit on failure. It's usually one but the last match attempt of 78 /// a block will need more. The (implemented) alternative is to tack a 79 /// GIM_Reject on the end of each try-block which is simpler but 80 /// requires an extra opcode and iteration in the interpreter on each 81 /// failed match. 82 GIM_Try, 83 84 /// Switch over the opcode on the specified instruction 85 /// - InsnID - Instruction ID 86 /// - LowerBound - numerically minimum opcode supported 87 /// - UpperBound - numerically maximum + 1 opcode supported 88 /// - Default - failure jump target 89 /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets 90 GIM_SwitchOpcode, 91 92 /// Switch over the LLT on the specified instruction operand 93 /// - InsnID - Instruction ID 94 /// - OpIdx - Operand index 95 /// - LowerBound - numerically minimum Type ID supported 96 /// - UpperBound - numerically maximum + 1 Type ID supported 97 /// - Default - failure jump target 98 /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets 99 GIM_SwitchType, 100 101 /// Record the specified instruction 102 /// - NewInsnID - Instruction ID to define 103 /// - InsnID - Instruction ID 104 /// - OpIdx - Operand index 105 GIM_RecordInsn, 106 107 /// Check the feature bits 108 /// - Expected features 109 GIM_CheckFeatures, 110 111 /// Check the opcode on the specified instruction 112 /// - InsnID - Instruction ID 113 /// - Expected opcode 114 GIM_CheckOpcode, 115 /// Check the instruction has the right number of operands 116 /// - InsnID - Instruction ID 117 /// - Expected number of operands 118 GIM_CheckNumOperands, 119 /// Check an immediate predicate on the specified instruction 120 /// - InsnID - Instruction ID 121 /// - The predicate to test 122 GIM_CheckI64ImmPredicate, 123 /// Check an immediate predicate on the specified instruction via an APInt. 124 /// - InsnID - Instruction ID 125 /// - The predicate to test 126 GIM_CheckAPIntImmPredicate, 127 /// Check a floating point immediate predicate on the specified instruction. 128 /// - InsnID - Instruction ID 129 /// - The predicate to test 130 GIM_CheckAPFloatImmPredicate, 131 /// Check a memory operation has the specified atomic ordering. 132 /// - InsnID - Instruction ID 133 /// - Ordering - The AtomicOrdering value 134 GIM_CheckAtomicOrdering, 135 GIM_CheckAtomicOrderingOrStrongerThan, 136 GIM_CheckAtomicOrderingWeakerThan, 137 /// Check the size of the memory access for the given machine memory operand. 138 /// - InsnID - Instruction ID 139 /// - MMOIdx - MMO index 140 /// - Size - The size in bytes of the memory access 141 GIM_CheckMemorySizeEqualTo, 142 /// Check the size of the memory access for the given machine memory operand 143 /// against the size of an operand. 144 /// - InsnID - Instruction ID 145 /// - MMOIdx - MMO index 146 /// - OpIdx - The operand index to compare the MMO against 147 GIM_CheckMemorySizeEqualToLLT, 148 GIM_CheckMemorySizeLessThanLLT, 149 GIM_CheckMemorySizeGreaterThanLLT, 150 /// Check a generic C++ instruction predicate 151 /// - InsnID - Instruction ID 152 /// - PredicateID - The ID of the predicate function to call 153 GIM_CheckCxxInsnPredicate, 154 155 /// Check the type for the specified operand 156 /// - InsnID - Instruction ID 157 /// - OpIdx - Operand index 158 /// - Expected type 159 GIM_CheckType, 160 /// Check the type of a pointer to any address space. 161 /// - InsnID - Instruction ID 162 /// - OpIdx - Operand index 163 /// - SizeInBits - The size of the pointer value in bits. 164 GIM_CheckPointerToAny, 165 /// Check the register bank for the specified operand 166 /// - InsnID - Instruction ID 167 /// - OpIdx - Operand index 168 /// - Expected register bank (specified as a register class) 169 GIM_CheckRegBankForClass, 170 171 /// Check the operand matches a complex predicate 172 /// - InsnID - Instruction ID 173 /// - OpIdx - Operand index 174 /// - RendererID - The renderer to hold the result 175 /// - Complex predicate ID 176 GIM_CheckComplexPattern, 177 178 /// Check the operand is a specific integer 179 /// - InsnID - Instruction ID 180 /// - OpIdx - Operand index 181 /// - Expected integer 182 GIM_CheckConstantInt, 183 /// Check the operand is a specific literal integer (i.e. MO.isImm() or 184 /// MO.isCImm() is true). 185 /// - InsnID - Instruction ID 186 /// - OpIdx - Operand index 187 /// - Expected integer 188 GIM_CheckLiteralInt, 189 /// Check the operand is a specific intrinsic ID 190 /// - InsnID - Instruction ID 191 /// - OpIdx - Operand index 192 /// - Expected Intrinsic ID 193 GIM_CheckIntrinsicID, 194 195 /// Check the specified operand is an MBB 196 /// - InsnID - Instruction ID 197 /// - OpIdx - Operand index 198 GIM_CheckIsMBB, 199 200 /// Check if the specified operand is safe to fold into the current 201 /// instruction. 202 /// - InsnID - Instruction ID 203 GIM_CheckIsSafeToFold, 204 205 /// Check the specified operands are identical. 206 /// - InsnID - Instruction ID 207 /// - OpIdx - Operand index 208 /// - OtherInsnID - Other instruction ID 209 /// - OtherOpIdx - Other operand index 210 GIM_CheckIsSameOperand, 211 212 /// Fail the current try-block, or completely fail to match if there is no 213 /// current try-block. 214 GIM_Reject, 215 216 //=== Renderers === 217 218 /// Mutate an instruction 219 /// - NewInsnID - Instruction ID to define 220 /// - OldInsnID - Instruction ID to mutate 221 /// - NewOpcode - The new opcode to use 222 GIR_MutateOpcode, 223 224 /// Build a new instruction 225 /// - InsnID - Instruction ID to define 226 /// - Opcode - The new opcode to use 227 GIR_BuildMI, 228 229 /// Copy an operand to the specified instruction 230 /// - NewInsnID - Instruction ID to modify 231 /// - OldInsnID - Instruction ID to copy from 232 /// - OpIdx - The operand to copy 233 GIR_Copy, 234 235 /// Copy an operand to the specified instruction or add a zero register if the 236 /// operand is a zero immediate. 237 /// - NewInsnID - Instruction ID to modify 238 /// - OldInsnID - Instruction ID to copy from 239 /// - OpIdx - The operand to copy 240 /// - ZeroReg - The zero register to use 241 GIR_CopyOrAddZeroReg, 242 /// Copy an operand to the specified instruction 243 /// - NewInsnID - Instruction ID to modify 244 /// - OldInsnID - Instruction ID to copy from 245 /// - OpIdx - The operand to copy 246 /// - SubRegIdx - The subregister to copy 247 GIR_CopySubReg, 248 249 /// Add an implicit register def to the specified instruction 250 /// - InsnID - Instruction ID to modify 251 /// - RegNum - The register to add 252 GIR_AddImplicitDef, 253 /// Add an implicit register use to the specified instruction 254 /// - InsnID - Instruction ID to modify 255 /// - RegNum - The register to add 256 GIR_AddImplicitUse, 257 /// Add an register to the specified instruction 258 /// - InsnID - Instruction ID to modify 259 /// - RegNum - The register to add 260 GIR_AddRegister, 261 262 /// Add a temporary register to the specified instruction 263 /// - InsnID - Instruction ID to modify 264 /// - TempRegID - The temporary register ID to add 265 /// - TempRegFlags - The register flags to set 266 GIR_AddTempRegister, 267 268 /// Add an immediate to the specified instruction 269 /// - InsnID - Instruction ID to modify 270 /// - Imm - The immediate to add 271 GIR_AddImm, 272 /// Render complex operands to the specified instruction 273 /// - InsnID - Instruction ID to modify 274 /// - RendererID - The renderer to call 275 GIR_ComplexRenderer, 276 277 /// Render sub-operands of complex operands to the specified instruction 278 /// - InsnID - Instruction ID to modify 279 /// - RendererID - The renderer to call 280 /// - RenderOpID - The suboperand to render. 281 GIR_ComplexSubOperandRenderer, 282 /// Render operands to the specified instruction using a custom function 283 /// - InsnID - Instruction ID to modify 284 /// - OldInsnID - Instruction ID to get the matched operand from 285 /// - RendererFnID - Custom renderer function to call 286 GIR_CustomRenderer, 287 288 /// Render a G_CONSTANT operator as a sign-extended immediate. 289 /// - NewInsnID - Instruction ID to modify 290 /// - OldInsnID - Instruction ID to copy from 291 /// The operand index is implicitly 1. 292 GIR_CopyConstantAsSImm, 293 294 /// Render a G_FCONSTANT operator as a sign-extended immediate. 295 /// - NewInsnID - Instruction ID to modify 296 /// - OldInsnID - Instruction ID to copy from 297 /// The operand index is implicitly 1. 298 GIR_CopyFConstantAsFPImm, 299 300 /// Constrain an instruction operand to a register class. 301 /// - InsnID - Instruction ID to modify 302 /// - OpIdx - Operand index 303 /// - RCEnum - Register class enumeration value 304 GIR_ConstrainOperandRC, 305 306 /// Constrain an instructions operands according to the instruction 307 /// description. 308 /// - InsnID - Instruction ID to modify 309 GIR_ConstrainSelectedInstOperands, 310 311 /// Merge all memory operands into instruction. 312 /// - InsnID - Instruction ID to modify 313 /// - MergeInsnID... - One or more Instruction ID to merge into the result. 314 /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to 315 /// merge. 316 GIR_MergeMemOperands, 317 318 /// Erase from parent. 319 /// - InsnID - Instruction ID to erase 320 GIR_EraseFromParent, 321 322 /// Create a new temporary register that's not constrained. 323 /// - TempRegID - The temporary register ID to initialize. 324 /// - Expected type 325 GIR_MakeTempReg, 326 327 /// A successful emission 328 GIR_Done, 329 330 /// Increment the rule coverage counter. 331 /// - RuleID - The ID of the rule that was covered. 332 GIR_Coverage, 333 334 /// Keeping track of the number of the GI opcodes. Must be the last entry. 335 GIU_NumOpcodes, 336 }; 337 338 enum { 339 /// Indicates the end of the variable-length MergeInsnID list in a 340 /// GIR_MergeMemOperands opcode. 341 GIU_MergeMemOperands_EndOfList = -1, 342 }; 343 344 /// Provides the logic to select generic machine instructions. 345 class InstructionSelector { 346 public: 347 virtual ~InstructionSelector() = default; 348 349 /// Select the (possibly generic) instruction \p I to only use target-specific 350 /// opcodes. It is OK to insert multiple instructions, but they cannot be 351 /// generic pre-isel instructions. 352 /// 353 /// \returns whether selection succeeded. 354 /// \pre I.getParent() && I.getParent()->getParent() 355 /// \post 356 /// if returns true: 357 /// for I in all mutated/inserted instructions: 358 /// !isPreISelGenericOpcode(I.getOpcode()) 359 virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0; 360 361 protected: 362 using ComplexRendererFns = 363 Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>; 364 using RecordedMIVector = SmallVector<MachineInstr *, 4>; 365 using NewMIVector = SmallVector<MachineInstrBuilder, 4>; 366 367 struct MatcherState { 368 std::vector<ComplexRendererFns::value_type> Renderers; 369 RecordedMIVector MIs; 370 DenseMap<unsigned, unsigned> TempRegisters; 371 372 MatcherState(unsigned MaxRenderers); 373 }; 374 375 public: 376 template <class PredicateBitset, class ComplexMatcherMemFn, 377 class CustomRendererFn> 378 struct ISelInfoTy { ISelInfoTyISelInfoTy379 ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects, 380 const PredicateBitset *FeatureBitsets, 381 const ComplexMatcherMemFn *ComplexPredicates, 382 const CustomRendererFn *CustomRenderers) 383 : TypeObjects(TypeObjects), 384 FeatureBitsets(FeatureBitsets), 385 ComplexPredicates(ComplexPredicates), 386 CustomRenderers(CustomRenderers) { 387 388 for (size_t I = 0; I < NumTypeObjects; ++I) 389 TypeIDMap[TypeObjects[I]] = I; 390 } 391 const LLT *TypeObjects; 392 const PredicateBitset *FeatureBitsets; 393 const ComplexMatcherMemFn *ComplexPredicates; 394 const CustomRendererFn *CustomRenderers; 395 396 SmallDenseMap<LLT, unsigned, 64> TypeIDMap; 397 }; 398 399 protected: 400 InstructionSelector(); 401 402 /// Execute a given matcher table and return true if the match was successful 403 /// and false otherwise. 404 template <class TgtInstructionSelector, class PredicateBitset, 405 class ComplexMatcherMemFn, class CustomRendererFn> 406 bool executeMatchTable( 407 TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State, 408 const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn> 409 &ISelInfo, 410 const int64_t *MatchTable, const TargetInstrInfo &TII, 411 MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, 412 const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures, 413 CodeGenCoverage &CoverageInfo) const; 414 getMatchTable()415 virtual const int64_t *getMatchTable() const { 416 llvm_unreachable("Should have been overridden by tablegen if used"); 417 } 418 testImmPredicate_I64(unsigned,int64_t)419 virtual bool testImmPredicate_I64(unsigned, int64_t) const { 420 llvm_unreachable( 421 "Subclasses must override this with a tablegen-erated function"); 422 } testImmPredicate_APInt(unsigned,const APInt &)423 virtual bool testImmPredicate_APInt(unsigned, const APInt &) const { 424 llvm_unreachable( 425 "Subclasses must override this with a tablegen-erated function"); 426 } testImmPredicate_APFloat(unsigned,const APFloat &)427 virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const { 428 llvm_unreachable( 429 "Subclasses must override this with a tablegen-erated function"); 430 } testMIPredicate_MI(unsigned,const MachineInstr &)431 virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const { 432 llvm_unreachable( 433 "Subclasses must override this with a tablegen-erated function"); 434 } 435 436 /// Constrain a register operand of an instruction \p I to a specified 437 /// register class. This could involve inserting COPYs before (for uses) or 438 /// after (for defs) and may replace the operand of \p I. 439 /// \returns whether operand regclass constraining succeeded. 440 bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx, 441 const TargetRegisterClass &RC, 442 const TargetInstrInfo &TII, 443 const TargetRegisterInfo &TRI, 444 const RegisterBankInfo &RBI) const; 445 446 bool isOperandImmEqual(const MachineOperand &MO, int64_t Value, 447 const MachineRegisterInfo &MRI) const; 448 449 /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the 450 /// right-hand side. GlobalISel's separation of pointer and integer types 451 /// means that we don't need to worry about G_OR with equivalent semantics. 452 bool isBaseWithConstantOffset(const MachineOperand &Root, 453 const MachineRegisterInfo &MRI) const; 454 455 /// Return true if MI can obviously be folded into IntoMI. 456 /// MI and IntoMI do not need to be in the same basic blocks, but MI must 457 /// preceed IntoMI. 458 bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const; 459 }; 460 461 } // end namespace llvm 462 463 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H 464