SelectionDAGISel.h revision 0e5f1306b059b62d7725f324e087efbc8e7a782d 
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/Pass.h"
19#include "llvm/Constant.h"
20#include "llvm/CodeGen/SelectionDAG.h"
21#include "llvm/CodeGen/SelectionDAGNodes.h"
22
23namespace llvm {
24  class SelectionDAGLowering;
25  class SDOperand;
26  class MachineRegisterInfo;
27  class MachineBasicBlock;
28  class MachineFunction;
29  class MachineInstr;
30  class TargetLowering;
31  class FunctionLoweringInfo;
32  class HazardRecognizer;
33  class CollectorMetadata;
34
35/// SelectionDAGISel - This is the common base class used for SelectionDAG-based
36/// pattern-matching instruction selectors.
37class SelectionDAGISel : public FunctionPass {
38public:
39  TargetLowering &TLI;
40  MachineRegisterInfo *RegInfo;
41  SelectionDAG *CurDAG;
42  MachineBasicBlock *BB;
43  AliasAnalysis *AA;
44  CollectorMetadata *GCI;
45  bool FastISel;
46  std::vector<SDNode*> TopOrder;
47  static char ID;
48
49  explicit SelectionDAGISel(TargetLowering &tli, bool fast = false) :
50    FunctionPass((intptr_t)&ID), TLI(tli), GCI(0), FastISel(fast), DAGSize(0) {}
51
52  TargetLowering &getTargetLowering() { return TLI; }
53
54  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
55
56  virtual bool runOnFunction(Function &Fn);
57
58  unsigned MakeReg(MVT VT);
59
60  virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {}
61  virtual void InstructionSelect(SelectionDAG &SD) = 0;
62  virtual void InstructionSelectPostProcessing(SelectionDAG &DAG) {}
63
64  virtual void SelectRootInit() {
65    DAGSize = CurDAG->AssignTopologicalOrder(TopOrder);
66  }
67
68  /// SelectInlineAsmMemoryOperand - Select the specified address as a target
69  /// addressing mode, according to the specified constraint code.  If this does
70  /// not match or is not implemented, return true.  The resultant operands
71  /// (which will appear in the machine instruction) should be added to the
72  /// OutOps vector.
73  virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op,
74                                            char ConstraintCode,
75                                            std::vector<SDOperand> &OutOps,
76                                            SelectionDAG &DAG) {
77    return true;
78  }
79
80  /// CanBeFoldedBy - Returns true if the specific operand node N of U can be
81  /// folded during instruction selection that starts at Root?
82  virtual bool CanBeFoldedBy(SDNode *N, SDNode *U, SDNode *Root) const {
83    return true;
84  }
85
86  /// CreateTargetHazardRecognizer - Return a newly allocated hazard recognizer
87  /// to use for this target when scheduling the DAG.
88  virtual HazardRecognizer *CreateTargetHazardRecognizer();
89
90  /// CaseBlock - This structure is used to communicate between SDLowering and
91  /// SDISel for the code generation of additional basic blocks needed by multi-
92  /// case switch statements.
93  struct CaseBlock {
94    CaseBlock(ISD::CondCode cc, Value *cmplhs, Value *cmprhs, Value *cmpmiddle,
95              MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
96              MachineBasicBlock *me)
97      : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
98        TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {}
99    // CC - the condition code to use for the case block's setcc node
100    ISD::CondCode CC;
101    // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit.
102    // Emit by default LHS op RHS. MHS is used for range comparisons:
103    // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
104    Value *CmpLHS, *CmpMHS, *CmpRHS;
105    // TrueBB/FalseBB - the block to branch to if the setcc is true/false.
106    MachineBasicBlock *TrueBB, *FalseBB;
107    // ThisBB - the block into which to emit the code for the setcc and branches
108    MachineBasicBlock *ThisBB;
109  };
110  struct JumpTable {
111    JumpTable(unsigned R, unsigned J, MachineBasicBlock *M,
112              MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {}
113
114    /// Reg - the virtual register containing the index of the jump table entry
115    //. to jump to.
116    unsigned Reg;
117    /// JTI - the JumpTableIndex for this jump table in the function.
118    unsigned JTI;
119    /// MBB - the MBB into which to emit the code for the indirect jump.
120    MachineBasicBlock *MBB;
121    /// Default - the MBB of the default bb, which is a successor of the range
122    /// check MBB.  This is when updating PHI nodes in successors.
123    MachineBasicBlock *Default;
124  };
125  struct JumpTableHeader {
126    JumpTableHeader(uint64_t F, uint64_t L, Value* SV, MachineBasicBlock* H,
127                    bool E = false):
128      First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {}
129    uint64_t First;
130    uint64_t Last;
131    Value *SValue;
132    MachineBasicBlock *HeaderBB;
133    bool Emitted;
134  };
135  typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
136
137  struct BitTestCase {
138    BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr):
139      Mask(M), ThisBB(T), TargetBB(Tr) { }
140    uint64_t Mask;
141    MachineBasicBlock* ThisBB;
142    MachineBasicBlock* TargetBB;
143  };
144
145  typedef SmallVector<BitTestCase, 3> BitTestInfo;
146
147  struct BitTestBlock {
148    BitTestBlock(uint64_t F, uint64_t R, Value* SV,
149                 unsigned Rg, bool E,
150                 MachineBasicBlock* P, MachineBasicBlock* D,
151                 const BitTestInfo& C):
152      First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E),
153      Parent(P), Default(D), Cases(C) { }
154    uint64_t First;
155    uint64_t Range;
156    Value  *SValue;
157    unsigned Reg;
158    bool Emitted;
159    MachineBasicBlock *Parent;
160    MachineBasicBlock *Default;
161    BitTestInfo Cases;
162  };
163
164protected:
165  /// DAGSize - Size of DAG being instruction selected.
166  ///
167  unsigned DAGSize;
168
169  /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
170  /// by tblgen.  Others should not call it.
171  void SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops,
172                                     SelectionDAG &DAG);
173
174  // Calls to these predicates are generated by tblgen.
175  bool CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
176                    int64_t DesiredMaskS) const;
177  bool CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
178                    int64_t DesiredMaskS) const;
179
180private:
181  void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
182                            FunctionLoweringInfo &FuncInfo);
183  void SelectBasicBlock(BasicBlock *BB, MachineFunction &MF,
184                        FunctionLoweringInfo &FuncInfo,
185                        alist<SDNode, LargestSDNode> &AllNodes);
186
187  void BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
188           std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
189                         FunctionLoweringInfo &FuncInfo);
190  void CodeGenAndEmitDAG(SelectionDAG &DAG);
191  void LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL);
192
193  void ComputeLiveOutVRegInfo(SelectionDAG &DAG);
194
195  /// Pick a safe ordering and emit instructions for each target node in the
196  /// graph.
197  void ScheduleAndEmitDAG(SelectionDAG &DAG);
198
199  /// SwitchCases - Vector of CaseBlock structures used to communicate
200  /// SwitchInst code generation information.
201  std::vector<CaseBlock> SwitchCases;
202
203  /// JTCases - Vector of JumpTable structures which holds necessary information
204  /// for emitting a jump tables during SwitchInst code generation.
205  std::vector<JumpTableBlock> JTCases;
206
207  std::vector<BitTestBlock> BitTestCases;
208};
209
210}
211
212#endif /* LLVM_CODEGEN_SELECTIONDAG_ISEL_H */
213