1 //===- FastISel.h - Definition of the FastISel class ------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file defines the FastISel class. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_FASTISEL_H 15 #define LLVM_CODEGEN_FASTISEL_H 16 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/StringRef.h" 20 #include "llvm/CodeGen/MachineBasicBlock.h" 21 #include "llvm/CodeGen/TargetLowering.h" 22 #include "llvm/IR/Attributes.h" 23 #include "llvm/IR/CallingConv.h" 24 #include "llvm/IR/DebugLoc.h" 25 #include "llvm/IR/DerivedTypes.h" 26 #include "llvm/IR/InstrTypes.h" 27 #include "llvm/Support/MachineValueType.h" 28 #include <cstdint> 29 #include <utility> 30 31 namespace llvm { 32 33 class AllocaInst; 34 class Instruction; 35 class IntrinsicInst; 36 class BasicBlock; 37 class CallInst; 38 class Constant; 39 class ConstantFP; 40 class DataLayout; 41 class FunctionLoweringInfo; 42 class LoadInst; 43 class MachineConstantPool; 44 class MachineFrameInfo; 45 class MachineFunction; 46 class MachineInstr; 47 class MachineMemOperand; 48 class MachineOperand; 49 class MachineRegisterInfo; 50 class MCContext; 51 class MCInstrDesc; 52 class MCSymbol; 53 class TargetInstrInfo; 54 class TargetLibraryInfo; 55 class TargetMachine; 56 class TargetRegisterClass; 57 class TargetRegisterInfo; 58 class Type; 59 class User; 60 class Value; 61 62 /// This is a fast-path instruction selection class that generates poor 63 /// code and doesn't support illegal types or non-trivial lowering, but runs 64 /// quickly. 65 class FastISel { 66 public: 67 using ArgListEntry = TargetLoweringBase::ArgListEntry; 68 using ArgListTy = TargetLoweringBase::ArgListTy; 69 struct CallLoweringInfo { 70 Type *RetTy = nullptr; 71 bool RetSExt : 1; 72 bool RetZExt : 1; 73 bool IsVarArg : 1; 74 bool IsInReg : 1; 75 bool DoesNotReturn : 1; 76 bool IsReturnValueUsed : 1; 77 bool IsPatchPoint : 1; 78 79 // IsTailCall Should be modified by implementations of FastLowerCall 80 // that perform tail call conversions. 81 bool IsTailCall = false; 82 83 unsigned NumFixedArgs = -1; 84 CallingConv::ID CallConv = CallingConv::C; 85 const Value *Callee = nullptr; 86 MCSymbol *Symbol = nullptr; 87 ArgListTy Args; 88 const CallBase *CB = nullptr; 89 MachineInstr *Call = nullptr; 90 Register ResultReg; 91 unsigned NumResultRegs = 0; 92 93 SmallVector<Value *, 16> OutVals; 94 SmallVector<ISD::ArgFlagsTy, 16> OutFlags; 95 SmallVector<Register, 16> OutRegs; 96 SmallVector<ISD::InputArg, 4> Ins; 97 SmallVector<Register, 4> InRegs; 98 99 CallLoweringInfo() 100 : RetSExt(false), RetZExt(false), IsVarArg(false), IsInReg(false), 101 DoesNotReturn(false), IsReturnValueUsed(true), IsPatchPoint(false) {} 102 103 CallLoweringInfo &setCallee(Type *ResultTy, FunctionType *FuncTy, 104 const Value *Target, ArgListTy &&ArgsList, 105 const CallBase &Call) { 106 RetTy = ResultTy; 107 Callee = Target; 108 109 IsInReg = Call.hasRetAttr(Attribute::InReg); 110 DoesNotReturn = Call.doesNotReturn(); 111 IsVarArg = FuncTy->isVarArg(); 112 IsReturnValueUsed = !Call.use_empty(); 113 RetSExt = Call.hasRetAttr(Attribute::SExt); 114 RetZExt = Call.hasRetAttr(Attribute::ZExt); 115 116 CallConv = Call.getCallingConv(); 117 Args = std::move(ArgsList); 118 NumFixedArgs = FuncTy->getNumParams(); 119 120 CB = &Call; 121 122 return *this; 123 } 124 125 CallLoweringInfo &setCallee(Type *ResultTy, FunctionType *FuncTy, 126 MCSymbol *Target, ArgListTy &&ArgsList, 127 const CallBase &Call, 128 unsigned FixedArgs = ~0U) { 129 RetTy = ResultTy; 130 Callee = Call.getCalledOperand(); 131 Symbol = Target; 132 133 IsInReg = Call.hasRetAttr(Attribute::InReg); 134 DoesNotReturn = Call.doesNotReturn(); 135 IsVarArg = FuncTy->isVarArg(); 136 IsReturnValueUsed = !Call.use_empty(); 137 RetSExt = Call.hasRetAttr(Attribute::SExt); 138 RetZExt = Call.hasRetAttr(Attribute::ZExt); 139 140 CallConv = Call.getCallingConv(); 141 Args = std::move(ArgsList); 142 NumFixedArgs = (FixedArgs == ~0U) ? FuncTy->getNumParams() : FixedArgs; 143 144 CB = &Call; 145 146 return *this; 147 } 148 149 CallLoweringInfo &setCallee(CallingConv::ID CC, Type *ResultTy, 150 const Value *Target, ArgListTy &&ArgsList, 151 unsigned FixedArgs = ~0U) { 152 RetTy = ResultTy; 153 Callee = Target; 154 CallConv = CC; 155 Args = std::move(ArgsList); 156 NumFixedArgs = (FixedArgs == ~0U) ? Args.size() : FixedArgs; 157 return *this; 158 } 159 160 CallLoweringInfo &setCallee(const DataLayout &DL, MCContext &Ctx, 161 CallingConv::ID CC, Type *ResultTy, 162 StringRef Target, ArgListTy &&ArgsList, 163 unsigned FixedArgs = ~0U); 164 165 CallLoweringInfo &setCallee(CallingConv::ID CC, Type *ResultTy, 166 MCSymbol *Target, ArgListTy &&ArgsList, 167 unsigned FixedArgs = ~0U) { 168 RetTy = ResultTy; 169 Symbol = Target; 170 CallConv = CC; 171 Args = std::move(ArgsList); 172 NumFixedArgs = (FixedArgs == ~0U) ? Args.size() : FixedArgs; 173 return *this; 174 } 175 176 CallLoweringInfo &setTailCall(bool Value = true) { 177 IsTailCall = Value; 178 return *this; 179 } 180 181 CallLoweringInfo &setIsPatchPoint(bool Value = true) { 182 IsPatchPoint = Value; 183 return *this; 184 } 185 186 ArgListTy &getArgs() { return Args; } 187 188 void clearOuts() { 189 OutVals.clear(); 190 OutFlags.clear(); 191 OutRegs.clear(); 192 } 193 194 void clearIns() { 195 Ins.clear(); 196 InRegs.clear(); 197 } 198 }; 199 200 protected: 201 DenseMap<const Value *, Register> LocalValueMap; 202 FunctionLoweringInfo &FuncInfo; 203 MachineFunction *MF; 204 MachineRegisterInfo &MRI; 205 MachineFrameInfo &MFI; 206 MachineConstantPool &MCP; 207 DebugLoc DbgLoc; 208 const TargetMachine &TM; 209 const DataLayout &DL; 210 const TargetInstrInfo &TII; 211 const TargetLowering &TLI; 212 const TargetRegisterInfo &TRI; 213 const TargetLibraryInfo *LibInfo; 214 bool SkipTargetIndependentISel; 215 bool UseInstrRefDebugInfo = false; 216 217 /// The position of the last instruction for materializing constants 218 /// for use in the current block. It resets to EmitStartPt when it makes sense 219 /// (for example, it's usually profitable to avoid function calls between the 220 /// definition and the use) 221 MachineInstr *LastLocalValue = nullptr; 222 223 /// The top most instruction in the current block that is allowed for 224 /// emitting local variables. LastLocalValue resets to EmitStartPt when it 225 /// makes sense (for example, on function calls) 226 MachineInstr *EmitStartPt = nullptr; 227 228 public: 229 virtual ~FastISel(); 230 231 /// Return the position of the last instruction emitted for 232 /// materializing constants for use in the current block. 233 MachineInstr *getLastLocalValue() { return LastLocalValue; } 234 235 /// Update the position of the last instruction emitted for 236 /// materializing constants for use in the current block. 237 void setLastLocalValue(MachineInstr *I) { 238 EmitStartPt = I; 239 LastLocalValue = I; 240 } 241 242 /// Set the current block to which generated machine instructions will 243 /// be appended. 244 void startNewBlock(); 245 246 /// Flush the local value map. 247 void finishBasicBlock(); 248 249 /// Return current debug location information. 250 DebugLoc getCurDebugLoc() const { return DbgLoc; } 251 252 /// Do "fast" instruction selection for function arguments and append 253 /// the machine instructions to the current block. Returns true when 254 /// successful. 255 bool lowerArguments(); 256 257 /// Do "fast" instruction selection for the given LLVM IR instruction 258 /// and append the generated machine instructions to the current block. 259 /// Returns true if selection was successful. 260 bool selectInstruction(const Instruction *I); 261 262 /// Do "fast" instruction selection for the given LLVM IR operator 263 /// (Instruction or ConstantExpr), and append generated machine instructions 264 /// to the current block. Return true if selection was successful. 265 bool selectOperator(const User *I, unsigned Opcode); 266 267 /// Create a virtual register and arrange for it to be assigned the 268 /// value for the given LLVM value. 269 Register getRegForValue(const Value *V); 270 271 /// Look up the value to see if its value is already cached in a 272 /// register. It may be defined by instructions across blocks or defined 273 /// locally. 274 Register lookUpRegForValue(const Value *V); 275 276 /// This is a wrapper around getRegForValue that also takes care of 277 /// truncating or sign-extending the given getelementptr index value. 278 Register getRegForGEPIndex(const Value *Idx); 279 280 /// We're checking to see if we can fold \p LI into \p FoldInst. Note 281 /// that we could have a sequence where multiple LLVM IR instructions are 282 /// folded into the same machineinstr. For example we could have: 283 /// 284 /// A: x = load i32 *P 285 /// B: y = icmp A, 42 286 /// C: br y, ... 287 /// 288 /// In this scenario, \p LI is "A", and \p FoldInst is "C". We know about "B" 289 /// (and any other folded instructions) because it is between A and C. 290 /// 291 /// If we succeed folding, return true. 292 bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst); 293 294 /// The specified machine instr operand is a vreg, and that vreg is 295 /// being provided by the specified load instruction. If possible, try to 296 /// fold the load as an operand to the instruction, returning true if 297 /// possible. 298 /// 299 /// This method should be implemented by targets. 300 virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/, 301 const LoadInst * /*LI*/) { 302 return false; 303 } 304 305 /// Reset InsertPt to prepare for inserting instructions into the 306 /// current block. 307 void recomputeInsertPt(); 308 309 /// Remove all dead instructions between the I and E. 310 void removeDeadCode(MachineBasicBlock::iterator I, 311 MachineBasicBlock::iterator E); 312 313 using SavePoint = MachineBasicBlock::iterator; 314 315 /// Prepare InsertPt to begin inserting instructions into the local 316 /// value area and return the old insert position. 317 SavePoint enterLocalValueArea(); 318 319 /// Reset InsertPt to the given old insert position. 320 void leaveLocalValueArea(SavePoint Old); 321 322 /// Signal whether instruction referencing variable locations are desired for 323 /// this function's debug-info. 324 void useInstrRefDebugInfo(bool Flag) { 325 UseInstrRefDebugInfo = Flag; 326 } 327 328 protected: 329 explicit FastISel(FunctionLoweringInfo &FuncInfo, 330 const TargetLibraryInfo *LibInfo, 331 bool SkipTargetIndependentISel = false); 332 333 /// This method is called by target-independent code when the normal 334 /// FastISel process fails to select an instruction. This gives targets a 335 /// chance to emit code for anything that doesn't fit into FastISel's 336 /// framework. It returns true if it was successful. 337 virtual bool fastSelectInstruction(const Instruction *I) = 0; 338 339 /// This method is called by target-independent code to do target- 340 /// specific argument lowering. It returns true if it was successful. 341 virtual bool fastLowerArguments(); 342 343 /// This method is called by target-independent code to do target- 344 /// specific call lowering. It returns true if it was successful. 345 virtual bool fastLowerCall(CallLoweringInfo &CLI); 346 347 /// This method is called by target-independent code to do target- 348 /// specific intrinsic lowering. It returns true if it was successful. 349 virtual bool fastLowerIntrinsicCall(const IntrinsicInst *II); 350 351 /// This method is called by target-independent code to request that an 352 /// instruction with the given type and opcode be emitted. 353 virtual unsigned fastEmit_(MVT VT, MVT RetVT, unsigned Opcode); 354 355 /// This method is called by target-independent code to request that an 356 /// instruction with the given type, opcode, and register operand be emitted. 357 virtual unsigned fastEmit_r(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0); 358 359 /// This method is called by target-independent code to request that an 360 /// instruction with the given type, opcode, and register operands be emitted. 361 virtual unsigned fastEmit_rr(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, 362 unsigned Op1); 363 364 /// This method is called by target-independent code to request that an 365 /// instruction with the given type, opcode, and register and immediate 366 /// operands be emitted. 367 virtual unsigned fastEmit_ri(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, 368 uint64_t Imm); 369 370 /// This method is a wrapper of fastEmit_ri. 371 /// 372 /// It first tries to emit an instruction with an immediate operand using 373 /// fastEmit_ri. If that fails, it materializes the immediate into a register 374 /// and try fastEmit_rr instead. 375 Register fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0, uint64_t Imm, 376 MVT ImmType); 377 378 /// This method is called by target-independent code to request that an 379 /// instruction with the given type, opcode, and immediate operand be emitted. 380 virtual unsigned fastEmit_i(MVT VT, MVT RetVT, unsigned Opcode, uint64_t Imm); 381 382 /// This method is called by target-independent code to request that an 383 /// instruction with the given type, opcode, and floating-point immediate 384 /// operand be emitted. 385 virtual unsigned fastEmit_f(MVT VT, MVT RetVT, unsigned Opcode, 386 const ConstantFP *FPImm); 387 388 /// Emit a MachineInstr with no operands and a result register in the 389 /// given register class. 390 Register fastEmitInst_(unsigned MachineInstOpcode, 391 const TargetRegisterClass *RC); 392 393 /// Emit a MachineInstr with one register operand and a result register 394 /// in the given register class. 395 Register fastEmitInst_r(unsigned MachineInstOpcode, 396 const TargetRegisterClass *RC, unsigned Op0); 397 398 /// Emit a MachineInstr with two register operands and a result 399 /// register in the given register class. 400 Register fastEmitInst_rr(unsigned MachineInstOpcode, 401 const TargetRegisterClass *RC, unsigned Op0, 402 unsigned Op1); 403 404 /// Emit a MachineInstr with three register operands and a result 405 /// register in the given register class. 406 Register fastEmitInst_rrr(unsigned MachineInstOpcode, 407 const TargetRegisterClass *RC, unsigned Op0, 408 unsigned Op1, unsigned Op2); 409 410 /// Emit a MachineInstr with a register operand, an immediate, and a 411 /// result register in the given register class. 412 Register fastEmitInst_ri(unsigned MachineInstOpcode, 413 const TargetRegisterClass *RC, unsigned Op0, 414 uint64_t Imm); 415 416 /// Emit a MachineInstr with one register operand and two immediate 417 /// operands. 418 Register fastEmitInst_rii(unsigned MachineInstOpcode, 419 const TargetRegisterClass *RC, unsigned Op0, 420 uint64_t Imm1, uint64_t Imm2); 421 422 /// Emit a MachineInstr with a floating point immediate, and a result 423 /// register in the given register class. 424 Register fastEmitInst_f(unsigned MachineInstOpcode, 425 const TargetRegisterClass *RC, 426 const ConstantFP *FPImm); 427 428 /// Emit a MachineInstr with two register operands, an immediate, and a 429 /// result register in the given register class. 430 Register fastEmitInst_rri(unsigned MachineInstOpcode, 431 const TargetRegisterClass *RC, unsigned Op0, 432 unsigned Op1, uint64_t Imm); 433 434 /// Emit a MachineInstr with a single immediate operand, and a result 435 /// register in the given register class. 436 Register fastEmitInst_i(unsigned MachineInstOpcode, 437 const TargetRegisterClass *RC, uint64_t Imm); 438 439 /// Emit a MachineInstr for an extract_subreg from a specified index of 440 /// a superregister to a specified type. 441 Register fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0, uint32_t Idx); 442 443 /// Emit MachineInstrs to compute the value of Op with all but the 444 /// least significant bit set to zero. 445 Register fastEmitZExtFromI1(MVT VT, unsigned Op0); 446 447 /// Emit an unconditional branch to the given block, unless it is the 448 /// immediate (fall-through) successor, and update the CFG. 449 void fastEmitBranch(MachineBasicBlock *MSucc, const DebugLoc &DbgLoc); 450 451 /// Emit an unconditional branch to \p FalseMBB, obtains the branch weight 452 /// and adds TrueMBB and FalseMBB to the successor list. 453 void finishCondBranch(const BasicBlock *BranchBB, MachineBasicBlock *TrueMBB, 454 MachineBasicBlock *FalseMBB); 455 456 /// Update the value map to include the new mapping for this 457 /// instruction, or insert an extra copy to get the result in a previous 458 /// determined register. 459 /// 460 /// NOTE: This is only necessary because we might select a block that uses a 461 /// value before we select the block that defines the value. It might be 462 /// possible to fix this by selecting blocks in reverse postorder. 463 void updateValueMap(const Value *I, Register Reg, unsigned NumRegs = 1); 464 465 Register createResultReg(const TargetRegisterClass *RC); 466 467 /// Try to constrain Op so that it is usable by argument OpNum of the 468 /// provided MCInstrDesc. If this fails, create a new virtual register in the 469 /// correct class and COPY the value there. 470 Register constrainOperandRegClass(const MCInstrDesc &II, Register Op, 471 unsigned OpNum); 472 473 /// Emit a constant in a register using target-specific logic, such as 474 /// constant pool loads. 475 virtual unsigned fastMaterializeConstant(const Constant *C) { return 0; } 476 477 /// Emit an alloca address in a register using target-specific logic. 478 virtual unsigned fastMaterializeAlloca(const AllocaInst *C) { return 0; } 479 480 /// Emit the floating-point constant +0.0 in a register using target- 481 /// specific logic. 482 virtual unsigned fastMaterializeFloatZero(const ConstantFP *CF) { 483 return 0; 484 } 485 486 /// Check if \c Add is an add that can be safely folded into \c GEP. 487 /// 488 /// \c Add can be folded into \c GEP if: 489 /// - \c Add is an add, 490 /// - \c Add's size matches \c GEP's, 491 /// - \c Add is in the same basic block as \c GEP, and 492 /// - \c Add has a constant operand. 493 bool canFoldAddIntoGEP(const User *GEP, const Value *Add); 494 495 /// Create a machine mem operand from the given instruction. 496 MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const; 497 498 CmpInst::Predicate optimizeCmpPredicate(const CmpInst *CI) const; 499 500 bool lowerCallTo(const CallInst *CI, MCSymbol *Symbol, unsigned NumArgs); 501 bool lowerCallTo(const CallInst *CI, const char *SymName, 502 unsigned NumArgs); 503 bool lowerCallTo(CallLoweringInfo &CLI); 504 505 bool lowerCall(const CallInst *I); 506 /// Select and emit code for a binary operator instruction, which has 507 /// an opcode which directly corresponds to the given ISD opcode. 508 bool selectBinaryOp(const User *I, unsigned ISDOpcode); 509 bool selectFNeg(const User *I, const Value *In); 510 bool selectGetElementPtr(const User *I); 511 bool selectStackmap(const CallInst *I); 512 bool selectPatchpoint(const CallInst *I); 513 bool selectCall(const User *I); 514 bool selectIntrinsicCall(const IntrinsicInst *II); 515 bool selectBitCast(const User *I); 516 bool selectFreeze(const User *I); 517 bool selectCast(const User *I, unsigned Opcode); 518 bool selectExtractValue(const User *U); 519 bool selectXRayCustomEvent(const CallInst *II); 520 bool selectXRayTypedEvent(const CallInst *II); 521 522 bool shouldOptForSize(const MachineFunction *MF) const { 523 // TODO: Implement PGSO. 524 return MF->getFunction().hasOptSize(); 525 } 526 527 private: 528 /// Handle PHI nodes in successor blocks. 529 /// 530 /// Emit code to ensure constants are copied into registers when needed. 531 /// Remember the virtual registers that need to be added to the Machine PHI 532 /// nodes as input. We cannot just directly add them, because expansion might 533 /// result in multiple MBB's for one BB. As such, the start of the BB might 534 /// correspond to a different MBB than the end. 535 bool handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 536 537 /// Helper for materializeRegForValue to materialize a constant in a 538 /// target-independent way. 539 Register materializeConstant(const Value *V, MVT VT); 540 541 /// Helper for getRegForVale. This function is called when the value 542 /// isn't already available in a register and must be materialized with new 543 /// instructions. 544 Register materializeRegForValue(const Value *V, MVT VT); 545 546 /// Clears LocalValueMap and moves the area for the new local variables 547 /// to the beginning of the block. It helps to avoid spilling cached variables 548 /// across heavy instructions like calls. 549 void flushLocalValueMap(); 550 551 /// Removes dead local value instructions after SavedLastLocalvalue. 552 void removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue); 553 554 /// Insertion point before trying to select the current instruction. 555 MachineBasicBlock::iterator SavedInsertPt; 556 557 /// Add a stackmap or patchpoint intrinsic call's live variable 558 /// operands to a stackmap or patchpoint machine instruction. 559 bool addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops, 560 const CallInst *CI, unsigned StartIdx); 561 bool lowerCallOperands(const CallInst *CI, unsigned ArgIdx, unsigned NumArgs, 562 const Value *Callee, bool ForceRetVoidTy, 563 CallLoweringInfo &CLI); 564 }; 565 566 } // end namespace llvm 567 568 #endif // LLVM_CODEGEN_FASTISEL_H 569