LegalizeTypes.h revision 4fc4fd657d4266059dac3849133a3a351b03d99d
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 PromoteInteger, // Replace this integer type with a larger one. 64 ExpandInteger, // Split this integer type into two of half the size. 65 SoftenFloat, // 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 SoftenFloat; 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 /// SoftenedFloats - For floating point nodes converted to integers of 123 /// the same size, this map indicates the converted value to use. 124 DenseMap<SDOperand, SDOperand> SoftenedFloats; 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 147public: 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 170private: 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 GetSoftenedFloat(SDOperand Op) { 325 SDOperand &SoftenedOp = SoftenedFloats[Op]; 326 RemapNode(SoftenedOp); 327 assert(SoftenedOp.Val && "Operand wasn't converted to integer?"); 328 return SoftenedOp; 329 } 330 void SetSoftenedFloat(SDOperand Op, SDOperand Result); 331 332 // Result Float to Integer Conversion. 333 void SoftenFloatResult(SDNode *N, unsigned OpNo); 334 SDOperand SoftenFloatRes_BIT_CONVERT(SDNode *N); 335 SDOperand SoftenFloatRes_BUILD_PAIR(SDNode *N); 336 SDOperand SoftenFloatRes_ConstantFP(ConstantFPSDNode *N); 337 SDOperand SoftenFloatRes_FADD(SDNode *N); 338 SDOperand SoftenFloatRes_FCOPYSIGN(SDNode *N); 339 SDOperand SoftenFloatRes_FMUL(SDNode *N); 340 SDOperand SoftenFloatRes_FSUB(SDNode *N); 341 SDOperand SoftenFloatRes_LOAD(SDNode *N); 342 SDOperand SoftenFloatRes_XINT_TO_FP(SDNode *N); 343 344 // Operand Float to Integer Conversion. 345 bool SoftenFloatOperand(SDNode *N, unsigned OpNo); 346 SDOperand SoftenFloatOp_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 430