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