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/CodeGen/MachineBasicBlock.h"
20
21namespace llvm {
22
23class AllocaInst;
24class Constant;
25class ConstantFP;
26class CallInst;
27class DataLayout;
28class FunctionLoweringInfo;
29class Instruction;
30class LoadInst;
31class MVT;
32class MachineConstantPool;
33class MachineFrameInfo;
34class MachineFunction;
35class MachineInstr;
36class MachineRegisterInfo;
37class TargetInstrInfo;
38class TargetLibraryInfo;
39class TargetLowering;
40class TargetMachine;
41class TargetRegisterClass;
42class TargetRegisterInfo;
43class User;
44class Value;
45
46/// This is a fast-path instruction selection class that generates poor code and
47/// doesn't support illegal types or non-trivial lowering, but runs quickly.
48class FastISel {
49protected:
50  DenseMap<const Value *, unsigned> LocalValueMap;
51  FunctionLoweringInfo &FuncInfo;
52  MachineFunction *MF;
53  MachineRegisterInfo &MRI;
54  MachineFrameInfo &MFI;
55  MachineConstantPool &MCP;
56  DebugLoc DbgLoc;
57  const TargetMachine &TM;
58  const DataLayout &DL;
59  const TargetInstrInfo &TII;
60  const TargetLowering &TLI;
61  const TargetRegisterInfo &TRI;
62  const TargetLibraryInfo *LibInfo;
63
64  /// The position of the last instruction for materializing constants for use
65  /// in the current block. It resets to EmitStartPt when it makes sense (for
66  /// example, it's usually profitable to avoid function calls between the
67  /// definition and the use)
68  MachineInstr *LastLocalValue;
69
70  /// The top most instruction in the current block that is allowed for emitting
71  /// local variables. LastLocalValue resets to EmitStartPt when it makes sense
72  /// (for example, on function calls)
73  MachineInstr *EmitStartPt;
74
75public:
76  /// Return the position of the last instruction emitted for materializing
77  /// constants for use in the current block.
78  MachineInstr *getLastLocalValue() { return LastLocalValue; }
79
80  /// Update the position of the last instruction emitted for materializing
81  /// constants for use in the current block.
82  void setLastLocalValue(MachineInstr *I) {
83    EmitStartPt = I;
84    LastLocalValue = I;
85  }
86
87  /// Set the current block to which generated machine instructions will be
88  /// appended, and clear the local CSE map.
89  void startNewBlock();
90
91  /// Return current debug location information.
92  DebugLoc getCurDebugLoc() const { return DbgLoc; }
93
94  /// Do "fast" instruction selection for function arguments and append machine
95  /// instructions to the current block. Return true if it is successful.
96  bool LowerArguments();
97
98  /// Do "fast" instruction selection for the given LLVM IR instruction, and
99  /// append generated machine instructions to the current block. Return true if
100  /// selection was successful.
101  bool SelectInstruction(const Instruction *I);
102
103  /// Do "fast" instruction selection for the given LLVM IR operator
104  /// (Instruction or ConstantExpr), and append generated machine instructions
105  /// to the current block. Return true if selection was successful.
106  bool SelectOperator(const User *I, unsigned Opcode);
107
108  /// Create a virtual register and arrange for it to be assigned the value for
109  /// the given LLVM value.
110  unsigned getRegForValue(const Value *V);
111
112  /// Look up the value to see if its value is already cached in a register. It
113  /// may be defined by instructions across blocks or defined locally.
114  unsigned lookUpRegForValue(const Value *V);
115
116  /// This is a wrapper around getRegForValue that also takes care of truncating
117  /// or sign-extending the given getelementptr index value.
118  std::pair<unsigned, bool> getRegForGEPIndex(const Value *V);
119
120  /// \brief We're checking to see if we can fold \p LI into \p FoldInst. Note
121  /// that we could have a sequence where multiple LLVM IR instructions are
122  /// folded into the same machineinstr.  For example we could have:
123  ///
124  ///   A: x = load i32 *P
125  ///   B: y = icmp A, 42
126  ///   C: br y, ...
127  ///
128  /// In this scenario, \p LI is "A", and \p FoldInst is "C".  We know about "B"
129  /// (and any other folded instructions) because it is between A and C.
130  ///
131  /// If we succeed folding, return true.
132  bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst);
133
134  /// \brief The specified machine instr operand is a vreg, and that vreg is
135  /// being provided by the specified load instruction.  If possible, try to
136  /// fold the load as an operand to the instruction, returning true if
137  /// possible.
138  ///
139  /// This method should be implemented by targets.
140  virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/,
141                                   const LoadInst * /*LI*/) {
142    return false;
143  }
144
145  /// Reset InsertPt to prepare for inserting instructions into the current
146  /// block.
147  void recomputeInsertPt();
148
149  /// Remove all dead instructions between the I and E.
150  void removeDeadCode(MachineBasicBlock::iterator I,
151                      MachineBasicBlock::iterator E);
152
153  struct SavePoint {
154    MachineBasicBlock::iterator InsertPt;
155    DebugLoc DL;
156  };
157
158  /// Prepare InsertPt to begin inserting instructions into the local value area
159  /// and return the old insert position.
160  SavePoint enterLocalValueArea();
161
162  /// Reset InsertPt to the given old insert position.
163  void leaveLocalValueArea(SavePoint Old);
164
165  virtual ~FastISel();
166
167protected:
168  explicit FastISel(FunctionLoweringInfo &funcInfo,
169                    const TargetLibraryInfo *libInfo);
170
171  /// This method is called by target-independent code when the normal FastISel
172  /// process fails to select an instruction.  This gives targets a chance to
173  /// emit code for anything that doesn't fit into FastISel's framework. It
174  /// returns true if it was successful.
175  virtual bool
176  TargetSelectInstruction(const Instruction *I) = 0;
177
178  /// This method is called by target-independent code to do target specific
179  /// argument lowering. It returns true if it was successful.
180  virtual bool FastLowerArguments();
181
182  /// This method is called by target-independent code to request that an
183  /// instruction with the given type and opcode be emitted.
184  virtual unsigned FastEmit_(MVT VT,
185                             MVT RetVT,
186                             unsigned Opcode);
187
188  /// This method is called by target-independent code to request that an
189  /// instruction with the given type, opcode, and register operand be emitted.
190  virtual unsigned FastEmit_r(MVT VT,
191                              MVT RetVT,
192                              unsigned Opcode,
193                              unsigned Op0, bool Op0IsKill);
194
195  /// This method is called by target-independent code to request that an
196  /// instruction with the given type, opcode, and register operands be emitted.
197  virtual unsigned FastEmit_rr(MVT VT,
198                               MVT RetVT,
199                               unsigned Opcode,
200                               unsigned Op0, bool Op0IsKill,
201                               unsigned Op1, bool Op1IsKill);
202
203  /// This method is called by target-independent code to request that an
204  /// instruction with the given type, opcode, and register and immediate
205  /// operands be emitted.
206  virtual unsigned FastEmit_ri(MVT VT,
207                               MVT RetVT,
208                               unsigned Opcode,
209                               unsigned Op0, bool Op0IsKill,
210                               uint64_t Imm);
211
212  /// This method is called by target-independent code to request that an
213  /// instruction with the given type, opcode, and register and floating-point
214  /// immediate operands be emitted.
215  virtual unsigned FastEmit_rf(MVT VT,
216                               MVT RetVT,
217                               unsigned Opcode,
218                               unsigned Op0, bool Op0IsKill,
219                               const ConstantFP *FPImm);
220
221  /// This method is called by target-independent code to request that an
222  /// instruction with the given type, opcode, and register and immediate
223  /// operands be emitted.
224  virtual unsigned FastEmit_rri(MVT VT,
225                                MVT RetVT,
226                                unsigned Opcode,
227                                unsigned Op0, bool Op0IsKill,
228                                unsigned Op1, bool Op1IsKill,
229                                uint64_t Imm);
230
231  /// \brief This method is a wrapper of FastEmit_ri.
232  ///
233  /// It first tries to emit an instruction with an immediate operand using
234  /// FastEmit_ri.  If that fails, it materializes the immediate into a register
235  /// and try FastEmit_rr instead.
236  unsigned FastEmit_ri_(MVT VT,
237                        unsigned Opcode,
238                        unsigned Op0, bool Op0IsKill,
239                        uint64_t Imm, MVT ImmType);
240
241  /// This method is called by target-independent code to request that an
242  /// instruction with the given type, opcode, and immediate operand be emitted.
243  virtual unsigned FastEmit_i(MVT VT,
244                              MVT RetVT,
245                              unsigned Opcode,
246                              uint64_t Imm);
247
248  /// This method is called by target-independent code to request that an
249  /// instruction with the given type, opcode, and floating-point immediate
250  /// operand be emitted.
251  virtual unsigned FastEmit_f(MVT VT,
252                              MVT RetVT,
253                              unsigned Opcode,
254                              const ConstantFP *FPImm);
255
256  /// Emit a MachineInstr with no operands and a result register in the given
257  /// register class.
258  unsigned FastEmitInst_(unsigned MachineInstOpcode,
259                         const TargetRegisterClass *RC);
260
261  /// Emit a MachineInstr with one register operand and a result register in the
262  /// given register class.
263  unsigned FastEmitInst_r(unsigned MachineInstOpcode,
264                          const TargetRegisterClass *RC,
265                          unsigned Op0, bool Op0IsKill);
266
267  /// Emit a MachineInstr with two register operands and a result register in
268  /// the given register class.
269  unsigned FastEmitInst_rr(unsigned MachineInstOpcode,
270                           const TargetRegisterClass *RC,
271                           unsigned Op0, bool Op0IsKill,
272                           unsigned Op1, bool Op1IsKill);
273
274  /// Emit a MachineInstr with three register operands and a result register in
275  /// the given register class.
276  unsigned FastEmitInst_rrr(unsigned MachineInstOpcode,
277                           const TargetRegisterClass *RC,
278                           unsigned Op0, bool Op0IsKill,
279                           unsigned Op1, bool Op1IsKill,
280                           unsigned Op2, bool Op2IsKill);
281
282  /// Emit a MachineInstr with a register operand, an immediate, and a result
283  /// register in the given register class.
284  unsigned FastEmitInst_ri(unsigned MachineInstOpcode,
285                           const TargetRegisterClass *RC,
286                           unsigned Op0, bool Op0IsKill,
287                           uint64_t Imm);
288
289  /// Emit a MachineInstr with one register operand and two immediate operands.
290  unsigned FastEmitInst_rii(unsigned MachineInstOpcode,
291                           const TargetRegisterClass *RC,
292                           unsigned Op0, bool Op0IsKill,
293                           uint64_t Imm1, uint64_t Imm2);
294
295  /// Emit a MachineInstr with two register operands and a result register in
296  /// the given register class.
297  unsigned FastEmitInst_rf(unsigned MachineInstOpcode,
298                           const TargetRegisterClass *RC,
299                           unsigned Op0, bool Op0IsKill,
300                           const ConstantFP *FPImm);
301
302  /// Emit a MachineInstr with two register operands, an immediate, and a result
303  /// register in the given register class.
304  unsigned FastEmitInst_rri(unsigned MachineInstOpcode,
305                            const TargetRegisterClass *RC,
306                            unsigned Op0, bool Op0IsKill,
307                            unsigned Op1, bool Op1IsKill,
308                            uint64_t Imm);
309
310  /// Emit a MachineInstr with two register operands, two immediates operands,
311  /// and a result register in the given register class.
312  unsigned FastEmitInst_rrii(unsigned MachineInstOpcode,
313                             const TargetRegisterClass *RC,
314                             unsigned Op0, bool Op0IsKill,
315                             unsigned Op1, bool Op1IsKill,
316                             uint64_t Imm1, uint64_t Imm2);
317
318  /// Emit a MachineInstr with a single immediate operand, and a result register
319  /// in the given register class.
320  unsigned FastEmitInst_i(unsigned MachineInstrOpcode,
321                          const TargetRegisterClass *RC,
322                          uint64_t Imm);
323
324  /// Emit a MachineInstr with a two immediate operands.
325  unsigned FastEmitInst_ii(unsigned MachineInstrOpcode,
326                          const TargetRegisterClass *RC,
327                          uint64_t Imm1, uint64_t Imm2);
328
329  /// Emit a MachineInstr for an extract_subreg from a specified index of a
330  /// superregister to a specified type.
331  unsigned FastEmitInst_extractsubreg(MVT RetVT,
332                                      unsigned Op0, bool Op0IsKill,
333                                      uint32_t Idx);
334
335  /// Emit MachineInstrs to compute the value of Op with all but the least
336  /// significant bit set to zero.
337  unsigned FastEmitZExtFromI1(MVT VT,
338                              unsigned Op0, bool Op0IsKill);
339
340  /// Emit an unconditional branch to the given block, unless it is the
341  /// immediate (fall-through) successor, and update the CFG.
342  void FastEmitBranch(MachineBasicBlock *MBB, DebugLoc DL);
343
344  void UpdateValueMap(const Value* I, unsigned Reg, unsigned NumRegs = 1);
345
346  unsigned createResultReg(const TargetRegisterClass *RC);
347
348  /// Try to constrain Op so that it is usable by argument OpNum of the provided
349  /// MCInstrDesc. If this fails, create a new virtual register in the correct
350  /// class and COPY the value there.
351  unsigned constrainOperandRegClass(const MCInstrDesc &II, unsigned Op,
352                                    unsigned OpNum);
353
354  /// Emit a constant in a register using target-specific logic, such as
355  /// constant pool loads.
356  virtual unsigned TargetMaterializeConstant(const Constant* C) {
357    return 0;
358  }
359
360  /// Emit an alloca address in a register using target-specific logic.
361  virtual unsigned TargetMaterializeAlloca(const AllocaInst* C) {
362    return 0;
363  }
364
365  virtual unsigned TargetMaterializeFloatZero(const ConstantFP* CF) {
366    return 0;
367  }
368
369  /// \brief Check if \c Add is an add that can be safely folded into \c GEP.
370  ///
371  /// \c Add can be folded into \c GEP if:
372  /// - \c Add is an add,
373  /// - \c Add's size matches \c GEP's,
374  /// - \c Add is in the same basic block as \c GEP, and
375  /// - \c Add has a constant operand.
376  bool canFoldAddIntoGEP(const User *GEP, const Value *Add);
377
378  /// Test whether the given value has exactly one use.
379  bool hasTrivialKill(const Value *V) const;
380
381  /// \brief Create a machine mem operand from the given instruction.
382  MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const;
383
384private:
385  bool SelectBinaryOp(const User *I, unsigned ISDOpcode);
386
387  bool SelectFNeg(const User *I);
388
389  bool SelectGetElementPtr(const User *I);
390
391  bool SelectStackmap(const CallInst *I);
392  bool SelectCall(const User *I);
393
394  bool SelectBitCast(const User *I);
395
396  bool SelectCast(const User *I, unsigned Opcode);
397
398  bool SelectExtractValue(const User *I);
399
400  bool SelectInsertValue(const User *I);
401
402  /// \brief Handle PHI nodes in successor blocks.
403  ///
404  /// Emit code to ensure constants are copied into registers when needed.
405  /// Remember the virtual registers that need to be added to the Machine PHI
406  /// nodes as input.  We cannot just directly add them, because expansion might
407  /// result in multiple MBB's for one BB.  As such, the start of the BB might
408  /// correspond to a different MBB than the end.
409  bool HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
410
411  /// Helper for getRegForVale. This function is called when the value isn't
412  /// already available in a register and must be materialized with new
413  /// instructions.
414  unsigned materializeRegForValue(const Value *V, MVT VT);
415
416  /// Clears LocalValueMap and moves the area for the new local variables to the
417  /// beginning of the block. It helps to avoid spilling cached variables across
418  /// heavy instructions like calls.
419  void flushLocalValueMap();
420
421  bool addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
422                           const CallInst *CI, unsigned StartIdx);
423};
424
425}
426
427#endif
428