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