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