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/IR/IntrinsicInst.h" 28 #include "llvm/Support/MachineValueType.h" 29 #include <algorithm> 30 #include <cstdint> 31 #include <utility> 32 33 namespace llvm { 34 35 class AllocaInst; 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 CallLoweringInfoCallLoweringInfo99 CallLoweringInfo() 100 : RetSExt(false), RetZExt(false), IsVarArg(false), IsInReg(false), 101 DoesNotReturn(false), IsReturnValueUsed(true), IsPatchPoint(false) {} 102 setCalleeCallLoweringInfo103 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 getArgsCallLoweringInfo186 ArgListTy &getArgs() { return Args; } 187 clearOutsCallLoweringInfo188 void clearOuts() { 189 OutVals.clear(); 190 OutFlags.clear(); 191 OutRegs.clear(); 192 } 193 clearInsCallLoweringInfo194 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 216 /// The position of the last instruction for materializing constants 217 /// for use in the current block. It resets to EmitStartPt when it makes sense 218 /// (for example, it's usually profitable to avoid function calls between the 219 /// definition and the use) 220 MachineInstr *LastLocalValue; 221 222 /// The top most instruction in the current block that is allowed for 223 /// emitting local variables. LastLocalValue resets to EmitStartPt when it 224 /// makes sense (for example, on function calls) 225 MachineInstr *EmitStartPt; 226 227 public: 228 virtual ~FastISel(); 229 230 /// Return the position of the last instruction emitted for 231 /// materializing constants for use in the current block. getLastLocalValue()232 MachineInstr *getLastLocalValue() { return LastLocalValue; } 233 234 /// Update the position of the last instruction emitted for 235 /// materializing constants for use in the current block. setLastLocalValue(MachineInstr * I)236 void setLastLocalValue(MachineInstr *I) { 237 EmitStartPt = I; 238 LastLocalValue = I; 239 } 240 241 /// Set the current block to which generated machine instructions will 242 /// be appended. 243 void startNewBlock(); 244 245 /// Flush the local value map. 246 void finishBasicBlock(); 247 248 /// Return current debug location information. getCurDebugLoc()249 DebugLoc getCurDebugLoc() const { return DbgLoc; } 250 251 /// Do "fast" instruction selection for function arguments and append 252 /// the machine instructions to the current block. Returns true when 253 /// successful. 254 bool lowerArguments(); 255 256 /// Do "fast" instruction selection for the given LLVM IR instruction 257 /// and append the generated machine instructions to the current block. 258 /// Returns true if selection was successful. 259 bool selectInstruction(const Instruction *I); 260 261 /// Do "fast" instruction selection for the given LLVM IR operator 262 /// (Instruction or ConstantExpr), and append generated machine instructions 263 /// to the current block. Return true if selection was successful. 264 bool selectOperator(const User *I, unsigned Opcode); 265 266 /// Create a virtual register and arrange for it to be assigned the 267 /// value for the given LLVM value. 268 Register getRegForValue(const Value *V); 269 270 /// Look up the value to see if its value is already cached in a 271 /// register. It may be defined by instructions across blocks or defined 272 /// locally. 273 Register lookUpRegForValue(const Value *V); 274 275 /// This is a wrapper around getRegForValue that also takes care of 276 /// truncating or sign-extending the given getelementptr index value. 277 Register getRegForGEPIndex(const Value *Idx); 278 279 /// We're checking to see if we can fold \p LI into \p FoldInst. Note 280 /// that we could have a sequence where multiple LLVM IR instructions are 281 /// folded into the same machineinstr. For example we could have: 282 /// 283 /// A: x = load i32 *P 284 /// B: y = icmp A, 42 285 /// C: br y, ... 286 /// 287 /// In this scenario, \p LI is "A", and \p FoldInst is "C". We know about "B" 288 /// (and any other folded instructions) because it is between A and C. 289 /// 290 /// If we succeed folding, return true. 291 bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst); 292 293 /// The specified machine instr operand is a vreg, and that vreg is 294 /// being provided by the specified load instruction. If possible, try to 295 /// fold the load as an operand to the instruction, returning true if 296 /// possible. 297 /// 298 /// This method should be implemented by targets. tryToFoldLoadIntoMI(MachineInstr *,unsigned,const LoadInst *)299 virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/, 300 const LoadInst * /*LI*/) { 301 return false; 302 } 303 304 /// Reset InsertPt to prepare for inserting instructions into the 305 /// current block. 306 void recomputeInsertPt(); 307 308 /// Remove all dead instructions between the I and E. 309 void removeDeadCode(MachineBasicBlock::iterator I, 310 MachineBasicBlock::iterator E); 311 312 using SavePoint = MachineBasicBlock::iterator; 313 314 /// Prepare InsertPt to begin inserting instructions into the local 315 /// value area and return the old insert position. 316 SavePoint enterLocalValueArea(); 317 318 /// Reset InsertPt to the given old insert position. 319 void leaveLocalValueArea(SavePoint Old); 320 321 protected: 322 explicit FastISel(FunctionLoweringInfo &FuncInfo, 323 const TargetLibraryInfo *LibInfo, 324 bool SkipTargetIndependentISel = false); 325 326 /// This method is called by target-independent code when the normal 327 /// FastISel process fails to select an instruction. This gives targets a 328 /// chance to emit code for anything that doesn't fit into FastISel's 329 /// framework. It returns true if it was successful. 330 virtual bool fastSelectInstruction(const Instruction *I) = 0; 331 332 /// This method is called by target-independent code to do target- 333 /// specific argument lowering. It returns true if it was successful. 334 virtual bool fastLowerArguments(); 335 336 /// This method is called by target-independent code to do target- 337 /// specific call lowering. It returns true if it was successful. 338 virtual bool fastLowerCall(CallLoweringInfo &CLI); 339 340 /// This method is called by target-independent code to do target- 341 /// specific intrinsic lowering. It returns true if it was successful. 342 virtual bool fastLowerIntrinsicCall(const IntrinsicInst *II); 343 344 /// This method is called by target-independent code to request that an 345 /// instruction with the given type and opcode be emitted. 346 virtual unsigned fastEmit_(MVT VT, MVT RetVT, unsigned Opcode); 347 348 /// This method is called by target-independent code to request that an 349 /// instruction with the given type, opcode, and register operand be emitted. 350 virtual unsigned fastEmit_r(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0); 351 352 /// This method is called by target-independent code to request that an 353 /// instruction with the given type, opcode, and register operands be emitted. 354 virtual unsigned fastEmit_rr(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, 355 unsigned Op1); 356 357 /// This method is called by target-independent code to request that an 358 /// instruction with the given type, opcode, and register and immediate 359 /// operands be emitted. 360 virtual unsigned fastEmit_ri(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, 361 uint64_t Imm); 362 363 /// This method is a wrapper of fastEmit_ri. 364 /// 365 /// It first tries to emit an instruction with an immediate operand using 366 /// fastEmit_ri. If that fails, it materializes the immediate into a register 367 /// and try fastEmit_rr instead. 368 Register fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0, uint64_t Imm, 369 MVT ImmType); 370 371 /// This method is called by target-independent code to request that an 372 /// instruction with the given type, opcode, and immediate operand be emitted. 373 virtual unsigned fastEmit_i(MVT VT, MVT RetVT, unsigned Opcode, uint64_t Imm); 374 375 /// This method is called by target-independent code to request that an 376 /// instruction with the given type, opcode, and floating-point immediate 377 /// operand be emitted. 378 virtual unsigned fastEmit_f(MVT VT, MVT RetVT, unsigned Opcode, 379 const ConstantFP *FPImm); 380 381 /// Emit a MachineInstr with no operands and a result register in the 382 /// given register class. 383 Register fastEmitInst_(unsigned MachineInstOpcode, 384 const TargetRegisterClass *RC); 385 386 /// Emit a MachineInstr with one register operand and a result register 387 /// in the given register class. 388 Register fastEmitInst_r(unsigned MachineInstOpcode, 389 const TargetRegisterClass *RC, unsigned Op0); 390 391 /// Emit a MachineInstr with two register operands and a result 392 /// register in the given register class. 393 Register fastEmitInst_rr(unsigned MachineInstOpcode, 394 const TargetRegisterClass *RC, unsigned Op0, 395 unsigned Op1); 396 397 /// Emit a MachineInstr with three register operands and a result 398 /// register in the given register class. 399 Register fastEmitInst_rrr(unsigned MachineInstOpcode, 400 const TargetRegisterClass *RC, unsigned Op0, 401 unsigned Op1, unsigned Op2); 402 403 /// Emit a MachineInstr with a register operand, an immediate, and a 404 /// result register in the given register class. 405 Register fastEmitInst_ri(unsigned MachineInstOpcode, 406 const TargetRegisterClass *RC, unsigned Op0, 407 uint64_t Imm); 408 409 /// Emit a MachineInstr with one register operand and two immediate 410 /// operands. 411 Register fastEmitInst_rii(unsigned MachineInstOpcode, 412 const TargetRegisterClass *RC, unsigned Op0, 413 uint64_t Imm1, uint64_t Imm2); 414 415 /// Emit a MachineInstr with a floating point immediate, and a result 416 /// register in the given register class. 417 Register fastEmitInst_f(unsigned MachineInstOpcode, 418 const TargetRegisterClass *RC, 419 const ConstantFP *FPImm); 420 421 /// Emit a MachineInstr with two register operands, an immediate, and a 422 /// result register in the given register class. 423 Register fastEmitInst_rri(unsigned MachineInstOpcode, 424 const TargetRegisterClass *RC, unsigned Op0, 425 unsigned Op1, uint64_t Imm); 426 427 /// Emit a MachineInstr with a single immediate operand, and a result 428 /// register in the given register class. 429 Register fastEmitInst_i(unsigned MachineInstOpcode, 430 const TargetRegisterClass *RC, uint64_t Imm); 431 432 /// Emit a MachineInstr for an extract_subreg from a specified index of 433 /// a superregister to a specified type. 434 Register fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0, uint32_t Idx); 435 436 /// Emit MachineInstrs to compute the value of Op with all but the 437 /// least significant bit set to zero. 438 Register fastEmitZExtFromI1(MVT VT, unsigned Op0); 439 440 /// Emit an unconditional branch to the given block, unless it is the 441 /// immediate (fall-through) successor, and update the CFG. 442 void fastEmitBranch(MachineBasicBlock *MSucc, const DebugLoc &DbgLoc); 443 444 /// Emit an unconditional branch to \p FalseMBB, obtains the branch weight 445 /// and adds TrueMBB and FalseMBB to the successor list. 446 void finishCondBranch(const BasicBlock *BranchBB, MachineBasicBlock *TrueMBB, 447 MachineBasicBlock *FalseMBB); 448 449 /// Update the value map to include the new mapping for this 450 /// instruction, or insert an extra copy to get the result in a previous 451 /// determined register. 452 /// 453 /// NOTE: This is only necessary because we might select a block that uses a 454 /// value before we select the block that defines the value. It might be 455 /// possible to fix this by selecting blocks in reverse postorder. 456 void updateValueMap(const Value *I, Register Reg, unsigned NumRegs = 1); 457 458 Register createResultReg(const TargetRegisterClass *RC); 459 460 /// Try to constrain Op so that it is usable by argument OpNum of the 461 /// provided MCInstrDesc. If this fails, create a new virtual register in the 462 /// correct class and COPY the value there. 463 Register constrainOperandRegClass(const MCInstrDesc &II, Register Op, 464 unsigned OpNum); 465 466 /// Emit a constant in a register using target-specific logic, such as 467 /// constant pool loads. fastMaterializeConstant(const Constant * C)468 virtual unsigned fastMaterializeConstant(const Constant *C) { return 0; } 469 470 /// Emit an alloca address in a register using target-specific logic. fastMaterializeAlloca(const AllocaInst * C)471 virtual unsigned fastMaterializeAlloca(const AllocaInst *C) { return 0; } 472 473 /// Emit the floating-point constant +0.0 in a register using target- 474 /// specific logic. fastMaterializeFloatZero(const ConstantFP * CF)475 virtual unsigned fastMaterializeFloatZero(const ConstantFP *CF) { 476 return 0; 477 } 478 479 /// Check if \c Add is an add that can be safely folded into \c GEP. 480 /// 481 /// \c Add can be folded into \c GEP if: 482 /// - \c Add is an add, 483 /// - \c Add's size matches \c GEP's, 484 /// - \c Add is in the same basic block as \c GEP, and 485 /// - \c Add has a constant operand. 486 bool canFoldAddIntoGEP(const User *GEP, const Value *Add); 487 488 /// Create a machine mem operand from the given instruction. 489 MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const; 490 491 CmpInst::Predicate optimizeCmpPredicate(const CmpInst *CI) const; 492 493 bool lowerCallTo(const CallInst *CI, MCSymbol *Symbol, unsigned NumArgs); 494 bool lowerCallTo(const CallInst *CI, const char *SymName, 495 unsigned NumArgs); 496 bool lowerCallTo(CallLoweringInfo &CLI); 497 498 bool lowerCall(const CallInst *I); 499 /// Select and emit code for a binary operator instruction, which has 500 /// an opcode which directly corresponds to the given ISD opcode. 501 bool selectBinaryOp(const User *I, unsigned ISDOpcode); 502 bool selectFNeg(const User *I, const Value *In); 503 bool selectGetElementPtr(const User *I); 504 bool selectStackmap(const CallInst *I); 505 bool selectPatchpoint(const CallInst *I); 506 bool selectCall(const User *I); 507 bool selectIntrinsicCall(const IntrinsicInst *II); 508 bool selectBitCast(const User *I); 509 bool selectFreeze(const User *I); 510 bool selectCast(const User *I, unsigned Opcode); 511 bool selectExtractValue(const User *U); 512 bool selectXRayCustomEvent(const CallInst *II); 513 bool selectXRayTypedEvent(const CallInst *II); 514 shouldOptForSize(const MachineFunction * MF)515 bool shouldOptForSize(const MachineFunction *MF) const { 516 // TODO: Implement PGSO. 517 return MF->getFunction().hasOptSize(); 518 } 519 520 private: 521 /// Handle PHI nodes in successor blocks. 522 /// 523 /// Emit code to ensure constants are copied into registers when needed. 524 /// Remember the virtual registers that need to be added to the Machine PHI 525 /// nodes as input. We cannot just directly add them, because expansion might 526 /// result in multiple MBB's for one BB. As such, the start of the BB might 527 /// correspond to a different MBB than the end. 528 bool handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 529 530 /// Helper for materializeRegForValue to materialize a constant in a 531 /// target-independent way. 532 Register materializeConstant(const Value *V, MVT VT); 533 534 /// Helper for getRegForVale. This function is called when the value 535 /// isn't already available in a register and must be materialized with new 536 /// instructions. 537 Register materializeRegForValue(const Value *V, MVT VT); 538 539 /// Clears LocalValueMap and moves the area for the new local variables 540 /// to the beginning of the block. It helps to avoid spilling cached variables 541 /// across heavy instructions like calls. 542 void flushLocalValueMap(); 543 544 /// Removes dead local value instructions after SavedLastLocalvalue. 545 void removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue); 546 547 /// Insertion point before trying to select the current instruction. 548 MachineBasicBlock::iterator SavedInsertPt; 549 550 /// Add a stackmap or patchpoint intrinsic call's live variable 551 /// operands to a stackmap or patchpoint machine instruction. 552 bool addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops, 553 const CallInst *CI, unsigned StartIdx); 554 bool lowerCallOperands(const CallInst *CI, unsigned ArgIdx, unsigned NumArgs, 555 const Value *Callee, bool ForceRetVoidTy, 556 CallLoweringInfo &CLI); 557 }; 558 559 } // end namespace llvm 560 561 #endif // LLVM_CODEGEN_FASTISEL_H 562