Split type expansion into ExpandInteger and ExpandFloat
[oota-llvm.git] / lib / CodeGen / SelectionDAG / LegalizeTypes.h
1 //===-- LegalizeTypes.h - Definition of the DAG Type Legalizer class ------===//
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 defines the DAGTypeLegalizer class.  This is a private interface
11 // shared between the code that implements the SelectionDAG::LegalizeTypes
12 // method.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #ifndef SELECTIONDAG_LEGALIZETYPES_H
17 #define SELECTIONDAG_LEGALIZETYPES_H
18
19 #define DEBUG_TYPE "legalize-types"
20 #include "llvm/CodeGen/SelectionDAG.h"
21 #include "llvm/Target/TargetLowering.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/Debug.h"
25
26 namespace llvm {
27
28 //===----------------------------------------------------------------------===//
29 /// DAGTypeLegalizer - This takes an arbitrary SelectionDAG as input and
30 /// hacks on it until the target machine can handle it.  This involves
31 /// eliminating value sizes the machine cannot handle (promoting small sizes to
32 /// large sizes or splitting up large values into small values) as well as
33 /// eliminating operations the machine cannot handle.
34 ///
35 /// This code also does a small amount of optimization and recognition of idioms
36 /// as part of its processing.  For example, if a target does not support a
37 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
38 /// will attempt merge setcc and brc instructions into brcc's.
39 ///
40 class VISIBILITY_HIDDEN DAGTypeLegalizer {
41   TargetLowering &TLI;
42   SelectionDAG &DAG;
43 public:
44   // NodeIDFlags - This pass uses the NodeID on the SDNodes to hold information
45   // about the state of the node.  The enum has all the values.
46   enum NodeIDFlags {
47     /// ReadyToProcess - All operands have been processed, so this node is ready
48     /// to be handled.
49     ReadyToProcess = 0,
50
51     /// NewNode - This is a new node that was created in the process of
52     /// legalizing some other node.
53     NewNode = -1,
54
55     /// Processed - This is a node that has already been processed.
56     Processed = -2
57
58     // 1+ - This is a node which has this many unlegalized operands.
59   };
60 private:
61   enum LegalizeAction {
62     Legal,          // The target natively supports this type.
63     PromoteInteger, // Replace this integer type with a larger one.
64     ExpandInteger,  // Split this integer type into two of half the size.
65     PromoteFloat,   // Convert this float type to a same size integer type.
66     ExpandFloat,    // Split this float type into two of half the size.
67     Scalarize,      // Replace this one-element vector type with its element type.
68     Split           // This vector type should be split into smaller vectors.
69   };
70
71   /// ValueTypeActions - This is a bitvector that contains two bits for each
72   /// simple value type, where the two bits correspond to the LegalizeAction
73   /// enum from TargetLowering.  This can be queried with "getTypeAction(VT)".
74   TargetLowering::ValueTypeActionImpl ValueTypeActions;
75
76   /// getTypeAction - Return how we should legalize values of this type, either
77   /// it is already legal, or we need to promote it to a larger integer type, or
78   /// we need to expand it into multiple registers of a smaller integer type, or
79   /// we need to scalarize a one-element vector type into the element type, or
80   /// we need to split a vector type into smaller vector types.
81   LegalizeAction getTypeAction(MVT VT) const {
82     switch (ValueTypeActions.getTypeAction(VT)) {
83     default:
84       assert(false && "Unknown legalize action!");
85     case TargetLowering::Legal:
86       return Legal;
87     case TargetLowering::Promote:
88       return PromoteInteger;
89     case TargetLowering::Expand:
90       // Expand can mean
91       // 1) split scalar in half, 2) convert a float to an integer,
92       // 3) scalarize a single-element vector, 4) split a vector in two.
93       if (!VT.isVector()) {
94         if (VT.isInteger())
95           return ExpandInteger;
96         else if (VT.getSizeInBits() ==
97                  TLI.getTypeToTransformTo(VT).getSizeInBits())
98           return PromoteFloat;
99         else
100           return ExpandFloat;
101       } else if (VT.getVectorNumElements() == 1) {
102         return Scalarize;
103       } else {
104         return Split;
105       }
106     }
107   }
108
109   /// isTypeLegal - Return true if this type is legal on this target.
110   bool isTypeLegal(MVT VT) const {
111     return ValueTypeActions.getTypeAction(VT) == TargetLowering::Legal;
112   }
113
114   /// PromotedIntegers - For integer nodes that are below legal width, this map
115   /// indicates what promoted value to use.
116   DenseMap<SDOperand, SDOperand> PromotedIntegers;
117
118   /// ExpandedIntegers - For integer nodes that need to be expanded this map
119   /// indicates which operands are the expanded version of the input.
120   DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedIntegers;
121
122   /// PromotedFloats - For floating point nodes converted to integers of
123   /// the same size, this map indicates the converted value to use.
124   DenseMap<SDOperand, SDOperand> PromotedFloats;
125
126   /// ExpandedFloats - For float nodes that need to be expanded this map
127   /// indicates which operands are the expanded version of the input.
128   DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedFloats;
129
130   /// ScalarizedVectors - For nodes that are <1 x ty>, this map indicates the
131   /// scalar value of type 'ty' to use.
132   DenseMap<SDOperand, SDOperand> ScalarizedVectors;
133
134   /// SplitVectors - For nodes that need to be split this map indicates
135   /// which operands are the expanded version of the input.
136   DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > SplitVectors;
137
138   /// ReplacedNodes - For nodes that have been replaced with another,
139   /// indicates the replacement node to use.
140   DenseMap<SDOperand, SDOperand> ReplacedNodes;
141
142   /// Worklist - This defines a worklist of nodes to process.  In order to be
143   /// pushed onto this worklist, all operands of a node must have already been
144   /// processed.
145   SmallVector<SDNode*, 128> Worklist;
146
147 public:
148   explicit DAGTypeLegalizer(SelectionDAG &dag)
149     : TLI(dag.getTargetLoweringInfo()), DAG(dag),
150     ValueTypeActions(TLI.getValueTypeActions()) {
151     assert(MVT::LAST_VALUETYPE <= 32 &&
152            "Too many value types for ValueTypeActions to hold!");
153   }
154
155   void run();
156
157   /// ReanalyzeNode - Recompute the NodeID and correct processed operands
158   /// for the specified node, adding it to the worklist if ready.
159   void ReanalyzeNode(SDNode *N) {
160     N->setNodeId(NewNode);
161     AnalyzeNewNode(N);
162   }
163
164   void NoteReplacement(SDOperand From, SDOperand To) {
165     ExpungeNode(From);
166     ExpungeNode(To);
167     ReplacedNodes[From] = To;
168   }
169
170 private:
171   void AnalyzeNewNode(SDNode *&N);
172
173   void ReplaceValueWith(SDOperand From, SDOperand To);
174   void ReplaceNodeWith(SDNode *From, SDNode *To);
175
176   void RemapNode(SDOperand &N);
177   void ExpungeNode(SDOperand N);
178
179   // Common routines.
180   SDOperand CreateStackStoreLoad(SDOperand Op, MVT DestVT);
181   SDOperand MakeLibCall(RTLIB::Libcall LC, MVT RetVT,
182                         const SDOperand *Ops, unsigned NumOps, bool isSigned);
183
184   SDOperand BitConvertToInteger(SDOperand Op);
185   SDOperand JoinIntegers(SDOperand Lo, SDOperand Hi);
186   void SplitInteger(SDOperand Op, SDOperand &Lo, SDOperand &Hi);
187   void SplitInteger(SDOperand Op, MVT LoVT, MVT HiVT,
188                     SDOperand &Lo, SDOperand &Hi);
189
190   SDOperand GetVectorElementPointer(SDOperand VecPtr, MVT EltVT,
191                                     SDOperand Index);
192
193   //===--------------------------------------------------------------------===//
194   // Integer Promotion Support: LegalizeIntegerTypes.cpp
195   //===--------------------------------------------------------------------===//
196
197   SDOperand GetPromotedInteger(SDOperand Op) {
198     SDOperand &PromotedOp = PromotedIntegers[Op];
199     RemapNode(PromotedOp);
200     assert(PromotedOp.Val && "Operand wasn't promoted?");
201     return PromotedOp;
202   }
203   void SetPromotedInteger(SDOperand Op, SDOperand Result);
204
205   /// ZExtPromotedInteger - Get a promoted operand and zero extend it to the
206   /// final size.
207   SDOperand ZExtPromotedInteger(SDOperand Op) {
208     MVT OldVT = Op.getValueType();
209     Op = GetPromotedInteger(Op);
210     return DAG.getZeroExtendInReg(Op, OldVT);
211   }
212
213   // Integer Result Promotion.
214   void PromoteIntegerResult(SDNode *N, unsigned ResNo);
215   SDOperand PromoteIntRes_BIT_CONVERT(SDNode *N);
216   SDOperand PromoteIntRes_BUILD_PAIR(SDNode *N);
217   SDOperand PromoteIntRes_Constant(SDNode *N);
218   SDOperand PromoteIntRes_CTLZ(SDNode *N);
219   SDOperand PromoteIntRes_CTPOP(SDNode *N);
220   SDOperand PromoteIntRes_CTTZ(SDNode *N);
221   SDOperand PromoteIntRes_EXTRACT_VECTOR_ELT(SDNode *N);
222   SDOperand PromoteIntRes_FP_ROUND(SDNode *N);
223   SDOperand PromoteIntRes_FP_TO_XINT(SDNode *N);
224   SDOperand PromoteIntRes_INT_EXTEND(SDNode *N);
225   SDOperand PromoteIntRes_LOAD(LoadSDNode *N);
226   SDOperand PromoteIntRes_SDIV(SDNode *N);
227   SDOperand PromoteIntRes_SELECT   (SDNode *N);
228   SDOperand PromoteIntRes_SELECT_CC(SDNode *N);
229   SDOperand PromoteIntRes_SETCC(SDNode *N);
230   SDOperand PromoteIntRes_SHL(SDNode *N);
231   SDOperand PromoteIntRes_SimpleIntBinOp(SDNode *N);
232   SDOperand PromoteIntRes_SRA(SDNode *N);
233   SDOperand PromoteIntRes_SRL(SDNode *N);
234   SDOperand PromoteIntRes_TRUNCATE(SDNode *N);
235   SDOperand PromoteIntRes_UDIV(SDNode *N);
236   SDOperand PromoteIntRes_UNDEF(SDNode *N);
237
238   // Integer Operand Promotion.
239   bool PromoteIntegerOperand(SDNode *N, unsigned OperandNo);
240   SDOperand PromoteIntOp_ANY_EXTEND(SDNode *N);
241   SDOperand PromoteIntOp_BUILD_PAIR(SDNode *N);
242   SDOperand PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo);
243   SDOperand PromoteIntOp_BRCOND(SDNode *N, unsigned OpNo);
244   SDOperand PromoteIntOp_BUILD_VECTOR(SDNode *N);
245   SDOperand PromoteIntOp_FP_EXTEND(SDNode *N);
246   SDOperand PromoteIntOp_FP_ROUND(SDNode *N);
247   SDOperand PromoteIntOp_INT_TO_FP(SDNode *N);
248   SDOperand PromoteIntOp_INSERT_VECTOR_ELT(SDNode *N, unsigned OpNo);
249   SDOperand PromoteIntOp_MEMBARRIER(SDNode *N);
250   SDOperand PromoteIntOp_SELECT(SDNode *N, unsigned OpNo);
251   SDOperand PromoteIntOp_SETCC(SDNode *N, unsigned OpNo);
252   SDOperand PromoteIntOp_SIGN_EXTEND(SDNode *N);
253   SDOperand PromoteIntOp_STORE(StoreSDNode *N, unsigned OpNo);
254   SDOperand PromoteIntOp_TRUNCATE(SDNode *N);
255   SDOperand PromoteIntOp_ZERO_EXTEND(SDNode *N);
256
257   void PromoteSetCCOperands(SDOperand &LHS,SDOperand &RHS, ISD::CondCode Code);
258
259   //===--------------------------------------------------------------------===//
260   // Integer Expansion Support: LegalizeIntegerTypes.cpp
261   //===--------------------------------------------------------------------===//
262
263   void GetExpandedInteger(SDOperand Op, SDOperand &Lo, SDOperand &Hi);
264   void SetExpandedInteger(SDOperand Op, SDOperand Lo, SDOperand Hi);
265
266   // Integer Result Expansion.
267   void ExpandIntegerResult(SDNode *N, unsigned ResNo);
268   void ExpandIntRes_ANY_EXTEND        (SDNode *N, SDOperand &Lo, SDOperand &Hi);
269   void ExpandIntRes_AssertZext        (SDNode *N, SDOperand &Lo, SDOperand &Hi);
270   void ExpandIntRes_BIT_CONVERT       (SDNode *N, SDOperand &Lo, SDOperand &Hi);
271   void ExpandIntRes_BUILD_PAIR        (SDNode *N, SDOperand &Lo, SDOperand &Hi);
272   void ExpandIntRes_Constant          (SDNode *N, SDOperand &Lo, SDOperand &Hi);
273   void ExpandIntRes_CTLZ              (SDNode *N, SDOperand &Lo, SDOperand &Hi);
274   void ExpandIntRes_CTPOP             (SDNode *N, SDOperand &Lo, SDOperand &Hi);
275   void ExpandIntRes_CTTZ              (SDNode *N, SDOperand &Lo, SDOperand &Hi);
276   void ExpandIntRes_EXTRACT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi);
277   void ExpandIntRes_LOAD          (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi);
278   void ExpandIntRes_MERGE_VALUES      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
279   void ExpandIntRes_SIGN_EXTEND       (SDNode *N, SDOperand &Lo, SDOperand &Hi);
280   void ExpandIntRes_SIGN_EXTEND_INREG (SDNode *N, SDOperand &Lo, SDOperand &Hi);
281   void ExpandIntRes_TRUNCATE          (SDNode *N, SDOperand &Lo, SDOperand &Hi);
282   void ExpandIntRes_UNDEF             (SDNode *N, SDOperand &Lo, SDOperand &Hi);
283   void ExpandIntRes_ZERO_EXTEND       (SDNode *N, SDOperand &Lo, SDOperand &Hi);
284   void ExpandIntRes_FP_TO_SINT        (SDNode *N, SDOperand &Lo, SDOperand &Hi);
285   void ExpandIntRes_FP_TO_UINT        (SDNode *N, SDOperand &Lo, SDOperand &Hi);
286
287   void ExpandIntRes_Logical           (SDNode *N, SDOperand &Lo, SDOperand &Hi);
288   void ExpandIntRes_BSWAP             (SDNode *N, SDOperand &Lo, SDOperand &Hi);
289   void ExpandIntRes_ADDSUB            (SDNode *N, SDOperand &Lo, SDOperand &Hi);
290   void ExpandIntRes_ADDSUBC           (SDNode *N, SDOperand &Lo, SDOperand &Hi);
291   void ExpandIntRes_ADDSUBE           (SDNode *N, SDOperand &Lo, SDOperand &Hi);
292   void ExpandIntRes_SELECT            (SDNode *N, SDOperand &Lo, SDOperand &Hi);
293   void ExpandIntRes_SELECT_CC         (SDNode *N, SDOperand &Lo, SDOperand &Hi);
294   void ExpandIntRes_MUL               (SDNode *N, SDOperand &Lo, SDOperand &Hi);
295   void ExpandIntRes_SDIV              (SDNode *N, SDOperand &Lo, SDOperand &Hi);
296   void ExpandIntRes_SREM              (SDNode *N, SDOperand &Lo, SDOperand &Hi);
297   void ExpandIntRes_UDIV              (SDNode *N, SDOperand &Lo, SDOperand &Hi);
298   void ExpandIntRes_UREM              (SDNode *N, SDOperand &Lo, SDOperand &Hi);
299   void ExpandIntRes_Shift             (SDNode *N, SDOperand &Lo, SDOperand &Hi);
300
301   void ExpandShiftByConstant(SDNode *N, unsigned Amt,
302                              SDOperand &Lo, SDOperand &Hi);
303   bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi);
304
305   // Integer Operand Expansion.
306   bool ExpandIntegerOperand(SDNode *N, unsigned OperandNo);
307   SDOperand ExpandIntOp_BIT_CONVERT(SDNode *N);
308   SDOperand ExpandIntOp_BR_CC(SDNode *N);
309   SDOperand ExpandIntOp_BUILD_VECTOR(SDNode *N);
310   SDOperand ExpandIntOp_EXTRACT_ELEMENT(SDNode *N);
311   SDOperand ExpandIntOp_SETCC(SDNode *N);
312   SDOperand ExpandIntOp_SINT_TO_FP(SDOperand Source, MVT DestTy);
313   SDOperand ExpandIntOp_STORE(StoreSDNode *N, unsigned OpNo);
314   SDOperand ExpandIntOp_TRUNCATE(SDNode *N);
315   SDOperand ExpandIntOp_UINT_TO_FP(SDOperand Source, MVT DestTy);
316
317   void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS,
318                            ISD::CondCode &CCCode);
319
320   //===--------------------------------------------------------------------===//
321   // Float to Integer Conversion Support: LegalizeFloatTypes.cpp
322   //===--------------------------------------------------------------------===//
323
324   SDOperand GetPromotedFloat(SDOperand Op) {
325     SDOperand &PromotedOp = PromotedFloats[Op];
326     RemapNode(PromotedOp);
327     assert(PromotedOp.Val && "Operand wasn't converted to integer?");
328     return PromotedOp;
329   }
330   void SetPromotedFloat(SDOperand Op, SDOperand Result);
331
332   // Result Float to Integer Conversion.
333   void PromoteFloatResult(SDNode *N, unsigned OpNo);
334   SDOperand PromoteFloatRes_BIT_CONVERT(SDNode *N);
335   SDOperand PromoteFloatRes_BUILD_PAIR(SDNode *N);
336   SDOperand PromoteFloatRes_ConstantFP(ConstantFPSDNode *N);
337   SDOperand PromoteFloatRes_FADD(SDNode *N);
338   SDOperand PromoteFloatRes_FCOPYSIGN(SDNode *N);
339   SDOperand PromoteFloatRes_FMUL(SDNode *N);
340   SDOperand PromoteFloatRes_FSUB(SDNode *N);
341   SDOperand PromoteFloatRes_LOAD(SDNode *N);
342   SDOperand PromoteFloatRes_XINT_TO_FP(SDNode *N);
343
344   // Operand Float to Integer Conversion.
345   bool PromoteFloatOperand(SDNode *N, unsigned OpNo);
346   SDOperand PromoteFloatOp_BIT_CONVERT(SDNode *N);
347
348   //===--------------------------------------------------------------------===//
349   // Float Expansion Support: LegalizeFloatTypes.cpp
350   //===--------------------------------------------------------------------===//
351
352   void GetExpandedFloat(SDOperand Op, SDOperand &Lo, SDOperand &Hi);
353   void SetExpandedFloat(SDOperand Op, SDOperand Lo, SDOperand Hi);
354
355   // Float Result Expansion.
356   void ExpandFloatResult(SDNode *N, unsigned ResNo);
357
358   // Float Operand Expansion.
359   bool ExpandFloatOperand(SDNode *N, unsigned OperandNo);
360
361   //===--------------------------------------------------------------------===//
362   // Scalarization Support: LegalizeVectorTypes.cpp
363   //===--------------------------------------------------------------------===//
364
365   SDOperand GetScalarizedVector(SDOperand Op) {
366     SDOperand &ScalarizedOp = ScalarizedVectors[Op];
367     RemapNode(ScalarizedOp);
368     assert(ScalarizedOp.Val && "Operand wasn't scalarized?");
369     return ScalarizedOp;
370   }
371   void SetScalarizedVector(SDOperand Op, SDOperand Result);
372
373   // Vector Result Scalarization: <1 x ty> -> ty.
374   void ScalarizeResult(SDNode *N, unsigned OpNo);
375   SDOperand ScalarizeRes_BinOp(SDNode *N);
376   SDOperand ScalarizeRes_UnaryOp(SDNode *N);
377
378   SDOperand ScalarizeRes_BIT_CONVERT(SDNode *N);
379   SDOperand ScalarizeRes_FPOWI(SDNode *N);
380   SDOperand ScalarizeRes_INSERT_VECTOR_ELT(SDNode *N);
381   SDOperand ScalarizeRes_LOAD(LoadSDNode *N);
382   SDOperand ScalarizeRes_SELECT(SDNode *N);
383   SDOperand ScalarizeRes_UNDEF(SDNode *N);
384   SDOperand ScalarizeRes_VECTOR_SHUFFLE(SDNode *N);
385
386   // Vector Operand Scalarization: <1 x ty> -> ty.
387   bool ScalarizeOperand(SDNode *N, unsigned OpNo);
388   SDOperand ScalarizeOp_BIT_CONVERT(SDNode *N);
389   SDOperand ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N);
390   SDOperand ScalarizeOp_STORE(StoreSDNode *N, unsigned OpNo);
391
392   //===--------------------------------------------------------------------===//
393   // Vector Splitting Support: LegalizeVectorTypes.cpp
394   //===--------------------------------------------------------------------===//
395
396   void GetSplitVector(SDOperand Op, SDOperand &Lo, SDOperand &Hi);
397   void SetSplitVector(SDOperand Op, SDOperand Lo, SDOperand Hi);
398
399   // Vector Result Splitting: <128 x ty> -> 2 x <64 x ty>.
400   void SplitResult(SDNode *N, unsigned OpNo);
401
402   void SplitRes_UNDEF(SDNode *N, SDOperand &Lo, SDOperand &Hi);
403   void SplitRes_LOAD(LoadSDNode *N, SDOperand &Lo, SDOperand &Hi);
404   void SplitRes_BUILD_PAIR(SDNode *N, SDOperand &Lo, SDOperand &Hi);
405   void SplitRes_INSERT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi);
406   void SplitRes_VECTOR_SHUFFLE(SDNode *N, SDOperand &Lo, SDOperand &Hi);
407
408   void SplitRes_BUILD_VECTOR(SDNode *N, SDOperand &Lo, SDOperand &Hi);
409   void SplitRes_CONCAT_VECTORS(SDNode *N, SDOperand &Lo, SDOperand &Hi);
410   void SplitRes_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi);
411   void SplitRes_UnOp(SDNode *N, SDOperand &Lo, SDOperand &Hi);
412   void SplitRes_BinOp(SDNode *N, SDOperand &Lo, SDOperand &Hi);
413   void SplitRes_FPOWI(SDNode *N, SDOperand &Lo, SDOperand &Hi);
414   void SplitRes_SELECT(SDNode *N, SDOperand &Lo, SDOperand &Hi);
415
416   // Vector Operand Splitting: <128 x ty> -> 2 x <64 x ty>.
417   bool SplitOperand(SDNode *N, unsigned OpNo);
418
419   SDOperand SplitOp_BIT_CONVERT(SDNode *N);
420   SDOperand SplitOp_EXTRACT_SUBVECTOR(SDNode *N);
421   SDOperand SplitOp_EXTRACT_VECTOR_ELT(SDNode *N);
422   SDOperand SplitOp_RET(SDNode *N, unsigned OpNo);
423   SDOperand SplitOp_STORE(StoreSDNode *N, unsigned OpNo);
424   SDOperand SplitOp_VECTOR_SHUFFLE(SDNode *N, unsigned OpNo);
425 };
426
427 } // end namespace llvm.
428
429 #endif