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