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