Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 1 | //===-- LegalizeTypes.h - Definition of the DAG Type Legalizer class ------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 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 | |
| 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 | |
| 61 | enum LegalizeAction { |
| 62 | Legal, // The target natively supports this type. |
| 63 | Promote, // This type should be executed in a larger type. |
| 64 | Expand // This type should be split into two types of half the size. |
| 65 | }; |
| 66 | |
| 67 | /// ValueTypeActions - This is a bitvector that contains two bits for each |
| 68 | /// simple value type, where the two bits correspond to the LegalizeAction |
| 69 | /// enum. This can be queried with "getTypeAction(VT)". |
| 70 | TargetLowering::ValueTypeActionImpl ValueTypeActions; |
| 71 | |
| 72 | /// getTypeAction - Return how we should legalize values of this type, either |
| 73 | /// it is already legal or we need to expand it into multiple registers of |
| 74 | /// smaller integer type, or we need to promote it to a larger type. |
| 75 | LegalizeAction getTypeAction(MVT::ValueType VT) const { |
| 76 | return (LegalizeAction)ValueTypeActions.getTypeAction(VT); |
| 77 | } |
| 78 | |
| 79 | /// isTypeLegal - Return true if this type is legal on this target. |
| 80 | /// |
| 81 | bool isTypeLegal(MVT::ValueType VT) const { |
| 82 | return getTypeAction(VT) == Legal; |
| 83 | } |
| 84 | |
| 85 | SDOperand getIntPtrConstant(uint64_t Val) { |
| 86 | return DAG.getConstant(Val, TLI.getPointerTy()); |
| 87 | } |
| 88 | |
| 89 | /// PromotedNodes - For nodes that are below legal width, this map indicates |
| 90 | /// what promoted value to use. |
| 91 | DenseMap<SDOperand, SDOperand> PromotedNodes; |
| 92 | |
| 93 | /// ExpandedNodes - For nodes that need to be expanded this map indicates |
| 94 | /// which operands are the expanded version of the input. |
| 95 | DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; |
| 96 | |
| 97 | /// ScalarizedNodes - For nodes that are <1 x ty>, this map indicates the |
| 98 | /// scalar value of type 'ty' to use. |
| 99 | DenseMap<SDOperand, SDOperand> ScalarizedNodes; |
Chris Lattner | e4af7b5 | 2007-12-08 22:40:18 +0000 | [diff] [blame] | 100 | |
| 101 | /// SplitNodes - For nodes that need to be split this map indicates |
| 102 | /// which operands are the expanded version of the input. |
| 103 | DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > SplitNodes; |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 104 | |
| 105 | /// ReplacedNodes - For nodes that have been replaced with another, |
| 106 | /// indicates the replacement node to use. |
| 107 | DenseMap<SDOperand, SDOperand> ReplacedNodes; |
| 108 | |
| 109 | /// Worklist - This defines a worklist of nodes to process. In order to be |
| 110 | /// pushed onto this worklist, all operands of a node must have already been |
| 111 | /// processed. |
| 112 | SmallVector<SDNode*, 128> Worklist; |
| 113 | |
| 114 | public: |
| 115 | explicit DAGTypeLegalizer(SelectionDAG &dag) |
| 116 | : TLI(dag.getTargetLoweringInfo()), DAG(dag), |
| 117 | ValueTypeActions(TLI.getValueTypeActions()) { |
| 118 | assert(MVT::LAST_VALUETYPE <= 32 && |
| 119 | "Too many value types for ValueTypeActions to hold!"); |
| 120 | } |
| 121 | |
| 122 | void run(); |
| 123 | |
| 124 | private: |
| 125 | void MarkNewNodes(SDNode *N); |
| 126 | |
| 127 | void ReplaceValueWith(SDOperand From, SDOperand To); |
| 128 | void ReplaceNodeWith(SDNode *From, SDNode *To); |
| 129 | |
| 130 | void RemapNode(SDOperand &N); |
| 131 | |
Chris Lattner | 7514646 | 2007-12-08 21:59:32 +0000 | [diff] [blame] | 132 | // Common routines. |
| 133 | SDOperand CreateStackStoreLoad(SDOperand Op, MVT::ValueType DestVT); |
| 134 | SDOperand HandleMemIntrinsic(SDNode *N); |
| 135 | void SplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); |
| 136 | |
| 137 | //===--------------------------------------------------------------------===// |
| 138 | // Promotion Support: LegalizeTypesPromote.cpp |
| 139 | //===--------------------------------------------------------------------===// |
| 140 | |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 141 | SDOperand GetPromotedOp(SDOperand Op) { |
| 142 | SDOperand &PromotedOp = PromotedNodes[Op]; |
| 143 | RemapNode(PromotedOp); |
| 144 | assert(PromotedOp.Val && "Operand wasn't promoted?"); |
| 145 | return PromotedOp; |
| 146 | } |
| 147 | void SetPromotedOp(SDOperand Op, SDOperand Result); |
Chris Lattner | 7514646 | 2007-12-08 21:59:32 +0000 | [diff] [blame] | 148 | |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 149 | /// GetPromotedZExtOp - Get a promoted operand and zero extend it to the final |
| 150 | /// size. |
| 151 | SDOperand GetPromotedZExtOp(SDOperand Op) { |
| 152 | MVT::ValueType OldVT = Op.getValueType(); |
| 153 | Op = GetPromotedOp(Op); |
| 154 | return DAG.getZeroExtendInReg(Op, OldVT); |
| 155 | } |
Chris Lattner | 7514646 | 2007-12-08 21:59:32 +0000 | [diff] [blame] | 156 | |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 157 | // Result Promotion. |
| 158 | void PromoteResult(SDNode *N, unsigned ResNo); |
| 159 | SDOperand PromoteResult_UNDEF(SDNode *N); |
| 160 | SDOperand PromoteResult_Constant(SDNode *N); |
| 161 | SDOperand PromoteResult_TRUNCATE(SDNode *N); |
| 162 | SDOperand PromoteResult_INT_EXTEND(SDNode *N); |
| 163 | SDOperand PromoteResult_FP_ROUND(SDNode *N); |
| 164 | SDOperand PromoteResult_FP_TO_XINT(SDNode *N); |
| 165 | SDOperand PromoteResult_SETCC(SDNode *N); |
| 166 | SDOperand PromoteResult_LOAD(LoadSDNode *N); |
| 167 | SDOperand PromoteResult_SimpleIntBinOp(SDNode *N); |
| 168 | SDOperand PromoteResult_SDIV(SDNode *N); |
| 169 | SDOperand PromoteResult_UDIV(SDNode *N); |
| 170 | SDOperand PromoteResult_SHL(SDNode *N); |
| 171 | SDOperand PromoteResult_SRA(SDNode *N); |
| 172 | SDOperand PromoteResult_SRL(SDNode *N); |
| 173 | SDOperand PromoteResult_SELECT (SDNode *N); |
| 174 | SDOperand PromoteResult_SELECT_CC(SDNode *N); |
| 175 | |
Chris Lattner | 7514646 | 2007-12-08 21:59:32 +0000 | [diff] [blame] | 176 | // Operand Promotion. |
| 177 | bool PromoteOperand(SDNode *N, unsigned OperandNo); |
| 178 | SDOperand PromoteOperand_ANY_EXTEND(SDNode *N); |
| 179 | SDOperand PromoteOperand_ZERO_EXTEND(SDNode *N); |
| 180 | SDOperand PromoteOperand_SIGN_EXTEND(SDNode *N); |
| 181 | SDOperand PromoteOperand_TRUNCATE(SDNode *N); |
| 182 | SDOperand PromoteOperand_FP_EXTEND(SDNode *N); |
| 183 | SDOperand PromoteOperand_FP_ROUND(SDNode *N); |
| 184 | SDOperand PromoteOperand_INT_TO_FP(SDNode *N); |
| 185 | SDOperand PromoteOperand_SELECT(SDNode *N, unsigned OpNo); |
| 186 | SDOperand PromoteOperand_BRCOND(SDNode *N, unsigned OpNo); |
| 187 | SDOperand PromoteOperand_BR_CC(SDNode *N, unsigned OpNo); |
| 188 | SDOperand PromoteOperand_SETCC(SDNode *N, unsigned OpNo); |
| 189 | SDOperand PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo); |
| 190 | |
| 191 | void PromoteSetCCOperands(SDOperand &LHS,SDOperand &RHS, ISD::CondCode Code); |
| 192 | |
| 193 | //===--------------------------------------------------------------------===// |
| 194 | // Expansion Support: LegalizeTypesExpand.cpp |
| 195 | //===--------------------------------------------------------------------===// |
| 196 | |
| 197 | void GetExpandedOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); |
| 198 | void SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi); |
| 199 | |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 200 | // Result Expansion. |
| 201 | void ExpandResult(SDNode *N, unsigned ResNo); |
| 202 | void ExpandResult_UNDEF (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 203 | void ExpandResult_Constant (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 204 | void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 205 | void ExpandResult_MERGE_VALUES(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 206 | void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 207 | void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 208 | void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 209 | void ExpandResult_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 210 | void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 211 | void ExpandResult_LOAD (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 212 | |
| 213 | void ExpandResult_Logical (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 214 | void ExpandResult_BSWAP (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 215 | void ExpandResult_ADDSUB (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 216 | void ExpandResult_ADDSUBC (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 217 | void ExpandResult_ADDSUBE (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 218 | void ExpandResult_SELECT (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 219 | void ExpandResult_SELECT_CC (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 220 | void ExpandResult_MUL (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 221 | void ExpandResult_Shift (SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 222 | |
| 223 | void ExpandShiftByConstant(SDNode *N, unsigned Amt, |
| 224 | SDOperand &Lo, SDOperand &Hi); |
| 225 | bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 226 | |
Chris Lattner | 7514646 | 2007-12-08 21:59:32 +0000 | [diff] [blame] | 227 | // Operand Expansion. |
| 228 | bool ExpandOperand(SDNode *N, unsigned OperandNo); |
| 229 | SDOperand ExpandOperand_TRUNCATE(SDNode *N); |
| 230 | SDOperand ExpandOperand_BIT_CONVERT(SDNode *N); |
| 231 | SDOperand ExpandOperand_UINT_TO_FP(SDOperand Source, MVT::ValueType DestTy); |
| 232 | SDOperand ExpandOperand_SINT_TO_FP(SDOperand Source, MVT::ValueType DestTy); |
| 233 | SDOperand ExpandOperand_EXTRACT_ELEMENT(SDNode *N); |
| 234 | SDOperand ExpandOperand_SETCC(SDNode *N); |
| 235 | SDOperand ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo); |
| 236 | |
| 237 | void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS, |
| 238 | ISD::CondCode &CCCode); |
| 239 | |
| 240 | //===--------------------------------------------------------------------===// |
| 241 | // Scalarization Support: LegalizeTypesScalarize.cpp |
| 242 | //===--------------------------------------------------------------------===// |
| 243 | |
| 244 | SDOperand GetScalarizedOp(SDOperand Op) { |
| 245 | SDOperand &ScalarOp = ScalarizedNodes[Op]; |
| 246 | RemapNode(ScalarOp); |
| 247 | assert(ScalarOp.Val && "Operand wasn't scalarized?"); |
| 248 | return ScalarOp; |
| 249 | } |
| 250 | void SetScalarizedOp(SDOperand Op, SDOperand Result); |
| 251 | |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 252 | // Result Vector Scalarization: <1 x ty> -> ty. |
| 253 | void ScalarizeResult(SDNode *N, unsigned OpNo); |
| 254 | SDOperand ScalarizeRes_UNDEF(SDNode *N); |
| 255 | SDOperand ScalarizeRes_LOAD(LoadSDNode *N); |
| 256 | SDOperand ScalarizeRes_BinOp(SDNode *N); |
| 257 | SDOperand ScalarizeRes_UnaryOp(SDNode *N); |
| 258 | SDOperand ScalarizeRes_FPOWI(SDNode *N); |
| 259 | SDOperand ScalarizeRes_VECTOR_SHUFFLE(SDNode *N); |
| 260 | SDOperand ScalarizeRes_BIT_CONVERT(SDNode *N); |
| 261 | SDOperand ScalarizeRes_SELECT(SDNode *N); |
| 262 | |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 263 | // Operand Vector Scalarization: <1 x ty> -> ty. |
| 264 | bool ScalarizeOperand(SDNode *N, unsigned OpNo); |
| 265 | SDOperand ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N, unsigned OpNo); |
| 266 | |
Chris Lattner | 13c6a17 | 2007-12-08 22:37:41 +0000 | [diff] [blame] | 267 | //===--------------------------------------------------------------------===// |
| 268 | // Vector Splitting Support: LegalizeTypesSplit.cpp |
| 269 | //===--------------------------------------------------------------------===// |
| 270 | |
| 271 | void GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); |
| 272 | void SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi); |
| 273 | |
| 274 | // Result Vector Splitting: <128 x ty> -> 2 x <64 x ty>. |
| 275 | void SplitResult(SDNode *N, unsigned OpNo); |
Chris Lattner | 697b53e | 2007-12-08 23:08:49 +0000 | [diff] [blame] | 276 | |
| 277 | void SplitRes_UNDEF(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 278 | void SplitRes_LOAD(LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); |
Chris Lattner | eeaad40 | 2007-12-08 23:58:27 +0000 | [diff] [blame] | 279 | void SplitRes_BUILD_PAIR(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 280 | void SplitRes_INSERT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 281 | void SplitRes_VECTOR_SHUFFLE(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 282 | |
| 283 | void SplitRes_BUILD_VECTOR(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 284 | void SplitRes_CONCAT_VECTORS(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 285 | void SplitRes_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 286 | void SplitRes_UnOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
Chris Lattner | 697b53e | 2007-12-08 23:08:49 +0000 | [diff] [blame] | 287 | void SplitRes_BinOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
Chris Lattner | eeaad40 | 2007-12-08 23:58:27 +0000 | [diff] [blame] | 288 | void SplitRes_FPOWI(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
| 289 | void SplitRes_SELECT(SDNode *N, SDOperand &Lo, SDOperand &Hi); |
Chris Lattner | 13c6a17 | 2007-12-08 22:37:41 +0000 | [diff] [blame] | 290 | |
| 291 | // Operand Vector Scalarization: <128 x ty> -> 2 x <64 x ty>. |
| 292 | bool SplitOperand(SDNode *N, unsigned OpNo); |
| 293 | |
Chris Lattner | 0097555 | 2007-12-09 00:06:19 +0000 | [diff] [blame] | 294 | SDOperand SplitOp_STORE(StoreSDNode *N, unsigned OpNo); |
| 295 | SDOperand SplitOp_RET(SDNode *N, unsigned OpNo); |
Chris Lattner | dff67f5 | 2007-12-08 20:16:06 +0000 | [diff] [blame] | 296 | }; |
| 297 | |
| 298 | } // end namespace llvm. |
| 299 | |
| 300 | #endif |