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