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