SelectionDAGISel.h revision d850ac79b57e6e0bf68ee93a94d0b3dcd9f6ca35 
1//===-- llvm/CodeGen/SelectionDAGISel.h - Common Base 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// This file implements the SelectionDAGISel class, which is used as the common
11// base class for SelectionDAG-based instruction selectors.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_SELECTIONDAG_ISEL_H
16#define LLVM_CODEGEN_SELECTIONDAG_ISEL_H
17
18#include "llvm/BasicBlock.h"
19#include "llvm/Pass.h"
20#include "llvm/Constant.h"
21#include "llvm/CodeGen/SelectionDAG.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23
24namespace llvm {
25  class FastISel;
26  class SelectionDAGBuilder;
27  class SDValue;
28  class MachineRegisterInfo;
29  class MachineBasicBlock;
30  class MachineFunction;
31  class MachineInstr;
32  class MachineModuleInfo;
33  class TargetLowering;
34  class TargetInstrInfo;
35  class FunctionLoweringInfo;
36  class ScheduleHazardRecognizer;
37  class GCFunctionInfo;
38  class ScheduleDAGSDNodes;
39
40/// SelectionDAGISel - This is the common base class used for SelectionDAG-based
41/// pattern-matching instruction selectors.
42class SelectionDAGISel : public MachineFunctionPass {
43public:
44  const TargetMachine &TM;
45  TargetLowering &TLI;
46  FunctionLoweringInfo *FuncInfo;
47  MachineFunction *MF;
48  MachineRegisterInfo *RegInfo;
49  SelectionDAG *CurDAG;
50  SelectionDAGBuilder *SDB;
51  MachineBasicBlock *BB;
52  AliasAnalysis *AA;
53  GCFunctionInfo *GFI;
54  CodeGenOpt::Level OptLevel;
55  static char ID;
56
57  explicit SelectionDAGISel(TargetMachine &tm,
58                            CodeGenOpt::Level OL = CodeGenOpt::Default);
59  virtual ~SelectionDAGISel();
60
61  TargetLowering &getTargetLowering() { return TLI; }
62
63  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
64
65  virtual bool runOnMachineFunction(MachineFunction &MF);
66
67  unsigned MakeReg(EVT VT);
68
69  virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {}
70
71  /// PreprocessISelDAG - This hook allows targets to hack on the graph before
72  /// instruction selection starts.
73  virtual void PreprocessISelDAG() {}
74
75  /// PostprocessISelDAG() - This hook allows the target to hack on the graph
76  /// right after selection.
77  virtual void PostprocessISelDAG() {}
78
79  /// Select - Main hook targets implement to select a node.
80  virtual SDNode *Select(SDNode *N) = 0;
81
82  /// SelectInlineAsmMemoryOperand - Select the specified address as a target
83  /// addressing mode, according to the specified constraint code.  If this does
84  /// not match or is not implemented, return true.  The resultant operands
85  /// (which will appear in the machine instruction) should be added to the
86  /// OutOps vector.
87  virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
88                                            char ConstraintCode,
89                                            std::vector<SDValue> &OutOps) {
90    return true;
91  }
92
93  /// IsProfitableToFold - Returns true if it's profitable to fold the specific
94  /// operand node N of U during instruction selection that starts at Root.
95  virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
96
97  /// IsLegalToFold - Returns true if the specific operand node N of
98  /// U can be folded during instruction selection that starts at Root.
99  bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
100                     bool IgnoreChains = false) const;
101
102  /// CreateTargetHazardRecognizer - Return a newly allocated hazard recognizer
103  /// to use for this target when scheduling the DAG.
104  virtual ScheduleHazardRecognizer *CreateTargetHazardRecognizer();
105
106
107  // Opcodes used by the DAG state machine:
108  enum BuiltinOpcodes {
109    OPC_Scope,
110    OPC_RecordNode,
111    OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
112    OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,
113    OPC_RecordMemRef,
114    OPC_CaptureFlagInput,
115    OPC_MoveChild,
116    OPC_MoveParent,
117    OPC_CheckSame,
118    OPC_CheckPatternPredicate,
119    OPC_CheckPredicate,
120    OPC_CheckOpcode,
121    OPC_SwitchOpcode,
122    OPC_CheckType,
123    OPC_SwitchType,
124    OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type,
125    OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type,
126    OPC_CheckChild6Type, OPC_CheckChild7Type,
127    OPC_CheckInteger,
128    OPC_CheckCondCode,
129    OPC_CheckValueType,
130    OPC_CheckComplexPat,
131    OPC_CheckAndImm, OPC_CheckOrImm,
132    OPC_CheckFoldableChainNode,
133
134    OPC_EmitInteger,
135    OPC_EmitRegister,
136    OPC_EmitConvertToTarget,
137    OPC_EmitMergeInputChains,
138    OPC_EmitMergeInputChains1_0,
139    OPC_EmitMergeInputChains1_1,
140    OPC_EmitCopyToReg,
141    OPC_EmitNodeXForm,
142    OPC_EmitNode,
143    OPC_MorphNodeTo,
144    OPC_MarkFlagResults,
145    OPC_CompleteMatch
146  };
147
148  enum {
149    OPFL_None       = 0,     // Node has no chain or flag input and isn't variadic.
150    OPFL_Chain      = 1,     // Node has a chain input.
151    OPFL_FlagInput  = 2,     // Node has a flag input.
152    OPFL_FlagOutput = 4,     // Node has a flag output.
153    OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
154    OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
155    OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
156    OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
157    OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
158    OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
159    OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
160    OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
161
162    OPFL_VariadicInfo = OPFL_Variadic6
163  };
164
165  /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
166  /// number of fixed arity values that should be skipped when copying from the
167  /// root.
168  static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
169    return ((Flags&OPFL_VariadicInfo) >> 4)-1;
170  }
171
172
173protected:
174  /// DAGSize - Size of DAG being instruction selected.
175  ///
176  unsigned DAGSize;
177
178  /// ISelPosition - Node iterator marking the current position of
179  /// instruction selection as it procedes through the topologically-sorted
180  /// node list.
181  SelectionDAG::allnodes_iterator ISelPosition;
182
183
184  /// ISelUpdater - helper class to handle updates of the
185  /// instruction selection graph.
186  class ISelUpdater : public SelectionDAG::DAGUpdateListener {
187    SelectionDAG::allnodes_iterator &ISelPosition;
188  public:
189    explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
190      : ISelPosition(isp) {}
191
192    /// NodeDeleted - Handle nodes deleted from the graph. If the
193    /// node being deleted is the current ISelPosition node, update
194    /// ISelPosition.
195    ///
196    virtual void NodeDeleted(SDNode *N, SDNode *E) {
197      if (ISelPosition == SelectionDAG::allnodes_iterator(N))
198        ++ISelPosition;
199    }
200
201    /// NodeUpdated - Ignore updates for now.
202    virtual void NodeUpdated(SDNode *N) {}
203  };
204
205  /// ReplaceUses - replace all uses of the old node F with the use
206  /// of the new node T.
207  void ReplaceUses(SDValue F, SDValue T) {
208    ISelUpdater ISU(ISelPosition);
209    CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
210  }
211
212  /// ReplaceUses - replace all uses of the old nodes F with the use
213  /// of the new nodes T.
214  void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
215    ISelUpdater ISU(ISelPosition);
216    CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
217  }
218
219  /// ReplaceUses - replace all uses of the old node F with the use
220  /// of the new node T.
221  void ReplaceUses(SDNode *F, SDNode *T) {
222    ISelUpdater ISU(ISelPosition);
223    CurDAG->ReplaceAllUsesWith(F, T, &ISU);
224  }
225
226
227  /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
228  /// by tblgen.  Others should not call it.
229  void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops);
230
231
232public:
233  // Calls to these predicates are generated by tblgen.
234  bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
235                    int64_t DesiredMaskS) const;
236  bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
237                    int64_t DesiredMaskS) const;
238
239
240  /// CheckPatternPredicate - This function is generated by tblgen in the
241  /// target.  It runs the specified pattern predicate and returns true if it
242  /// succeeds or false if it fails.  The number is a private implementation
243  /// detail to the code tblgen produces.
244  virtual bool CheckPatternPredicate(unsigned PredNo) const {
245    assert(0 && "Tblgen should generate the implementation of this!");
246    return 0;
247  }
248
249  /// CheckNodePredicate - This function is generated by tblgen in the target.
250  /// It runs node predicate number PredNo and returns true if it succeeds or
251  /// false if it fails.  The number is a private implementation
252  /// detail to the code tblgen produces.
253  virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
254    assert(0 && "Tblgen should generate the implementation of this!");
255    return 0;
256  }
257
258  virtual bool CheckComplexPattern(SDNode *Root, SDValue N, unsigned PatternNo,
259                                   SmallVectorImpl<SDValue> &Result) {
260    assert(0 && "Tblgen should generate the implementation of this!");
261    return false;
262  }
263
264  virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
265    assert(0 && "Tblgen shoudl generate this!");
266    return SDValue();
267  }
268
269  SDNode *SelectCodeCommon(SDNode *NodeToMatch,
270                           const unsigned char *MatcherTable,
271                           unsigned TableSize);
272
273private:
274
275  // Calls to these functions are generated by tblgen.
276  SDNode *Select_INLINEASM(SDNode *N);
277  SDNode *Select_UNDEF(SDNode *N);
278  void CannotYetSelect(SDNode *N);
279
280private:
281  void DoInstructionSelection();
282  SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTs,
283                    const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo);
284
285  void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
286                            MachineModuleInfo *MMI,
287                            const TargetInstrInfo &TII);
288  void FinishBasicBlock();
289
290  void SelectBasicBlock(BasicBlock *LLVMBB,
291                        BasicBlock::iterator Begin,
292                        BasicBlock::iterator End,
293                        bool &HadTailCall);
294  void CodeGenAndEmitDAG();
295  void LowerArguments(BasicBlock *BB);
296
297  void ShrinkDemandedOps();
298  void ComputeLiveOutVRegInfo();
299
300  void HandlePHINodesInSuccessorBlocks(BasicBlock *LLVMBB);
301
302  bool HandlePHINodesInSuccessorBlocksFast(BasicBlock *LLVMBB, FastISel *F);
303
304  /// Create the scheduler. If a specific scheduler was specified
305  /// via the SchedulerRegistry, use it, otherwise select the
306  /// one preferred by the target.
307  ///
308  ScheduleDAGSDNodes *CreateScheduler();
309
310  /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
311  /// state machines that start with a OPC_SwitchOpcode node.
312  std::vector<unsigned> OpcodeOffset;
313
314  void UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain,
315                            const SmallVectorImpl<SDNode*> &ChainNodesMatched,
316                            SDValue InputFlag,const SmallVectorImpl<SDNode*> &F,
317                            bool isMorphNodeTo);
318
319};
320
321}
322
323#endif /* LLVM_CODEGEN_SELECTIONDAG_ISEL_H */
324