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