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/CodeGen/CallingConvLower.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/IR/CallingConv.h"
22 #include "llvm/IR/IntrinsicInst.h"
23 #include "llvm/Target/TargetLowering.h"
27 /// \brief This is a fast-path instruction selection class that generates poor
28 /// code and doesn't support illegal types or non-trivial lowering, but runs
46 : Val(nullptr), Ty(nullptr), IsSExt(false), IsZExt(false),
47 IsInReg(false), IsSRet(false), IsNest(false), IsByVal(false),
48 IsInAlloca(false), IsReturned(false), Alignment(0) {}
50 /// \brief Set CallLoweringInfo attribute flags based on a call instruction
51 /// and called function attributes.
52 void setAttributes(ImmutableCallSite *CS, unsigned AttrIdx);
54 typedef std::vector<ArgListEntry> ArgListTy;
56 struct CallLoweringInfo {
62 bool DoesNotReturn : 1;
63 bool IsReturnValueUsed : 1;
65 // \brief IsTailCall Should be modified by implementations of FastLowerCall
66 // that perform tail call conversions.
69 unsigned NumFixedArgs;
70 CallingConv::ID CallConv;
74 ImmutableCallSite *CS;
77 unsigned NumResultRegs;
81 SmallVector<Value *, 16> OutVals;
82 SmallVector<ISD::ArgFlagsTy, 16> OutFlags;
83 SmallVector<unsigned, 16> OutRegs;
84 SmallVector<ISD::InputArg, 4> Ins;
85 SmallVector<unsigned, 4> InRegs;
88 : RetTy(nullptr), RetSExt(false), RetZExt(false), IsVarArg(false),
89 IsInReg(false), DoesNotReturn(false), IsReturnValueUsed(true),
90 IsTailCall(false), NumFixedArgs(-1), CallConv(CallingConv::C),
91 Callee(nullptr), SymName(nullptr), CS(nullptr), Call(nullptr),
92 ResultReg(0), NumResultRegs(0), IsPatchPoint(false) {}
94 CallLoweringInfo &setCallee(Type *ResultTy, FunctionType *FuncTy,
95 const Value *Target, ArgListTy &&ArgsList,
96 ImmutableCallSite &Call) {
100 IsInReg = Call.paramHasAttr(0, Attribute::InReg);
101 DoesNotReturn = Call.doesNotReturn();
102 IsVarArg = FuncTy->isVarArg();
103 IsReturnValueUsed = !Call.getInstruction()->use_empty();
104 RetSExt = Call.paramHasAttr(0, Attribute::SExt);
105 RetZExt = Call.paramHasAttr(0, Attribute::ZExt);
107 CallConv = Call.getCallingConv();
108 Args = std::move(ArgsList);
109 NumFixedArgs = FuncTy->getNumParams();
116 CallLoweringInfo &setCallee(Type *ResultTy, FunctionType *FuncTy,
117 const char *Target, ArgListTy &&ArgsList,
118 ImmutableCallSite &Call,
119 unsigned FixedArgs = ~0U) {
121 Callee = Call.getCalledValue();
124 IsInReg = Call.paramHasAttr(0, Attribute::InReg);
125 DoesNotReturn = Call.doesNotReturn();
126 IsVarArg = FuncTy->isVarArg();
127 IsReturnValueUsed = !Call.getInstruction()->use_empty();
128 RetSExt = Call.paramHasAttr(0, Attribute::SExt);
129 RetZExt = Call.paramHasAttr(0, Attribute::ZExt);
131 CallConv = Call.getCallingConv();
132 Args = std::move(ArgsList);
133 NumFixedArgs = (FixedArgs == ~0U) ? FuncTy->getNumParams() : FixedArgs;
140 CallLoweringInfo &setCallee(CallingConv::ID CC, Type *ResultTy,
141 const Value *Target, ArgListTy &&ArgsList,
142 unsigned FixedArgs = ~0U) {
146 Args = std::move(ArgsList);
147 NumFixedArgs = (FixedArgs == ~0U) ? Args.size() : FixedArgs;
151 CallLoweringInfo &setCallee(CallingConv::ID CC, Type *ResultTy,
152 const char *Target, ArgListTy &&ArgsList,
153 unsigned FixedArgs = ~0U) {
157 Args = std::move(ArgsList);
158 NumFixedArgs = (FixedArgs == ~0U) ? Args.size() : FixedArgs;
162 CallLoweringInfo &setTailCall(bool Value = true) {
167 CallLoweringInfo &setIsPatchPoint(bool Value = true) {
168 IsPatchPoint = Value;
172 ArgListTy &getArgs() { return Args; }
187 DenseMap<const Value *, unsigned> LocalValueMap;
188 FunctionLoweringInfo &FuncInfo;
190 MachineRegisterInfo &MRI;
191 MachineFrameInfo &MFI;
192 MachineConstantPool &MCP;
194 const TargetMachine &TM;
195 const DataLayout &DL;
196 const TargetInstrInfo &TII;
197 const TargetLowering &TLI;
198 const TargetRegisterInfo &TRI;
199 const TargetLibraryInfo *LibInfo;
200 bool SkipTargetIndependentISel;
202 /// \brief The position of the last instruction for materializing constants
203 /// for use in the current block. It resets to EmitStartPt when it makes sense
204 /// (for example, it's usually profitable to avoid function calls between the
205 /// definition and the use)
206 MachineInstr *LastLocalValue;
208 /// \brief The top most instruction in the current block that is allowed for
209 /// emitting local variables. LastLocalValue resets to EmitStartPt when it
210 /// makes sense (for example, on function calls)
211 MachineInstr *EmitStartPt;
214 /// \brief Return the position of the last instruction emitted for
215 /// materializing constants for use in the current block.
216 MachineInstr *getLastLocalValue() { return LastLocalValue; }
218 /// \brief Update the position of the last instruction emitted for
219 /// materializing constants for use in the current block.
220 void setLastLocalValue(MachineInstr *I) {
225 /// \brief Set the current block to which generated machine instructions will
226 /// be appended, and clear the local CSE map.
227 void startNewBlock();
229 /// \brief Return current debug location information.
230 DebugLoc getCurDebugLoc() const { return DbgLoc; }
232 /// \brief Do "fast" instruction selection for function arguments and append
233 /// the machine instructions to the current block. Returns true when
235 bool lowerArguments();
237 /// \brief Do "fast" instruction selection for the given LLVM IR instruction
238 /// and append the generated machine instructions to the current block.
239 /// Returns true if selection was successful.
240 bool selectInstruction(const Instruction *I);
242 /// \brief Do "fast" instruction selection for the given LLVM IR operator
243 /// (Instruction or ConstantExpr), and append generated machine instructions
244 /// to the current block. Return true if selection was successful.
245 bool selectOperator(const User *I, unsigned Opcode);
247 /// \brief Create a virtual register and arrange for it to be assigned the
248 /// value for the given LLVM value.
249 unsigned getRegForValue(const Value *V);
251 /// \brief Look up the value to see if its value is already cached in a
252 /// register. It may be defined by instructions across blocks or defined
254 unsigned lookUpRegForValue(const Value *V);
256 /// \brief This is a wrapper around getRegForValue that also takes care of
257 /// truncating or sign-extending the given getelementptr index value.
258 std::pair<unsigned, bool> getRegForGEPIndex(const Value *V);
260 /// \brief We're checking to see if we can fold \p LI into \p FoldInst. Note
261 /// that we could have a sequence where multiple LLVM IR instructions are
262 /// folded into the same machineinstr. For example we could have:
264 /// A: x = load i32 *P
265 /// B: y = icmp A, 42
268 /// In this scenario, \p LI is "A", and \p FoldInst is "C". We know about "B"
269 /// (and any other folded instructions) because it is between A and C.
271 /// If we succeed folding, return true.
272 bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst);
274 /// \brief The specified machine instr operand is a vreg, and that vreg is
275 /// being provided by the specified load instruction. If possible, try to
276 /// fold the load as an operand to the instruction, returning true if
279 /// This method should be implemented by targets.
280 virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/,
281 const LoadInst * /*LI*/) {
285 /// \brief Reset InsertPt to prepare for inserting instructions into the
287 void recomputeInsertPt();
289 /// \brief Remove all dead instructions between the I and E.
290 void removeDeadCode(MachineBasicBlock::iterator I,
291 MachineBasicBlock::iterator E);
294 MachineBasicBlock::iterator InsertPt;
298 /// \brief Prepare InsertPt to begin inserting instructions into the local
299 /// value area and return the old insert position.
300 SavePoint enterLocalValueArea();
302 /// \brief Reset InsertPt to the given old insert position.
303 void leaveLocalValueArea(SavePoint Old);
308 explicit FastISel(FunctionLoweringInfo &FuncInfo,
309 const TargetLibraryInfo *LibInfo,
310 bool SkipTargetIndependentISel = false);
312 /// \brief This method is called by target-independent code when the normal
313 /// FastISel process fails to select an instruction. This gives targets a
314 /// chance to emit code for anything that doesn't fit into FastISel's
315 /// framework. It returns true if it was successful.
316 virtual bool fastSelectInstruction(const Instruction *I) = 0;
318 /// \brief This method is called by target-independent code to do target-
319 /// specific argument lowering. It returns true if it was successful.
320 virtual bool fastLowerArguments();
322 /// \brief This method is called by target-independent code to do target-
323 /// specific call lowering. It returns true if it was successful.
324 virtual bool fastLowerCall(CallLoweringInfo &CLI);
326 /// \brief This method is called by target-independent code to do target-
327 /// specific intrinsic lowering. It returns true if it was successful.
328 virtual bool fastLowerIntrinsicCall(const IntrinsicInst *II);
330 /// \brief This method is called by target-independent code to request that an
331 /// instruction with the given type and opcode be emitted.
332 virtual unsigned fastEmit_(MVT VT, MVT RetVT, unsigned Opcode);
334 /// \brief This method is called by target-independent code to request that an
335 /// instruction with the given type, opcode, and register operand be emitted.
336 virtual unsigned fastEmit_r(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0,
339 /// \brief This method is called by target-independent code to request that an
340 /// instruction with the given type, opcode, and register operands be emitted.
341 virtual unsigned fastEmit_rr(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0,
342 bool Op0IsKill, unsigned Op1, bool Op1IsKill);
344 /// \brief This method is called by target-independent code to request that an
345 /// instruction with the given type, opcode, and register and immediate
346 // operands be emitted.
347 virtual unsigned fastEmit_ri(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0,
348 bool Op0IsKill, uint64_t Imm);
350 /// \brief This method is called by target-independent code to request that an
351 /// instruction with the given type, opcode, and register and floating-point
352 /// immediate operands be emitted.
353 virtual unsigned fastEmit_rf(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0,
354 bool Op0IsKill, const ConstantFP *FPImm);
356 /// \brief This method is called by target-independent code to request that an
357 /// instruction with the given type, opcode, and register and immediate
358 /// operands be emitted.
359 virtual unsigned fastEmit_rri(MVT VT, MVT RetVT, unsigned Opcode,
360 unsigned Op0, bool Op0IsKill, unsigned Op1,
361 bool Op1IsKill, uint64_t Imm);
363 /// \brief This method is a wrapper of fastEmit_ri.
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 unsigned fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0, bool Op0IsKill,
369 uint64_t Imm, MVT ImmType);
371 /// \brief 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);
375 /// \brief 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);
381 /// \brief Emit a MachineInstr with no operands and a result register in the
382 /// given register class.
383 unsigned fastEmitInst_(unsigned MachineInstOpcode,
384 const TargetRegisterClass *RC);
386 /// \brief Emit a MachineInstr with one register operand and a result register
387 /// in the given register class.
388 unsigned fastEmitInst_r(unsigned MachineInstOpcode,
389 const TargetRegisterClass *RC, unsigned Op0,
392 /// \brief Emit a MachineInstr with two register operands and a result
393 /// register in the given register class.
394 unsigned fastEmitInst_rr(unsigned MachineInstOpcode,
395 const TargetRegisterClass *RC, unsigned Op0,
396 bool Op0IsKill, unsigned Op1, bool Op1IsKill);
398 /// \brief Emit a MachineInstr with three register operands and a result
399 /// register in the given register class.
400 unsigned fastEmitInst_rrr(unsigned MachineInstOpcode,
401 const TargetRegisterClass *RC, unsigned Op0,
402 bool Op0IsKill, unsigned Op1, bool Op1IsKill,
403 unsigned Op2, bool Op2IsKill);
405 /// \brief Emit a MachineInstr with a register operand, an immediate, and a
406 /// result register in the given register class.
407 unsigned fastEmitInst_ri(unsigned MachineInstOpcode,
408 const TargetRegisterClass *RC, unsigned Op0,
409 bool Op0IsKill, uint64_t Imm);
411 /// \brief Emit a MachineInstr with one register operand and two immediate
413 unsigned fastEmitInst_rii(unsigned MachineInstOpcode,
414 const TargetRegisterClass *RC, unsigned Op0,
415 bool Op0IsKill, uint64_t Imm1, uint64_t Imm2);
417 /// \brief Emit a MachineInstr with two register operands and a result
418 /// register in the given register class.
419 unsigned fastEmitInst_rf(unsigned MachineInstOpcode,
420 const TargetRegisterClass *RC, unsigned Op0,
421 bool Op0IsKill, const ConstantFP *FPImm);
423 /// \brief Emit a MachineInstr with two register operands, an immediate, and a
424 /// result register in the given register class.
425 unsigned fastEmitInst_rri(unsigned MachineInstOpcode,
426 const TargetRegisterClass *RC, unsigned Op0,
427 bool Op0IsKill, unsigned Op1, bool Op1IsKill,
430 /// \brief Emit a MachineInstr with two register operands, two immediates
431 /// operands, and a result register in the given register class.
432 unsigned fastEmitInst_rrii(unsigned MachineInstOpcode,
433 const TargetRegisterClass *RC, unsigned Op0,
434 bool Op0IsKill, unsigned Op1, bool Op1IsKill,
435 uint64_t Imm1, uint64_t Imm2);
437 /// \brief Emit a MachineInstr with a single immediate operand, and a result
438 /// register in the given register class.
439 unsigned fastEmitInst_i(unsigned MachineInstrOpcode,
440 const TargetRegisterClass *RC, uint64_t Imm);
442 /// \brief Emit a MachineInstr with a two immediate operands.
443 unsigned fastEmitInst_ii(unsigned MachineInstrOpcode,
444 const TargetRegisterClass *RC, uint64_t Imm1,
447 /// \brief Emit a MachineInstr for an extract_subreg from a specified index of
448 /// a superregister to a specified type.
449 unsigned fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0, bool Op0IsKill,
452 /// \brief Emit MachineInstrs to compute the value of Op with all but the
453 /// least significant bit set to zero.
454 unsigned fastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill);
456 /// \brief Emit an unconditional branch to the given block, unless it is the
457 /// immediate (fall-through) successor, and update the CFG.
458 void fastEmitBranch(MachineBasicBlock *MBB, DebugLoc DL);
460 /// \brief Update the value map to include the new mapping for this
461 /// instruction, or insert an extra copy to get the result in a previous
462 /// determined register.
464 /// NOTE: This is only necessary because we might select a block that uses a
465 /// value before we select the block that defines the value. It might be
466 /// possible to fix this by selecting blocks in reverse postorder.
467 void updateValueMap(const Value *I, unsigned Reg, unsigned NumRegs = 1);
469 unsigned createResultReg(const TargetRegisterClass *RC);
471 /// \brief Try to constrain Op so that it is usable by argument OpNum of the
472 /// provided MCInstrDesc. If this fails, create a new virtual register in the
473 /// correct class and COPY the value there.
474 unsigned constrainOperandRegClass(const MCInstrDesc &II, unsigned Op,
477 /// \brief Emit a constant in a register using target-specific logic, such as
478 /// constant pool loads.
479 virtual unsigned fastMaterializeConstant(const Constant *C) { return 0; }
481 /// \brief Emit an alloca address in a register using target-specific logic.
482 virtual unsigned fastMaterializeAlloca(const AllocaInst *C) { return 0; }
484 /// \brief Emit the floating-point constant +0.0 in a register using target-
486 virtual unsigned fastMaterializeFloatZero(const ConstantFP *CF) {
490 /// \brief Check if \c Add is an add that can be safely folded into \c GEP.
492 /// \c Add can be folded into \c GEP if:
493 /// - \c Add is an add,
494 /// - \c Add's size matches \c GEP's,
495 /// - \c Add is in the same basic block as \c GEP, and
496 /// - \c Add has a constant operand.
497 bool canFoldAddIntoGEP(const User *GEP, const Value *Add);
499 /// \brief Test whether the given value has exactly one use.
500 bool hasTrivialKill(const Value *V);
502 /// \brief Create a machine mem operand from the given instruction.
503 MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const;
505 CmpInst::Predicate optimizeCmpPredicate(const CmpInst *CI) const;
507 bool lowerCallTo(const CallInst *CI, const char *SymName, unsigned NumArgs);
508 bool lowerCallTo(CallLoweringInfo &CLI);
510 bool isCommutativeIntrinsic(IntrinsicInst const *II) {
511 switch (II->getIntrinsicID()) {
512 case Intrinsic::sadd_with_overflow:
513 case Intrinsic::uadd_with_overflow:
514 case Intrinsic::smul_with_overflow:
515 case Intrinsic::umul_with_overflow:
523 bool lowerCall(const CallInst *I);
524 /// \brief Select and emit code for a binary operator instruction, which has
525 /// an opcode which directly corresponds to the given ISD opcode.
526 bool selectBinaryOp(const User *I, unsigned ISDOpcode);
527 bool selectFNeg(const User *I);
528 bool selectGetElementPtr(const User *I);
529 bool selectStackmap(const CallInst *I);
530 bool selectPatchpoint(const CallInst *I);
531 bool selectCall(const User *Call);
532 bool selectIntrinsicCall(const IntrinsicInst *II);
533 bool selectBitCast(const User *I);
534 bool selectCast(const User *I, unsigned Opcode);
535 bool selectExtractValue(const User *I);
536 bool selectInsertValue(const User *I);
539 /// \brief Handle PHI nodes in successor blocks.
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);
548 /// \brief Helper for materializeRegForValue to materialize a constant in a
549 /// target-independent way.
550 unsigned materializeConstant(const Value *V, MVT VT);
552 /// \brief Helper for getRegForVale. This function is called when the value
553 /// isn't already available in a register and must be materialized with new
555 unsigned materializeRegForValue(const Value *V, MVT VT);
557 /// \brief 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();
562 /// \brief Insertion point before trying to select the current instruction.
563 MachineBasicBlock::iterator SavedInsertPt;
565 /// \brief Add a stackmap or patchpoint intrinsic call's live variable
566 /// operands to a stackmap or patchpoint machine instruction.
567 bool addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
568 const CallInst *CI, unsigned StartIdx);
569 bool lowerCallOperands(const CallInst *CI, unsigned ArgIdx, unsigned NumArgs,
570 const Value *Callee, bool ForceRetVoidTy,
571 CallLoweringInfo &CLI);
574 } // end namespace llvm