1 //===- FastISel.h - Definition of the FastISel class ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file defines the FastISel class.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_FASTISEL_H
16 #define LLVM_CODEGEN_FASTISEL_H
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"
43 class FunctionLoweringInfo;
45 class MachineConstantPool;
46 class MachineFrameInfo;
47 class MachineFunction;
49 class MachineMemOperand;
51 class MachineRegisterInfo;
55 class TargetInstrInfo;
56 class TargetLibraryInfo;
58 class TargetRegisterClass;
59 class TargetRegisterInfo;
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
69 using ArgListEntry = TargetLoweringBase::ArgListEntry;
70 using ArgListTy = TargetLoweringBase::ArgListTy;
71 struct CallLoweringInfo {
72 Type *RetTy = nullptr;
77 bool DoesNotReturn : 1;
78 bool IsReturnValueUsed : 1;
79 bool IsPatchPoint : 1;
81 // \brief IsTailCall Should be modified by implementations of FastLowerCall
82 // that perform tail call conversions.
83 bool IsTailCall = false;
85 unsigned NumFixedArgs = -1;
86 CallingConv::ID CallConv = CallingConv::C;
87 const Value *Callee = nullptr;
88 MCSymbol *Symbol = nullptr;
90 ImmutableCallSite *CS = nullptr;
91 MachineInstr *Call = nullptr;
92 unsigned ResultReg = 0;
93 unsigned NumResultRegs = 0;
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;
102 : RetSExt(false), RetZExt(false), IsVarArg(false), IsInReg(false),
103 DoesNotReturn(false), IsReturnValueUsed(true), IsPatchPoint(false) {}
105 CallLoweringInfo &setCallee(Type *ResultTy, FunctionType *FuncTy,
106 const Value *Target, ArgListTy &&ArgsList,
107 ImmutableCallSite &Call) {
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);
118 CallConv = Call.getCallingConv();
119 Args = std::move(ArgsList);
120 NumFixedArgs = FuncTy->getNumParams();
127 CallLoweringInfo &setCallee(Type *ResultTy, FunctionType *FuncTy,
128 MCSymbol *Target, ArgListTy &&ArgsList,
129 ImmutableCallSite &Call,
130 unsigned FixedArgs = ~0U) {
132 Callee = Call.getCalledValue();
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);
142 CallConv = Call.getCallingConv();
143 Args = std::move(ArgsList);
144 NumFixedArgs = (FixedArgs == ~0U) ? FuncTy->getNumParams() : FixedArgs;
151 CallLoweringInfo &setCallee(CallingConv::ID CC, Type *ResultTy,
152 const Value *Target, ArgListTy &&ArgsList,
153 unsigned FixedArgs = ~0U) {
157 Args = std::move(ArgsList);
158 NumFixedArgs = (FixedArgs == ~0U) ? Args.size() : FixedArgs;
162 CallLoweringInfo &setCallee(const DataLayout &DL, MCContext &Ctx,
163 CallingConv::ID CC, Type *ResultTy,
164 StringRef Target, ArgListTy &&ArgsList,
165 unsigned FixedArgs = ~0U);
167 CallLoweringInfo &setCallee(CallingConv::ID CC, Type *ResultTy,
168 MCSymbol *Target, ArgListTy &&ArgsList,
169 unsigned FixedArgs = ~0U) {
173 Args = std::move(ArgsList);
174 NumFixedArgs = (FixedArgs == ~0U) ? Args.size() : FixedArgs;
178 CallLoweringInfo &setTailCall(bool Value = true) {
183 CallLoweringInfo &setIsPatchPoint(bool Value = true) {
184 IsPatchPoint = Value;
188 ArgListTy &getArgs() { return Args; }
203 DenseMap<const Value *, unsigned> LocalValueMap;
204 FunctionLoweringInfo &FuncInfo;
206 MachineRegisterInfo &MRI;
207 MachineFrameInfo &MFI;
208 MachineConstantPool &MCP;
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;
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;
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;
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; }
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) {
243 /// \brief Set the current block to which generated machine instructions will
244 /// be appended, and clear the local CSE map.
245 void startNewBlock();
247 /// \brief Return current debug location information.
248 DebugLoc getCurDebugLoc() const { return DbgLoc; }
250 /// \brief Do "fast" instruction selection for function arguments and append
251 /// the machine instructions to the current block. Returns true when
253 bool lowerArguments();
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);
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);
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);
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
272 unsigned lookUpRegForValue(const Value *V);
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);
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:
282 /// A: x = load i32 *P
283 /// B: y = icmp A, 42
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.
289 /// If we succeed folding, return true.
290 bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst);
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
297 /// This method should be implemented by targets.
298 virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/,
299 const LoadInst * /*LI*/) {
303 /// \brief Reset InsertPt to prepare for inserting instructions into the
305 void recomputeInsertPt();
307 /// \brief Remove all dead instructions between the I and E.
308 void removeDeadCode(MachineBasicBlock::iterator I,
309 MachineBasicBlock::iterator E);
312 MachineBasicBlock::iterator InsertPt;
316 /// \brief Prepare InsertPt to begin inserting instructions into the local
317 /// value area and return the old insert position.
318 SavePoint enterLocalValueArea();
320 /// \brief Reset InsertPt to the given old insert position.
321 void leaveLocalValueArea(SavePoint Old);
324 explicit FastISel(FunctionLoweringInfo &FuncInfo,
325 const TargetLibraryInfo *LibInfo,
326 bool SkipTargetIndependentISel = false);
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;
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();
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);
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);
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);
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,
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);
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);
366 /// \brief This method is a wrapper of fastEmit_ri.
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);
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);
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);
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);
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,
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);
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);
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);
414 /// \brief Emit a MachineInstr with one register operand and two immediate
416 unsigned fastEmitInst_rii(unsigned MachineInstOpcode,
417 const TargetRegisterClass *RC, unsigned Op0,
418 bool Op0IsKill, uint64_t Imm1, uint64_t Imm2);
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);
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,
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);
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,
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);
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);
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);
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.
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);
465 unsigned createResultReg(const TargetRegisterClass *RC);
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,
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; }
477 /// \brief Emit an alloca address in a register using target-specific logic.
478 virtual unsigned fastMaterializeAlloca(const AllocaInst *C) { return 0; }
480 /// \brief Emit the floating-point constant +0.0 in a register using target-
482 virtual unsigned fastMaterializeFloatZero(const ConstantFP *CF) {
486 /// \brief Check if \c Add is an add that can be safely folded into \c GEP.
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);
495 /// \brief Test whether the given value has exactly one use.
496 bool hasTrivialKill(const Value *V);
498 /// \brief Create a machine mem operand from the given instruction.
499 MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const;
501 CmpInst::Predicate optimizeCmpPredicate(const CmpInst *CI) const;
503 bool lowerCallTo(const CallInst *CI, MCSymbol *Symbol, unsigned NumArgs);
504 bool lowerCallTo(const CallInst *CI, const char *SymbolName,
506 bool lowerCallTo(CallLoweringInfo &CLI);
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:
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);
537 /// \brief Handle PHI nodes in successor blocks.
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);
546 /// \brief Helper for materializeRegForValue to materialize a constant in a
547 /// target-independent way.
548 unsigned materializeConstant(const Value *V, MVT VT);
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
553 unsigned materializeRegForValue(const Value *V, MVT VT);
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();
560 /// \brief Removes dead local value instructions after SavedLastLocalvalue.
561 void removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue);
563 /// \brief Insertion point before trying to select the current instruction.
564 MachineBasicBlock::iterator SavedInsertPt;
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);
575 } // end namespace llvm
577 #endif // LLVM_CODEGEN_FASTISEL_H