LegalizeTypes.h revision 4ac8ecc756bd6829ca06c4289548d3eed31c3fa7
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 26namespace 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/// 40class VISIBILITY_HIDDEN DAGTypeLegalizer { 41 TargetLowering &TLI; 42 SelectionDAG &DAG; 43public: 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 }; 60private: 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 FloatToInt, // Convert a floating point type to an integer of the same size. 66 Scalarize, // Replace this one-element vector type with its element type. 67 Split // This vector type should be split into smaller vectors. 68 }; 69 70 /// ValueTypeActions - This is a bitvector that contains two bits for each 71 /// simple value type, where the two bits correspond to the LegalizeAction 72 /// enum from TargetLowering. This can be queried with "getTypeAction(VT)". 73 TargetLowering::ValueTypeActionImpl ValueTypeActions; 74 75 /// getTypeAction - Return how we should legalize values of this type, either 76 /// it is already legal, or we need to promote it to a larger integer type, or 77 /// we need to expand it into multiple registers of a smaller integer type, or 78 /// we need to scalarize a one-element vector type into the element type, or 79 /// we need to split a vector type into smaller vector types. 80 LegalizeAction getTypeAction(MVT::ValueType VT) const { 81 switch (ValueTypeActions.getTypeAction(VT)) { 82 default: 83 assert(false && "Unknown legalize action!"); 84 case TargetLowering::Legal: 85 return Legal; 86 case TargetLowering::Promote: 87 return Promote; 88 case TargetLowering::Expand: 89 // Expand can mean 90 // 1) split scalar in half, 2) convert a float to an integer, 91 // 3) scalarize a single-element vector, 4) split a vector in two. 92 if (!MVT::isVector(VT)) { 93 if (MVT::getSizeInBits(VT) == 94 MVT::getSizeInBits(TLI.getTypeToTransformTo(VT))) 95 return FloatToInt; 96 else 97 return Expand; 98 } else if (MVT::getVectorNumElements(VT) == 1) { 99 return Scalarize; 100 } else { 101 return Split; 102 } 103 } 104 } 105 106 /// isTypeLegal - Return true if this type is legal on this target. 107 bool isTypeLegal(MVT::ValueType VT) const { 108 return ValueTypeActions.getTypeAction(VT) == TargetLowering::Legal; 109 } 110 111 /// PromotedNodes - For nodes that are below legal width, this map indicates 112 /// what promoted value to use. 113 DenseMap<SDOperandImpl, SDOperand> PromotedNodes; 114 115 /// ExpandedNodes - For nodes that need to be expanded this map indicates 116 /// which operands are the expanded version of the input. 117 DenseMap<SDOperandImpl, std::pair<SDOperand, SDOperand> > ExpandedNodes; 118 119 /// FloatToIntedNodes - For floating point nodes converted to integers of 120 /// the same size, this map indicates the converted value to use. 121 DenseMap<SDOperandImpl, SDOperand> FloatToIntedNodes; 122 123 /// ScalarizedNodes - For nodes that are <1 x ty>, this map indicates the 124 /// scalar value of type 'ty' to use. 125 DenseMap<SDOperandImpl, SDOperand> ScalarizedNodes; 126 127 /// SplitNodes - For nodes that need to be split this map indicates 128 /// which operands are the expanded version of the input. 129 DenseMap<SDOperandImpl, std::pair<SDOperand, SDOperand> > SplitNodes; 130 131 /// ReplacedNodes - For nodes that have been replaced with another, 132 /// indicates the replacement node to use. 133 DenseMap<SDOperandImpl, SDOperand> ReplacedNodes; 134 135 /// Worklist - This defines a worklist of nodes to process. In order to be 136 /// pushed onto this worklist, all operands of a node must have already been 137 /// processed. 138 SmallVector<SDNode*, 128> Worklist; 139 140public: 141 explicit DAGTypeLegalizer(SelectionDAG &dag) 142 : TLI(dag.getTargetLoweringInfo()), DAG(dag), 143 ValueTypeActions(TLI.getValueTypeActions()) { 144 assert(MVT::LAST_VALUETYPE <= 32 && 145 "Too many value types for ValueTypeActions to hold!"); 146 } 147 148 void run(); 149 150 /// ReanalyzeNode - Recompute the NodeID and correct processed operands 151 /// for the specified node, adding it to the worklist if ready. 152 void ReanalyzeNode(SDNode *N) { 153 N->setNodeId(NewNode); 154 AnalyzeNewNode(N); 155 } 156 157private: 158 void AnalyzeNewNode(SDNode *&N); 159 160 void ReplaceValueWith(SDOperand From, SDOperand To); 161 void ReplaceNodeWith(SDNode *From, SDNode *To); 162 163 void RemapNode(SDOperand &N); 164 165 // Common routines. 166 SDOperand BitConvertToInteger(SDOperand Op); 167 SDOperand CreateStackStoreLoad(SDOperand Op, MVT::ValueType DestVT); 168 SDOperand JoinIntegers(SDOperand Lo, SDOperand Hi); 169 void SplitInteger(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 170 void SplitInteger(SDOperand Op, MVT::ValueType LoVT, MVT::ValueType HiVT, 171 SDOperand &Lo, SDOperand &Hi); 172 173 //===--------------------------------------------------------------------===// 174 // Promotion Support: LegalizeTypesPromote.cpp 175 //===--------------------------------------------------------------------===// 176 177 SDOperand GetPromotedOp(SDOperand Op) { 178 SDOperand &PromotedOp = PromotedNodes[Op]; 179 RemapNode(PromotedOp); 180 assert(PromotedOp.Val && "Operand wasn't promoted?"); 181 return PromotedOp; 182 } 183 void SetPromotedOp(SDOperand Op, SDOperand Result); 184 185 /// GetPromotedZExtOp - Get a promoted operand and zero extend it to the final 186 /// size. 187 SDOperand GetPromotedZExtOp(SDOperand Op) { 188 MVT::ValueType OldVT = Op.getValueType(); 189 Op = GetPromotedOp(Op); 190 return DAG.getZeroExtendInReg(Op, OldVT); 191 } 192 193 // Result Promotion. 194 void PromoteResult(SDNode *N, unsigned ResNo); 195 SDOperand PromoteResult_BIT_CONVERT(SDNode *N); 196 SDOperand PromoteResult_BUILD_PAIR(SDNode *N); 197 SDOperand PromoteResult_Constant(SDNode *N); 198 SDOperand PromoteResult_CTLZ(SDNode *N); 199 SDOperand PromoteResult_CTPOP(SDNode *N); 200 SDOperand PromoteResult_CTTZ(SDNode *N); 201 SDOperand PromoteResult_EXTRACT_VECTOR_ELT(SDNode *N); 202 SDOperand PromoteResult_FP_ROUND(SDNode *N); 203 SDOperand PromoteResult_FP_TO_XINT(SDNode *N); 204 SDOperand PromoteResult_INT_EXTEND(SDNode *N); 205 SDOperand PromoteResult_LOAD(LoadSDNode *N); 206 SDOperand PromoteResult_SDIV(SDNode *N); 207 SDOperand PromoteResult_SELECT (SDNode *N); 208 SDOperand PromoteResult_SELECT_CC(SDNode *N); 209 SDOperand PromoteResult_SETCC(SDNode *N); 210 SDOperand PromoteResult_SHL(SDNode *N); 211 SDOperand PromoteResult_SimpleIntBinOp(SDNode *N); 212 SDOperand PromoteResult_SRA(SDNode *N); 213 SDOperand PromoteResult_SRL(SDNode *N); 214 SDOperand PromoteResult_TRUNCATE(SDNode *N); 215 SDOperand PromoteResult_UDIV(SDNode *N); 216 SDOperand PromoteResult_UNDEF(SDNode *N); 217 218 // Operand Promotion. 219 bool PromoteOperand(SDNode *N, unsigned OperandNo); 220 SDOperand PromoteOperand_ANY_EXTEND(SDNode *N); 221 SDOperand PromoteOperand_BUILD_PAIR(SDNode *N); 222 SDOperand PromoteOperand_BR_CC(SDNode *N, unsigned OpNo); 223 SDOperand PromoteOperand_BRCOND(SDNode *N, unsigned OpNo); 224 SDOperand PromoteOperand_BUILD_VECTOR(SDNode *N); 225 SDOperand PromoteOperand_FP_EXTEND(SDNode *N); 226 SDOperand PromoteOperand_FP_ROUND(SDNode *N); 227 SDOperand PromoteOperand_INT_TO_FP(SDNode *N); 228 SDOperand PromoteOperand_INSERT_VECTOR_ELT(SDNode *N, unsigned OpNo); 229 SDOperand PromoteOperand_MEMBARRIER(SDNode *N); 230 SDOperand PromoteOperand_RET(SDNode *N, unsigned OpNo); 231 SDOperand PromoteOperand_SELECT(SDNode *N, unsigned OpNo); 232 SDOperand PromoteOperand_SETCC(SDNode *N, unsigned OpNo); 233 SDOperand PromoteOperand_SIGN_EXTEND(SDNode *N); 234 SDOperand PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo); 235 SDOperand PromoteOperand_TRUNCATE(SDNode *N); 236 SDOperand PromoteOperand_ZERO_EXTEND(SDNode *N); 237 238 void PromoteSetCCOperands(SDOperand &LHS,SDOperand &RHS, ISD::CondCode Code); 239 240 //===--------------------------------------------------------------------===// 241 // Expansion Support: LegalizeTypesExpand.cpp 242 //===--------------------------------------------------------------------===// 243 244 void GetExpandedOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 245 void SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi); 246 247 // Result Expansion. 248 void ExpandResult(SDNode *N, unsigned ResNo); 249 void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi); 250 void ExpandResult_AssertZext (SDNode *N, SDOperand &Lo, SDOperand &Hi); 251 void ExpandResult_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 252 void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi); 253 void ExpandResult_Constant (SDNode *N, SDOperand &Lo, SDOperand &Hi); 254 void ExpandResult_CTLZ (SDNode *N, SDOperand &Lo, SDOperand &Hi); 255 void ExpandResult_CTPOP (SDNode *N, SDOperand &Lo, SDOperand &Hi); 256 void ExpandResult_CTTZ (SDNode *N, SDOperand &Lo, SDOperand &Hi); 257 void ExpandResult_EXTRACT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 258 void ExpandResult_LOAD (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); 259 void ExpandResult_MERGE_VALUES(SDNode *N, SDOperand &Lo, SDOperand &Hi); 260 void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); 261 void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi); 262 void ExpandResult_TRUNCATE (SDNode *N, SDOperand &Lo, SDOperand &Hi); 263 void ExpandResult_UNDEF (SDNode *N, SDOperand &Lo, SDOperand &Hi); 264 void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); 265 266 void ExpandResult_Logical (SDNode *N, SDOperand &Lo, SDOperand &Hi); 267 void ExpandResult_BSWAP (SDNode *N, SDOperand &Lo, SDOperand &Hi); 268 void ExpandResult_ADDSUB (SDNode *N, SDOperand &Lo, SDOperand &Hi); 269 void ExpandResult_ADDSUBC (SDNode *N, SDOperand &Lo, SDOperand &Hi); 270 void ExpandResult_ADDSUBE (SDNode *N, SDOperand &Lo, SDOperand &Hi); 271 void ExpandResult_SELECT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 272 void ExpandResult_SELECT_CC (SDNode *N, SDOperand &Lo, SDOperand &Hi); 273 void ExpandResult_MUL (SDNode *N, SDOperand &Lo, SDOperand &Hi); 274 void ExpandResult_Shift (SDNode *N, SDOperand &Lo, SDOperand &Hi); 275 276 void ExpandShiftByConstant(SDNode *N, unsigned Amt, 277 SDOperand &Lo, SDOperand &Hi); 278 bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi); 279 280 // Operand Expansion. 281 bool ExpandOperand(SDNode *N, unsigned OperandNo); 282 SDOperand ExpandOperand_BIT_CONVERT(SDNode *N); 283 SDOperand ExpandOperand_BR_CC(SDNode *N); 284 SDOperand ExpandOperand_BUILD_VECTOR(SDNode *N); 285 SDOperand ExpandOperand_EXTRACT_ELEMENT(SDNode *N); 286 SDOperand ExpandOperand_SETCC(SDNode *N); 287 SDOperand ExpandOperand_SINT_TO_FP(SDOperand Source, MVT::ValueType DestTy); 288 SDOperand ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo); 289 SDOperand ExpandOperand_TRUNCATE(SDNode *N); 290 SDOperand ExpandOperand_UINT_TO_FP(SDOperand Source, MVT::ValueType DestTy); 291 292 void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS, 293 ISD::CondCode &CCCode); 294 295 //===--------------------------------------------------------------------===// 296 // Float to Integer Conversion Support: LegalizeTypesFloatToInt.cpp 297 //===--------------------------------------------------------------------===// 298 299 SDOperand GetIntegerOp(SDOperand Op) { 300 SDOperand &IntegerOp = FloatToIntedNodes[Op]; 301 RemapNode(IntegerOp); 302 assert(IntegerOp.Val && "Operand wasn't converted to integer?"); 303 return IntegerOp; 304 } 305 void SetIntegerOp(SDOperand Op, SDOperand Result); 306 307 // Result Float to Integer Conversion. 308 void FloatToIntResult(SDNode *N, unsigned OpNo); 309 SDOperand FloatToIntRes_BIT_CONVERT(SDNode *N); 310 SDOperand FloatToIntRes_BUILD_PAIR(SDNode *N); 311 SDOperand FloatToIntRes_FCOPYSIGN(SDNode *N); 312 SDOperand FloatToIntRes_LOAD(SDNode *N); 313 314 // Operand Float to Integer Conversion. 315 bool FloatToIntOperand(SDNode *N, unsigned OpNo); 316 SDOperand FloatToIntOp_BIT_CONVERT(SDNode *N); 317 318 //===--------------------------------------------------------------------===// 319 // Scalarization Support: LegalizeTypesScalarize.cpp 320 //===--------------------------------------------------------------------===// 321 322 SDOperand GetScalarizedOp(SDOperand Op) { 323 SDOperand &ScalarOp = ScalarizedNodes[Op]; 324 RemapNode(ScalarOp); 325 assert(ScalarOp.Val && "Operand wasn't scalarized?"); 326 return ScalarOp; 327 } 328 void SetScalarizedOp(SDOperand Op, SDOperand Result); 329 330 // Result Vector Scalarization: <1 x ty> -> ty. 331 void ScalarizeResult(SDNode *N, unsigned OpNo); 332 SDOperand ScalarizeRes_BinOp(SDNode *N); 333 SDOperand ScalarizeRes_UnaryOp(SDNode *N); 334 335 SDOperand ScalarizeRes_BIT_CONVERT(SDNode *N); 336 SDOperand ScalarizeRes_FPOWI(SDNode *N); 337 SDOperand ScalarizeRes_INSERT_VECTOR_ELT(SDNode *N); 338 SDOperand ScalarizeRes_LOAD(LoadSDNode *N); 339 SDOperand ScalarizeRes_SELECT(SDNode *N); 340 SDOperand ScalarizeRes_UNDEF(SDNode *N); 341 SDOperand ScalarizeRes_VECTOR_SHUFFLE(SDNode *N); 342 343 // Operand Vector Scalarization: <1 x ty> -> ty. 344 bool ScalarizeOperand(SDNode *N, unsigned OpNo); 345 SDOperand ScalarizeOp_BIT_CONVERT(SDNode *N); 346 SDOperand ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N); 347 SDOperand ScalarizeOp_STORE(StoreSDNode *N, unsigned OpNo); 348 349 //===--------------------------------------------------------------------===// 350 // Vector Splitting Support: LegalizeTypesSplit.cpp 351 //===--------------------------------------------------------------------===// 352 353 void GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 354 void SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi); 355 356 // Result Vector Splitting: <128 x ty> -> 2 x <64 x ty>. 357 void SplitResult(SDNode *N, unsigned OpNo); 358 359 void SplitRes_UNDEF(SDNode *N, SDOperand &Lo, SDOperand &Hi); 360 void SplitRes_LOAD(LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); 361 void SplitRes_BUILD_PAIR(SDNode *N, SDOperand &Lo, SDOperand &Hi); 362 void SplitRes_INSERT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 363 void SplitRes_VECTOR_SHUFFLE(SDNode *N, SDOperand &Lo, SDOperand &Hi); 364 365 void SplitRes_BUILD_VECTOR(SDNode *N, SDOperand &Lo, SDOperand &Hi); 366 void SplitRes_CONCAT_VECTORS(SDNode *N, SDOperand &Lo, SDOperand &Hi); 367 void SplitRes_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 368 void SplitRes_UnOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); 369 void SplitRes_BinOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); 370 void SplitRes_FPOWI(SDNode *N, SDOperand &Lo, SDOperand &Hi); 371 void SplitRes_SELECT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 372 373 // Operand Vector Splitting: <128 x ty> -> 2 x <64 x ty>. 374 bool SplitOperand(SDNode *N, unsigned OpNo); 375 376 SDOperand SplitOp_BIT_CONVERT(SDNode *N); 377 SDOperand SplitOp_EXTRACT_SUBVECTOR(SDNode *N); 378 SDOperand SplitOp_EXTRACT_VECTOR_ELT(SDNode *N); 379 SDOperand SplitOp_RET(SDNode *N, unsigned OpNo); 380 SDOperand SplitOp_STORE(StoreSDNode *N, unsigned OpNo); 381 SDOperand SplitOp_VECTOR_SHUFFLE(SDNode *N, unsigned OpNo); 382 383public: 384 void SanityCheck(SDNode *N); 385}; 386 387} // end namespace llvm. 388 389#endif 390